栈式虚拟机：GC 根、两个后端与 Criterion

1
[package]
2
name = "pebble-vm"
3
description = "A stack-based virtual machine for Pebble bytecode."
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-bytecode.workspace = true
15
pebble-gc.workspace = true
16
pebble-value.workspace = true
17

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

21
[lints]
22
workspace = true

1
[workspace.dependencies]
2
# --- internal crates ---------------------------------------------------------
3
pebble-span = { path = "crates/pebble-span", version = "0.1.0" }
4
pebble-diag = { path = "crates/pebble-diag", version = "0.1.0" }
5
pebble-lexer = { path = "crates/pebble-lexer", version = "0.1.0" }
6
pebble-ast = { path = "crates/pebble-ast", version = "0.1.0" }
7
pebble-macros = { path = "crates/pebble-macros", version = "0.1.0" }
8
pebble-parser = { path = "crates/pebble-parser", version = "0.1.0" }
9
pebble-value = { path = "crates/pebble-value", version = "0.1.0" }
10
pebble-interp = { path = "crates/pebble-interp", version = "0.1.0" }
11
pebble-bytecode = { path = "crates/pebble-bytecode", version = "0.1.0" }
12
pebble-gc = { path = "crates/pebble-gc", version = "0.1.0" }
13
pebble-vm = { path = "crates/pebble-vm", version = "0.1.0" }
14

15
# --- external ----------------------------------------------------------------
16
anyhow = "1"
17
clap = { version = "4", features = ["derive", "wrap_help"] }
18
criterion = { version = "0.8", features = ["html_reports"] }
19
proc-macro2 = "1"
20
quote = "1"
21
rand = "0.10"
22
rustyline = "18"
23
syn = { version = "3", features = ["full"] }

1
#![forbid(unsafe_code)]
2
//! A stack-based virtual machine for Pebble bytecode.
3
//!
4
//! The VM is the second backend. Where the tree-walker in `pebble-interp` walks
5
//! the AST with `Rc<RefCell<..>>` environments (and therefore leaks recursive
6
//! closures through reference cycles), the VM allocates its runtime objects on
7
//! the [`pebble_gc::Heap`], so cycles are collectable.
8
//!
9
//! The value stack holds [`VmValue`]s. Scalars are inline; everything with a
10
//! dynamic shape (strings, lists, maps, environments, closures) is a
11
//! [`GcRef`] index into the heap. Before each instruction the VM may collect;
12
//! the roots are the value stack, every live frame's environment, and the
13
//! globals.
14

15
use std::rc::Rc;
16

17
use pebble_bytecode::{Chunk, Compiled, Constant, FunctionProto, Opcode};
18
use pebble_gc::{GcObject, GcRef, Heap};
19
use pebble_span::Span;
20
use pebble_value::{Output, RuntimeError, Stdout};
21

22
/// A VM value.
23
///
24
/// `Copy`, so pushing one around never clones a heap object; the heap object
25
/// lives behind the [`GcRef`].
26
#[derive(Copy, Clone, PartialEq, Debug)]
27
pub enum VmValue {
28
    Nil,
29
    Bool(bool),
30
    Int(i64),
31
    Float(f64),
32
    /// A reference to a heap object.
33
    Ref(GcRef),
34
}
35

36
impl VmValue {
37
    fn is_truthy(self) -> bool {
38
        !matches!(self, VmValue::Nil | VmValue::Bool(false))
39
    }
40

41
    fn as_ref(self) -> Option<GcRef> {
42
        match self {
43
            VmValue::Ref(reference) => Some(reference),
44
            _ => None,
45
        }
46
    }
47
}

