index_test.gno
10.40 Kb · 367 lines
1package index
2
3import (
4 "testing"
5
6 "gno.land/p/moul/kit/store/v0"
7 "gno.land/p/nt/uassert/v0"
8 "gno.land/p/nt/urequire/v0"
9)
10
11func ids(ns ...uint64) []store.ID {
12 out := make([]store.ID, len(ns))
13 for i, n := range ns {
14 out[i] = store.ID(n)
15 }
16 return out
17}
18
19func equalIDs(t *testing.T, want, got []store.ID) {
20 t.Helper()
21 urequire.Equal(t, len(want), len(got))
22 for i := range want {
23 uassert.Equal(t, want[i].String(), got[i].String())
24 }
25}
26
27func TestZeroValueIsUsable(t *testing.T) {
28 var ix Index
29 uassert.Equal(t, 0, ix.Keys())
30 uassert.Equal(t, 0, ix.Len())
31 uassert.False(t, ix.Has("gno"))
32 uassert.Equal(t, 0, ix.Count("gno"))
33 uassert.Equal(t, 0, len(ix.Lookup("gno")))
34 _, ok := ix.First("gno")
35 uassert.False(t, ok)
36 uassert.False(t, ix.Remove("gno", 1))
37 uassert.Equal(t, 0, ix.RemoveKey("gno"))
38 uassert.False(t, ix.Each(func(string, []store.ID) bool { return true }))
39
40 urequire.NoError(t, ix.Add("gno", 1))
41 uassert.Equal(t, 1, ix.Keys())
42}
43
44// The whole point of sorting the ids: Lookup must depend on the SET of ids, not
45// on the order they arrived in, or two realms that indexed the same records in
46// a different order render differently.
47func TestLookupDoesNotDependOnInsertionOrder(t *testing.T) {
48 forward, reverse := New(), New()
49 for _, n := range []uint64{3, 1, 2} {
50 urequire.NoError(t, forward.Add("gno", store.ID(n)))
51 }
52 for _, n := range []uint64{2, 1, 3} {
53 urequire.NoError(t, reverse.Add("gno", store.ID(n)))
54 }
55 equalIDs(t, ids(1, 2, 3), forward.Lookup("gno"))
56 equalIDs(t, ids(1, 2, 3), reverse.Lookup("gno"))
57}
58
59func TestAddIsIdempotentForTheSamePair(t *testing.T) {
60 ix := New()
61 urequire.NoError(t, ix.Add("gno", 7))
62 urequire.NoError(t, ix.Add("gno", 7))
63 equalIDs(t, ids(7), ix.Lookup("gno"))
64 uassert.Equal(t, 1, ix.Len())
65 uassert.Equal(t, 1, ix.Keys())
66}
67
68func TestAddRefusals(t *testing.T) {
69 for _, tc := range []struct {
70 name string
71 key string
72 id store.ID
73 want error
74 }{
75 {"empty key", "", 1, ErrEmptyKey},
76 {"zero id", "gno", 0, ErrZeroID},
77 } {
78 t.Run(tc.name, func(t *testing.T) {
79 ix := New()
80 err := ix.Add(tc.key, tc.id)
81 urequire.ErrorIs(t, err, tc.want)
82 uassert.Equal(t, 0, ix.Len())
83 })
84 }
85}
86
87func TestUniqueRefusesASecondID(t *testing.T) {
88 ix := Unique()
89 uassert.True(t, ix.IsUnique())
90 urequire.NoError(t, ix.Add("moul", 1))
91
92 err := ix.Add("moul", 2)
93 urequire.ErrorIs(t, err, ErrDuplicateKey)
94 equalIDs(t, ids(1), ix.Lookup("moul"))
95 uassert.Equal(t, 1, ix.Len())
96
97 // Re-adding the SAME pair is still a no-op, not a duplicate: a realm
98 // re-running a write must not be punished for it.
99 urequire.NoError(t, ix.Add("moul", 1))
100 uassert.Equal(t, 1, ix.Len())
101}
102
103// Keys and Len answer different questions and the difference is the fan-out,
104// which is what the index actually costs.
105func TestKeysAndLenDiffer(t *testing.T) {
106 ix := New()
107 urequire.NoError(t, ix.Add("gno", 1))
108 urequire.NoError(t, ix.Add("gno", 2))
109 urequire.NoError(t, ix.Add("go", 3))
110 uassert.Equal(t, 2, ix.Keys())
111 uassert.Equal(t, 3, ix.Len())
112 uassert.Equal(t, 2, ix.Count("gno"))
113 uassert.Equal(t, 1, ix.Count("go"))
114 uassert.Equal(t, 0, ix.Count("rust"))
115}
116
117func TestRemoveDropsTheKeyWithItsLastID(t *testing.T) {
118 ix := New()
119 urequire.NoError(t, ix.Add("gno", 1))
120 urequire.NoError(t, ix.Add("gno", 2))
121
122 uassert.True(t, ix.Remove("gno", 1))
123 uassert.True(t, ix.Has("gno"))
124 equalIDs(t, ids(2), ix.Lookup("gno"))
125
126 uassert.True(t, ix.Remove("gno", 2))
127 uassert.False(t, ix.Has("gno"))
128 uassert.Equal(t, 0, ix.Keys())
129 uassert.Equal(t, 0, ix.Len())
130
131 uassert.False(t, ix.Remove("gno", 2))
132}
133
134func TestRemoveKey(t *testing.T) {
135 ix := New()
136 urequire.NoError(t, ix.Add("gno", 1))
137 urequire.NoError(t, ix.Add("gno", 2))
138 urequire.NoError(t, ix.Add("go", 3))
139
140 uassert.Equal(t, 2, ix.RemoveKey("gno"))
141 uassert.Equal(t, 1, ix.Keys())
142 uassert.Equal(t, 1, ix.Len())
143 uassert.Equal(t, 0, ix.RemoveKey("gno"))
144}
145
146// A returned slice that is the stored one makes every caller a writer: an
147// assignment into it corrupts the index with no write path having been called.
148func TestLookupHandsOutACopy(t *testing.T) {
149 ix := New()
150 urequire.NoError(t, ix.Add("gno", 1))
151 urequire.NoError(t, ix.Add("gno", 2))
152
153 got := ix.Lookup("gno")
154 got[0] = store.ID(999)
155 equalIDs(t, ids(1, 2), ix.Lookup("gno"))
156}
157
158func TestEachIsAscendingAndStops(t *testing.T) {
159 ix := New()
160 for _, k := range []string{"go", "gno", "rust"} {
161 urequire.NoError(t, ix.Add(k, 1))
162 }
163
164 var seen []string
165 uassert.False(t, ix.Each(func(k string, _ []store.ID) bool {
166 seen = append(seen, k)
167 return false
168 }))
169 urequire.Equal(t, 3, len(seen))
170 uassert.Equal(t, "gno", seen[0])
171 uassert.Equal(t, "go", seen[1])
172 uassert.Equal(t, "rust", seen[2])
173
174 var first string
175 uassert.True(t, ix.Each(func(k string, _ []store.ID) bool {
176 first = k
177 return true
178 }))
179 uassert.Equal(t, "gno", first)
180}
181
182func TestEachHandsOutACopy(t *testing.T) {
183 ix := New()
184 urequire.NoError(t, ix.Add("gno", 1))
185 ix.Each(func(_ string, got []store.ID) bool {
186 got[0] = store.ID(999)
187 return true
188 })
189 equalIDs(t, ids(1), ix.Lookup("gno"))
190}
191
192func TestPage(t *testing.T) {
193 ix := New()
194 for _, k := range []string{"a", "b", "c", "d", "e"} {
195 urequire.NoError(t, ix.Add(k, 1))
196 }
197 for _, tc := range []struct {
198 name string
199 page int
200 size int
201 want []string
202 }{
203 {"first", 1, 2, []string{"a", "b"}},
204 {"second", 2, 2, []string{"c", "d"}},
205 {"last, short", 3, 2, []string{"e"}},
206 {"past the end", 4, 2, nil},
207 {"page zero", 0, 2, nil},
208 {"size zero", 1, 0, nil},
209 {"negative page", -1, 2, nil},
210 } {
211 t.Run(tc.name, func(t *testing.T) {
212 got := ix.Page(tc.page, tc.size)
213 urequire.Equal(t, len(tc.want), len(got))
214 for i := range tc.want {
215 uassert.Equal(t, tc.want[i], got[i].Key)
216 }
217 })
218 }
219}
220
221// Pages is what a page picker divides by, so it is never 0.
222func TestPagesIsNeverZero(t *testing.T) {
223 ix := New()
224 uassert.Equal(t, 1, ix.Pages(10))
225 uassert.Equal(t, 1, ix.Pages(0))
226 uassert.Equal(t, 1, ix.Pages(-1))
227
228 for _, k := range []string{"a", "b", "c"} {
229 urequire.NoError(t, ix.Add(k, 1))
230 }
231 uassert.Equal(t, 2, ix.Pages(2))
232 uassert.Equal(t, 1, ix.Pages(3))
233 uassert.Equal(t, 3, ix.Pages(1))
234}
235
236func TestFirst(t *testing.T) {
237 ix := New()
238 urequire.NoError(t, ix.Add("gno", 9))
239 urequire.NoError(t, ix.Add("gno", 4))
240
241 got, ok := ix.First("gno")
242 urequire.True(t, ok)
243 uassert.Equal(t, "4", got.String())
244
245 _, ok = ix.First("missing")
246 uassert.False(t, ok)
247}
248
249// Many ids under one key is the case this package exists for, so the binary
250// search has to hold at a size where a linear scan would still look fine.
251func TestManyIDsUnderOneKey(t *testing.T) {
252 ix := New()
253 for n := uint64(64); n >= 1; n-- {
254 urequire.NoError(t, ix.Add("gno", store.ID(n)))
255 }
256 uassert.Equal(t, 64, ix.Count("gno"))
257 uassert.Equal(t, 1, ix.Keys())
258
259 got := ix.Lookup("gno")
260 urequire.Equal(t, 64, len(got))
261 for i, id := range got {
262 uassert.Equal(t, store.ID(i+1).String(), id.String())
263 }
264}
265
266// maxInt is the largest int, which is where unchecked arithmetic in Page and
267// Pages goes wrong.
268const maxInt = int(^uint(0) >> 1)
269
270// A removed id must drop the old backing array, not merely shorten it.
271//
272// In gno a slice is ONE persisted object, and the deposit comes back when the
273// object is dropped and at no other time (EFFECTIVE_GNO.md section 2.12).
274// Shortening in place keeps the peak allocation charged until the whole key
275// goes, so a key that grew to 1,000 ids and shrank to 1 would still be paying
276// for 1,000.
277//
278// Not observable through the API, so this reads the entry directly: same
279// package, and the invariant is worth more than the encapsulation.
280func TestRemoveReleasesTheBackingArray(t *testing.T) {
281 ix := New()
282 for n := uint64(1); n <= 16; n++ {
283 urequire.NoError(t, ix.Add("gno", store.ID(n)))
284 }
285 for n := uint64(1); n <= 15; n++ {
286 uassert.True(t, ix.Remove("gno", store.ID(n)))
287 }
288
289 e, _ := ix.s.tree.Get("gno").(*entry)
290 urequire.True(t, e != nil)
291 uassert.Equal(t, 1, len(e.ids))
292 uassert.Equal(t, 1, cap(e.ids),
293 "the shrunk bucket still owns its peak allocation, so the deposit never comes back")
294}
295
296// Page's contract is that a page past the end is nil. Unchecked
297// (page-1)*size wraps negative at the limit, and bptree.IterateByOffset
298// normalises a negative offset to 0, so the caller silently gets page 1.
299func TestPageDoesNotWrapAtTheIntegerLimit(t *testing.T) {
300 ix := New()
301 for _, k := range []string{"a", "b", "c"} {
302 urequire.NoError(t, ix.Add(k, 1))
303 }
304 uassert.Equal(t, 0, len(ix.Page(maxInt, 2)),
305 "a page past the end is nil, including when the offset would overflow")
306 uassert.Equal(t, 0, len(ix.Page(maxInt/2+2, 2)))
307}
308
309// A huge size must not reserve a huge slice for three keys.
310func TestPageCapsItsAllocationToWhatExists(t *testing.T) {
311 ix := New()
312 for _, k := range []string{"a", "b", "c"} {
313 urequire.NoError(t, ix.Add(k, 1))
314 }
315 got := ix.Page(1, maxInt)
316 urequire.Equal(t, 3, len(got))
317 uassert.True(t, cap(got) <= 3, "the capacity follows the keys, not the requested size")
318}
319
320// Pages documents "at least 1". The ceiling n+size-1 wraps when size is the
321// limit, and the division then returns 0.
322func TestPagesNeverReturnsZeroAtTheIntegerLimit(t *testing.T) {
323 ix := New()
324 urequire.NoError(t, ix.Add("a", 1))
325 urequire.NoError(t, ix.Add("b", 1))
326 uassert.Equal(t, 1, ix.Pages(maxInt))
327}
328
329// An Index is a handle. A copy taken after the first write must see every
330// later write through either copy, or Len (a counter) and Keys (the tree)
331// disagree about what the index holds.
332func TestCopiesAfterTheFirstWriteShareOneIndex(t *testing.T) {
333 var a Index
334 urequire.NoError(t, a.Add("a", 1))
335 b := a
336 urequire.NoError(t, b.Add("b", 2))
337 uassert.Equal(t, 2, a.Keys())
338 uassert.Equal(t, 2, a.Len(), "the copy wrote a pair the original does not count")
339 uassert.True(t, b.Remove("a", 1))
340 uassert.Equal(t, 1, a.Len())
341
342 u := *Unique()
343 v := u
344 urequire.NoError(t, v.Add("k", 1))
345 uassert.ErrorIs(t, u.Add("k", 2), ErrDuplicateKey)
346 uassert.Equal(t, 1, u.Len())
347}
348
349// Every out-of-range page is nil, including the one that starts exactly at
350// the end and the first page of an index that has been emptied.
351func TestPagePastTheEndIsAlwaysNil(t *testing.T) {
352 ix := New()
353 for _, k := range []string{"a", "b", "c", "d"} {
354 urequire.NoError(t, ix.Add(k, 1))
355 }
356 uassert.True(t, ix.Page(2, 2) != nil)
357 uassert.True(t, ix.Page(3, 2) == nil, "a page starting exactly at the end is past the end")
358 uassert.True(t, ix.Page(4, 2) == nil)
359
360 for _, k := range []string{"a", "b", "c", "d"} {
361 uassert.Equal(t, 1, ix.RemoveKey(k))
362 }
363 uassert.True(t, ix.Page(1, 2) == nil, "an emptied index has no first page")
364
365 var zero Index
366 uassert.True(t, zero.Page(1, 2) == nil)
367}
