blob: c0651b0ef86531997dca302bf014846f7ec53a8c [file] [log] [blame]
// Copyright 2021 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.
//go:build go1.13
// +build go1.13
package trie
import (
"reflect"
"strconv"
"testing"
)
func TestScope(t *testing.T) {
def := Scope{}
s0, s1 := newScope(), newScope()
if s0 == def || s1 == def {
t.Error("newScope() should never be == to the default scope")
}
if s0 == s1 {
t.Errorf("newScope() %q and %q should not be ==", s0, s1)
}
if s0.id == 0 {
t.Error("s0.id is 0")
}
if s1.id == 0 {
t.Error("s1.id is 0")
}
got := s0.String()
if _, err := strconv.Atoi(got); err != nil {
t.Errorf("scope{%s}.String() is not an int: got %s with error %s", s0, got, err)
}
}
func TestCollision(t *testing.T) {
var x interface{} = 1
var y interface{} = 2
if v := TakeLhs(x, y); v != x {
t.Errorf("TakeLhs(%s, %s) got %s. want %s", x, y, v, x)
}
if v := TakeRhs(x, y); v != y {
t.Errorf("TakeRhs(%s, %s) got %s. want %s", x, y, v, y)
}
}
func TestDefault(t *testing.T) {
def := Map{}
if def.Size() != 0 {
t.Errorf("default node has non-0 size %d", def.Size())
}
if want, got := (Scope{}), def.Scope(); got != want {
t.Errorf("default is in a non default scope (%s) from b (%s)", got, want)
}
if v, ok := def.Lookup(123); !(v == nil && !ok) {
t.Errorf("Scope{}.Lookup() = (%s, %v) not (nil, false)", v, ok)
}
if !def.Range(func(k uint64, v interface{}) bool {
t.Errorf("Scope{}.Range() called it callback on %d:%s", k, v)
return true
}) {
t.Error("Scope{}.Range() always iterates through all elements")
}
if got, want := def.String(), "{}"; got != want {
t.Errorf("Scope{}.String() got %s. want %s", got, want)
}
b := NewBuilder()
if def == b.Empty() {
t.Error("Scope{} == to an empty node from a builder")
}
if b.Clone(def) != b.Empty() {
t.Error("b.Clone(Scope{}) should equal b.Empty()")
}
if !def.DeepEqual(b.Empty()) {
t.Error("Scope{}.DeepEqual(b.Empty()) should hold")
}
}
func TestBuilders(t *testing.T) {
b0, b1 := NewBuilder(), NewBuilder()
if b0.Scope() == b1.Scope() {
t.Errorf("builders have the same scope %s", b0.Scope())
}
if b0.Empty() == b1.Empty() {
t.Errorf("empty nodes from different scopes are disequal")
}
if !b0.Empty().DeepEqual(b1.Empty()) {
t.Errorf("empty nodes from different scopes are not DeepEqual")
}
clone := b1.Clone(b0.Empty())
if clone != b1.Empty() {
t.Errorf("Clone() empty nodes %v != %v", clone, b1.Empty())
}
}
func TestEmpty(t *testing.T) {
b := NewBuilder()
e := b.Empty()
if e.Size() != 0 {
t.Errorf("empty nodes has non-0 size %d", e.Size())
}
if e.Scope() != b.Scope() {
t.Errorf("b.Empty() is in a different scope (%s) from b (%s)", e.Scope(), b.Scope())
}
if v, ok := e.Lookup(123); !(v == nil && !ok) {
t.Errorf("empty.Lookup() = (%s, %v) not (nil, false)", v, ok)
}
if l := e.n.find(123); l != nil {
t.Errorf("empty.find(123) got %v. want nil", l)
}
e.Range(func(k uint64, v interface{}) bool {
t.Errorf("empty.Range() called it callback on %d:%s", k, v)
return true
})
want := "{}"
if got := e.String(); got != want {
t.Errorf("empty.String(123) got %s. want %s", got, want)
}
}
func TestCreate(t *testing.T) {
// The node orders are printed in lexicographic little-endian.
b := NewBuilder()
for _, c := range []struct {
m map[uint64]interface{}
want string
}{
{
map[uint64]interface{}{},
"{}",
},
{
map[uint64]interface{}{1: "a"},
"{1: a}",
},
{
map[uint64]interface{}{2: "b", 1: "a"},
"{1: a, 2: b}",
},
{
map[uint64]interface{}{1: "x", 4: "y", 5: "z"},
"{1: x, 4: y, 5: z}",
},
} {
m := b.Create(c.m)
if got := m.String(); got != c.want {
t.Errorf("Create(%v) got %q. want %q ", c.m, got, c.want)
}
}
}
func TestElems(t *testing.T) {
b := NewBuilder()
for _, orig := range []map[uint64]interface{}{
{},
{1: "a"},
{1: "a", 2: "b"},
{1: "x", 4: "y", 5: "z"},
{1: "x", 4: "y", 5: "z", 123: "abc"},
} {
m := b.Create(orig)
if elems := Elems(m); !reflect.DeepEqual(orig, elems) {
t.Errorf("Elems(%v) got %q. want %q ", m, elems, orig)
}
}
}
func TestRange(t *testing.T) {
b := NewBuilder()
m := b.Create(map[uint64]interface{}{1: "x", 3: "y", 5: "z", 6: "stop", 8: "a"})
calls := 0
cb := func(k uint64, v interface{}) bool {
t.Logf("visiting (%d, %v)", k, v)
calls++
return k%2 != 0 // stop after the first even number.
}
// The nodes are visited in increasing order.
all := m.Range(cb)
if all {
t.Error("expected to stop early")
}
want := 4
if calls != want {
t.Errorf("# of callbacks (%d) was expected to equal %d (1 + # of evens)",
calls, want)
}
}
func TestDeepEqual(t *testing.T) {
for _, m := range []map[uint64]interface{}{
{},
{1: "x"},
{1: "x", 2: "y"},
} {
l := NewBuilder().Create(m)
r := NewBuilder().Create(m)
if !l.DeepEqual(r) {
t.Errorf("Expect %v to be DeepEqual() to %v", l, r)
}
}
}
func TestNotDeepEqual(t *testing.T) {
for _, c := range []struct {
left map[uint64]interface{}
right map[uint64]interface{}
}{
{
map[uint64]interface{}{1: "x"},
map[uint64]interface{}{},
},
{
map[uint64]interface{}{},
map[uint64]interface{}{1: "y"},
},
{
map[uint64]interface{}{1: "x"},
map[uint64]interface{}{1: "y"},
},
{
map[uint64]interface{}{1: "x"},
map[uint64]interface{}{1: "x", 2: "Y"},
},
{
map[uint64]interface{}{1: "x", 2: "Y"},
map[uint64]interface{}{1: "x"},
},
{
map[uint64]interface{}{1: "x", 2: "y"},
map[uint64]interface{}{1: "x", 2: "Y"},
},
} {
l := NewBuilder().Create(c.left)
r := NewBuilder().Create(c.right)
if l.DeepEqual(r) {
t.Errorf("Expect %v to be !DeepEqual() to %v", l, r)
}
}
}
func TestMerge(t *testing.T) {
b := NewBuilder()
for _, c := range []struct {
left map[uint64]interface{}
right map[uint64]interface{}
want string
}{
{
map[uint64]interface{}{},
map[uint64]interface{}{},
"{}",
},
{
map[uint64]interface{}{},
map[uint64]interface{}{1: "a"},
"{1: a}",
},
{
map[uint64]interface{}{1: "a"},
map[uint64]interface{}{},
"{1: a}",
},
{
map[uint64]interface{}{1: "a", 2: "b"},
map[uint64]interface{}{},
"{1: a, 2: b}",
},
{
map[uint64]interface{}{1: "x"},
map[uint64]interface{}{1: "y"},
"{1: x}", // default collision is left
},
{
map[uint64]interface{}{1: "x"},
map[uint64]interface{}{2: "y"},
"{1: x, 2: y}",
},
{
map[uint64]interface{}{4: "y", 5: "z"},
map[uint64]interface{}{1: "x"},
"{1: x, 4: y, 5: z}",
},
{
map[uint64]interface{}{1: "x", 5: "z"},
map[uint64]interface{}{4: "y"},
"{1: x, 4: y, 5: z}",
},
{
map[uint64]interface{}{1: "x", 4: "y"},
map[uint64]interface{}{5: "z"},
"{1: x, 4: y, 5: z}",
},
{
map[uint64]interface{}{1: "a", 4: "c"},
map[uint64]interface{}{2: "b", 5: "d"},
"{1: a, 2: b, 4: c, 5: d}",
},
{
map[uint64]interface{}{1: "a", 4: "c"},
map[uint64]interface{}{2: "b", 5 + 8: "d"},
"{1: a, 2: b, 4: c, 13: d}",
},
{
map[uint64]interface{}{2: "b", 5 + 8: "d"},
map[uint64]interface{}{1: "a", 4: "c"},
"{1: a, 2: b, 4: c, 13: d}",
},
{
map[uint64]interface{}{1: "a", 4: "c"},
map[uint64]interface{}{2: "b", 5 + 8: "d"},
"{1: a, 2: b, 4: c, 13: d}",
},
{
map[uint64]interface{}{2: "b", 5 + 8: "d"},
map[uint64]interface{}{1: "a", 4: "c"},
"{1: a, 2: b, 4: c, 13: d}",
},
{
map[uint64]interface{}{2: "b", 5 + 8: "d"},
map[uint64]interface{}{2: "", 3: "a"},
"{2: b, 3: a, 13: d}",
},
{
// crafted for `!prefixesOverlap(p, m, q, n)`
left: map[uint64]interface{}{1: "a", 2 + 1: "b"},
right: map[uint64]interface{}{4 + 1: "c", 4 + 2: "d"},
// p: 5, m: 2 q: 1, n: 2
want: "{1: a, 3: b, 5: c, 6: d}",
},
{
// crafted for `ord(m, n) && !zeroBit(q, m)`
left: map[uint64]interface{}{8 + 2 + 1: "a", 16 + 4: "b"},
right: map[uint64]interface{}{16 + 8 + 2 + 1: "c", 16 + 8 + 4 + 2 + 1: "d"},
// left: p: 15, m: 16
// right: q: 27, n: 4
want: "{11: a, 20: b, 27: c, 31: d}",
},
{
// crafted for `ord(n, m) && !zeroBit(p, n)`
// p: 6, m: 1 q: 5, n: 2
left: map[uint64]interface{}{4 + 2: "b", 4 + 2 + 1: "c"},
right: map[uint64]interface{}{4: "a", 4 + 2 + 1: "dropped"},
want: "{4: a, 6: b, 7: c}",
},
} {
l, r := b.Create(c.left), b.Create(c.right)
m := b.Merge(l, r)
if got := m.String(); got != c.want {
t.Errorf("Merge(%s, %s) got %q. want %q ", l, r, got, c.want)
}
}
}
func TestIntersect(t *testing.T) {
// Most of the test cases go after specific branches of intersect.
b := NewBuilder()
for _, c := range []struct {
left map[uint64]interface{}
right map[uint64]interface{}
want string
}{
{
left: map[uint64]interface{}{10: "a", 39: "b"},
right: map[uint64]interface{}{10: "A", 39: "B", 75: "C"},
want: "{10: a, 39: b}",
},
{
left: map[uint64]interface{}{10: "a", 39: "b"},
right: map[uint64]interface{}{},
want: "{}",
},
{
left: map[uint64]interface{}{},
right: map[uint64]interface{}{10: "A", 39: "B", 75: "C"},
want: "{}",
},
{ // m == n && p == q && left.(*empty) case
left: map[uint64]interface{}{4: 1, 6: 3, 10: 8, 15: "on left"},
right: map[uint64]interface{}{0: 8, 7: 6, 11: 0, 15: "on right"},
want: "{15: on left}",
},
{ // m == n && p == q && right.(*empty) case
left: map[uint64]interface{}{0: "on left", 1: 2, 2: 3, 3: 1, 7: 3},
right: map[uint64]interface{}{0: "on right", 5: 1, 6: 8},
want: "{0: on left}",
},
{ // m == n && p == q && both left and right are not empty
left: map[uint64]interface{}{1: "a", 2: "b", 3: "c"},
right: map[uint64]interface{}{0: "A", 1: "B", 2: "C"},
want: "{1: a, 2: b}",
},
{ // m == n && p == q && both left and right are not empty
left: map[uint64]interface{}{1: "a", 2: "b", 3: "c"},
right: map[uint64]interface{}{0: "A", 1: "B", 2: "C"},
want: "{1: a, 2: b}",
},
{ // !prefixesOverlap(p, m, q, n)
// p = 1, m = 2, q = 5, n = 2
left: map[uint64]interface{}{0b001: 1, 0b011: 3},
right: map[uint64]interface{}{0b100: 4, 0b111: 7},
want: "{}",
},
{ // ord(m, n) && zeroBit(q, m)
// p = 3, m = 4, q = 0, n = 1
left: map[uint64]interface{}{0b010: 2, 0b101: 5},
right: map[uint64]interface{}{0b000: 0, 0b001: 1},
want: "{}",
},
{ // ord(m, n) && !zeroBit(q, m)
// p = 29, m = 2, q = 30, n = 1
left: map[uint64]interface{}{
0b11101: "29",
0b11110: "30",
},
right: map[uint64]interface{}{
0b11110: "30 on right",
0b11111: "31",
},
want: "{30: 30}",
},
{ // ord(n, m) && zeroBit(p, n)
// p = 5, m = 2, q = 3, n = 4
left: map[uint64]interface{}{0b000: 0, 0b001: 1},
right: map[uint64]interface{}{0b010: 2, 0b101: 5},
want: "{}",
},
{ // default case
// p = 5, m = 2, q = 3, n = 4
left: map[uint64]interface{}{0b100: 1, 0b110: 3},
right: map[uint64]interface{}{0b000: 8, 0b111: 6},
want: "{}",
},
} {
l, r := b.Create(c.left), b.Create(c.right)
m := b.Intersect(l, r)
if got := m.String(); got != c.want {
t.Errorf("Intersect(%s, %s) got %q. want %q ", l, r, got, c.want)
}
}
}
func TestIntersectWith(t *testing.T) {
b := NewBuilder()
l := b.Create(map[uint64]interface{}{10: 2.0, 39: 32.0})
r := b.Create(map[uint64]interface{}{10: 6.0, 39: 10.0, 75: 1.0})
prodIfDifferent := func(x interface{}, y interface{}) interface{} {
if x, ok := x.(float64); ok {
if y, ok := y.(float64); ok {
if x == y {
return x
}
return x * y
}
}
return x
}
m := b.IntersectWith(prodIfDifferent, l, r)
want := "{10: %!s(float64=12), 39: %!s(float64=320)}"
if got := m.String(); got != want {
t.Errorf("IntersectWith(min, %s, %s) got %q. want %q ", l, r, got, want)
}
}
func TestRemove(t *testing.T) {
// Most of the test cases go after specific branches of intersect.
b := NewBuilder()
for _, c := range []struct {
m map[uint64]interface{}
key uint64
want string
}{
{map[uint64]interface{}{}, 10, "{}"},
{map[uint64]interface{}{10: "a"}, 10, "{}"},
{map[uint64]interface{}{39: "b"}, 10, "{39: b}"},
// Branch cases:
// !matchPrefix(kp, br.prefix, br.branching)
{map[uint64]interface{}{10: "a", 39: "b"}, 128, "{10: a, 39: b}"},
// case: left == br.left && right == br.right
{map[uint64]interface{}{10: "a", 39: "b"}, 16, "{10: a, 39: b}"},
// left updated and is empty.
{map[uint64]interface{}{10: "a", 39: "b"}, 10, "{39: b}"},
// right updated and is empty.
{map[uint64]interface{}{10: "a", 39: "b"}, 39, "{10: a}"},
// final b.mkBranch(...) case.
{map[uint64]interface{}{10: "a", 39: "b", 128: "c"}, 39, "{10: a, 128: c}"},
} {
pre := b.Create(c.m)
post := b.Remove(pre, c.key)
if got := post.String(); got != c.want {
t.Errorf("Remove(%s, %d) got %q. want %q ", pre, c.key, got, c.want)
}
}
}
func TestRescope(t *testing.T) {
b := NewBuilder()
l := b.Create(map[uint64]interface{}{10: "a", 39: "b"})
r := b.Create(map[uint64]interface{}{10: "A", 39: "B", 75: "C"})
b.Rescope()
m := b.Intersect(l, r)
if got, want := m.String(), "{10: a, 39: b}"; got != want {
t.Errorf("Intersect(%s, %s) got %q. want %q", l, r, got, want)
}
if m.Scope() == l.Scope() {
t.Errorf("m.Scope() = %v should not equal l.Scope() = %v", m.Scope(), l.Scope())
}
if m.Scope() == r.Scope() {
t.Errorf("m.Scope() = %v should not equal r.Scope() = %v", m.Scope(), r.Scope())
}
}
func TestSharing(t *testing.T) {
b := NewBuilder()
l := b.Create(map[uint64]interface{}{0: "a", 1: "b"})
r := b.Create(map[uint64]interface{}{1: "B", 2: "C"})
rleftold := r.n.(*branch).left
m := b.Merge(l, r)
if mleft := m.n.(*branch).left; mleft != l.n {
t.Errorf("unexpected value for left branch of %v. want %v got %v", m, l, mleft)
}
if rleftnow := r.n.(*branch).left; rleftnow != rleftold {
t.Errorf("r.n.(*branch).left was modified by the Merge operation. was %v now %v", rleftold, rleftnow)
}
}