accrual.gno

  1// Package accrual is stock that fills at a rate while nobody is playing: the
  2// resource field of an idle game, the warehouse of a 4X, anything whose state
  3// 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 the
  6// rest on demand; a player who does nothing for a month costs nothing, and the
  7// 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 three
  9// ways, each of which has been observed in this repository rather than
 10// reasoned about.
 11//
 12// # 1. Re-anchoring to now makes acting more often pay
 13//
 14// Written naively, a claim advances the anchor to now and computes
 15// elapsed/Period whole periods of production. The division truncates, so every
 16// claim silently forfeits the part-period it lands in, and a player who claims
 17// twice forfeits twice. Run in reverse on a decaying stat it is worse than
 18// unfair, it is free: [r/moul/x/daily/tamagotchi] decayed by elapsed/2 and
 19// elapsed/3, so at elapsed == 1 it decayed by nothing at all, and feeding once
 20// per block made the pet immortal while every other cadence died inside 240
 21// blocks. It was fixed in #221.
 22//
 23// The invariant that rules it out is worth stating on its own, because it is
 24// the whole contract of this package:
 25//
 26//	Advance(s, a, c) == Advance(Advance(s, a, b), b, c)   for a <= b <= c
 27//
 28// How often you call must not change where you end up. [Rate.Advance] gets
 29// there by advancing the anchor only by the WHOLE periods it paid for, leaving
 30// the remainder on the clock rather than throwing it away. TestSplitInvariant
 31// asserts it over pseudo-random partitions rather than over a handful of
 32// hand-picked spans, because the hand-picked spans are exactly the ones a
 33// wrong implementation already passes.
 34//
 35// # 2. A view that does not share the write path's arithmetic drifts from it
 36//
 37// The same realm had a second copy of the decay for its Render, so the page
 38// showed a pet the next call would not honour. Two implementations of one rule
 39// means one of them is the stale one somebody acts on. Here there is one
 40// function: [Rate.At] is [Rate.Advance] with the anchor discarded, so a view
 41// cannot disagree with a write even in principle.
 42//
 43// # 3. A projection that is not closed form cannot be rendered at all
 44//
 45// Render runs under a query gas limit and may not write, so whatever it
 46// computes has to be bounded however long the player was away. Anything
 47// iterative, stepping a simulation once per block, is fine in a transaction
 48// and unusable in a page: the player who comes back after a month is exactly
 49// the one whose page times out. Everything here is O(1) in elapsed time, which
 50// is the property that makes a live-updating page possible, not an
 51// 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 drifts
 55// in wall-clock terms every time the chain's block time moves, and gno.land's
 56// has moved from about 4.1s to 3.405s inside one month. Nothing here reads the
 57// chain, so a realm can test a year of its own economy without one.
 58//
 59// A game built on this package is at
 60// [r/moul/x/games/idle](/r/moul/x/games/idle/v0).
 61//
 62// [r/moul/x/daily/tamagotchi]: /r/moul/x/daily/tamagotchi/v0
 63package accrual
 64
 65import "errors"
 66
 67const maxInt64 = int64(9223372036854775807)
 68
 69var (
 70	// ErrBadAmount is returned when the amount produced per period is not
 71	// 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 and
 77	// 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 moving
 83	// backwards is a caller bug (a stored anchor from another clock, a test
 84	// 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)
 89
 90// Rate is production per unit of time, against a ceiling. Construct with New
 91// so the invariants are checked once instead of on every call.
 92type Rate struct {
 93	Amount int64 // produced each whole Period
 94	Period int64 // time units in one period
 95	Cap    int64 // ceiling on the stock; zero means unbounded
 96}
 97
 98// 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{}, ErrBadAmount
102	}
103	if period <= 0 {
104		return Rate{}, ErrBadPeriod
105	}
106	if capacity < 0 {
107		return Rate{}, ErrBadCap
108	}
109	return Rate{Amount: amount, Period: period, Cap: capacity}, nil
110}
111
112// Advance returns the stock and the new anchor at time now, given stock held
113// since anchor.
114//
115// The new anchor is NOT now. It is the anchor plus the whole periods actually
116// paid out, so the part-period in progress stays on the clock and splitting a
117// 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 <= c
120//
121// Production past the cap is lost, which is what a cap is for. Saturation is
122// idempotent, so it does not break the equality above, and it means a CAPPED
123// rate can never return ErrOverflow: the answer is the cap however long the
124// 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, err
128	}
129	if stock < 0 {
130		return 0, 0, ErrNegativeStock
131	}
132	if now < anchor {
133		return 0, 0, ErrBackwards
134	}
135	// now-anchor wraps only when the anchor is negative and now is far
136	// enough above it. maxInt64+anchor is safe to compute precisely because
137	// anchor is negative there.
138	if anchor < 0 && now > maxInt64+anchor {
139		return 0, 0, ErrOverflow
140	}
141
142	periods := (now - anchor) / r.Period
143
144	// The anchor only moves by what was paid for. periods*r.Period cannot
145	// overflow, it is at most now-anchor, and adding it back cannot pass now.
146	newAnchor := anchor + periods*r.Period
147
148	if r.Cap > 0 && stock >= r.Cap {
149		return stock, newAnchor, nil
150	}
151
152	// Production is only computed when its exact value can matter. A capped
153	// rate whose payout would wrap int64 has an answer regardless of what
154	// 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.Amount
159	if produced > maxInt64-stock {
160		return r.saturate(newAnchor)
161	}
162
163	total := stock + produced
164	if r.Cap > 0 && total > r.Cap {
165		total = r.Cap
166	}
167	return total, newAnchor, nil
168}
169
170// 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 also
173// having to bound its own lifetime.
174func (r Rate) saturate(newAnchor int64) (int64, int64, error) {
175	if r.Cap == 0 {
176		return 0, 0, ErrOverflow
177	}
178	return r.Cap, newAnchor, nil
179}
180
181// At is Advance with the anchor discarded: the read-only view of the same
182// arithmetic, for a Render that must not write. It is defined in terms of
183// Advance on purpose, so a page can never show a number a write would not
184// honour.
185func (r Rate) At(stock, anchor, now int64) (int64, error) {
186	got, _, err := r.Advance(stock, anchor, now)
187	return got, err
188}
189
190// Full returns the time at which the stock first reaches the cap, for a realm
191// 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 the
194// 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, err
198	}
199	if stock < 0 {
200		return 0, ErrNegativeStock
201	}
202	if r.Cap == 0 {
203		return 0, nil
204	}
205	if stock >= r.Cap {
206		return anchor, nil
207	}
208
209	// Whole periods needed to cover the shortfall, rounded UP: the cap is
210	// reached by the payout that crosses it, not by the one before.
211	need := r.Cap - stock
212	periods := need / r.Amount
213	if need%r.Amount != 0 {
214		periods++
215	}
216	if periods > maxInt64/r.Period {
217		return 0, ErrOverflow
218	}
219	span := periods * r.Period
220	if span > maxInt64-anchor {
221		return 0, ErrOverflow
222	}
223	return anchor + span, nil
224}
225
226// check rejects a zero Rate built by struct literal instead of New, so a
227// caller that skipped the constructor gets the same error it would have.
228func (r Rate) check() error {
229	if r.Amount <= 0 {
230		return ErrBadAmount
231	}
232	if r.Period <= 0 {
233		return ErrBadPeriod
234	}
235	if r.Cap < 0 {
236		return ErrBadCap
237	}
238	return nil
239}