brainfck/
lib.rs

1//! Brainfuck interpreter
2//!
3//! # Example
4//! ```
5//! use brainfck::Interpreter;
6//!
7//! let hello_world = b">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]
8//! >++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++
9//! .------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.";
10//!
11//! let input = core::iter::empty();
12//! let mut out = Vec::new();
13//! let mut interpreter = Interpreter::new(hello_world, input, &mut out);
14//! interpreter.run().unwrap();
15//!
16//! assert_eq!(out, b"Hello world!\n");
17//! ```
18
19#![cfg_attr(not(feature = "std"), no_std)]
20
21#[cfg(feature = "alloc")]
22extern crate alloc;
23#[cfg(feature = "alloc")]
24use alloc::{
25    vec::Vec,
26};
27
28use core::fmt::Display;
29use core::iter::{self, Empty};
30
31use tiny_vec::{Cow, TinyVec};
32
33const DEFAULT_MEM_SIZE: usize = tiny_vec::n_elements_for_stack::<u8>();
34const DEFAULT_PROGRAM_SIZE: usize = tiny_vec::n_elements_for_stack::<u8>();
35const DEFAULT_LOOP_STACK_SIZE: usize = tiny_vec::n_elements_for_stack::<usize>();
36
37/// Interpreter for a brainfuck program
38#[derive(Clone, Debug, Default)]
39pub struct Interpreter<'prog,
40    In,
41    Out,
42    const MS: usize = DEFAULT_MEM_SIZE,
43    const PS: usize = DEFAULT_PROGRAM_SIZE,
44    const LS: usize = DEFAULT_LOOP_STACK_SIZE,
45>
46where
47    In: Iterator<Item = u8>,
48    Out: Writer,
49{
50    memory: TinyVec<u8, MS>,
51    /// Mem pointer. Index for the currentñy selected memory cell
52    ptr: usize,
53    /// Program counter. Index of the next instruction to execute
54    pc: usize,
55    program: Cow<'prog, u8, PS>,
56    input: In,
57    output: Out,
58    /// Currently open loops
59    open_loops: TinyVec<usize, LS>,
60    skiping_open_loop: Option<usize>,
61}
62
63impl<'prog, In, Out> Interpreter<'prog, In, Out>
64where
65    In: Iterator<Item = u8>,
66    Out: Writer
67{
68    /// Builds a new brainfuck interpreter for the given `program`.
69    #[inline]
70    pub fn new<Prog>(program: Prog, input: In, output: Out) -> Self
71    where
72        Prog: Into<Cow<'prog, u8, DEFAULT_PROGRAM_SIZE>>
73    {
74        Interpreter::with_custom_stack(program, input, output)
75    }
76}
77
78impl<'prog, In, Out,
79    const MS: usize,
80    const PS: usize,
81    const LS: usize
82> Interpreter<'prog, In, Out, MS, PS, LS>
83where
84    In: Iterator<Item = u8>,
85    Out: Writer
86{
87    /// Builds a new brainfuck interpreter for the given `program`.
88    pub fn with_custom_stack<Prog>(program: Prog, input: In, output: Out) -> Self
89    where
90        Prog: Into<Cow<'prog, u8, PS>>
91    {
92        let mut memory = TinyVec::<u8, MS>::new();
93        memory.resize(MS, 0);
94        Self {
95            pc: 0,
96            memory,
97            program: program.into(),
98            input,
99            output,
100            ptr: 0,
101            open_loops: TinyVec::<_, LS>::new(),
102            skiping_open_loop: None,
103        }
104    }
105
106    /// Turns the borrowed program slice into an [owned](Cow::Owned) variant.
107    ///
108    /// This returns a new [Interpreter], with a `'static` lifetime
109    pub fn into_owned(self) -> Interpreter<'static, In, Out, MS, PS, LS> {
110        let Self { memory, ptr, pc, program, input, output, open_loops: loop_starts, skiping_open_loop: parsing_open_loop } = self;
111        Interpreter {
112            memory,
113            program: Cow::<'static, _, PS>::Owned(program.into_owned()),
114            ptr,
115            pc,
116            input,
117            output,
118            open_loops: loop_starts,
119            skiping_open_loop: parsing_open_loop
120        }
121    }
122
123    /// Pushes an instruction to the program
124    pub fn push_instruction(&mut self, ins: u8) {
125        self.program.to_mut().push(ins);
126    }
127
128    /// Pushes the given instruction slice into the program
129    pub fn push_instruction_slice(&mut self, ins: &[u8]) {
130        self.program.to_mut().extend_from_slice(ins);
131    }
132
133    /// Pushes all the elements yielded from `iterator`
134    /// into the program
135    ///
136    /// # Example
137    /// ```
138    /// use brainfck::Interpreter;
139    ///
140    /// let mut bf = Interpreter::vec_output_empty_input(&[]);
141    ///
142    /// let ins = b"++++[>+<-]>.";
143    ///
144    /// bf.push_instructions_iter(ins.iter().copied());
145    /// bf.run().unwrap();
146    ///
147    /// assert_eq!(bf.get_output(), [4]);
148    ///
149    /// ```
150    pub fn push_instructions_iter<I>(&mut self, iterator: I)
151    where
152        I: Iterator<Item = u8>
153    {
154        self.program.to_mut().extend(iterator);
155    }
156
157    /// Executes the program until the end is reached
158    pub fn run(&mut self) -> Result<(), Error> {
159        while self.pc < self.program.len() {
160            self.step()?;
161        }
162        if self.open_loops.is_empty() {
163            Ok(())
164        } else {
165            Err(Error::OpenLoopsRemain)
166        }
167    }
168
169    /// Skips a loop that was open when the pointed memory cell was 0.
170    fn skip_loop(&mut self) -> Result<(), Error> {
171        /* Restore the nest level, in case the program reached eof before
172         * exiting the skiped loop. The program could've been extended
173         * with new instructions */
174        let mut nest = self.skiping_open_loop.take().unwrap_or(1);
175        while nest != 0 {
176            let next_ins = self.program.get(self.pc)
177                .copied()
178                .ok_or_else(|| {
179                    /* If we reach EOF, store the current next level and return */
180                    self.skiping_open_loop = Some(nest);
181                    Error::OpenLoopsRemain
182                })?;
183            if next_ins == b'[' { nest += 1; }
184            if next_ins == b']' { nest -= 1; }
185            self.pc += 1;
186        }
187        Ok(())
188    }
189
190    /// Executes the next instruction
191    pub fn step(&mut self) -> Result<(), Error> {
192        /* If a skiping operation was aborted because the program didn't have
193         * more instructions, resume it. */
194        if self.skiping_open_loop.is_some() {
195            return self.skip_loop();
196        }
197        if self.pc >= self.program.len() {
198            return if self.open_loops.is_empty() {
199                Ok(())
200            } else {
201                Err(Error::OpenLoopsRemain)
202            }
203        }
204        let ins  = self.program[self.pc];
205        self.pc += 1;
206        match ins {
207            b'>' => {
208                let cap = self.memory.capacity();
209                if self.ptr == cap {
210                    self.memory.extend_from_slice(&[0; 100]);
211                }
212                self.ptr += 1;
213            },
214            b'<' => self.ptr -= 1,
215            b'+' => self.memory[self.ptr] += 1,
216            b'-' => self.memory[self.ptr] -= 1,
217            b'.' => {
218                let b = self.memory[self.ptr];
219                self.output.push_byte(b).map_err(|_| Error::Output)?;
220            },
221            b',' => {
222                let b = self.input.next().unwrap_or(b'\0');
223                self.memory[self.ptr] = b;
224            },
225            b'[' => {
226                if self.memory[self.ptr] == 0 {
227                    self.skip_loop()?;
228                } else {
229                    self.open_loops.push(self.pc - 1);
230                }
231            },
232            b']' => {
233                let start = self.open_loops.pop().ok_or(Error::MissingOpenLoop)?;
234                if self.memory[self.ptr] != 0 {
235                    self.pc = start;
236                }
237            },
238            c if c.is_ascii_whitespace() => {},
239            _ => return Err(Error::UnexpectedByte(ins)),
240        }
241        Ok(())
242    }
243
244    /// Gets the current state of the program's memory
245    #[inline]
246    pub const fn get_memory(&self) -> &[u8] { self.memory.as_slice() }
247
248    /// Returns true if this `Interpreter` hasn't allocated any
249    /// memory on the heap
250    ///
251    /// The interpreter uses a [TinyVec] to store the program's memory
252    /// and stack of open loops.
253    /// The `TinyVec` first stores elements on the stack, until it reaches
254    /// a certain length, in which it moves to the heap.
255    ///
256    /// If both vectors (memory and open_loops) are stack-based, and the
257    /// program buffer is still borrowed, this Interpreter hasn't allocated
258    /// any memory __directly__.
259    pub const fn lives_on_stack(&self) -> bool {
260        self.memory.lives_on_stack()
261        && self.open_loops.lives_on_stack()
262        && self.program.lives_on_stack()
263    }
264}
265
266#[cfg(feature = "alloc")]
267impl<'prog, In> Interpreter<'prog, In, Vec<u8>>
268where
269    In: Iterator<Item = u8>,
270{
271    /// Creates a new `Interpreter` with a `Vec` output
272    ///
273    /// This is just a shortcut for `Interpreter::new(program, input, Vec::new())`
274    pub fn vec_output(program: impl Into<Cow<'prog, u8, DEFAULT_PROGRAM_SIZE>>, input: In) -> Self {
275        Self::new(program, input, Vec::new())
276    }
277
278    /// Gets the output for this [`Interpreter<_, Vec<u8>>`]
279    pub fn get_output(&self) -> &[u8] { &self.output }
280}
281
282impl<'prog, Out> Interpreter<'prog, Empty<u8>, Out>
283where
284    Out: Writer
285{
286    /// Creates a new `Interpreter` with an empty input
287    ///
288    /// This is just a shortcut for `Interpreter::new(program, iter::empty(), output)`
289    pub fn empty_input(program: impl Into<Cow<'prog, u8, DEFAULT_PROGRAM_SIZE>>, output: Out) -> Self {
290        Self::with_custom_stack(program, iter::empty(), output)
291    }
292}
293
294#[cfg(feature = "alloc")]
295impl<'prog> Interpreter<'prog, Empty<u8>, Vec<u8>> {
296
297    /// Creates a new `Interpreter` with an empty input and a `Vec` output
298    /// This is just a shortcut for `Interpreter::new(program, iter::empty(), Vec::new())`
299    pub fn vec_output_empty_input(program: impl Into<Cow<'prog, u8, DEFAULT_PROGRAM_SIZE>>) -> Self {
300        Self::new(program, iter::empty(), Vec::new())
301    }
302}
303
304/// Signals an error on the [interpreter](Interpreter)
305#[derive(Debug)]
306pub enum Error {
307    /// Output error. Emited from the given [writer](Writer)
308    Output,
309    /// Encountered a closing loop ']' that didn't match with an open '['
310    MissingOpenLoop,
311    /// Couldn't interpret the given byte
312    UnexpectedByte(u8),
313    /// EOF Reached while loops still open
314    OpenLoopsRemain,
315}
316
317impl Display for Error {
318    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
319        match self {
320            Error::UnexpectedByte(b) => write!(f, "Got unexpected instruction '{}' ({b})", *b as char),
321            Error::Output => write!(f, "Error writing to output"),
322            Error::MissingOpenLoop => write!(f, "Missing open '[' for ']'"),
323            Error::OpenLoopsRemain => write!(f, "EOF reached with loops still open"),
324        }
325    }
326}
327
328/// Wrapper trait of [`std::io::Read`] for `no_std` enviroments.
329///
330/// [`std::io::Read`]: <https://doc.rust-lang.org/std/io/trait.Write.html>
331pub trait Writer {
332    type Error;
333    fn push_byte(&mut self, byte: u8) -> Result<(), Self::Error>;
334}
335
336/// A dummy [Writer] that ignores the input and always returns [Ok]
337pub struct NoOutput;
338
339impl Writer for NoOutput {
340    type Error = core::convert::Infallible;
341
342    fn push_byte(&mut self, _byte: u8) -> Result<(), Self::Error> {
343        Ok(())
344    }
345}
346
347#[cfg(feature = "std")]
348impl <T: std::io::Write> Writer for T {
349    type Error = std::io::Error;
350
351    fn push_byte(&mut self, byte: u8) -> Result<(), Self::Error> {
352        self.write_all(&[byte])
353    }
354}
355
356#[cfg(all(not(feature = "std"), not(feature = "alloc")))]
357impl<const N: usize> Writer for TinyVec<u8, N> {
358    type Error = core::convert::Infallible;
359
360    fn push_byte(&mut self, byte: u8) -> Result<(), Self::Error> {
361        self.push(byte);
362        Ok(())
363    }
364}
365
366#[cfg(all(not(feature = "std"), not(feature = "alloc")))]
367impl<const N: usize> Writer for &mut TinyVec<u8, N> {
368    type Error = core::convert::Infallible;
369
370    fn push_byte(&mut self, byte: u8) -> Result<(), Self::Error> {
371        self.push(byte);
372        Ok(())
373    }
374}
375
376#[cfg(all(not(feature = "std"), feature = "alloc"))]
377impl Writer for Vec<u8> {
378    type Error = core::convert::Infallible;
379
380    fn push_byte(&mut self, byte: u8) -> Result<(), Self::Error> {
381        self.push(byte);
382        Ok(())
383    }
384}
385
386#[cfg(all(test, feature = "std"))]
387mod test;
388#[cfg(all(test, not(feature = "std")))]
389mod test_no_std;
brainfck/lib.rs

brainfck/
lib.rs
