Source file src/golang.org/x/tools/go/callgraph/vta/internal/trie/trie_test.go

Documentation: golang.org/x/tools/go/callgraph/vta/internal/trie

     1  // Copyright 2021 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:build go1.13
     6  // +build go1.13
     7  
     8  package trie
     9  
    10  import (
    11  	"reflect"
    12  	"strconv"
    13  	"testing"
    14  )
    15  
    16  func TestScope(t *testing.T) {
    17  	def := Scope{}
    18  	s0, s1 := newScope(), newScope()
    19  	if s0 == def || s1 == def {
    20  		t.Error("newScope() should never be == to the default scope")
    21  	}
    22  	if s0 == s1 {
    23  		t.Errorf("newScope() %q and %q should not be ==", s0, s1)
    24  	}
    25  	if s0.id == 0 {
    26  		t.Error("s0.id is 0")
    27  	}
    28  	if s1.id == 0 {
    29  		t.Error("s1.id is 0")
    30  	}
    31  	got := s0.String()
    32  	if _, err := strconv.Atoi(got); err != nil {
    33  		t.Errorf("scope{%s}.String() is not an int: got %s with error %s", s0, got, err)
    34  	}
    35  }
    36  
    37  func TestCollision(t *testing.T) {
    38  	var x interface{} = 1
    39  	var y interface{} = 2
    40  
    41  	if v := TakeLhs(x, y); v != x {
    42  		t.Errorf("TakeLhs(%s, %s) got %s. want %s", x, y, v, x)
    43  	}
    44  	if v := TakeRhs(x, y); v != y {
    45  		t.Errorf("TakeRhs(%s, %s) got %s. want %s", x, y, v, y)
    46  	}
    47  }
    48  
    49  func TestDefault(t *testing.T) {
    50  	def := Map{}
    51  
    52  	if def.Size() != 0 {
    53  		t.Errorf("default node has non-0 size %d", def.Size())
    54  	}
    55  	if want, got := (Scope{}), def.Scope(); got != want {
    56  		t.Errorf("default is in a non default scope (%s) from b (%s)", got, want)
    57  	}
    58  	if v, ok := def.Lookup(123); !(v == nil && !ok) {
    59  		t.Errorf("Scope{}.Lookup() = (%s, %v) not (nil, false)", v, ok)
    60  	}
    61  	if !def.Range(func(k uint64, v interface{}) bool {
    62  		t.Errorf("Scope{}.Range() called it callback on %d:%s", k, v)
    63  		return true
    64  	}) {
    65  		t.Error("Scope{}.Range() always iterates through all elements")
    66  	}
    67  
    68  	if got, want := def.String(), "{}"; got != want {
    69  		t.Errorf("Scope{}.String() got %s. want %s", got, want)
    70  	}
    71  
    72  	b := NewBuilder()
    73  	if def == b.Empty() {
    74  		t.Error("Scope{} == to an empty node from a builder")
    75  	}
    76  	if b.Clone(def) != b.Empty() {
    77  		t.Error("b.Clone(Scope{}) should equal b.Empty()")
    78  	}
    79  	if !def.DeepEqual(b.Empty()) {
    80  		t.Error("Scope{}.DeepEqual(b.Empty()) should hold")
    81  	}
    82  }
    83  
    84  func TestBuilders(t *testing.T) {
    85  	b0, b1 := NewBuilder(), NewBuilder()
    86  	if b0.Scope() == b1.Scope() {
    87  		t.Errorf("builders have the same scope %s", b0.Scope())
    88  	}
    89  
    90  	if b0.Empty() == b1.Empty() {
    91  		t.Errorf("empty nodes from different scopes are disequal")
    92  	}
    93  	if !b0.Empty().DeepEqual(b1.Empty()) {
    94  		t.Errorf("empty nodes from different scopes are not DeepEqual")
    95  	}
    96  
    97  	clone := b1.Clone(b0.Empty())
    98  	if clone != b1.Empty() {
    99  		t.Errorf("Clone() empty nodes %v != %v", clone, b1.Empty())
   100  	}
   101  }
   102  
   103  func TestEmpty(t *testing.T) {
   104  	b := NewBuilder()
   105  	e := b.Empty()
   106  	if e.Size() != 0 {
   107  		t.Errorf("empty nodes has non-0 size %d", e.Size())
   108  	}
   109  	if e.Scope() != b.Scope() {
   110  		t.Errorf("b.Empty() is in a different scope (%s) from b (%s)", e.Scope(), b.Scope())
   111  	}
   112  	if v, ok := e.Lookup(123); !(v == nil && !ok) {
   113  		t.Errorf("empty.Lookup() = (%s, %v) not (nil, false)", v, ok)
   114  	}
   115  	if l := e.n.find(123); l != nil {
   116  		t.Errorf("empty.find(123) got %v. want nil", l)
   117  	}
   118  	e.Range(func(k uint64, v interface{}) bool {
   119  		t.Errorf("empty.Range() called it callback on %d:%s", k, v)
   120  		return true
   121  	})
   122  
   123  	want := "{}"
   124  	if got := e.String(); got != want {
   125  		t.Errorf("empty.String(123) got %s. want %s", got, want)
   126  	}
   127  }
   128  
   129  func TestCreate(t *testing.T) {
   130  	// The node orders are printed in lexicographic little-endian.
   131  	b := NewBuilder()
   132  	for _, c := range []struct {
   133  		m    map[uint64]interface{}
   134  		want string
   135  	}{
   136  		{
   137  			map[uint64]interface{}{},
   138  			"{}",
   139  		},
   140  		{
   141  			map[uint64]interface{}{1: "a"},
   142  			"{1: a}",
   143  		},
   144  		{
   145  			map[uint64]interface{}{2: "b", 1: "a"},
   146  			"{1: a, 2: b}",
   147  		},
   148  		{
   149  			map[uint64]interface{}{1: "x", 4: "y", 5: "z"},
   150  			"{1: x, 4: y, 5: z}",
   151  		},
   152  	} {
   153  		m := b.Create(c.m)
   154  		if got := m.String(); got != c.want {
   155  			t.Errorf("Create(%v) got %q. want %q ", c.m, got, c.want)
   156  		}
   157  	}
   158  }
   159  
   160  func TestElems(t *testing.T) {
   161  	b := NewBuilder()
   162  	for _, orig := range []map[uint64]interface{}{
   163  		{},
   164  		{1: "a"},
   165  		{1: "a", 2: "b"},
   166  		{1: "x", 4: "y", 5: "z"},
   167  		{1: "x", 4: "y", 5: "z", 123: "abc"},
   168  	} {
   169  		m := b.Create(orig)
   170  		if elems := Elems(m); !reflect.DeepEqual(orig, elems) {
   171  			t.Errorf("Elems(%v) got %q. want %q ", m, elems, orig)
   172  		}
   173  	}
   174  }
   175  
   176  func TestRange(t *testing.T) {
   177  	b := NewBuilder()
   178  	m := b.Create(map[uint64]interface{}{1: "x", 3: "y", 5: "z", 6: "stop", 8: "a"})
   179  
   180  	calls := 0
   181  	cb := func(k uint64, v interface{}) bool {
   182  		t.Logf("visiting (%d, %v)", k, v)
   183  		calls++
   184  		return k%2 != 0 // stop after the first even number.
   185  	}
   186  	// The nodes are visited in increasing order.
   187  	all := m.Range(cb)
   188  	if all {
   189  		t.Error("expected to stop early")
   190  	}
   191  	want := 4
   192  	if calls != want {
   193  		t.Errorf("# of callbacks (%d) was expected to equal %d (1 + # of evens)",
   194  			calls, want)
   195  	}
   196  }
   197  
   198  func TestDeepEqual(t *testing.T) {
   199  	for _, m := range []map[uint64]interface{}{
   200  		{},
   201  		{1: "x"},
   202  		{1: "x", 2: "y"},
   203  	} {
   204  		l := NewBuilder().Create(m)
   205  		r := NewBuilder().Create(m)
   206  		if !l.DeepEqual(r) {
   207  			t.Errorf("Expect %v to be DeepEqual() to %v", l, r)
   208  		}
   209  	}
   210  }
   211  
   212  func TestNotDeepEqual(t *testing.T) {
   213  	for _, c := range []struct {
   214  		left  map[uint64]interface{}
   215  		right map[uint64]interface{}
   216  	}{
   217  		{
   218  			map[uint64]interface{}{1: "x"},
   219  			map[uint64]interface{}{},
   220  		},
   221  		{
   222  			map[uint64]interface{}{},
   223  			map[uint64]interface{}{1: "y"},
   224  		},
   225  		{
   226  			map[uint64]interface{}{1: "x"},
   227  			map[uint64]interface{}{1: "y"},
   228  		},
   229  		{
   230  			map[uint64]interface{}{1: "x"},
   231  			map[uint64]interface{}{1: "x", 2: "Y"},
   232  		},
   233  		{
   234  			map[uint64]interface{}{1: "x", 2: "Y"},
   235  			map[uint64]interface{}{1: "x"},
   236  		},
   237  		{
   238  			map[uint64]interface{}{1: "x", 2: "y"},
   239  			map[uint64]interface{}{1: "x", 2: "Y"},
   240  		},
   241  	} {
   242  		l := NewBuilder().Create(c.left)
   243  		r := NewBuilder().Create(c.right)
   244  		if l.DeepEqual(r) {
   245  			t.Errorf("Expect %v to be !DeepEqual() to %v", l, r)
   246  		}
   247  	}
   248  }
   249  
   250  func TestMerge(t *testing.T) {
   251  	b := NewBuilder()
   252  	for _, c := range []struct {
   253  		left  map[uint64]interface{}
   254  		right map[uint64]interface{}
   255  		want  string
   256  	}{
   257  		{
   258  			map[uint64]interface{}{},
   259  			map[uint64]interface{}{},
   260  			"{}",
   261  		},
   262  		{
   263  			map[uint64]interface{}{},
   264  			map[uint64]interface{}{1: "a"},
   265  			"{1: a}",
   266  		},
   267  		{
   268  			map[uint64]interface{}{1: "a"},
   269  			map[uint64]interface{}{},
   270  			"{1: a}",
   271  		},
   272  		{
   273  			map[uint64]interface{}{1: "a", 2: "b"},
   274  			map[uint64]interface{}{},
   275  			"{1: a, 2: b}",
   276  		},
   277  		{
   278  			map[uint64]interface{}{1: "x"},
   279  			map[uint64]interface{}{1: "y"},
   280  			"{1: x}", // default collision is left
   281  		},
   282  		{
   283  			map[uint64]interface{}{1: "x"},
   284  			map[uint64]interface{}{2: "y"},
   285  			"{1: x, 2: y}",
   286  		},
   287  		{
   288  			map[uint64]interface{}{4: "y", 5: "z"},
   289  			map[uint64]interface{}{1: "x"},
   290  			"{1: x, 4: y, 5: z}",
   291  		},
   292  		{
   293  			map[uint64]interface{}{1: "x", 5: "z"},
   294  			map[uint64]interface{}{4: "y"},
   295  			"{1: x, 4: y, 5: z}",
   296  		},
   297  		{
   298  			map[uint64]interface{}{1: "x", 4: "y"},
   299  			map[uint64]interface{}{5: "z"},
   300  			"{1: x, 4: y, 5: z}",
   301  		},
   302  		{
   303  			map[uint64]interface{}{1: "a", 4: "c"},
   304  			map[uint64]interface{}{2: "b", 5: "d"},
   305  			"{1: a, 2: b, 4: c, 5: d}",
   306  		},
   307  		{
   308  			map[uint64]interface{}{1: "a", 4: "c"},
   309  			map[uint64]interface{}{2: "b", 5 + 8: "d"},
   310  			"{1: a, 2: b, 4: c, 13: d}",
   311  		},
   312  		{
   313  			map[uint64]interface{}{2: "b", 5 + 8: "d"},
   314  			map[uint64]interface{}{1: "a", 4: "c"},
   315  			"{1: a, 2: b, 4: c, 13: d}",
   316  		},
   317  		{
   318  			map[uint64]interface{}{1: "a", 4: "c"},
   319  			map[uint64]interface{}{2: "b", 5 + 8: "d"},
   320  			"{1: a, 2: b, 4: c, 13: d}",
   321  		},
   322  		{
   323  			map[uint64]interface{}{2: "b", 5 + 8: "d"},
   324  			map[uint64]interface{}{1: "a", 4: "c"},
   325  			"{1: a, 2: b, 4: c, 13: d}",
   326  		},
   327  		{
   328  			map[uint64]interface{}{2: "b", 5 + 8: "d"},
   329  			map[uint64]interface{}{2: "", 3: "a"},
   330  			"{2: b, 3: a, 13: d}",
   331  		},
   332  
   333  		{
   334  			// crafted for `!prefixesOverlap(p, m, q, n)`
   335  			left:  map[uint64]interface{}{1: "a", 2 + 1: "b"},
   336  			right: map[uint64]interface{}{4 + 1: "c", 4 + 2: "d"},
   337  			// p: 5, m: 2 q: 1, n: 2
   338  			want: "{1: a, 3: b, 5: c, 6: d}",
   339  		},
   340  		{
   341  			// crafted for `ord(m, n) && !zeroBit(q, m)`
   342  			left:  map[uint64]interface{}{8 + 2 + 1: "a", 16 + 4: "b"},
   343  			right: map[uint64]interface{}{16 + 8 + 2 + 1: "c", 16 + 8 + 4 + 2 + 1: "d"},
   344  			// left: p: 15, m: 16
   345  			// right: q: 27, n: 4
   346  			want: "{11: a, 20: b, 27: c, 31: d}",
   347  		},
   348  		{
   349  			// crafted for `ord(n, m) && !zeroBit(p, n)`
   350  			// p: 6, m: 1 q: 5, n: 2
   351  			left:  map[uint64]interface{}{4 + 2: "b", 4 + 2 + 1: "c"},
   352  			right: map[uint64]interface{}{4: "a", 4 + 2 + 1: "dropped"},
   353  			want:  "{4: a, 6: b, 7: c}",
   354  		},
   355  	} {
   356  		l, r := b.Create(c.left), b.Create(c.right)
   357  		m := b.Merge(l, r)
   358  		if got := m.String(); got != c.want {
   359  			t.Errorf("Merge(%s, %s) got %q. want %q ", l, r, got, c.want)
   360  		}
   361  	}
   362  }
   363  
   364  func TestIntersect(t *testing.T) {
   365  	// Most of the test cases go after specific branches of intersect.
   366  	b := NewBuilder()
   367  	for _, c := range []struct {
   368  		left  map[uint64]interface{}
   369  		right map[uint64]interface{}
   370  		want  string
   371  	}{
   372  		{
   373  			left:  map[uint64]interface{}{10: "a", 39: "b"},
   374  			right: map[uint64]interface{}{10: "A", 39: "B", 75: "C"},
   375  			want:  "{10: a, 39: b}",
   376  		},
   377  		{
   378  			left:  map[uint64]interface{}{10: "a", 39: "b"},
   379  			right: map[uint64]interface{}{},
   380  			want:  "{}",
   381  		},
   382  		{
   383  			left:  map[uint64]interface{}{},
   384  			right: map[uint64]interface{}{10: "A", 39: "B", 75: "C"},
   385  			want:  "{}",
   386  		},
   387  		{ // m == n && p == q  && left.(*empty) case
   388  			left:  map[uint64]interface{}{4: 1, 6: 3, 10: 8, 15: "on left"},
   389  			right: map[uint64]interface{}{0: 8, 7: 6, 11: 0, 15: "on right"},
   390  			want:  "{15: on left}",
   391  		},
   392  		{ // m == n && p == q  && right.(*empty) case
   393  			left:  map[uint64]interface{}{0: "on left", 1: 2, 2: 3, 3: 1, 7: 3},
   394  			right: map[uint64]interface{}{0: "on right", 5: 1, 6: 8},
   395  			want:  "{0: on left}",
   396  		},
   397  		{ // m == n && p == q  &&  both left and right are not empty
   398  			left:  map[uint64]interface{}{1: "a", 2: "b", 3: "c"},
   399  			right: map[uint64]interface{}{0: "A", 1: "B", 2: "C"},
   400  			want:  "{1: a, 2: b}",
   401  		},
   402  		{ // m == n && p == q  &&  both left and right are not empty
   403  			left:  map[uint64]interface{}{1: "a", 2: "b", 3: "c"},
   404  			right: map[uint64]interface{}{0: "A", 1: "B", 2: "C"},
   405  			want:  "{1: a, 2: b}",
   406  		},
   407  		{ // !prefixesOverlap(p, m, q, n)
   408  			// p = 1, m = 2, q = 5, n = 2
   409  			left:  map[uint64]interface{}{0b001: 1, 0b011: 3},
   410  			right: map[uint64]interface{}{0b100: 4, 0b111: 7},
   411  			want:  "{}",
   412  		},
   413  		{ // ord(m, n) && zeroBit(q, m)
   414  			// p = 3, m = 4, q = 0, n = 1
   415  			left:  map[uint64]interface{}{0b010: 2, 0b101: 5},
   416  			right: map[uint64]interface{}{0b000: 0, 0b001: 1},
   417  			want:  "{}",
   418  		},
   419  
   420  		{ // ord(m, n) && !zeroBit(q, m)
   421  			// p = 29, m = 2, q = 30, n = 1
   422  			left: map[uint64]interface{}{
   423  				0b11101: "29",
   424  				0b11110: "30",
   425  			},
   426  			right: map[uint64]interface{}{
   427  				0b11110: "30 on right",
   428  				0b11111: "31",
   429  			},
   430  			want: "{30: 30}",
   431  		},
   432  		{ // ord(n, m) && zeroBit(p, n)
   433  			// p = 5, m = 2, q = 3, n = 4
   434  			left:  map[uint64]interface{}{0b000: 0, 0b001: 1},
   435  			right: map[uint64]interface{}{0b010: 2, 0b101: 5},
   436  			want:  "{}",
   437  		},
   438  		{ // default case
   439  			// p = 5, m = 2, q = 3, n = 4
   440  			left:  map[uint64]interface{}{0b100: 1, 0b110: 3},
   441  			right: map[uint64]interface{}{0b000: 8, 0b111: 6},
   442  			want:  "{}",
   443  		},
   444  	} {
   445  		l, r := b.Create(c.left), b.Create(c.right)
   446  		m := b.Intersect(l, r)
   447  		if got := m.String(); got != c.want {
   448  			t.Errorf("Intersect(%s, %s) got %q. want %q ", l, r, got, c.want)
   449  		}
   450  	}
   451  }
   452  
   453  func TestIntersectWith(t *testing.T) {
   454  	b := NewBuilder()
   455  	l := b.Create(map[uint64]interface{}{10: 2.0, 39: 32.0})
   456  	r := b.Create(map[uint64]interface{}{10: 6.0, 39: 10.0, 75: 1.0})
   457  
   458  	prodIfDifferent := func(x interface{}, y interface{}) interface{} {
   459  		if x, ok := x.(float64); ok {
   460  			if y, ok := y.(float64); ok {
   461  				if x == y {
   462  					return x
   463  				}
   464  				return x * y
   465  			}
   466  		}
   467  		return x
   468  	}
   469  
   470  	m := b.IntersectWith(prodIfDifferent, l, r)
   471  
   472  	want := "{10: %!s(float64=12), 39: %!s(float64=320)}"
   473  	if got := m.String(); got != want {
   474  		t.Errorf("IntersectWith(min, %s, %s) got %q. want %q ", l, r, got, want)
   475  	}
   476  }
   477  
   478  func TestRemove(t *testing.T) {
   479  	// Most of the test cases go after specific branches of intersect.
   480  	b := NewBuilder()
   481  	for _, c := range []struct {
   482  		m    map[uint64]interface{}
   483  		key  uint64
   484  		want string
   485  	}{
   486  		{map[uint64]interface{}{}, 10, "{}"},
   487  		{map[uint64]interface{}{10: "a"}, 10, "{}"},
   488  		{map[uint64]interface{}{39: "b"}, 10, "{39: b}"},
   489  		// Branch cases:
   490  		// !matchPrefix(kp, br.prefix, br.branching)
   491  		{map[uint64]interface{}{10: "a", 39: "b"}, 128, "{10: a, 39: b}"},
   492  		// case: left == br.left && right == br.right
   493  		{map[uint64]interface{}{10: "a", 39: "b"}, 16, "{10: a, 39: b}"},
   494  		// left updated and is empty.
   495  		{map[uint64]interface{}{10: "a", 39: "b"}, 10, "{39: b}"},
   496  		// right updated and is empty.
   497  		{map[uint64]interface{}{10: "a", 39: "b"}, 39, "{10: a}"},
   498  		// final b.mkBranch(...) case.
   499  		{map[uint64]interface{}{10: "a", 39: "b", 128: "c"}, 39, "{10: a, 128: c}"},
   500  	} {
   501  		pre := b.Create(c.m)
   502  		post := b.Remove(pre, c.key)
   503  		if got := post.String(); got != c.want {
   504  			t.Errorf("Remove(%s, %d) got %q. want %q ", pre, c.key, got, c.want)
   505  		}
   506  	}
   507  }
   508  
   509  func TestRescope(t *testing.T) {
   510  	b := NewBuilder()
   511  	l := b.Create(map[uint64]interface{}{10: "a", 39: "b"})
   512  	r := b.Create(map[uint64]interface{}{10: "A", 39: "B", 75: "C"})
   513  
   514  	b.Rescope()
   515  
   516  	m := b.Intersect(l, r)
   517  	if got, want := m.String(), "{10: a, 39: b}"; got != want {
   518  		t.Errorf("Intersect(%s, %s) got %q. want %q", l, r, got, want)
   519  	}
   520  	if m.Scope() == l.Scope() {
   521  		t.Errorf("m.Scope() = %v should not equal l.Scope() = %v", m.Scope(), l.Scope())
   522  	}
   523  	if m.Scope() == r.Scope() {
   524  		t.Errorf("m.Scope() = %v should not equal r.Scope() = %v", m.Scope(), r.Scope())
   525  	}
   526  }
   527  
   528  func TestSharing(t *testing.T) {
   529  	b := NewBuilder()
   530  	l := b.Create(map[uint64]interface{}{0: "a", 1: "b"})
   531  	r := b.Create(map[uint64]interface{}{1: "B", 2: "C"})
   532  
   533  	rleftold := r.n.(*branch).left
   534  
   535  	m := b.Merge(l, r)
   536  	if mleft := m.n.(*branch).left; mleft != l.n {
   537  		t.Errorf("unexpected value for left branch of %v. want %v got %v", m, l, mleft)
   538  	}
   539  
   540  	if rleftnow := r.n.(*branch).left; rleftnow != rleftold {
   541  		t.Errorf("r.n.(*branch).left was modified by the Merge operation. was %v now %v", rleftold, rleftnow)
   542  	}
   543  }
   544  

View as plain text