Toy Brainfuck interpreter in Rust.

bf.rs

use std::fmt;
use std::io;
use thiserror::Error;

fn main() {
    let mut bf = Bf::new(1000, true);
    let mut input = String::new();
    loop {
        match io::stdin().read_line(&mut input) {
            Ok(0) => return,
            Ok(_) => {
                if let Err(err) = bf.execute(&input) {
                    eprintln!("{}", err);
                }
                bf.reset();
                input.clear();
            }
            Err(err) => {
                eprintln!("{}", err);
                return;
            }
        }
    }
}

#[derive(Debug)]
enum Op {
    Incr,
    Decr,
    MoveLeft,
    MoveRight,
    EndLoop(usize),
    BeginLoop(usize),
    Input,
    Output,
}

impl std::fmt::Display for Op {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> fmt::Result {
        let text = match self {
            Self::Incr => "+",
            Self::Decr => "-",
            Self::MoveLeft => "<",
            Self::MoveRight => ">",
            Self::EndLoop(_) => "[",
            Self::BeginLoop(_) => "]",
            Self::Input => ",",
            Self::Output => ".",
        };

        write!(f, "{}", text)
    }
}

#[derive(Debug, Error)]
enum Error {
    #[error("memory overflow at pos {0}")]
    CellOverflow(usize),
    #[error("memory underflow at pos {0}")]
    CellUnderflow(usize),
    #[error("data pointer overflow at pos {0}")]
    PointerOverflow(usize),
    #[error("data pointer underflow at pos {0}")]
    PointerUnderflow(usize),
    #[error("I/O error at pos {0}")]
    Input(usize),
    #[error("syntax error: unmatched loop at pos {0}")]
    Loop(usize),
    #[error("empty program")]
    Empty,
}

struct Bf {
    op_pointer: usize,
    data_pointer: usize,
    cycles: usize,
    memory: Vec<u8>,
    output: Vec<u8>,
    debug: bool,
}

impl Bf {
    fn new(size: usize, debug: bool) -> Bf {
        Bf {
            op_pointer: 0,
            data_pointer: 0,
            cycles: 0,
            memory: vec![0; size],
            output: Vec::new(),
            debug,
        }
    }

    fn reset(&mut self) {
        self.op_pointer = 0;
        self.data_pointer = 0;
        self.cycles = 0;
        self.memory.fill(0);
        self.output.clear();
    }

    fn parse(&self, code: &str) -> Result<Vec<Op>, Error> {
        let mut ops = Vec::with_capacity(code.len());
        let mut loops = std::collections::HashMap::new();
        let code = code.as_bytes();
        for (i, c) in code.iter().enumerate() {
            match c {
                b'+' => ops.push(Op::Incr),
                b'-' => ops.push(Op::Decr),
                b'<' => ops.push(Op::MoveLeft),
                b'>' => ops.push(Op::MoveRight),
                b'[' => {
                    let end = self.find_loop_end(code, i).ok_or(Error::Loop(i))?;
                    assert_eq!(code[end], b']');
                    ops.push(Op::EndLoop(end));
                    loops.insert(end, i);
                }
                b']' => {
                    let begin = loops.get(&i).ok_or(Error::Loop(i))?;
                    assert_eq!(code[*begin], b'[');
                    ops.push(Op::BeginLoop(*begin));
                }
                b'.' => ops.push(Op::Output),
                b',' => ops.push(Op::Input),
                _ => (), // Allow inline comments, etc.
            }
        }

        if ops.is_empty() {
            return Err(Error::Empty);
        }

        Ok(ops)
    }

    fn execute(&mut self, code: &str) -> Result<(), Error> {
        let ops = self.parse(code)?;
        let last_op = ops.len() - 1;
        while self.op_pointer <= last_op {
            self.execute_one(&ops)?;
        }

        if !self.output.is_empty() {
            print!("{}", String::from_utf8(self.output.clone()).unwrap());
        }

        Ok(())
    }

