path: root/bytecode/src/bytecode.rs

use crate::data::Value;
use crate::heap::Heap;

// The cute scheme virtual machine is a register based VM.
// There are 256 registers, also called locals.

#[derive(Debug, Eq, PartialEq, Clone, Copy)]
pub struct Local(pub u8);

#[derive(Debug, Eq, PartialEq, Clone, Copy)]
pub enum Arg {
    L(Local),
    Const(Value),
}

#[derive(Debug, Eq, PartialEq, Clone, Copy)]
pub enum Op {
    // Signed arithmetic
    // =================

    // Adds two integers.
    Add(Local, Arg, Arg),
    // Subtracts two integers.
    Sub(Local, Arg, Arg),
    // Multiplies two integers.
    Mul(Local, Arg, Arg),
    // Divides two integers and truncates the result.
    Div(Local, Arg, Arg),
    // Remainder from Div.
    Mod(Local, Arg, Arg),

    // Heap
    // ======

    // Allocates n words and returns the address.
    Alloc(Local, Arg),
    // Allocates n bytes and returns the address. The contents of this allocation will be treated
    // as raw data and not walked by the garbage collector.
    AllocBytevector(Local, Arg),
    // Fetches a 64 bit word from the specified address plus the
    // given offset.
    Peek(Local, Arg, Arg),
    // Stores a 64 bit word at the specified address plus the
    // given offset.
    Poke(Arg, Arg, Arg),
    // Fetches a byte from the specified address plus the given offset.
    PeekByte(Local, Arg, Arg),
    // Stores a byte at the specified address plus the given offset.
    PokeByte(Arg, Arg, Arg),

    // Locals
    // ======

    // Loads a value into a register.
    Mov(Local, Arg),

    // Control flow
    // ============

    // Jumps to the specified address.
    Jmp(Arg),
    // Jumps to the specified address if the argument is not false. Note: the first argument is the
    // condition and the second argument is the address.
    JmpIf(Arg, Arg),
    // Terminates the interpreter with the given status code.
    Exit(Arg),
}

struct Interpreter {
    locals: Vec<Value>,
    heap: Heap,
}

impl Interpreter {
    fn read_arg(&self, x: Arg) -> Value {
        match x {
            Arg::L(Local(i)) => self.locals[usize::from(i)],
            Arg::Const(c) => c,
        }
    }

    fn set_arg(&mut self, dest: Local, val: Value) {
        let Local(i) = dest;
        self.locals[usize::from(i)] = val;
    }

    fn add(&mut self, dest: Local, x: Arg, y: Arg) -> Result<(), String> {
        let n1 = self.read_arg(x).to_int()?;
        let n2 = self.read_arg(y).to_int()?;
        self.set_arg(dest, Value::from_int(n1.wrapping_add(n2)));
        Ok(())
    }

    fn sub(&mut self, dest: Local, x: Arg, y: Arg) -> Result<(), String> {
        let n1 = self.read_arg(x).to_int()?;
        let n2 = self.read_arg(y).to_int()?;
        self.set_arg(dest, Value::from_int(n1.wrapping_sub(n2)));
        Ok(())
    }

    fn mul(&mut self, dest: Local, x: Arg, y: Arg) -> Result<(), String> {
        let n1 = self.read_arg(x).to_int()?;
        let n2 = self.read_arg(y).to_int()?;
        self.set_arg(dest, Value::from_int(n1.wrapping_mul(n2)));
        Ok(())
    }

    fn div(&mut self, dest: Local, x: Arg, y: Arg) -> Result<(), String> {
        let n1 = self.read_arg(x).to_int()?;
        let n2 = self.read_arg(y).to_int()?;
        self.set_arg(dest, Value::from_int(n1.wrapping_div(n2)));
        Ok(())
    }

    fn fn_mod(&mut self, dest: Local, x: Arg, y: Arg) -> Result<(), String> {
        let n1 = self.read_arg(x).to_int()?;
        let n2 = self.read_arg(y).to_int()?;
        self.set_arg(dest, Value::from_int(n1.wrapping_rem(n2)));
        Ok(())
    }

    fn alloc(&mut self, dest: Local, size: Arg) -> Result<(), String> {
        let n = self.read_arg(size).to_int()?;
        if n < 0 {
            return Err(String::from("tried to allocate negative memory"));
        }
        let p = self
            .heap
            .alloc(usize::try_from(n).unwrap(), &mut self.locals)?;
        self.set_arg(dest, Value::from_pointer(p));
        Ok(())
    }

