bf 0.4.8

An optimizing Brainfuck interpeter and JIT compiler
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

use super::*;
use ast;

/// Program forms that can be compiled to the RLE AST.
pub trait RleCompilable {
    /// Convert the given program to unoptimized AST to prepare for run-length encoding.
    fn with_ast<F, R>(&self, k: F) -> R
        where F: FnOnce(&ast::Program) -> R;

    /// Run-length encode the given program.
    fn rle_compile(&self) -> Box<Program> {
        self.with_ast(compile)
    }
}

/// Compiles an unoptimized [`ast`](../ast/index.html) program to a run-length encoded program.
pub fn compile(program: &ast::Program) -> Box<Program> {
    let mut compiler = Compiler::new();
    compiler.compile(program);
    compiler.into_program()
}

/// Represents the state of an RLE compiler from `ast::Instruction` to `Instruction`.
pub struct Compiler {
    instructions: Vec<Statement>,
    last_command: Command,
    last_repeat: Count,
}

impl Compiler {
    /// Creates a new RLE compiler.
    pub fn new() -> Self {
        Compiler {
            instructions: Vec::new(),
            last_command: Command::Right,
            last_repeat:  0,
        }
    }

    /// Compiles the given sequence of instructions.
    pub fn compile(&mut self, program: &[ast::Statement]) {
        for instruction in program {
            match *instruction {
                ast::Statement::Cmd(op_code) => self.issue_op(op_code),
                ast::Statement::Loop(ref body) => self.issue_loop(compile(body)),
            }
        }
    }

    /// Extracts the compiled program.
    pub fn into_program(mut self) -> Box<Program> {
        self.push_op();
        self.instructions.into_boxed_slice()
    }

    fn push_op(&mut self) {
        if self.last_repeat > 0 {
            self.instructions.push(Statement::Cmd(self.last_command, self.last_repeat));
            self.last_command = Command::Right;
            self.last_repeat = 0;
        }
    }

    fn issue_op(&mut self, cmd: Command) {
        if cmd == self.last_command {
            if let Some(last_repeat) = self.last_repeat.checked_add(1) {
                self.last_repeat = last_repeat;
            } else {
                self.push_op();
                self.last_repeat = 1;
            }
        } else {
            self.push_op();
            self.last_command = cmd;
            self.last_repeat = 1;
        }
    }

    fn issue_loop(&mut self, body: Box<Program>) {
        self.push_op();
        self.instructions.push(Statement::Loop(body));
    }
}


#[cfg(test)]
mod tests {
    use super::*;
    use ast::Statement as Src;
    use super::Statement as Obj;
    use super::Command::*;

    #[test]
    fn right_compiles() {
        assert_compile(&[Src::Cmd(Right)], &[Obj::Cmd(Right, 1)]);
    }

    #[test]
    fn three_rights_compile() {
        assert_compile(&[Src::Cmd(Right), Src::Cmd(Right), Src::Cmd(Right)],
                       &[Obj::Cmd(Right, 3)]);
    }

    #[test]
    fn two_rights_two_ups_compile() {
        assert_compile(&[Src::Cmd(Right), Src::Cmd(Right), Src::Cmd(Up), Src::Cmd(Up)],
                       &[Obj::Cmd(Right, 2), Obj::Cmd(Up, 2)]);
    }

    #[test]
    fn loop_compiles() {
        assert_compile(&[Src::Cmd(In), src_mk_loop(vec![Src::Cmd(Right)]), Src::Cmd(In)],
                       &[Obj::Cmd(In, 1), mk_loop(vec![Obj::Cmd(Right, 1)]), Obj::Cmd(In, 1)]);

    }

    fn assert_compile(src: &[ast::Statement], expected: &[Statement]) {
        let actual = compile(src);
        assert_eq!(&*actual, expected);
    }

    fn src_mk_loop(body: Vec<Src>) -> Src {
        Src::Loop(body.into_boxed_slice())
    }

    fn mk_loop(body: Vec<Statement>) -> Statement {
        Obj::Loop(body.into_boxed_slice())
    }
}

impl RleCompilable for ast::Program {
    fn with_ast<F, R>(&self, k: F) -> R
        where F: FnOnce(&ast::Program) -> R
    {
        k(self)
    }
}