dazzle_core/scheme/
arena.rs

1//! Arena-based value storage with separate mark bitmap
2//!
3//! Simplified design:
4//! - ValueData has no GC-specific fields
5//! - Separate Vec<bool> for GC marks
6//! - Works uniformly for all value types
7
8use std::rc::Rc;
9use crate::scheme::parser::Position;
10use crate::scheme::value::{Unit, SourceInfo};
11use crate::grove;
12
13/// Value identifier - lightweight copyable index
14#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
15pub struct ValueId(pub u32);
16
17/// Special constants
18pub const NIL_ID: ValueId = ValueId(0);
19pub const TRUE_ID: ValueId = ValueId(1);
20pub const FALSE_ID: ValueId = ValueId(2);
21pub const UNSPECIFIED_ID: ValueId = ValueId(3);
22pub const ERROR_ID: ValueId = ValueId(4);
23pub const FIRST_USER_ID: u32 = 5;
24
25/// Value data (no GC fields)
26#[derive(Debug)]
27pub enum ValueData {
28    Nil,
29    Bool(bool),
30    Integer(i64),
31    Real(f64),
32    Quantity { magnitude: f64, unit: Unit },
33    Char(char),
34    String(String),
35    Symbol(Rc<str>),
36    Keyword(Rc<str>),
37    Pair {
38        car: ValueId,
39        cdr: ValueId,
40        pos: Option<Position>,
41    },
42    Vector(Vec<ValueId>),
43    Procedure(ProcedureData),
44    Node(Rc<Box<dyn grove::Node>>),
45    NodeList(Rc<Box<dyn grove::NodeList>>),
46    Sosofo,
47    Unspecified,
48    Error,
49}
50
51/// Procedure data
52pub enum ProcedureData {
53    Primitive {
54        name: &'static str,
55        func: fn(&mut Arena, &[ValueId]) -> Result<ValueId, String>,
56    },
57    Lambda {
58        params: Vec<String>,
59        required_count: usize,
60        optional_defaults: Vec<ValueId>,
61        body: ValueId,
62        env: ValueId,
63        source: Option<SourceInfo>,
64        name: Option<String>,
65    },
66    /// Compiled lambda (bytecode)
67    CompiledLambda {
68        params: Vec<String>,
69        required_count: usize,
70        optional_defaults: Vec<ValueId>,
71        body_ip: usize, // Instruction pointer to lambda body
72        env: ValueId,
73        source: Option<SourceInfo>,
74        name: Option<String>,
75    },
76}
77
78impl std::fmt::Debug for ProcedureData {
79    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
80        match self {
81            ProcedureData::Primitive { name, .. } => {
82                write!(f, "Primitive {{ name: {:?}, func: <fn> }}", name)
83            }
84            ProcedureData::Lambda { params, required_count, name, .. } => {
85                write!(f, "Lambda {{ params: {:?}, required_count: {}, name: {:?}, ... }}", params, required_count, name)
86            }
87            ProcedureData::CompiledLambda { params, required_count, body_ip, name, .. } => {
88                write!(f, "CompiledLambda {{ params: {:?}, required_count: {}, body_ip: {}, name: {:?}, ... }}", params, required_count, body_ip, name)
89            }
90        }
91    }
92}
93
94/// Arena with separate mark bitmap
95pub struct Arena {
96    values: Vec<ValueData>,
97    marks: Vec<bool>,  // Separate mark bitmap
98    free_list: Vec<u32>,
99    next_id: u32,
100    // Grove runtime state
101    pub current_node: Option<Rc<Box<dyn grove::Node>>>,
102    pub grove: Option<Rc<dyn grove::Grove>>,
103}
104
105impl Arena {
106    pub fn new() -> Self {
107        let mut arena = Arena {
108            values: Vec::with_capacity(1024),
109            marks: Vec::with_capacity(1024),
110            free_list: Vec::new(),
111            next_id: FIRST_USER_ID,
112            current_node: None,
113            grove: None,
114        };
115
116        // Pre-allocate constants
117        arena.values.push(ValueData::Nil);
118        arena.marks.push(true);  // Constants always marked
119        arena.values.push(ValueData::Bool(true));
120        arena.marks.push(true);
121        arena.values.push(ValueData::Bool(false));
122        arena.marks.push(true);
123        arena.values.push(ValueData::Unspecified);
124        arena.marks.push(true);
125        arena.values.push(ValueData::Error);
126        arena.marks.push(true);
127
128        arena
129    }
130
131    pub fn alloc(&mut self, data: ValueData) -> ValueId {
132        let id = if let Some(id) = self.free_list.pop() {
133            self.values[id as usize] = data;
134            self.marks[id as usize] = false;
135            id
136        } else {
137            let id = self.next_id;
138            self.next_id += 1;
139            self.values.push(data);
140            self.marks.push(false);
141            id
142        };
143        ValueId(id)
144    }
145
146    #[inline]
147    pub fn get(&self, id: ValueId) -> &ValueData {
148        &self.values[id.0 as usize]
149    }
150
151    #[inline]
152    pub fn get_mut(&mut self, id: ValueId) -> &mut ValueData {
153        &mut self.values[id.0 as usize]
154    }
155
156    #[inline]
157    pub fn cons(&mut self, car: ValueId, cdr: ValueId) -> ValueId {
158        self.alloc(ValueData::Pair { car, cdr, pos: None })
159    }
160
161    #[inline]
162    pub fn cons_with_pos(&mut self, car: ValueId, cdr: ValueId, pos: Position) -> ValueId {
163        self.alloc(ValueData::Pair { car, cdr, pos: Some(pos) })
164    }
165
166    #[inline]
167    pub fn int(&mut self, n: i64) -> ValueId {
168        self.alloc(ValueData::Integer(n))
169    }
170
171    #[inline]
172    pub fn real(&mut self, f: f64) -> ValueId {
173        self.alloc(ValueData::Real(f))
174    }
175
176    #[inline]
177    pub fn string(&mut self, s: String) -> ValueId {
178        self.alloc(ValueData::String(s))
179    }
180
181    #[inline]
182    pub fn symbol(&mut self, s: Rc<str>) -> ValueId {
183        self.alloc(ValueData::Symbol(s))
184    }
185
186    #[inline]
187    pub fn char(&mut self, c: char) -> ValueId {
188        self.alloc(ValueData::Char(c))
189    }
190
191    #[inline]
192    pub fn keyword(&mut self, k: Rc<str>) -> ValueId {
193        self.alloc(ValueData::Keyword(k))
194    }
195
196    #[inline]
197    pub fn vector(&mut self, elements: Vec<ValueId>) -> ValueId {
198        self.alloc(ValueData::Vector(elements))
199    }
200
201    /// Mark phase - mark a value and recursively mark its children
202    fn mark(&mut self, id: ValueId) {
203        let idx = id.0 as usize;
204
205        if self.marks[idx] {
206            return; // Already marked
207        }
208
209        self.marks[idx] = true;
210
211        // Get child IDs to mark
212        let child_ids = match &self.values[idx] {
213            ValueData::Pair { car, cdr, .. } => vec![*car, *cdr],
214            ValueData::Vector(elements) => elements.clone(),
215            ValueData::Procedure(ProcedureData::Lambda {
216                optional_defaults,
217                body,
218                env,
219                ..
220            }) => {
221                let mut ids = optional_defaults.clone();
222                ids.push(*body);
223                ids.push(*env);
224                ids
225            }
226            ValueData::Procedure(ProcedureData::CompiledLambda {
227                optional_defaults,
228                env,
229                ..
230            }) => {
231                let mut ids = optional_defaults.clone();
232                ids.push(*env);
233                ids
234            }
235            _ => vec![],
236        };
237
238        // Recursively mark children
239        for child_id in child_ids {
240            self.mark(child_id);
241        }
242    }
243
244    /// Sweep phase - collect unmarked values
245    fn sweep(&mut self) {
246        for i in FIRST_USER_ID as usize..self.values.len() {
247            if !self.marks[i] {
248                // Unmarked - free it
249                self.values[i] = ValueData::Nil;
250                self.free_list.push(i as u32);
251            } else {
252                // Marked - unmark for next GC
253                self.marks[i] = false;
254            }
255        }
256    }
257
258    /// Garbage collect
259    pub fn gc(&mut self, roots: &[ValueId]) {
260        // Mark phase
261        for root in roots {
262            self.mark(*root);
263        }
264
265        // Sweep phase
266        self.sweep();
267    }
268
269    pub fn len(&self) -> usize {
270        self.values.len() - self.free_list.len()
271    }
272
273    pub fn is_empty(&self) -> bool {
274        self.len() == FIRST_USER_ID as usize
275    }
276}
277
278impl Default for Arena {
279    fn default() -> Self {
280        Self::new()
281    }
282}
283
284#[cfg(test)]
285mod tests {
286    use super::*;
287
288    #[test]
289    fn test_arena_constants() {
290        let arena = Arena::new();
291        assert!(matches!(arena.get(NIL_ID), ValueData::Nil));
292        assert!(matches!(arena.get(TRUE_ID), ValueData::Bool(true)));
293        assert!(matches!(arena.get(FALSE_ID), ValueData::Bool(false)));
294    }
295
296    #[test]
297    fn test_cons() {
298        let mut arena = Arena::new();
299        let one = arena.int(1);
300        let two = arena.int(2);
301        let pair = arena.cons(one, two);
302
303        match arena.get(pair) {
304            ValueData::Pair { car, cdr, .. } => {
305                assert_eq!(*car, one);
306                assert_eq!(*cdr, two);
307            }
308            _ => panic!("Expected pair"),
309        }
310    }
311
312    #[test]
313    fn test_gc_keeps_reachable() {
314        let mut arena = Arena::new();
315
316        let one = arena.int(1);
317        let two = arena.int(2);
318        let pair = arena.cons(one, two);
319
320        arena.gc(&[pair]);
321
322        // Verify values still accessible
323        assert!(matches!(arena.get(pair), ValueData::Pair { .. }));
324        assert!(matches!(arena.get(one), ValueData::Integer(1)));
325        assert!(matches!(arena.get(two), ValueData::Integer(2)));
326    }
327
328    #[test]
329    fn test_gc_collects_unreachable() {
330        let mut arena = Arena::new();
331
332        let one = arena.int(1);
333        let _two = arena.int(2);  // Not referenced
334        let three = arena.int(3);
335        let pair = arena.cons(one, three);
336
337        let before = arena.len();
338        arena.gc(&[pair]);
339        let after = arena.len();
340
341        // Should have collected 'two'
342        assert_eq!(before - after, 1);
343    }
344}
dazzle_core/scheme/arena.rs

dazzle_core/scheme/
arena.rs
