store.gno
10.17 Kb · 302 lines
1// Package store is the auto-id ordered collection every r/moul realm was
2// building by hand: an avl.Tree, an int counter, and a private function that
3// zero-pads the counter into a key so the tree iterates in the order a human
4// expects.
5//
6// Sixteen realm files in this repo carry that third piece. They do not agree:
7//
8// padID width 6 for len(s) < 6 { s = "0" + s } asciiart
9// pad width 12 for len(s) < 12 { s = "0" + s } tictactoe
10// key width 12 the same loop, a different name blog, crowdfund,
11// englishauction,
12// erc721, splitter
13// idKey width 12 the same loop, a third name connect4
14// idKey width 12 strings.Repeat, guarded by len(s) >= 12 governor, todos
15// idKey width 12 strings.Repeat, UNGUARDED timecapsule
16// seqKey width 16 strings.Repeat, guarded guestbook
17//
18// Every one of them is a silent ceiling. Past the width, the padding stops and
19// the tree starts ordering "1000000000000" before "999999999999", so the list
20// a realm renders is simply wrong from that entry on. The unguarded variant is
21// worse: strings.Repeat panics on a negative count, so the realm stops
22// accepting writes rather than merely mis-sorting them. asciiart's width of 6
23// puts that ceiling at one million entries.
24//
25// The ceiling exists because the key is a decimal string, and decimal strings
26// do not sort numerically. This package removes the ceiling by removing the
27// decision: keys are the big-endian bytes of a [gno.land/p/nt/seqid/v0] ID, a
28// fixed 8 bytes whose lexicographic order IS numeric order, for every value a
29// uint64 can hold. There is no width to pick and no width to outgrow.
30//
31// # Usage
32//
33// var games store.Store // the zero value is an empty store
34//
35// func NewGame(cur realm) int64 {
36// id := games.Add(&Game{...})
37// return int64(id)
38// }
39//
40// func Move(cur realm, gameID int64, cell int) {
41// g := games.MustGet(store.ID(gameID)).(*Game)
42// ...
43// }
44//
45// func Render(path string) string {
46// for _, e := range games.PageReverse(1, 20) { // newest first
47// g := e.Value.(*Game)
48// ... e.ID ...
49// }
50// }
51//
52// # Identifiers
53//
54// An ID is a uint64 that renders as a plain decimal number, so a realm ported
55// to this package keeps showing "#7" exactly as it did before. Only the avl
56// key changes, and the key was never user-visible.
57//
58// IDs start at 1. The zero ID is never assigned, so it is usable as "absent",
59// and [Store.Get] on it always misses.
60//
61// Removing an entry does not free its ID. IDs are a history, not a dense
62// index: reusing one would silently repoint an old link at a new object.
63package store
64
65import (
66 "strconv"
67
68 "gno.land/p/nt/avl/v0"
69 "gno.land/p/nt/seqid/v0"
70)
71
72// ID identifies one entry. It is a plain integer to the outside world and an
73// ordered fixed-width key inside the tree.
74type ID uint64
75
76// String renders the ID in decimal, which is how realms show it and how it
77// arrives back in a Render path.
78func (id ID) String() string { return strconv.FormatUint(uint64(id), 10) }
79
80// Key is the avl key for the ID: the 8 big-endian bytes of the underlying
81// seqid, whose byte order is its numeric order.
82//
83// Exposed because a realm that keeps a secondary index keyed by the same ID
84// needs the identical key, and because it is the one place the encoding is
85// decided.
86func (id ID) Key() string { return seqid.ID(id).Binary() }
87
88// ParseID reads an ID from its decimal form, the shape it has in a Render
89// path or a function argument.
90//
91// It returns false for anything that is not a plain unsigned decimal, which
92// includes "", "-1", "1.0", a value past uint64, and the zero ID (never
93// assigned, so accepting it would only produce a lookup that cannot hit).
94// Leading zeros are accepted: "007" is the ID 7.
95func ParseID(s string) (ID, bool) {
96 n, err := strconv.ParseUint(s, 10, 64)
97 if err != nil || n == 0 {
98 return 0, false
99 }
100 return ID(n), true
101}
102
103// Entry is one ID/value pair, as returned by the paging methods.
104type Entry struct {
105 ID ID
106 Value any
107}
108
109// Store is an ordered collection of values under auto-assigned IDs.
110//
111// The zero Store is an empty store and is ready to use, so a realm can declare
112// one as a package-level var without an initializer. [New] exists for the
113// pointer form.
114type Store struct {
115 tree avl.Tree
116 last seqid.ID
117 label string
118}
119
120// New returns an empty store.
121func New() *Store { return &Store{} }
122
123// Named is [New] with a noun for what the store holds, used in the panic
124// [Store.MustGet] raises: store.Named("game") makes it "game #7 not found"
125// instead of "store: no entry #7".
126//
127// It exists so porting a realm to this package does not have to trade its own
128// error wording for one shared implementation. The realms being replaced here
129// panic "game not found", "proposal not found", "capsule not found"; the label
130// keeps that and adds the id they all omitted.
131func Named(label string) *Store { return &Store{label: label} }
132
133// Add stores v under the next ID and returns it.
134//
135// It panics if the ID space is exhausted, which is [seqid.ID.Next]'s behaviour
136// and requires 2^64 insertions to reach.
137func (s *Store) Add(v any) ID {
138 id := ID(s.last.Next())
139 s.tree.Set(id.Key(), v)
140 return id
141}
142
143// Set writes v at an existing or explicit ID, and reports whether it replaced
144// a value.
145//
146// Use it to update an entry in place. It does not move the ID counter, so
147// setting an ID above [Store.LastID] leaves a gap that [Store.Add] will later
148// walk into and overwrite. Prefer [Store.Add] to create.
149func (s *Store) Set(id ID, v any) (replaced bool) {
150 return s.tree.Set(id.Key(), v)
151}
152
153// Get returns the value at id, and whether it was there.
154//
155// Unlike avl.Tree.Get, a nil value stored at a live ID is distinguishable from
156// an absent one, because the second result comes from Has rather than from the
157// value being nil.
158func (s *Store) Get(id ID) (any, bool) {
159 k := id.Key()
160 if !s.tree.Has(k) {
161 return nil, false
162 }
163 return s.tree.Get(k), true
164}
165
166// MustGet returns the value at id, or panics.
167//
168// This is the "get or panic" the realms wrote eighteen times, with one
169// implementation instead of eighteen. The panic names the id, which none of
170// them did: "store: no entry #7", or "game #7 not found" for a store built
171// with [Named].
172func (s *Store) MustGet(id ID) any {
173 v, ok := s.Get(id)
174 if !ok {
175 panic(s.missing(id))
176 }
177 return v
178}
179
180func (s *Store) missing(id ID) string {
181 if s.label == "" {
182 return "store: no entry #" + id.String()
183 }
184 return s.label + " #" + id.String() + " not found"
185}
186
187// Has reports whether id is present.
188func (s *Store) Has(id ID) bool { return s.tree.Has(id.Key()) }
189
190// Remove deletes the entry at id and returns the value it held.
191//
192// The ID is not recycled: see the package doc.
193func (s *Store) Remove(id ID) (any, bool) { return s.tree.Remove(id.Key()) }
194
195// Len reports how many entries are present. Removals lower it; [Store.LastID]
196// does not move.
197func (s *Store) Len() int { return s.tree.Size() }
198
199// LastID is the highest ID ever assigned, or 0 when nothing has been added.
200// It is the count of insertions, not of live entries.
201func (s *Store) LastID() ID { return ID(s.last) }
202
203// Each visits every entry in ascending ID order.
204//
205// It takes no stop signal on purpose: this is the common case, and a callback
206// whose bool means "stop" reads identically to one whose bool means
207// "continue". When iteration has to end early, say so in the name and use
208// [Store.EachUntil].
209func (s *Store) Each(fn func(id ID, v any)) {
210 s.tree.Iterate("", "", func(k string, v any) bool {
211 fn(keyID(k), v)
212 return false
213 })
214}
215
216// EachReverse is [Store.Each] in descending ID order, which is what a
217// newest-first list wants.
218func (s *Store) EachReverse(fn func(id ID, v any)) {
219 s.tree.ReverseIterate("", "", func(k string, v any) bool {
220 fn(keyID(k), v)
221 return false
222 })
223}
224
225// EachUntil visits entries in ascending ID order and stops when fn returns
226// true. It reports whether it stopped early.
227//
228// True means stop, matching avl.IterCbFn exactly, so a callback moved between
229// this package and a raw tree keeps its meaning.
230func (s *Store) EachUntil(fn func(id ID, v any) bool) bool {
231 return s.tree.Iterate("", "", func(k string, v any) bool {
232 return fn(keyID(k), v)
233 })
234}
235
236// EachReverseUntil is [Store.EachUntil] in descending ID order.
237func (s *Store) EachReverseUntil(fn func(id ID, v any) bool) bool {
238 return s.tree.ReverseIterate("", "", func(k string, v any) bool {
239 return fn(keyID(k), v)
240 })
241}
242
243// Page returns page number page of size entries, in ascending ID order.
244//
245// Pages are 1-based, because they are shown to a reader ("page 1 of 4") and an
246// off-by-one between the URL and the label is the bug this saves. A page past
247// the end, or a page or size below 1, returns an empty slice rather than
248// panicking: the page number usually comes from a Render path, which is user
249// input.
250//
251// It walks only the requested window, not the whole tree.
252func (s *Store) Page(page, size int) []Entry {
253 return s.slice(page, size, false)
254}
255
256// PageReverse is [Store.Page] in descending ID order: page 1 holds the newest
257// entries.
258func (s *Store) PageReverse(page, size int) []Entry {
259 return s.slice(page, size, true)
260}
261
262func (s *Store) slice(page, size int, reverse bool) []Entry {
263 if page < 1 || size < 1 {
264 return nil
265 }
266 offset := (page - 1) * size
267 out := make([]Entry, 0, size)
268 cb := func(k string, v any) bool {
269 out = append(out, Entry{ID: keyID(k), Value: v})
270 return false
271 }
272 if reverse {
273 s.tree.ReverseIterateByOffset(offset, size, cb)
274 } else {
275 s.tree.IterateByOffset(offset, size, cb)
276 }
277 return out
278}
279
280// Pages reports how many pages of the given size the store holds, which is
281// what a pager footer needs. A size below 1 gives 0.
282func (s *Store) Pages(size int) int {
283 if size < 1 {
284 return 0
285 }
286 n := s.Len()
287 return (n + size - 1) / size
288}
289
290// keyID decodes an avl key back to its ID. The keys in this tree are always
291// written by ID.Key, so a short or malformed key means the tree was written by
292// something other than this package.
293func keyID(k string) ID {
294 if len(k) != 8 {
295 panic("store: foreign key in tree")
296 }
297 var n uint64
298 for i := 0; i < 8; i++ {
299 n = n<<8 | uint64(k[i])
300 }
301 return ID(n)
302}
