vtashkov_bf/
interpreter.rs

1//! Brainfuck interpreter
2//!
3//! # Examples
4//!
5//! This will output "Hello World!\n" in the output vector:
6//!
7//! ```
8//! use std::io::Cursor;
9//! use std::str;
10
11//! use vtashkov_bf::Interpreter;
12
13//! let source_code = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.";
14//! let mut input = Cursor::new(vec![]);
15//! let mut output = vec![];
16//! let mut interpreter = Interpreter::new(&mut input, &mut output, 30000);
17//! interpreter.execute(&source_code);
18//! assert_eq!("Hello World!\n", str::from_utf8(output.as_slice()).unwrap());
19//! ```
20//!
21
22use std::io::{Read, Write};
23
24use crate::memory::Memory;
25
26/// Brainfuck interpreter
27pub struct Interpreter<'a, R, W>
28where
29    R: Read,
30    W: Write,
31{
32    memory: Memory<u8>,
33    input: &'a mut R,
34    output: &'a mut W,
35}
36
37impl<'a, R, W> Interpreter<'a, R, W>
38where
39    R: Read,
40    W: Write,
41{
42    /// Creates new interpreter with the given input stream, output stream and number of cells
43    pub fn new(input: &'a mut R, output: &'a mut W, memory_size: usize) -> Interpreter<'a, R, W> {
44        Interpreter {
45            memory: Memory::new(memory_size),
46            input,
47            output,
48        }
49    }
50
51    /// Executes a program
52    pub fn execute(&mut self, source_code: &str) {
53        self.memory.clear();
54        let instructions = parse(&mut source_code.chars());
55        self.execute_instructions(&instructions);
56    }
57
58    fn execute_instructions(&mut self, instructions: &Vec<Instruction>) {
59        for instruction in instructions {
60            match instruction {
61                Instruction::NextCell => self.memory.next(),
62                Instruction::PreviousCell => self.memory.previous(),
63                Instruction::IncrementData => self.memory.increment(),
64                Instruction::DecrementData => self.memory.decrement(),
65                Instruction::OutputData => {
66                    let value = self.memory.read();
67                    self.output.write(&[*value]).unwrap();
68                }
69                Instruction::InputData => {
70                    let mut value = [0_u8];
71                    if self.input.read_exact(&mut value).is_ok() {
72                        self.memory.write(value[0]);
73                    }
74                }
75                Instruction::Loop(loop_instructions) => {
76                    while *self.memory.read() != 0 {
77                        self.execute_instructions(loop_instructions)
78                    }
79                }
80            }
81        }
82    }
83}
84
85#[derive(PartialEq, Debug)]
86enum Instruction {
87    NextCell,
88    PreviousCell,
89    IncrementData,
90    DecrementData,
91    OutputData,
92    InputData,
93    Loop(Vec<Instruction>),
94}
95
96fn parse(chars: &mut impl Iterator<Item = char>) -> Vec<Instruction> {
97    let mut instructions: Vec<Instruction> = Vec::new();
98
99    while let Some(char) = chars.next() {
100        instructions.push(match char {
101            '>' => Instruction::NextCell,
102            '<' => Instruction::PreviousCell,
103            '+' => Instruction::IncrementData,
104            '-' => Instruction::DecrementData,
105            '.' => Instruction::OutputData,
106            ',' => Instruction::InputData,
107            '[' => Instruction::Loop(parse(chars)),
108            ']' => break,
109            _ => continue,
110        });
111    }
112
113    instructions
114}
115
116#[cfg(test)]
117mod tests {
118    use std::io::Cursor;
119
120    use super::*;
121
122    #[test]
123    fn interpreter_can_be_created() {
124        let mut input = Cursor::new(vec![]);
125        let mut output = vec![];
126        let _interpreter = Interpreter::new(&mut input, &mut output, 1);
127    }
128
129    #[test]
130    fn interpreter_can_execute_code() {
131        let mut input = Cursor::new(vec![]);
132        let mut output = vec![];
133        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
134        interpreter.execute("");
135    }
136
137    #[test]
138    fn interpreter_ignores_non_instructions() {
139        let mut input = Cursor::new(vec![]);
140        let mut output = vec![];
141        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
142        interpreter.execute(" !\"#$%&'()*/0123456789:;=?@ABCDEFGHIJKLMNOPQRSTUVWXYZ\\^_`abcdefghijklmnopqrstuvwxyz{|}~");
143        let expected: Vec<u8> = vec![];
144        assert_eq!(expected, output)
145    }
146
147    #[test]
148    fn interpreter_outputs_default_cell_value_of_zero() {
149        let mut input = Cursor::new(vec![]);
150        let mut output = vec![];
151        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
152        interpreter.execute(".");
153        assert_eq!(vec![0], output)
154    }
155
156    #[test]
157    fn interpreter_inputs_and_outputs_value() {
158        let mut input = Cursor::new(vec![1]);
159        let mut output = vec![];
160        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
161        interpreter.execute(",.");
162        assert_eq!(vec![1], output)
163    }
164
165    #[test]
166    fn interpreter_inputs_and_outputs_multiple_value() {
167        let mut input = Cursor::new(vec![1, 2]);
168        let mut output = vec![];
169        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
170        interpreter.execute(".,.,.");
171        assert_eq!(vec![0, 1, 2], output)
172    }
173
174    #[test]
175    fn interpreter_does_not_change_anything_if_no_input_value() {
176        let mut input = Cursor::new(vec![]);
177        let mut output = vec![];
178        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
179        interpreter.execute(",.");
180        assert_eq!(vec![0], output)
181    }
182
183    #[test]
184    fn interpreter_increments_cell() {
185        let mut input = Cursor::new(vec![]);
186        let mut output = vec![];
187        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
188        interpreter.execute("+.");
189        assert_eq!(vec![1], output)
190    }
191
192    #[test]
193    fn interpreter_decrements_cell() {
194        let mut input = Cursor::new(vec![2]);
195        let mut output = vec![];
196        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
197        interpreter.execute(",.-.");
198        assert_eq!(vec![2, 1], output)
199    }
200
201    #[test]
202    fn interpreter_increments_and_decrements_cell_multiple_times() {
203        let mut input = Cursor::new(vec![]);
204        let mut output = vec![];
205        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
206        interpreter.execute(".+.+.+.-.-.-.");
207        assert_eq!(vec![0, 1, 2, 3, 2, 1, 0], output)
208    }
209
210    #[test]
211    fn interpreter_moves_to_next_cell() {
212        let mut input = Cursor::new(vec![]);
213        let mut output = vec![];
214        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
215        interpreter.execute(".+.>.");
216        assert_eq!(vec![0, 1, 0], output)
217    }
218
219    #[test]
220    fn interpreter_moves_back_and_forth() {
221        let mut input = Cursor::new(vec![]);
222        let mut output = vec![];
223        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
224        interpreter.execute(".+.>.+.+.<.-.>.");
225        assert_eq!(vec![0, 1, 0, 1, 2, 1, 0, 2], output)
226    }
227
228    #[test]
229    fn interpreter_goes_back_to_first_cell_after_reaching_the_end() {
230        let mut input = Cursor::new(vec![1, 2, 3]);
231        let mut output = vec![];
232        let mut interpreter = Interpreter::new(&mut input, &mut output, 3);
233        interpreter.execute(",>,>,>.>.>.");
234        assert_eq!(vec![1, 2, 3], output)
235    }
236
237    #[test]
238    fn interpreter_goes_back_to_the_end_if_going_back_from_the_first_cell() {
239        let mut input = Cursor::new(vec![1, 2, 3]);
240        let mut output = vec![];
241        let mut interpreter = Interpreter::new(&mut input, &mut output, 3);
242        interpreter.execute(",>,>,><.<.<.");
243        assert_eq!(vec![3, 2, 1], output)
244    }
245
246    #[test]
247    fn interpreter_skips_loop_if_current_cell_is_zero() {
248        let mut input = Cursor::new(vec![]);
249        let mut output = vec![];
250        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
251        interpreter.execute(".[.].");
252        assert_eq!(vec![0, 0], output)
253    }
254
255    #[test]
256    fn interpreter_executes_loop_once_if_current_cell_is_non_zero() {
257        let mut input = Cursor::new(vec![]);
258        let mut output = vec![];
259        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
260        interpreter.execute(".+[.-].");
261        assert_eq!(vec![0, 1, 0], output)
262    }
263
264    #[test]
265    fn interpreter_executes_loop_twice_if_current_cell_is_two() {
266        let mut input = Cursor::new(vec![]);
267        let mut output = vec![];
268        let mut interpreter = Interpreter::new(&mut input, &mut output, 1);
269        interpreter.execute(".++[.-].");
270        assert_eq!(vec![0, 2, 1, 0], output)
271    }
272
273    #[test]
274    fn interpreter_executes_embedded_loops() {
275        let mut input = Cursor::new(vec![]);
276        let mut output = vec![];
277        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
278        interpreter.execute("+[>++[.-].<.-].");
279        assert_eq!(vec![2, 1, 0, 1, 0], output)
280    }
281
282    #[test]
283    fn interpreter_executes_two_embedded_loops() {
284        let mut input = Cursor::new(vec![]);
285        let mut output = vec![];
286        let mut interpreter = Interpreter::new(&mut input, &mut output, 3);
287        interpreter.execute("+[>+[.-]+[.-].<.-].");
288        assert_eq!(vec![1, 1, 0, 1, 0], output)
289    }
290
291    #[test]
292    fn interpreter_executes_double_embedded_loops() {
293        let mut input = Cursor::new(vec![]);
294        let mut output = vec![];
295        let mut interpreter = Interpreter::new(&mut input, &mut output, 3);
296        interpreter.execute("+[->++[->+[.-]<]]");
297        assert_eq!(vec![1, 1], output)
298    }
299
300    #[test]
301    fn interpreter_executes_no_end_loop() {
302        let mut input = Cursor::new(vec![]);
303        let mut output = vec![];
304        let mut interpreter = Interpreter::new(&mut input, &mut output, 3);
305        interpreter.execute(".+.[-.");
306        assert_eq!(vec![0, 1, 0], output)
307    }
308
309    #[test]
310    fn interpreter_executes_embedded_no_end_loop() {
311        let mut input = Cursor::new(vec![]);
312        let mut output = vec![];
313        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
314        interpreter.execute("+[>++[.-].<.-");
315        assert_eq!(vec![2, 1, 0, 1], output)
316    }
317
318    #[test]
319    fn interpreter_executes_no_embedded_end_loop() {
320        let mut input = Cursor::new(vec![]);
321        let mut output = vec![];
322        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
323        interpreter.execute("+[>++[.-.<.-].");
324        assert_eq!(vec![2, 1, 1, 0], output)
325    }
326
327    #[test]
328    fn interpreter_executes_embedded_no_end_loops() {
329        let mut input = Cursor::new(vec![]);
330        let mut output = vec![];
331        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
332        interpreter.execute("+[>++[.-.<.-");
333        assert_eq!(vec![2, 1, 1], output)
334    }
335
336    #[test]
337    fn interpreter_executes_two_embedded_no_end_loop() {
338        let mut input = Cursor::new(vec![]);
339        let mut output = vec![];
340        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
341        interpreter.execute("+[>+[.-]+[.-].<.-].");
342        assert_eq!(vec![1, 1, 0, 1, 0], output)
343    }
344
345    #[test]
346    fn interpreter_executes_double_embedded_no_end_loops() {
347        let mut input = Cursor::new(vec![]);
348        let mut output = vec![];
349        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
350        interpreter.execute("+[->++[->+[.-<]]");
351        assert_eq!(vec![1, 1], output)
352    }
353
354    #[test]
355    fn interpreter_executes_only_end_loop() {
356        let mut input = Cursor::new(vec![]);
357        let mut output = vec![];
358        let mut interpreter = Interpreter::new(&mut input, &mut output, 2);
359        interpreter.execute(".].");
360        assert_eq!(vec![0], output)
361    }
362}
vtashkov_bf/interpreter.rs

vtashkov_bf/
interpreter.rs
