catalog.gno
5.83 Kb · 189 lines
1package toolbox
2
3import "gno.land/p/nt/bptree/v0"
4
5// Catalog is the directory itself: tools keyed by slug, ordered by it.
6//
7// The zero value is an empty, usable catalog. A Catalog is a HANDLE: copying
8// one shares the directory, and a write through either copy is seen through
9// both, the way copying a map does. A copy of a zero value that was never
10// written is a separate empty catalog.
11//
12// # Why a tree and not a sorted slice
13//
14// A sorted slice is cheaper to READ at the size a directory actually reaches:
15// at n = 100 one cold operation costs 92,571 gas against a fanout-128 tree's
16// 230,754 (`gnobench`, gno master 1fc4c140e, 2026-09-29). It is still the
17// wrong structure, for two reasons that outlive the gas.
18//
19// A slice is ONE persisted object, so every write rewrites all of it: O(n) per
20// transaction and O(n^2) over n of them. That costs nothing for a hub whose
21// catalog is compiled in and never written after deploy, and it is the whole
22// bill for one that accepts registration, which is the other half of what this
23// package is for. Removing is worse than writing: shortening a slice in place
24// keeps the peak allocation charged and refunds no deposit at all.
25//
26// And the ordering comes free. A slug-keyed tree iterates in slug order, which
27// is the order every listing here wants, rather than a hand-rolled binary
28// search that has to be kept correct.
29type Catalog struct {
30 s *state
31}
32
33// state is everything a Catalog holds, behind one pointer so that a copy of
34// the handle cannot split the tree from the counter that describes it.
35//
36// Embedding [bptree.BPTree] by value was the first shape here and it is wrong
37// for exactly that reason: the tree's root is a pointer and its size is an int,
38// so `b := a; b.Set(x)` would thread the new node onto the tree both of them
39// see while incrementing only b's size. a.Len() would say 1 while a.Get(x)
40// found the entry. One pointer, or two readers of the same directory disagree
41// about how big it is.
42type state struct {
43 tools *bptree.BPTree
44}
45
46// Fanout is the B+ tree fanout this package uses.
47//
48// 32 rather than 128 because a tool can be unregistered, and wide nodes lose
49// most on removal: a removal shifts every later value in its leaf and rewrites
50// each one. Same choice, and the same reason, as
51// [gno.land/p/moul/kit/index](/p/moul/kit/index/v0).
52const Fanout = 32
53
54// New returns an empty catalog. It is the zero value, spelled out for a caller
55// who prefers a constructor.
56func New() *Catalog { return &Catalog{} }
57
58// init materialises the state. Called by every mutating method, so the zero
59// value works without a constructor. The tree is created with the state, so a
60// non-nil state always has one.
61func (c *Catalog) init() {
62 if c.s == nil {
63 c.s = &state{tools: bptree.NewBPTreeN(Fanout)}
64 }
65}
66
67// Set inserts t, replacing any tool already under its slug.
68//
69// Replacing rather than refusing is what makes a hub's init idempotent: a
70// compiled-in catalog is rebuilt from source on every redeploy, and a second
71// Set of the same slug is a corrected description rather than a collision.
72func (c *Catalog) Set(t Tool) error {
73 if err := t.Validate(); err != nil {
74 return err
75 }
76 c.init()
77 c.s.tools.Set(t.Slug, copyTool(t))
78 return nil
79}
80
81// Remove deletes the tool under slug. It returns [ErrUnknownSlug] when there
82// is none, so a realm removing an entry it believes in learns that it is gone.
83func (c *Catalog) Remove(slug string) error {
84 if c.s == nil {
85 return ErrUnknownSlug
86 }
87 if _, removed := c.s.tools.Remove(slug); !removed {
88 return ErrUnknownSlug
89 }
90 return nil
91}
92
93// Get returns the tool under slug.
94func (c *Catalog) Get(slug string) (Tool, bool) {
95 if c.s == nil {
96 return Tool{}, false
97 }
98 v := c.s.tools.Get(slug)
99 if v == nil {
100 return Tool{}, false
101 }
102 return copyTool(v.(Tool)), true
103}
104
105// Has reports whether slug is in the catalog.
106func (c *Catalog) Has(slug string) bool {
107 return c.s != nil && c.s.tools.Has(slug)
108}
109
110// Len is how many tools the catalog holds.
111func (c *Catalog) Len() int {
112 if c.s == nil {
113 return 0
114 }
115 return c.s.tools.Size()
116}
117
118// List returns every tool, in slug order.
119func (c *Catalog) List() []Tool {
120 if c.s == nil {
121 return nil
122 }
123 out := make([]Tool, 0, c.s.tools.Size())
124 c.s.tools.Iterate("", "", func(_ string, v any) bool {
125 out = append(out, copyTool(v.(Tool)))
126 return false
127 })
128 return out
129}
130
131// ByTag returns every tool carrying tag, in slug order. An empty tag matches
132// nothing rather than everything: it is almost always an unset field.
133func (c *Catalog) ByTag(tag string) []Tool {
134 if tag == "" || c.s == nil {
135 return nil
136 }
137 var out []Tool
138 c.s.tools.Iterate("", "", func(_ string, v any) bool {
139 if t := v.(Tool); t.HasTag(tag) {
140 out = append(out, copyTool(t))
141 }
142 return false
143 })
144 return out
145}
146
147// Tags returns every tag used by any tool, each once, in first-seen order
148// within slug order. Deterministic, which iterating a map would not be.
149func (c *Catalog) Tags() []string {
150 if c.s == nil {
151 return nil
152 }
153 var out []string
154 c.s.tools.Iterate("", "", func(_ string, v any) bool {
155 for _, tag := range v.(Tool).Tags {
156 if !contains(out, tag) {
157 out = append(out, tag)
158 }
159 }
160 return false
161 })
162 return out
163}
164
165// copyTool deep-copies the one field that is not a scalar.
166//
167// A Tool is a value, so handing one out already copies Slug, Path, Title and
168// Desc. Tags is a slice: the struct copy duplicates the header and shares the
169// backing array, so `c.List()[0].Tags[0] = "x"` would reach into the catalog
170// and change what every later read returns. Copied on the way in as well as on
171// the way out, or the caller of Set keeps a handle on stored state.
172func copyTool(t Tool) Tool {
173 if t.Tags == nil {
174 return t
175 }
176 tags := make([]string, len(t.Tags))
177 copy(tags, t.Tags)
178 t.Tags = tags
179 return t
180}
181
182func contains(haystack []string, needle string) bool {
183 for _, s := range haystack {
184 if s == needle {
185 return true
186 }
187 }
188 return false
189}
