Construindo um compilador e uma máquina virtual do zero em Rust

[workspace]
members = ["cadencia", "mini-vm"]
resolver = "2"

[package]
name = "cadencia"
version = "0.1.0"
edition = "2021"

[dependencies]
pulso = { path = "../../pulso" }

pub const MAGIC: &[u8; 4] = b"PBC1";
pub const VERSION: u16 = 1;

#[derive(Debug, Clone, PartialEq)]
pub enum Constant {
    Number(f64),
    Text(String),
}

#[derive(Debug, Clone, PartialEq)]
pub struct Function {
    pub name: String,
    pub arity: u16,
    pub local_count: u16,
    pub code: Vec<u8>,
}

#[derive(Debug, Clone, PartialEq)]
pub struct Program {
    pub constants: Vec<Constant>,
    pub globals: u16,
    pub functions: Vec<Function>,
}

#[repr(u8)]
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum OpCode {
    Constant = 1,
    True = 2,
    False = 3,
    Nil = 4,
    Add = 5,
    Subtract = 6,
    Multiply = 7,
    Divide = 8,
    Equal = 9,
    Greater = 10,
    Less = 11,
    Not = 12,
    Negate = 13,
    Print = 14,
    Pop = 15,
    LoadGlobal = 16,
    StoreGlobal = 17,
    LoadLocal = 18,
    StoreLocal = 19,
    JumpIfFalse = 20,
    Jump = 21,
    Call = 22,
    Return = 23,
    And = 24,
    Or = 25,
    Halt = 26,
}

impl TryFrom<u8> for OpCode {
    type Error = String;

    fn try_from(value: u8) -> Result<Self, Self::Error> {
        use OpCode::*;
        Ok(match value {
            1 => Constant, 2 => True, 3 => False, 4 => Nil, 5 => Add,
            6 => Subtract, 7 => Multiply, 8 => Divide, 9 => Equal,
            10 => Greater, 11 => Less, 12 => Not, 13 => Negate,
            14 => Print, 15 => Pop, 16 => LoadGlobal, 17 => StoreGlobal,
            18 => LoadLocal, 19 => StoreLocal, 20 => JumpIfFalse,
            21 => Jump, 22 => Call, 23 => Return, 24 => And, 25 => Or, 26 => Halt,
            other => return Err(format!("opcode desconhecido: {other}")),
        })
    }
}

use std::collections::BTreeMap;
use pulso::ast::{BinaryOp, Expr, FunctionDecl, Program as AstProgram, Stmt, UnaryOp};
use crate::bytecode::{Constant, Function, OpCode, Program};

pub struct Compiler {
    constants: Vec<Constant>,
    globals: BTreeMap<String, u16>,
    function_ids: BTreeMap<String, u16>,
}

struct FunctionCompiler {
    code: Vec<u8>,
    locals: BTreeMap<String, u16>,
}

impl Compiler {
    pub fn compile(ast: &AstProgram) -> Result<Program, String> {
        let mut compiler = Self {
            constants: Vec::new(), globals: BTreeMap::new(), function_ids: BTreeMap::new()
        };
        let declarations: Vec<_> = ast.statements.iter().filter_map(|stmt| {
            if let Stmt::Function(function) = stmt { Some(function.clone()) } else { None }
        }).collect();
        compiler.function_ids.insert("<main>".into(), 0);
        for function in &declarations {
            let id = compiler.function_ids.len() as u16;
            compiler.function_ids.insert(function.name.clone(), id);
        }
        let mut functions = vec![compiler.compile_main(ast)?];
        for function in &declarations { functions.push(compiler.compile_function(function)?); }
        Ok(Program { constants: compiler.constants, globals: compiler.globals.len() as u16, functions })
    }

    fn compile_main(&mut self, ast: &AstProgram) -> Result<Function, String> {
        let mut fc = FunctionCompiler { code: Vec::new(), locals: BTreeMap::new() };
        for stmt in &ast.statements {
            if !matches!(stmt, Stmt::Function(_)) { self.statement(stmt, &mut fc, true)?; }
        }
        emit(&mut fc.code, OpCode::Halt);
        Ok(Function { name: "<main>".into(), arity: 0, local_count: 0, code: fc.code })
    }

    fn compile_function(&mut self, function: &FunctionDecl) -> Result<Function, String> {
        let mut fc = FunctionCompiler { code: Vec::new(), locals: BTreeMap::new() };
        for parameter in &function.parameters {
            let slot = fc.locals.len() as u16;
            fc.locals.insert(parameter.clone(), slot);
        }
        for stmt in &function.body { self.statement(stmt, &mut fc, false)?; }
        emit(&mut fc.code, OpCode::Nil);
        emit(&mut fc.code, OpCode::Return);
        Ok(Function {
            name: function.name.clone(),
            arity: function.parameters.len() as u16,
            local_count: fc.locals.len() as u16,
            code: fc.code,
        })
    }

