Skip to main content

vihaco_cpu/
data.rs

1// SPDX-FileCopyrightText: 2026 The vihaco Authors
2// SPDX-License-Identifier: MIT
3
4use 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// Keep execution inside the state-owning module so CPU fields need no
15// crate-wide visibility. The component macro scopes implicit fields here.
16#[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        /// Allocate a full heap object,  where the allocation length
102        /// is the capacity.
103        #[pattern = "'heap_alloc $0"]
104        HeapAlloc(u32),
105
106        #[pattern = "'get_item"]
107        GetItem,
108        #[pattern = "'heap_dealloc"]
109        HeapDealloc,
110
111        /// Reserves `n` slots (where `n` is the top value on the stack) that can be
112        /// pushed to.
113        #[pattern = "'heap_reserve"]
114        HeapReserve,
115
116        /// Push to a heap_ref that is below capacity.
117        #[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        /// Pop a heap reference and push the object's current length as a u64.
348        #[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/// Append-only storage with a fixed capacity limit and a current length.
361/// `heap_alloc` creates a full object, and `heap_reserve` creates an empty one.
362/// Appends never overwrite elements or grow the allocation, and reads are
363/// bounded by `values.len()` rather than capacity.
364#[derive(Debug, Default)]
365struct HeapObject {
366    values: Vec<Word>,
367    capacity: usize,
368}
369
370impl Clone for HeapObject {
371    fn clone(&self) -> Self {
372        // Vec::clone may discard spare capacity. Preserve it so appending to a
373        // cloned CPU's heap also needs no allocation.
374        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    /// Allocate a full object; spare Vec capacity does not permit appending.
410    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    /// Allocate an empty object with an exact, fixed element limit.
417    /// Returns an error if its storage cannot be allocated.
418    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    /// Append without reallocating or overwriting existing elements.
425    /// Returns an error for invalid, deallocated, or full objects.
426    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    /// Number of operands above the current frame's reserved locals.
590    /// Before entry, all stack values are available as operands/arguments.
591    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}