brainfuck/
brainfuck.rs

1//! Brainfuck interpreter written in Rust, using Logos.
2//!
3//! Usage:
4//!     cargo run --example brainfuck <path/to/file>
5//!
6//! Example:
7//!     cargo run --example brainfuck examples/hello_word.bf
8//!
9//! Brainfuck is an esoteric programming language that only
10//! uses 8 single-character commands:
11//! - '>';
12//! - '<';
13//! - '+';
14//! - '-';
15//! - '.';
16//! - ',';
17//! - '[';
18//! - and ']'.
19//!
20//! Despite being very hard to use in practice, this makes
21//! this language very simple to interpret. The following code
22//! defines an [`execute`] function that runs Brainfuck code.
23//!
24//! Logos is used here to directly transform the code stream
25//! into meaningful `Op` operations (or commands).
26//! Errors, i.e., unknown tokens, are discarded using `filter_map`.
27//!
28//! More details can be found on Wikipedia:
29//! <https://en.wikipedia.org/wiki/Brainfuck>.
30//!
31//! or on <http://brainfuck.org/>.
32
33/* ANCHOR: all */
34use logos::Logos;
35use std::collections::HashMap;
36use std::env;
37use std::fs;
38use std::io::{self, Read};
39
40/* ANCHOR: tokens */
41/// Each [`Op`] variant is a single character.
42#[derive(Debug, Logos)]
43// skip all non-op characters
44#[logos(skip(".|\n", priority = 0))]
45enum Op {
46    /// Increment pointer.
47    #[token(">")]
48    IncPointer,
49    /// Decrement pointer.
50    #[token("<")]
51    DecPointer,
52    /// Increment data at pointer.
53    #[token("+")]
54    IncData,
55    /// Decrement data at pointer.
56    #[token("-")]
57    DecData,
58    /// Output data at pointer.
59    #[token(".")]
60    OutData,
61    /// Input (read) to data at pointer.
62    #[token(",")]
63    InpData,
64    /// Conditionally jump to matching `']'`.
65    #[token("[")]
66    CondJumpForward,
67    /// Conditionally jump to matching `'['`.
68    #[token("]")]
69    CondJumpBackward,
70}
71/* ANCHOR_END: tokens */
72
73/// Print one byte to the terminal.
74#[inline(always)]
75fn print_byte(byte: u8) {
76    print!("{}", byte as char);
77}
78
79/// Read one byte from the terminal.
80#[inline(always)]
81fn read_byte() -> u8 {
82    let mut input = [0u8; 1];
83    io::stdin()
84        .read_exact(&mut input)
85        .expect("An error occurred while reading byte!");
86    input[0]
87}
88
89/// Execute Brainfuck code from a string slice.
90pub fn execute(code: &str) {
91    let operations: Vec<_> = Op::lexer(code).collect::<Result<_, _>>().unwrap();
92    let mut data = [0u8; 30_000]; // Minimum recommended size
93    let mut pointer: usize = 0;
94    let len = operations.len();
95
96    // We pre-process matching jump commands, and we create
97    // a mapping between them.
98    let mut queue = Vec::new();
99    let mut pairs = HashMap::new();
100    let mut pairs_reverse = HashMap::new();
101
102    for (i, op) in operations.iter().enumerate() {
103        match op {
104            Op::CondJumpForward => queue.push(i),
105            Op::CondJumpBackward => {
106                if let Some(start) = queue.pop() {
107                    pairs.insert(start, i);
108                    pairs_reverse.insert(i, start);
109                } else {
110                    panic!(
111                        "Unexpected conditional backward jump at position {}, does not match any '['",
112                        i
113                    );
114                }
115            }
116            _ => (),
117        }
118    }
119
120    if !queue.is_empty() {
121        panic!("Unmatched conditional forward jump at positions {:?}, expecting a closing ']' for each of them", queue);
122    }
123
124    /* ANCHOR: fsm */
125    let mut i: usize = 0;
126    // True program execution.
127    loop {
128        match operations[i] {
129            Op::IncPointer => pointer += 1,
130            Op::DecPointer => pointer -= 1,
131            Op::IncData => data[pointer] = data[pointer].wrapping_add(1),
132            Op::DecData => data[pointer] = data[pointer].wrapping_sub(1),
133            Op::OutData => print_byte(data[pointer]),
134            Op::InpData => data[pointer] = read_byte(),
135            Op::CondJumpForward => {
136                if data[pointer] == 0 {
137                    // Skip until matching end.
138                    i = *pairs.get(&i).unwrap();
139                }
140            }
141            Op::CondJumpBackward => {
142                if data[pointer] != 0 {
143                    // Go back to matching start.
144                    i = *pairs_reverse.get(&i).unwrap();
145                }
146            }
147        }
148        i += 1;
149
150        if i >= len {
151            break;
152        }
153    }
154    /* ANCHOR_END: fsm */
155}
156
157fn main() {
158    let src = fs::read_to_string(env::args().nth(1).expect("Expected file argument"))
159        .expect("Failed to read file");
160
161    execute(src.as_str());
162}
163/* ANCHOR_END: all */
brainfuck/brainfuck.rs

brainfuck/
brainfuck.rs
