Brainfuck interpreter utilizing idiomatic Rust

Question

I'm learning Rust at the moment, I've read the book and been just playing around with the language. I wrote this simple Brainfuck interpreter, because I think that it's always a fun exercise. The interpreter uses a tape size of 30000 and cell size of one byte. Decrementing a cell's value under 0 will wrap it to 255 and vice versa.

The program consists of three files: main.rs, tape.rs, and errors.rs and has no dependencies outside the standard library. It expects a relative path to a Brainfuck source file as a command line argument, and can be run with the command (I'm using Rust 1.41.0):

$ cargo run --release bf/mandelbrot.bf

Would be great to get some feedback on this. Especially looking for ways to write some parts more idiomatically, using some of Rust's nicer features I've missed.

main.rs:

use std::env;
use std::error::Error;
use std::fs;
use std::io;
use std::process;

use crate::errors::{BraceError, TapeError};
use crate::tape::Tape;

mod errors;
mod tape;

const TAPE_LENGTH: i32 = 30000;

fn main() -> Result<(), Box<dyn Error>> {
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
        eprintln!(
            "{}{}",
            "Expected a brainfuck source file as a command line argument.\n",
            "Terminating the program."
        );
        process::exit(1);
    }

    let tokens = read_file_to_tokens(&args[1])?;
    let tokens = remove_comments(tokens);
    let tokens = pair_braces(tokens)?;
    interpret(tokens)?;

    Ok(())
}

#[derive(PartialEq)]
enum Token {
    Add,
    Sub,
    Right,
    Left,
    Dot,
    Comma,
    LeftBrace(Option<usize>),
    RightBrace(Option<usize>),
    Comment,
}

/// This will ignore all the comment chars in the file.
fn read_file_to_tokens(file_path: &str) -> Result<Vec<Token>, io::Error> {
    Ok(fs::read_to_string(file_path)?
        .chars()
        .map(|c| match c {
            '+' => Token::Add,
            '-' => Token::Sub,
            '>' => Token::Right,
            '<' => Token::Left,
            '.' => Token::Dot,
            ',' => Token::Comma,
            '[' => Token::LeftBrace(None),
            ']' => Token::RightBrace(None),
            _ => Token::Comment,
        })
        .collect())
}

/// Remove all the comment chars from the tokens, this removes all chars
/// which have no meaning in brainfuck, so everything except: `+-<>.,[]`.
fn remove_comments(tokens: Vec<Token>) -> Vec<Token> {
    tokens
        .into_iter()
        .filter(|t| t != &Token::Comment)
        .collect()
}

/// Pair the braces into the LeftBrace and RightBrace tokens.
/// The index of the matching brace will be inside the Some variant of the token value.
fn pair_braces(mut tokens: Vec<Token>) -> Result<Vec<Token>, BraceError> {
    // Form all the (i, j) index pairs that correspond to a matching brace pair.
    let mut pairs = Vec::new();
    for (i, tok) in tokens.iter().enumerate() {
        if *tok == Token::LeftBrace(None) {
            let mut j = i;
            let mut brace_count = 1;
            while tokens[j] != Token::RightBrace(None) || brace_count != 0 {
                if j == tokens.len() - 1 {
                    return Err(BraceError { brace_index: i });
                }
                j += 1;
                match tokens[j] {
                    Token::LeftBrace(None) => brace_count += 1,
                    Token::RightBrace(None) => brace_count -= 1,
                    _ => (),
                }
            }
            pairs.push((i, j));
        }
    }

    // Do the actual pairing of the braces in the tokens.
    for (i, j) in pairs {
        tokens[i] = Token::LeftBrace(Some(j));
        tokens[j] = Token::RightBrace(Some(i));
    }

    // Final check that all the braces got paired correctly.
    // This will return an error when for example the source had
    // only a single right brace in it.
    for (i, tok) in tokens.iter().enumerate() {
        if *tok == Token::LeftBrace(None) || *tok == Token::RightBrace(None) {
            return Err(BraceError { brace_index: i });
        }
    }

    Ok(tokens)
}