    fn statement(&mut self, stmt: &Stmt, fc: &mut FunctionCompiler, global: bool) -> Result<(), String> {
        match stmt {
            Stmt::Var { name, initializer } => {
                self.expression(initializer, fc)?;
                let slot = if global {
                    slot_for(&mut self.globals, name)
                } else {
                    slot_for(&mut fc.locals, name)
                };
                emit_u16(&mut fc.code, if global { OpCode::StoreGlobal } else { OpCode::StoreLocal }, slot);
            }
            Stmt::Assign { name, value } => {
                self.expression(value, fc)?;
                if let Some(slot) = fc.locals.get(name) {
                    emit_u16(&mut fc.code, OpCode::StoreLocal, *slot);
                } else {
                    let slot = slot_for(&mut self.globals, name);
                    emit_u16(&mut fc.code, OpCode::StoreGlobal, slot);
                }
            }
            Stmt::Print(expr) => { self.expression(expr, fc)?; emit(&mut fc.code, OpCode::Print); }
            Stmt::Expression(expr) => { self.expression(expr, fc)?; emit(&mut fc.code, OpCode::Pop); }
            Stmt::Block(statements) => for stmt in statements { self.statement(stmt, fc, global)?; },
            Stmt::If { condition, then_branch, else_branch } => {
                self.expression(condition, fc)?;
                let jump_false = emit_jump(&mut fc.code, OpCode::JumpIfFalse);
                self.statement(then_branch, fc, global)?;
                let jump_end = emit_jump(&mut fc.code, OpCode::Jump);
                patch_jump(&mut fc.code, jump_false);
                if let Some(other) = else_branch { self.statement(other, fc, global)?; }
                patch_jump(&mut fc.code, jump_end);
            }
            Stmt::While { condition, body } => {
                let start = fc.code.len() as u32;
                self.expression(condition, fc)?;
                let exit = emit_jump(&mut fc.code, OpCode::JumpIfFalse);
                self.statement(body, fc, global)?;
                emit_u32(&mut fc.code, OpCode::Jump, start);
                patch_jump(&mut fc.code, exit);
            }
            Stmt::Return(value) => {
                if let Some(value) = value { self.expression(value, fc)?; } else { emit(&mut fc.code, OpCode::Nil); }
                emit(&mut fc.code, OpCode::Return);
            }
            Stmt::Function(_) => {}
        }
        Ok(())
    }

    fn expression(&mut self, expr: &Expr, fc: &mut FunctionCompiler) -> Result<(), String> {
        match expr {
            Expr::Number(value) => { let id = self.constant(Constant::Number(*value)); emit_u16(&mut fc.code, OpCode::Constant, id); }
            Expr::String(value) => { let id = self.constant(Constant::Text(value.clone())); emit_u16(&mut fc.code, OpCode::Constant, id); }
            Expr::Bool(true) => emit(&mut fc.code, OpCode::True),
            Expr::Bool(false) => emit(&mut fc.code, OpCode::False),
            Expr::Variable(name) => {
                if let Some(slot) = fc.locals.get(name) { emit_u16(&mut fc.code, OpCode::LoadLocal, *slot); }
                else if let Some(slot) = self.globals.get(name) { emit_u16(&mut fc.code, OpCode::LoadGlobal, *slot); }
                else { return Err(format!("variável não declarada: {name}")); }
            }
            Expr::Unary { operator, right } => {
                self.expression(right, fc)?;
                emit(&mut fc.code, match operator { UnaryOp::Negate => OpCode::Negate, UnaryOp::Not => OpCode::Not });
            }
            Expr::Binary { left, operator, right } => {
                self.expression(left, fc)?;
                self.expression(right, fc)?;
                emit(&mut fc.code, match operator {
                    BinaryOp::Add => OpCode::Add, BinaryOp::Subtract => OpCode::Subtract,
                    BinaryOp::Multiply => OpCode::Multiply, BinaryOp::Divide => OpCode::Divide,
                    BinaryOp::Equal => OpCode::Equal,
                    BinaryOp::NotEqual => { emit(&mut fc.code, OpCode::Equal); OpCode::Not },
                    BinaryOp::Greater => OpCode::Greater,
                    BinaryOp::Less => OpCode::Less,
                    BinaryOp::GreaterEqual => { emit(&mut fc.code, OpCode::Less); OpCode::Not },
                    BinaryOp::LessEqual => { emit(&mut fc.code, OpCode::Greater); OpCode::Not },
                    BinaryOp::And => OpCode::And,
                    BinaryOp::Or => OpCode::Or,
                });
            }
            Expr::Call { name, arguments } => {
                for argument in arguments { self.expression(argument, fc)?; }
                let function = *self.function_ids.get(name).ok_or_else(|| format!("função desconhecida: {name}"))?;
                emit(&mut fc.code, OpCode::Call);
                fc.code.extend(function.to_le_bytes());
                fc.code.push(arguments.len() as u8);
            }
        }
        Ok(())
    }

