树遍历解释器：闭包、控制流与一个内存泄漏

1
/// How a statement finished.
2
///
3
/// Most statements produce a value and fall through (`Value`); the other three
4
/// variants unwind the walker.
5
#[derive(Debug)]
6
pub enum Flow {
7
    /// Completed normally, producing this value.
8
    Value(Value),
9
    /// A `return` escaped.
10
    Return(Value),
11
    /// A `break` escaped.
12
    Break,
13
    /// A `continue` escaped.
14
    Continue,
15
}
16

17
impl Flow {
18
    fn is_normal(&self) -> bool {
19
        matches!(self, Flow::Value(_))
20
    }
21
}

1
[package]
2
name = "pebble-interp"
3
description = "A tree-walking interpreter for Pebble."
4
version.workspace = true
5
edition.workspace = true
6
rust-version.workspace = true
7
authors.workspace = true
8
license.workspace = true
9
repository.workspace = true
10

11
[dependencies]
12
pebble-span.workspace = true
13
pebble-diag.workspace = true
14
pebble-ast.workspace = true
15
pebble-value.workspace = true
16

17
[dev-dependencies]
18
pebble-parser.workspace = true
19

20
[lints]
21
workspace = true

1
/// How a statement finished.
2
///
3
/// Most statements produce a value and fall through (`Value`); the other three
4
/// variants unwind the walker.
5
#[derive(Debug)]
6
pub enum Flow {
7
    /// Completed normally, producing this value.
8
    Value(Value),
9
    /// A `return` escaped.
10
    Return(Value),
11
    /// A `break` escaped.
12
    Break,
13
    /// A `continue` escaped.
14
    Continue,
15
}
16

17
impl Flow {
18
    fn is_normal(&self) -> bool {
19
        matches!(self, Flow::Value(_))
20
    }
21
}

1
/// The tree-walking interpreter.
2
pub struct Interpreter {
3
    globals: Rc<RefCell<Env>>,
4
}
5

6
impl Default for Interpreter {
7
    fn default() -> Self {
8
        Self::new()
9
    }
10
}
11

12
impl Interpreter {
13
    /// Creates an interpreter whose global scope holds the builtins.
14
    #[must_use]
15
    pub fn new() -> Self {
16
        let globals = Rc::new(RefCell::new(Env::new()));
17
        {
18
            let mut scope = globals.borrow_mut();
19
            for function in pebble_value::BUILTINS {
20
                scope.define(function.name, Value::Native(function));
21
            }
22
        }
23
        Self { globals }
24
    }
25

26
    /// The global scope.
27
    #[must_use]
28
    pub fn globals(&self) -> Rc<RefCell<Env>> {
29
        Rc::clone(&self.globals)
30
    }

1
    // --- statements -------------------------------------------------------
2

3
    fn execute_block(
4
        &mut self,
5
        stmts: &[Stmt],
6
        env: Rc<RefCell<Env>>,
7
    ) -> Result<Flow, RuntimeError> {
8
        let mut last = Flow::Value(Value::Nil);
9
        for stmt in stmts {
10
            last = self.execute_stmt(stmt, &env)?;
11
            if !last.is_normal() {
12
                return Ok(last);
13
            }
14
        }
15
        Ok(last)
16
    }

1
            Expr::Unary { op, operand, span } => {
2
                let value = self.eval(operand, env)?;
3
                match op {
4
                    UnaryOp::Neg => negate(&value, *span),
5
                    UnaryOp::Not => Ok(Value::Bool(!value.is_truthy())),
6
                }
7
            }
8
            Expr::Binary { op, lhs, rhs, span } => {
9
                let lhs = self.eval(lhs, env)?;
10
                let rhs = self.eval(rhs, env)?;
11
                eval_binary(*op, &lhs, &rhs, *span)
12
            }
13
            Expr::Logical { op, lhs, rhs, .. } => {
14
                let lhs = self.eval(lhs, env)?;
15
                match op {
16
                    LogicalOp::And => {
17
                        if lhs.is_truthy() {
18
                            self.eval(rhs, env)
19
                        } else {
20
                            Ok(lhs)
21
                        }
22
                    }
23
                    LogicalOp::Or => {
24
                        if lhs.is_truthy() {
25
                            Ok(lhs)
26
                        } else {
27
                            self.eval(rhs, env)
28
                        }
29
                    }
30
                }
31
            }

1
            Expr::Assign { target, value, .. } => {
2
                let new_value = self.eval(value, env)?;
3
                match target.as_ref() {
4
                    Expr::Var { name, span } => {
5
                        if env.borrow_mut().assign(&name.name, new_value.clone()) {
6
                            Ok(new_value)
7
                        } else {
8
                            Err(RuntimeError::new(
9
                                *span,
10
                                format!("cannot assign to undefined variable `{}`", name.name),
11
                            ))
12
                        }
13
                    }
14
                    other => Err(RuntimeError::new(other.span(), "invalid assignment target")),
15
                }
16
            }
17
            _ => todo!("calls, closures and collections come later"),
18
        }