1
/// A heap-allocated VM object.
2
pub enum VmObject {
3
    /// An immutable string.
4
    Str(String),
5
    /// A mutable list.
6
    List(Vec<VmValue>),
7
    /// A map, stored as insertion-ordered key/value pairs and searched linearly.
8
    Map(Vec<(VmValue, VmValue)>),
9
    /// A function value: a prototype plus the environment it closed over.
10
    Closure {
11
        proto: Rc<FunctionProto>,
12
        env: GcRef,
13
    },
14
    /// A frame of bindings with a link to the enclosing frame.
15
    Env {
16
        parent: Option<GcRef>,
17
        slots: Vec<(String, VmValue)>,
18
    },
19
    /// A builtin function, identified by name.
20
    Native(&'static str),
21
}

1
impl GcObject for VmObject {
2
    fn trace(&self, mark: &mut dyn FnMut(GcRef)) {
3
        match self {
4
            VmObject::Str(_) | VmObject::Native(_) => {}
5
            VmObject::List(items) => {
6
                for item in items {
7
                    if let VmValue::Ref(reference) = item {
8
                        mark(*reference);
9
                    }
10
                }
11
            }
12
            VmObject::Map(entries) => {
13
                for (key, value) in entries {
14
                    if let VmValue::Ref(reference) = key {
15
                        mark(*reference);
16
                    }
17
                    if let VmValue::Ref(reference) = value {
18
                        mark(*reference);
19
                    }
20
                }
21
            }
22
            VmObject::Closure { env, .. } => mark(*env),
23
            VmObject::Env { parent, slots } => {
24
                if let Some(parent) = parent {
25
                    mark(*parent);
26
                }
27
                for (_, value) in slots {
28
                    if let VmValue::Ref(reference) = value {
29
                        mark(*reference);
30
                    }
31
                }
32
            }
33
        }
34
    }
35
}

1
/// One activation record.
2
struct Frame {
3
    proto: Rc<FunctionProto>,
4
    env: GcRef,
5
    ip: usize,
6
}
7

8
/// The virtual machine.
9
pub struct Vm {
10
    heap: Heap<VmObject>,
11
    stack: Vec<VmValue>,
12
    frames: Vec<Frame>,
13
    globals: GcRef,
14
    out: Box<dyn Output>,
15
    max_frames: usize,
16
    gc_threshold: usize,
17
}
18

19
impl Default for Vm {
20
    fn default() -> Self {
21
        Self::new()
22
    }
23
}

1
impl Vm {
2
    /// Creates a VM with default limits, printing to standard output.
3
    #[must_use]
4
    pub fn new() -> Self {
5
        Self::with_output(Box::new(Stdout))
6
    }
7

8
    /// Creates a VM with a custom output sink.
9
    #[must_use]
10
    pub fn with_output(out: Box<dyn Output>) -> Self {
11
        let mut heap = Heap::new();
12
        let globals = heap.alloc(VmObject::Env {
13
            parent: None,
14
            slots: Vec::new(),
15
        });
16
        for name in pebble_value::builtin_names() {
17
            let native = heap.alloc(VmObject::Native(name));
18
            if let VmObject::Env { slots, .. } = heap.get_mut(globals) {
19
                slots.push((name.to_string(), VmValue::Ref(native)));
20
            }
21
        }
22
        Self {
23
            heap,
24
            stack: Vec::new(),
25
            frames: Vec::new(),
26
            globals,
27
            out,
28
            max_frames: 256,
29
            gc_threshold: 1024,
30
        }
31
    }
32

33
    /// Sets the recursion limit.
34
    pub fn set_max_frames(&mut self, frames: usize) {
35
        self.max_frames = frames;
36
    }
37

38
    /// Sets how many allocations may accumulate before a collection.
39
    pub fn set_gc_threshold(&mut self, threshold: usize) {
40
        self.gc_threshold = threshold;
41
    }
42

43
    /// Number of live heap objects.
44
    #[must_use]
45
    pub fn heap_live(&self) -> usize {
46
        self.heap.live_count()
47
    }
48

49
    /// Estimated heap bytes.
50
    #[must_use]
51
    pub fn heap_bytes(&self) -> usize {
52
        self.heap.bytes_allocated()
53
    }

1
    /// Runs a compiled program and returns its value.
2
    ///
3
    /// # Errors
4
    /// Returns a [`RuntimeError`] for any type error, undefined name, arity
5
    /// mismatch, or recursion-limit breach.
6
    pub fn run(&mut self, compiled: &Compiled) -> Result<VmValue, RuntimeError> {
7
        self.stack.clear();
8
        self.frames.clear();
9
        self.frames.push(Frame {
10
            proto: Rc::clone(&compiled.main),
11
            env: self.globals,
12
            ip: 0,
13
        });
14

15
        loop {
16
            if self.frames.is_empty() {
17
                return Ok(self.stack.pop().unwrap_or(VmValue::Nil));
18
            }
19
            if self.heap.allocations_since_gc() > self.gc_threshold {
20
                self.collect_garbage();
21
            }
22

23
            let frame_index = self.frames.len() - 1;
24
            let proto = Rc::clone(&self.frames[frame_index].proto);
25
            let ip = self.frames[frame_index].ip;
26

27
            if ip >= proto.chunk.len() {
28
                // Falling off the end of a chunk returns its top-of-stack.
29
                self.frames.pop();
30
                let result = self.stack.pop().unwrap_or(VmValue::Nil);
31
                if self.frames.is_empty() {
32
                    return Ok(result);
33
                }
34
                self.stack.push(result);
35
                continue;
36
            }
37

38
            let instruction = proto.chunk.code()[ip];
39
            self.frames[frame_index].ip = ip + 1;
40
            let span = proto.chunk.span_at(ip);
41

42
            match instruction {

1
                Opcode::Const(index) => self.push_constant(&proto.chunk, index, span)?,
2
                Opcode::Nil => self.stack.push(VmValue::Nil),
3
                Opcode::True => self.stack.push(VmValue::Bool(true)),
4
                Opcode::False => self.stack.push(VmValue::Bool(false)),
5
                Opcode::Pop => {
6
                    self.stack.pop();
7
                }
8
                Opcode::DefineName(index) => {
9
                    let name = self.constant_name(&proto.chunk, index);
10
                    let value = self.stack.pop().unwrap_or(VmValue::Nil);
11
                    self.define(name, value);
12
                }
13
                Opcode::GetName(index) => {
14
                    let name = self.constant_name(&proto.chunk, index);
15
                    let value = self.lookup(&name).ok_or_else(|| {
16
                        RuntimeError::new(span, format!("undefined variable `{name}`"))
17
                    })?;
18
                    self.stack.push(value);
19
                }
20
                Opcode::SetName(index) => {
21
                    let name = self.constant_name(&proto.chunk, index);
22
                    let value = *self.stack.last().unwrap_or(&VmValue::Nil);
23
                    if !self.assign(&name, value) {
24
                        return Err(RuntimeError::new(
25
                            span,
26
                            format!("cannot assign to undefined variable `{name}`"),
27
                        ));
28
                    }
29
                }
30
                Opcode::MakeClosure(index) => {
31
                    let Constant::Function(proto_of_closure) =
32
                        &proto.chunk.constants()[index as usize]
33
                    else {
34
                        return Err(RuntimeError::new(span, "malformed closure constant"));
35
                    };
36
                    let env = self.frames[frame_index].env;
37
                    let reference = self.heap.alloc(VmObject::Closure {
38
                        proto: Rc::clone(proto_of_closure),
39
                        env,
40
                    });
41
                    self.stack.push(VmValue::Ref(reference));
42
                }

1
                Opcode::Add => self.binary_add(span)?,
2
                Opcode::Sub => self.binary_numeric(span, "-", i64::checked_sub, |a, b| a - b)?,
3
                Opcode::Mul => self.binary_numeric(span, "*", i64::checked_mul, |a, b| a * b)?,
4
                Opcode::Div => self.binary_div(span)?,
5
                Opcode::Rem => self.binary_rem(span)?,
6
                Opcode::Neg => {
7
                    let value = self.pop(span)?;
8
                    let result = match value {
9
                        VmValue::Int(inner) => inner
10
                            .checked_neg()
11
                            .map(VmValue::Int)
12
                            .ok_or_else(|| self.overflow(span))?,
13
                        VmValue::Float(inner) => VmValue::Float(-inner),
14
                        other => {
15
                            return Err(RuntimeError::new(
16
                                span,
17
                                format!("cannot negate {}", self.type_name(other)),
18
                            ));
19
                        }
20
                    };
21
                    self.stack.push(result);
22
                }
23
                Opcode::Not => {
24
                    let value = self.pop(span)?;
25
                    self.stack.push(VmValue::Bool(!value.is_truthy()));
26
                }
27
                Opcode::Equal => {
28
                    let rhs = self.pop(span)?;
29
                    let lhs = self.pop(span)?;
30
                    let equal = self.value_equal(lhs, rhs);
31
                    self.stack.push(VmValue::Bool(equal));
32
                }
33
                Opcode::NotEqual => {
34
                    let rhs = self.pop(span)?;
35
                    let lhs = self.pop(span)?;
36
                    let equal = self.value_equal(lhs, rhs);
37
                    self.stack.push(VmValue::Bool(!equal));
38
                }
39
                Opcode::Less | Opcode::LessEqual | Opcode::Greater | Opcode::GreaterEqual => {
40
                    let ordering = self.binary_compare(span)?;
41
                    use std::cmp::Ordering;
42
                    let result = match instruction {
43
                        Opcode::Less => ordering == Ordering::Less,
44
                        Opcode::LessEqual => ordering != Ordering::Greater,
45
                        Opcode::Greater => ordering == Ordering::Greater,
46
                        Opcode::GreaterEqual => ordering != Ordering::Less,
47
                        _ => unreachable!(),
48
                    };
49
                    self.stack.push(VmValue::Bool(result));
50
                }

1
                Opcode::Jump(target) => self.frames[frame_index].ip = target as usize,
2
                Opcode::JumpIfFalse(target) => {
3
                    let value = self.pop(span)?;
4
                    if !value.is_truthy() {
5
                        self.frames[frame_index].ip = target as usize;
6
                    }
7
                }
8
                Opcode::JumpIfFalseKeep(target) => {
9
                    let value = *self.stack.last().unwrap_or(&VmValue::Nil);
10
                    if value.is_truthy() {
11
                        self.stack.pop();
12
                    } else {
13
                        self.frames[frame_index].ip = target as usize;
14
                    }
15
                }
16
                Opcode::JumpIfTrueKeep(target) => {
17
                    let value = *self.stack.last().unwrap_or(&VmValue::Nil);
18
                    if value.is_truthy() {
19
                        self.frames[frame_index].ip = target as usize;
20
                    } else {
21
                        self.stack.pop();
22
                    }
23
                }
24
                Opcode::Call(count) => self.call(count, span)?,
25
                Opcode::Return => {
26
                    let value = self.stack.pop().unwrap_or(VmValue::Nil);
27
                    self.frames.pop();
28
                    if self.frames.is_empty() {
29
                        return Ok(value);
30
                    }
31
                    self.stack.push(value);
32
                }

1
                Opcode::BuildList(count) => {
2
                    let items = self.stack.split_off(self.stack.len() - count as usize);
3
                    let reference = self.heap.alloc(VmObject::List(items));
4
                    self.stack.push(VmValue::Ref(reference));
5
                }
6
                Opcode::BuildMap(count) => {
7
                    let flat = self
8
                        .stack
9
                        .split_off(self.stack.len() - (count as usize * 2));
10
                    let mut entries = Vec::with_capacity(count as usize);
11
                    let mut iter = flat.into_iter();
12
                    while let (Some(key), Some(value)) = (iter.next(), iter.next()) {
13
                        entries.push((key, value));
14
                    }
15
                    let reference = self.heap.alloc(VmObject::Map(entries));
16
                    self.stack.push(VmValue::Ref(reference));
17
                }
18
                Opcode::Index => {
19
                    let index = self.pop(span)?;
20
                    let container = self.pop(span)?;
21
                    let result = self.index_value(container, index, span)?;
22
                    self.stack.push(result);
23
                }
24
                Opcode::SetIndex => {
25
                    let value = self.pop(span)?;
26
                    let index = self.pop(span)?;
27
                    let container = self.pop(span)?;
28
                    self.set_index_value(container, index, value, span)?;
29
                    self.stack.push(value);
30
                }
31
            }
32
        }
33
    }

1
     12 error[E0599]: no method named `pop` found for mutable reference `&mut Vm` in the current scope
2
      3 error[E0599]: no method named `constant_name` found for mutable reference `&mut Vm` in the current scope
3
      2 error[E0599]: no method named `value_equal` found for mutable reference `&mut Vm` in the current scope
4
      2 error[E0599]: no method named `binary_numeric` found for mutable reference `&mut Vm` in the current scope
5
      1 error[E0599]: no method named `type_name` found for mutable reference `&mut Vm` in the current scope
6
      1 error[E0599]: no method named `set_index_value` found for mutable reference `&mut Vm` in the current scope
7
      1 error[E0599]: no method named `push_constant` found for mutable reference `&mut Vm` in the current scope
8
      1 error[E0599]: no method named `overflow` found for mutable reference `&mut Vm` in the current scope
9
      1 error[E0599]: no method named `lookup` found for mutable reference `&mut Vm` in the current scope
10
      1 error[E0599]: no method named `index_value` found for mutable reference `&mut Vm` in the current scope
11
      1 error[E0599]: no method named `define` found for mutable reference `&mut Vm` in the current scope
12
      1 error[E0599]: no method named `collect_garbage` found for mutable reference `&mut Vm` in the current scope
13
      1 error[E0599]: no method named `call` found for mutable reference `&mut Vm` in the current scope
14
      1 error[E0599]: no method named `binary_rem` found for mutable reference `&mut Vm` in the current scope
15
      1 error[E0599]: no method named `binary_div` found for mutable reference `&mut Vm` in the current scope
16
      1 error[E0599]: no method named `binary_compare` found for mutable reference `&mut Vm` in the current scope
17
      1 error[E0599]: no method named `binary_add` found for mutable reference `&mut Vm` in the current scope
18
      1 error[E0599]: no method named `assign` found for mutable reference `&mut Vm` in the current scope
19
      1 error: could not compile `pebble-vm` (lib) due to 33 previous errors; 2 warnings emitted

1
    // --- helpers: stack, constants ---------------------------------------
2

3
    fn pop(&mut self, span: Span) -> Result<VmValue, RuntimeError> {
4
        self.stack
5
            .pop()
6
            .ok_or_else(|| RuntimeError::new(span, "internal error: value stack underflow"))
7
    }
8

9
    fn push_constant(&mut self, chunk: &Chunk, index: u32, span: Span) -> Result<(), RuntimeError> {
10
        match &chunk.constants()[index as usize] {
11
            Constant::Nil => self.stack.push(VmValue::Nil),
12
            Constant::Bool(value) => self.stack.push(VmValue::Bool(*value)),
13
            Constant::Int(value) => self.stack.push(VmValue::Int(*value)),
14
            Constant::Float(value) => self.stack.push(VmValue::Float(*value)),
15
            Constant::Str(value) => {
16
                let reference = self.heap.alloc(VmObject::Str(value.clone()));
17
                self.stack.push(VmValue::Ref(reference));
18
            }
19
            Constant::Function(_) => {
20
                return Err(RuntimeError::new(span, "function constant used as a value"));
21
            }
22
        }
23
        Ok(())
24
    }
25

26
    fn constant_name(&self, chunk: &Chunk, index: u32) -> String {
27
        match &chunk.constants()[index as usize] {
28
            Constant::Str(name) => name.clone(),
29
            _ => format!("<constant {index}>"),
30
        }
31
    }

1
    // --- helpers: environments -------------------------------------------
2

3
    fn current_env(&self) -> GcRef {
4
        self.frames.last().map_or(self.globals, |frame| frame.env)
5
    }
6

7
    fn define(&mut self, name: String, value: VmValue) {
8
        let env = self.current_env();
9
        if let VmObject::Env { slots, .. } = self.heap.get_mut(env) {
10
            if let Some(slot) = slots.iter_mut().find(|(existing, _)| *existing == name) {
11
                slot.1 = value;
12
            } else {
13
                slots.push((name, value));
14
            }
15
        }
16
    }
17

18
    fn lookup(&self, name: &str) -> Option<VmValue> {
19
        let mut current = Some(self.current_env());
20
        while let Some(env) = current {
21
            let VmObject::Env { parent, slots } = self.heap.get(env) else {
22
                return None;
23
            };
24
            if let Some((_, value)) = slots.iter().find(|(existing, _)| existing == name) {
25
                return Some(*value);
26
            }
27
            current = *parent;
28
        }
29
        None
30
    }
31

32
    fn assign(&mut self, name: &str, value: VmValue) -> bool {
33
        let mut current = Some(self.current_env());
34
        while let Some(env) = current {
35
            if let VmObject::Env { parent, slots } = self.heap.get_mut(env) {
36
                if let Some(slot) = slots.iter_mut().find(|(existing, _)| existing == name) {
37
                    slot.1 = value;
38
                    return true;
39
                }
40
                current = *parent;
41
            } else {
42
                return false;
43
            }
44
        }
45
        false
46
    }

1
    // --- helpers: calls ---------------------------------------------------
2

3
    fn call(&mut self, count: u32, span: Span) -> Result<(), RuntimeError> {
4
        let count = count as usize;
5
        if self.stack.len() < count + 1 {
6
            return Err(RuntimeError::new(
7
                span,
8
                "internal error: call stack underflow",
9
            ));
10
        }
11
        let args = self.stack.split_off(self.stack.len() - count);
12
        let callee = self.pop(span)?;
13

14
        enum Target {
15
            Native(&'static str),
16
            Closure(Rc<FunctionProto>, GcRef),
17
        }
18

19
        let target = match callee.as_ref().map(|reference| self.heap.get(reference)) {
20
            Some(VmObject::Native(name)) => Target::Native(name),
21
            Some(VmObject::Closure { proto, env }) => Target::Closure(Rc::clone(proto), *env),
22
            _ => {
23
                return Err(RuntimeError::new(
24
                    span,
25
                    format!("{} is not callable", self.type_name(callee)),
26
                ));
27
            }
28
        };

1
error[E0502]: cannot borrow `self.heap` as mutable because it is also borrowed as immutable
2
   --> crates/pebble-vm/src/lib.rs:480:27
3
    |
4
477 |               callee.as_ref().map(|reference| self.heap.get(reference))
5
    |                                   ----------- --------- first borrow occurs due to use of `self.heap` in closure
6
    |                                   |
7
    |                                   immutable borrow occurs here
8
...
9
480 |               let new_env = self.heap.alloc(VmObject::Env {
10
    |  ___________________________^
11
481 | |                 parent: Some(*env),
12
482 | |                 slots,
13
483 | |             });
14
    | |______________^ mutable borrow occurs here
15
484 |               self.frames.push(Frame {
16
485 |                   proto: Rc::clone(proto),
17
    |                                    ----- immutable borrow later used here
18

19
For more information about this error, try `rustc --explain E0502`.
20
error: could not compile `pebble-vm` (lib) due to 1 previous error