1// Package duebook is a pure scheduling primitive for realms that need to2// authorize an action now and perform it later. It is to *time* what3// feeledger is to *money*: it holds no coins, performs no effects, imports4// no chain APIs, and owns no package-level state. The importing realm owns5// a *Book, supplies the clock, and performs its own effects.6//7// # The one idea8//9// A realm does not ask duebook to execute anything — Gno has no autonomous10// execution, so "scheduled" always means "someone sends a transaction11// later". What a realm actually needs is for that later transaction to be12// 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 claimed17// }18// // ... the realm performs its own effect here, under its own authority19//20// Claim checks due / not-expired / still-open and CONSUMES the deferral in21// the same call, before returning. The realm then acts. Replay is not22// guarded against, it is structurally impossible:23//24// - IDs are allocated monotonically from an internal counter and are25// 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 the30// first one happened in this transaction or a year ago.31//32// Because the realm performs the effect itself, no closure, callback, or33// capability ever crosses a realm boundary. duebook cannot be handed code34// to run, so it cannot be tricked into running the wrong code.35//36// # Lifecycle37//38// A deferral is open from Schedule until exactly one of Claim, Cancel, or39// 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 == 047// never expires and has ExpiresAt == 0.48//49// # State growth50//51// Consumed deferrals are removed, not archived — the ID counter, not a52// tombstone, is what prevents replay, so there is nothing to keep. Open53// deferrals are capped per Book at construction. Storage is therefore54// 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 from60// runtime.ChainHeight() or time.Now().Unix(). A realm that lets a caller61// choose `now` has no delay at all. Pass the chain's clock, never a62// transaction parameter. This is the single most important obligation63// and the one most commonly got wrong.64// 2. USE ONE CLOCK CONSISTENTLY. Heights and seconds must not be mixed65// within a Book; delay, ttl and now are all in the caller's chosen66// unit.67// 3. DO NOT EXPORT THE BOOK. A *Book is a mutable handle. Returning one68// across a realm boundary hands out the right to schedule, cancel and69// claim. Expose your own crossing functions instead; this package70// returns Deferral values, never pointers into its state.71// 4. AUTHORIZE THE ACTOR. duebook authenticates nothing but ownership on72// 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's75// return value is the authorization. Storing it to act on later76// reintroduces the replay window this package exists to close.77//78// All failures are returned as errors and leave the Book COMPLETELY79// UNCHANGED. Must* wrappers are the only functions here that panic.80//81// The Book is address-agnostic: owners are non-empty strings. Realms82// normally use address.String().83package duebook8485import (86 "errors"87 "strconv"8889 "gno.land/p/nt/avl/v0"90)9192// MaxPayloadLen bounds a single deferral's payload. The payload is opaque93// to duebook — it exists so a realm can recover what it scheduled without94// keeping a parallel table.95const MaxPayloadLen = 40969697// MaxOpenLimit is the largest maxOpen a Book may be constructed with. It98// bounds the worst-case cost of Due and IterateOpen, which scan the open99// set.100const MaxOpenLimit = 10000101102// 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)119120// Deferral is a scheduled action. It is returned BY VALUE: holders cannot121// reach into a Book through it. Payload is opaque to this package.122//123// ExpiresAt == 0 means the deferral never expires. Otherwise the deferral124// is claimable exactly on [DueAt, ExpiresAt).125type Deferral struct {126 ID uint64127 Owner string128 Payload string129 CreatedAt int64130 DueAt int64131 ExpiresAt int64132}133134// IsDue reports whether the deferral has reached its due time at now.135func (d Deferral) IsDue(now int64) bool { return now >= d.DueAt }136137// 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.ExpiresAt141}142143// IsClaimable reports whether Claim would succeed at now, assuming the144// deferral is still open.145func (d Deferral) IsClaimable(now int64) bool {146 return d.IsDue(now) && !d.IsExpired(now)147}148149// Book holds the open deferrals of one consuming realm. The zero value is150// not usable; construct with New.151type Book struct {152 minDelay int64153 maxDelay int64154 maxOpen int155 nextID uint64 // never decreases; IDs are never reused156 open *avl.Tree // padded id -> Deferral157}158159// New returns an empty Book.160//161// minDelay is the floor on how far ahead a deferral may be scheduled; 0162// permits same-instant scheduling. maxDelay is the ceiling, and doubles as163// the overflow guard on now+delay. maxOpen caps simultaneously open164// deferrals and must be in [1, MaxOpenLimit].165//166// Units are the caller's choice — block heights or seconds — but must be167// 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, ErrInvalidConfig171 }172 if maxOpen < 1 || maxOpen > MaxOpenLimit {173 return nil, ErrInvalidConfig174 }175 return &Book{176 minDelay: minDelay,177 maxDelay: maxDelay,178 maxOpen: maxOpen,179 nextID: 1,180 open: avl.NewTree(),181 }, nil182}183184// 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 b191}192193// MinDelay returns the Book's scheduling floor.194func (b *Book) MinDelay() int64 { return b.minDelay }195196// MaxDelay returns the Book's scheduling ceiling.197func (b *Book) MaxDelay() int64 { return b.maxDelay }198199// MaxOpen returns the Book's cap on simultaneously open deferrals.200func (b *Book) MaxOpen() int { return b.maxOpen }201202// OpenCount returns how many deferrals are currently open.203func (b *Book) OpenCount() int { return b.open.Size() }204205// NextID returns the identifier the next Schedule will allocate. It only206// ever increases, which is what makes a consumed ID unreusable.207func (b *Book) NextID() uint64 { return b.nextID }208209// Schedule opens a deferral owned by owner, due at now+delay, expiring210// ttl after that (ttl == 0 means it never expires). It returns the new211// deferral's ID.212//213// Fails with ErrEmptyOwner, ErrPayloadTooBig, ErrInvalidNow (now < 0),214// ErrInvalidDelay (delay outside [MinDelay, MaxDelay]), ErrInvalidTTL215// (ttl < 0), ErrBookFull, ErrOverflow, or ErrIDExhausted. On error216// nothing is modified.217func (b *Book) Schedule(owner, payload string, now, delay, ttl int64) (uint64, error) {218 if owner == "" {219 return 0, ErrEmptyOwner220 }221 if len(payload) > MaxPayloadLen {222 return 0, ErrPayloadTooBig223 }224 if now < 0 {225 return 0, ErrInvalidNow226 }227 if delay < b.minDelay || delay > b.maxDelay {228 return 0, ErrInvalidDelay229 }230 if ttl < 0 {231 return 0, ErrInvalidTTL232 }233 if b.open.Size() >= b.maxOpen {234 return 0, ErrBookFull235 }236 if b.nextID == 0 {237 return 0, ErrIDExhausted238 }239240 dueAt, ok := checkedAdd(now, delay)241 if !ok {242 return 0, ErrOverflow243 }244 expiresAt := int64(0)245 if ttl > 0 {246 expiresAt, ok = checkedAdd(dueAt, ttl)247 if !ok {248 return 0, ErrOverflow249 }250 }251252 id := b.nextID253 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, nil263}264265// 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 id272}273274// Claim consumes the deferral and returns it, authorizing the caller to275// perform the deferred action NOW, in this transaction.276//277// It succeeds only while the deferral is open and now is in278// [DueAt, ExpiresAt). The deferral is removed BEFORE Claim returns, so a279// re-entrant or later Claim of the same ID finds nothing; combined with280// non-reused IDs, at most one Claim per ID ever succeeds.281//282// Fails with ErrInvalidNow, ErrNotFound (never existed, or already283// consumed by Claim/Cancel/Expire), ErrNotDue, or ErrExpired. On error284// nothing is modified.285//286// duebook does NOT check who is claiming: whether a deferral is287// permissionlessly claimable or restricted to its owner is the consuming288// realm's policy, applied before calling Claim.289func (b *Book) Claim(id uint64, now int64) (Deferral, error) {290 if now < 0 {291 return Deferral{}, ErrInvalidNow292 }293 d, ok := b.get(id)294 if !ok {295 return Deferral{}, ErrNotFound296 }297 if !d.IsDue(now) {298 return Deferral{}, ErrNotDue299 }300 if d.IsExpired(now) {301 return Deferral{}, ErrExpired302 }303 // Consume before returning: the caller acts only after this point, so304 // the deferral is already gone when the effect runs.305 b.open.Remove(idKey(id))306 return d, nil307}308309// 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 d316}317318// Cancel consumes an open deferral without performing it. Only its owner319// may cancel, and cancellation is permitted at any time while the deferral320// is open — including after it became due but before anyone claimed it.321//322// Fails with ErrEmptyOwner, ErrNotFound, or ErrNotOwner. On error nothing323// is modified.324func (b *Book) Cancel(id uint64, owner string) (Deferral, error) {325 if owner == "" {326 return Deferral{}, ErrEmptyOwner327 }328 d, ok := b.get(id)329 if !ok {330 return Deferral{}, ErrNotFound331 }332 if d.Owner != owner {333 return Deferral{}, ErrNotOwner334 }335 b.open.Remove(idKey(id))336 return d, nil337}338339// 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 d346}347348// Expire consumes a deferral that is past its expiry, reclaiming its349// storage. It is deliberately permissionless: an expired deferral can350// never be claimed again, so letting anyone clear it keeps a Book from351// silting up with dead entries that block Schedule against maxOpen.352//353// Fails with ErrInvalidNow, ErrNotFound, or ErrNotExpired (including for354// deferrals with no expiry, which never expire). On error nothing is355// modified.356func (b *Book) Expire(id uint64, now int64) (Deferral, error) {357 if now < 0 {358 return Deferral{}, ErrInvalidNow359 }360 d, ok := b.get(id)361 if !ok {362 return Deferral{}, ErrNotFound363 }364 if !d.IsExpired(now) {365 return Deferral{}, ErrNotExpired366 }367 b.open.Remove(idKey(id))368 return d, nil369}370371// 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 d378}379380// Get returns an open deferral by ID. The second result is false if the381// deferral never existed or has already been consumed — Get cannot tell382// those apart, by design: consumed deferrals leave no tombstone.383//384// Get is a read-only preview and never authorizes anything. Only Claim's385// return value authorizes an action.386func (b *Book) Get(id uint64) (Deferral, bool) { return b.get(id) }387388// Due returns up to limit open deferrals that are claimable at now, in389// 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 out396 }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) >= limit403 })404 return out405}406407// Expirable returns up to limit open deferrals that Expire would accept at408// 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 out413 }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) >= limit420 })421 return out422}423424// 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 scalars428// and strings, so fn gets no pointer into the Book and cannot reach past429// 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: mutating434// the tree while iterating it is undefined. Collect IDs first, then435// act after IterateOpen returns.436//437// - fn runs under the CALLING REALM'S STORAGE AUTHORITY. This method's438// receiver is stamped with the importing realm's PkgID, so the borrow439// rules leave the realm context set to that realm for the whole440// callback, and a top-level fn has no receiver and no declaring realm441// to anchor it elsewhere. A callback that re-enters the calling442// realm's own mutators therefore does so with that realm's authority.443// Never pass a caller-supplied function here from inside a444// permission-gated path; pass only a closure this package's consumer445// 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}451452// 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{}, false457 }458 return v.(Deferral), true459}460461// idKey encodes an ID so that avl's lexical key order matches numeric ID462// order. math.MaxUint64 is 20 digits, so a fixed 20-wide zero-padded463// decimal is both sufficient and unambiguous.464func idKey(id uint64) string {465 s := strconv.FormatUint(id, 10)466 const width = 20467 if len(s) >= width {468 return s469 }470 return zeros[:width-len(s)] + s471}472473const zeros = "00000000000000000000"474475// checkedAdd returns a+b and reports whether the addition did not476// overflow int64.477func checkedAdd(a, b int64) (int64, bool) {478 sum := a + b479 if (b > 0 && sum < a) || (b < 0 && sum > a) {480 return 0, false481 }482 return sum, true483}484Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.