duebook.gno

  1// Package duebook is a pure scheduling primitive for realms that need to
  2// authorize an action now and perform it later. It is to *time* what
  3// feeledger is to *money*: it holds no coins, performs no effects, imports
  4// no chain APIs, and owns no package-level state. The importing realm owns
  5// a *Book, supplies the clock, and performs its own effects.
  6//
  7// # The one idea
  8//
  9// A realm does not ask duebook to execute anything — Gno has no autonomous
 10// execution, so "scheduled" always means "someone sends a transaction
 11// later". What a realm actually needs is for that later transaction to be
 12// authorized exactly once. Claim is that step:
 13//
 14//	d, err := book.Claim(id, now)
 15//	if err != nil {
 16//		panic(err) // not due, expired, cancelled, or already claimed
 17//	}
 18//	// ... the realm performs its own effect here, under its own authority
 19//
 20// Claim checks due / not-expired / still-open and CONSUMES the deferral in
 21// the same call, before returning. The realm then acts. Replay is not
 22// guarded against, it is structurally impossible:
 23//
 24//   - IDs are allocated monotonically from an internal counter and are
 25//     NEVER reused, for the lifetime of the Book;
 26//   - a successful Claim removes the deferral before returning;
 27//
 28// so at most one Claim per ID can ever succeed, across all transactions,
 29// forever. A second Claim of the same ID returns ErrNotFound whether the
 30// first one happened in this transaction or a year ago.
 31//
 32// Because the realm performs the effect itself, no closure, callback, or
 33// capability ever crosses a realm boundary. duebook cannot be handed code
 34// to run, so it cannot be tricked into running the wrong code.
 35//
 36// # Lifecycle
 37//
 38// A deferral is open from Schedule until exactly one of Claim, Cancel, or
 39// Expire consumes it. There is no other transition and no way back.
 40//
 41//	Schedule ──> open ──┬── Claim   (now >= DueAt, before ExpiresAt)
 42//	                    ├── Cancel  (owner only, any time while open)
 43//	                    └── Expire  (anyone, once now >= ExpiresAt)
 44//
 45// Claimability is the half-open interval [DueAt, ExpiresAt): due at DueAt,
 46// no longer claimable at ExpiresAt. A deferral scheduled with ttl == 0
 47// never expires and has ExpiresAt == 0.
 48//
 49// # State growth
 50//
 51// Consumed deferrals are removed, not archived — the ID counter, not a
 52// tombstone, is what prevents replay, so there is nothing to keep. Open
 53// deferrals are capped per Book at construction. Storage is therefore
 54// bounded by maxOpen regardless of how many deferrals have ever existed.
 55// Audit history belongs in the consuming realm's events.
 56//
 57// # Consumer contract (the parts the package cannot enforce)
 58//
 59//  1. SUPPLY A REAL CLOCK. duebook cannot verify that `now` came from
 60//     runtime.ChainHeight() or time.Now().Unix(). A realm that lets a caller
 61//     choose `now` has no delay at all. Pass the chain's clock, never a
 62//     transaction parameter. This is the single most important obligation
 63//     and the one most commonly got wrong.
 64//  2. USE ONE CLOCK CONSISTENTLY. Heights and seconds must not be mixed
 65//     within a Book; delay, ttl and now are all in the caller's chosen
 66//     unit.
 67//  3. DO NOT EXPORT THE BOOK. A *Book is a mutable handle. Returning one
 68//     across a realm boundary hands out the right to schedule, cancel and
 69//     claim. Expose your own crossing functions instead; this package
 70//     returns Deferral values, never pointers into its state.
 71//  4. AUTHORIZE THE ACTOR. duebook authenticates nothing but ownership on
 72//     Cancel. Who may Schedule, and who may Claim, are the realm's policy —
 73//     derive the caller from cur.Previous().Address(), not from an argument.
 74//  5. ACT AFTER A SUCCESSFUL CLAIM, IN THE SAME TRANSACTION. Claim's
 75//     return value is the authorization. Storing it to act on later
 76//     reintroduces the replay window this package exists to close.
 77//
 78// All failures are returned as errors and leave the Book COMPLETELY
 79// UNCHANGED. Must* wrappers are the only functions here that panic.
 80//
 81// The Book is address-agnostic: owners are non-empty strings. Realms
 82// normally use address.String().
 83package duebook
 84
 85import (
 86	"errors"
 87	"strconv"
 88
 89	"gno.land/p/nt/avl/v0"
 90)
 91
 92// MaxPayloadLen bounds a single deferral's payload. The payload is opaque
 93// to duebook — it exists so a realm can recover what it scheduled without
 94// keeping a parallel table.
 95const MaxPayloadLen = 4096
 96
 97// MaxOpenLimit is the largest maxOpen a Book may be constructed with. It
 98// bounds the worst-case cost of Due and IterateOpen, which scan the open
 99// set.
