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