152. A Pratt compiler in Rust, part 2

Closures that share

The TypeScript compiler from chapter 48 is one function, compile. It declares its state as local variables, and every helper is a closure over them (trimmed):

let current = { type: 'eof', ... };
let previous = current;
let hadError = false;
function advance() {
  previous = current;
  current = scanner.scanToken();
}
const number = () =>
  emitConstant(Number(previous.lexeme));

Dozens of helpers read and write the same few variables, and call each other freely, even recursively: expression calls parsePrecedence, which calls binary, which calls parsePrecedence again. clox does the same with global variables^[1].

Try it in Rust with two closures:

let mut pos = 0;
let mut code = Vec::new();
let mut advance = || pos += 1;
let mut number = || {
    code.push(bytes[pos]);
    advance();
};

rustc 1.97 (trimmed):

error[E0502]: cannot borrow `pos` as
  immutable because it is also
  borrowed as mutable
5 | let mut advance = || pos += 1;
  |                   -- --- first
  |   borrow occurs due to use of `pos`
6 | let mut number = || {
  |                  ^^ immutable
  |                     borrow occurs here

A closure that changes pos holds a mutable borrow of it for as long as the closure may still be called (chapter 134). No other closure may even read pos in that time. And a closure can’t call itself, so the recursion is out too.

The state becomes a struct

So drip-rs collects the variables into one struct. Adapted from src/compiler.rs:

struct Compiler<'src, 'a> {
    scanner: Scanner<'src>,
    current: Token<'src>,
    previous: Token<'src>,
    had_error: bool,
    panic_mode: bool,
    functions: Vec<FunctionState<'src>>,
    classes: Vec<ClassState>,
    heap: &'a mut Heap,
    roots: &'a dyn Trace,
    errors: &'a mut Vec<String>,
}

Every helper becomes a method taking &mut self. A method that calls another lends it the same &mut, and gets it back when the call returns. There is only ever one user, so there is nothing to conflict with.

The two lifetimes (chapter 133) say what the compiler borrows. 'src is the source text. A Token<'src> holds its lexeme as a &str slice of the source, so tokens are small, Copy, and never copy text. Local variable names are slices of the source too. 'a is the caller’s heap, its GC roots and its error list. compile builds the Compiler on its own stack and drops it at the end, which ends those borrows.

A stack instead of a linked list

When fn bodies nest, the TypeScript compiler links one FnCompiler per function through an enclosing field. Resolving an upvalue walks that list and changes entries in it along the way, so it would need mutable access to several of them at once. In Rust that is a fight with the borrow checker. drip-rs keeps the functions in a Vec, innermost last, and names a function by its index:

fn state(&mut self)
    -> &mut FunctionState<'src> {
    self.functions.last_mut()
        .expect("compiling a function")
}

fn chunk(&mut self) -> &mut Chunk {
    &mut self.state().chunk
}

resolve_upvalue(level, name) looks in self.functions[level - 1], and recurses with level - 1 until it runs out of functions. The level is a plain number, and it borrows nothing. Classes nest the same way, in classes: Vec<ClassState>.

Read first, then borrow

One habit shows up all over compiler.rs. Here is a first try at emitting a byte with its line number:

fn emit(&mut self, b: u8) {
    self.chunk().code.push(b);
    self.chunk().lines.push(self.line);
}

rustc 1.97 rejects the second line (trimmed):

error[E0503]: cannot use `self.line`
  because it was mutably borrowed
15 | self.chunk().lines.push(self.line);
   | ----               ---- ^^^^^^^^^
   | |                   use of borrowed
   | `*self` is borrowed here

self.chunk() borrows all of self mutably, because the method’s signature says so, and that borrow lasts until push is done. Reading self.line for the argument falls inside it. The fix is to read first:

fn emit(&mut self, byte: u8) {
    let line = self.previous.line;
    self.chunk().write(byte, line);
}

Token and TokenKind are Copy, so reading them into locals is cheap. binary begins the same way, with let operator = self.previous.kind;. There it is needed for meaning too: parsing the right operand moves previous on.

Errors, and the end

had_error and panic_mode are fields, used exactly as in chapter 34’s panic-mode recovery. Messages go into the borrowed errors list. When the script is done, compile ends with:

let (function, _) = compiler.end_function();
(!compiler.had_error).then_some(function)

then_some turns true into Some(function) and false into None, where TypeScript returned null.

Your turn

#[derive(Clone, Copy, Debug, PartialEq)]
enum Op {
    Num(f64),
    Add,
    Sub,
    Mul,
    Div,
}

struct Compiler {
    src: Vec<char>,
    pos: usize,
    code: Vec<Op>,
}

fn prec(c: char) -> u8 {
    match c {
        '+' | '-' => 1,
        '*' | '/' => 2,
        _ => 0,
    }
}

impl Compiler {
    fn peek(&self) -> char {
        let i = self.pos;
        self.src.get(i).copied()
            .unwrap_or('\0')
    }

    fn advance(&mut self) -> char {
        let c = self.peek();
        self.pos += 1;
        c
    }

    fn number(&mut self) {
        let c = self.advance();
        let d = c.to_digit(10).unwrap();
        let n = d as f64;
        self.code.push(Op::Num(n));
    }

    // Compile operators of precedence
    // at least min, after one operand.
    fn expr(&mut self, min: u8) {
        todo!()
    }
}

fn compile(s: &str) -> Vec<Op> {
    let mut c = Compiler {
        src: s.chars().collect(),
        pos: 0,
        code: Vec::new(),
    };
    c.expr(1);
    c.code
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum Op {
    Num(f64),
    Add,
    Sub,
    Mul,
    Div,
    Neg,
}

struct Compiler {
    src: Vec<char>,
    pos: usize,
    code: Vec<Op>,
}

fn prec(c: char) -> u8 {
    match c {
        '+' | '-' => 1,
        '*' | '/' => 2,
        _ => 0,
    }
}

impl Compiler {
    fn peek(&self) -> char {
        let i = self.pos;
        self.src.get(i).copied()
            .unwrap_or('\0')
    }

    fn advance(&mut self) -> char {
        let c = self.peek();
        self.pos += 1;
        c
    }

    fn number(&mut self) {
        let c = self.advance();
        let d = c.to_digit(10).unwrap();
        let n = d as f64;
        self.code.push(Op::Num(n));
    }

    // Compile operators of precedence
    // at least min, after one operand.
    fn expr(&mut self, min: u8) {
        self.prefix();
        loop {
            let op = self.peek();
            let p = prec(op);
            if p == 0 || p < min {
                break;
            }
            self.advance();
            self.expr(p + 1);
            self.code.push(match op {
                '+' => Op::Add,
                '-' => Op::Sub,
                '*' => Op::Mul,
                _ => Op::Div,
            });
        }
    }

    // A '-' here is unary minus.
    fn prefix(&mut self) {
        todo!()
    }
}

fn compile(s: &str) -> Vec<Op> {
    let mut c = Compiler {
        src: s.chars().collect(),
        pos: 0,
        code: Vec::new(),
    };
    c.expr(1);
    c.code
}

What you learned

• Closures that share mutable variables, the TypeScript compiler’s style, don’t pass the borrow checker. A closure that writes a variable borrows it mutably for as long as the closure may still be called.
• Compiler state lives in one Compiler struct, and every helper is a method on &mut self. A call lends the whole state, and it comes back on return.
• 'src lets tokens and names borrow the source; 'a covers the borrowed heap, roots and errors.
• Nested functions are a Vec<FunctionState>, innermost last, named by index, instead of an enclosing list.
• Read what you need into locals before calling a &mut self helper such as chunk() (E0503).