clock.gno

  1// Package clock is a deadline that actions push forward, with the two guards a
  2// naive "extend on every action" clock lacks.
  3//
  4// Any last-action-wins game has the same clock: every action buys more time, so
  5// 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, a
  9// contested pot is extended forever and the prize is always worth one more
 10// 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 to
 14// relieve the pressure of the first: a grant that is a share of the life left
 15// shrinks toward zero near the end, so the last stretch becomes too short for a
 16// 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 the
 18// 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 can
 22// test its whole endgame without one.
 23//
 24// A game built on this package is at
 25// [r/moul/x/games/lastwords](/r/moul/x/games/lastwords/v0).
 26package clock
 27
 28import "errors"
 29
 30const maxInt64 = int64(9223372036854775807)
 31
 32var (
 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 shorter
 38	// 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 a
 43	// 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)
 48
 49// Clock is a deadline plus the three bounds that make it terminate: the window
 50// 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    int64
 55	deadline int64
 56	window   int64
 57	floor    int64
 58	life     int64 // 0 means unbounded
 59}
 60
 61// 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 the
 64// clock, and must not exceed the window (a floor above the window would mean
 65// every bump granting more than the window, which is not a floor). life is the
 66// total lifetime from now, after which the deadline can no longer move; zero
 67// leaves the clock unbounded, which is the shape that never terminates, so pass
 68// it deliberately.
 69func New(now, window, floor, life int64) (*Clock, error) {
 70	if window <= 0 {
 71		return nil, ErrBadWindow
 72	}
 73	if floor < 0 || floor > window {
 74		return nil, ErrBadFloor
 75	}
 76	if life < 0 || (life > 0 && life < window) {
 77		return nil, ErrBadLife
 78	}
 79	if window > maxInt64-now || life > maxInt64-now {
 80		return nil, ErrOverflow
 81	}
 82	return &Clock{
 83		start:    now,
 84		deadline: now + window,
 85		window:   window,
 86		floor:    floor,
 87		life:     life,
 88	}, nil
 89}
 90
 91// Start returns when the clock opened.
 92func (c *Clock) Start() int64 { return c.start }
 93
 94// Deadline returns the time the clock currently expires at.
 95func (c *Clock) Deadline() int64 { return c.deadline }
 96
 97// Window returns the grant a plain Bump aims for.
 98func (c *Clock) Window() int64 { return c.window }
 99
100// Floor returns the minimum a bump leaves on the clock.
101func (c *Clock) Floor() int64 { return c.floor }
102
103// Life returns the configured lifetime, zero when unbounded.
104func (c *Clock) Life() int64 { return c.life }
105
106// HardEnd returns the time no bump can push the deadline past, or zero when the
107// clock is unbounded.
108func (c *Clock) HardEnd() int64 {
109	if c.life == 0 {
110		return 0
111	}
112	return c.start + c.life
113}
114
115// Expired reports whether the clock has run out at now. The deadline itself is
116// past it: a clock due at 100 is expired at 100, so an action and an expiry can
117// never both be valid at the same instant.
118func (c *Clock) Expired(now int64) bool { return now >= c.deadline }
119
120// 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 0
124	}
125	return c.deadline - now
126}
127
128// 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 0
132	}
133	return now - c.start
134}
135
136// Final reports whether the deadline has reached the hard end, so no further
137// bump can move it. A game should say so on its page: it is the only moment at
138// which holding is worth more than acting.
139func (c *Clock) Final() bool { return c.life > 0 && c.deadline >= c.HardEnd() }
140
141// 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) }
143
144// 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 share
147// of what is left, a function of the amount paid. The clock owns the four
148// invariants that policy keeps getting wrong:
149//
150//   - An expired clock never restarts. Once it has run out the deadline is
151//     frozen, so a late action cannot reopen a settled game.
152//   - The deadline never moves backwards. A small grant late in the game leaves
153//     the existing deadline alone rather than shortening it.
154//   - A bump always leaves at least the floor on the clock, so a decaying grant
155//     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.deadline
160	}
161	if grant < c.floor {
162		grant = c.floor
163	}
164	want := c.deadline
165	if grant <= maxInt64-now && now+grant > want {
166		want = now + grant
167	} else if grant > maxInt64-now {
168		want = maxInt64
169	}
170	if end := c.HardEnd(); c.life > 0 && want > end {
171		want = end
172	}
173	c.deadline = want
174	return c.deadline
175}
176
177// BumpShare grants pct percent of the time left until the hard end, and is the
178// decaying grant a converging game wants.
179//
180// A grant that is a share of what is left on the DEADLINE cannot extend
181// anything: now+(deadline-now)*pct/100 is always before the deadline itself. A
182// share of the distance to the hard end is the one that works. Each action
183// closes a fraction of the gap, so the deadline crawls toward the hard end and
184// the grants shrink as it does, which is exactly the "the pot is worth one more
185// action" pressure a fixed grant never relieves. The floor is what stops the
186// 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, ErrUnbounded
192	}
193	if pct < 0 || pct > 100 {
194		return c.deadline, ErrBadShare
195	}
196	left := c.HardEnd() - now
197	if left < 0 {
198		left = 0
199	}
200	var grant int64
201	if left > maxInt64/100 {
202		grant = left / 100 * pct // lossy, but only where exactness is meaningless
203	} else {
204		grant = left * pct / 100 // multiply first, so a small gap still grants
205	}
206	return c.BumpBy(now, grant), nil
207}