Search Apps Documentation Source Content File Folder Download Copy Actions Download State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

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(&note{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}