    fn constant(&mut self, value: Constant) -> u16 {
        if let Some(index) = self.constants.iter().position(|item| item == &value) { return index as u16; }
        self.constants.push(value);
        (self.constants.len() - 1) as u16
    }
}

fn slot_for(map: &mut BTreeMap<String, u16>, name: &str) -> u16 {
    if let Some(slot) = map.get(name) { *slot } else {
        let slot = map.len() as u16; map.insert(name.into(), slot); slot
    }
}
fn emit(code: &mut Vec<u8>, op: OpCode) { code.push(op as u8); }
fn emit_u16(code: &mut Vec<u8>, op: OpCode, value: u16) { emit(code, op); code.extend(value.to_le_bytes()); }
fn emit_u32(code: &mut Vec<u8>, op: OpCode, value: u32) { emit(code, op); code.extend(value.to_le_bytes()); }
fn emit_jump(code: &mut Vec<u8>, op: OpCode) -> usize { emit(code, op); let at = code.len(); code.extend(0u32.to_le_bytes()); at }
fn patch_jump(code: &mut [u8], at: usize) { let target = code.len() as u32; code[at..at + 4].copy_from_slice(&target.to_le_bytes()); }

use crate::bytecode::{Constant, Function, Program, MAGIC, VERSION};

fn put_u16(out: &mut Vec<u8>, value: u16) { out.extend(value.to_le_bytes()); }
fn put_u32(out: &mut Vec<u8>, value: u32) { out.extend(value.to_le_bytes()); }
fn put_text(out: &mut Vec<u8>, text: &str) {
    put_u32(out, text.len() as u32);
    out.extend(text.as_bytes());
}

pub fn encode(program: &Program) -> Vec<u8> {
    let mut out = Vec::new();
    out.extend(MAGIC);
    put_u16(&mut out, VERSION);
    put_u16(&mut out, program.globals);
    put_u32(&mut out, program.constants.len() as u32);
    for constant in &program.constants {
        match constant {
            Constant::Number(value) => { out.push(1); out.extend(value.to_le_bytes()); }
            Constant::Text(value) => { out.push(2); put_text(&mut out, value); }
        }
    }
    put_u16(&mut out, program.functions.len() as u16);
    for function in &program.functions {
        put_text(&mut out, &function.name);
        put_u16(&mut out, function.arity);
        put_u16(&mut out, function.local_count);
        put_u32(&mut out, function.code.len() as u32);
        out.extend(&function.code);
    }
    out
}

struct Reader<'a> { bytes: &'a [u8], at: usize }
impl<'a> Reader<'a> {
    fn take(&mut self, n: usize) -> Result<&'a [u8], String> {
        let end = self.at.checked_add(n).ok_or("tamanho inválido")?;
        let value = self.bytes.get(self.at..end).ok_or("arquivo PBC truncado")?;
        self.at = end; Ok(value)
    }
    fn u16(&mut self) -> Result<u16, String> {
        Ok(u16::from_le_bytes(self.take(2)?.try_into().unwrap()))
    }
    fn u32(&mut self) -> Result<u32, String> {
        Ok(u32::from_le_bytes(self.take(4)?.try_into().unwrap()))
    }
    fn text(&mut self) -> Result<String, String> {
        let len = self.u32()? as usize;
        String::from_utf8(self.take(len)?.to_vec()).map_err(|_| "texto UTF-8 inválido".into())
    }
}

