vihaco_cpu/
data.rs

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

vihaco_cpu/
data.rs