    fn alloc_bytevector(&mut self, dest: Local, size: Arg) -> Result<(), String> {
        let n = self.read_arg(size).to_int()?;
        if n < 0 {
            return Err(String::from("tried to allocate negative memory"));
        }
        let p = self
            .heap
            .alloc_bytevector(usize::try_from(n).unwrap(), &mut self.locals)?;
        self.set_arg(dest, Value::from_pointer(p));
        Ok(())
    }

    fn peek(&mut self, dest: Local, ptr: Arg, offset: Arg) -> Result<(), String> {
        let p = self.read_arg(ptr).to_pointer()?;
        let o = self.read_arg(offset).to_int()?;
        if o < 0 {
            return Err(String::from("pointer offset can't be negative"));
        }
        let result = self.heap.peek(p.offset(usize::try_from(o).unwrap()))?;
        self.set_arg(dest, result);
        Ok(())
    }

    fn poke(&mut self, word: Arg, ptr: Arg, offset: Arg) -> Result<(), String> {
        let w = self.read_arg(word);
        let p = self.read_arg(ptr).to_pointer()?;
        let o = self.read_arg(offset).to_int()?;
        if o < 0 {
            return Err(String::from("pointer offset can't be negative"));
        }
        self.heap.poke(w, p.offset(usize::try_from(o).unwrap()))?;
        Ok(())
    }

    fn peek_byte(&mut self, dest: Local, ptr: Arg, offset: Arg) -> Result<(), String> {
        let p = self.read_arg(ptr).to_pointer()?;
        let o = self.read_arg(offset).to_int()?;
        if o < 0 {
            return Err(String::from("pointer offset can't be negative"));
        }
        let result = self.heap.peek_byte(p.offset(usize::try_from(o).unwrap()))?;
        self.set_arg(dest, Value::from_int(i64::from(result)));
        Ok(())
    }

    fn poke_byte(&mut self, word: Arg, ptr: Arg, offset: Arg) -> Result<(), String> {
        let w = self.read_arg(word).to_int()?;
        let p = self.read_arg(ptr).to_pointer()?;
        let o = self.read_arg(offset).to_int()?;
        if o < 0 {
            return Err(String::from("pointer offset can't be negative"));
        }
        if !(0 <= w && w <= 0xff) {
            return Err(format!("value {} is not byte-sized", w));
        }
        self.heap.poke_byte(
            u8::try_from(w).unwrap(),
            p.offset(usize::try_from(o).unwrap()),
        )?;
        Ok(())
    }

    fn mov(&mut self, dest: Local, src: Arg) {
        self.set_arg(dest, self.read_arg(src));
    }

    fn jmp(&mut self, ip: &mut usize, addr: Arg) -> Result<(), String> {
        let a = self.read_arg(addr).to_int()?;
        if a < 0 {
            return Err(String::from("can't jump to a negative address"));
        }
        *ip = usize::try_from(a).unwrap();
        Ok(())
    }

    fn jmp_if(&mut self, ip: &mut usize, cond: Arg, addr: Arg) -> Result<(), String> {
        let c = self.read_arg(cond);
        let a = self.read_arg(addr).to_int()?;
        if a < 0 {
            return Err(String::from("can't jump to a negative address"));
        }
        if c != Value::from_bool(false) {
            *ip = usize::try_from(a).unwrap();
        }
        Ok(())
    }

    fn eval(&mut self, prog: &[Op]) -> Result<u8, String> {
        let mut ip = 0;
        loop {
            if ip >= prog.len() {
                return Err(String::from("invalid instruction pointer"));
            }
            let op = prog[ip];
            ip += 1;
            match op {
                Op::Add(dest, x, y) => self.add(dest, x, y)?,
                Op::Sub(dest, x, y) => self.sub(dest, x, y)?,
                Op::Mul(dest, x, y) => self.mul(dest, x, y)?,
                Op::Div(dest, x, y) => self.div(dest, x, y)?,
                Op::Mod(dest, x, y) => self.fn_mod(dest, x, y)?,
                Op::Alloc(dest, size) => self.alloc(dest, size)?,
                Op::AllocBytevector(dest, size) => self.alloc_bytevector(dest, size)?,
                Op::Peek(dest, ptr, offset) => self.peek(dest, ptr, offset)?,
                Op::Poke(word, ptr, offset) => self.poke(word, ptr, offset)?,
                Op::PeekByte(dest, ptr, offset) => self.peek_byte(dest, ptr, offset)?,
                Op::PokeByte(word, ptr, offset) => self.poke_byte(word, ptr, offset)?,
                Op::Mov(dest, src) => self.mov(dest, src),
                Op::Jmp(addr) => self.jmp(&mut ip, addr)?,
                Op::JmpIf(cond, addr) => self.jmp_if(&mut ip, cond, addr)?,
                Op::Exit(code) => {
                    let n = self.read_arg(code).to_int()?;
                    return Ok((n & 0xff) as u8);
                }
            }
        }
    }
}

