bf.gno

  1// Package bf is a Brainfuck machine for gno.land, and the measuring stick the
  2// rest of the guest-VM work is calibrated against.
  3//
  4// It ships two things that look alike and are not:
  5//
  6//   - [Execute], the naive interpreter: a switch over the source bytes, a
  7//     brace matcher that rescans the program on every loop edge. It is kept
  8//     verbatim as rung 0 of the optimization ladder, because a baseline you
  9//     have edited is not a baseline.
 10//   - [Compile] plus [Machine], the real one: the program is compiled to an
 11//     op array with resolved jumps, runs of identical operators are fused,
 12//     the common loop idioms become single ops, and execution is metered by
 13//     a caller-supplied fuel budget against a
 14//     [vmkit](/p/moul/x/vm/vmkit/v0) Host, so a program can pause when it
 15//     runs out and resume in a later transaction.
 16//
 17// The ladder between them is measured, not asserted: see the README for the
 18// table, and ladder_test.gno for the harness that produces it.
 19//
 20// Live demo: [r/moul/x/vm/bfdemo](/r/moul/x/vm/bfdemo/v0).
 21package bf
 22
 23import "strings"
 24
 25// NaiveTapeSize is the tape length used by [Execute]. It is 30,000 because
 26// that is what the original had, and rung 0 is not allowed to drift.
 27const NaiveTapeSize = 30000
 28
 29// Execute runs code on a fresh tape and returns everything it wrote, using
 30// the original 2023 implementation: no compilation step, one switch per
 31// source byte, and a brace matcher that rescans the source every time a loop
 32// opens or closes.
 33//
 34// It is rung 0 of the ladder and exists to be measured. Two of its properties
 35// are bugs that are deliberately preserved, and are the reason nothing should
 36// call it on untrusted input:
 37//
 38//   - `,` panics with "unsupported": there is no input.
 39//   - unbalanced brackets run the scan off the end of the source and panic
 40//     with an index out of range.
 41//
 42// Use [Compile] and [Machine] for anything real: they reject a malformed
 43// program up front, read input from the host, and cannot run unbounded.
 44func Execute(code string) string {
 45	var (
 46		memory  = make([]byte, NaiveTapeSize) // memory tape
 47		pointer = 0                           // initial memory pointer
 48		buf     strings.Builder
 49	)
 50
 51	// Loop through each character in the code
 52	for i := 0; i < len(code); i++ {
 53		switch code[i] {
 54		case '>':
 55			// Increment memory pointer
 56			pointer++
 57			if pointer >= NaiveTapeSize {
 58				pointer = 0
 59			}
 60		case '<':
 61			// Decrement memory pointer
 62			pointer--
 63			if pointer < 0 {
 64				pointer = NaiveTapeSize - 1
 65			}
 66		case '+':
 67			// Increment the byte at the memory pointer
 68			memory[pointer]++
 69		case '-':
 70			// Decrement the byte at the memory pointer
 71			memory[pointer]--
 72		case '.':
 73			// Output the byte at the memory pointer
 74			buf.WriteByte(memory[pointer])
 75		case ',':
 76			// Input a byte and store it in the memory
 77			panic("unsupported")
 78		case '[':
 79			// Jump forward past the matching ']' if the byte at the memory pointer is zero
 80			if memory[pointer] == 0 {
 81				braceCount := 1
 82				for braceCount > 0 {
 83					i++
 84					if code[i] == '[' {
 85						braceCount++
 86					} else if code[i] == ']' {
 87						braceCount--
 88					}
 89				}
 90			}
 91		case ']':
 92			// Jump backward to the matching '[' if the byte at the memory pointer is nonzero
 93			if memory[pointer] != 0 {
 94				braceCount := 1
 95				for braceCount > 0 {
 96					i--
 97					if code[i] == ']' {
 98						braceCount++
 99					} else if code[i] == '[' {
100						braceCount--
101					}
102				}
103				i-- // Move back one more to compensate for the upcoming increment in the loop
104			}
105		}
106	}
107	return buf.String()
108}