index.gno
12.54 Kb · 391 lines
1// Package index is the secondary index every realm with a store was writing by
2// hand: a lookup from a key a human typed to the [store.ID]s that carry it.
3//
4// A realm keeps its records in a [gno.land/p/moul/kit/store] and answers
5// "entry 7". The moment it also has to answer "every entry tagged gno" it needs
6// a second container, and the correctness of the pair is entirely in the
7// discipline of writing both in the same function. This package owns the second
8// container and as much of that discipline as a package can.
9//
10// var notes = store.Named("note")
11// var byTag index.Index // the zero value is an empty, usable index
12//
13// func Post(cur realm, tag, body string) int64 {
14// id := notes.Add(¬e{Tag: tag, Body: body})
15// if err := byTag.Add(tag, id); err != nil {
16// panic(err) // the store write is not committed either: same frame
17// }
18// return int64(id)
19// }
20//
21// It is NOT a multi-index record store. [gno.land/p/moul/collection] is that,
22// and at n = 1,000 an update there costs 964,833 gas against the 508,977 that
23// created the record, because it re-indexes every index whether or not the
24// indexed value changed. Two containers written side by side cost a third of
25// that and the realm can see what it is paying for.
26//
27// Live demo: r/moul/x/kitindexdemo.
28package index
29
30import (
31 "errors"
32
33 "gno.land/p/moul/kit/store/v0"
34 "gno.land/p/nt/bptree/v0"
35)
36
37// Fanout is the B+ tree fanout this package uses, and 128 is not the package
38// default of 32.
39//
40// Measured against gno master 1fc4c140e on 2026-09-29, at n = 1,000 with string
41// values: fanout 128 costs 592 bytes per entry and 152,975 gas per insert,
42// against 671 and 162,161 at fanout 32, and against avl's 2,029 and 417,811.
43// Raising the fanout amortises the node objects, and nothing below it can be
44// recovered: the remaining cost is the B+ tree's per-entry value box.
45const Fanout = 128
46
47// Errors an Add can return. A /p/ package returns errors and lets the realm
48// decide whether they are fatal; every one of these is a programming error in
49// the realm rather than a value a user chose, so panicking on them is the
50// normal handling.
51var (
52 // ErrEmptyKey is returned for "". An empty key sorts before every real one
53 // and is almost always an unset field rather than a deliberate bucket, so
54 // it is refused rather than silently indexed.
55 ErrEmptyKey = errors.New("index: the key is empty")
56
57 // ErrZeroID is returned for store.ID(0), which [store.Store] never assigns,
58 // so indexing it can only produce a lookup that cannot hit.
59 ErrZeroID = errors.New("index: the id is zero")
60
61 // ErrDuplicateKey is returned by a [Unique] index asked to attach a second
62 // id to a key that already has one.
63 ErrDuplicateKey = errors.New("index: the key is already taken")
64)
65
66// Index maps a key to the ids carrying it, ordered by key.
67//
68// The zero value is an empty, usable, non-unique index: a realm declares
69// `var byTag index.Index` and writes to it, exactly as it does with a
70// [store.Store]. Use [Unique] when at most one id may carry a key.
71//
72// An Index is a handle, like the [store.Store] it sits next to: copies taken
73// after the first write, or of anything [Unique] returned, are the same index,
74// and a write through one is seen through all of them. A copy of a zero value
75// that was never written is a separate empty index.
76type Index struct {
77 s *state
78}
79
80// state is everything an Index holds, behind one pointer so that a copy of the
81// handle cannot split the tree from the counter that describes it.
82type state struct {
83 tree *bptree.BPTree
84 unique bool
85 pairs int
86}
87
88// New returns an empty index where a key may carry many ids. It is the zero
89// value, spelled out for a caller who prefers a constructor.
90func New() *Index { return &Index{} }
91
92// Unique returns an empty index where a key carries at most one id, and a
93// second [Index.Add] to the same key fails with [ErrDuplicateKey] instead of
94// appending.
95//
96// Unique is a constructor rather than a field or a setter because flipping it
97// on a populated index would have to either reject the duplicates already in it
98// or silently keep them, and both are worse than not offering the operation.
99func Unique() *Index {
100 return &Index{s: &state{tree: bptree.NewBPTreeN(Fanout), unique: true}}
101}
102
103// entry is the value stored at a key: the ids carrying it, ascending.
104//
105// A struct rather than a bare []store.ID so that a later field (a count, a
106// timestamp) does not change the stored shape, and so the slice itself is never
107// handed out by accident.
108type entry struct {
109 ids []store.ID
110}
111
112// init materialises the state. Called by every mutating method, so the zero
113// value works without a constructor. The tree is created with the state, so a
114// non-nil state always has one.
115func (ix *Index) init() {
116 if ix.s == nil {
117 ix.s = &state{tree: bptree.NewBPTreeN(Fanout)}
118 }
119}
120
121// Add attaches id to key.
122//
123// Adding a pair that is already present is a no-op and returns nil, so a realm
124// re-running a write is not punished for it. The ids under a key are kept
125// ascending, which makes [Index.Lookup] depend on the set of ids and not on the
126// order they arrived in: two realms that indexed the same records in a
127// different order render identically, and a Render whose output depends on
128// insertion history is the determinism bug this avoids.
129func (ix *Index) Add(key string, id store.ID) error {
130 if key == "" {
131 return ErrEmptyKey
132 }
133 if id == 0 {
134 return ErrZeroID
135 }
136 ix.init()
137
138 e, _ := ix.s.tree.Get(key).(*entry)
139 if e == nil {
140 ix.s.tree.Set(key, &entry{ids: []store.ID{id}})
141 ix.s.pairs++
142 return nil
143 }
144 pos, found := e.find(id)
145 if found {
146 return nil
147 }
148 if ix.s.unique {
149 return ErrDuplicateKey
150 }
151 e.ids = append(e.ids, 0)
152 copy(e.ids[pos+1:], e.ids[pos:])
153 e.ids[pos] = id
154 ix.s.tree.Set(key, e)
155 ix.s.pairs++
156 return nil
157}
158
159// Remove detaches id from key and reports whether the pair was there. A key
160// whose last id is removed is removed with it, so [Index.Keys] never counts an
161// empty bucket.
162func (ix *Index) Remove(key string, id store.ID) bool {
163 if ix.s == nil {
164 return false
165 }
166 e, _ := ix.s.tree.Get(key).(*entry)
167 if e == nil {
168 return false
169 }
170 pos, found := e.find(id)
171 if !found {
172 return false
173 }
174 ix.s.pairs--
175 if len(e.ids) == 1 {
176 ix.s.tree.Remove(key)
177 return true
178 }
179 // A fresh slice, not append(ids[:pos], ids[pos+1:]...).
180 //
181 // In gno a slice is ONE persisted object and the storage deposit comes back
182 // when that object is dropped, at no other time: shortening in place keeps
183 // the peak allocation charged until the whole key goes, so a key that grew
184 // to 1,000 ids and shrank to 1 would still be paying for 1,000. Allocating
185 // the exact size drops the old array and refunds the difference. Same O(n)
186 // as the memmove it replaces.
187 trimmed := make([]store.ID, 0, len(e.ids)-1)
188 trimmed = append(trimmed, e.ids[:pos]...)
189 trimmed = append(trimmed, e.ids[pos+1:]...)
190 e.ids = trimmed
191 ix.s.tree.Set(key, e)
192 return true
193}
194
195// RemoveKey detaches every id from key and reports how many it detached.
196func (ix *Index) RemoveKey(key string) int {
197 if ix.s == nil {
198 return 0
199 }
200 v, removed := ix.s.tree.Remove(key)
201 if !removed {
202 return 0
203 }
204 n := len(v.(*entry).ids)
205 ix.s.pairs -= n
206 return n
207}
208
209// Lookup returns the ids carrying key, ascending, or nil.
210//
211// The slice is a COPY. Handing out the stored one would make every caller a
212// writer: an append past its length would be invisible to the index, and an
213// assignment into it would corrupt the index with no write path having been
214// called. A realm that returns this value onward is returning its own data,
215// not a handle to ours.
216func (ix *Index) Lookup(key string) []store.ID {
217 if ix.s == nil {
218 return nil
219 }
220 e, _ := ix.s.tree.Get(key).(*entry)
221 if e == nil {
222 return nil
223 }
224 out := make([]store.ID, len(e.ids))
225 copy(out, e.ids)
226 return out
227}
228
229// First returns the lowest id carrying key. On a [Unique] index it is the only
230// one, which is the usual reason to call it.
231func (ix *Index) First(key string) (store.ID, bool) {
232 if ix.s == nil {
233 return 0, false
234 }
235 e, _ := ix.s.tree.Get(key).(*entry)
236 if e == nil || len(e.ids) == 0 {
237 return 0, false
238 }
239 return e.ids[0], true
240}
241
242// Has reports whether any id carries key.
243func (ix *Index) Has(key string) bool {
244 if ix.s == nil {
245 return false
246 }
247 return ix.s.tree.Has(key)
248}
249
250// Count returns how many ids carry key.
251func (ix *Index) Count(key string) int {
252 if ix.s == nil {
253 return 0
254 }
255 e, _ := ix.s.tree.Get(key).(*entry)
256 if e == nil {
257 return 0
258 }
259 return len(e.ids)
260}
261
262// Keys returns the number of distinct keys.
263func (ix *Index) Keys() int {
264 if ix.s == nil {
265 return 0
266 }
267 return ix.s.tree.Size()
268}
269
270// Len returns the number of (key, id) pairs, which is what the index actually
271// costs. It is NOT [Index.Keys], and the two differ by exactly the amount of
272// fan-out a realm has.
273func (ix *Index) Len() int {
274 if ix.s == nil {
275 return 0
276 }
277 return ix.s.pairs
278}
279
280// IsUnique reports whether this index was built by [Unique].
281func (ix *Index) IsUnique() bool { return ix.s != nil && ix.s.unique }
282
283// Each visits every key in ascending order with a copy of its ids, and stops
284// when fn returns true. It reports whether it stopped early.
285//
286// True means stop, matching bptree.IterCbFn and kit/store's EachUntil exactly,
287// so a callback moved between them keeps its meaning.
288//
289// fn must not call [Index.Add], [Index.Remove] or [Index.RemoveKey] on this
290// index. The walk is the B+ tree's own, which holds a position inside a leaf:
291// removing the key being visited shifts the next one into that slot and the
292// walk steps over it, and inserting one ahead of it is visited twice. Collect
293// what to change, then change it after Each returns.
294func (ix *Index) Each(fn func(key string, ids []store.ID) bool) bool {
295 if ix.s == nil {
296 return false
297 }
298 return ix.s.tree.Iterate("", "", func(k string, v any) bool {
299 e := v.(*entry)
300 ids := make([]store.ID, len(e.ids))
301 copy(ids, e.ids)
302 return fn(k, ids)
303 })
304}
305
306// Page returns page number page of size keys, ascending, each with a copy of
307// its ids.
308//
309// Pages are 1-based, and every out-of-range page (zero, negative, past the end,
310// any page of an empty index) returns nil rather than panicking, because the
311// page number usually arrives from a Render path and is user input. This is
312// NOT [store.Store.Page], which returns an empty non-nil slice past the end;
313// test with len, not with nil, when code handles both.
314func (ix *Index) Page(page, size int) []Entry {
315 if ix.s == nil || page < 1 || size < 1 {
316 return nil
317 }
318 // The offset is computed in a way that cannot wrap, because
319 // bptree.IterateByOffset normalises a NEGATIVE offset to 0: an overflowed
320 // (page-1)*size would silently hand back page 1 for a page past the end,
321 // which is the opposite of this method's contract.
322 //
323 // page <= 1+(keys-1)/size bounds (page-1)*size by keys-1, so the product
324 // cannot overflow, and it also rejects the page that starts exactly at the
325 // end, which would otherwise come back as an empty non-nil slice while
326 // every later page is nil.
327 keys := ix.s.tree.Size()
328 if keys == 0 || page > 1+(keys-1)/size {
329 return nil
330 }
331 //gnovet:ignore page-offset-overflow bounded by keys-1 on the line above
332 offset := (page - 1) * size
333
334 // The capacity follows what exists, not what was asked for, so Page(1,
335 // maxInt) over three keys reserves three slots and not two billion.
336 room := keys - offset
337 if room > size {
338 room = size
339 }
340 out := make([]Entry, 0, room)
341 ix.s.tree.IterateByOffset(offset, size, func(k string, v any) bool {
342 e := v.(*entry)
343 ids := make([]store.ID, len(e.ids))
344 copy(ids, e.ids)
345 out = append(out, Entry{Key: k, IDs: ids})
346 return false
347 })
348 return out
349}
350
351// Pages returns how many pages of the given size the keys fill, at least 1 so
352// a page picker always has something to render.
353func (ix *Index) Pages(size int) int {
354 if size < 1 {
355 return 1
356 }
357 n := ix.Keys()
358 if n == 0 {
359 return 1
360 }
361 // 1 + (n-1)/size rather than (n+size-1)/size: the second overflows when
362 // size is near the integer limit, wraps negative, and divides to 0, which
363 // contradicts the "at least 1" this method promises and divides a page
364 // picker by zero.
365 return 1 + (n-1)/size
366}
367
368// Entry is one key and the ids carrying it, as returned by [Index.Page].
369type Entry struct {
370 Key string
371 IDs []store.ID
372}
373
374// find returns the position id occupies, or would occupy, in the ascending ids,
375// and whether it is already there. Binary search: a key with many ids is the
376// case this package exists for.
377func (e *entry) find(id store.ID) (int, bool) {
378 lo, hi := 0, len(e.ids)
379 for lo < hi {
380 mid := int(uint(lo+hi) >> 1)
381 switch {
382 case e.ids[mid] == id:
383 return mid, true
384 case e.ids[mid] < id:
385 lo = mid + 1
386 default:
387 hi = mid
388 }
389 }
390 return lo, false
391}