tapir_bf/

lib.rs

//! Tapir is a one-function, zero-dependency Brainfuck interpreter.

#![warn(
    clippy::all,
    clippy::restriction,
    clippy::pedantic,
    clippy::nursery,
    clippy::cargo
)]

use crate::TapirError::*;
use std::fmt::{Debug, Display, Formatter};
use std::io::{self, Write};
use std::iter;

fn match_right(index: usize, program: &[u8], lma: usize, lmv: usize) -> (usize, usize, usize) {
    if lma == index {
        return (lmv, lma, lmv);
    }

    let lma = index;
    let mut index = index;

    let mut depth = 0;
    while index < program.len() {
        if program[index] as char == '[' {
            depth += 1;
        } else if program[index] as char == ']' {
            depth -= 1;
        }
        if depth == 0 {
            break;
        }
        index += 1;
    }
    if depth != 0 {
        return (0, lma, lmv);
    }
    (index, lma, index)
}

fn match_left(
    index: usize,
    program: &[u8],
    lma: usize,
    lmv: usize,
) -> (Option<usize>, usize, usize) {
    if lma == index {
        return (Some(lmv), lma, lmv);
    }

    let lma = index;
    let origin = index;
    let mut index = index;
    let mut depth = 0;

    while index <= origin {
        if program[index] as char == '[' {
            depth += 1;
        } else if program[index] as char == ']' {
            depth -= 1;
        }
        if depth == 0 {
            break;
        }
        index -= 1;
    }
    if depth != 0 {
        return (None, lma, lmv);
    }

    (Some(index), lma, index)
}

fn enhanced(s: &[u8]) -> Result<Vec<u8>, String> {
    let mut bytes: Vec<u8> = Vec::with_capacity(s.len());

    let byte_input = s;

    let mut i = 0;
    let input_len = byte_input.len();
    while i < input_len {
        if byte_input[i] as char == '\\' {
            if i + 1 < input_len {
                i += 1;
                bytes.push(match byte_input[i] {
                    b'n' => b'\n' as u8,
                    b'r' => b'\r' as u8,
                    b't' => b'\t' as u8,
                    b'\\' => b'\\' as u8,
                    b'#' => b'#' as u8,
                    _ => {
                        return Err(format!(
                            "expected an escape code but found '{}'",
                            byte_input[i] as char
                        ));
                    }
                });
            } else {
                return Err("expected an escape code but found nothing".to_string());
            }
        } else if byte_input[i] as char == '#' {
            if i + 3 < input_len {
                let mut res: u8 = 0;
                for j in 1..4 {
                    if byte_input[i + j].is_ascii_digit() {
                        res += (byte_input[i + j] - 48) * 10_u8.pow(3 - j as u32);
                    } else {
                        return Err(format!(
                            "expected a digit but found '{}'",
                            byte_input[i + j] as char
                        ));
                    }
                }
                bytes.push(res);
                i += 3;
            } else {
                return Err("expected a byte literal but didn't find enough digits".to_string());
            }
        } else {
            bytes.push(byte_input[i]);
        }
        i += 1;
    }

    debug_assert!(
        !bytes.is_empty(),
        "This function should only ever be called on non-empty arguments."
    );

    Ok(bytes)
}

/// Wraps any valid input stream with a line-based preprocessor.
///
/// The following three modes for specifying input values are supported:
/// 1. By character: simply press a key (except `\` or `#`) to enter its ascii value.
/// 2. By escape code: type `\n`, `\r`, `\t`, `\\`, or `\#` to enter a newline, return,
/// tab, backslash, or octothorpe respectively.
/// 3. By byte literal: type `#xyz`, where `xyz` is a three-digit, base-ten ascii code
/// to enter the value of `xyz`.
pub fn enhanced_input<I, E>(input: I) -> impl Iterator<Item = Result<u8, EnhancedInputError<E>>>
where
    I: IntoIterator<Item = Result<u8, E>>,
{
    let mut input = input.into_iter();

    let mut line: Vec<u8> = Vec::new();

    iter::from_fn(move || match input.next() {
        Some(Ok(b'\n')) => {
            let r = Some(Some(Ok(line.clone())));
            line.clear();
            r
        }
        Some(Ok(c)) => {
            line.push(c);
            Some(None)
        }
        Some(Err(e)) => Some(Some(Err(EnhancedInputError::InputException(e)))),
        None => None,
    })
    .filter_map(|x| match x {
        None => None,
        Some(Ok(line)) => match enhanced(&line) {
            Ok(u8s) => Some(Ok(u8s)),
            Err(e) => Some(Err(EnhancedInputError::MalformedInput(e))),
        },
        Some(Err(e)) => Some(Err(e)),
    })
    .flat_map(|result| match result {
        Ok(vec) => vec.into_iter().map(Ok).collect::<Vec<_>>().into_iter(),
        Err(e) => std::iter::once(Err(e)).collect::<Vec<_>>().into_iter(),
    })
}

/// The type of errors generated by [`enhanced_input`].
/// Wraps the error type `E` of the underlying iterator in `InputException<E>`.
#[derive(Debug)]
pub enum EnhancedInputError<E> {
    MalformedInput(String),
    InputException(E),
}

