store_test.gno
10.77 Kb · 372 lines
1package store
2
3import (
4 "strconv"
5 "strings"
6 "testing"
7
8 "gno.land/p/nt/uassert/v0"
9)
10
11func TestZeroValueIsUsable(t *testing.T) {
12 var s Store
13 uassert.Equal(t, 0, s.Len())
14 uassert.Equal(t, uint64(0), uint64(s.LastID()))
15 uassert.Equal(t, uint64(1), uint64(s.Add("first")))
16 uassert.Equal(t, 1, s.Len())
17}
18
19func TestAddAssignsSequentialIDsFromOne(t *testing.T) {
20 s := New()
21 for want := uint64(1); want <= 5; want++ {
22 uassert.Equal(t, want, uint64(s.Add("v"+strconv.FormatUint(want, 10))))
23 }
24 uassert.Equal(t, 5, s.Len())
25 uassert.Equal(t, uint64(5), uint64(s.LastID()))
26}
27
28func TestGetHasMustGet(t *testing.T) {
29 s := New()
30 id := s.Add("hello")
31
32 got, ok := s.Get(id)
33 uassert.True(t, ok, "live id is found")
34 uassert.Equal(t, "hello", got.(string))
35 uassert.True(t, s.Has(id), "Has agrees with Get")
36 uassert.Equal(t, "hello", s.MustGet(id).(string))
37
38 _, ok = s.Get(ID(2))
39 uassert.False(t, ok, "unassigned id misses")
40 _, ok = s.Get(ID(0))
41 uassert.False(t, ok, "the zero id always misses")
42 uassert.False(t, s.Has(ID(0)), "the zero id is never present")
43}
44
45// A nil value at a live id must still read as present. avl.Tree.Get alone
46// cannot tell those apart, which is why Get consults Has.
47func TestNilValueIsDistinguishableFromAbsent(t *testing.T) {
48 s := New()
49 id := s.Add(nil)
50
51 v, ok := s.Get(id)
52 uassert.True(t, ok, "a stored nil is present")
53 uassert.Nil(t, v, "and reads back as nil")
54 uassert.Equal(t, 1, s.Len())
55}
56
57func TestMustGetPanicsNamingTheEntry(cur realm, t *testing.T) {
58 s := New()
59 s.Add("only")
60 uassert.PanicsWithMessage(t, cur, "store: no entry #7", func() { s.MustGet(ID(7)) })
61 uassert.NotPanics(t, cur, func() { s.MustGet(ID(1)) })
62}
63
64// A labelled store keeps the realm's own wording, so porting one does not
65// trade "game not found" for a generic message.
66func TestNamedStoreUsesItsLabelInThePanic(cur realm, t *testing.T) {
67 s := Named("game")
68 s.Add("only")
69 uassert.PanicsWithMessage(t, cur, "game #7 not found", func() { s.MustGet(ID(7)) })
70 uassert.NotPanics(t, cur, func() { s.MustGet(ID(1)) })
71
72 // The label changes nothing else.
73 uassert.Equal(t, uint64(1), uint64(s.LastID()))
74 uassert.Equal(t, 1, s.Len())
75}
76
77func TestSetReplacesInPlace(t *testing.T) {
78 s := New()
79 id := s.Add("before")
80
81 uassert.True(t, s.Set(id, "after"), "Set reports the replacement")
82 uassert.Equal(t, "after", s.MustGet(id).(string))
83 uassert.Equal(t, 1, s.Len(), "replacing does not grow the store")
84 uassert.Equal(t, uint64(1), uint64(s.LastID()), "replacing does not move the counter")
85}
86
87func TestRemoveDoesNotRecycleIDs(t *testing.T) {
88 s := New()
89 a := s.Add("a")
90 s.Add("b")
91
92 v, ok := s.Remove(a)
93 uassert.True(t, ok, "removing a live id succeeds")
94 uassert.Equal(t, "a", v.(string))
95 uassert.Equal(t, 1, s.Len())
96
97 _, ok = s.Remove(a)
98 uassert.False(t, ok, "removing twice is a miss, not a panic")
99
100 // The next Add continues the history rather than refilling the hole.
101 uassert.Equal(t, uint64(3), uint64(s.Add("c")))
102}
103
104func TestParseID(t *testing.T) {
105 cases := []struct {
106 name string
107 in string
108 want ID
109 ok bool
110 }{
111 {"plain", "7", 7, true},
112 {"leading zeros", "007", 7, true},
113 {"max uint64", "18446744073709551615", ID(18446744073709551615), true},
114 {"empty", "", 0, false},
115 {"zero is never assigned", "0", 0, false},
116 {"negative", "-1", 0, false},
117 {"signed positive", "+1", 0, false},
118 {"decimal point", "1.0", 0, false},
119 {"not a number", "abc", 0, false},
120 {"trailing space", "7 ", 0, false},
121 {"overflows uint64", "18446744073709551616", 0, false},
122 }
123 for _, tc := range cases {
124 got, ok := ParseID(tc.in)
125 uassert.Equal(t, tc.ok, ok, tc.name+": ok")
126 uassert.Equal(t, uint64(tc.want), uint64(got), tc.name+": value")
127 }
128}
129
130// The round trip a realm actually performs: render an id into a path, take it
131// back off the path, look the entry up.
132func TestIDRoundTripsThroughAPath(t *testing.T) {
133 s := New()
134 id := s.Add("entry")
135 for i := 0; i < 20; i++ {
136 id = s.Add("entry")
137 }
138
139 parsed, ok := ParseID(id.String())
140 uassert.True(t, ok, "the rendered id parses back")
141 uassert.Equal(t, uint64(id), uint64(parsed))
142 uassert.Equal(t, "entry", s.MustGet(parsed).(string))
143}
144
145func TestKeyIsFixedWidthAndOrdered(t *testing.T) {
146 uassert.Equal(t, 8, len(ID(1).Key()), "every key is 8 bytes")
147 uassert.Equal(t, 8, len(ID(18446744073709551615).Key()), "including the largest")
148
149 // Byte order is numeric order, which is the whole point.
150 prev := ID(0).Key()
151 for _, n := range []uint64{1, 9, 10, 99, 100, 999999, 1000000, 999999999999, 1000000000000, 18446744073709551615} {
152 k := ID(n).Key()
153 uassert.True(t, prev < k, "keys ascend at "+strconv.FormatUint(n, 10))
154 prev = k
155 }
156}
157
158// padWidth is the shape sixteen realm files carry, reproduced so the defect it
159// causes is asserted rather than described. The widths in the tree are 6
160// (asciiart), 12 (most) and 16 (guestbook).
161func padWidth(n uint64, width int) string {
162 s := strconv.FormatUint(n, 10)
163 if len(s) >= width {
164 return s
165 }
166 return strings.Repeat("0", width-len(s)) + s
167}
168
169// The ceiling: one entry past the chosen width, decimal keys stop sorting
170// numerically. store's keys do not have a width to outgrow.
171func TestOrderSurvivesThePaddingCeiling(t *testing.T) {
172 cases := []struct {
173 name string
174 width int
175 lo, hi uint64
176 }{
177 {"asciiart, width 6", 6, 999999, 1000000},
178 {"the width 12 majority", 12, 999999999999, 1000000000000},
179 {"guestbook, width 16", 16, 9999999999999999, 10000000000000000},
180 }
181 for _, tc := range cases {
182 // The hand-rolled key inverts: the larger id sorts first.
183 uassert.True(t, padWidth(tc.hi, tc.width) < padWidth(tc.lo, tc.width),
184 tc.name+": the padded key is expected to invert here")
185
186 // The store key does not.
187 uassert.True(t, ID(tc.lo).Key() < ID(tc.hi).Key(), tc.name+": store keys stay ordered")
188
189 // And iteration follows.
190 s := New()
191 s.Set(ID(tc.hi), "hi")
192 s.Set(ID(tc.lo), "lo")
193 var order []string
194 s.Each(func(id ID, v any) { order = append(order, v.(string)) })
195 uassert.Equal(t, "lo,hi", strings.Join(order, ","), tc.name+": iteration is numeric")
196 }
197}
198
199// timecapsule's variant calls strings.Repeat without the len guard, so past
200// the width it panics instead of mis-sorting: the realm stops accepting
201// writes. Asserted here because it is the reason this is a correctness fix and
202// not a tidy-up.
203func TestUnguardedPadPanicsPastItsWidth(cur realm, t *testing.T) {
204 unguarded := func(n uint64) string {
205 return strings.Repeat("0", 12-len(strconv.FormatUint(n, 10))) + strconv.FormatUint(n, 10)
206 }
207 uassert.NotPanics(t, cur, func() { unguarded(999999999999) })
208 uassert.PanicsContains(t, cur, "negative", func() { unguarded(1000000000000) })
209 uassert.NotPanics(t, cur, func() { ID(1000000000000).Key() })
210}
211
212func TestEachVisitsEverythingInOrder(t *testing.T) {
213 s := New()
214 for i := 1; i <= 5; i++ {
215 s.Add(strconv.Itoa(i))
216 }
217
218 var fwd, rev []string
219 s.Each(func(id ID, v any) { fwd = append(fwd, id.String()+"="+v.(string)) })
220 s.EachReverse(func(id ID, v any) { rev = append(rev, id.String()+"="+v.(string)) })
221
222 uassert.Equal(t, "1=1,2=2,3=3,4=4,5=5", strings.Join(fwd, ","))
223 uassert.Equal(t, "5=5,4=4,3=3,2=2,1=1", strings.Join(rev, ","))
224}
225
226func TestEachOnAnEmptyStoreIsANoOp(t *testing.T) {
227 s := New()
228 calls := 0
229 s.Each(func(id ID, v any) { calls++ })
230 s.EachReverse(func(id ID, v any) { calls++ })
231 uassert.Equal(t, 0, calls)
232 uassert.Equal(t, 0, len(s.Page(1, 10)))
233 uassert.Equal(t, 0, s.Pages(10))
234}
235
236// True means stop, the same as avl.IterCbFn, so a callback keeps its meaning
237// when it moves between this package and a raw tree.
238func TestEachUntilStopsOnTrue(t *testing.T) {
239 s := New()
240 for i := 1; i <= 5; i++ {
241 s.Add(strconv.Itoa(i))
242 }
243
244 var seen []string
245 stopped := s.EachUntil(func(id ID, v any) bool {
246 seen = append(seen, v.(string))
247 return id == 3
248 })
249 uassert.True(t, stopped, "it reports stopping early")
250 uassert.Equal(t, "1,2,3", strings.Join(seen, ","))
251
252 seen = nil
253 stopped = s.EachReverseUntil(func(id ID, v any) bool {
254 seen = append(seen, v.(string))
255 return id == 4
256 })
257 uassert.True(t, stopped)
258 uassert.Equal(t, "5,4", strings.Join(seen, ","))
259
260 stopped = s.EachUntil(func(id ID, v any) bool { return false })
261 uassert.False(t, stopped, "running to the end is not stopping early")
262}
263
264func TestPageIsOneBased(t *testing.T) {
265 s := New()
266 for i := 1; i <= 7; i++ {
267 s.Add(strconv.Itoa(i))
268 }
269
270 cases := []struct {
271 name string
272 page, size int
273 want string
274 }{
275 {"first page", 1, 3, "1,2,3"},
276 {"second page", 2, 3, "4,5,6"},
277 {"short last page", 3, 3, "7"},
278 {"past the end", 4, 3, ""},
279 {"far past the end", 99, 3, ""},
280 {"whole store in one page", 1, 100, "1,2,3,4,5,6,7"},
281 {"page 0 is not page 1", 0, 3, ""},
282 {"negative page", -1, 3, ""},
283 {"size 0", 1, 0, ""},
284 {"negative size", 1, -3, ""},
285 }
286 for _, tc := range cases {
287 var got []string
288 for _, e := range s.Page(tc.page, tc.size) {
289 got = append(got, e.Value.(string))
290 }
291 uassert.Equal(t, tc.want, strings.Join(got, ","), tc.name)
292 }
293}
294
295func TestPageReverseStartsWithTheNewest(t *testing.T) {
296 s := New()
297 for i := 1; i <= 7; i++ {
298 s.Add(strconv.Itoa(i))
299 }
300
301 cases := []struct {
302 name string
303 page, size int
304 want string
305 }{
306 {"newest first", 1, 3, "7,6,5"},
307 {"second page", 2, 3, "4,3,2"},
308 {"short last page", 3, 3, "1"},
309 {"past the end", 4, 3, ""},
310 }
311 for _, tc := range cases {
312 var got []string
313 for _, e := range s.PageReverse(tc.page, tc.size) {
314 got = append(got, e.Value.(string))
315 }
316 uassert.Equal(t, tc.want, strings.Join(got, ","), tc.name)
317 }
318}
319
320func TestPageCarriesTheID(t *testing.T) {
321 s := New()
322 s.Add("a")
323 s.Add("b")
324
325 p := s.Page(1, 10)
326 uassert.Equal(t, 2, len(p))
327 uassert.Equal(t, uint64(1), uint64(p[0].ID))
328 uassert.Equal(t, uint64(2), uint64(p[1].ID))
329
330 r := s.PageReverse(1, 10)
331 uassert.Equal(t, uint64(2), uint64(r[0].ID))
332 uassert.Equal(t, uint64(1), uint64(r[1].ID))
333}
334
335func TestPages(t *testing.T) {
336 s := New()
337 uassert.Equal(t, 0, s.Pages(10), "an empty store has no pages")
338
339 for i := 1; i <= 10; i++ {
340 s.Add("v")
341 }
342 uassert.Equal(t, 1, s.Pages(10), "an exact fit is one page")
343 uassert.Equal(t, 2, s.Pages(9), "a remainder adds a page")
344 uassert.Equal(t, 10, s.Pages(1))
345 uassert.Equal(t, 0, s.Pages(0), "a size below 1 has no pages")
346 uassert.Equal(t, 0, s.Pages(-1))
347}
348
349// Paging and iteration must stay consistent after entries are removed from the
350// middle, which is where a dense-index assumption would break.
351func TestPagingAfterRemovals(t *testing.T) {
352 s := New()
353 for i := 1; i <= 6; i++ {
354 s.Add(strconv.Itoa(i))
355 }
356 s.Remove(ID(2))
357 s.Remove(ID(5))
358
359 uassert.Equal(t, 4, s.Len())
360 uassert.Equal(t, uint64(6), uint64(s.LastID()), "the counter does not rewind")
361
362 var got []string
363 s.Each(func(id ID, v any) { got = append(got, id.String()) })
364 uassert.Equal(t, "1,3,4,6", strings.Join(got, ","))
365
366 got = nil
367 for _, e := range s.Page(2, 2) {
368 got = append(got, e.ID.String())
369 }
370 uassert.Equal(t, "4,6", strings.Join(got, ","), "page 2 of the survivors")
371 uassert.Equal(t, 2, s.Pages(2))
372}