/// The actual interpreter. Goes through the source char by char and
/// acts according to Brainfuck's rules.
fn interpret(tokens: Vec<Token>) -> Result<(), TapeError> {
    let mut tape = Tape::new(TAPE_LENGTH);

    let mut i = 0usize;
    while i < tokens.len() {
        match tokens[i] {
            Token::Add => tape.incr_cell(),
            Token::Sub => tape.decr_cell(),
            Token::Right => tape.incr_head()?,
            Token::Left => tape.decr_head()?,
            Token::Dot => tape.print_current(),
            Token::Comma => tape.read_to_current(),
            Token::LeftBrace(Some(n)) if tape.get_current() == 0 => i = n,
            Token::RightBrace(Some(n)) if tape.get_current() != 0 => i = n,
            _ => (),
        }
        i += 1;
    }

    Ok(())
}

tape.rs:

use std::fmt::{self, Display, Formatter};
use std::io::{self, Read, Write};
use std::num::Wrapping;

use crate::errors::TapeError;

/// The memory tape of the program.
pub struct Tape {
    size: i32,
    head: i32,
    tape: Vec<Wrapping<u8>>,
}

impl Tape {
    pub fn new(size: i32) -> Tape {
        Tape {
            size,
            head: 0,
            tape: vec![Wrapping(0u8); size as usize],
        }
    }

    pub fn incr_cell(&mut self) {
        self.tape[self.head as usize] += Wrapping(1);
    }

    pub fn decr_cell(&mut self) {
        self.tape[self.head as usize] -= Wrapping(1);
    }

    pub fn incr_head(&mut self) -> Result<(), TapeError> {
        self.head += 1;
        self.err_if_not_in_bounds()
    }

    pub fn decr_head(&mut self) -> Result<(), TapeError> {
        self.head -= 1;
        self.err_if_not_in_bounds()
    }

    pub fn print_current(&self) {
        print!("{}", self.tape[self.head as usize].0 as char);
        io::stdout().flush().unwrap();
    }

    pub fn read_to_current(&mut self) {
        self.tape[self.head as usize].0 = io::stdin()
            .bytes()
            .next()
            .and_then(|result| result.ok())
            .map(|byte| byte as u8)
            .unwrap();
    }

    pub fn get_current(&self) -> u8 {
        self.tape[self.head as usize].0
    }

    fn err_if_not_in_bounds(&self) -> Result<(), TapeError> {
        if self.head < 0 || self.head >= self.size {
            Err(TapeError {
                tape_index: self.head,
            })
        } else {
            Ok(())
        }
    }
}

impl Display for Tape {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        let sample = 40;
        let mut s = String::with_capacity(4 * sample);

        for cell in self.tape.iter().take(sample) {
            s.push_str(format!("[{}] ", cell.0).as_str());
        }
        write!(f, "{}", s)
    }
}

errors.rs:

use std::error::Error;
use std::fmt::{self, Debug, Display, Formatter};

pub struct BraceError {
    pub brace_index: usize,
}

impl Error for BraceError {}

impl Display for BraceError {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(
            f,
            "Mismatched braces in the source file, no pair for the brace at position: {}",
            self.brace_index + 1
        )
    }
}

impl Debug for BraceError {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        return Display::fmt(&self, f);
    }
}

pub struct TapeError {
    pub tape_index: i32,
}

impl Error for TapeError {}

impl Display for TapeError {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(
            f,
            "Tape head over tape bounds at index: {}",
            self.tape_index
        )
    }
}

impl Debug for TapeError {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        return Display::fmt(&self, f);
    }
}

Answer 1

The main thing I notice is that pair_braces looks clumsy. For every left brace, it goes off to find the matching right brace, tracking nested braces along the way. This is very inefficient (N^2 if your input consists only of perfectly nested braces, e.g. [[[[[[]]]]]]). It also simply doesn't feel right.

A better way is to keep a stack of left brace positions. As you go through the tokens, you push the position for each left brace on the stack. For each right brace, you pop the most recent position off the stack and add it, together with the current position, to the pair vector. If the stack is empty when you try to pop, you have an unmatched right brace. If the stack is not empty when you're done, you have an unmatched left brace.

For code organization, my personal preference would be to not have an errors module, but instead put the errors with the module they belong to: TapeError goes into tape.rs, BraceError goes into parser.rs (where you also put the other tokenizer/parser functions).

Another thing: if you're just going to discard comment tokens, why have them in the first place? You could just skip them in the initial step.

I really like that you're using the Wrapping wrapper.