compile.gno
9.18 Kb · 327 lines
1package bf
2
3import (
4 "errors"
5
6 "gno.land/p/nt/ufmt/v0"
7)
8
9// TapeSize is the tape length of a compiled [Machine]. It matches
10// [NaiveTapeSize] so that the ladder compares like with like: a rung that
11// changed the semantics would not be a rung, it would be a different program.
12const TapeSize = 30000
13
14// MaxSource bounds the program a realm will accept. Compilation is linear in
15// the source, but the op array and every snapshot of it are consensus state,
16// so the size has to be bounded somewhere the caller can see.
17const MaxSource = 64 * 1024
18
19// ErrSourceTooLong is returned by [Compile] for a program above [MaxSource].
20var ErrSourceTooLong = errors.New("bf: source too long")
21
22// Level selects how far up the optimization ladder [Compile] goes.
23//
24// Every level produces the same output for the same program: the levels exist
25// so the cost of each optimization can be measured in isolation, which is the
26// published result this package is really for. Rung 0 of the ladder is
27// [Execute] and has no compiler at all.
28type Level int
29
30const (
31 // LevelJumps is rung 1: one op per source byte, with the jump targets
32 // resolved at compile time. This is the rung that kills the brace
33 // rescan, which in [Execute] costs O(loop body) on every iteration.
34 LevelJumps Level = iota
35
36 // LevelFuse is rung 2: runs of identical operators collapse, so
37 // "+++++" is one add-5 and ">>>" is one move-3. Real programs are
38 // mostly runs.
39 LevelFuse
40
41 // LevelIdioms is rung 3: a loop whose body only moves and adds, and
42 // which returns to where it started while decrementing the current
43 // cell by one, is replaced by the multiply-adds it performs plus a
44 // clear. "[-]" becomes one op, "[->+<]" becomes two.
45 LevelIdioms
46)
47
48// Default is the level [CompileDefault] uses, and the one a realm should
49// want: every optimization this package knows, same semantics.
50const Default = LevelIdioms
51
52// String names the level, for the ladder table and for realm output.
53func (l Level) String() string {
54 switch l {
55 case LevelJumps:
56 return "jumps"
57 case LevelFuse:
58 return "fuse"
59 case LevelIdioms:
60 return "idioms"
61 }
62 return "unknown"
63}
64
65type opcode byte
66
67const (
68 opAdd opcode = iota // tape[p] += arg (arg normalized to 0..255)
69 opMove // p += arg
70 opOut // write tape[p] to the host
71 opIn // read one input byte into tape[p]
72 opJmpZ // if tape[p] == 0 { pc = arg }
73 opJmpNZ // if tape[p] != 0 { pc = arg }
74 opSet // tape[p] = byte(arg)
75 opAddMul // tape[p+off] += tape[p] * byte(arg)
76 opScan // while tape[p] != 0 { p += arg }
77 opHalt // end of program
78)
79
80// op is one compiled instruction. It is a flat struct on purpose: the
81// execution loop indexes an array of these, and an op that owned a slice
82// would allocate in the hot path.
83type op struct {
84 code opcode
85 arg int
86 off int
87}
88
89// Program is compiled Brainfuck, ready to run on a [Machine].
90type Program struct {
91 ops []op
92 src string
93 level Level
94}
95
96// Source returns the program text the [Program] was compiled from.
97func (p *Program) Source() string { return p.src }
98
99// Level returns the ladder rung this program was compiled at.
100func (p *Program) Level() Level { return p.level }
101
102// Len returns the number of compiled ops, including the trailing halt. It is
103// the number worth quoting next to the source length: the ratio is exactly
104// what the ladder buys.
105func (p *Program) Len() int { return len(p.ops) }
106
107// CompileDefault compiles at [Default].
108func CompileDefault(src string) (*Program, error) { return Compile(src, Default) }
109
110// Compile turns Brainfuck source into a [Program] at the requested ladder
111// level. Everything that is not one of the eight operators is a comment, as
112// the language requires.
113//
114// It fails on unbalanced brackets rather than trusting the runtime to notice,
115// which is the first thing that separates it from [Execute]: a malformed
116// program is rejected before anybody pays to run it.
117func Compile(src string, lvl Level) (*Program, error) {
118 if len(src) > MaxSource {
119 return nil, ErrSourceTooLong
120 }
121 if lvl < LevelJumps || lvl > LevelIdioms {
122 return nil, ufmt.Errorf("bf: unknown level %d", int(lvl))
123 }
124
125 ops := []op{}
126 opens := []int{} // pc of each unclosed opJmpZ
127
128 for i := 0; i < len(src); i++ {
129 c := src[i]
130 switch c {
131 case '+', '-':
132 delta := 1
133 if c == '-' {
134 delta = -1
135 }
136 if lvl >= LevelFuse {
137 n := 1
138 for i+n < len(src) && (src[i+n] == '+' || src[i+n] == '-') {
139 if src[i+n] == '+' {
140 delta++
141 } else {
142 delta--
143 }
144 n++
145 }
146 i += n - 1
147 }
148 if a := normAdd(delta); a != 0 {
149 ops = append(ops, op{code: opAdd, arg: a})
150 }
151 case '>', '<':
152 delta := 1
153 if c == '<' {
154 delta = -1
155 }
156 if lvl >= LevelFuse {
157 n := 1
158 for i+n < len(src) && (src[i+n] == '>' || src[i+n] == '<') {
159 if src[i+n] == '>' {
160 delta++
161 } else {
162 delta--
163 }
164 n++
165 }
166 i += n - 1
167 }
168 if d := normMove(delta); d != 0 {
169 ops = append(ops, op{code: opMove, arg: d})
170 }
171 case '.':
172 ops = append(ops, op{code: opOut})
173 case ',':
174 ops = append(ops, op{code: opIn})
175 case '[':
176 opens = append(opens, len(ops))
177 ops = append(ops, op{code: opJmpZ})
178 case ']':
179 if len(opens) == 0 {
180 return nil, ufmt.Errorf("bf: unmatched ']' at byte %d", i)
181 }
182 open := opens[len(opens)-1]
183 opens = opens[:len(opens)-1]
184
185 if lvl >= LevelIdioms {
186 if idiom, ok := simpleLoop(ops[open+1:]); ok {
187 ops = append(ops[:open], idiom...)
188 continue
189 }
190 }
191 // pc lands on the op after the jump, so a jump target is
192 // the index of the partner op itself.
193 ops = append(ops, op{code: opJmpNZ, arg: open})
194 ops[open].arg = len(ops) - 1
195 }
196 }
197 if len(opens) != 0 {
198 return nil, ufmt.Errorf("bf: %d unmatched '['", len(opens))
199 }
200
201 ops = append(ops, op{code: opHalt})
202 return &Program{ops: ops, src: src, level: lvl}, nil
203}
204
205// normAdd folds a signed delta into the 0..255 the byte tape actually sees,
206// so the execution loop never has to convert a negative int to a byte.
207func normAdd(d int) int {
208 d %= 256
209 if d < 0 {
210 d += 256
211 }
212 return d
213}
214
215// normMove folds a pointer delta into one lap of the tape. Moving right
216// TapeSize times is a no-op on a wrapping tape, in the naive interpreter as
217// much as here, so collapsing it changes nothing but the op count.
218func normMove(d int) int {
219 d %= TapeSize
220 if d < 0 {
221 d += TapeSize
222 }
223 if d > TapeSize/2 {
224 d -= TapeSize
225 }
226 return d
227}
228
229// cell is one offset the body of a simple loop writes to.
230type cell struct {
231 off int
232 delta int
233}
234
235// simpleLoop decides whether a loop body can be replaced by straight-line
236// code, and returns that code.
237//
238// Two shapes qualify, and they are the two that dominate real programs:
239//
240// - The body only moves, and ends somewhere other than where it started:
241// that is a scan, "[>]" walking to the next zero cell.
242// - The body only moves and adds, ends where it started, and takes exactly
243// one off the current cell: that is a multiply-add. The loop runs
244// tape[p] times, so every other cell it touches gains its delta times
245// tape[p], and the current cell ends at zero. "[-]" is the degenerate
246// case with no other cells.
247//
248// Anything else, including any body containing I/O or a nested loop that was
249// itself rewritten, is left alone. Being conservative here costs a few ops in
250// rare programs and is the only reason this rewrite is safe at all: a loop
251// whose current cell does not reach zero in steps of one is not guaranteed to
252// terminate, and constant-folding it would change the program.
253func simpleLoop(body []op) ([]op, bool) {
254 cursor := 0
255 cells := []cell{}
256 adds := 0
257
258 for _, o := range body {
259 switch o.code {
260 case opMove:
261 cursor += o.arg
262 case opAdd:
263 adds++
264 // Carry the delta as a signed value; it is normalized
265 // back into 0..255 when it is emitted.
266 d := o.arg
267 if d > 128 {
268 d -= 256
269 }
270 cells = addCell(cells, cursor, d)
271 default:
272 return nil, false
273 }
274 }
275
276 if cursor != 0 {
277 // Net movement: only a pure scan qualifies, and only when the
278 // step is not zero (which normMove already guarantees here).
279 if adds != 0 {
280 return nil, false
281 }
282 return []op{{code: opScan, arg: cursor}}, true
283 }
284
285 // Balanced. The current cell must fall by exactly one per iteration,
286 // or the loop is not a counted multiply-add.
287 if delta(cells, 0) != -1 {
288 return nil, false
289 }
290
291 out := []op{}
292 for _, c := range cells {
293 if c.off == 0 || c.delta == 0 {
294 continue
295 }
296 out = append(out, op{code: opAddMul, arg: normAdd(c.delta), off: c.off})
297 }
298 out = append(out, op{code: opSet, arg: 0})
299 return out, true
300}
301
302// addCell accumulates a delta at an offset, keeping cells sorted by offset so
303// that the op stream a program compiles to is identical on every node.
304func addCell(cells []cell, off, d int) []cell {
305 for i := range cells {
306 if cells[i].off == off {
307 cells[i].delta += d
308 return cells
309 }
310 if cells[i].off > off {
311 cells = append(cells, cell{})
312 copy(cells[i+1:], cells[i:])
313 cells[i] = cell{off: off, delta: d}
314 return cells
315 }
316 }
317 return append(cells, cell{off: off, delta: d})
318}
319
320func delta(cells []cell, off int) int {
321 for _, c := range cells {
322 if c.off == off {
323 return c.delta
324 }
325 }
326 return 0
327}