    fn execute_one(&mut self, ops: &[Op]) -> Result<(), Error> {
        let orig_ip = self.op_pointer;
        match ops[self.op_pointer] {
            Op::Incr => {
                self.memory[self.data_pointer] = self.memory[self.data_pointer]
                    .checked_add(1)
                    .ok_or(Error::CellOverflow(self.op_pointer))?;
            }
            Op::Decr => {
                self.memory[self.data_pointer] = self.memory[self.data_pointer]
                    .checked_sub(1)
                    .ok_or(Error::CellUnderflow(self.op_pointer))?
            }
            Op::MoveLeft => {
                self.data_pointer = self
                    .data_pointer
                    .checked_sub(1)
                    .ok_or(Error::PointerUnderflow(self.op_pointer))?
            }
            Op::MoveRight => {
                self.data_pointer = self
                    .data_pointer
                    .checked_add(1)
                    .ok_or(Error::PointerOverflow(self.op_pointer))?
            }
            Op::EndLoop(end) => {
                if self.memory[self.data_pointer] == 0 {
                    self.op_pointer = end;
                }
            }
            Op::BeginLoop(begin) => {
                if self.memory[self.data_pointer] != 0 {
                    self.op_pointer = begin;
                }
            }
            Op::Output => self.output.push(self.memory[self.data_pointer]),
            Op::Input => self.memory[self.data_pointer] = self.getc()?,
        }

        if self.debug {
            println!(
                "{:x}: op: {}; ip: {:x}; dp: {:x}; memory: {:x}",
                self.cycles,
                ops[orig_ip],
                orig_ip,
                self.data_pointer,
                self.memory[self.data_pointer],
            );
        }

        self.op_pointer += 1;
        self.cycles += 1;

        Ok(())
    }

    fn find_loop_end(&self, code: &[u8], begin: usize) -> Option<usize> {
        let mut lvl = 0;
        code[begin..]
            .iter()
            .position(|&c| {
                if c == b']' {
                    lvl -= 1;
                } else if c == b'[' {
                    lvl += 1;
                }

                lvl <= 0
            })
            .map(|i| i + begin)
    }

    fn getc(&self) -> Result<u8, Error> {
        use std::io::Read;

        let mut input = [0; 1];
        std::io::stdin()
            .read_exact(&mut input)
            .or(Err(Error::Input(self.op_pointer)))?;

        Ok(input[0])
    }
}

#[test]
fn hello_world() {
    let prog = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.";
    let mut bf = Bf::new(1000, false);
    assert!(bf.execute(prog).is_ok())
}

#[test]
fn fibonacci() {
    let prog = "+++++++++++>+>>>>++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-<-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<-]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<+>>[-]]<<<<<<<]>>>>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++++++++++++++++++++++++++++++++++++++++++++++.[-]<<<<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<[-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]";
    let mut bf = Bf::new(1000, false);
    assert!(bf.execute(prog).is_ok());
}

#[test]
fn execute_many() {
    let progs = [
        "+++++++++++>+>>>>++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++<<<<<<[>[>>>>>>+>+<<<<<<<-]>>>>>>>[<<<<<<<+>>>>>>>-]<[>++++++++++[-<-[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<[>>>+<<<-]>>[-]]<<]>>>[>>+>+<<<-]>>>[<<<+>>>-]+<[>[-]<[-]]>[<<+>>[-]]<<<<<<<]>>>>>[++++++++++++++++++++++++++++++++++++++++++++++++.[-]]++++++++++<[->-<]>++++++++++++++++++++++++++++++++++++++++++++++++.[-]<<<<<<<<<<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<-[>>.>.<<<[-]]<<[>>+>+<<<-]>>>[<<<+>>>-]<<[<+>-]>[<+>-]<<<-]",
        "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.",
    ];
    let mut bf = Bf::new(1000, false);
    for prog in progs.into_iter() {
        assert!(bf.execute(prog).is_ok());
        bf.reset();
    }
}