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}