Realm

1// Package compact makes fragmentation a number you can act on.
2//
3// A soft delete does not free anything. It clears the element and leaves the
4// tree node behind, so the bytes stay locked and every read still walks past
5// them. Compacting drops those nodes and the chain refunds their deposit to
6// whoever signed the transaction. So compaction is paid work, and the only
7// real question is WHEN: too early and you free too few nodes to cover the
8// gas, too late and every read has been paying for the holes in between.
9//
10// This realm refuses to answer that question, on purpose. It publishes the
11// two integers the answer is made of and lets whoever is watching decide,
12// because the realm cannot see the gas price of the day and the caller can.
13//
14//   - Fragmentation() is live vs allocated, the free read a bot polls.
15//   - Reclaimable() is what a Compact would actually free, right now.
16//   - Quote() prices it at the floor gas price, as an advertisement.
17//
18// The arithmetic is gno.land/p/moul/x/storagecost and the container is
19// gno.land/p/moul/ulist, whose Compact drops dead nodes without moving a live
20// index, so an index is stable for the life of the realm.
21//
22// # Why this quote is trustworthy where a reaper's is not
23//
24// A reaper advertises what deleting entries will refund, and to do that it has
25// to guess how much state an entry occupies from its payload length. That
26// guess is bad: a per-entry floor dominates at the small end, and one realm
27// under-advertised by 25x on chain because of it.
28//
29// Compaction has no such problem. What it frees is a COUNT of dead nodes, and
30// the container already reports that count exactly. Every node costs the same
31// whatever it carried. So the number on this page is a measured constant times
32// an exact integer, not a ratio applied to a guess, which is why this is the
33// half of the mechanism worth showing first.
34package compact
35
36import (
37	"strings"
38
39	"chain/runtime"
40
41	"gno.land/p/moul/kit/ui/v0"
42	"gno.land/p/moul/md/v0"
43	"gno.land/p/moul/ulist/v1"
44	"gno.land/p/moul/x/storagecost/v1"
45	"gno.land/p/nt/ufmt/v0"
46)
47
48// gasWantedCompact is the gas ceiling a compacting transaction is assumed to
49// ask for, used only to price the advertised bounty. A caller compacting an
50// unusually large number of nodes should re-price with
51// storagecost.EvaluateAtFloor directly rather than trust this.
52const gasWantedCompact int64 = 5_000_000
53
54// maxText caps an entry so one caller cannot lock an unbounded deposit in a
55// single call. Small on purpose: this realm is about the NODES, and a fat
56// payload would only hide the thing it exists to show.
57const maxText = 256
58
59// Entry is one element. Author is kept so a drop can be refused to anyone
60// else: soft-deleting a stranger's entry would be vandalism, and the holes
61// this realm studies should come from ordinary use.
62type Entry struct {
63	Text   string
64	Author address
65	Added  int64 // block height
66}
67
68var entries = ulist.New()
69
70// Add appends an entry and locks its storage deposit against the caller.
71func Add(cur realm, text string) int {
72	if text == "" {
73		panic("compact: empty entry")
74	}
75	if len(text) > maxText {
76		panic(ufmt.Sprintf("compact: entry too long, %d bytes against a %d cap", len(text), maxText))
77	}
78	entries.Append(&Entry{
79		Text:   text,
80		Author: cur.Previous().Address(),
81		Added:  runtime.ChainHeight(),
82	})
83	return entries.TotalSize() - 1
84}
85
86// Drop soft-deletes your own entry, which is what creates a hole.
87//
88// It frees nothing on its own, and that is the point of the realm: the bytes
89// stay locked until somebody compacts. Only the author may drop, so the
90// fragmentation on this page is the honest kind that ordinary use produces.
91func Drop(cur realm, index int) {
92	e, ok := entryAt(index)
93	if !ok {
94		panic(ufmt.Sprintf("compact: no live entry at %d", index))
95	}
96	if e.Author != cur.Previous().Address() {
97		panic("compact: only the author may drop an entry")
98	}
99	entries.MustDelete(index)
100}
101
102// Compact frees the dead tree nodes and returns how many it freed.
103//
104// Permissionless by design, and the refund goes to whoever signs this
105// transaction rather than to the realm or to the authors: the chain pays the
106// signer directly, so there is nothing here to distribute and nothing to
107// steal. The worst a caller can do is waste their own gas compacting a board
108// that had no holes.
109func Compact(cur realm) int {
110	return entries.Compact()
111}
112
113// Fragmentation reports live elements against allocated indices.
114//
115// The gap between them is what a compaction has to work with. It is a free
116// read so a bot can poll it and decide for itself, which is the whole design:
117// the realm publishes, the caller times.
118func Fragmentation() (live, allocated int) {
119	return entries.Size(), entries.TotalSize()
120}
121
122// Reclaimable is how many dead nodes a Compact would free right now.
123//
124// It is NOT the same as allocated minus live. A dead element only becomes a
125// reclaimable node once every element under it is also dead, so a board with
126// many scattered holes can report a large gap and nothing to reclaim. That
127// difference is exactly what makes the timing a decision instead of a rule.
128func Reclaimable() int { return entries.Compactable() }
129
130// Quote prices what a Compact would return, at the default storage price and
131// the floor gas price.
132//
133// Unlike a payload-derived bounty this is a counted quantity: Reclaimable is
134// exact, and storagecost.EstimateNodes multiplies it by a measured per-node
135// constant. Treat it as an advertisement all the same. The authoritative
136// numbers are the chain's, in the StorageUnlockEvent the transaction emits.
137func Quote() storagecost.Quote {
138	return storagecost.EvaluateAtFloor(
139		storagecost.EstimateNodes(int64(Reclaimable())), gasWantedCompact)
140}
141
142// entryAt reads index i, reporting whether a live entry is there.
143func entryAt(i int) (*Entry, bool) {
144	v := entries.Get(i)
145	if v == nil {
146		return nil, false
147	}
148	e, ok := v.(*Entry)
149	return e, ok
150}
151
152func Render(path string) string {
153	var b strings.Builder
154
155	b.WriteString(md.H1("Compact"))
156	b.WriteString("\nSoft-deleting an entry frees nothing: the tree node stays, the bytes stay locked, and every read still walks past the hole. Compacting drops those nodes and the chain refunds their deposit **to whoever signs the transaction**. The only question is when.\n\n")
157
158	live, allocated := Fragmentation()
159	dead := Reclaimable()
160	q := Quote()
161
162	b.WriteString(md.H2("The two integers"))
163	b.WriteString("\n")
164	b.WriteString(md.BulletList([]string{
165		ufmt.Sprintf("**%d live** of **%d allocated** indices%s", live, allocated, ratioSuffix(live, allocated)),
166		ufmt.Sprintf("**%d reclaimable nodes**, about %d bytes of state", dead, q.Bytes),
167		ufmt.Sprintf("refunds roughly **%s** to whoever compacts", storagecost.FormatGNOT(q.Refund)),
168		ufmt.Sprintf("against **%s** of gas at the floor price, break-even at %d bytes", storagecost.FormatGNOT(q.Fee), q.BreakEven),
169		ufmt.Sprintf("verdict: **%s**", verdict(q, dead)),
170	}))
171	b.WriteString("\n")
172
173	if dead > 0 {
174		b.WriteString(ui.Action("Compact it", "Compact") + "\n\n")
175	}
176
177	b.WriteString(md.H2("Why allocated minus live is not the answer"))
178	b.WriteString(ufmt.Sprintf("\nThis board has **%d** unused indices and **%d** reclaimable nodes. A dead element only becomes a reclaimable node once everything under it is dead too, so scattered holes free nothing while a dead tail frees a lot. That is why nobody can write down a rule for when to compact, and why the realm publishes the numbers instead of a schedule.\n\n", allocated-live, dead))
179
180	b.WriteString(md.H2("Board"))
181	b.WriteString("\n")
182	if live == 0 {
183		b.WriteString("Empty. " + ui.Action("Add the first entry", "Add", "text", "hello") + "\n\n")
184	} else {
185		rows := []string{}
186		for i := 0; i < allocated; i++ {
187			e, ok := entryAt(i)
188			if !ok {
189				continue
190			}
191			rows = append(rows, ufmt.Sprintf("`#%d` %s | by %s at height %d",
192				i, ui.Excerpt(strings.ReplaceAll(e.Text, "|", " "), 48), ui.Addr(e.Author), e.Added))
193		}
194		b.WriteString(md.BulletList(rows))
195		b.WriteString("\n")
196	}
197
198	b.WriteString(md.HorizontalRule())
199	b.WriteString("\nThe arithmetic is [p/moul/x/storagecost](/p/moul/x/storagecost/v1); the container is [p/moul/ulist](/p/moul/ulist/v1), whose `Compact` drops dead nodes without moving a live index. The byte figure is an exact node count times a measured per-node constant, which is why it is sounder than a payload-derived bounty, but it is still an estimate: the chain's `StorageUnlockEvent` is the settlement.\n")
200
201	return b.String()
202}
203
204// ratioSuffix adds the fragmentation percentage, and says nothing at all when
205// the board is empty rather than dividing by zero.
206func ratioSuffix(live, allocated int) string {
207	if allocated <= 0 || live == allocated {
208		return ""
209	}
210	return ufmt.Sprintf(", %d%% of indices are holes", (allocated-live)*100/allocated)
211}
212
213func verdict(q storagecost.Quote, dead int) string {
214	if dead == 0 {
215		return "nothing to reclaim, compacting would only burn gas"
216	}
217	if q.Worth() {
218		return "worth " + storagecost.FormatGNOT(q.Net)
219	}
220	return "not worth the gas yet"
221}
222