brainstem 0.1.0

A Brainfuck compiler and interpreter library, with a BrainStem frontend language.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

/// Basic Brainfuck Operations.
#[derive(Debug, Copy, Clone)]
pub enum Op {
    /// Move the pointer to the right by n cells - corresponds to '>' and '<'.
    MovePointer(isize),
    /// Increment the value at the current cell by n - corresponds to '+' and '-'.
    Increment(i32),
    /// Jump to the instruction after the matching ']' if the current cell is zero - corresponds to '['.
    JumpIfZero(usize),
    /// Jump back to the instruction after the matching '[' if the current cell is not zero - corresponds to ']'.
    JumpBack(usize),
    /// Read a byte from the standard input and store it in the current cell - corresponds to ','.
    Read,
    /// Write the byte at the current cell to the standard output - corresponds to '.'.
    Write,
    /// Set the value at the current cell to zero - corresponds to '[-]'.
    SetToZero,
}

/// Compact the program by combining consecutive MovePointer and Increment operations.
fn compact(mut program: Vec<Op>) -> Vec<Op> {
    let mut compacted;
    while !program.is_empty() {
        compacted = Vec::new();
        let mut previous_op = program[0];
        for op in program.iter().skip(1) {
            match (previous_op, op) {
                (Op::MovePointer(n), Op::MovePointer(m)) => {
                    previous_op = Op::MovePointer(n + m);
                }
                (Op::Increment(n), Op::Increment(m)) => {
                    previous_op = Op::Increment(n + m);
                }
                _ => {
                    match previous_op {
                        Op::MovePointer(0) | Op::Increment(0) => (),
                        _ => compacted.push(previous_op),
                    }
                    previous_op = *op;
                }
            }
        }
        match previous_op {
            Op::MovePointer(0) | Op::Increment(0) => (),
            _ => compacted.push(previous_op),
        }
        if compacted.len() == program.len() {
            break;
        }
        program = compacted;
    }
    program
}

/// Find set to zero operations and replace them with SetToZero.
fn optimize_set_to_zero(mut program: Vec<Op>) -> Vec<Op> {
    let mut i = 0;
    while i + 2 < program.len() {
        match program[i..i + 3] {
            [Op::JumpIfZero(_), Op::Increment(-1), Op::JumpBack(_)] => {
                program[i] = Op::SetToZero;
                program.remove(i + 1);
                program.remove(i + 1);
            }
            _ => i += 1,
        }
    }
    // Remove any Increment operations that are followed by SetToZero.
    i = 0;
    while i + 1 < program.len() {
        match program[i..i + 2] {
            [Op::Increment(_), Op::SetToZero] => {
                program[i] = Op::SetToZero;
                program.remove(i + 1);
            }
            _ => i += 1,
        }
    }
    program
}

/// Match jumps and populates the JumpIfNotZero and JumpBack operations.
fn match_jumps(mut program: Vec<Op>) -> Result<Vec<Op>, &'static str> {
    let mut jumps = Vec::new();
    for i in 0..program.len() {
        match program[i] {
            Op::JumpIfZero(_) => jumps.push(i),
            Op::JumpBack(_) => {
                if jumps.is_empty() {
                    return Err("Unmatched ']'");
                }
                let jz = jumps.pop().unwrap();
                program[jz] = Op::JumpIfZero(i + 1);
                program[i] = Op::JumpBack(jz);
            }
            _ => (),
        }
    }
    if jumps.is_empty() {
        Ok(program)
    } else {
        Err("Unmatched '['")
    }
}

/// Finalize the program by compacting, optimizing set to zero, and matching jumps.
pub fn finalize(program: Vec<Op>) -> Result<Vec<Op>, &'static str> {
    let program = compact(program);
    let program = optimize_set_to_zero(program);
    match_jumps(program)
}