pub fn decode(bytes: &[u8]) -> Result<Program, String> {
    let mut r = Reader { bytes, at: 0 };
    if r.take(4)? != MAGIC { return Err("magic bytes não são PBC1".into()); }
    if r.u16()? != VERSION { return Err("versão PBC incompatível".into()); }
    let globals = r.u16()?;
    let mut constants = Vec::new();
    for _ in 0..r.u32()? {
        constants.push(match r.take(1)?[0] {
            1 => Constant::Number(f64::from_le_bytes(r.take(8)?.try_into().unwrap())),
            2 => Constant::Text(r.text()?),
            tag => return Err(format!("constante desconhecida: {tag}")),
        });
    }
    let mut functions = Vec::new();
    for _ in 0..r.u16()? {
        let name = r.text()?;
        let arity = r.u16()?;
        let local_count = r.u16()?;
        let code_len = r.u32()? as usize;
        functions.push(Function { name, arity, local_count, code: r.take(code_len)?.to_vec() });
    }
    if r.at != bytes.len() { return Err("bytes extras após o programa".into()); }
    Ok(Program { constants, globals, functions })
}

use std::{env, fs};
use cadencia::{encode, Compiler};
use pulso::{lexer::Lexer, parser::Parser};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let source_path = env::args().nth(1).ok_or("uso: cadencia arquivo.pulso [saida.pbc]")?;
    let output_path = env::args().nth(2).unwrap_or_else(|| "program.pbc".into());
    let source = fs::read_to_string(source_path)?;
    let tokens = Lexer::new(&source).scan()?;
    let ast = Parser::new(tokens).parse()?;
    let program = Compiler::compile(&ast)?;
    fs::write(&output_path, encode(&program))?;
    println!("bytecode salvo em {output_path}");
    Ok(())
}

[package]
name = "mini-vm"
version = "0.1.0"
edition = "2021"

[dependencies]
cadencia = { path = "../cadencia" }

use cadencia::{Constant, OpCode, Program};

#[derive(Debug, Clone, PartialEq)]
pub enum Value { Number(f64), Text(String), Bool(bool), Nil }

struct Frame { function: usize, ip: usize, locals: Vec<Value> }

pub struct Vm {
    program: Program,
    stack: Vec<Value>,
    globals: Vec<Value>,
    frames: Vec<Frame>,
    output: Vec<String>,
}

impl Vm {
    pub fn new(program: Program) -> Self {
        let globals = vec![Value::Nil; program.globals as usize];
        let main_locals = program.functions[0].local_count as usize;
        Self {
            program, stack: Vec::new(), globals,
            frames: vec![Frame { function: 0, ip: 0, locals: vec![Value::Nil; main_locals] }],
            output: Vec::new(),
        }
    }

    pub fn run(mut self) -> Result<Vec<String>, String> {
        loop {
            let byte = self.read_u8()?;
            match OpCode::try_from(byte)? {
                OpCode::Constant => {
                    let id = self.read_u16()? as usize;
                    let value = match self.program.constants.get(id).ok_or("constante inexistente")? {
                        Constant::Number(value) => Value::Number(*value),
                        Constant::Text(value) => Value::Text(value.clone()),
                    };
                    self.stack.push(value);
                }
                OpCode::True => self.stack.push(Value::Bool(true)),
                OpCode::False => self.stack.push(Value::Bool(false)),
                OpCode::Nil => self.stack.push(Value::Nil),
                OpCode::Add => self.binary(|a, b| match (a, b) {
                    (Value::Number(a), Value::Number(b)) => Ok(Value::Number(a + b)),
                    (Value::Text(a), Value::Text(b)) => Ok(Value::Text(a + &b)),
                    _ => Err("soma exige dois números ou dois textos".into()),
                })?,
                OpCode::Subtract => self.numbers(|a, b| a - b)?,
                OpCode::Multiply => self.numbers(|a, b| a * b)?,
                OpCode::Divide => self.numbers(|a, b| a / b)?,
                OpCode::Equal => self.binary(|a, b| Ok(Value::Bool(a == b)))?,
                OpCode::Greater => self.compare(|a, b| a > b)?,
                OpCode::Less => self.compare(|a, b| a < b)?,
                OpCode::Not => { let value = self.pop()?; self.stack.push(Value::Bool(!truthy(&value))); }
                OpCode::And => self.binary(|a, b| Ok(Value::Bool(truthy(&a) && truthy(&b))))?,
                OpCode::Or => self.binary(|a, b| Ok(Value::Bool(truthy(&a) || truthy(&b))))?,
                OpCode::Negate => { let Value::Number(value) = self.pop()? else { return Err("negação exige número".into()) }; self.stack.push(Value::Number(-value)); }
                OpCode::Print => { let text = display(&self.pop()?); println!("{text}"); self.output.push(text); }
                OpCode::Pop => { self.pop()?; }
                OpCode::LoadGlobal => { let slot = self.read_u16()? as usize; self.stack.push(self.globals.get(slot).ok_or("global inválida")?.clone()); }
                OpCode::StoreGlobal => { let slot = self.read_u16()? as usize; self.globals[slot] = self.pop()?; }
                OpCode::LoadLocal => { let slot = self.read_u16()? as usize; let value = self.frame()?.locals.get(slot).ok_or("local inválida")?.clone(); self.stack.push(value); }
                OpCode::StoreLocal => { let slot = self.read_u16()? as usize; let value = self.pop()?; self.frame_mut()?.locals[slot] = value; }
                OpCode::JumpIfFalse => { let target = self.read_u32()? as usize; if !truthy(self.stack.last().ok_or("stack vazia")?) { self.frame_mut()?.ip = target; } self.pop()?; }
                OpCode::Jump => { let target = self.read_u32()? as usize; self.frame_mut()?.ip = target; }
                OpCode::Call => {
                    let function = self.read_u16()? as usize;
                    let argc = self.read_u8()? as usize;
                    let meta = self.program.functions.get(function).ok_or("função inválida")?;
                    if argc != meta.arity as usize { return Err("quantidade de argumentos incorreta".into()); }
                    let mut locals = vec![Value::Nil; meta.local_count as usize];
                    for slot in (0..argc).rev() { locals[slot] = self.pop()?; }
                    self.frames.push(Frame { function, ip: 0, locals });
                }
                OpCode::Return => {
                    let value = self.pop()?;
                    self.frames.pop();
                    if self.frames.is_empty() { return Ok(self.output); }
                    self.stack.push(value);
                }
                OpCode::Halt => return Ok(self.output),
            }
        }
    }

