tidepool_eval/
heap.rs

1use crate::env::Env;
2use crate::value::{ThunkId, Value};
3use tidepool_repr::CoreExpr;
4
5/// State of a thunk in the thunk store.
6#[derive(Debug, Clone)]
7pub enum ThunkState {
8    /// Not yet evaluated: captured env + expression
9    Unevaluated(Env, CoreExpr),
10    /// Currently being forced (cycle detection)
11    BlackHole,
12    /// Already evaluated to a value
13    Evaluated(Value),
14}
15
16/// Heap trait: thunk allocation and forcing.
17/// The interpreter uses VecHeap. Codegen uses ArenaHeap (from core-heap).
18pub trait Heap {
19    /// Allocate a new thunk. Returns its id.
20    fn alloc(&mut self, env: Env, expr: CoreExpr) -> ThunkId;
21
22    /// Read the current state of a thunk.
23    fn read(&self, id: ThunkId) -> &ThunkState;
24
25    /// Write a new state to a thunk (for force protocol and LetRec back-patching).
26    fn write(&mut self, id: ThunkId, state: ThunkState);
27}
28
29/// Simple Vec-backed heap for the interpreter. No GC.
30#[derive(Debug, Default)]
31pub struct VecHeap {
32    thunks: Vec<ThunkState>,
33}
34
35impl VecHeap {
36    pub fn new() -> Self {
37        Self { thunks: Vec::new() }
38    }
39}
40
41impl Heap for VecHeap {
42    fn alloc(&mut self, env: Env, expr: CoreExpr) -> ThunkId {
43        let id = ThunkId(self.thunks.len() as u32);
44        self.thunks.push(ThunkState::Unevaluated(env, expr));
45        id
46    }
47
48    fn read(&self, id: ThunkId) -> &ThunkState {
49        &self.thunks[id.0 as usize]
50    }
51
52    fn write(&mut self, id: ThunkId, state: ThunkState) {
53        self.thunks[id.0 as usize] = state;
54    }
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60    use tidepool_repr::{CoreFrame, Literal, RecursiveTree, VarId};
61
62    #[test]
63    fn test_vecheap_ops() {
64        let mut heap = VecHeap::new();
65        let env = Env::new();
66        let expr = RecursiveTree {
67            nodes: vec![CoreFrame::Var(VarId(0))],
68        };
69
70        let id1 = heap.alloc(env.clone(), expr.clone());
71        let id2 = heap.alloc(env.clone(), expr.clone());
72        let id3 = heap.alloc(env.clone(), expr.clone());
73
74        assert_eq!(id1.0, 0);
75        assert_eq!(id2.0, 1);
76        assert_eq!(id3.0, 2);
77
78        match heap.read(id1) {
79            ThunkState::Unevaluated(_, _) => (),
80            _ => panic!("Expected Unevaluated"),
81        }
82
83        heap.write(id1, ThunkState::BlackHole);
84        match heap.read(id1) {
85            ThunkState::BlackHole => (),
86            _ => panic!("Expected BlackHole"),
87        }
88
89        let val = Value::Lit(Literal::LitInt(100));
90        heap.write(id1, ThunkState::Evaluated(val));
91        match heap.read(id1) {
92            ThunkState::Evaluated(Value::Lit(Literal::LitInt(100))) => (),
93            _ => panic!("Expected Evaluated(100)"),
94        }
95    }
96
97    #[test]
98    fn test_thunk_state_machine() {
99        let mut heap = VecHeap::new();
100        let env = Env::new();
101        let expr = RecursiveTree {
102            nodes: vec![CoreFrame::Var(VarId(0))],
103        };
104        let id = heap.alloc(env, expr);
105
106        // Unevaluated
107        match heap.read(id) {
108            ThunkState::Unevaluated(_, _) => (),
109            _ => panic!("Expected Unevaluated"),
110        }
111
112        // Force started: Unevaluated -> BlackHole
113        heap.write(id, ThunkState::BlackHole);
114        match heap.read(id) {
115            ThunkState::BlackHole => (),
116            _ => panic!("Expected BlackHole"),
117        }
118
119        // Force complete: BlackHole -> Evaluated
120        let val = Value::Lit(Literal::LitInt(42));
121        heap.write(id, ThunkState::Evaluated(val));
122        match heap.read(id) {
123            ThunkState::Evaluated(_) => (),
124            _ => panic!("Expected Evaluated"),
125        }
126    }
127}
tidepool_eval/heap.rs

tidepool_eval/
heap.rs