impl<E: Display> Display for EnhancedInputError<E> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::MalformedInput(s) => write!(f, "Malformed input: {}", s),
            Self::InputException(e) => write!(f, "{}", e),
        }
    }
}

/// The type of errors encountered/generated by [`interpret`] during execution,
/// representing I/O failures as well as invalid Brainfuck programs/interpreter states.
#[derive(Debug)]
pub enum TapirError<E> {
    BracketError,
    MemPtrUnderflowError,
    InputExceptionError(E),
    MissingInputError,
    OutputError(io::Error),
}

impl<E: Display> Display for TapirError<E> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            InputExceptionError(e) => write!(f, "InputExceptionError: {}", e),
            OutputError(e) => write!(f, "OutputError: {}", e),
            BracketError => write!(f, "BracketError"),
            MemPtrUnderflowError => write!(f, "MemPtrUnderflowError"),
            MissingInputError => write!(f, "MissingInputError"),
        }
    }
}

impl<E> Into<i32> for TapirError<E> {
    fn into(self) -> i32 {
        match self {
            BracketError => 2,
            MemPtrUnderflowError => 3,
            InputExceptionError(_) => 4,
            MissingInputError => 5,
            OutputError(_) => 6,
        }
    }
}

/// Runs a Brainfuck program to completion,
/// or produces an error in the form of a [`TapirError`] along with
/// the index into `program` of the last instruction executed.
/// 
/// ## Arguments
/// * `mem` - A buffer to use as the memory tape
/// * `program` - Brainfuck program text as bytes
/// * `input` - An iterator over bytes of "user" input,
/// read when [`interpret`] encounters a `,` instruction
/// * `output` - A [`Write`]able sink for program output,
/// written to when [`interpret`] encounters a `.` instruction
/// * `eof_retry` - Whether to repeatedly call `next` when
/// reading input fails, i.e. when `input.into_iter().next()` returns `None`
#[inline]
pub fn interpret<I, E, O>(
    mem: &mut Vec<u8>,
    program: &[u8],
    input: I,
    mut output: O,
    eof_retry: bool,
) -> Result<(), (TapirError<E>, usize)>
where
    I: IntoIterator<Item = Result<u8, E>>,
    O: Write,
{
    let mut mem_ptr: usize = 0;
    let mut ins_ptr: usize = 0;

    let mut last_match_left_arg = 0;
    let mut last_match_left_val = 0;
    let mut last_match_right_arg = usize::MAX;
    let mut last_match_right_val = 0;

    if mem.is_empty() {
        mem.push(0);
    } // ensure that mem_ptr starts at a valid cell

    let mut input = input.into_iter();

    while ins_ptr < program.len() {
        match program[ins_ptr] as char {
            '>' => {
                mem_ptr += 1;
                if mem_ptr == mem.len() {
                    mem.push(0);
                    mem.resize(mem.capacity(), 0);
                } else {
                    debug_assert!(mem_ptr < mem.len(), "if we somehow increment by > 1");
                }
            }
            '<' => {
                let new_mem_ptr = mem_ptr - 1;
                if new_mem_ptr > mem_ptr {
                    return Err((MemPtrUnderflowError, ins_ptr));
                }
                mem_ptr = new_mem_ptr;
            }
            '+' => mem[mem_ptr] += 1,
            '-' => mem[mem_ptr] -= 1,
            '.' => {
                print!("{}", mem[mem_ptr] as char);
            }
            ',' => {
                if let Err(e) = output.flush() {
                    return Err((OutputError(e), ins_ptr));
                }

                // I'll have to write some tests for this.
                // Retries getting input until it succeeds (or forever)
                // Pretend you didn't see this.
                let incoming_byte: u8 = match input.next() {
                    Some(Err(e)) => return Err((InputExceptionError(e), ins_ptr)),
                    Some(Ok(val)) => val,
                    None => {
                        if eof_retry {
                            match (|| loop {
                                match input.next() {
                                    Some(Ok(val)) => return Ok(val),
                                    Some(Err(e)) => return Err(InputExceptionError(e)),
                                    None => (),
                                }
                            })() {
                                Ok(val) => val,
                                Err(e) => return Err((e, ins_ptr)),
                            }
                        } else {
                            return Err((MissingInputError, ins_ptr));
                        }
                    }
                };

                mem[mem_ptr] = incoming_byte;
            }
            '[' => {
                if mem[mem_ptr] == 0 {
                    match match_right(ins_ptr, program, last_match_right_arg, last_match_right_val)
                    {
                        (0, _, _) => return Err((BracketError, ins_ptr)),
                        (n, lma, lmv) => {
                            ins_ptr = n;
                            last_match_right_arg = lma;
                            last_match_right_val = lmv;
                        }
                    }
                }
            }
            ']' => {
                if mem[mem_ptr] != 0 {
                    match match_left(ins_ptr, program, last_match_left_arg, last_match_left_val) {
                        (None, _, _) => return Err((BracketError, ins_ptr)),
                        (Some(n), lma, lmv) => {
                            ins_ptr = n;
                            last_match_left_arg = lma;
                            last_match_left_val = lmv;
                        }
                    }
                }
            }
            _ => {}
        }
        ins_ptr += 1;
    }

    if let Err(e) = output.flush() {
        return Err((OutputError(e), ins_ptr));
    }

    Ok(())
}