    fn frame(&self) -> Result<&Frame, String> { self.frames.last().ok_or("sem frame".into()) }
    fn frame_mut(&mut self) -> Result<&mut Frame, String> { self.frames.last_mut().ok_or("sem frame".into()) }
    fn read_u8(&mut self) -> Result<u8, String> {
        let frame = self.frame_mut()?;
        let function = frame.function;
        let ip = frame.ip;
        frame.ip += 1;
        self.program.functions[function].code.get(ip).copied().ok_or("fim inesperado".into())
    }
    fn read_u16(&mut self) -> Result<u16, String> { Ok(u16::from_le_bytes([self.read_u8()?, self.read_u8()?])) }
    fn read_u32(&mut self) -> Result<u32, String> { Ok(u32::from_le_bytes([self.read_u8()?, self.read_u8()?, self.read_u8()?, self.read_u8()?])) }
    fn pop(&mut self) -> Result<Value, String> { self.stack.pop().ok_or("stack vazia".into()) }
    fn binary(&mut self, operation: impl Fn(Value, Value) -> Result<Value, String>) -> Result<(), String> {
        let right = self.pop()?; let left = self.pop()?; self.stack.push(operation(left, right)?); Ok(())
    }
    fn numbers(&mut self, operation: impl Fn(f64, f64) -> f64) -> Result<(), String> {
        self.binary(|a, b| match (a, b) { (Value::Number(a), Value::Number(b)) => Ok(Value::Number(operation(a, b))), _ => Err("operação exige números".into()) })
    }
    fn compare(&mut self, operation: impl Fn(f64, f64) -> bool) -> Result<(), String> {
        self.binary(|a, b| match (a, b) { (Value::Number(a), Value::Number(b)) => Ok(Value::Bool(operation(a, b))), _ => Err("comparação exige números".into()) })
    }
}

fn truthy(value: &Value) -> bool { !matches!(value, Value::Bool(false) | Value::Nil) }
fn display(value: &Value) -> String {
    match value {
        Value::Number(value) if value.fract() == 0.0 => format!("{value:.0}"),
        Value::Number(value) => value.to_string(),
        Value::Text(value) => value.clone(),
        Value::Bool(value) => value.to_string(),
        Value::Nil => "nulo".into(),
    }
}

use std::{env, fs};
use cadencia::decode;
use mini_vm::Vm;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let path = env::args().nth(1).ok_or("uso: mini-vm program.pbc")?;
    let bytes = fs::read(path)?;
    let program = decode(&bytes)?;
    Vm::new(program).run()?;
    Ok(())
}

funcao dobro(numero) {
    retorne numero * 2;
}

var resposta = dobro(21);
mostre("Pulso compilada:");
mostre(resposta);

# Pulso Bytecode

Continuação direta do projeto Pulso. O lexer, os tokens, o parser e a AST vêm do
projeto `../pulso`. A **Cadência** transforma a AST em um arquivo PBC1 e o
`mini-vm` executa esse arquivo.

```bash
cargo run -p cadencia -- examples/programa.pulso program.pbc
cargo run -p mini-vm -- program.pbc
```