1// Package checkpoint remembers what a number used to be.2//3// A Series is one value's history. It answers what that value held during a4// past epoch, which is the question governance asks: voting weight has to be5// read as of the moment a question was put, or it can be borrowed for the6// length of one transaction and voted twice.7//8// It was written for a token's balances and its total supply, and there is9// nothing about it that knows what a token is. Anything a realm wants to look10// back at — a fee, a quorum, a member count — is a Series.11//12// # What it costs13//14// One fact about gno shapes the whole thing: storage deposit is charged per15// OBJECT, on the DELTA of its encoded size (gnovm/pkg/gnolang/store.go,16// LastObjectSize, at 100ugnot/byte). A field added to a record that was going17// to be written anyway is paid for once, at creation, and costs nothing on18// every write after. On the EVM every extra word touched is a fresh SSTORE19// forever, which is the entire reason OpenZeppelin's ERC20Votes appends to an20// array per block — and the reason that shape does not have to be inherited.21//22// So: two points inline, the rest paged into an archive. The overwhelmingly23// common query is answered without touching the archive at all, and a value24// that changes several times within one epoch coalesces into a single update25// of a record already being written.26//27// # Epochs, not blocks28//29// The caller supplies the epoch and this package never asks what one is. That30// is deliberate — the clock is policy. Quantising to something coarser than a31// block is what makes the cost work, because a checkpoint per block maximises32// the one thing gno charges dearly for, a brand new key.33//34// It also turns the anti-flash-loan property from a convention into an35// invariant, if the caller refuses to answer for the current epoch: a36// transaction cannot outlive its block and a block cannot outlive its epoch,37// so a borrowed balance cannot be voted and returned. This package cannot38// enforce that, because it does not know what time it is. It is the caller's39// half of the bargain and worth writing down where the caller will read it.40package checkpoint4142import (43 "strings"4445 bptree "gno.land/p/nt/bptree/v0"46)4748// Sep separates a caller's key from this package's own suffix.49//50// Exported because a caller sharing one Archive between several keyspaces51// usually wants the same byte for its own compound keys, and two constants52// with the same value in different files eventually disagree.53//54// A key may not contain it. That is checked rather than documented, because55// the failure is silent: one key's range scan would reach into another's and56// return a plausible number belonging to somebody else.57const Sep = "\x00"5859// MaxKey bounds a key.60//61// A key is not stored once. It is the prefix of every page key this series ever62// writes, so its length multiplies by the number of pages a long-lived value63// accumulates — and the pages are what the design buys with the deposit it64// saves elsewhere.65//66// Exported so a caller can check before calling rather than discover by67// panicking. A hundred and twenty-eight is room for a bech32 address twice over68// with a separator between, which is the largest sensible key the realm this69// came out of could form.70const MaxKey = 1287172// PageEpochs is how many epochs one archive page covers.73//74// It bounds the archive in both directions, and both matter.75//76// Downwards: one new key buys this many checkpoints instead of one, which is77// what keeps the marginal cost of history near zero.78//79// Upwards: a page cannot grow past one bucket. Keeping every checkpoint for a80// key in a single page would be CHEAPER in keys — one per key, forever — and81// that is exactly its problem. Appending stays cheap, since the deposit is82// charged on the size delta, but the whole object is deserialised to answer83// anything about it. A key with years behind it would pay to load all of them84// to answer about one epoch.85const PageEpochs = uint32(32)8687// Archive is the shared store the older points live in.88//89// One Archive can hold any number of Series, told apart by key. Bounding each90// scan to its own key's prefix is what keeps them apart, and it is the reason91// a key may not contain Sep.92type Archive struct {93 t *bptree.BPTree94}9596// NewArchive returns an empty archive.97func NewArchive() *Archive { return &Archive{t: bptree.NewBPTree32()} }9899// Size is the number of pages stored, across every key.100//101// Exported for the caller that wants to assert what its own history costs —102// the count is the number of KEYS bought, which is the expensive quantity.103func (a *Archive) Size() int { return a.t.Size() }104105// page is one bucket of archived checkpoints for one key, ascending.106//107// One packed string, not slices: gno stores a []int64 or []uint32 as an array of108// TypedValues at ~40 bytes an element, but a string (like a []byte) at one byte109// each. So the entries pack big-endian into a single string — 4 bytes of epoch110// then 8 of value, 12 bytes per entry — which is ~3x smaller than the two-slice111// form and is what the archive's locked deposit is charged on. Appending112// reassigns this *page's field (no tree Set), so a write still dirties exactly one113// object.114type page struct {115 packed string // ascending [epoch:4 BE][value:8 BE] entries, 12 bytes each116}117118// Series is one value's history: the two most recent points inline, everything119// older in the archive.120//121// at >= e0 -> cur122// e1 <= at < e0 -> prev123// at < e1 -> the archive124//125// e1 == 0 means the second slot was never used, and prev is then zero, which126// is the correct answer for every epoch below e0 — so a key that has held a127// steady value since it was created never touches the archive at all. That128// case is the overwhelming majority of queries.129//130// That sentinel is why epochs are 1-BASED and SetAt refuses zero. Zero has to131// mean "before this series existed" and cannot also be an epoch somebody wrote132// in, or the two readings collide: a value written at epoch 0 leaves e1 == 0133// after the next change, the roll after that reads it as an empty slot, and the134// point is dropped instead of archived. Silently — the archive stays empty and135// every query below the newest two points answers zero.136//137// The realm this came out of never could have hit it, because its clock is138// 1-based for exactly this reason. The assumption did not travel with the code,139// which is the whole hazard of moving code into a package.140//141// Hold it as a VALUE field in whatever record the caller already persists.142// Mutating it then dirties only that record. A pointer would make it a second143// object, which is a second key, which is the cost this design exists to144// avoid.145type Series struct {146 cur int64147 prev int64148 e0 uint32149 e1 uint32150}151152// Value is what the series holds now, without consulting anything.153func (s *Series) Value() int64 { return s.cur }154155// Prev is the older of the two inline points: its epoch and value. A zero156// epoch means that slot was never used (the series has at most one point).157// Callers assembling a full history read the archive, then Prev, then158// Since/Value — ascending by construction, since points only roll outward.159func (s *Series) Prev() (uint32, int64) { return s.e1, s.prev }160161// Since is the epoch the current value has held from.162//163// Useful for asserting that something did NOT write — a caller that expects an164// operation to be free can check this did not move.165func (s *Series) Since() uint32 { return s.e0 }166167// SetAt records v from epoch e onward, rolling whatever falls out of the two168// inline slots into the archive.169//170// e must be at least 1, and must not be below the newest epoch already171// recorded. Callers pass a chain height quantised to an epoch, which only ever172// increases.173func (s *Series) SetAt(a *Archive, key string, e uint32, v int64) {174 mustBeUsable(key)175 if e == 0 {176 // Refused rather than documented, because the damage is silent and177 // arrives two changes later. See the note on Series: zero is the178 // sentinel for an unused slot, so a real checkpoint written there is179 // read as an empty one and dropped on the roll after next.180 panic("checkpoint: epochs are 1-based; 0 means before the series existed")181 }182 if e < s.e0 {183 // The clock went backwards. Impossible on a chain, so this means the184 // caller is not on one — a test harness that resets the height between185 // cases produces exactly this.186 //187 // Worth a panic rather than a comment because the failure it prevents188 // is invisible: a checkpoint written below the newest one pushes a189 // stale value into the previous slot and moves e0 backwards, and every190 // later query returns a plausible, wrong number.191 panic("checkpoint: the clock went backwards")192 }193 if e == s.e0 {194 // The second and later change within one epoch. No new key, and the195 // object was going to be written anyway: free, in the sense that196 // matters.197 s.cur = v198 return199 }200 if s.e1 != 0 {201 a.append(key, s.e1, s.prev)202 }203 s.prev, s.e1 = s.cur, s.e0204 s.cur, s.e0 = v, e205}206207// ValueAt answers what the series held during epoch at.208//209// Zero for an epoch before the series began, which is exact rather than a210// miss: the key held nothing then.211func (s *Series) ValueAt(a *Archive, key string, at uint32) int64 {212 if at >= s.e0 {213 return s.cur214 }215 // Covers e1 == 0 as well, where prev is zero and zero is exact.216 if at >= s.e1 {217 return s.prev218 }219 mustBeUsable(key)220 out := int64(0)221 // Bounded below by this key's own prefix so the descent cannot walk back222 // into the previous key's pages. ReverseIterate is [start, end] descending223 // with end inclusive (bptree tree.gno, "ReverseIterate calls cb"), which is224 // the floor query — no binary search of our own.225 a.t.ReverseIterate(key+Sep, pageKey(key, at/PageEpochs), func(_ string, pv any) bool {226 s := pv.(*page).packed227 for i := len(s)/12 - 1; i >= 0; i-- {228 off := i * 12229 if rd32(s, off) <= at {230 out = rd64(s, off+4)231 return true232 }233 }234 // Pages bucket EPOCHS, not checkpoints, so the page a query lands in235 // may hold only points later than the epoch being asked about. Keep236 // walking down; the answer is in an older page.237 return false238 })239 return out240}241242func (a *Archive) append(key string, e uint32, v int64) {243 pk := pageKey(key, e/PageEpochs)244 entry := be32(e) + be64(v) // 12 bytes: epoch then value245 if pv := a.t.Get(pk); pv != nil {246 p := pv.(*page)247 // Reassign the field on the pointer the tree already holds. No Set, so the248 // leaf and its whole inner path stay clean and the write dirties only this249 // *page. Entries arrive ascending by construction, so there is nothing to250 // sort.251 p.packed += entry252 return253 }254 a.t.Set(pk, &page{packed: entry})255}256257// mustBeUsable refuses a key that would collide with another key's pages.258//259// A p/ package's callers are not the people who wrote it, so this is a case260// that can happen rather than defensive decoration. The cost is a scan of a261// short key against the tree operations it precedes, which is nothing.262func mustBeUsable(key string) {263 if strings.Contains(key, Sep) {264 panic("checkpoint: a key may not contain checkpoint.Sep")265 }266 if len(key) > MaxKey {267 panic("checkpoint: that key is too long")268 }269 if key == "" {270 // An empty key is not wrong so much as unusable: its page range is a271 // prefix of every other key's, so it would scan into whatever sorts272 // first. Refused for the same reason as one containing the separator.273 panic("checkpoint: a key may not be empty")274 }275}276277// be32 is big-endian and fixed width, so byte order is numeric order.278//279// The floor query is a range scan over these keys and nothing else puts them280// in order. Little-endian would sort pages 0, 1 and 2 correctly and come apart281// at 256.282func be32(u uint32) string {283 b := [4]byte{byte(u >> 24), byte(u >> 16), byte(u >> 8), byte(u)}284 return string(b[:])285}286287// be64 packs an int64 value big-endian (via its uint64 bit pattern, so a negative288// value round-trips through rd64). Together with be32 it forms a page's 12-byte289// entry.290func be64(v int64) string {291 u := uint64(v)292 var b [8]byte293 for i := 7; i >= 0; i-- {294 b[i] = byte(u & 0xff)295 u >>= 8296 }297 return string(b[:])298}299300// rd32 and rd64 read a packed entry's epoch and value back from a page string.301func rd32(s string, off int) uint32 {302 return uint32(s[off])<<24 | uint32(s[off+1])<<16 | uint32(s[off+2])<<8 | uint32(s[off+3])303}304305func rd64(s string, off int) int64 {306 var u uint64307 for i := 0; i < 8; i++ {308 u = (u << 8) | uint64(s[off+i])309 }310 return int64(u)311}312313func pageKey(key string, page uint32) string { return key + Sep + be32(page) }314315// Trim deletes archive pages of key that lie entirely below keepFrom — except316// the newest such page — oldest-first, at most maxPages per call. It returns317// how many pages were removed.318//319// The exception is the floor-preservation invariant: a value set below the320// horizon and unchanged since is still the correct answer for epochs INSIDE321// the kept window, and its floor entry lives in the newest all-below page.322// Sparing that one page keeps ValueAt exact at and above keepFrom through323// every intermediate state of a bounded, multi-call trim. A page straddling324// the horizon is never a candidate (it is not entirely below), so up to325// PageEpochs-1 epochs of over-retention are kept deliberately.326//327// Deletion frees the page object's bytes; on chains with storage deposits the328// locked amount is released by the same mechanism that charged it. Trim never329// touches the two inline points — recent reads stay exact by construction.330//331// The walk is collect-then-remove because the tree forbids mutation from an332// iteration callback, and it is bounded to maxPages+1 keys of collection, so333// a call's cost is a constant of the caller's choosing.334func (a *Archive) Trim(key string, keepFrom uint32, maxPages int) int {335 mustBeUsable(key)336 if maxPages <= 0 {337 return 0338 }339 // Candidates are pages strictly below the horizon's own page: page P340 // covers epochs [P*PageEpochs, P*PageEpochs+PageEpochs-1], so P <341 // keepFrom/PageEpochs puts every epoch in P below keepFrom. Iterate is342 // [start, end) ascending, which is exactly the candidate range.343 end := pageKey(key, keepFrom/PageEpochs)344 keys := []string{}345 a.t.Iterate(key+Sep, end, func(k string, _ any) bool {346 keys = append(keys, k)347 return len(keys) >= maxPages+1348 })349 var del []string350 if len(keys) == maxPages+1 {351 // The budget's worth, oldest-first. The newest collected candidate —352 // and anything beyond it the bounded walk never reached — survives,353 // so the newest all-below page survives.354 del = keys[:maxPages]355 } else if len(keys) > 0 {356 // The walk exhausted the candidates: the last one collected IS the357 // newest all-below page. Spare it.358 del = keys[:len(keys)-1]359 }360 for _, k := range del {361 a.t.Remove(k)362 }363 return len(del)364}365366// WalkDesc visits key's ARCHIVED checkpoints newest-first, stopping when fn367// returns true. The two inline points are the Series' own fields and are not368// visited — a caller assembling a history appends them itself (they are always369// newer than anything archived, because points only ever roll OUT of the370// inline slots). Bounded by the key's page prefix like every other walk here.371func (a *Archive) WalkDesc(key string, fn func(e uint32, v int64) bool) {372 mustBeUsable(key)373 a.t.ReverseIterate(key+Sep, pageKey(key, ^uint32(0)), func(_ string, pv any) bool {374 s := pv.(*page).packed375 for i := len(s)/12 - 1; i >= 0; i-- {376 off := i * 12377 if fn(rd32(s, off), rd64(s, off+4)) {378 return true379 }380 }381 return false382 })383}384Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.