pub fn eval(prog: &[Op]) -> Result<u8, String> {
    let mut interpreter = Interpreter {
        locals: vec![Value(0); 256],
        heap: Heap::new(),
    };
    interpreter.eval(prog)
}

#[cfg(test)]
mod tests {
    use super::Arg::*;
    use super::Op::*;
    use super::*;

    #[test]
    fn eval_const() {
        assert_eq!(Ok(5), eval(&vec![Exit(Const(Value::from_int(5)))]));
    }

    #[test]
    fn eval_add() {
        assert_eq!(
            Ok(10),
            eval(&vec![
                Add(
                    Local(0),
                    Const(Value::from_int(5)),
                    Const(Value::from_int(5))
                ),
                Exit(L(Local(0))),
            ])
        );
    }

    #[test]
    fn eval_sub() {
        assert_eq!(
            Ok(2),
            eval(&vec![
                Sub(
                    Local(0),
                    Const(Value::from_int(5)),
                    Const(Value::from_int(3))
                ),
                Exit(L(Local(0))),
            ])
        );
    }

    #[test]
    fn eval_mul() {
        assert_eq!(
            Ok(25),
            eval(&vec![
                Mul(
                    Local(0),
                    Const(Value::from_int(5)),
                    Const(Value::from_int(5))
                ),
                Exit(L(Local(0))),
            ])
        );
    }

    #[test]
    fn eval_div() {
        assert_eq!(
            Ok(2),
            eval(&vec![
                Div(
                    Local(0),
                    Const(Value::from_int(5)),
                    Const(Value::from_int(2))
                ),
                Exit(L(Local(0))),
            ])
        );
    }

    #[test]
    fn eval_mod() {
        assert_eq!(
            Ok(1),
            eval(&vec![
                Mod(
                    Local(0),
                    Const(Value::from_int(5)),
                    Const(Value::from_int(2))
                ),
                Exit(L(Local(0))),
            ])
        );
    }

    #[test]
    fn eval_alloc() {
        assert_eq!(
            Ok(0),
            eval(&vec![
                Alloc(Local(0), Const(Value::from_int(10))),
                Exit(Const(Value::from_int(0))),
            ])
        );
    }

    #[test]
    fn eval_bytevector() {
        assert_eq!(
            Ok(0),
            eval(&vec![
                AllocBytevector(Local(0), Const(Value::from_int(10))),
                Exit(Const(Value::from_int(0))),
            ])
        );
    }

    #[test]
    fn eval_peek() {
        assert_eq!(
            Ok(5),
            eval(&vec![
                Alloc(Local(0), Const(Value::from_int(1))),
                Poke(
                    Const(Value::from_int(5)),
                    L(Local(0)),
                    Const(Value::from_int(0))
                ),
                Peek(Local(1), L(Local(0)), Const(Value::from_int(0))),
                Exit(L(Local(1))),
            ])
        );
    }

    #[test]
    fn eval_poke() {
        assert_eq!(
            Ok(0),
            eval(&vec![
                Alloc(Local(0), Const(Value::from_int(1))),
                Poke(
                    Const(Value::from_int(5)),
                    L(Local(0)),
                    Const(Value::from_int(0))
                ),
                Exit(Const(Value::from_int(0))),
            ])
        );
    }

    #[test]
    fn eval_peek_byte() {
        assert_eq!(
            Ok(0),
            eval(&vec![
                AllocBytevector(Local(0), Const(Value::from_int(1))),
                PeekByte(Local(1), L(Local(0)), Const(Value::from_int(0))),
                Exit(L(Local(1))),
            ])
        );
    }

    #[test]
    fn eval_poke_byte() {
        assert_eq!(
            Ok(0),
            eval(&vec![
                AllocBytevector(Local(0), Const(Value::from_int(1))),
                PokeByte(
                    Const(Value::from_int(5)),
                    L(Local(0)),
                    Const(Value::from_int(0))
                ),
                Exit(Const(Value::from_int(0))),
            ])
        );
    }
}