19
    }

1
fn eval_binary(op: BinaryOp, lhs: &Value, rhs: &Value, span: Span) -> Result<Value, RuntimeError> {
2
    use std::cmp::Ordering;
3
    Ok(match op {
4
        BinaryOp::Add => pebble_value::add(lhs, rhs, span)?,
5
        BinaryOp::Sub => sub(lhs, rhs, span)?,
6
        BinaryOp::Mul => mul(lhs, rhs, span)?,
7
        BinaryOp::Div => div(lhs, rhs, span)?,
8
        BinaryOp::Rem => rem(lhs, rhs, span)?,
9
        BinaryOp::Eq => Value::Bool(lhs.equals(rhs)),
10
        BinaryOp::NotEq => Value::Bool(!lhs.equals(rhs)),
11
        BinaryOp::Lt => Value::Bool(compare(lhs, rhs, span)? == Ordering::Less),
12
        BinaryOp::LtEq => Value::Bool(compare(lhs, rhs, span)? != Ordering::Greater),
13
        BinaryOp::Gt => Value::Bool(compare(lhs, rhs, span)? == Ordering::Greater),
14
        BinaryOp::GtEq => Value::Bool(compare(lhs, rhs, span)? != Ordering::Less),
15
    })
16
}

1
#[cfg(test)]
2
mod tests {
3
    use super::*;
4
    use pebble_parser::parse;
5
    use pebble_span::SourceId;
6

7
    fn run(src: &str) -> Result<Value, RuntimeError> {
8
        let mut interpreter = Interpreter::new();
9
        let result = parse(SourceId(0), src);
10
        assert!(result.is_ok(), "parse errors: {:?}", result.diagnostics);
11
        interpreter.interpret(&result.program)
12
    }
13

14
    #[test]
15
    fn evaluates_arithmetic_with_precedence() {
16
        assert_eq!(run("1 + 2 * 3;").unwrap(), Value::Int(7));
17
        assert_eq!(run("(1 + 2) * 3;").unwrap(), Value::Int(9));
18
        assert_eq!(run("7 % 3;").unwrap(), Value::Int(1));
19
    }
20

21
    #[test]
22
    fn variables_and_assignment() {
23
        assert_eq!(run("let x = 1; x = x + 41; x;").unwrap(), Value::Int(42));
24
    }
25
}

1
    /// Runs a nested block in a fresh child scope, normalising its value to
2
    /// `nil`.
3
    ///
4
    /// Only expression statements carry a value; a control-flow statement such
5
    /// as `if` produces `nil`. The bytecode compiler makes the same choice, so
6
    /// the two backends agree on what a program evaluates to.
7
    fn run_scoped_block(
8
        &mut self,
9
        stmts: &[Stmt],
10
        env: &Rc<RefCell<Env>>,
11
    ) -> Result<Flow, RuntimeError> {
12
        let scope = Env::child(Rc::clone(env));
13
        match self.execute_block(stmts, scope)? {
14
            Flow::Value(_) => Ok(Flow::Value(Value::Nil)),
15
            other => Ok(other),
16
        }
17
    }

1
            Stmt::For {
2
                var, iter, body, ..
3
            } => {
4
                let iterable = self.eval(iter, env)?;
5
                let Value::List(items) = &iterable else {
6
                    return Err(RuntimeError::new(
7
                        iterable_span(iter),
8
                        format!("`for` needs a list, got {}", iterable.type_name()),
9
                    ));
10
                };
11
                let snapshot = items.borrow().clone();
12
                for item in snapshot {
13
                    let scope = Env::child(Rc::clone(env));
14
                    scope.borrow_mut().define(var.name.clone(), item);
15
                    match self.execute_block(body, scope)? {
16
                        Flow::Return(value) => return Ok(Flow::Return(value)),
17
                        Flow::Break => break,
18
                        Flow::Value(_) | Flow::Continue => {}
19
                    }
20
                }
21
                Ok(Flow::Value(Value::Nil))
22
            }