1use crate::Word;
5#[cfg(not(feature = "typed-declarations"))]
6use crate::instruction::SurfaceValue;
7use vihaco::{
8 frame::Frame,
9 traits::{FrameMemory, StackFrame, StackMemory},
10};
11#[cfg(not(feature = "typed-declarations"))]
12use vihaco_parser::Ident;
13
14#[path = "component.rs"]
17pub(crate) mod component;
18#[cfg(not(feature = "typed-declarations"))]
19pub use component::CPUMessage;
20
21#[cfg(not(feature = "typed-declarations"))]
22vihaco::component! {
23 #[derive(Default, Debug)]
24 pub component CPU {
25 pub(crate) frames: Vec<Frame>,
26 heap: Heap,
27 pub(crate) stack: Vec<Word>,
28 pub(crate) span: (u32, u32, u32),
29 pub(crate) pending_pc: Option<u32>,
30 pub(crate) current_pc: u32,
31 pub(crate) return_values: Vec<Word>,
32 }
33
34 type Type = vihaco::Type;
35 value Word = crate::Word;
36
37 instruction {
38 #[pattern = "'span $0 $1 $2"]
39 Span(u32, u32, u32),
40
41 #[pattern = "'label `@` $0"]
42 Label(Ident),
43
44 #[pattern = "'func_start"]
45 FunctionStart,
46
47 #[pattern = "'func_end"]
48 FunctionEnd,
49
50 Breakpoint,
51
52 #[pattern = "'br `@` $0"]
53 Branch(Ident => u32),
54
55 #[pattern = "'cond_br `@` $0 `,` `@` $1"]
56 ConditionalBranch(Ident => u32, Ident => u32),
57
58 #[pattern = "'ret $0"]
59 Return(u32),
60
61 #[pattern = "'call_indirect"]
62 IndirectCall,
63
64 Call(u32, Ident => u32),
65
66 Halt,
67
68 Print,
69
70 #[pattern = "'load_i32 $0"]
71 LoadI32(u32),
72 #[pattern = "'load_i64 $0"]
73 LoadI64(u32),
74 #[pattern = "'load_u32 $0"]
75 LoadU32(u32),
76 #[pattern = "'load_u64 $0"]
77 LoadU64(u32),
78 #[pattern = "'load_f32 $0"]
79 LoadF32(u32),
80 #[pattern = "'load_f64 $0"]
81 LoadF64(u32),
82 #[pattern = "'load_bool $0"]
83 LoadBool(u32),
84 #[pattern = "'store_i32 $0"]
85 StoreI32(u32),
86 #[pattern = "'store_i64 $0"]
87 StoreI64(u32),
88 #[pattern = "'store_u32 $0"]
89 StoreU32(u32),
90 #[pattern = "'store_u64 $0"]
91 StoreU64(u32),
92 #[pattern = "'store_f32 $0"]
93 StoreF32(u32),
94 #[pattern = "'store_f64 $0"]
95 StoreF64(u32),
96 #[pattern = "'store_bool $0"]
97 StoreBool(u32),
98
99 Dup,
100
101 #[pattern = "'heap_alloc $0"]
104 HeapAlloc(u32),
105
106 #[pattern = "'get_item"]
107 GetItem,
108 #[pattern = "'heap_dealloc"]
109 HeapDealloc,
110
111 #[pattern = "'heap_reserve"]
114 HeapReserve,
115
116 #[pattern = "'heap_push"]
118 HeapPush,
119
120 #[pattern = "'const_i32 $0"]
121 ConstI32(SurfaceValue => Word),
122 #[pattern = "'const_i64 $0"]
123 ConstI64(SurfaceValue => Word),
124 #[pattern = "'const_u32 $0"]
125 ConstU32(SurfaceValue => Word),
126 #[pattern = "'const_u64 $0"]
127 ConstU64(SurfaceValue => Word),
128 #[pattern = "'const_f32 $0"]
129 ConstF32(SurfaceValue => Word),
130 #[pattern = "'const_f64 $0"]
131 ConstF64(SurfaceValue => Word),
132 #[pattern = "'const_bool $0"]
133 ConstBool(SurfaceValue => Word),
134 #[pattern = "'const_string $0"]
135 ConstString(SurfaceValue => Word),
136 #[pattern = "'const_fn_ref $0"]
137 ConstFunctionRef(SurfaceValue => Word),
138 #[pattern = "'const_heap_ref $0"]
139 ConstHeapRef(SurfaceValue => Word),
140
141 #[pattern = "'add_i32"]
142 AddI32,
143 #[pattern = "'add_f32"]
144 AddF32,
145 #[pattern = "'add_i64"]
146 AddI64,
147 #[pattern = "'add_u32"]
148 AddU32,
149 #[pattern = "'add_u64"]
150 AddU64,
151 #[pattern = "'add_f64"]
152 AddF64,
153 #[pattern = "'sub_i32"]
154 SubI32,
155 #[pattern = "'sub_i64"]
156 SubI64,
157 #[pattern = "'sub_u32"]
158 SubU32,
159 #[pattern = "'sub_u64"]
160 SubU64,
161 #[pattern = "'sub_f32"]
162 SubF32,
163 #[pattern = "'sub_f64"]
164 SubF64,
165 #[pattern = "'mul_i32"]
166 MulI32,
167 #[pattern = "'mul_i64"]
168 MulI64,
169 #[pattern = "'mul_u32"]
170 MulU32,
171 #[pattern = "'mul_u64"]
172 MulU64,
173 #[pattern = "'mul_f32"]
174 MulF32,
175 #[pattern = "'mul_f64"]
176 MulF64,
177 #[pattern = "'div_i32"]
178 DivI32,
179 #[pattern = "'div_i64"]
180 DivI64,
181 #[pattern = "'div_u32"]
182 DivU32,
183 #[pattern = "'div_u64"]
184 DivU64,
185 #[pattern = "'div_f32"]
186 DivF32,
187 #[pattern = "'div_f64"]
188 DivF64,
189 #[pattern = "'rem_i32"]
190 RemI32,
191 #[pattern = "'rem_i64"]
192 RemI64,
193 #[pattern = "'rem_u32"]
194 RemU32,
195 #[pattern = "'rem_u64"]
196 RemU64,
197 #[pattern = "'rem_f32"]
198 RemF32,
199 #[pattern = "'rem_f64"]
200 RemF64,
201 #[pattern = "'neg_i32"]
202 NegI32,
203 #[pattern = "'neg_i64"]
204 NegI64,
205 #[pattern = "'neg_f32"]
206 NegF32,
207 #[pattern = "'neg_f64"]
208 NegF64,
209 #[pattern = "'shl_i32"]
210 ShlI32,
211 #[pattern = "'shl_i64"]
212 ShlI64,
213 #[pattern = "'shl_u32"]
214 ShlU32,
215 #[pattern = "'shl_u64"]
216 ShlU64,
217 #[pattern = "'shr_i32"]
218 ShrI32,
219 #[pattern = "'shr_i64"]
220 ShrI64,
221 #[pattern = "'shr_u32"]
222 ShrU32,
223 #[pattern = "'shr_u64"]
224 ShrU64,
225 #[pattern = "'rol_i32"]
226 RolI32,
227 #[pattern = "'rol_i64"]
228 RolI64,
229 #[pattern = "'rol_u32"]
230 RolU32,
231 #[pattern = "'rol_u64"]
232 RolU64,
233 #[pattern = "'ror_i32"]
234 RorI32,
235 #[pattern = "'ror_i64"]
236 RorI64,
237 #[pattern = "'ror_u32"]
238 RorU32,
239 #[pattern = "'ror_u64"]
240 RorU64,
241 #[pattern = "'bitand_i32"]
242 BitAndI32,
243 #[pattern = "'bitand_i64"]
244 BitAndI64,
245 #[pattern = "'bitand_u32"]
246 BitAndU32,
247 #[pattern = "'bitand_u64"]
248 BitAndU64,
249 #[pattern = "'bitor_i32"]
250 BitOrI32,
251 #[pattern = "'bitor_i64"]
252 BitOrI64,
253 #[pattern = "'bitor_u32"]
254 BitOrU32,
255 #[pattern = "'bitor_u64"]
256 BitOrU64,
257 #[pattern = "'bitxor_i32"]
258 BitXorI32,
259 #[pattern = "'bitxor_i64"]
260 BitXorI64,
261 #[pattern = "'bitxor_u32"]
262 BitXorU32,
263 #[pattern = "'bitxor_u64"]
264 BitXorU64,
265
266 Not,
267
268 And,
269
270 Or,
271
272 Xor,
273
274 #[pattern = "'eq_i32"]
275 EqI32,
276 #[pattern = "'eq_i64"]
277 EqI64,
278 #[pattern = "'eq_u32"]
279 EqU32,
280 #[pattern = "'eq_u64"]
281 EqU64,
282 #[pattern = "'eq_f32"]
283 EqF32,
284 #[pattern = "'eq_f64"]
285 EqF64,
286 #[pattern = "'ne_i32"]
287 NeI32,
288 #[pattern = "'ne_i64"]
289 NeI64,
290 #[pattern = "'ne_u32"]
291 NeU32,
292 #[pattern = "'ne_u64"]
293 NeU64,
294 #[pattern = "'ne_f32"]
295 NeF32,
296 #[pattern = "'ne_f64"]
297 NeF64,
298 #[pattern = "'lt_i32"]
299 LtI32,
300 #[pattern = "'lt_i64"]
301 LtI64,
302 #[pattern = "'lt_u32"]
303 LtU32,
304 #[pattern = "'lt_u64"]
305 LtU64,
306 #[pattern = "'lt_f32"]
307 LtF32,
308 #[pattern = "'lt_f64"]
309 LtF64,
310 #[pattern = "'gt_i32"]
311 GtI32,
312 #[pattern = "'gt_i64"]
313 GtI64,
314 #[pattern = "'gt_u32"]
315 GtU32,
316 #[pattern = "'gt_u64"]
317 GtU64,
318 #[pattern = "'gt_f32"]
319 GtF32,
320 #[pattern = "'gt_f64"]
321 GtF64,
322 #[pattern = "'le_i32"]
323 LeI32,
324 #[pattern = "'le_i64"]
325 LeI64,
326 #[pattern = "'le_u32"]
327 LeU32,
328 #[pattern = "'le_u64"]
329 LeU64,
330 #[pattern = "'le_f32"]
331 LeF32,
332 #[pattern = "'le_f64"]
333 LeF64,
334 #[pattern = "'ge_i32"]
335 GeI32,
336 #[pattern = "'ge_i64"]
337 GeI64,
338 #[pattern = "'ge_u32"]
339 GeU32,
340 #[pattern = "'ge_u64"]
341 GeU64,
342 #[pattern = "'ge_f32"]
343 GeF32,
344 #[pattern = "'ge_f64"]
345 GeF64,
346
347 #[pattern = "'heap_len"]
349 HeapLen,
350 }
351}
352
353#[cfg(not(feature = "typed-declarations"))]
354pub use cpu::CPU;
355#[cfg(not(feature = "typed-declarations"))]
356pub use cpu::runtime::Instruction as RuntimeInstruction;
357#[cfg(not(feature = "typed-declarations"))]
358pub use cpu::syntax::Instruction as SurfaceInstruction;
359
360#[derive(Debug, Default)]
365struct HeapObject {
366 values: Vec<Word>,
367 capacity: usize,
368}
369
370impl Clone for HeapObject {
371 fn clone(&self) -> Self {
372 let mut values = Vec::with_capacity(self.capacity);
375 values.extend_from_slice(&self.values);
376 Self {
377 values,
378 capacity: self.capacity,
379 }
380 }
381}
382
383#[derive(Debug, Clone)]
384enum HeapSlot {
385 Alive(HeapObject),
386 Deallocated,
387}
388#[cfg(feature = "typed-declarations")]
389#[vihaco::component]
390#[instructions { crate::cpu }]
391#[derive(Default, Debug)]
392pub struct CPU {
393 pub(crate) frames: Vec<Frame>,
394 heap: Heap,
395 pub(crate) stack: Vec<Word>,
396 pub(crate) span: (u32, u32, u32),
397 pub(crate) pending_pc: Option<u32>,
398 pub(crate) current_pc: u32,
399 pub(crate) return_values: Vec<Word>,
400}
401
402#[derive(Debug, Clone, Default)]
403struct Heap {
404 slots: Vec<HeapSlot>,
405 free_list: Vec<u32>,
406}
407
408impl Heap {
409 pub(crate) fn alloc(&mut self, values: impl Into<Vec<Word>>) -> u32 {
411 let values = values.into();
412 let capacity = values.len();
413 self.insert(HeapObject { values, capacity })
414 }
415
416 pub(crate) fn reserve(&mut self, capacity: usize) -> eyre::Result<u32> {
419 let mut values = Vec::new();
420 values.try_reserve_exact(capacity)?;
421 Ok(self.insert(HeapObject { values, capacity }))
422 }
423
424 pub(crate) fn push(&mut self, id: u32, value: Word) -> eyre::Result<()> {
427 let object = match self.slots.get_mut(id as usize) {
428 Some(HeapSlot::Alive(object)) => object,
429 Some(HeapSlot::Deallocated) => {
430 return Err(eyre::eyre!("heap object {} has been deallocated", id));
431 }
432 None => return Err(eyre::eyre!("invalid heap object id {}", id)),
433 };
434 eyre::ensure!(
435 object.values.len() < object.capacity,
436 "heap object {} is full (capacity {})",
437 id,
438 object.capacity
439 );
440 object.values.push(value);
441 Ok(())
442 }
443
444 pub(crate) fn insert(&mut self, object: HeapObject) -> u32 {
445 if let Some(id) = self.free_list.pop() {
446 self.slots[id as usize] = HeapSlot::Alive(object);
447 id
448 } else {
449 let id = self.slots.len() as u32;
450 self.slots.push(HeapSlot::Alive(object));
451 id
452 }
453 }
454
455 pub(crate) fn dealloc(&mut self, id: u32) -> eyre::Result<()> {
456 match self.slots.get_mut(id as usize) {
457 Some(slot @ HeapSlot::Alive(_)) => {
458 *slot = HeapSlot::Deallocated;
459 self.free_list.push(id);
460 Ok(())
461 }
462 Some(HeapSlot::Deallocated) => Err(eyre::eyre!(
463 "double-free: heap object {} already deallocated",
464 id
465 )),
466 None => Err(eyre::eyre!("invalid heap object id {}", id)),
467 }
468 }
469
470 fn get(&self, id: u32) -> eyre::Result<&[Word]> {
471 match self.slots.get(id as usize) {
472 Some(HeapSlot::Alive(object)) => Ok(&object.values),
473 Some(HeapSlot::Deallocated) => {
474 Err(eyre::eyre!("heap object {} has been deallocated", id))
475 }
476 None => Err(eyre::eyre!("invalid heap object id {}", id)),
477 }
478 }
479
480 fn clear(&mut self) {
481 self.slots.clear();
482 self.free_list.clear();
483 }
484
485 #[cfg(test)]
486 pub fn is_empty(&self) -> bool {
487 self.slots.is_empty()
488 }
489}
490
491impl StackMemory for CPU {
492 type Value = Word;
493
494 fn stack(&self) -> &Vec<Self::Value> {
495 &self.stack
496 }
497
498 fn stack_mut(&mut self) -> &mut Vec<Self::Value> {
499 &mut self.stack
500 }
501
502 fn stack_is_empty(&self) -> bool {
503 self.stack.is_empty()
504 }
505
506 fn stack_len(&self) -> usize {
507 self.stack.len()
508 }
509
510 fn stack_get(&self, pos: usize) -> eyre::Result<&Self::Value> {
511 self.stack
512 .get(pos)
513 .ok_or_else(|| eyre::eyre!("stack underflow"))
514 }
515
516 fn stack_get_mut(&mut self, pos: usize) -> eyre::Result<&mut Self::Value> {
517 self.stack
518 .get_mut(pos)
519 .ok_or_else(|| eyre::eyre!("stack underflow"))
520 }
521
522 fn stack_pop(&mut self) -> eyre::Result<Self::Value> {
523 self.require_operands(1)?;
524 self.stack
525 .pop()
526 .ok_or_else(|| eyre::eyre!("stack underflow"))
527 }
528
529 fn stack_push<T: Into<Self::Value>>(&mut self, v: T) {
530 self.stack.push(v.into());
531 }
532
533 fn stack_top(&self) -> eyre::Result<&Self::Value> {
534 self.require_operands(1)?;
535 self.stack_get(self.stack.len() - 1)
536 }
537
538 fn stack_top_mut(&mut self) -> eyre::Result<&mut Self::Value> {
539 self.require_operands(1)?;
540 self.stack_get_mut(self.stack.len() - 1)
541 }
542}
543
544impl StackFrame for CPU {
545 fn get_frame(&self) -> eyre::Result<&Frame> {
546 self.frames
547 .last()
548 .ok_or_else(|| eyre::eyre!("no current frame"))
549 }
550
551 fn get_frame_mut(&mut self) -> eyre::Result<&mut Frame> {
552 self.frames
553 .last_mut()
554 .ok_or_else(|| eyre::eyre!("no current frame"))
555 }
556
557 fn push_frame(&mut self, frame: Frame) {
558 self.frames.push(frame);
559 }
560
561 fn pop_frame(&mut self) -> eyre::Result<Frame> {
562 self.frames
563 .pop()
564 .ok_or_else(|| eyre::eyre!("no frame to pop"))
565 }
566}
567
568impl FrameMemory for CPU {
569 fn frame_base(&self) -> eyre::Result<usize> {
570 self.get_frame().map(|f| f.base)
571 }
572
573 fn get_local(&self, index: usize) -> eyre::Result<&Self::Value> {
574 let address = self.local_address(index)?;
575 self.stack
576 .get(address)
577 .ok_or_else(|| eyre::eyre!("local index out of bounds"))
578 }
579
580 fn get_local_mut(&mut self, index: usize) -> eyre::Result<&mut Self::Value> {
581 let address = self.local_address(index)?;
582 self.stack
583 .get_mut(address)
584 .ok_or_else(|| eyre::eyre!("local index out of bounds"))
585 }
586}
587
588impl CPU {
589 pub fn operand_count(&self) -> usize {
592 let start = self.frames.last().map_or(0, Frame::operands_index);
593 self.stack.len().saturating_sub(start)
594 }
595
596 #[inline(always)]
597 pub(crate) fn require_operands(&self, count: usize) -> eyre::Result<()> {
598 eyre::ensure!(self.operand_count() >= count, "stack underflow");
599 Ok(())
600 }
601
602 pub(crate) fn ensure_local_count_is_at_least_arity(
603 &self,
604 arity: u32,
605 count: u32,
606 ) -> eyre::Result<()> {
607 eyre::ensure!(
608 count >= arity,
609 "local count includes arity, count must be at least arity"
610 );
611 Ok(())
612 }
613
614 pub(crate) fn local_address(&self, index: usize) -> eyre::Result<usize> {
615 let frame = self.get_frame()?;
616 eyre::ensure!(index < frame.local_count, "local index out of bounds");
617 frame
618 .base
619 .checked_add(index)
620 .ok_or_else(|| eyre::eyre!("local address overflow"))
621 }
622
623 pub(crate) fn push_heap_object(&mut self, values: impl Into<Vec<Word>>) -> u32 {
624 self.heap.alloc(values)
625 }
626
627 pub(crate) fn heap_object(&self, id: u32) -> eyre::Result<&[Word]> {
628 self.heap.get(id)
629 }
630
631 #[cfg(feature = "typed-declarations")]
632 pub(crate) fn reserve_heap_object(&mut self, capacity: usize) -> eyre::Result<u32> {
633 self.heap.reserve(capacity)
634 }
635
636 #[cfg(feature = "typed-declarations")]
637 pub(crate) fn append_heap_object(&mut self, id: u32, value: Word) -> eyre::Result<()> {
638 self.heap.push(id, value)
639 }
640
641 pub(crate) fn dealloc_heap_object(&mut self, id: u32) -> eyre::Result<()> {
642 self.heap.dealloc(id)
643 }
644
645 pub(crate) fn clear_heap(&mut self) {
646 self.heap.clear();
647 }
648
649 #[cfg(test)]
650 pub(crate) fn heap_is_empty(&self) -> bool {
651 self.heap.is_empty()
652 }
653
654 pub fn take_pending_pc(&mut self) -> Option<u32> {
655 self.pending_pc.take()
656 }
657
658 pub(crate) fn set_pending_pc(&mut self, pc: u32) {
659 self.pending_pc = Some(pc);
660 }
661
662 pub(crate) fn clear_pending_pc(&mut self) {
663 self.pending_pc = None;
664 }
665
666 pub fn set_current_pc(&mut self, pc: u32) {
667 self.current_pc = pc;
668 }
669
670 pub fn return_values(&self) -> &[Word] {
671 &self.return_values
672 }
673
674 pub(crate) fn set_return_values(&mut self, values: Vec<Word>) {
675 self.return_values = values;
676 }
677}
678
679#[cfg(test)]
680mod heap_tests {
681 use super::Heap;
682
683 #[test]
684 fn allocated_objects_are_full_even_with_spare_vec_capacity() {
685 let mut heap = Heap::default();
686 let mut values = Vec::with_capacity(8);
687 values.push(1);
688 let id = heap.alloc(values);
689 assert!(heap.push(id, 2).unwrap_err().to_string().contains("full"));
690 assert_eq!(heap.get(id).unwrap(), &[1]);
691 }
692
693 #[test]
694 fn cloned_heap_preserves_append_capacity_without_reallocation() {
695 let mut heap = Heap::default();
696 let id = heap.reserve(3).unwrap();
697 heap.push(id, 1).unwrap();
698 let mut cloned = heap.clone();
699 for heap in [&mut heap, &mut cloned] {
700 let storage = heap.get(id).unwrap().as_ptr();
701 heap.push(id, 2).unwrap();
702 heap.push(id, 3).unwrap();
703 assert_eq!(heap.get(id).unwrap().as_ptr(), storage);
704 assert_eq!(heap.get(id).unwrap(), &[1, 2, 3]);
705 assert!(heap.push(id, 4).is_err());
706 }
707 }
708}