Skip to main content

bvm_lang/
chunk.rs

1//! A unit of executable bytecode: its instructions, its constants, and the size
2//! of the register file they operate on.
3//!
4//! A [`Chunk`] is what you hand to [`Vm::run`](crate::Vm::run). It is built up
5//! instruction by instruction with [`emit`](Chunk::emit); large or non-integer
6//! literals go into the constant pool with [`constant`](Chunk::constant), which
7//! returns the index a [`LoadConst`](crate::Op::LoadConst) uses to read them back.
8//!
9//! The register-file size is tracked automatically: every emitted instruction
10//! widens the file to cover the highest register it names, so callers never size
11//! it by hand and can never under-provision it. Forward branches — the jump out
12//! of an `if`, the back-edge of a loop — are written with a placeholder target
13//! and later fixed up with [`patch`](Chunk::patch) once the destination is known.
14
15use crate::{Addr, Op};
16use alloc::vec::Vec;
17use value_lang::Value;
18
19/// An assembled sequence of instructions with its constant pool.
20///
21/// Cloning a chunk is a deep copy of both vectors; it is cheap relative to
22/// execution and lets a compiled program be run many times. A chunk carries no
23/// interpreter state — that lives in the [`Vm`](crate::Vm) — so the same chunk can
24/// be executed concurrently by separate VMs.
25#[derive(Debug, Clone, Default, PartialEq)]
26#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
27pub struct Chunk {
28    code: Vec<Op>,
29    constants: Vec<Value>,
30    registers: u16,
31}
32
33impl Chunk {
34    /// Create an empty chunk with no instructions, no constants, and a
35    /// zero-width register file.
36    ///
37    /// # Examples
38    ///
39    /// ```
40    /// use bvm_lang::Chunk;
41    ///
42    /// let chunk = Chunk::new();
43    /// assert!(chunk.is_empty());
44    /// assert_eq!(chunk.registers(), 0);
45    /// ```
46    #[must_use]
47    pub fn new() -> Self {
48        Self::default()
49    }
50
51    /// Append an instruction and return its address.
52    ///
53    /// The returned [`Addr`] is where the instruction sits in the code array —
54    /// the same value a branch uses as its target, and the argument
55    /// [`patch`](Chunk::patch) takes to rewrite this slot later. Returning an
56    /// `Addr` lets an emitted address feed straight back into a `Jump`/`patch`
57    /// without a cast. Emitting widens the register file to include every
58    /// register the instruction names.
59    ///
60    /// # Examples
61    ///
62    /// ```
63    /// use bvm_lang::{Chunk, Op};
64    ///
65    /// let mut chunk = Chunk::new();
66    /// let first = chunk.emit(Op::LoadInt { dst: 0, val: 41 });
67    /// assert_eq!(first, 0);
68    /// // Naming register 0 sized the file to one slot.
69    /// assert_eq!(chunk.registers(), 1);
70    /// ```
71    pub fn emit(&mut self, op: Op) -> Addr {
72        if let Some(top) = max_register(op) {
73            // `top` is the highest index named; the file must hold `top + 1`
74            // slots. Saturating keeps the arithmetic total even at `u16::MAX`.
75            self.registers = self.registers.max(top.saturating_add(1));
76        }
77        // A chunk cannot hold more than `u32::MAX` instructions in practice
78        // (the code alone would exceed addressable memory), so the address
79        // always fits an `Addr`.
80        let addr = self.code.len() as Addr;
81        self.code.push(op);
82        addr
83    }
84
85    /// Add `value` to the constant pool and return its index for
86    /// [`LoadConst`](crate::Op::LoadConst).
87    ///
88    /// Constants are not deduplicated; adding the same value twice yields two
89    /// slots. This keeps the builder allocation-light and predictable — a
90    /// compiler that wants interning can layer it on top.
91    ///
92    /// # Errors
93    ///
94    /// Returns [`None`] if the pool already holds `u16::MAX + 1` constants, the
95    /// most a [`Const`](crate::Const) index can address. A single function body
96    /// reaching 65 536 distinct constants is pathological, so callers typically
97    /// treat this as unreachable rather than a runtime path.
98    ///
99    /// # Examples
100    ///
101    /// ```
102    /// use bvm_lang::{Chunk, Op, Value};
103    ///
104    /// let mut chunk = Chunk::new();
105    /// let k = chunk.constant(Value::float(3.5)).expect("pool has room");
106    /// chunk.emit(Op::LoadConst { dst: 0, index: k });
107    /// ```
108    #[must_use = "the returned index is how the constant is later loaded"]
109    pub fn constant(&mut self, value: Value) -> Option<u16> {
110        let index = u16::try_from(self.constants.len()).ok()?;
111        self.constants.push(value);
112        Some(index)
113    }
114
115    /// Overwrite the instruction at `addr`, typically to fill in a branch target
116    /// that was not known when the instruction was first emitted.
117    ///
118    /// Returns `true` if `addr` was a valid slot and the rewrite happened, and
119    /// `false` if it was out of range. Rewriting can change which registers the
120    /// chunk touches, so the register file is re-derived from scratch to stay
121    /// exact.
122    ///
123    /// # Examples
124    ///
125    /// ```
126    /// use bvm_lang::{Chunk, Op};
127    ///
128    /// let mut chunk = Chunk::new();
129    /// // Emit a forward branch whose target is not yet known.
130    /// let jump = chunk.emit(Op::Jump { target: 0 });
131    /// chunk.emit(Op::LoadInt { dst: 0, val: 1 }); // skipped by the jump
132    /// let landing = chunk.emit(Op::Halt);         // where the jump should land
133    /// // Now patch the branch to skip the load. `landing` is already an `Addr`.
134    /// assert!(chunk.patch(jump, Op::Jump { target: landing }));
135    /// ```
136    pub fn patch(&mut self, addr: Addr, op: Op) -> bool {
137        let Some(slot) = self.code.get_mut(addr as usize) else {
138            return false;
139        };
140        *slot = op;
141        self.recompute_registers();
142        true
143    }
144
145    /// The chunk's instructions, in address order.
146    #[must_use]
147    pub fn code(&self) -> &[Op] {
148        &self.code
149    }
150
151    /// The chunk's constant pool, indexed by [`LoadConst`](crate::Op::LoadConst).
152    #[must_use]
153    pub fn constants(&self) -> &[Value] {
154        &self.constants
155    }
156
157    /// The number of registers the chunk uses — one more than the highest
158    /// register index any instruction names, or zero for a chunk that names none.
159    #[must_use]
160    pub fn registers(&self) -> u16 {
161        self.registers
162    }
163
164    /// The number of instructions in the chunk.
165    #[must_use]
166    pub fn len(&self) -> usize {
167        self.code.len()
168    }
169
170    /// Whether the chunk contains no instructions.
171    #[must_use]
172    pub fn is_empty(&self) -> bool {
173        self.code.is_empty()
174    }
175
176    /// Re-derive the register-file size from the current code. Used after
177    /// [`patch`](Chunk::patch), where an edit may have removed the instruction
178    /// that justified the previous width.
179    fn recompute_registers(&mut self) {
180        self.registers = self
181            .code
182            .iter()
183            .filter_map(|op| max_register(*op))
184            .map(|top| top.saturating_add(1))
185            .max()
186            .unwrap_or(0);
187    }
188}
189
190/// The highest register index an instruction names, or `None` if it names none
191/// (`Jump`, `Halt`).
192#[inline]
193fn max_register(op: Op) -> Option<u16> {
194    match op {
195        Op::Move { dst, src } | Op::Neg { dst, src } | Op::Not { dst, src } => Some(dst.max(src)),
196        Op::LoadConst { dst, .. }
197        | Op::LoadNil { dst }
198        | Op::LoadBool { dst, .. }
199        | Op::LoadInt { dst, .. } => Some(dst),
200        Op::Add { dst, lhs, rhs }
201        | Op::Sub { dst, lhs, rhs }
202        | Op::Mul { dst, lhs, rhs }
203        | Op::Div { dst, lhs, rhs }
204        | Op::Rem { dst, lhs, rhs }
205        | Op::Eq { dst, lhs, rhs }
206        | Op::Ne { dst, lhs, rhs }
207        | Op::Lt { dst, lhs, rhs }
208        | Op::Le { dst, lhs, rhs }
209        | Op::Gt { dst, lhs, rhs }
210        | Op::Ge { dst, lhs, rhs } => Some(dst.max(lhs).max(rhs)),
211        Op::JumpIfTrue { cond, .. } | Op::JumpIfFalse { cond, .. } | Op::Return { src: cond } => {
212            Some(cond)
213        }
214        Op::Jump { .. } | Op::Halt => None,
215    }
216}
217
218#[cfg(test)]
219mod tests {
220    #![allow(clippy::unwrap_used, clippy::expect_used)]
221    use super::*;
222
223    #[test]
224    fn test_emit_returns_sequential_addresses() {
225        let mut c = Chunk::new();
226        assert_eq!(c.emit(Op::Halt), 0);
227        assert_eq!(c.emit(Op::Halt), 1);
228        assert_eq!(c.len(), 2);
229    }
230
231    #[test]
232    fn test_register_file_tracks_highest_index() {
233        let mut c = Chunk::new();
234        let _ = c.emit(Op::Add {
235            dst: 5,
236            lhs: 2,
237            rhs: 9,
238        });
239        assert_eq!(c.registers(), 10);
240    }
241
242    #[test]
243    fn test_constant_returns_incrementing_indices() {
244        let mut c = Chunk::new();
245        assert_eq!(c.constant(Value::int(1)), Some(0));
246        assert_eq!(c.constant(Value::int(2)), Some(1));
247        assert_eq!(c.constants().len(), 2);
248    }
249
250    #[test]
251    fn test_patch_replaces_instruction_and_reports_success() {
252        let mut c = Chunk::new();
253        let at = c.emit(Op::Jump { target: 0 });
254        assert!(c.patch(at, Op::Jump { target: 7 }));
255        assert_eq!(c.code()[at as usize], Op::Jump { target: 7 });
256    }
257
258    #[test]
259    fn test_patch_out_of_range_returns_false() {
260        let mut c = Chunk::new();
261        assert!(!c.patch(0, Op::Halt));
262    }
263
264    #[test]
265    fn test_patch_recomputes_register_file() {
266        let mut c = Chunk::new();
267        let at = c.emit(Op::LoadInt { dst: 40, val: 1 });
268        assert_eq!(c.registers(), 41);
269        // Replace the wide instruction; the file should shrink to fit.
270        assert!(c.patch(at, Op::Halt));
271        assert_eq!(c.registers(), 0);
272    }
273
274    #[test]
275    fn test_new_chunk_is_empty() {
276        let c = Chunk::new();
277        assert!(c.is_empty());
278        assert_eq!(c.registers(), 0);
279    }
280}