duebook.gno
16.18 Kb · 483 lines
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}
