1// Package clock is a deadline that actions push forward, with the two guards a2// naive "extend on every action" clock lacks.3//4// Any last-action-wins game has the same clock: every action buys more time, so5// the game ends only when nobody acts. Written naively it has two failure modes,6// and both have been observed on chain rather than reasoned about.7//8// The first is that it never ends. If the grant per action is constant, a9// contested pot is extended forever and the prize is always worth one more10// action. Life is the terminator: an absolute end, fixed when the clock opens,11// that no bump can pass. A game with real money in it needs one.12//13// The second is the opposite, and it shows up as soon as the grant decays to14// relieve the pressure of the first: a grant that is a share of the life left15// shrinks toward zero near the end, so the last stretch becomes too short for a16// transaction to land in, and whoever is holding when that happens simply wins.17// Floor is the anti-snipe: a bump always leaves at least that much on the18// clock, however little is left to share.19//20// Times are int64 and the unit is the caller's: block heights or unix seconds,21// as long as it is consistent. Nothing here reads the chain, so a realm can22// test its whole endgame without one.23//24// A game built on this package is at25// [r/moul/x/games/lastwords](/r/moul/x/games/lastwords/v0).26package clock2728import "errors"2930const maxInt64 = int64(9223372036854775807)3132var (33 // ErrBadWindow is returned when the opening grant is not positive.34 ErrBadWindow = errors.New("clock: window must be positive")35 // ErrBadFloor is returned when the floor is negative or exceeds the window.36 ErrBadFloor = errors.New("clock: floor must be between zero and the window")37 // ErrBadLife is returned when the life is negative, or positive but shorter38 // than the opening window, which would close the clock before it opened.39 ErrBadLife = errors.New("clock: life must be zero (unbounded) or at least the window")40 // ErrBadShare is returned when a share is outside 0..100.41 ErrBadShare = errors.New("clock: share must be a percentage between 0 and 100")42 // ErrUnbounded is returned when a share of the remaining life is asked of a43 // clock that has no hard end to measure against.44 ErrUnbounded = errors.New("clock: a share of the life needs a bounded clock")45 // ErrOverflow is returned when the requested times do not fit in an int64.46 ErrOverflow = errors.New("clock: times overflow int64")47)4849// Clock is a deadline plus the three bounds that make it terminate: the window50// a bump grants, the floor a bump always leaves, and the life it can never pass.51//52// The zero Clock is not usable; build one with New.53type Clock struct {54 start int6455 deadline int6456 window int6457 floor int6458 life int64 // 0 means unbounded59}6061// New opens a clock at now, due now+window.62//63// window is what a plain Bump grants. floor is the minimum a bump leaves on the64// clock, and must not exceed the window (a floor above the window would mean65// every bump granting more than the window, which is not a floor). life is the66// total lifetime from now, after which the deadline can no longer move; zero67// leaves the clock unbounded, which is the shape that never terminates, so pass68// it deliberately.69func New(now, window, floor, life int64) (*Clock, error) {70 if window <= 0 {71 return nil, ErrBadWindow72 }73 if floor < 0 || floor > window {74 return nil, ErrBadFloor75 }76 if life < 0 || (life > 0 && life < window) {77 return nil, ErrBadLife78 }79 if window > maxInt64-now || life > maxInt64-now {80 return nil, ErrOverflow81 }82 return &Clock{83 start: now,84 deadline: now + window,85 window: window,86 floor: floor,87 life: life,88 }, nil89}9091// Start returns when the clock opened.92func (c *Clock) Start() int64 { return c.start }9394// Deadline returns the time the clock currently expires at.95func (c *Clock) Deadline() int64 { return c.deadline }9697// Window returns the grant a plain Bump aims for.98func (c *Clock) Window() int64 { return c.window }99100// Floor returns the minimum a bump leaves on the clock.101func (c *Clock) Floor() int64 { return c.floor }102103// Life returns the configured lifetime, zero when unbounded.104func (c *Clock) Life() int64 { return c.life }105106// HardEnd returns the time no bump can push the deadline past, or zero when the107// clock is unbounded.108func (c *Clock) HardEnd() int64 {109 if c.life == 0 {110 return 0111 }112 return c.start + c.life113}114115// Expired reports whether the clock has run out at now. The deadline itself is116// past it: a clock due at 100 is expired at 100, so an action and an expiry can117// never both be valid at the same instant.118func (c *Clock) Expired(now int64) bool { return now >= c.deadline }119120// Remaining returns how much time is left at now, never negative.121func (c *Clock) Remaining(now int64) int64 {122 if now >= c.deadline {123 return 0124 }125 return c.deadline - now126}127128// Elapsed returns how long the clock has been open at now, never negative.129func (c *Clock) Elapsed(now int64) int64 {130 if now <= c.start {131 return 0132 }133 return now - c.start134}135136// Final reports whether the deadline has reached the hard end, so no further137// bump can move it. A game should say so on its page: it is the only moment at138// which holding is worth more than acting.139func (c *Clock) Final() bool { return c.life > 0 && c.deadline >= c.HardEnd() }140141// Bump extends the deadline by the window. See BumpBy for the guards.142func (c *Clock) Bump(now int64) int64 { return c.BumpBy(now, c.window) }143144// BumpBy extends the deadline to now+grant and returns the new deadline.145//146// The caller owns the policy, so grant is whatever it wants: a constant, a share147// of what is left, a function of the amount paid. The clock owns the four148// invariants that policy keeps getting wrong:149//150// - An expired clock never restarts. Once it has run out the deadline is151// frozen, so a late action cannot reopen a settled game.152// - The deadline never moves backwards. A small grant late in the game leaves153// the existing deadline alone rather than shortening it.154// - A bump always leaves at least the floor on the clock, so a decaying grant155// cannot be shaved below the time a transaction needs to land.156// - The deadline never passes the hard end.157func (c *Clock) BumpBy(now, grant int64) int64 {158 if c.Expired(now) {159 return c.deadline160 }161 if grant < c.floor {162 grant = c.floor163 }164 want := c.deadline165 if grant <= maxInt64-now && now+grant > want {166 want = now + grant167 } else if grant > maxInt64-now {168 want = maxInt64169 }170 if end := c.HardEnd(); c.life > 0 && want > end {171 want = end172 }173 c.deadline = want174 return c.deadline175}176177// BumpShare grants pct percent of the time left until the hard end, and is the178// decaying grant a converging game wants.179//180// A grant that is a share of what is left on the DEADLINE cannot extend181// anything: now+(deadline-now)*pct/100 is always before the deadline itself. A182// share of the distance to the hard end is the one that works. Each action183// closes a fraction of the gap, so the deadline crawls toward the hard end and184// the grants shrink as it does, which is exactly the "the pot is worth one more185// action" pressure a fixed grant never relieves. The floor is what stops the186// tail of that curve from becoming too short to act in.187//188// It requires a bounded clock: there is no distance to share without one.189func (c *Clock) BumpShare(now, pct int64) (int64, error) {190 if c.life == 0 {191 return c.deadline, ErrUnbounded192 }193 if pct < 0 || pct > 100 {194 return c.deadline, ErrBadShare195 }196 left := c.HardEnd() - now197 if left < 0 {198 left = 0199 }200 var grant int64201 if left > maxInt64/100 {202 grant = left / 100 * pct // lossy, but only where exactness is meaningless203 } else {204 grant = left * pct / 100 // multiply first, so a small gap still grants205 }206 return c.BumpBy(now, grant), nil207}208Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.