gopls/go/callgraph/vta/internal/trie/bits

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	"math/rand"
12	"testing"
13	)
14
15	func TestMask(t *testing.T) {
16	for _, c := range []struct {
17	p prefix
18	b bitpos
19	want prefix
20	}{
21	{
22	p: 0b00001000,
23	b: 0b00000100,
24	want: 0b00001011,
25	}, {
26	p: 0b01011011,
27	b: 0b00000000,
28	want: ^prefix(0),
29	}, {
30	p: 0b01011011,
31	b: 0b00000001,
32	want: 0b01011010,
33	}, {
34	p: 0b01011011,
35	b: 0b00000010,
36	want: 0b01011001,
37	}, {
38	p: 0b01011011,
39	b: 0b00000100,
40	want: 0b01011011,
41	}, {
42	p: 0b01011011,
43	b: 0b00001000,
44	want: 0b01010111,
45	}, {
46	p: 0b01011011,
47	b: 0b00010000,
48	want: 0b01001111,
49	}, {
50	p: 0b01011011,
51	b: 0b00100000,
52	want: 0b01011111,
53	}, {
54	p: 0b01011011,
55	b: 0b01000000,
56	want: 0b00111111,
57	}, {
58	p: 0b01011011,
59	b: 0b01000000,
60	want: 0b00111111,
61	}, {
62	p: 0b01011011,
63	b: 0b10000000,
64	want: 0b01111111,
65	},
66	} {
67	if got := mask(c.p, c.b); got != c.want {
68	t.Errorf("mask(%#b,%#b) got %#b. want %#b", c.p, c.b, got, c.want)
69	}
70	}
71	}
72
73	func TestMaskImpotent(t *testing.T) {
74	// test mask(mask(p, b), b) == mask(p,b)
75	for _, p := range []prefix{
76	0b0, 0b1, 0b100, ^prefix(0b0), ^prefix(0b10),
77	} {
78	for _, b := range []bitpos{
79	0, 0b1, 1 << 2, 1 << 63,
80	} {
81	once := mask(p, b)
82	twice := mask(once, b)
83	if once != twice {
84	t.Errorf("mask(mask(%#b,%#b), %#b) != mask(%#b,%#b) got %#b. want %#b",
85	p, b, b, p, b, twice, once)
86	}
87	}
88	}
89	}
90
91	func TestMatchPrefix(t *testing.T) {
92	for _, c := range []struct {
93	k prefix
94	p prefix
95	b bitpos
96	}{
97	{
98	k: 0b1000,
99	p: 0b1011,
100	b: 0b0100,
101	}, {
102	k: 0b1001,
103	p: 0b1011,
104	b: 0b0100,
105	}, {
106	k: 0b1010,
107	p: 0b1011,
108	b: 0b0100,
109	}, {
110	k: 0b1011,
111	p: 0b1011,
112	b: 0b0100,
113	}, {
114	k: 0b1100,
115	p: 0b1011,
116	b: 0b0100,
117	}, {
118	k: 0b1101,
119	p: 0b1011,
120	b: 0b0100,
121	}, {
122	k: 0b1110,
123	p: 0b1011,
124	b: 0b0100,
125	}, {
126	k: 0b1111,
127	p: 0b1011,
128	b: 0b0100,
129	},
130	} {
131	if !matchPrefix(c.k, c.p, c.b) {
132	t.Errorf("matchPrefix(%#b, %#b,%#b) should be true", c.k, c.p, c.b)
133	}
134	}
135	}
136
137	func TestNotMatchPrefix(t *testing.T) {
138	for _, c := range []struct {
139	k prefix
140	p prefix
141	b bitpos
142	}{
143	{
144	k: 0b0000,
145	p: 0b1011,
146	b: 0b0100,
147	}, {
148	k: 0b0010,
149	p: 0b1011,
150	b: 0b0100,
151	},
152	} {
153	if matchPrefix(c.k, c.p, c.b) {
154	t.Errorf("matchPrefix(%#b, %#b,%#b) should be false", c.k, c.p, c.b)
155	}
156	}
157	}
158
159	func TestBranchingBit(t *testing.T) {
160	for _, c := range []struct {
161	x prefix
162	y prefix
163	want bitpos
164	}{
165	{
166	x: 0b0000,
167	y: 0b1011,
168	want: 0b1000,
169	}, {
170	x: 0b1010,
171	y: 0b1011,
172	want: 0b0001,
173	}, {
174	x: 0b1011,
175	y: 0b1111,
176	want: 0b0100,
177	}, {
178	x: 0b1011,
179	y: 0b1001,
180	want: 0b0010,
181	},
182	} {
183	if got := branchingBit(c.x, c.y); got != c.want {
184	t.Errorf("branchingBit(%#b, %#b,) is not expected value. got %#b want %#b",
185	c.x, c.y, got, c.want)
186	}
187	}
188	}
189
190	func TestZeroBit(t *testing.T) {
191	for _, c := range []struct {
192	k prefix
193	b bitpos
194	}{
195	{
196	k: 0b1000,
197	b: 0b0100,
198	}, {
199	k: 0b1001,
200	b: 0b0100,
201	}, {
202	k: 0b1010,
203	b: 0b0100,
204	},
205	} {
206	if !zeroBit(c.k, c.b) {
207	t.Errorf("zeroBit(%#b, %#b) should be true", c.k, c.b)
208	}
209	}
210	}
211	func TestZeroBitFails(t *testing.T) {
212	for _, c := range []struct {
213	k prefix
214	b bitpos
215	}{
216	{
217	k: 0b1000,
218	b: 0b1000,
219	}, {
220	k: 0b1001,
221	b: 0b0001,
222	}, {
223	k: 0b1010,
224	b: 0b0010,
225	}, {
226	k: 0b1011,
227	b: 0b0001,
228	},
229	} {
230	if zeroBit(c.k, c.b) {
231	t.Errorf("zeroBit(%#b, %#b) should be false", c.k, c.b)
232	}
233	}
234	}
235
236	func TestOrd(t *testing.T) {
237	a := bitpos(0b0010)
238	b := bitpos(0b1000)
239	if ord(a, b) {
240	t.Errorf("ord(%#b, %#b) should be false", a, b)
241	}
242	if !ord(b, a) {
243	t.Errorf("ord(%#b, %#b) should be true", b, a)
244	}
245	if ord(a, a) {
246	t.Errorf("ord(%#b, %#b) should be false", a, a)
247	}
248	if !ord(a, 0) {
249	t.Errorf("ord(%#b, %#b) should be true", a, 0)
250	}
251	}
252
253	func TestPrefixesOverlapLemma(t *testing.T) {
254	// test
255	// mask(p, fbb) == mask(q, fbb)
256	// iff
257	// m > n && matchPrefix(q, p, m) or (note: big endian encoding)
258	// m < n && matchPrefix(p, q, n) or (note: big endian encoding)
259	// m ==n && p == q
260
261	// Case 1: mask(p, fbb) == mask(q, fbb) => m > n && matchPrefix(q, p, m)
262	m, n := bitpos(1<<2), bitpos(1<<1)
263	p, q := mask(0b100, m), mask(0b010, n)
264	if !(prefixesOverlap(p, m, q, n) && m > n && matchPrefix(q, p, m)) {
265	t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
266	p, m, q, n)
267	}
268	// Case 2: mask(p, fbb) == mask(q, fbb) => m < n && matchPrefix(p, q, n)
269	m, n = bitpos(1<<2), bitpos(1<<3)
270	p, q = mask(0b100, m), mask(0b1000, n)
271	if !(prefixesOverlap(p, m, q, n) && m < n && matchPrefix(p, q, n)) {
272	t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
273	p, m, q, n)
274	}
275	// Case 3: mask(p, fbb) == mask(q, fbb) => m < n && matchPrefix(p, q, n)
276	m, n = bitpos(1<<2), bitpos(1<<2)
277	p, q = mask(0b100, m), mask(0b001, n)
278	if !(prefixesOverlap(p, m, q, n) && m == n && p == q) {
279	t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
280	p, m, q, n)
281	}
282	// Case 4: mask(p, fbb) != mask(q, fbb)
283	m, n = bitpos(1<<1), bitpos(1<<1)
284	p, q = mask(0b100, m), mask(0b001, n)
285	if prefixesOverlap(p, m, q, n) \|\|
286	(m > n && matchPrefix(q, p, m)) \|\|
287	(m < n && matchPrefix(p, q, n)) \|\|
288	(m == n && p == q) {
289	t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold",
290	p, m, q, n)
291	}
292
293	// Do a few more random cases
294	r := rand.New(rand.NewSource(123))
295	N := 2000
296	for i := 0; i < N; i++ {
297	m := bitpos(1 << (r.Uint64() % (64 + 1)))
298	n := bitpos(1 << (r.Uint64() % (64 + 1)))
299
300	p := mask(prefix(r.Uint64()), m)
301	q := mask(prefix(r.Uint64()), n)
302
303	lhs := prefixesOverlap(p, m, q, n)
304	rhs := (m > n && matchPrefix(q, p, m)) \|\|
305	(m < n && matchPrefix(p, q, n)) \|\|
306	(m == n && p == q)
307
308	if lhs != rhs {
309	t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) != <lemma> got %v. want %v",
310	p, m, q, n, lhs, rhs)
311	}
312	}
313	}
314