ablescript/
brian.rs

1//! A brainfuck interpreter capable of executing arbitrary code, with arbitrary inputs and outputs.
2//!
3//! If you just want to execute some simple brainfuck, check the [`interpret_with_io`] function.
4//!
5//! To construct the interpreter, use the [`from_ascii`] or [`from_ascii_with_input_buffer`] methods
6//! (or their variants that take a maximum tape size). The latter grants access to
7//! the method [`add_input`], which allows for the addition of input while the interpreter is running.
8//!
9//! [`from_ascii`]: Interpreter::from_ascii
10//! [`from_ascii_with_input_buffer`]: Interpreter::from_ascii_with_input_buffer
11//! [`add_input`]: Interpreter::add_input
12//!
13//! Finally, to run the interpreter, you can use the [`advance`], [`advance_until_io`], or [`interpret_with_output`] methods.
14//!
15//! [`advance`]: Interpreter::advance
16//! [`advance_until_io`]: Interpreter::advance_until_io
17//! [`interpret_with_output`]: Interpreter::interpret_with_output
18
19#![deny(missing_docs)]
20// Putting this here because we still don't use the entire capabilities of this module. ~~Alex
21#![allow(dead_code)]
22
23use std::{
24    collections::VecDeque,
25    error::Error,
26    fmt::Display,
27    io::{Read, Write},
28};
29
30// NOTE(Able): This is the brain fuck interface
31
32/// The default limit for the tape size. This is the value used by methods that don't take it as a parameter
33pub const DEFAULT_TAPE_SIZE_LIMIT: usize = 30_000;
34
35/// Mappings from integers to BF instructions
36pub const INSTRUCTION_MAPPINGS: &[u8] = b"[]+-,.<>";
37#[derive(Debug, Clone, PartialEq, Eq)]
38/// A brainfuck interpreter. Read the [module level documentation](self) for more
39pub struct Interpreter<'a, I> {
40    code: &'a [u8],
41    instr_ptr: usize,
42    tape: Vec<i8>,
43    data_ptr: usize,
44    tape_size_limit: usize,
45    input: I,
46}
47
48impl<'a> Interpreter<'a, InputBuffer> {
49    /// Construct an `Interpreter` from an ASCII string of code with an empty input buffer
50    /// This methods sets the tape size limit to [its default value](DEFAULT_TAPE_SIZE_LIMIT)
51    pub fn from_ascii_with_input_buffer(code: &'a [u8]) -> Self {
52        Self::from_ascii_with_input_buffer_and_tape_limit(code, DEFAULT_TAPE_SIZE_LIMIT)
53    }
54
55    /// Construct an `Interpreter` from an ASCII string of code with an empty input buffer,
56    /// setting the tape size limit to the specified value
57    pub fn from_ascii_with_input_buffer_and_tape_limit(
58        code: &'a [u8],
59        tape_size_limit: usize,
60    ) -> Self {
61        Self {
62            code,
63            instr_ptr: 0,
64            tape: Vec::new(),
65            data_ptr: 0,
66            tape_size_limit,
67            input: InputBuffer(VecDeque::new()),
68        }
69    }
70
71    /// Add a byte to the input buffer of this interpreter
72    pub fn add_input(&mut self, input: i8) {
73        self.input.0.push_back(input);
74    }
75}
76
77impl<'a, I: BootlegRead> Interpreter<'a, I> {
78    /// Construct an interpreter from an ASCII string of code, a source of input bytes, and a tape size limit
79    pub fn from_ascii_with_tape_limit(code: &'a [u8], input: I, tape_size_limit: usize) -> Self {
80        Self {
81            code,
82            instr_ptr: 0,
83            tape: Vec::new(),
84            data_ptr: 0,
85            tape_size_limit,
86            input,
87        }
88    }
89
90    /// Constructs an interpreter from an ASCII string of code, a source of input bytes, and [the default tape size limit](DEFAULT_TAPE_SIZE_LIMIT)
91    pub fn from_ascii(code: &'a [u8], input: I) -> Self {
92        Self::from_ascii_with_tape_limit(code, input, DEFAULT_TAPE_SIZE_LIMIT)
93    }
94
95    /// Advance the interpreter by one instruction.
96    /// A return value of Ok(None) indicates succesful termination of the interpreter
97    pub fn advance(&mut self) -> Result<Option<Status>, ProgramError> {
98        let &opcode = match self.code.get(self.instr_ptr) {
99            Some(opcode) => opcode,
100            None => return Ok(None),
101        };
102
103        match opcode {
104            b'>' => self.data_ptr += 1,
105
106            b'<' => {
107                self.data_ptr = self
108                    .data_ptr
109                    .checked_sub(1)
110                    .ok_or(ProgramError::DataPointerUnderflow)?;
111            }
112
113            b'+' => {
114                let val = self
115                    .get_or_resize_tape_mut()
116                    .ok_or(ProgramError::TapeSizeExceededLimit)?;
117                *val = val.wrapping_add(1)
118            }
119
120            b'-' => {
121                let val = self
122                    .get_or_resize_tape_mut()
123                    .ok_or(ProgramError::TapeSizeExceededLimit)?;
124                *val = val.wrapping_sub(1)
125            }
126
127            b'.' => {
128                self.instr_ptr += 1;
129                return Ok(Some(Status::Output(self.get_at_data_ptr())));
130            }
131
132            b',' => match self.input.bootleg_read() {
133                Ok(Some(num)) => {
134                    let cell = self
135                        .get_or_resize_tape_mut()
136                        .ok_or(ProgramError::TapeSizeExceededLimit)?;
137                    *cell = num;
138                }
139                Ok(None) => return Ok(Some(Status::NeedsInput)),
140                Err(_) => return Err(ProgramError::InputReadError),
141            },
142
143            b'[' => {
144                if self.get_at_data_ptr() == 0 {
145                    self.instr_ptr = self
146                        .get_matching_closing_bracket(self.instr_ptr)
147                        .ok_or(ProgramError::UnmatchedOpeningBracket)?
148                    //Instruction pointer will be incremented by 1 after the match
149                }
150            }
151
152            b']' => {
153                if self.get_at_data_ptr() != 0 {
154                    self.instr_ptr = self
155                        .get_matching_opening_bracket(self.instr_ptr)
156                        .ok_or(ProgramError::UnmatchedClosingBracket)?
157                    //Instruction pointer will be incremented by 1 after the match
158                }
159            }
160
161            _ => {} //brainfuck treats all characters it doesn't understand as comments
162        }
163
164        self.instr_ptr += 1;
165
166        Ok(Some(Status::Continue))
167    }
168
169    /// Advances the interpreter until the next IO operation. See [`advance`](Interpreter::advance)  
170    pub fn advance_until_io(&mut self) -> Result<Option<IoStatus>, ProgramError> {
171        while let Some(status) = self.advance()? {
172            match status {
173                Status::NeedsInput => return Ok(Some(IoStatus::NeedsInput)),
174                Status::Output(out) => return Ok(Some(IoStatus::Output(out))),
175                Status::Continue => continue,
176            }
177        }
178        Ok(None)
179    }
180
181    /// Executes the interpreter until it halts, writing all return values to the provided `Write` type.
182    /// For more granular control, use [`advance`](Interpreter::advance)
183    pub fn interpret_with_output<O: Write>(&mut self, mut output: O) -> Result<(), InterpretError> {
184        while let Some(status) = self.advance_until_io()? {
185            match status {
186                IoStatus::NeedsInput => return Err(InterpretError::EndOfInput),
187                IoStatus::Output(out) => match output.write(&[out as u8]) {
188                    Ok(0) => return Err(InterpretError::OutputBufferFull),
189                    Ok(_) => continue,
190                    Err(_) => return Err(InterpretError::OutputWriteError),
191                },
192            }
193        }
194        Ok(())
195    }
196
197    fn get_or_resize_tape_mut(&mut self) -> Option<&mut i8> {
198        if self.data_ptr > self.tape_size_limit {
199            return None;
200        }
201        if self.data_ptr >= self.tape.len() {
202            self.tape.resize(self.data_ptr + 1, 0);
203        }
204        Some(&mut self.tape[self.data_ptr])
205    }
206
207    fn get_at_data_ptr(&self) -> i8 {
208        //No need to resize the tape to read: if the tape doesn't extend that far already, it holds a value of 0
209        self.tape.get(self.data_ptr).copied().unwrap_or(0)
210    }
211
212    fn get_matching_closing_bracket(&mut self, opening: usize) -> Option<usize> {
213        self.code[opening..]
214            .iter()
215            .zip(opening..)
216            .scan(0, |counter, (char, index)| {
217                match char {
218                    b'[' => *counter += 1,
219                    b']' => *counter -= 1,
220                    _ => {}
221                };
222                Some((*counter, index))
223            })
224            .find_map(|(counter, index)| (counter == 0).then_some(index))
225    }
226
227    fn get_matching_opening_bracket(&mut self, closing: usize) -> Option<usize> {
228        self.code[..closing + 1]
229            .iter()
230            .zip(0..closing + 1)
231            .rev()
232            .scan(0, |counter, (char, index)| {
233                match char {
234                    b']' => *counter += 1,
235                    b'[' => *counter -= 1,
236                    _ => {}
237                };
238                Some((*counter, index))
239            })
240            .find_map(|(counter, index)| (counter == 0).then_some(index))
241    }
242}
243
244/// A convenience function for interpreting brainfuck code with a given input and output source.
245/// For more information, consult [the module level documentation](self)
246pub fn interpret_with_io<I: BootlegRead, O: Write>(
247    code: &[u8],
248    input: I,
249    output: O,
250) -> Result<(), InterpretError> {
251    Interpreter::from_ascii(code, input).interpret_with_output(output)
252}
253
254#[derive(Debug, Clone, Copy, PartialEq, Eq)]
255///The result of advancing the interpreter by one step, assuming it didn't terminate
256pub enum Status {
257    NeedsInput,
258    Output(i8),
259    Continue,
260}
261
262#[derive(Debug, Clone, Copy, PartialEq, Eq)]
263/// The result of advancing the interpreter until the next IO operation, assuming it didn't terminate
264pub enum IoStatus {
265    NeedsInput,
266    Output(i8),
267}
268
269#[derive(Debug, Clone, Copy, PartialEq, Eq)]
270/// An error that occurred while the interpreter was advancing
271pub enum ProgramError {
272    DataPointerUnderflow,
273    InputReadError,
274    UnmatchedOpeningBracket,
275    UnmatchedClosingBracket,
276    TapeSizeExceededLimit,
277}
278
279impl Display for ProgramError {
280    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
281        write!(
282            f,
283            "{}",
284            match self {
285                ProgramError::DataPointerUnderflow => "data pointer underflow",
286                ProgramError::InputReadError => "input read error",
287                ProgramError::UnmatchedOpeningBracket => "unmatched `[`",
288                ProgramError::UnmatchedClosingBracket => "unmatched `]`",
289                ProgramError::TapeSizeExceededLimit => "tape size exceeded",
290            }
291        )
292    }
293}
294impl Error for ProgramError {}
295
296#[derive(Debug, Clone, Copy, PartialEq, Eq)]
297/// An error that occurred while the interpreter was being run start-to-end all in one go
298pub enum InterpretError {
299    ProgramError(ProgramError),
300    EndOfInput,
301    OutputBufferFull,
302    OutputWriteError,
303}
304
305impl Display for InterpretError {
306    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
307        match self {
308            InterpretError::ProgramError(e) => write!(f, "program error: {}", e),
309            InterpretError::EndOfInput => write!(f, "unexpected end of input"),
310            InterpretError::OutputBufferFull => write!(f, "output buffer full"),
311            InterpretError::OutputWriteError => write!(f, "output write error"),
312        }
313    }
314}
315impl Error for InterpretError {}
316
317impl From<ProgramError> for InterpretError {
318    fn from(e: ProgramError) -> Self {
319        InterpretError::ProgramError(e)
320    }
321}
322
323/// A bootlegged version of the standard library's read trait, so as to allow the interpreter to be generic over any `Read`
324/// type, as well as over an input buffer.
325pub trait BootlegRead {
326    type Error;
327    fn bootleg_read(&mut self) -> Result<Option<i8>, Self::Error>;
328}
329
330impl<T: Read> BootlegRead for T {
331    type Error = std::io::Error;
332    fn bootleg_read(&mut self) -> Result<Option<i8>, Self::Error> {
333        let mut buffer = [0];
334        match self.read(&mut buffer) {
335            Ok(0) => Ok(None),
336            Ok(_) => Ok(Some(buffer[0] as i8)),
337            Err(e) => Err(e),
338        }
339    }
340}
341
342/// A wrapper around a `VecDeque`, to be able to implement `BootlegRead` for it
343struct InputBuffer(VecDeque<i8>);
344impl BootlegRead for InputBuffer {
345    type Error = std::convert::Infallible;
346    fn bootleg_read(&mut self) -> Result<Option<i8>, Self::Error> {
347        Ok(self.0.pop_front())
348    }
349}
350
351#[cfg(test)]
352mod tests {
353    use super::*;
354
355    #[test]
356    fn adder() {
357        let mut interpreter = Interpreter {
358            code: b"[->+<]", //Source: https://en.wikipedia.org/wiki/Brainfuck
359            instr_ptr: 0,
360            tape: vec![10, 5],
361            data_ptr: 0,
362            tape_size_limit: DEFAULT_TAPE_SIZE_LIMIT,
363            input: std::io::empty(),
364        };
365
366        while let Some(status) = interpreter.advance_until_io().expect("Unexpected error") {
367            match status {
368                IoStatus::NeedsInput => panic!("Requested input in an IO-less program"),
369                IoStatus::Output(_) => panic!("Produced output in an IO-less program"),
370            }
371        }
372
373        assert_eq!(interpreter.tape, vec![0, 15]);
374    }
375
376    #[test]
377    fn hello_world() {
378        let mut interpreter = Interpreter::from_ascii(
379            b"++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.", 
380            std::io::empty(),
381        );
382
383        let mut string = Vec::new();
384        interpreter
385            .interpret_with_output(&mut string)
386            .expect("Failed to write to output buffer");
387        assert_eq!(string, b"Hello World!\n");
388    }
389
390    #[test]
391    fn with_input_buffer() {
392        let mut interpreter = Interpreter::from_ascii_with_input_buffer(b"+++++.>,[-<->].");
393        let output = match interpreter
394            .advance_until_io()
395            .expect("Unexpected error")
396            .expect("Unexpected termination")
397        {
398            IoStatus::NeedsInput => panic!("Unexpected input request"),
399            IoStatus::Output(out) => out,
400        };
401
402        assert_eq!(
403            interpreter.advance_until_io(),
404            Ok(Some(IoStatus::NeedsInput))
405        );
406
407        interpreter.add_input(output);
408
409        assert_eq!(
410            interpreter.advance_until_io(),
411            Ok(Some(IoStatus::Output(0)))
412        );
413        assert_eq!(interpreter.advance_until_io(), Ok(None));
414    }
415
416    #[test]
417    fn hit_tape_size_limit() {
418        let mut interpreter =
419            Interpreter::from_ascii_with_tape_limit(b"+>+>+>+>+>", std::io::empty(), 1);
420        let result = interpreter.interpret_with_output(std::io::sink());
421        assert_eq!(
422            result,
423            Err(InterpretError::ProgramError(
424                ProgramError::TapeSizeExceededLimit
425            ))
426        );
427    }
428
429    #[test]
430    fn positive_integer_overflow() {
431        interpret_with_io(b"+[+]", std::io::empty(), std::io::sink()).unwrap();
432    }
433
434    #[test]
435    fn negative_integer_overflow() {
436        interpret_with_io(b"-", std::io::empty(), std::io::sink()).unwrap();
437    }
438}
ablescript/brian.rs

ablescript/
brian.rs
