Skip to content Search Apps Documentation Source Content Run Reset Eval Playground File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Playground

compact.gno

// 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"
}

compact_test.gno

package 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)
}

example_test.gno

package 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
}

gnomod.toml

module = "gno.land/r/moul/x/compact/v0"
gno = "0.9"
private = true

[addpkg]
  creator = "g1manfred47kzduec920z88wfr64ylksmdcedlf5"
  height = 410019
  max_deposit = "10000000ugnot"