1// Package accrual is stock that fills at a rate while nobody is playing: the2// resource field of an idle game, the warehouse of a 4X, anything whose state3// is a function of how long it has been left alone.4//5// The shape is always the same. Store what you had and when, and compute the6// rest on demand; a player who does nothing for a month costs nothing, and the7// realm needs no cron, no keeper and no per-block hook. That much is obvious.8// What is not obvious is that the obvious implementation is wrong in three9// ways, each of which has been observed in this repository rather than10// reasoned about.11//12// # 1. Re-anchoring to now makes acting more often pay13//14// Written naively, a claim advances the anchor to now and computes15// elapsed/Period whole periods of production. The division truncates, so every16// claim silently forfeits the part-period it lands in, and a player who claims17// twice forfeits twice. Run in reverse on a decaying stat it is worse than18// unfair, it is free: [r/moul/x/daily/tamagotchi] decayed by elapsed/2 and19// elapsed/3, so at elapsed == 1 it decayed by nothing at all, and feeding once20// per block made the pet immortal while every other cadence died inside 24021// blocks. It was fixed in #221.22//23// The invariant that rules it out is worth stating on its own, because it is24// the whole contract of this package:25//26// Advance(s, a, c) == Advance(Advance(s, a, b), b, c) for a <= b <= c27//28// How often you call must not change where you end up. [Rate.Advance] gets29// there by advancing the anchor only by the WHOLE periods it paid for, leaving30// the remainder on the clock rather than throwing it away. TestSplitInvariant31// asserts it over pseudo-random partitions rather than over a handful of32// hand-picked spans, because the hand-picked spans are exactly the ones a33// wrong implementation already passes.34//35// # 2. A view that does not share the write path's arithmetic drifts from it36//37// The same realm had a second copy of the decay for its Render, so the page38// showed a pet the next call would not honour. Two implementations of one rule39// means one of them is the stale one somebody acts on. Here there is one40// function: [Rate.At] is [Rate.Advance] with the anchor discarded, so a view41// cannot disagree with a write even in principle.42//43// # 3. A projection that is not closed form cannot be rendered at all44//45// Render runs under a query gas limit and may not write, so whatever it46// computes has to be bounded however long the player was away. Anything47// iterative, stepping a simulation once per block, is fine in a transaction48// and unusable in a page: the player who comes back after a month is exactly49// the one whose page times out. Everything here is O(1) in elapsed time, which50// is the property that makes a live-updating page possible, not an51// optimisation.52//53// Times are int64 and the unit is the caller's, block heights or unix seconds,54// as long as it is consistent. Prefer a timestamp: a block-height rate drifts55// in wall-clock terms every time the chain's block time moves, and gno.land's56// has moved from about 4.1s to 3.405s inside one month. Nothing here reads the57// chain, so a realm can test a year of its own economy without one.58//59// A game built on this package is at60// [r/moul/x/games/idle](/r/moul/x/games/idle/v0).61//62// [r/moul/x/daily/tamagotchi]: /r/moul/x/daily/tamagotchi/v063package accrual6465import "errors"6667const maxInt64 = int64(9223372036854775807)6869var (70 // ErrBadAmount is returned when the amount produced per period is not71 // positive. A zero rate is a bug in the caller, not a valid still life:72 // it makes Full unanswerable and every Advance a no-op.73 ErrBadAmount = errors.New("accrual: amount must be positive")74 // ErrBadPeriod is returned when the period is not positive.75 ErrBadPeriod = errors.New("accrual: period must be positive")76 // ErrBadCap is returned when the cap is negative. Zero is legal and77 // means unbounded.78 ErrBadCap = errors.New("accrual: cap must not be negative")79 // ErrNegativeStock is returned when the stock handed in is negative,80 // which would let a caller mint by going through zero.81 ErrNegativeStock = errors.New("accrual: stock must not be negative")82 // ErrBackwards is returned when now falls before the anchor. Time moving83 // backwards is a caller bug (a stored anchor from another clock, a test84 // that rewound), and silently treating it as zero elapsed would hide it.85 ErrBackwards = errors.New("accrual: now must not fall before the anchor")86 // ErrOverflow is returned when the arithmetic would wrap int64.87 ErrOverflow = errors.New("accrual: int64 overflow")88)8990// Rate is production per unit of time, against a ceiling. Construct with New91// so the invariants are checked once instead of on every call.92type Rate struct {93 Amount int64 // produced each whole Period94 Period int64 // time units in one period95 Cap int64 // ceiling on the stock; zero means unbounded96}9798// New validates and returns a Rate. A zero cap means unbounded.99func New(amount, period, capacity int64) (Rate, error) {100 if amount <= 0 {101 return Rate{}, ErrBadAmount102 }103 if period <= 0 {104 return Rate{}, ErrBadPeriod105 }106 if capacity < 0 {107 return Rate{}, ErrBadCap108 }109 return Rate{Amount: amount, Period: period, Cap: capacity}, nil110}111112// Advance returns the stock and the new anchor at time now, given stock held113// since anchor.114//115// The new anchor is NOT now. It is the anchor plus the whole periods actually116// paid out, so the part-period in progress stays on the clock and splitting a117// span into pieces yields exactly what advancing it in one go would:118//119// Advance(s, a, c) == Advance(Advance(s, a, b), b, c) for a <= b <= c120//121// Production past the cap is lost, which is what a cap is for. Saturation is122// idempotent, so it does not break the equality above, and it means a CAPPED123// rate can never return ErrOverflow: the answer is the cap however long the124// player was away. Only an uncapped rate can run out of int64.125func (r Rate) Advance(stock, anchor, now int64) (int64, int64, error) {126 if err := r.check(); err != nil {127 return 0, 0, err128 }129 if stock < 0 {130 return 0, 0, ErrNegativeStock131 }132 if now < anchor {133 return 0, 0, ErrBackwards134 }135 // now-anchor wraps only when the anchor is negative and now is far136 // enough above it. maxInt64+anchor is safe to compute precisely because137 // anchor is negative there.138 if anchor < 0 && now > maxInt64+anchor {139 return 0, 0, ErrOverflow140 }141142 periods := (now - anchor) / r.Period143144 // The anchor only moves by what was paid for. periods*r.Period cannot145 // overflow, it is at most now-anchor, and adding it back cannot pass now.146 newAnchor := anchor + periods*r.Period147148 if r.Cap > 0 && stock >= r.Cap {149 return stock, newAnchor, nil150 }151152 // Production is only computed when its exact value can matter. A capped153 // rate whose payout would wrap int64 has an answer regardless of what154 // that payout is, so it gets one instead of an error.155 if periods > maxInt64/r.Amount {156 return r.saturate(newAnchor)157 }158 produced := periods * r.Amount159 if produced > maxInt64-stock {160 return r.saturate(newAnchor)161 }162163 total := stock + produced164 if r.Cap > 0 && total > r.Cap {165 total = r.Cap166 }167 return total, newAnchor, nil168}169170// saturate answers an accrual too large for int64: the cap if there is one,171// and an error if there is not. A capped Rate therefore never overflows,172// which is the property that lets a realm size a warehouse without also173// having to bound its own lifetime.174func (r Rate) saturate(newAnchor int64) (int64, int64, error) {175 if r.Cap == 0 {176 return 0, 0, ErrOverflow177 }178 return r.Cap, newAnchor, nil179}180181// At is Advance with the anchor discarded: the read-only view of the same182// arithmetic, for a Render that must not write. It is defined in terms of183// Advance on purpose, so a page can never show a number a write would not184// honour.185func (r Rate) At(stock, anchor, now int64) (int64, error) {186 got, _, err := r.Advance(stock, anchor, now)187 return got, err188}189190// Full returns the time at which the stock first reaches the cap, for a realm191// that wants to tell a player when their production starts being wasted.192//193// An uncapped rate returns zero, meaning never. A stock already at or past the194// cap returns the anchor, meaning now.195func (r Rate) Full(stock, anchor int64) (int64, error) {196 if err := r.check(); err != nil {197 return 0, err198 }199 if stock < 0 {200 return 0, ErrNegativeStock201 }202 if r.Cap == 0 {203 return 0, nil204 }205 if stock >= r.Cap {206 return anchor, nil207 }208209 // Whole periods needed to cover the shortfall, rounded UP: the cap is210 // reached by the payout that crosses it, not by the one before.211 need := r.Cap - stock212 periods := need / r.Amount213 if need%r.Amount != 0 {214 periods++215 }216 if periods > maxInt64/r.Period {217 return 0, ErrOverflow218 }219 span := periods * r.Period220 if span > maxInt64-anchor {221 return 0, ErrOverflow222 }223 return anchor + span, nil224}225226// check rejects a zero Rate built by struct literal instead of New, so a227// caller that skipped the constructor gets the same error it would have.228func (r Rate) check() error {229 if r.Amount <= 0 {230 return ErrBadAmount231 }232 if r.Period <= 0 {233 return ErrBadPeriod234 }235 if r.Cap < 0 {236 return ErrBadCap237 }238 return nil239}240Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.