1use std::sync::Arc;
2use std::time::Duration;
3
4use crate::bytecode::{Chunk, Instruction, Opcode, Value};
5
6use super::fault::Fault;
7use super::frame::Frame;
8use super::native::NativeTable;
9use super::result::VmResult;
10
11pub const MAX_CALL_DEPTH: usize = 4096;
17
18pub struct Vm {
26 chunk: Arc<Chunk>,
27 natives: Arc<NativeTable>,
28 frames: Vec<Frame>,
29 instructions_executed: u64,
32}
33
34impl Vm {
35 pub fn new(chunk: Arc<Chunk>, natives: Arc<NativeTable>, function: u32, args: &[Value]) -> Result<Self, Fault> {
40 let def = chunk
41 .function(function)
42 .ok_or(Fault::BadFunction { index: function, table_size: chunk.functions.len() as u32 })?;
43 let mut frame = Frame::new(function, def.num_registers, None);
44 frame.pc = def.entry as usize;
45 for (i, arg) in args.iter().enumerate().take(def.arity as usize) {
54 match frame.registers.get_mut(i) {
55 Some(slot) => *slot = arg.clone(),
56 None => {
57 return Err(Fault::RegisterOutOfRange {
58 reg: i as u8,
59 frame_size: def.num_registers,
60 })
61 }
62 }
63 }
64 Ok(Vm { chunk, natives, frames: vec![frame], instructions_executed: 0 })
65 }
66
67 pub fn instructions_executed(&self) -> u64 {
68 self.instructions_executed
69 }
70
71 pub fn current_function(&self) -> u32 {
74 debug_assert!(!self.frames.is_empty(), "frames empty while running");
78 match self.frames.last() {
79 Some(frame) => frame.function,
80 None => 0,
81 }
82 }
83
84 pub fn chunk_arc(&self) -> Arc<Chunk> {
90 self.chunk.clone()
91 }
92
93 pub fn natives_arc(&self) -> Arc<NativeTable> {
97 self.natives.clone()
98 }
99
100 #[inline]
107 pub fn resume_with(&mut self, dest_reg: u8, value: Value) -> Result<(), Fault> {
108 self.set_reg(dest_reg, value)
109 }
110
111 #[inline]
114 fn current(&mut self) -> Result<&mut Frame, Fault> {
115 debug_assert!(!self.frames.is_empty(), "frames empty while running");
116 self.frames
117 .last_mut()
118 .ok_or(Fault::Invariant("empty frame stack while running"))
119 }
120
121 #[inline]
122 fn get_reg(&self, reg: u8) -> Result<Value, Fault> {
123 let frame = self
124 .frames
125 .last()
126 .ok_or(Fault::Invariant("empty frame stack while running"))?;
127 frame
128 .registers
129 .get(reg as usize)
130 .cloned()
131 .ok_or(Fault::RegisterOutOfRange {
132 reg,
133 frame_size: frame.registers.len() as u8,
134 })
135 }
136
137 #[inline]
138 fn set_reg(&mut self, reg: u8, value: Value) -> Result<(), Fault> {
139 let frame = self.current()?;
140 let len = frame.registers.len() as u8;
141 match frame.registers.get_mut(reg as usize) {
142 Some(slot) => {
143 *slot = value;
144 Ok(())
145 }
146 None => Err(Fault::RegisterOutOfRange { reg, frame_size: len }),
147 }
148 }
149
150 #[inline]
161 fn fetch(&mut self) -> Result<Option<Instruction>, Fault> {
162 let pc = self.current()?.pc;
163 let instr = self.chunk.code.get(pc).copied();
164 if instr.is_some() {
165 self.current()?.pc = pc + 1;
166 }
167 Ok(instr)
168 }
169
170 fn numeric_binop(&mut self, op: Opcode, dst: u8, lhs: u8, rhs: u8) -> Result<(), Fault> {
171 let a = self.get_reg(lhs)?;
172 let b = self.get_reg(rhs)?;
173 let result = match (op, &a, &b) {
174 (Opcode::Add, Value::Int(x), Value::Int(y)) => Value::Int(x.wrapping_add(*y)),
175 (Opcode::Add, _, _) => Value::Float(as_f64(&a)? + as_f64(&b)?),
176 (Opcode::Sub, Value::Int(x), Value::Int(y)) => Value::Int(x.wrapping_sub(*y)),
177 (Opcode::Sub, _, _) => Value::Float(as_f64(&a)? - as_f64(&b)?),
178 (Opcode::Mul, Value::Int(x), Value::Int(y)) => Value::Int(x.wrapping_mul(*y)),
179 (Opcode::Mul, _, _) => Value::Float(as_f64(&a)? * as_f64(&b)?),
180 (Opcode::Div, Value::Int(x), Value::Int(y)) => {
181 if *y == 0 {
182 return Err(Fault::DivideByZero);
183 }
184 Value::Int(x.wrapping_div(*y))
185 }
186 (Opcode::Div, _, _) => {
187 let denom = as_f64(&b)?;
188 Value::Float(as_f64(&a)? / denom)
189 }
190 (Opcode::Mod, Value::Int(x), Value::Int(y)) => {
191 if *y == 0 {
192 return Err(Fault::DivideByZero);
193 }
194 Value::Int(x.wrapping_rem(*y))
195 }
196 (Opcode::Eq, _, _) => Value::Bool(a == b),
197 (Opcode::Lt, Value::Int(x), Value::Int(y)) => Value::Bool(x < y),
198 (Opcode::Lt, _, _) => Value::Bool(as_f64(&a)? < as_f64(&b)?),
199 (Opcode::Le, Value::Int(x), Value::Int(y)) => Value::Bool(x <= y),
200 (Opcode::Le, _, _) => Value::Bool(as_f64(&a)? <= as_f64(&b)?),
201 _ => {
202 return Err(Fault::Invariant(
203 "numeric_binop called with a non-arithmetic opcode",
204 ))
205 }
206 };
207 self.set_reg(dst, result)
208 }
209
210 pub fn run(&mut self, budget: u32) -> VmResult {
218 for _ in 0..budget {
219 self.instructions_executed += 1;
220 let instr = match self.fetch() {
221 Ok(Some(i)) => i,
222 Ok(None) => {
223 match self.pop_frame(Value::Unit) {
225 Ok(Some(result)) => return result,
226 Ok(None) => continue,
227 Err(fault) => return VmResult::Trap(fault),
228 }
229 }
230 Err(fault) => return VmResult::Trap(fault),
231 };
232
233 macro_rules! trap {
234 ($e:expr) => {
235 match $e {
236 Ok(v) => v,
237 Err(fault) => return VmResult::Trap(fault),
238 }
239 };
240 }
241
242 match instr.op {
243 Opcode::Halt => {
244 let v = trap!(self.get_reg(0));
245 return VmResult::Complete(v);
246 }
247 Opcode::Nop => {}
248 Opcode::LoadConst => {
249 let idx = instr.imm as u32;
250 let konst = match self.chunk.constant(idx) {
251 Some(v) => v.clone(),
252 None => {
253 return VmResult::Trap(Fault::BadConstant {
254 index: idx,
255 pool_size: self.chunk.constants.len() as u32,
256 })
257 }
258 };
259 trap!(self.set_reg(instr.a, konst));
260 }
261 Opcode::LoadImm => {
262 trap!(self.set_reg(instr.a, Value::Int(instr.imm as i64)));
263 }
264 Opcode::Move => {
265 let v = trap!(self.get_reg(instr.b));
266 trap!(self.set_reg(instr.a, v));
267 }
268 Opcode::Add | Opcode::Sub | Opcode::Mul | Opcode::Div | Opcode::Mod
269 | Opcode::Eq | Opcode::Lt | Opcode::Le => {
270 trap!(self.numeric_binop(instr.op, instr.a, instr.b, instr.c));
271 }
272 Opcode::Neg => {
273 let v = trap!(self.get_reg(instr.b));
274 let negated = match v {
275 Value::Int(x) => Value::Int(-x),
276 Value::Float(x) => Value::Float(-x),
277 other => {
278 return VmResult::Trap(Fault::TypeMismatch {
279 expected: "int or float",
280 got: other.type_name(),
281 })
282 }
283 };
284 trap!(self.set_reg(instr.a, negated));
285 }
286 Opcode::Jump => {
287 let frame = trap!(self.current());
288 let target = frame.pc as i64 + instr.imm as i64;
289 frame.pc = target as usize;
290 }
291 Opcode::Branch => {
292 let cond = trap!(self.get_reg(instr.a));
293 if !cond.is_truthy() {
294 let frame = trap!(self.current());
295 let target = frame.pc as i64 + instr.imm as i64;
296 frame.pc = target as usize;
297 }
298 }
299 Opcode::Call => {
300 let function = instr.imm as u32;
301 let argc = instr.b;
302 let dst = instr.a;
303 if self.frames.len() >= MAX_CALL_DEPTH {
304 return VmResult::Trap(Fault::CallStackOverflow { depth: self.frames.len() });
305 }
306 let def = match self.chunk.function(function) {
307 Some(d) => d.clone(),
308 None => {
309 return VmResult::Trap(Fault::BadFunction {
310 index: function,
311 table_size: self.chunk.functions.len() as u32,
312 })
313 }
314 };
315 let mut args = Vec::with_capacity(argc as usize);
316 for i in 0..argc {
317 args.push(trap!(self.get_reg(trap!(reg_at(dst, u16::from(i))))));
318 }
319 let mut new_frame = Frame::new(function, def.num_registers, Some(dst));
320 new_frame.pc = def.entry as usize;
321 for (i, a) in args.into_iter().enumerate().take(def.arity as usize) {
323 match new_frame.registers.get_mut(i) {
324 Some(slot) => *slot = a,
325 None => {
326 return VmResult::Trap(Fault::RegisterOutOfRange {
327 reg: i as u8,
328 frame_size: def.num_registers,
329 })
330 }
331 }
332 }
333 self.frames.push(new_frame);
334 }
335 Opcode::CallNative => {
336 let native_index = instr.imm as u32;
337 let argc = instr.b;
338 let dst = instr.a;
339 let native_fn = match self.natives.get(native_index) {
340 Some(f) => f.clone(),
341 None => {
342 return VmResult::Trap(Fault::BadNative {
343 index: native_index,
344 table_size: self.natives.len() as u32,
345 })
346 }
347 };
348 let mut args = Vec::with_capacity(argc as usize);
349 for i in 0..argc {
350 args.push(trap!(self.get_reg(trap!(reg_at(dst, u16::from(i))))));
351 }
352 match native_fn(&args) {
360 Ok(value) => trap!(self.set_reg(dst, value)),
361 Err(fault) => return VmResult::Trap(fault),
362 }
363 }
364 Opcode::Return => {
365 let v = trap!(self.get_reg(instr.a));
366 match self.pop_frame(v) {
367 Ok(Some(result)) => return result,
368 Ok(None) => {}
369 Err(fault) => return VmResult::Trap(fault),
370 }
371 }
372 Opcode::Spawn => {
373 let argc = instr.b;
374 let mut args = Vec::with_capacity(argc as usize);
375 for i in 0..argc {
376 args.push(trap!(
385 self.get_reg(trap!(reg_at(instr.a, u16::from(i) + 1)))
386 ));
387 }
388 return VmResult::Spawn { function: instr.imm as u32, args, dest_reg: instr.a };
389 }
390 Opcode::Yield => return VmResult::Yield,
391 Opcode::Sleep => {
392 let millis = trap!(self.get_reg(instr.a));
393 let ms = match millis.as_int() {
394 Some(ms) if ms >= 0 => ms as u64,
395 _ => {
396 return VmResult::Trap(Fault::TypeMismatch {
397 expected: "non-negative int",
398 got: millis.type_name(),
399 })
400 }
401 };
402 return VmResult::Sleep(Duration::from_millis(ms));
403 }
404 Opcode::Exit => {
405 let v = trap!(self.get_reg(instr.a));
406 return VmResult::Complete(v);
407 }
408 Opcode::SelfPid => {
409 return VmResult::SelfPid { dest_reg: instr.a };
410 }
411 Opcode::Send => {
412 let target = trap!(self.get_reg(instr.a));
413 let message = trap!(self.get_reg(instr.b));
414 let cap = match target.as_cap() {
415 Some(c) => c,
416 None => {
417 return VmResult::Trap(Fault::TypeMismatch {
418 expected: "cap",
419 got: target.type_name(),
420 })
421 }
422 };
423 if message.as_message().is_none() {
424 return VmResult::Trap(Fault::TypeMismatch {
425 expected: "message",
426 got: message.type_name(),
427 });
428 }
429 return VmResult::Send {
430 target_cap: cap,
431 message,
432 };
433 }
434 Opcode::Receive => {
435 return VmResult::Receive {
436 dest_reg: instr.a,
437 timeout: None,
438 match_tag: None,
439 };
440 }
441 Opcode::ReceiveTimeout => {
442 let millis = trap!(self.get_reg(instr.b));
443 let ms = match millis.as_int() {
444 Some(n) if n >= 0 => n as u64,
445 _ => 0,
446 };
447 return VmResult::Receive {
448 dest_reg: instr.a,
449 timeout: Some(Duration::from_millis(ms)),
450 match_tag: None,
451 };
452 }
453 Opcode::ReceiveMatch => {
454 let tag_v = trap!(self.get_reg(instr.b));
455 let tag = match tag_from_value(&tag_v) {
456 Ok(t) => t,
457 Err(f) => return VmResult::Trap(f),
458 };
459 return VmResult::Receive {
460 dest_reg: instr.a,
461 timeout: None,
462 match_tag: Some(tag),
463 };
464 }
465 Opcode::ReceiveMatchImm => {
466 let tag = match u16::try_from(instr.imm) {
467 Ok(t) if instr.imm >= 0 => t,
468 _ => {
469 return VmResult::Trap(Fault::TypeMismatch {
470 expected: "tag u16",
471 got: "imm-out-of-range",
472 })
473 }
474 };
475 return VmResult::Receive {
476 dest_reg: instr.a,
477 timeout: None,
478 match_tag: Some(tag),
479 };
480 }
481 Opcode::Ask => {
482 let target = trap!(self.get_reg(instr.b));
483 let request = trap!(self.get_reg(instr.c));
484 let cap = match target.as_cap() {
485 Some(c) => c,
486 None => {
487 return VmResult::Trap(Fault::TypeMismatch {
488 expected: "cap",
489 got: target.type_name(),
490 })
491 }
492 };
493 if request.as_message().is_none() {
494 return VmResult::Trap(Fault::TypeMismatch {
495 expected: "message",
496 got: request.type_name(),
497 });
498 }
499 return VmResult::Ask {
500 dest_reg: instr.a,
501 target_cap: cap,
502 request,
503 };
504 }
505 Opcode::Trap => return VmResult::Trap(Fault::Explicit(instr.imm)),
506 }
507 }
508 VmResult::Yield
509 }
510
511 fn pop_frame(&mut self, value: Value) -> Result<Option<VmResult>, Fault> {
515 let finished = self
516 .frames
517 .pop()
518 .ok_or(Fault::Invariant("pop_frame on empty stack"))?;
519 match finished.dest_reg {
520 Some(dest) => {
521 if self.set_reg(dest, value).is_err() {
526 let frame_size = match self.frames.last() {
527 Some(f) => f.registers.len() as u8,
528 None => 0,
529 };
530 return Ok(Some(VmResult::Trap(Fault::RegisterOutOfRange {
531 reg: dest,
532 frame_size,
533 })));
534 }
535 Ok(None)
536 }
537 None => Ok(Some(VmResult::Complete(value))),
538 }
539 }
540}
541
542#[inline]
552fn reg_at(base: u8, offset: u16) -> Result<u8, Fault> {
553 match u8::try_from(u32::from(base) + u32::from(offset)) {
554 Ok(reg) => Ok(reg),
555 Err(_) => Err(Fault::RegisterIndexOverflow {
556 base,
557 offset: match u8::try_from(offset) {
558 Ok(o) => o,
559 Err(_) => u8::MAX,
560 },
561 }),
562 }
563}
564
565#[inline]
566fn as_f64(v: &Value) -> Result<f64, Fault> {
567 match v {
568 Value::Int(i) => Ok(*i as f64),
569 Value::Float(f) => Ok(*f),
570 other => Err(Fault::TypeMismatch { expected: "int or float", got: other.type_name() }),
571 }
572}
573
574#[inline]
576fn tag_from_value(v: &Value) -> Result<u16, Fault> {
577 match v.as_int() {
578 Some(i) if (0..=i64::from(u16::MAX)).contains(&i) => Ok(i as u16),
579 Some(_) => Err(Fault::TypeMismatch {
580 expected: "tag u16",
581 got: "int-out-of-range",
582 }),
583 None => Err(Fault::TypeMismatch {
584 expected: "int",
585 got: v.type_name(),
586 }),
587 }
588}
589
590#[cfg(test)]
591mod tests {
592 use super::*;
593 use crate::bytecode::ChunkBuilder;
594
595 type TestResult = Result<(), Box<dyn std::error::Error>>;
596
597 #[test]
602 fn spawn_from_the_last_register_traps_instead_of_wrapping() -> TestResult {
603 let mut b = ChunkBuilder::new("t");
604 b.begin_function("main", 0, 2);
605 b.emit_spawn(255, 0, 1);
606 b.emit_return(0);
607 let mut vm = Vm::new(Arc::new(b.finish()), NativeTable::empty(), 0, &[])?;
608 match vm.run(10) {
609 VmResult::Trap(Fault::RegisterIndexOverflow {
610 base: 255,
611 offset: 1,
612 }) => Ok(()),
613 other => Err(format!("expected RegisterIndexOverflow, got {other:?}").into()),
614 }
615 }
616
617 #[test]
621 fn entering_a_function_with_too_few_registers_faults() -> TestResult {
622 let mut b = ChunkBuilder::new("t");
623 b.begin_function("main", 3, 1);
624 b.emit_return(0);
625 let args = [Value::Int(1), Value::Int(2), Value::Int(3)];
626 match Vm::new(Arc::new(b.finish()), NativeTable::empty(), 0, &args) {
627 Err(Fault::RegisterOutOfRange {
628 reg: 1,
629 frame_size: 1,
630 }) => Ok(()),
631 Err(e) => Err(format!("unexpected fault: {e}").into()),
632 Ok(_) => Err("three arguments cannot be loaded into one register".into()),
633 }
634 }
635
636 #[test]
637 fn calling_a_function_with_too_few_registers_traps() -> TestResult {
638 let mut b = ChunkBuilder::new("t");
639 let callee = b.begin_function("callee", 3, 1);
640 b.emit_return(0);
641 let main = b.begin_function("main", 0, 4);
642 b.emit_load_imm(0, 7);
643 b.emit_load_imm(1, 8);
644 b.emit_load_imm(2, 9);
645 b.emit_call(0, callee, 3);
646 b.emit_return(0);
647 let mut vm = Vm::new(Arc::new(b.finish()), NativeTable::empty(), main, &[])?;
648 match vm.run(50) {
649 VmResult::Trap(Fault::RegisterOutOfRange {
650 reg: 1,
651 frame_size: 1,
652 }) => Ok(()),
653 other => Err(format!("expected RegisterOutOfRange, got {other:?}").into()),
654 }
655 }
656
657 #[test]
660 fn gathering_up_to_the_last_register_still_works() -> TestResult {
661 let mut b = ChunkBuilder::new("t");
662 let callee = b.begin_function("callee", 1, 1);
663 b.emit_return(0);
664 let main = b.begin_function("main", 0, 255);
665 b.emit_load_imm(254, 5);
666 b.emit_call(254, callee, 1);
668 b.emit_return(254);
669 let mut vm = Vm::new(Arc::new(b.finish()), NativeTable::empty(), main, &[])?;
670 match vm.run(100) {
671 VmResult::Complete(_) => Ok(()),
672 other => Err(format!("expected completion, got {other:?}").into()),
673 }
674 }
675}