nostd-brainfuck.rs

#[derive(Copy, Clone)]
enum LinkedList<'a> {
    Nil,
    Cons(u8, &'a LinkedList<'a>),
}

struct LinkedListIter<'a> {
    list: LinkedList<'a>,
}

impl<'a> Iterator for LinkedListIter<'a> {
    type Item = u8;
    fn next(&mut self) -> Option<u8> {
        match self.list {
            LinkedList::Nil => None,
            LinkedList::Cons(v, l) => {
                self.list = *l;
                Some(v)
            }
        }
    }
}

impl<'a> core::fmt::Debug for LinkedList<'a> {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_list().entries(self.iter()).finish()
    }
}

impl<'a> Default for LinkedList<'a> {
    fn default() -> LinkedList<'a> {
        LinkedList::Nil
    }
}

impl<'a> LinkedList<'a> {
    fn pop(self) -> (u8, LinkedList<'a>) {
        match self {
            LinkedList::Nil => (0, LinkedList::Nil),
            LinkedList::Cons(x, xs) => (x, *xs),
        }
    }

    fn push<F>(self, value: u8, f: F)
    where
        for<'b> F: FnOnce(LinkedList<'b>),
    {
        f(LinkedList::Cons(value, &self))
    }

    fn iter(self) -> LinkedListIter<'a> {
        LinkedListIter { list: self }
    }
}

#[derive(Copy, Clone, Default, Debug)]
struct Brainfuck<'a> {
    left: LinkedList<'a>,
    cur: u8,
    right: LinkedList<'a>,
    program: &'a [u8],
    pc: usize,
    output: LinkedList<'a>,
}

impl<'a> Brainfuck<'a> {
    fn inc_ptr<F>(self, f: F)
    where
        for<'b> F: FnOnce(Brainfuck<'b>),
    {
        self.left.push(self.cur, move |left| {
            let (cur, right) = self.right.pop();
            f(Brainfuck {
                left,
                right,
                cur,
                program: self.program,
                pc: self.pc,
                output: self.output,
            })
        })
    }

    fn dec_ptr<F>(self, f: F)
    where
        for<'b> F: FnOnce(Brainfuck<'b>),
    {
        self.right.push(self.cur, move |right| {
            let (cur, left) = self.left.pop();
            f(Brainfuck {
                left,
                right,
                cur,
                program: self.program,
                pc: self.pc,
                output: self.output,
            })
        })
    }

    fn output<F>(self, f: F)
    where
        for<'b> F: FnOnce(Brainfuck<'b>),
    {
        self.output.push(self.cur, move |output| {
            f(Brainfuck {
                left: self.left,
                right: self.right,
                cur: self.cur,
                program: self.program,
                pc: self.pc,
                output,
            })
        })
    }

    fn interpret(mut self) {
        'outer: while let Some(instruction) = self.program.get(self.pc).cloned() {
            self.pc += 1;
            match instruction {
                b'>' => return self.inc_ptr(|b| b.interpret()),
                b'<' => return self.dec_ptr(|b| b.interpret()),
                b'+' => self.cur = self.cur.wrapping_add(1),
                b'-' => self.cur = self.cur.wrapping_sub(1),
                b'.' => return self.output(|b| b.interpret()),
                b'[' => {
                    if self.cur == 0 {
                        let mut nesting_level = 1u64;
                        while nesting_level != 0 {
                            match self.program.get(self.pc).cloned() {
                                Some(b'[') => nesting_level += 1,
                                Some(b']') => nesting_level -= 1,
                                Some(_) => (),
                                None => break 'outer,
                            }
                            self.pc += 1;
                        }
                    }
                }
                b']' => {
                    if self.cur != 0 {
                        let mut nesting_level = 1u64;
                        self.pc = self.pc.wrapping_sub(1);
                        while nesting_level != 0 {
                            self.pc = self.pc.wrapping_sub(1);
                            match self.program.get(self.pc).cloned() {
                                Some(b']') => nesting_level += 1,
                                Some(b'[') => nesting_level -= 1,
                                Some(_) => (),
                                None => break 'outer,
                            }
                        }
                    }
                }
                _ => (),
            }
        }
        let mut output: Vec<u8> = self.output.iter().collect();
        output.reverse();
        print!("{}", core::str::from_utf8(&output).unwrap());
    }
}

fn main() {
    let mut b = Brainfuck::default();
    b.program = b"++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
";
    b.interpret();
}