bf_test.gno
6.25 Kb · 186 lines
1package bf
2
3import (
4 "testing"
5
6 "gno.land/p/moul/x/vm/vmkit/v0"
7 "gno.land/p/nt/uassert/v0"
8)
9
10// hello is the classic 106 byte hello-world. It writes "Hello World", 11
11// bytes: the original run.gno comment was optimistic about the trailing "!\n".
12const hello = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------."
13
14// corpus is the set of programs every ladder level must agree on. Each one is
15// here because it exercises a rewrite that could plausibly be wrong.
16var corpus = []struct {
17 name string
18 src string
19 want string
20}{
21 {"empty", "", ""},
22 {"comment only", "this is not brainfuck", ""},
23 {"hello", hello, "Hello World"},
24 {"clear idiom", "+++++[-]+++++++++++++++++++++++++++++++++++++++++++++++.", "/"},
25 {"move idiom", "+++++++++++++++++++++++++++++++++++++++++++++++++++[->+<]>.", "3"},
26 {"multiply idiom", "+++++[->++++++++++<]>++.", "4"},
27 {"two targets", "+++[->+>++<<]>+++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++.", "*/"},
28 {"scan walks", ">+>+>+>+[<]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.", "H"},
29 {"scan right", ">>>+++++++++<<<[>]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.", "?"},
30 {"nested loops", "++[>++[>+<-]<-]>>+++++++++++++++++++++++++++++++++++++++++++++++++.", "5"},
31 {"dead run", "+++--+++--+++++++++++++++++++++++++++++++++++++++++++.", "-"},
32 {"skipped loop", "[++++++++++++++++++++]+++++++++++++++++++++++++++++++++++++++++++++++.", "/"},
33 {"wraps under zero", "-[>+<-]>++++++++++.", "\t"},
34}
35
36func runLevel(t *testing.T, src string, lvl Level, input string) string {
37 t.Helper()
38 prog, err := Compile(src, lvl)
39 uassert.NoError(t, err)
40 if prog == nil {
41 return ""
42 }
43 h := vmkit.NewTestHost().WithInput([]byte(input))
44 m := NewMachine(prog)
45 _, status := m.Step(h, vmkit.Unmetered)
46 uassert.Equal(t, "halted", status.String())
47 return h.OutString()
48}
49
50// TestLadderLevelsAgree is the test the whole ladder rests on: an
51// optimization that changes the output is not an optimization.
52func TestLadderLevelsAgree(t *testing.T) {
53 for _, tc := range corpus {
54 naive := Execute(tc.src)
55 uassert.Equal(t, tc.want, naive)
56
57 for _, lvl := range []Level{LevelJumps, LevelFuse, LevelIdioms} {
58 got := runLevel(t, tc.src, lvl, "")
59 if got != tc.want {
60 t.Errorf("%s at level %s: got %q, want %q",
61 tc.name, lvl.String(), got, tc.want)
62 }
63 }
64 }
65}
66
67func TestExecuteBaseline(t *testing.T) {
68 // Rung 0 is kept verbatim, so this is also a regression test on the
69 // thing the published cycles-per-op number was measured against.
70 uassert.Equal(t, "Hello World", Execute(hello))
71 uassert.Equal(t, 11, len(Execute(hello)))
72}
73
74func TestCompileRejectsUnbalanced(t *testing.T) {
75 cases := []string{"[", "]", "[[]", "+[->+<", "][", "[[[]]"}
76 for _, src := range cases {
77 _, err := CompileDefault(src)
78 if err == nil {
79 t.Errorf("Compile(%q) should have failed", src)
80 }
81 }
82}
83
84func TestCompileRejectsOversizeSource(t *testing.T) {
85 src := "+"
86 for len(src) <= MaxSource {
87 src += src // doubling, not O(n^2) appending
88 }
89 _, err := CompileDefault(src)
90 uassert.ErrorIs(t, err, ErrSourceTooLong)
91}
92
93func TestCompileRejectsUnknownLevel(t *testing.T) {
94 _, err := Compile("+", Level(42))
95 uassert.Error(t, err)
96 _, err = Compile("+", Level(-1))
97 uassert.Error(t, err)
98}
99
100// TestLadderShrinksTheOpStream is the compile-time half of the ladder: each
101// rung has to produce strictly fewer ops than the one below it, or it is not
102// buying anything.
103func TestLadderShrinksTheOpStream(t *testing.T) {
104 jumps, err := Compile(hello, LevelJumps)
105 uassert.NoError(t, err)
106 fuse, err := Compile(hello, LevelFuse)
107 uassert.NoError(t, err)
108 idioms, err := Compile(hello, LevelIdioms)
109 uassert.NoError(t, err)
110
111 uassert.True(t, jumps.Len() > fuse.Len())
112 uassert.True(t, fuse.Len() > idioms.Len())
113 uassert.Equal(t, "jumps", jumps.Level().String())
114 uassert.Equal(t, hello, idioms.Source())
115}
116
117func TestIdiomRecognition(t *testing.T) {
118 cases := []struct {
119 name string
120 src string
121 want int // ops, excluding the trailing halt
122 }{
123 {"clear", "[-]", 1}, // opSet
124 {"move", "[->+<]", 2}, // opAddMul, opSet
125 {"multiply two", "[->++>+++<<]", 3}, // two opAddMul, opSet
126 {"scan right", "[>]", 1}, // opScan
127 {"scan left", "[<]", 1}, // opScan
128 }
129 for _, tc := range cases {
130 prog, err := Compile(tc.src, LevelIdioms)
131 uassert.NoError(t, err)
132 if prog == nil {
133 continue
134 }
135 if got := prog.Len() - 1; got != tc.want {
136 t.Errorf("%s: %q compiled to %d ops, want %d",
137 tc.name, tc.src, got, tc.want)
138 }
139 }
140}
141
142// TestPlusLoopIsNotRewritten pins the conservative half of the rewrite: a
143// loop that adds one per iteration still reaches zero by wrapping, but only
144// after 256 iterations, and folding it would be a different program. It has
145// to stay a real loop.
146func TestPlusLoopIsNotRewritten(t *testing.T) {
147 prog, err := Compile("[+]", LevelIdioms)
148 uassert.NoError(t, err)
149 // opJmpZ, opAdd, opJmpNZ, opHalt: untouched.
150 uassert.Equal(t, 4, prog.Len())
151}
152
153func TestInputThroughTheHost(t *testing.T) {
154 // Read three bytes and echo them back.
155 const echo3 = ",.,.,."
156 h := vmkit.NewTestHost().WithInput([]byte("gno"))
157 m, err := Load(echo3)
158 uassert.NoError(t, err)
159 _, status := m.Step(h, vmkit.Unmetered)
160 uassert.Equal(t, "halted", status.String())
161 uassert.Equal(t, "gno", h.OutString())
162}
163
164func TestInputEndsAsZero(t *testing.T) {
165 // Past the end of input, `,` yields a zero cell. Without input at all,
166 // the naive interpreter would have panicked here.
167 h := vmkit.NewTestHost().WithInput([]byte("a"))
168 m, err := Load(",.+++++++++++++++++++++++++++++++++++++++++++++++.,+++++++++++++++++++++++++++++++++++++++++++++++++.")
169 uassert.NoError(t, err)
170 _, status := m.Step(h, vmkit.Unmetered)
171 uassert.Equal(t, "halted", status.String())
172 uassert.Equal(t, "a\x901", h.OutString())
173}
174
175func TestExecutePanicsOnInput(cur realm, t *testing.T) {
176 // Rung 0's second preserved bug, pinned so nobody "fixes" the baseline.
177 uassert.PanicsWithMessage(t, cur, "unsupported", func() { Execute(",") })
178}
179
180func TestMachineWithoutProgram(t *testing.T) {
181 m := &Machine{status: vmkit.Running}
182 used, status := m.Step(vmkit.NewTestHost(), 10)
183 uassert.Equal(t, int64(0), used)
184 uassert.Equal(t, "trapped", status.String())
185 uassert.Equal(t, "no program", m.Trap())
186}
