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

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}