brainfuck/
interpreter.rs

1use std::io::{Read, Write};
2use std::collections::VecDeque;
3
4use super::Instruction;
5
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub struct InterpreterState<'a> {
8    /// index in the program of the instruction that was just run
9    /// Note that this instruction is computed *after* precompilation and so it may not
10    /// match the program file exactly
11    pub current_instruction: usize,
12    /// The instruction that was just run
13    pub instruction: Instruction,
14    /// The current "pointer" value that represents the current cell in memory
15    pub current_pointer: usize,
16    /// The entire memory buffer (read-only)
17    pub memory: &'a VecDeque<u8>,
18}
19
20/// callback is called after each instruction
21pub fn interpret<I, O, F>(mut inp: I, mut out: O, mut program: Vec<Instruction>, mut callback: F)
22    where I: Read, O: Write,
23          F: FnMut(InterpreterState) {
24
25    let mut buffer: VecDeque<u8> = VecDeque::new();
26    // Make sure there is at least one cell to begin with
27    buffer.push_back(0u8);
28
29    // pointer is the position "pointer" in the buffer
30    let mut pointer: usize = 0;
31    // next_instruction is the instruction index in the program
32    let mut next_instruction: usize = 0;
33
34    loop {
35        if next_instruction >= program.len() {
36            break;
37        }
38        let current_instruction = next_instruction;
39        let mut instr = program[current_instruction];
40        next_instruction += 1;
41
42        match instr {
43            Instruction::Right(amount) => {
44                pointer += amount;
45                while pointer >= buffer.len() {
46                    buffer.push_back(0u8);
47                }
48            },
49            Instruction::Left(amount) => {
50                if amount > pointer {
51                    for _ in 0..(amount - pointer) {
52                        buffer.push_front(0u8);
53                    }
54                    pointer = 0;
55                }
56                else {
57                    pointer -= amount;
58                }
59            },
60            Instruction::Increment(amount) => buffer[pointer] = buffer[pointer].wrapping_add(amount as u8),
61            Instruction::Decrement(amount) => buffer[pointer] = buffer[pointer].wrapping_sub(amount as u8),
62            Instruction::Write => out.write_all(&[buffer[pointer]]).expect("Could not output"),
63            Instruction::Read => {
64                let mut inbuffer: [u8; 1] = [0];
65                let res = inp.read_exact(&mut inbuffer[0..1]);
66                if res.is_ok() {
67                    buffer[pointer] = inbuffer[0];
68                }
69                else {
70                    buffer[pointer] = 0;
71                }
72            },
73            Instruction::JumpForwardIfZero {ref mut matching} => {
74                if buffer[pointer] == 0 {
75                    next_instruction = matching.unwrap_or_else(|| fill_matching(&mut program, next_instruction - 1));
76                }
77            },
78            Instruction::JumpBackwardUnlessZero {matching} => {
79                if buffer[pointer] != 0 {
80                    next_instruction = matching;
81                }
82            },
83        }
84
85        callback(InterpreterState {
86            current_instruction,
87            instruction: instr,
88            current_pointer: pointer,
89            memory: &buffer,
90        });
91    }
92}
93
94/// Finds the matching ']' for the given '[' located at `start`
95/// Designed to fill in any JumpForwardIfZero instructions found along the way
96/// so this function doesn't need to be called needlessly.
97///
98/// # Panics
99/// Panics if a match is not found
100fn fill_matching(mut program: &mut Vec<Instruction>, start: usize) -> usize {
101    use super::MAX_NESTED_JUMPS;
102    let mut jumps = VecDeque::with_capacity(MAX_NESTED_JUMPS);
103
104    let program_size = program.len();
105    let mut current = start;
106    loop {
107        if current >= program_size {
108            panic!("Mismatched `[` instruction");
109        }
110
111        match program[current] {
112            Instruction::JumpForwardIfZero { .. } => jumps.push_back(current),
113            Instruction::JumpBackwardUnlessZero { .. } => {
114                let last_forward = jumps.pop_back().expect("Mismatched `]` instruction");
115                match program[last_forward] {
116                    Instruction::JumpForwardIfZero {ref mut matching} => {
117                        debug_assert!(matching.is_none(),
118                            "matching was already set which means this function ran needlessly");
119                        *matching = Some(current + 1);
120                    },
121                    _ => unreachable!(),
122                }
123            },
124            _ => {},
125        };
126
127        if jumps.is_empty() {
128            break;
129        }
130
131        current += 1;
132    }
133
134    current + 1
135}
136
137#[cfg(test)]
138mod tests {
139    use super::*;
140    use super::super::Instruction::*;
141
142    use std::collections::VecDeque;
143
144    #[test]
145    fn basic_movements() {
146        // Test to make sure basic movements are working
147        assert_eq!(test_interpret_output(vec![
148            Increment(1),
149            Right(1),
150            Increment(2),
151            Right(1),
152            Increment(3),
153            Write,
154            Left(1),
155            Write,
156            Left(1),
157            Write,
158        ]), vec![3, 2, 1]);
159    }
160
161    #[test]
162    fn wrapping() {
163        assert_eq!(test_interpret_output(vec![
164            Write,
165            Decrement(1),
166            Write,
167            Increment(2),
168            Write,
169            Increment(256),
170            Write,
171            Decrement(255),
172            Write,
173            Decrement(1),
174            Write,
175            Decrement(1),
176            Write,
177            Decrement(1),
178            Write,
179            Increment(1),
180            Write,
181            Increment(1),
182            Write,
183            Increment(255 * 2),
184            Write,
185            Decrement(255 * 2),
186            Write,
187        ]), vec![0, 255, 1, 1, 2, 1, 0, 255, 0, 1, 255, 1]);
188    }
189
190    #[test]
191    fn move_left_past_zero() {
192        // These movements are designed to cause problems if the move instructions are not
193        // implemented correctly. If all goes well, the code should end up back at the same spot
194        // in the brainfuck tape.
195        assert_eq!(test_interpret_output(vec![
196            Increment(1),
197            Right(1),
198            Left(4),
199            Right(3),
200            Left(3),
201            Right(3),
202            Increment(1),
203            Write,
204        ]), vec![2]);
205    }
206
207    #[test]
208    fn move_right_past_capacity() {
209        assert_eq!(test_interpret_output(vec![
210            Increment(1),
211            Right(10),
212            // If we don't grow the buffer properly, this will fail
213            Increment(1),
214            Left(20),
215            Right(20),
216            Left(10),
217            Right(15),
218            Left(15),
219            Increment(1),
220            Write,
221        ]), vec![2]);
222    }
223
224    #[test]
225    fn skip_first_loop() {
226        // Any complient brainfuck implementation should always skip the first loop no matter what
227        // instructions are in it
228        assert_eq!(test_interpret_output(vec![
229            JumpForwardIfZero {matching: None},
230            Right(1),
231            Left(1),
232            Increment(1),
233            Decrement(2),
234            Write,
235            Read,
236            JumpBackwardUnlessZero {matching: 1},
237        ]), vec![]);
238    }
239
240    #[test]
241    fn reading_input() {
242        assert_eq!(test_interpret_with_input(vec![
243            Write,
244            Read,
245            Write,
246            Decrement(1),
247            Write,
248            Read,
249            Write,
250            Increment(1),
251            Write,
252            Right(1),
253            Read, // reads should overwrite each other
254            Read,
255            Right(1),
256            Read,
257            Right(1),
258            Read,
259            Left(2),
260            Write,
261            Right(1),
262            Write,
263            Right(1),
264            Write,
265            Left(3), // should not have changed
266            Write,
267            Read, // All reads past the end of input should result in 0
268            Write,
269            Read,
270            Read,
271            Read,
272            Read,
273            Read,
274            Read,
275            Read,
276            Write,
277        ], &[ // input
278            5,
279            0,
280            8,
281            17,
282            32,
283            49,
284        ]), vec![0, 5, 4, 0, 1, 17, 32, 49, 1, 0, 0]);
285    }
286
287    #[test]
288    fn basic_looping() {
289        // This loop increments cell index 1 using cell index 0 as a loop counter
290        // The result is x * y
291        let x = 13;
292        let y = 15;
293        assert_eq!(test_interpret_output(vec![
294            Increment(x),
295            JumpForwardIfZero {matching: None},
296            Right(1),
297            Increment(y),
298            Left(1),
299            Decrement(1),
300            JumpBackwardUnlessZero {matching: 2},
301            Right(1),
302            Write,
303        ]), vec![(x * y) as u8]);
304    }
305
306    #[test]
307    fn nested_loops() {
308        // The result of this is x * y * z
309        // Note that 13 * 15 * 2 = 390 which overflows since 390 > 255
310        let x = 13;
311        let y = 15;
312        let z = 2;
313        assert_eq!(test_interpret_output(vec![
314            Increment(x),
315            JumpForwardIfZero {matching: None},
316            Right(1),
317            Increment(y),
318            JumpForwardIfZero {matching: None},
319            Right(1),
320            Increment(z),
321            Left(1),
322            Decrement(1),
323            JumpBackwardUnlessZero {matching: 5},
324            Left(1),
325            Decrement(1),
326            JumpBackwardUnlessZero {matching: 2},
327            Right(2),
328            Write,
329        ]), vec![(x * y * z) as u8]);
330    }
331
332    #[test]
333    fn hello_world() {
334        use super::super::{precompile, OptimizationLevel};
335
336        // hello world program from examples/hello-world.bf
337        let source: Vec<u8> = include_bytes!("../examples/hello-world.bf").to_vec();
338        let program = precompile(source.iter(), OptimizationLevel::Off);
339        assert_eq!(test_interpret_output(program),
340            b"Hello World!\n");
341
342        let program = precompile(source.iter(), OptimizationLevel::Speed);
343        assert_eq!(test_interpret_output(program),
344            b"Hello World!\n");
345    }
346
347    #[test]
348    #[should_panic(expected = "Mismatched `[` instruction")]
349    fn mismatched_jumps() {
350        test_interpret_output(vec![
351            JumpForwardIfZero {matching: None},
352        ]);
353    }
354
355    #[test]
356    fn callback_behaviour() {
357        let mut inp: &[u8] = &[];
358        let mut out = Vec::new();
359        let program = vec![
360            Right(4),
361            Left(5),
362            Increment(2),
363            JumpForwardIfZero {matching: None},
364            Decrement(1),
365            JumpBackwardUnlessZero {matching: 4},
366        ];
367        let states = vec![
368            (0, Right(4), 4, vec![0, 0, 0, 0, 0].into()),
369            (1, Left(5), 0, vec![0, 0, 0, 0, 0, 0].into()),
370            (2, Increment(2), 0, vec![2, 0, 0, 0, 0, 0].into()),
371            (3, JumpForwardIfZero {matching: None}, 0, vec![2, 0, 0, 0, 0, 0].into()),
372            (4, Decrement(1), 0, vec![1, 0, 0, 0, 0, 0].into()),
373            (5, JumpBackwardUnlessZero {matching: 4}, 0, vec![1, 0, 0, 0, 0, 0].into()),
374            (4, Decrement(1), 0, vec![0, 0, 0, 0, 0, 0].into()),
375            (5, JumpBackwardUnlessZero {matching: 4}, 0, vec![0, 0, 0, 0, 0, 0].into()),
376        ];
377        let mut states: VecDeque<_> = states.iter().map(|&(current_instruction, instruction, current_pointer, ref memory)| {
378            InterpreterState {current_instruction, instruction, current_pointer, memory}
379        }).collect();
380
381        interpret(&mut inp, &mut out, program, |state| {
382            let expected = states.pop_front().expect("callback was called unexpectedly");
383            assert_eq!(expected, state, "Failed with {} states left", states.len());
384        });
385
386        assert!(states.is_empty());
387        assert_eq!(out, vec![]);
388    }
389
390    fn test_interpret_output(program: Vec<Instruction>) -> Vec<u8> {
391        let inp: &[u8] = &[];
392        test_interpret_with_input(program, inp)
393    }
394
395    fn test_interpret_with_input(program: Vec<Instruction>, mut inp: &[u8]) -> Vec<u8> {
396        let mut out = Vec::new();
397        interpret(&mut inp, &mut out, program, |_| {});
398        out
399    }
400}
brainfuck/interpreter.rs

brainfuck/
interpreter.rs
