Playground
bfdemo.gno
// Package bfdemo is the playground for the guest-VM work: a realm that runs
// Brainfuck programs on chain, a slice at a time.
//
// It is a demo of two libraries and carries no logic of its own:
// [p/moul/x/vm/bf](/p/moul/x/vm/bf/v0) is the machine, and
// [p/moul/x/vm/vmkit](/p/moul/x/vm/vmkit/v0) is the host ABI, the fuel meter
// and the instance store.
//
// What it exists to show is the thing gno realm code cannot do for itself: a
// program that runs out of fuel does not fail, it pauses. The realm keeps the
// snapshot, and the next caller pays for the next slice. Upload a program,
// call Step a few times, and watch one computation finish across several
// transactions.
package bfdemo
import (
"chain"
"chain/runtime"
"chain/runtime/unsafe"
"time"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/vm/bf/v0"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/vm/vmkit/v0"
"gno.land/p/nt/avl/v0"
"gno.land/p/nt/seqid/v0"
"gno.land/p/nt/ufmt/v0"
)
// Caps. Everything a caller can grow is bounded, because all of it is storage
// somebody pays a deposit on.
const (
// MaxInstances is how many programs the realm keeps at once. Past it,
// an upload has to wait for someone to remove one.
MaxInstances = 64
// MaxOutput caps the bytes one program may write. Past it the guest is
// trapped rather than truncated, so rendered output is never a lie.
MaxOutput = 4096
// MaxInput caps the call input a program can be given.
MaxInput = 1024
// DefaultFuel is the budget an upload gets when it asks for none, and
// the slice size Step uses when asked for none.
DefaultFuel = 100000
// MaxSliceFuel bounds one transaction's work regardless of what the
// caller asked for.
MaxSliceFuel = 5000000
)
var (
// store holds the instances: program, snapshot, status, accounting.
store = vmkit.NewStore()
// inputs holds each instance's call input, keyed by id. It is separate
// from the instance so vmkit.Instance stays the VM-agnostic record it
// is meant to be.
inputs = avl.NewTree()
idgen seqid.ID
count int
)
// host is the realm-backed [vmkit.Host]. One is built per call, wrapping the
// instance being stepped, so a guest's output and authority are scoped to it
// and nothing ambient leaks in.
type host struct {
inst *vmkit.Instance
in []byte
kv *avl.Tree
overrun bool // the guest wrote past MaxOutput
}
func (h *host) Caller() address { return h.inst.Owner }
func (h *host) Origin() address { return h.inst.Owner }
func (h *host) Now() int64 { return time.Now().Unix() }
func (h *host) Height() int64 { return runtime.ChainHeight() }
func (h *host) Input() []byte { return h.in }
// Get and Set are scoped to the instance by construction: the tree belongs to
// the instance being stepped, so one program cannot reach another's storage
// even though both live in this one realm. bf never calls them; they are here
// because the ABI is the point.
func (h *host) Get(key []byte) []byte {
v := h.kv.Get(string(key))
if v == nil {
return nil
}
return v.([]byte)
}
func (h *host) Set(key, val []byte) { h.kv.Set(string(key), val) }
func (h *host) Output(p []byte) {
if len(h.inst.Output)+len(p) > MaxOutput {
h.overrun = true
return
}
h.inst.Output = append(h.inst.Output, p...)
}
func (h *host) Emit(typ string, kv ...string) { chain.Emit(typ, kv...) }
// Send is never granted here. The demo funds no instance, so a guest that
// tries to move coins is refused. That is the capability rule doing its job,
// not a missing feature.
func (h *host) Send(to address, amount int64) error { return vmkit.ErrNotGranted }
func (h *host) Log(msg string) {}
// Upload compiles src and stores it as a new instance, returning its id.
//
// Compilation happens here rather than at the first Step, so an unbalanced
// program is rejected by the transaction that submitted it instead of costing
// somebody else the gas later.
func Upload(cur realm, src, input string, budget int64) string {
if count >= MaxInstances {
panic("bfdemo: too many instances, remove one first")
}
if len(input) > MaxInput {
panic("bfdemo: input too long")
}
if _, err := bf.CompileDefault(src); err != nil {
panic("bfdemo: " + err.Error())
}
if budget <= 0 {
budget = DefaultFuel
}
id := idgen.Next().String()
owner := unsafe.PreviousRealm().Address()
store.Set(vmkit.NewInstance(id, owner, bf.VMName, []byte(src), budget))
if input != "" {
inputs.Set(id, input)
}
count++
chain.Emit("bf_upload", "id", id, "bytes", ufmt.Sprintf("%d", len(src)))
return id
}
// Step runs one slice of the instance: up to `fuel` guest ops, then stop and
// keep the snapshot. Anyone may pay for a slice, not only the owner: a paused
// program that only its owner can advance is a worse demo and no safer, since
// the program and its budget were both fixed at upload.
func Step(cur realm, id string, fuel int64) string {
inst := store.Get(id)
if inst == nil {
panic("bfdemo: no such instance")
}
if inst.Status != vmkit.Running {
panic("bfdemo: instance is " + inst.Status.String())
}
if fuel <= 0 {
fuel = DefaultFuel
}
if fuel > MaxSliceFuel {
fuel = MaxSliceFuel
}
prog, err := bf.CompileDefault(string(inst.Program))
if err != nil {
panic("bfdemo: " + err.Error())
}
h := &host{inst: inst, in: []byte(inputOf(id)), kv: avl.NewTree()}
if err := inst.Run(bf.NewMachine(prog), h, fuel); err != nil {
panic("bfdemo: " + err.Error())
}
if h.overrun {
inst.Status = vmkit.Trapped
inst.Trap = "output limit reached"
}
chain.Emit("bf_step",
"id", id,
"status", inst.Status.String(),
"fuel", ufmt.Sprintf("%d", inst.FuelUsed),
)
return inst.Status.String()
}
// Remove deletes an instance. Owner only.
func Remove(cur realm, id string) {
inst := store.Get(id)
if inst == nil {
panic("bfdemo: no such instance")
}
if inst.Owner != unsafe.PreviousRealm().Address() {
panic("bfdemo: not your instance")
}
store.Remove(id)
inputs.Remove(id)
count--
}
func inputOf(id string) string {
v := inputs.Get(id)
if v == nil {
return ""
}
return v.(string)
}
bfdemo_test.gno
package bfdemo
import (
"strings"
"testing"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/vm/vmkit/v0"
"gno.land/p/nt/avl/v0"
"gno.land/p/nt/seqid/v0"
"gno.land/p/nt/testutils/v0"
"gno.land/p/nt/uassert/v0"
)
const hello = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------."
// resetState puts the realm globals back where init() left them. Realm state
// persists for the whole test binary, so every test that asserts on ids or on
// the rendered instance list has to start from here.
func resetState() {
store = vmkit.NewStore()
inputs = avl.NewTree()
idgen = seqid.ID(0)
count = 0
}
func TestUploadAndRunToCompletion(cur realm, t *testing.T) {
resetState()
alice := testutils.TestAddress("alice")
testing.SetRealm(testing.NewUserRealm(alice))
id := Upload(cross(cur), hello, "", 0)
uassert.Equal(t, "halted", Step(cross(cur), id, 0))
inst := store.Get(id)
uassert.Equal(t, "Hello World", string(inst.Output))
uassert.Equal(t, int64(1), inst.Slices)
uassert.Equal(t, alice, inst.Owner)
}
// TestOneProgramAcrossManyTransactions is what the realm exists to
// demonstrate: the same computation, finished over several calls, each paying
// for its own slice.
func TestOneProgramAcrossManyTransactions(cur realm, t *testing.T) {
resetState()
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("alice")))
id := Upload(cross(cur), hello, "", 0)
status := ""
slices := 0
for slices < 500 {
status = Step(cross(cur), id, 7)
slices++
if status != "running" {
break
}
}
inst := store.Get(id)
uassert.Equal(t, "halted", status)
uassert.Equal(t, "Hello World", string(inst.Output))
uassert.True(t, inst.Slices > 1, "took more than one slice")
}
func TestInputIsReadThroughTheHost(cur realm, t *testing.T) {
resetState()
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("alice")))
// ",[.,]" echoes its input back.
id := Upload(cross(cur), ",[.,]", "gno.land", 0)
uassert.Equal(t, "halted", Step(cross(cur), id, 0))
uassert.Equal(t, "gno.land", string(store.Get(id).Output))
}
func TestBudgetStopsAProgram(cur realm, t *testing.T) {
resetState()
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("alice")))
id := Upload(cross(cur), hello, "", 12)
uassert.Equal(t, "out of fuel", Step(cross(cur), id, 0))
uassert.Equal(t, int64(12), store.Get(id).FuelUsed)
// And it stays stopped rather than quietly continuing.
uassert.AbortsContains(t, cur, "instance is out of fuel", func() {
Step(cross(cur), id, 0)
})
}
func TestUploadRejectsAMalformedProgram(cur realm, t *testing.T) {
resetState()
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("alice")))
// Rejected by the transaction that submitted it, not by whoever pays
// for the first slice later.
uassert.AbortsContains(t, cur, "unmatched", func() {
Upload(cross(cur), "+++[", "", 0)
})
uassert.Equal(t, 0, count)
}
func TestRemoveIsOwnerOnly(cur realm, t *testing.T) {
resetState()
alice := testutils.TestAddress("alice")
bob := testutils.TestAddress("bob")
testing.SetRealm(testing.NewUserRealm(alice))
id := Upload(cross(cur), hello, "", 0)
testing.SetRealm(testing.NewUserRealm(bob))
uassert.AbortsContains(t, cur, "not your instance", func() {
Remove(cross(cur), id)
})
// Anyone may pay for a slice, though: the program and its budget were
// both fixed at upload.
uassert.Equal(t, "halted", Step(cross(cur), id, 0))
testing.SetRealm(testing.NewUserRealm(alice))
Remove(cross(cur), id)
uassert.Equal(t, 0, count)
uassert.True(t, store.Get(id) == nil)
}
func TestOutputIsCappedAndTrapped(cur realm, t *testing.T) {
resetState()
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("alice")))
// A cell set to 1 and printed forever: an infinite writer.
id := Upload(cross(cur), "+[.]", "", 0)
status := Step(cross(cur), id, 0)
inst := store.Get(id)
uassert.Equal(t, "trapped", status)
uassert.Equal(t, "output limit reached", inst.Trap)
uassert.Equal(t, MaxOutput, len(inst.Output))
}
func TestRenderUnknownInstance(t *testing.T) {
resetState()
uassert.True(t, strings.Contains(Render("/nope"), "No such instance"))
}
// TestRenderEscapesGuestOutput pins the rule that a realm cannot be fixed in
// place once it is live: everything a caller controls is escaped before it
// reaches the page.
func TestRenderEscapesGuestOutput(cur realm, t *testing.T) {
resetState()
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("alice")))
// Print a backtick (96), which would otherwise close the code fence.
src := strings.Repeat("+", 96) + "."
id := Upload(cross(cur), src, "", 0)
Step(cross(cur), id, 0)
page := Render("/" + id)
uassert.Equal(t, "`", string(store.Get(id).Output))
uassert.True(t, strings.Contains(page, "\\x60"), "the backtick is escaped")
// The comment text in a program never reaches the page at all: only
// the eight operators do.
uassert.Equal(t, "+++[-]<>", operatorsOnly("+++ this is a comment [-] </script>"))
}
// Output sits in a code span, where markdown escapes show verbatim: only the
// pipe is escaped there, and nothing else.
func TestCodeCell(t *testing.T) {
uassert.Equal(t, "`Hello, gno.land\\n`", codeCell("Hello, gno.land\\n"))
uassert.Equal(t, "`a\\|b`", codeCell("a|b"))
}
// emit returns a program that prints s, one byte at a time, so a test can put
// any text in the output column without hand-writing Brainfuck.
func emit(s string) string {
var sb strings.Builder
for i := 0; i < len(s); i++ {
sb.WriteString("[-]" + strings.Repeat("+", int(s[i])) + ".")
}
return sb.String()
}
// instanceRow returns the first instance row of the home page.
func instanceRow(t *testing.T) string {
for _, line := range strings.Split(Render(""), "\n") {
if strings.HasPrefix(line, "| [") {
return line
}
}
t.Fatalf("no instance row on the home page")
return ""
}
// The output column is pinned on the rendered page, not only through the
// helper, so the call site cannot drift back to ui.Cell inside backticks
// (which would show `a\.b`) with the suite green.
func TestRenderOutputCell(cur realm, t *testing.T) {
cases := []struct {
name, out, cell string
}{
{"an escapable character shows as written", "a.b", "| `a.b` |"},
{"no output is an empty cell, not two backticks", "", "| 0 | |"},
{"a space at each end is padded in the markdown, past CommonMark's strip", " a ", "| ` a ` |"},
{"a guest pipe stays inside its cell", "a|b", "| `a\\|b` |"},
}
for _, c := range cases {
resetState()
testing.SetRealm(testing.NewUserRealm(testutils.TestAddress("alice")))
id := Upload(cross(cur), emit(c.out), "", 0)
if c.out != "" {
Step(cross(cur), id, 0)
uassert.Equal(t, c.out, string(store.Get(id).Output))
}
row := instanceRow(t)
uassert.True(t, strings.HasSuffix(row, c.cell), c.name+": "+row)
}
}
// codeCell follows the three rules of a code span, not only the pipe: empty
// content is not a span, a space at either end needs a pad, and the fence
// outscans any backtick run in the content.
func TestCodeCellRules(t *testing.T) {
cases := []struct{ in, want string }{
{"", ""},
{"Hello World", "`Hello World`"},
{"a|b", "`a\\|b`"},
{" hi ", "` hi `"},
{" hi", "` hi `"},
{"hi ", "` hi `"},
{"a`b", "``a`b``"},
}
for _, c := range cases {
uassert.Equal(t, c.want, codeCell(c.in), "codeCell("+c.in+")")
}
}
gnomod.toml
module = "gno.land/r/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/vm/bfdemo/v0" gno = "0.9" private = true [addpkg] creator = "g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv" height = 914348 max_deposit = "10000000ugnot"
render.gno
package bfdemo
import (
"strings"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/vm/bf/v0"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/vm/vmkit/v0"
"gno.land/p/nt/ufmt/v0"
)
// samples are the programs the home page offers, so the realm is usable
// without writing Brainfuck by hand.
var samples = []struct {
name string
src string
input string
note string
}{
{
"Hello World",
"++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.",
"",
"385 guest ops, five tape cells. Finishes in one slice.",
},
{
"Echo the input",
",[.,]",
"gno.land",
"Reads through Host.Input, which is what the naive interpreter could not do at all: it panicked on `,`.",
},
{
"Heavy loop",
"++++++++++[->++++++++++[->++++++++++[-]<]<]",
"",
"About 111k guest ops. Give it 20000 fuel and it takes six slices, which is the point.",
},
}
// Render is the realm's gnoweb view.
//
// - "/" the samples, the instance list, and how the thing works.
// - "/<id>" one instance: its program, status, fuel and output.
func Render(path string) string {
id := strings.TrimPrefix(path, "/")
id = strings.TrimSpace(id)
if id == "" {
return renderHome()
}
return renderInstance(id)
}
func renderHome() string {
var sb strings.Builder
sb.WriteString("# Brainfuck, on chain, a slice at a time\n\n")
sb.WriteString("Demo of [`p/moul/x/vm/bf`](/p/moul/x/vm/bf/v0) (the machine) and ")
sb.WriteString("[`p/moul/x/vm/vmkit`](/p/moul/x/vm/vmkit/v0) (the host ABI, the fuel meter, ")
sb.WriteString("the instance store). This realm holds no logic of its own.\n\n")
sb.WriteString("A program here does not run to completion. It runs until its fuel slice is spent, ")
sb.WriteString("then pauses: the realm keeps the snapshot and the next caller pays for the next slice. ")
sb.WriteString("Realm code cannot pause itself, and a guest can.\n\n")
sb.WriteString("## Samples\n\n")
for _, s := range samples {
sb.WriteString("**" + ui.Inline(s.name) + "**: " + s.note + "\n\n")
sb.WriteString("```\n" + s.src + "\n```\n\n")
sb.WriteString(ui.Action("Upload "+s.name, "Upload",
"src", s.src, "input", s.input, "budget", "0") + "\n\n")
}
sb.WriteString("## Instances\n\n")
t := ui.NewTable("id", "status", "fuel used", "slices", "output")
store.ReverseIterate(func(i *vmkit.Instance) bool {
t.Row(
"["+i.ID+"](/r/moul/x/vm/bfdemo/v0:"+i.ID+")",
i.Status.String(),
ufmt.Sprintf("%d", i.FuelUsed),
ufmt.Sprintf("%d", i.Slices),
codeCell(printable(i.Output, 24)),
)
return false
})
sb.WriteString(t.OrEmpty("No instances yet. Upload one of the samples above."))
sb.WriteString("\n\n")
sb.WriteString("## Limits\n\n")
lt := ui.NewTable("limit", "value")
lt.Row("instances", ufmt.Sprintf("%d", MaxInstances))
lt.Row("source bytes", ufmt.Sprintf("%d", bf.MaxSource))
lt.Row("input bytes", ufmt.Sprintf("%d", MaxInput))
lt.Row("output bytes", ufmt.Sprintf("%d", MaxOutput))
lt.Row("fuel per slice", ufmt.Sprintf("%d", MaxSliceFuel))
lt.Row("tape cells", ufmt.Sprintf("%d", bf.TapeSize))
sb.WriteString(lt.String())
return sb.String()
}
func renderInstance(id string) string {
var sb strings.Builder
sb.WriteString("# Instance " + ui.Inline(id) + "\n\n")
sb.WriteString("[← all instances](/r/moul/x/vm/bfdemo/v0)\n\n")
inst := store.Get(id)
if inst == nil {
sb.WriteString("**No such instance.** It was never uploaded, or its owner removed it.\n")
return sb.String()
}
t := ui.NewTable("field", "value")
t.Row("owner", ui.Addr(inst.Owner))
t.Row("vm", ui.Cell(inst.VM))
t.Row("status", inst.Status.String())
if inst.Trap != "" {
t.Row("trap", ui.Cell(inst.Trap))
}
t.Row("fuel used", ufmt.Sprintf("%d", inst.FuelUsed))
t.Row("fuel budget", fuelText(inst.FuelBudget))
t.Row("slices", ufmt.Sprintf("%d", inst.Slices))
t.Row("source bytes", ufmt.Sprintf("%d", len(inst.Program)))
t.Row("snapshot bytes", ufmt.Sprintf("%d", len(inst.Snapshot)))
sb.WriteString(t.String())
sb.WriteString("\n")
// The source is caller-supplied, and everything outside the eight
// operators is a comment that may hold anything at all. Show the
// program the machine actually compiled, which cannot contain a
// backtick or a newline and so cannot break out of the fence.
sb.WriteString("## Program\n\n```\n" + operatorsOnly(string(inst.Program)) + "\n```\n\n")
sb.WriteString("## Output\n\n")
if len(inst.Output) == 0 {
sb.WriteString(ui.Empty("Nothing written yet."))
} else {
sb.WriteString("```\n" + printable(inst.Output, MaxOutput) + "\n```\n")
}
sb.WriteString("\n")
if inst.Status == vmkit.Running {
sb.WriteString(ui.Action("Run 10000 more fuel", "Step", "id", id, "fuel", "10000"))
sb.WriteString(" · ")
sb.WriteString(ui.Action("Run 100000 more fuel", "Step", "id", id, "fuel", "100000"))
sb.WriteString("\n")
} else {
sb.WriteString("This instance is **" + inst.Status.String() + "** and cannot be stepped again.\n")
}
return sb.String()
}
func fuelText(n int64) string {
if n == vmkit.Unmetered {
return "unmetered"
}
return ufmt.Sprintf("%d", n)
}
// operatorsOnly strips a program down to the eight characters the language
// defines. Everything else is a comment by definition, and a comment is
// attacker-controlled text that has no business reaching a renderer.
func operatorsOnly(src string) string {
var sb strings.Builder
for i := 0; i < len(src); i++ {
switch src[i] {
case '+', '-', '<', '>', '[', ']', '.', ',':
sb.WriteByte(src[i])
}
}
if sb.Len() == 0 {
return "(no operators: this program does nothing)"
}
return sb.String()
}
// printable renders guest output for a code fence: printable ASCII as itself,
// everything else as an escape. A guest writes arbitrary bytes, so this is
// the only form of it that is safe to show.
func printable(b []byte, max int) string {
if len(b) == 0 {
return ""
}
truncated := false
if len(b) > max {
b, truncated = b[:max], true
}
const hexDigits = "0123456789abcdef"
var sb strings.Builder
for _, c := range b {
switch {
case c == '\n':
sb.WriteString("\\n")
case c == '\t':
sb.WriteString("\\t")
case c == '\\':
sb.WriteString("\\\\")
case c == '`':
sb.WriteString("\\x60")
case c >= 0x20 && c < 0x7f:
sb.WriteByte(c)
default:
sb.WriteString("\\x")
sb.WriteByte(hexDigits[c>>4])
sb.WriteByte(hexDigits[c&0x0f])
}
}
if truncated {
sb.WriteString("…")
}
return sb.String()
}
// codeCell puts already-printable text in a code span inside a table cell.
// Inside backticks markdown escapes are not applied, so ui.Cell's backslashes
// would reach the reader verbatim ("Hello, gno\.land"). md.InlineCode builds
// the span: empty text is no span at all (two bare backticks render as two
// backticks), a space at either end is padded so CommonMark's strip does not
// eat it, and the fence outscans any backtick run. The GFM row splitter runs
// before inline parsing, so the pipe is escaped on top.
func codeCell(s string) string {
return strings.ReplaceAll(md.InlineCode(s), "|", "\\|")
}