group.gno

  1package groups
  2
  3import (
  4	"errors"
  5
  6	"gno.land/p/moul/addrset"
  7	"gno.land/p/nt/bptree/v0"
  8)
  9
 10var (
 11	ErrRoleExists = errors.New("role already exists")
 12	ErrEmptyName  = errors.New("role name is required")
 13)
 14
 15// Group is a container with a base address set plus a registry of named
 16// Roles. The zero value is not usable; construct with NewGroup.
 17//
 18// # Security
 19//
 20// A Group, and the *Role values it hands out, are meant to be allocated and
 21// held by the consuming realm. Three rules apply at realm boundaries:
 22//
 23//  1. Do not ACCEPT a *Group or *Role from an external/untrusted caller —
 24//     subsequent mutations would route to the allocating (attacker)
 25//     realm's authority, and a poisoned Group could cause DoS or
 26//     unexpected state.
 27//
 28//  2. Do not RETURN a *Group or *Role from any method or function callable
 29//     by untrusted realms. Return *ReadonlyGroup or *ReadonlyRole instead.
 30//
 31//  3. Do not TRUST a *ReadonlyGroup or *ReadonlyRole received from an
 32//     untrusted caller — it is a live handle over the sender's data, not a
 33//     snapshot; the contents are attacker-controlled and can change between
 34//     reads.
 35//
 36// Both directions matter: exposing a *Group to attacker code is as
 37// dangerous as accepting one. The Readonly() views are the only safe
 38// handles to cross a realm boundary.
 39type Group struct {
 40	base  *addrset.Set
 41	roles *bptree.BPTree // name -> *Role
 42}
 43
 44// NewGroup constructs an empty group.
 45func NewGroup() *Group {
 46	return &Group{
 47		base:  &addrset.Set{},
 48		roles: bptree.NewBPTree32(),
 49	}
 50}
 51
 52// --- Base set ---
 53//
 54// All base methods operate ONLY on the base set; roles are never consulted.
 55// Use the aggregated forms (HasAny, TotalSize, IterateAll, RemoveFromAll)
 56// for views across base + roles.
 57
 58// Add inserts addr into the base set. Returns true if newly added.
 59func (g *Group) Add(addr address) (added bool) {
 60	return g.base.Add(addr)
 61}
 62
 63// Remove deletes addr from the base set. Returns true if it was present.
 64func (g *Group) Remove(addr address) (removed bool) {
 65	return g.base.Remove(addr)
 66}
 67
 68// Has reports whether addr is in the base set. It does NOT consult roles;
 69// use HasAny for an aggregated check.
 70func (g *Group) Has(addr address) bool {
 71	return g.base.Has(addr)
 72}
 73
 74// Size returns the number of addresses in the base set only.
 75func (g *Group) Size() int {
 76	return g.base.Size()
 77}
 78
 79// Iterate walks the base set (only) in sorted order, starting at offset.
 80// fn returns true to stop; Iterate returns true if stopped early.
 81func (g *Group) Iterate(offset, count int, fn func(addr address) bool) (stopped bool) {
 82	g.base.IterateByOffset(offset, count, func(a address) bool {
 83		stopped = fn(a)
 84		return stopped
 85	})
 86	return stopped
 87}
 88
 89// --- Role registry ---
 90
 91// AddRole registers a new empty role. Returns ErrEmptyName if name is
 92// empty, ErrRoleExists if a role of that name already exists.
 93func (g *Group) AddRole(name string) (*Role, error) {
 94	if name == "" {
 95		return nil, ErrEmptyName
 96	}
 97	if g.roles.Has(name) {
 98		return nil, ErrRoleExists
 99	}
100	r := newRole(name)
101	g.roles.Set(name, r)
102	return r, nil
103}
104
105// GetRole returns the mutable role if it exists.
106//
107// SECURITY: the returned *Role exposes mutators (Members().Add/Remove,
108// SetMeta). Do not pass it to untrusted callers — use GetRole on a
109// *ReadonlyGroup for cross-realm exposure.
110func (g *Group) GetRole(name string) (r *Role, found bool) {
111	r, found = g.roles.Get(name).(*Role)
112	return r, found
113}
114
115// HasRole reports whether a role with the given name exists.
116func (g *Group) HasRole(name string) bool {
117	return g.roles.Has(name)
118}
119
120// RemoveRole removes the named role and its membership records. Members of
121// the removed role are NOT removed from the base set or from any other
122// role; only this role's own data is discarded. Returns false if no such
123// role exists.
124func (g *Group) RemoveRole(name string) (removed bool) {
125	_, removed = g.roles.Remove(name)
126	return removed
127}
128
129// RoleCount returns the number of registered roles.
130func (g *Group) RoleCount() int {
131	return g.roles.Size()
132}
133
134// IterateRoles walks roles in lexicographic name order, starting at offset
135// and visiting up to count roles. The callback receives a *ReadonlyRole —
136// deliberately not a *Role, so that plumbing an untrusted callback into the
137// iteration cannot escalate into role mutation under this realm's authority.
138// To mutate, capture names during iteration and revisit via GetRole from a
139// trusted context after iteration returns; registry mutation (AddRole,
140// RemoveRole) mid-iteration can panic and abort the transaction. fn returns
141// true to stop; IterateRoles returns true if stopped early.
142func (g *Group) IterateRoles(offset, count int, fn func(*ReadonlyRole) bool) (stopped bool) {
143	return g.roles.IterateByOffset(offset, count, func(_ string, value any) bool {
144		return fn(value.(*Role).Readonly())
145	})
146}
147
148// --- Aggregations across base + all roles ---
149
150// HasAny reports whether addr is in the base set OR in any role.
151func (g *Group) HasAny(addr address) bool {
152	if g.base.Has(addr) {
153		return true
154	}
155	found := false
156	g.roles.IterateByOffset(0, g.roles.Size(), func(_ string, value any) bool {
157		if value.(*Role).members.Has(addr) {
158			found = true
159			return true // stop
160		}
161		return false
162	})
163	return found
164}
165
166// TotalSize returns the count of distinct addresses across the base set and
167// all roles, deduplicated. A caller may place the same address in base and
168// in multiple roles; TotalSize counts it once.
169//
170// Implementation note: dedup tracks seen addresses in an internal addrset,
171// costing O(N) memory in the total membership.
172func (g *Group) TotalSize() int {
173	n := 0
174	g.visitDistinct(func(address) bool {
175		n++
176		return false
177	})
178	return n
179}
180
181// IterateAll walks every distinct address across base + all roles,
182// deduplicated. Order: base first (in addrset order), then roles in name
183// order, skipping addresses already yielded. offset and count apply to the
184// deduplicated output, not the pre-dedup items; a negative offset counts as
185// zero. fn returns true to stop; IterateAll returns true if stopped early.
186//
187// The walk is live: do not mutate the group (base set, member sets, or the
188// role registry) from within fn — registry mutation mid-iteration can panic
189// and abort the transaction. Collect addresses first, mutate after
190// IterateAll returns.
191//
192// Implementation note: dedup tracks seen addresses in an internal addrset
193// (O(N) memory in the addresses scanned); scanning stops as soon as the
194// requested window has been served. For paginating a large Group without
195// dedup, use Iterate (base only) or IterateRoles.
196func (g *Group) IterateAll(offset, count int, fn func(addr address) bool) (stopped bool) {
197	if count <= 0 {
198		return false
199	}
200	if offset < 0 {
201		offset = 0
202	}
203	seen := 0
204	g.visitDistinct(func(a address) bool {
205		if seen < offset {
206			seen++
207			return false
208		}
209		if fn(a) {
210			stopped = true
211			return true
212		}
213		seen++
214		return seen-offset >= count
215	})
216	return stopped
217}
218
219// visitDistinct walks the base set then every role (in name order), calling
220// visit once per distinct address the first time it is seen. visit returns
221// true to stop the walk early.
222func (g *Group) visitDistinct(visit func(addr address) bool) {
223	seen := &addrset.Set{}
224	done := false
225	record := func(a address) bool {
226		if !seen.Add(a) { // Add returns false when already seen
227			return false
228		}
229		done = visit(a)
230		return done
231	}
232	g.base.IterateByOffset(0, g.base.Size(), record)
233	if done {
234		return
235	}
236	g.roles.IterateByOffset(0, g.roles.Size(), func(_ string, value any) bool {
237		r := value.(*Role)
238		r.members.IterateByOffset(0, r.members.Size(), record)
239		return done
240	})
241}
242
243// RolesContaining returns the names of all roles containing addr, in
244// lexicographic name order. The base set is not consulted (base membership
245// is not a "role"). Returns nil if addr is in no roles.
246func (g *Group) RolesContaining(addr address) []string {
247	var names []string
248	g.roles.IterateByOffset(0, g.roles.Size(), func(name string, value any) bool {
249		if value.(*Role).members.Has(addr) {
250			names = append(names, name)
251		}
252		return false
253	})
254	return names
255}
256
257// RemoveFromAll removes addr from the base set and from every role. Returns
258// true if it was removed from at least one location.
259func (g *Group) RemoveFromAll(addr address) (removed bool) {
260	if g.base.Remove(addr) {
261		removed = true
262	}
263	g.roles.IterateByOffset(0, g.roles.Size(), func(_ string, value any) bool {
264		if value.(*Role).members.Remove(addr) {
265			removed = true
266		}
267		return false
268	})
269	return removed
270}
271
272// Readonly returns a read-only view of the group.
273func (g *Group) Readonly() *ReadonlyGroup {
274	return &ReadonlyGroup{group: g}
275}