08639A0D227DFD…A4D6D3736DED

Arguments · 11

1. #1compact
2. #2README.md
3. #3# `gno.land/r/moul/x/compact/v0` Fragmentation, as a number you can act on. A soft delete frees nothing. It clears the element and leaves the tree node behind, so 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**. Compaction is therefore paid work, and the only real question is *when*: too early and you free too few nodes to cover the gas, too late and every read has been paying for the holes in between. This realm refuses to answer that question. It publishes the integers the answer is made of and lets whoever is watching decide, because the realm cannot see the gas price of the day and the caller can. ## The interface | | | |---|---| | `Add(text)` | appends an entry and locks its deposit against you | | `Drop(index)` | soft-deletes **your own** entry, which is what creates a hole. Frees nothing | | `Compact()` | drops the dead nodes. Permissionless, and the refund goes to you | | `Fragmentation()` | live against allocated, the free read a bot polls | | `Reclaimable()` | what a `Compact` would actually free right now | | `Quote()` | that, priced, as a `storagecost.Quote` | Only the author may `Drop`, so the fragmentation here is the honest kind that ordinary use produces rather than vandalism. `Compact` stays open to anyone, and that asymmetry is the mechanism: **choosing what dies is owned, reclaiming it is not.** ## Why `allocated - live` is the wrong number The obvious reading of fragmentation is the gap between allocated indices and live elements. It is not what a compaction frees. A dead element only becomes a reclaimable node once **everything under it is also dead**. So a board with many scattered holes reports a large gap and reclaims almost nothing, while a board with a dead tail reclaims a lot from the same gap. `Reclaimable()` is the real number and it is free to read. That is the whole reason this cannot be a schedule or a heuristic baked into the package. The shape of the holes decides, the shape changes with use, and only a caller watching both integers can time it. ## Why this quote is sounder than a reaper's A reaper advertises what deleting entries will refund, and to do that it has to guess how much state an entry occupies from its payload length. That guess is bad at the small end, where a per-entry floor dominates the payload, and one realm under-advertised by **25x** on chain because of it. Compaction has no such problem: | | reaper's bounty | this quote | |---|---|---| | quantity | payload bytes, **guessed** from string length | dead nodes, **counted** by the container | | conversion | a ratio measured at one payload size | a per-node constant, measured twice at 856 bytes | | fails when | entries are small, or the container dominates | never structurally; the constant can drift | `Quote()` is a measured constant times an exact integer. Still an estimate, and the chain's `StorageUnlockEvent` is still the only settlement, but the failure mode that cost a reaper 25x is absent by construction. `TestQuoteCountsNodesRatherThanGuessingFromPayload` pins it: eight entries of 1 byte and eight of 256 produce the identical quote, because the node is what gets freed. ## What it is built from - [`p/moul/ulist`](https://github.com/moul/gno-contracts/tree/main/p/moul/ulist) stores the entries and owns compaction. Its `Compact` drops dead nodes without moving a live index, so an index is stable for the life of the realm. - [`p/moul/x/storagecost`](https://github.com/moul/gno-contracts/tree/main/p/moul/x/storagecost) owns the arithmetic, including `EstimateNodes` and the measured `BytesPerTreeNode`. - [`p/moul/kit/ui`](https://github.com/moul/gno-contracts/tree/main/p/moul/kit/ui) owns the display, including escaping an entry before it reaches the page. ## Related [`r/moul/x/reaper`](https://github.com/moul/gno-contracts/tree/main/r/moul/x/reaper) is the other half: it deletes expired entries, where this one reclaims what deletion left behind. Reap first, then compact, because compaction returns nothing while a live element still sits below the dead ones. <!-- BEGIN GNOCONTRACTS FOOTER (generated by `make readmes`; do not edit below) --> --- Part of **[moul/gno-contracts](https://github.com/moul/gno-contracts)** — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage. **Dependency graph:**  > 🧪 **Highly experimental — potentially vibe-coded.** Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: [DISCLAIMER](https://github.com/moul/gno-contracts/blob/main/DISCLAIMER.md). <!-- END GNOCONTRACTS FOOTER -->
4. #4compact.gno
5. #5// Package compact makes fragmentation a number you can act on. // // A soft delete does not free anything. It clears the element and leaves the // tree node behind, so the bytes stay locked and every read still walks past // them. Compacting drops those nodes and the chain refunds their deposit to // whoever signed the transaction. So compaction is paid work, and the only // real question is WHEN: too early and you free too few nodes to cover the // gas, too late and every read has been paying for the holes in between. // // This realm refuses to answer that question, on purpose. It publishes the // two integers the answer is made of and lets whoever is watching decide, // because the realm cannot see the gas price of the day and the caller can. // // - Fragmentation() is live vs allocated, the free read a bot polls. // - Reclaimable() is what a Compact would actually free, right now. // - Quote() prices it at the floor gas price, as an advertisement. // // The arithmetic is gno.land/p/moul/x/storagecost and the container is // gno.land/p/moul/ulist, whose Compact drops dead nodes without moving a live // index, so an index is stable for the life of the realm. // // # Why this quote is trustworthy where a reaper's is not // // A reaper advertises what deleting entries will refund, and to do that it has // to guess how much state an entry occupies from its payload length. That // guess is bad: a per-entry floor dominates at the small end, and one realm // under-advertised by 25x on chain because of it. // // Compaction has no such problem. What it frees is a COUNT of dead nodes, and // the container already reports that count exactly. Every node costs the same // whatever it carried. So the number on this page is a measured constant times // an exact integer, not a ratio applied to a guess, which is why this is the // half of the mechanism worth showing first. package compact import ( "strings" "chain/runtime" "gno.land/p/moul/kit/ui/v0" "gno.land/p/moul/md/v0" "gno.land/p/moul/ulist/v1" "gno.land/p/moul/x/storagecost/v1" "gno.land/p/nt/ufmt/v0" ) // gasWantedCompact is the gas ceiling a compacting transaction is assumed to // ask for, used only to price the advertised bounty. A caller compacting an // unusually large number of nodes should re-price with // storagecost.EvaluateAtFloor directly rather than trust this. const gasWantedCompact int64 = 5_000_000 // maxText caps an entry so one caller cannot lock an unbounded deposit in a // single call. Small on purpose: this realm is about the NODES, and a fat // payload would only hide the thing it exists to show. const maxText = 256 // Entry is one element. Author is kept so a drop can be refused to anyone // else: soft-deleting a stranger's entry would be vandalism, and the holes // this realm studies should come from ordinary use. type Entry struct { Text string Author address Added int64 // block height } var entries = ulist.New() // Add appends an entry and locks its storage deposit against the caller. func Add(cur realm, text string) int { if text == "" { panic("compact: empty entry") } if len(text) > maxText { panic(ufmt.Sprintf("compact: entry too long, %d bytes against a %d cap", len(text), maxText)) } entries.Append(&Entry{ Text: text, Author: cur.Previous().Address(), Added: runtime.ChainHeight(), }) return entries.TotalSize() - 1 } // Drop soft-deletes your own entry, which is what creates a hole. // // It frees nothing on its own, and that is the point of the realm: the bytes // stay locked until somebody compacts. Only the author may drop, so the // fragmentation on this page is the honest kind that ordinary use produces. func Drop(cur realm, index int) { e, ok := entryAt(index) if !ok { panic(ufmt.Sprintf("compact: no live entry at %d", index)) } if e.Author != cur.Previous().Address() { panic("compact: only the author may drop an entry") } entries.MustDelete(index) } // Compact frees the dead tree nodes and returns how many it freed. // // Permissionless by design, and the refund goes to whoever signs this // transaction rather than to the realm or to the authors: the chain pays the // signer directly, so there is nothing here to distribute and nothing to // steal. The worst a caller can do is waste their own gas compacting a board // that had no holes. func Compact(cur realm) int { return entries.Compact() } // Fragmentation reports live elements against allocated indices. // // The gap between them is what a compaction has to work with. It is a free // read so a bot can poll it and decide for itself, which is the whole design: // the realm publishes, the caller times. func Fragmentation() (live, allocated int) { return entries.Size(), entries.TotalSize() } // Reclaimable is how many dead nodes a Compact would free right now. // // It is NOT the same as allocated minus live. A dead element only becomes a // reclaimable node once every element under it is also dead, so a board with // many scattered holes can report a large gap and nothing to reclaim. That // difference is exactly what makes the timing a decision instead of a rule. func Reclaimable() int { return entries.Compactable() } // Quote prices what a Compact would return, at the default storage price and // the floor gas price. // // Unlike a payload-derived bounty this is a counted quantity: Reclaimable is // exact, and storagecost.EstimateNodes multiplies it by a measured per-node // constant. Treat it as an advertisement all the same. The authoritative // numbers are the chain's, in the StorageUnlockEvent the transaction emits. func Quote() storagecost.Quote { return storagecost.EvaluateAtFloor( storagecost.EstimateNodes(int64(Reclaimable())), gasWantedCompact) } // entryAt reads index i, reporting whether a live entry is there. func entryAt(i int) (*Entry, bool) { v := entries.Get(i) if v == nil { return nil, false } e, ok := v.(*Entry) return e, ok } func Render(path string) string { var b strings.Builder b.WriteString(md.H1("Compact")) 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") live, allocated := Fragmentation() dead := Reclaimable() q := Quote() b.WriteString(md.H2("The two integers")) b.WriteString("\n") b.WriteString(md.BulletList([]string{ ufmt.Sprintf("**%d live** of **%d allocated** indices%s", live, allocated, ratioSuffix(live, allocated)), ufmt.Sprintf("**%d reclaimable nodes**, about %d bytes of state", dead, q.Bytes), ufmt.Sprintf("refunds roughly **%s** to whoever compacts", storagecost.FormatGNOT(q.Refund)), ufmt.Sprintf("against **%s** of gas at the floor price, break-even at %d bytes", storagecost.FormatGNOT(q.Fee), q.BreakEven), ufmt.Sprintf("verdict: **%s**", verdict(q, dead)), })) b.WriteString("\n") if dead > 0 { b.WriteString(ui.Action("Compact it", "Compact") + "\n\n") } b.WriteString(md.H2("Why allocated minus live is not the answer")) 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)) b.WriteString(md.H2("Board")) b.WriteString("\n") if live == 0 { b.WriteString("Empty. " + ui.Action("Add the first entry", "Add", "text", "hello") + "\n\n") } else { rows := []string{} for i := 0; i < allocated; i++ { e, ok := entryAt(i) if !ok { continue } rows = append(rows, ufmt.Sprintf("`#%d` %s | by %s at height %d", i, ui.Excerpt(strings.ReplaceAll(e.Text, "|", " "), 48), ui.Addr(e.Author), e.Added)) } b.WriteString(md.BulletList(rows)) b.WriteString("\n") } b.WriteString(md.HorizontalRule()) 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") return b.String() } // ratioSuffix adds the fragmentation percentage, and says nothing at all when // the board is empty rather than dividing by zero. func ratioSuffix(live, allocated int) string { if allocated <= 0 || live == allocated { return "" } return ufmt.Sprintf(", %d%% of indices are holes", (allocated-live)*100/allocated) } func verdict(q storagecost.Quote, dead int) string { if dead == 0 { return "nothing to reclaim, compacting would only burn gas" } if q.Worth() { return "worth " + storagecost.FormatGNOT(q.Net) } return "not worth the gas yet" }
6. #6compact_test.gno
7. #7package compact import ( "strings" "testing" "gno.land/p/moul/kit/ui/v0" "gno.land/p/moul/x/storagecost/v1" "gno.land/p/nt/testutils/v0" "gno.land/p/nt/uassert/v0" ) var ( alice = testutils.TestAddress("alice") bob = testutils.TestAddress("bob") // janitor never adds anything, it only compacts. The whole point of the // realm is that this is the address the chain pays. janitor = testutils.TestAddress("janitor") ) // drain empties the board and asserts it, so a test starts from a known // state whatever ran before it. Indices are append-addressed for the life of // the realm, so every test asserts on counts and never on absolute indices. func drain(cur realm, t *testing.T) { t.Helper() for i := 0; i < entries.TotalSize(); i++ { if e, ok := entryAt(i); ok { testing.SetRealm(testing.NewUserRealm(e.Author)) Drop(cross(cur), i) } } testing.SetRealm(testing.NewUserRealm(janitor)) Compact(cross(cur)) live, _ := Fragmentation() uassert.Equal(t, 0, live) } func TestDropFreesNothingUntilCompact(cur realm, t *testing.T) { drain(cur, t) testing.SetRealm(testing.NewUserRealm(alice)) for i := 0; i < 8; i++ { Add(cross(cur), "entry") } live, allocated := Fragmentation() uassert.Equal(t, 8, live) uassert.Equal(t, 0, Reclaimable()) // Dropping everything moves the live count but frees no nodes by itself. base := allocated - 8 for i := base; i < allocated; i++ { Drop(cross(cur), i) } live, allocated2 := Fragmentation() uassert.Equal(t, 0, live) uassert.Equal(t, allocated, allocated2, "a soft delete must not change the index space") uassert.True(t, Reclaimable() > 0, "a fully dead tail should be reclaimable") // And compaction is what actually frees them. testing.SetRealm(testing.NewUserRealm(janitor)) freed := Compact(cross(cur)) uassert.True(t, freed > 0) uassert.Equal(t, 0, Reclaimable()) // Compacting twice is not an error, it just frees nothing, so two bots // racing for the same nodes both survive rather than one aborting. uassert.Equal(t, 0, Compact(cross(cur))) } // TestScatteredHolesReclaimLessThanTheGap is the claim the Render makes, and // the reason the realm publishes two numbers instead of one. No other test // could catch it: they all drop contiguous runs. func TestScatteredHolesReclaimLessThanTheGap(cur realm, t *testing.T) { drain(cur, t) testing.SetRealm(testing.NewUserRealm(alice)) base := entries.TotalSize() for i := 0; i < 16; i++ { Add(cross(cur), "entry") } // Every other index, so no whole subtree dies. for i := base; i < base+16; i += 2 { Drop(cross(cur), i) } live, allocated := Fragmentation() gap := allocated - live uassert.True(t, gap >= 8, "eight holes were made") uassert.True(t, Reclaimable() < gap, "scattered holes must reclaim fewer nodes than the gap suggests") drain(cur, t) } func TestOnlyTheAuthorMayDrop(cur realm, t *testing.T) { drain(cur, t) testing.SetRealm(testing.NewUserRealm(alice)) i := Add(cross(cur), "alice's entry") testing.SetRealm(testing.NewUserRealm(bob)) uassert.AbortsWithMessage(t, cur, "compact: only the author may drop an entry", func() { Drop(cross(cur), i) }) // But compaction stays permissionless, which is the asymmetry that makes // the mechanism work: choosing what dies is owned, reclaiming is not. testing.SetRealm(testing.NewUserRealm(janitor)) uassert.NotAborts(t, cur, func() { Compact(cross(cur)) }) drain(cur, t) } func TestAddRejectsBadInput(cur realm, t *testing.T) { drain(cur, t) testing.SetRealm(testing.NewUserRealm(alice)) uassert.AbortsWithMessage(t, cur, "compact: empty entry", func() { Add(cross(cur), "") }) uassert.AbortsWithMessage(t, cur, "compact: entry too long, 257 bytes against a 256 cap", func() { Add(cross(cur), strings.Repeat("x", maxText+1)) }) uassert.AbortsContains(t, cur, "compact: no live entry at", func() { Drop(cross(cur), 99999) }) } // TestQuoteCountsNodesRatherThanGuessingFromPayload is the design claim of the // realm. The quote must depend on the NODE COUNT and not on how fat the // entries were, which is exactly where a payload-derived bounty goes wrong. func TestQuoteCountsNodesRatherThanGuessingFromPayload(cur realm, t *testing.T) { drain(cur, t) // An empty board advertises nothing and must not claim a profit. empty := Quote() uassert.Equal(t, int64(0), empty.Bytes) uassert.False(t, empty.Worth()) // Eight tiny entries, dropped and measured. testing.SetRealm(testing.NewUserRealm(alice)) base := entries.TotalSize() for i := 0; i < 8; i++ { Add(cross(cur), "x") } for i := base; i < base+8; i++ { Drop(cross(cur), i) } tiny := Quote() tinyNodes := Reclaimable() testing.SetRealm(testing.NewUserRealm(janitor)) Compact(cross(cur)) // Eight fat entries, same count, same treatment. testing.SetRealm(testing.NewUserRealm(alice)) base = entries.TotalSize() fat := strings.Repeat("y", maxText) for i := 0; i < 8; i++ { Add(cross(cur), fat) } for i := base; i < base+8; i++ { Drop(cross(cur), i) } big := Quote() bigNodes := Reclaimable() // 256x the payload, and the quote is still purely a function of the node // count. Not the same TOTAL: the two batches sit at different offsets in // an append-addressed index space, so the tree shape differs and one // reclaimed a node more than the other. That is the honest version of the // claim, and asserting equal totals (which an earlier draft of this test // did) only passed by luck of the offsets. uassert.True(t, tinyNodes > 0 && bigNodes > 0) uassert.Equal(t, storagecost.EstimateNodes(int64(tinyNodes)), tiny.Bytes) uassert.Equal(t, storagecost.EstimateNodes(int64(bigNodes)), big.Bytes) // The rate is what must not move: same bytes per reclaimed node whether // the entries were 1 byte or 256. A payload-derived bounty would differ // by 256x here, which is the failure this realm is built to avoid. uassert.Equal(t, tiny.Bytes/int64(tinyNodes), big.Bytes/int64(bigNodes), "bytes per reclaimed node must not depend on payload size") drain(cur, t) } // TestRenderEscapesTheBoard: an entry is a caller's string landing in an // inline markdown slot, so it goes through ui.Excerpt or it is an injection. func TestRenderEscapesTheBoard(cur realm, t *testing.T) { drain(cur, t) testing.SetRealm(testing.NewUserRealm(alice)) Add(cross(cur), "[Claim 100 GNOT](https://evil.example)\n# Official") out := Render("") uassert.False(t, strings.Contains(out, "](https://evil.example)"), out) uassert.False(t, strings.Contains(out, "\n# Official"), out) uassert.True(t, strings.Contains(out, "Claim 100 GNOT"), out) uassert.True(t, strings.Contains(out, ui.Addr(alice)), out) drain(cur, t) } func TestRenderShowsBothIntegersAndTheAction(cur realm, t *testing.T) { drain(cur, t) out := Render("") uassert.True(t, strings.Contains(out, "# Compact"), out) uassert.True(t, strings.Contains(out, "Add the first entry"), out) uassert.True(t, strings.Contains(out, "nothing to reclaim"), out) testing.SetRealm(testing.NewUserRealm(alice)) base := entries.TotalSize() for i := 0; i < 8; i++ { Add(cross(cur), "entry") } for i := base; i < base+8; i++ { Drop(cross(cur), i) } out = Render("") uassert.True(t, strings.Contains(out, "reclaimable nodes"), out) uassert.True(t, strings.Contains(out, "$help&func=Compact"), out) drain(cur, t) } // TestRenderNeverEmitsTwoBlankLines is what lets ExampleRender stay // meaningful: gno collapses them, so output containing them can never be // pinned by an example. func TestRenderNeverEmitsTwoBlankLines(cur realm, t *testing.T) { drain(cur, t) testing.SetRealm(testing.NewUserRealm(alice)) i := Add(cross(cur), "one") Add(cross(cur), "two") Drop(cross(cur), i) for _, path := range []string{"", "anything"} { out := Render(path) uassert.False(t, strings.Contains(out, "\n\n\n"), "blank-line run in Render("+path+")") } drain(cur, t) }
8. #8example_test.gno
9. #9package compact import "strings" // ExampleRender pins the page's skeleton: the title and the three sections // that are always there, whatever the board holds. // // Only the invariant lines, on purpose. Everything else on the page is // derived from the current fragmentation, and an Example runs after every // Test in the package and sees whatever state they left. The variable half is // pinned by TestRenderShowsBothIntegersAndTheAction, which controls the board // first. func ExampleRender() { for _, line := range strings.Split(Render(""), "\n") { switch { case strings.HasPrefix(line, "# "), strings.HasPrefix(line, "## "), strings.HasPrefix(line, "Soft-deleting"): print(line + "\n") } } // Output: // # Compact // Soft-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. // ## The two integers // ## Why allocated minus live is not the answer // ## Board }
10. #10gnomod.toml
11. #11module = "gno.land/r/moul/x/compact/v0" gno = "0.9" private = true