100const MaxOpenLimit = 10000
101
102// Errors returned by Book operations.
103var (
104	ErrEmptyOwner    = errors.New("duebook: empty owner key")
105	ErrPayloadTooBig = errors.New("duebook: payload exceeds MaxPayloadLen")
106	ErrInvalidNow    = errors.New("duebook: now must be non-negative")
107	ErrInvalidDelay  = errors.New("duebook: delay outside [minDelay, maxDelay]")
108	ErrInvalidTTL    = errors.New("duebook: ttl must be non-negative")
109	ErrInvalidConfig = errors.New("duebook: invalid book configuration")
110	ErrBookFull      = errors.New("duebook: open deferral cap reached")
111	ErrNotFound      = errors.New("duebook: no such open deferral")
112	ErrNotDue        = errors.New("duebook: not due yet")
113	ErrExpired       = errors.New("duebook: deferral has expired")
114	ErrNotExpired    = errors.New("duebook: deferral has not expired")
115	ErrNotOwner      = errors.New("duebook: caller does not own this deferral")
116	ErrOverflow      = errors.New("duebook: int64 overflow")
117	ErrIDExhausted   = errors.New("duebook: identifier space exhausted")
118)
119
120// Deferral is a scheduled action. It is returned BY VALUE: holders cannot
121// reach into a Book through it. Payload is opaque to this package.
122//
123// ExpiresAt == 0 means the deferral never expires. Otherwise the deferral
124// is claimable exactly on [DueAt, ExpiresAt).
125type Deferral struct {
126	ID        uint64
127	Owner     string
128	Payload   string
129	CreatedAt int64
130	DueAt     int64
131	ExpiresAt int64
132}
133
134// IsDue reports whether the deferral has reached its due time at now.
135func (d Deferral) IsDue(now int64) bool { return now >= d.DueAt }
136
137// IsExpired reports whether the deferral is past its expiry at now.
138// A deferral with no expiry is never expired.
139func (d Deferral) IsExpired(now int64) bool {
140	return d.ExpiresAt != 0 && now >= d.ExpiresAt
141}
142
143// IsClaimable reports whether Claim would succeed at now, assuming the
144// deferral is still open.
145func (d Deferral) IsClaimable(now int64) bool {
146	return d.IsDue(now) && !d.IsExpired(now)
147}
148
149// Book holds the open deferrals of one consuming realm. The zero value is
150// not usable; construct with New.
151type Book struct {
152	minDelay int64
153	maxDelay int64
154	maxOpen  int
155	nextID   uint64    // never decreases; IDs are never reused
156	open     *avl.Tree // padded id -> Deferral
157}
158
159// New returns an empty Book.
160//
161// minDelay is the floor on how far ahead a deferral may be scheduled; 0
162// permits same-instant scheduling. maxDelay is the ceiling, and doubles as
163// the overflow guard on now+delay. maxOpen caps simultaneously open
164// deferrals and must be in [1, MaxOpenLimit].
165//
166// Units are the caller's choice — block heights or seconds — but must be
167// used consistently for the life of the Book.
168func New(minDelay, maxDelay int64, maxOpen int) (*Book, error) {
169	if minDelay < 0 || maxDelay < minDelay {
170		return nil, ErrInvalidConfig
171	}
172	if maxOpen < 1 || maxOpen > MaxOpenLimit {
173		return nil, ErrInvalidConfig
174	}
175	return &Book{
176		minDelay: minDelay,
177		maxDelay: maxDelay,
178		maxOpen:  maxOpen,
179		nextID:   1,
180		open:     avl.NewTree(),
181	}, nil
182}
183
184// MustNew is New but panics on error.
185func MustNew(minDelay, maxDelay int64, maxOpen int) *Book {
186	b, err := New(minDelay, maxDelay, maxOpen)
187	if err != nil {
188		panic(err)
189	}
190	return b
191}
192
193// MinDelay returns the Book's scheduling floor.
194func (b *Book) MinDelay() int64 { return b.minDelay }
195
196// MaxDelay returns the Book's scheduling ceiling.
197func (b *Book) MaxDelay() int64 { return b.maxDelay }
198
199// MaxOpen returns the Book's cap on simultaneously open deferrals.
200func (b *Book) MaxOpen() int { return b.maxOpen }
201
202// OpenCount returns how many deferrals are currently open.
203func (b *Book) OpenCount() int { return b.open.Size() }
204
205// NextID returns the identifier the next Schedule will allocate. It only
206// ever increases, which is what makes a consumed ID unreusable.
207func (b *Book) NextID() uint64 { return b.nextID }
208
209// Schedule opens a deferral owned by owner, due at now+delay, expiring
210// ttl after that (ttl == 0 means it never expires). It returns the new
211// deferral's ID.
212//
213// Fails with ErrEmptyOwner, ErrPayloadTooBig, ErrInvalidNow (now < 0),
214// ErrInvalidDelay (delay outside [MinDelay, MaxDelay]), ErrInvalidTTL
215// (ttl < 0), ErrBookFull, ErrOverflow, or ErrIDExhausted. On error
216// nothing is modified.
217func (b *Book) Schedule(owner, payload string, now, delay, ttl int64) (uint64, error) {
218	if owner == "" {
219		return 0, ErrEmptyOwner
220	}
221	if len(payload) > MaxPayloadLen {
222		return 0, ErrPayloadTooBig
223	}
224	if now < 0 {
225		return 0, ErrInvalidNow
226	}
227	if delay < b.minDelay || delay > b.maxDelay {
228		return 0, ErrInvalidDelay
229	}
230	if ttl < 0 {
231		return 0, ErrInvalidTTL
232	}
233	if b.open.Size() >= b.maxOpen {
234		return 0, ErrBookFull
235	}
236	if b.nextID == 0 {
237		return 0, ErrIDExhausted
238	}
239
240	dueAt, ok := checkedAdd(now, delay)
241	if !ok {
242		return 0, ErrOverflow
243	}
244	expiresAt := int64(0)
245	if ttl > 0 {
246		expiresAt, ok = checkedAdd(dueAt, ttl)
247		if !ok {
248			return 0, ErrOverflow
249		}
250	}
251
252	id := b.nextID
253	b.nextID++
254	b.open.Set(idKey(id), Deferral{
255		ID:        id,
256		Owner:     owner,
257		Payload:   payload,
258		CreatedAt: now,
259		DueAt:     dueAt,
260		ExpiresAt: expiresAt,
261	})
262	return id, nil
263}
264
265// MustSchedule is Schedule but panics on error.
266func (b *Book) MustSchedule(owner, payload string, now, delay, ttl int64) uint64 {
267	id, err := b.Schedule(owner, payload, now, delay, ttl)
268	if err != nil {
269		panic(err)
270	}
271	return id
272}
273
274// Claim consumes the deferral and returns it, authorizing the caller to
275// perform the deferred action NOW, in this transaction.
276//
277// It succeeds only while the deferral is open and now is in
278// [DueAt, ExpiresAt). The deferral is removed BEFORE Claim returns, so a
279// re-entrant or later Claim of the same ID finds nothing; combined with
280// non-reused IDs, at most one Claim per ID ever succeeds.
281//
282// Fails with ErrInvalidNow, ErrNotFound (never existed, or already
283// consumed by Claim/Cancel/Expire), ErrNotDue, or ErrExpired. On error
284// nothing is modified.
285//
286// duebook does NOT check who is claiming: whether a deferral is
287// permissionlessly claimable or restricted to its owner is the consuming
288// realm's policy, applied before calling Claim.
289func (b *Book) Claim(id uint64, now int64) (Deferral, error) {
290	if now < 0 {
291		return Deferral{}, ErrInvalidNow
292	}
293	d, ok := b.get(id)
294	if !ok {
295		return Deferral{}, ErrNotFound
296	}
297	if !d.IsDue(now) {
298		return Deferral{}, ErrNotDue
299	}
300	if d.IsExpired(now) {
301		return Deferral{}, ErrExpired
302	}
303	// Consume before returning: the caller acts only after this point, so
304	// the deferral is already gone when the effect runs.
305	b.open.Remove(idKey(id))
306	return d, nil
307}
308
309// MustClaim is Claim but panics on error.
310func (b *Book) MustClaim(id uint64, now int64) Deferral {
311	d, err := b.Claim(id, now)
312	if err != nil {
313		panic(err)
314	}
315	return d
316}
317
318// Cancel consumes an open deferral without performing it. Only its owner
319// may cancel, and cancellation is permitted at any time while the deferral
320// is open — including after it became due but before anyone claimed it.
321//
322// Fails with ErrEmptyOwner, ErrNotFound, or ErrNotOwner. On error nothing
323// is modified.
324func (b *Book) Cancel(id uint64, owner string) (Deferral, error) {
325	if owner == "" {
326		return Deferral{}, ErrEmptyOwner
327	}
328	d, ok := b.get(id)
329	if !ok {
330		return Deferral{}, ErrNotFound
331	}
332	if d.Owner != owner {
333		return Deferral{}, ErrNotOwner
334	}
335	b.open.Remove(idKey(id))
336	return d, nil
337}
338
339// MustCancel is Cancel but panics on error.
340func (b *Book) MustCancel(id uint64, owner string) Deferral {
341	d, err := b.Cancel(id, owner)
342	if err != nil {
343		panic(err)
344	}
345	return d
346}
347
348// Expire consumes a deferral that is past its expiry, reclaiming its
349// storage. It is deliberately permissionless: an expired deferral can
350// never be claimed again, so letting anyone clear it keeps a Book from
351// silting up with dead entries that block Schedule against maxOpen.
352//
353// Fails with ErrInvalidNow, ErrNotFound, or ErrNotExpired (including for
354// deferrals with no expiry, which never expire). On error nothing is
355// modified.
356func (b *Book) Expire(id uint64, now int64) (Deferral, error) {
357	if now < 0 {
358		return Deferral{}, ErrInvalidNow
359	}
360	d, ok := b.get(id)
361	if !ok {
362		return Deferral{}, ErrNotFound
363	}
364	if !d.IsExpired(now) {
365		return Deferral{}, ErrNotExpired
366	}
367	b.open.Remove(idKey(id))
368	return d, nil
369}
370
371// MustExpire is Expire but panics on error.
372func (b *Book) MustExpire(id uint64, now int64) Deferral {
373	d, err := b.Expire(id, now)
374	if err != nil {
375		panic(err)
376	}
377	return d
378}
379
380// Get returns an open deferral by ID. The second result is false if the
381// deferral never existed or has already been consumed — Get cannot tell
382// those apart, by design: consumed deferrals leave no tombstone.
383//
384// Get is a read-only preview and never authorizes anything. Only Claim's
385// return value authorizes an action.
386func (b *Book) Get(id uint64) (Deferral, bool) { return b.get(id) }
387
388// Due returns up to limit open deferrals that are claimable at now, in
389// ascending ID order (oldest first). A limit <= 0 returns nothing.
390//
391// It scans the open set, so its cost is bounded by MaxOpen.
392func (b *Book) Due(now int64, limit int) []Deferral {
393	out := []Deferral{}
394	if limit <= 0 || now < 0 {
395		return out
396	}
397	b.open.Iterate("", "", func(_ string, value any) bool {
398		d := value.(Deferral)
399		if d.IsClaimable(now) {
400			out = append(out, d)
401		}
402		return len(out) >= limit
403	})
404	return out
405}
406
407// Expirable returns up to limit open deferrals that Expire would accept at
408// now, in ascending ID order. A limit <= 0 returns nothing.
409func (b *Book) Expirable(now int64, limit int) []Deferral {
410	out := []Deferral{}
411	if limit <= 0 || now < 0 {
412		return out
413	}
414	b.open.Iterate("", "", func(_ string, value any) bool {
415		d := value.(Deferral)
416		if d.IsExpired(now) {
417			out = append(out, d)
418		}
419		return len(out) >= limit
420	})
421	return out
422}
423
424// IterateOpen calls fn for every open deferral in ascending ID order.
425// Iteration stops early when fn returns true.
426//
427// fn receives a COPY: Deferral is passed by value and holds only scalars
428// and strings, so fn gets no pointer into the Book and cannot reach past
429// it — Book's fields are all unexported.
430//
431// Two rules for fn, and the second is the one that is easy to miss.
432//
433//   - Do not Schedule, Claim, Cancel or Expire from inside fn: mutating
434//     the tree while iterating it is undefined. Collect IDs first, then
435//     act after IterateOpen returns.
436//
437//   - fn runs under the CALLING REALM'S STORAGE AUTHORITY. This method's
438//     receiver is stamped with the importing realm's PkgID, so the borrow
439//     rules leave the realm context set to that realm for the whole
440//     callback, and a top-level fn has no receiver and no declaring realm
441//     to anchor it elsewhere. A callback that re-enters the calling
442//     realm's own mutators therefore does so with that realm's authority.
443//     Never pass a caller-supplied function here from inside a
444//     permission-gated path; pass only a closure this package's consumer
445//     wrote itself.
446func (b *Book) IterateOpen(fn func(Deferral) bool) {
447	b.open.Iterate("", "", func(_ string, value any) bool {
448		return fn(value.(Deferral))
449	})
450}
451
452// get looks up an open deferral without touching the tree otherwise.
453func (b *Book) get(id uint64) (Deferral, bool) {
454	v := b.open.Get(idKey(id))
455	if v == nil {
456		return Deferral{}, false
457	}
458	return v.(Deferral), true
459}
460
461// idKey encodes an ID so that avl's lexical key order matches numeric ID
462// order. math.MaxUint64 is 20 digits, so a fixed 20-wide zero-padded
463// decimal is both sufficient and unambiguous.
464func idKey(id uint64) string {
465	s := strconv.FormatUint(id, 10)
466	const width = 20
467	if len(s) >= width {
468		return s
469	}
470	return zeros[:width-len(s)] + s
471}
472
473const zeros = "00000000000000000000"
474
475// checkedAdd returns a+b and reports whether the addition did not
476// overflow int64.
477func checkedAdd(a, b int64) (int64, bool) {
478	sum := a + b
479	if (b > 0 && sum < a) || (b < 0 && sum > a) {
480		return 0, false
481	}
482	return sum, true
483}