// Copyright 2022 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package persistent
import (
"fmt"
"maps"
"math/rand"
"reflect"
"sync/atomic"
"testing"
)
type mapEntry struct {
key int
value int
}
type validatedMap struct {
impl *Map[int, int]
expected map[int]int // current key-value mapping.
deleted map[mapEntry]int // maps deleted entries to their clock time of last deletion
seen map[mapEntry]int // maps seen entries to their clock time of last insertion
clock int
}
func TestSimpleMap(t *testing.T) {
deletedEntries := make(map[mapEntry]int)
seenEntries := make(map[mapEntry]int)
m1 := &validatedMap{
impl: new(Map[int, int]),
expected: make(map[int]int),
deleted: deletedEntries,
seen: seenEntries,
}
m3 := m1.clone()
validateRef(t, m1, m3)
m3.set(t, 8, 8)
validateRef(t, m1, m3)
m3.destroy()
assertSameMap(t, entrySet(deletedEntries), map[mapEntry]struct{}{
{key: 8, value: 8}: {},
})
validateRef(t, m1)
m1.set(t, 1, 1)
validateRef(t, m1)
m1.set(t, 2, 2)
validateRef(t, m1)
m1.set(t, 3, 3)
validateRef(t, m1)
m1.remove(t, 2)
validateRef(t, m1)
m1.set(t, 6, 6)
validateRef(t, m1)
assertSameMap(t, entrySet(deletedEntries), map[mapEntry]struct{}{
{key: 2, value: 2}: {},
{key: 8, value: 8}: {},
})
m2 := m1.clone()
validateRef(t, m1, m2)
m1.set(t, 6, 60)
validateRef(t, m1, m2)
m1.remove(t, 1)
validateRef(t, m1, m2)
gotAllocs := int(testing.AllocsPerRun(10, func() {
m1.impl.Delete(100)
m1.impl.Delete(1)
}))
wantAllocs := 0
if gotAllocs != wantAllocs {
t.Errorf("wanted %d allocs, got %d", wantAllocs, gotAllocs)
}
for i := 10; i < 14; i++ {
m1.set(t, i, i)
validateRef(t, m1, m2)
}
m1.set(t, 10, 100)
validateRef(t, m1, m2)
m1.remove(t, 12)
validateRef(t, m1, m2)
m2.set(t, 4, 4)
validateRef(t, m1, m2)
m2.set(t, 5, 5)
validateRef(t, m1, m2)
m1.destroy()
assertSameMap(t, entrySet(deletedEntries), map[mapEntry]struct{}{
{key: 2, value: 2}: {},
{key: 6, value: 60}: {},
{key: 8, value: 8}: {},
{key: 10, value: 10}: {},
{key: 10, value: 100}: {},
{key: 11, value: 11}: {},
{key: 12, value: 12}: {},
{key: 13, value: 13}: {},
})
m2.set(t, 7, 7)
validateRef(t, m2)
m2.destroy()
assertSameMap(t, entrySet(seenEntries), entrySet(deletedEntries))
}
func TestRandomMap(t *testing.T) {
deletedEntries := make(map[mapEntry]int)
seenEntries := make(map[mapEntry]int)
m := &validatedMap{
impl: new(Map[int, int]),
expected: make(map[int]int),
deleted: deletedEntries,
seen: seenEntries,
}
keys := make([]int, 0, 1000)
for i := range 1000 {
key := rand.Intn(10000)
m.set(t, key, key)
keys = append(keys, key)
if i%10 == 1 {
index := rand.Intn(len(keys))
last := len(keys) - 1
key = keys[index]
keys[index], keys[last] = keys[last], keys[index]
keys = keys[:last]
m.remove(t, key)
}
}
m.destroy()
assertSameMap(t, entrySet(seenEntries), entrySet(deletedEntries))
}
func entrySet(m map[mapEntry]int) map[mapEntry]struct{} {
set := make(map[mapEntry]struct{})
for k := range m {
set[k] = struct{}{}
}
return set
}
func TestUpdate(t *testing.T) {
deletedEntries := make(map[mapEntry]int)
seenEntries := make(map[mapEntry]int)
m1 := &validatedMap{
impl: new(Map[int, int]),
expected: make(map[int]int),
deleted: deletedEntries,
seen: seenEntries,
}
m2 := m1.clone()
m1.set(t, 1, 1)
m1.set(t, 2, 2)
m2.set(t, 2, 20)
m2.set(t, 3, 3)
m1.setAll(t, m2)
m1.destroy()
m2.destroy()
assertSameMap(t, entrySet(seenEntries), entrySet(deletedEntries))
}
func validateRef(t *testing.T, maps ...*validatedMap) {
t.Helper()
actualCountByEntry := make(map[mapEntry]int32)
nodesByEntry := make(map[mapEntry]map[*mapNode]struct{})
expectedCountByEntry := make(map[mapEntry]int32)
for i, m := range maps {
dfsRef(m.impl.root, actualCountByEntry, nodesByEntry)
dumpMap(t, fmt.Sprintf("%d:", i), m.impl.root)
}
for entry, nodes := range nodesByEntry {
expectedCountByEntry[entry] = int32(len(nodes))
}
assertSameMap(t, expectedCountByEntry, actualCountByEntry)
}
func dfsRef(node *mapNode, countByEntry map[mapEntry]int32, nodesByEntry map[mapEntry]map[*mapNode]struct{}) {
if node == nil {
return
}
entry := mapEntry{key: node.key.(int), value: node.value.value.(int)}
countByEntry[entry] = atomic.LoadInt32(&node.value.refCount)
nodes, ok := nodesByEntry[entry]
if !ok {
nodes = make(map[*mapNode]struct{})
nodesByEntry[entry] = nodes
}
nodes[node] = struct{}{}
dfsRef(node.left, countByEntry, nodesByEntry)
dfsRef(node.right, countByEntry, nodesByEntry)
}
func dumpMap(t *testing.T, prefix string, n *mapNode) {
if n == nil {
t.Logf("%s nil", prefix)
return
}
t.Logf("%s {key: %v, value: %v (ref: %v), ref: %v, weight: %v}", prefix, n.key, n.value.value, n.value.refCount, n.refCount, n.weight)
dumpMap(t, prefix+"l", n.left)
dumpMap(t, prefix+"r", n.right)
}
func (vm *validatedMap) validate(t *testing.T) {
t.Helper()
validateNode(t, vm.impl.root)
// Note: this validation may not make sense if maps were constructed using
// SetAll operations. If this proves to be problematic, remove the clock,
// deleted, and seen fields.
for key, value := range vm.expected {
entry := mapEntry{key: key, value: value}
if deleteAt := vm.deleted[entry]; deleteAt > vm.seen[entry] {
t.Fatalf("entry is deleted prematurely, key: %d, value: %d", key, value)
}
}
actualMap := make(map[int]int, len(vm.expected))
for key, value := range vm.impl.All() {
if other, ok := actualMap[key]; ok {
t.Fatalf("key is present twice, key: %d, first value: %d, second value: %d", key, value, other)
}
actualMap[key] = value
}
assertSameMap(t, actualMap, vm.expected)
}
func validateNode(t *testing.T, node *mapNode) {
if node == nil {
return
}
if node.left != nil {
if node.key.(int) < node.left.key.(int) {
t.Fatalf("left child has larger key: %v vs %v", node.left.key, node.key)
}
if node.left.weight > node.weight {
t.Fatalf("left child has larger weight: %v vs %v", node.left.weight, node.weight)
}
}
if node.right != nil {
if node.right.key.(int) < node.key.(int) {
t.Fatalf("right child has smaller key: %v vs %v", node.right.key, node.key)
}
if node.right.weight > node.weight {
t.Fatalf("right child has larger weight: %v vs %v", node.right.weight, node.weight)
}
}
validateNode(t, node.left)
validateNode(t, node.right)
}
func (vm *validatedMap) setAll(t *testing.T, other *validatedMap) {
vm.impl.SetAll(other.impl)
// Note: this is buggy because we are not updating vm.clock, vm.deleted, or
// vm.seen.
maps.Copy(vm.expected, other.expected)
vm.validate(t)
}
func (vm *validatedMap) set(t *testing.T, key, value int) {
entry := mapEntry{key: key, value: value}
vm.clock++
vm.seen[entry] = vm.clock
vm.impl.Set(key, value, func(deletedKey, deletedValue any) {
if deletedKey != key || deletedValue != value {
t.Fatalf("unexpected passed in deleted entry: %v/%v, expected: %v/%v", deletedKey, deletedValue, key, value)
}
// Not safe if closure shared between two validatedMaps.
vm.deleted[entry] = vm.clock
})
vm.expected[key] = value
vm.validate(t)
gotValue, ok := vm.impl.Get(key)
if !ok || gotValue != value {
t.Fatalf("unexpected get result after insertion, key: %v, expected: %v, got: %v (%v)", key, value, gotValue, ok)
}
}
func (vm *validatedMap) remove(t *testing.T, key int) {
vm.clock++
deleted := vm.impl.Delete(key)
if _, ok := vm.expected[key]; ok != deleted {
t.Fatalf("Delete(%d) = %t, want %t", key, deleted, ok)
}
delete(vm.expected, key)
vm.validate(t)
gotValue, ok := vm.impl.Get(key)
if ok {
t.Fatalf("unexpected get result after removal, key: %v, got: %v", key, gotValue)
}
}
func (vm *validatedMap) clone() *validatedMap {
expected := make(map[int]int, len(vm.expected))
maps.Copy(expected, vm.expected)
return &validatedMap{
impl: vm.impl.Clone(),
expected: expected,
deleted: vm.deleted,
seen: vm.seen,
}
}
func (vm *validatedMap) destroy() {
vm.impl.Destroy()
}
func assertSameMap(t *testing.T, map1, map2 any) {
t.Helper()
if !reflect.DeepEqual(map1, map2) {
t.Fatalf("different maps:\n%v\nvs\n%v", map1, map2)
}
}