slvm/
heap.rs

1use std::sync::Arc;
2
3use crate::bits::FLAG_MUT;
4use crate::{Chunk, FxHashMap, Interned, VMError, VMResult, Value, get_code};
5pub mod handle;
6pub use crate::handle::Handle;
7use crate::heap::io::HeapIo;
8use crate::heap::storage::Storage;
9use crate::vm_hashmap::VMHashMap;
10
11pub mod bits;
12pub mod io;
13mod storage;
14pub mod vm_hashmap;
15
16#[derive(Clone, Debug)]
17pub struct CallFrame {
18    pub id: usize,
19    pub chunk: Arc<Chunk>,
20    pub ip: *const u8,
21    pub current_ip: *const u8,
22    pub stack_top: usize,
23    pub this_fn: Option<Value>,
24    pub defers: Vec<Value>,
25    pub on_error: Option<Value>,
26    pub called: Value,
27}
28
29impl CallFrame {
30    /// Return the line number that corresponds to the current_ip if available.
31    pub fn current_line(&self) -> Option<u32> {
32        let offset = unsafe { self.current_ip.offset_from(get_code!(self.chunk)) as usize };
33        self.chunk.offset_to_line(offset)
34    }
35
36    /// Return the current offset (IP) for the frame using current_ip.
37    pub fn current_offset(&self) -> usize {
38        unsafe { self.current_ip.offset_from(get_code!(self.chunk)) as usize }
39    }
40}
41
42#[derive(Clone, Debug)]
43pub struct Continuation {
44    pub frame: CallFrame,
45    pub arg_reg: usize,
46    pub stack: Vec<Value>,
47}
48
49// This is anything that can live on the heap.  Values normally live on the
50// stack or as constants.
51#[derive(Clone, Debug)]
52enum Object {
53    String(Arc<String>),
54    Vector(Arc<Vec<Value>>),
55    Map(Arc<VMHashMap>),
56    Bytes(Arc<Vec<u8>>),
57
58    // Everything below here is always read only.
59    Lambda(Arc<Chunk>),
60    Closure(Arc<(Arc<Chunk>, Vec<Handle>)>),
61    // Place holder for an empty object slot.
62    Empty,
63}
64
65#[derive(Clone, Copy)]
66pub struct Error {
67    pub keyword: Interned,
68    pub data: Value,
69}
70
71pub enum MutState {
72    Mutable,
73    Immutable,
74}
75
76impl MutState {
77    fn flag(&self) -> u8 {
78        match self {
79            Self::Mutable => FLAG_MUT,
80            Self::Immutable => 0,
81        }
82    }
83}
84
85//#[derive(Debug)]
86pub struct Heap {
87    objects: Storage<Object>,
88    callframes: Storage<CallFrame>,
89    continuations: Storage<Continuation>,
90    errors: Storage<Error>,
91    pairs: Storage<(Value, Value)>,
92    values: Storage<Value>,
93    ios: Storage<HeapIo>,
94    props: Option<FxHashMap<Value, Arc<FxHashMap<Interned, Value>>>>,
95    greys: Vec<Value>,
96    paused: u32,
97}
98
99impl Default for Heap {
100    fn default() -> Self {
101        Self::new()
102    }
103}
104
105macro_rules! value_op {
106    ($heap:expr, $val:expr, $op:ident, $default:expr) => {{
107        match $val {
108            $crate::Value::CharClusterLong(handle) => $heap.objects.$op(handle.idx()),
109            $crate::Value::String(handle) => $heap.objects.$op(handle.idx()),
110            $crate::Value::Vector(handle) => $heap.objects.$op(handle.idx()),
111            $crate::Value::Map(handle) => $heap.objects.$op(handle.idx()),
112            $crate::Value::Bytes(handle) => $heap.objects.$op(handle.idx()),
113            $crate::Value::Pair(handle) => $heap.pairs.$op(handle.idx()),
114            $crate::Value::List(handle, _) => $heap.objects.$op(handle.idx()),
115            $crate::Value::Lambda(handle) => $heap.objects.$op(handle.idx()),
116            $crate::Value::Closure(handle) => $heap.objects.$op(handle.idx()),
117            $crate::Value::Continuation(handle) => $heap.continuations.$op(handle.idx()),
118            $crate::Value::CallFrame(handle) => $heap.callframes.$op(handle.idx()),
119            $crate::Value::Value(handle) => $heap.values.$op(handle.idx()),
120
121            $crate::Value::Error(handle) => $heap.errors.$op(handle.idx()),
122            $crate::Value::Io(handle) => $heap.ios.$op(handle.idx()),
123
124            $crate::Value::Byte(_)
125            | $crate::Value::Int(_)
126            | $crate::Value::Float(_)
127            | $crate::Value::CodePoint(_)
128            | $crate::Value::CharCluster(_, _)
129            | $crate::Value::Symbol(_)
130            | $crate::Value::Keyword(_)
131            | $crate::Value::StringConst(_)
132            | $crate::Value::Special(_)
133            | $crate::Value::Builtin(_)
134            | $crate::Value::True
135            | $crate::Value::False
136            | $crate::Value::Nil
137            | $crate::Value::Undefined => $default,
138        }
139    }};
140}
141
142macro_rules! mark {
143    ($heap:expr, $val:expr) => {{
144        value_op!($heap, $val, mark, ());
145    }};
146}
147
148impl Heap {
149    pub fn new() -> Self {
150        Heap {
151            objects: Storage::default(),
152            callframes: Storage::default(),
153            continuations: Storage::default(),
154            errors: Storage::default(),
155            pairs: Storage::default(),
156            values: Storage::default(),
157            ios: Storage::default(),
158            props: Some(FxHashMap::default()),
159            greys: vec![],
160            paused: 0,
161        }
162    }
163
164    fn props(&self) -> &FxHashMap<Value, Arc<FxHashMap<Interned, Value>>> {
165        self.props.as_ref().expect("missing heap properties")
166    }
167
168    fn props_mut(&mut self) -> &mut FxHashMap<Value, Arc<FxHashMap<Interned, Value>>> {
169        self.props.as_mut().expect("missing heap properties")
170    }
171
172    pub fn sizeof_object() -> usize {
173        std::mem::size_of::<Object>()
174    }
175
176    /// Pause garbage collection.
177    /// Each pause_gc must have an unpause_gc before GC resumes (it is a counter that must be 0).
178    pub fn pause_gc(&mut self) {
179        self.paused += 1;
180    }
181
182    /// UnPause garbage collection.
183    /// Each pause_gc must have an unpause_gc before GC resumes (it is a counter that must be 0).
184    pub fn unpause_gc(&mut self) {
185        self.paused -= 1;
186    }
187
188    pub fn set_grow_factor(&mut self, grow_factor: f64) {
189        self.objects.set_grow_factor(grow_factor);
190    }
191
192    fn alloc<MarkFunc>(&mut self, obj: Object, flags: u8, mark_roots: MarkFunc) -> Handle
193    where
194        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
195    {
196        if self.objects.live_objects() >= self.objects.capacity() && self.paused == 0 {
197            self.collect(mark_roots);
198        }
199        Handle::new32(self.objects.alloc(obj, flags))
200    }
201
202    pub fn alloc_pair<MarkFunc>(
203        &mut self,
204        car: Value,
205        cdr: Value,
206        mutable: MutState,
207        mark_roots: MarkFunc,
208    ) -> Value
209    where
210        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
211    {
212        if self.pairs.live_objects() >= self.pairs.capacity() && self.paused == 0 {
213            self.collect(mark_roots);
214        }
215        Value::Pair(self.pairs.alloc((car, cdr), mutable.flag()).into())
216    }
217
218    pub fn alloc_string<MarkFunc>(
219        &mut self,
220        s: String,
221        mutable: MutState,
222        mark_roots: MarkFunc,
223    ) -> Value
224    where
225        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
226    {
227        Value::String(self.alloc(Object::String(Arc::new(s)), mutable.flag(), mark_roots))
228    }
229
230    pub fn alloc_vector<MarkFunc>(
231        &mut self,
232        v: Vec<Value>,
233        mutable: MutState,
234        mark_roots: MarkFunc,
235    ) -> Value
236    where
237        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
238    {
239        Value::Vector(self.alloc(Object::Vector(Arc::new(v)), mutable.flag(), mark_roots))
240        //Value::Vector(self.alloc(Object::Vector(v), mutable.flag(), mark_roots))
241    }
242
243    pub fn alloc_map<MarkFunc>(
244        &mut self,
245        map: VMHashMap,
246        mutable: MutState,
247        mark_roots: MarkFunc,
248    ) -> Value
249    where
250        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
251    {
252        Value::Map(self.alloc(Object::Map(Arc::new(map)), mutable.flag(), mark_roots))
253    }
254
255    pub fn alloc_bytes<MarkFunc>(
256        &mut self,
257        v: Vec<u8>,
258        mutable: MutState,
259        mark_roots: MarkFunc,
260    ) -> Value
261    where
262        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
263    {
264        Value::Bytes(self.alloc(Object::Bytes(Arc::new(v)), mutable.flag(), mark_roots))
265    }
266
267    pub fn alloc_lambda<MarkFunc>(&mut self, l: Arc<Chunk>, mark_roots: MarkFunc) -> Value
268    where
269        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
270    {
271        Value::Lambda(self.alloc(Object::Lambda(l), 0, mark_roots))
272    }
273
274    pub fn alloc_closure<MarkFunc>(
275        &mut self,
276        l: Arc<Chunk>,
277        v: Vec<Handle>,
278        mark_roots: MarkFunc,
279    ) -> Value
280    where
281        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
282    {
283        Value::Closure(self.alloc(Object::Closure(Arc::new((l, v))), 0, mark_roots))
284    }
285
286    pub fn alloc_continuation<MarkFunc>(&mut self, k: Continuation, mark_roots: MarkFunc) -> Value
287    where
288        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
289    {
290        if self.continuations.live_objects() >= self.continuations.capacity() && self.paused == 0 {
291            self.collect(mark_roots);
292        }
293        Value::Continuation(Handle::new32(self.continuations.alloc(k, 0)))
294    }
295
296    pub fn alloc_callframe<MarkFunc>(&mut self, frame: CallFrame, mark_roots: MarkFunc) -> Value
297    where
298        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
299    {
300        if self.callframes.live_objects() >= self.callframes.capacity() && self.paused == 0 {
301            self.collect(mark_roots);
302        }
303        Value::CallFrame(Handle::new32(self.callframes.alloc(frame, 0)))
304    }
305
306    pub fn alloc_value<MarkFunc>(
307        &mut self,
308        val: Value,
309        mutable: MutState,
310        mark_roots: MarkFunc,
311    ) -> Value
312    where
313        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
314    {
315        if self.values.live_objects() >= self.values.capacity() && self.paused == 0 {
316            self.collect(mark_roots);
317        }
318        Value::Value(self.values.alloc(val, mutable.flag()).into())
319    }
320
321    pub fn alloc_error<MarkFunc>(
322        &mut self,
323        error: Error,
324        mutable: MutState,
325        mark_roots: MarkFunc,
326    ) -> Value
327    where
328        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
329    {
330        if self.errors.live_objects() >= self.errors.capacity() && self.paused == 0 {
331            self.collect(mark_roots);
332        }
333        Value::Error(self.errors.alloc(error, mutable.flag()).into())
334    }
335
336    pub fn alloc_io<MarkFunc>(
337        &mut self,
338        io: HeapIo,
339        mutable: MutState,
340        mark_roots: MarkFunc,
341    ) -> Value
342    where
343        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
344    {
345        if self.ios.live_objects() >= self.ios.capacity() && self.paused == 0 {
346            self.collect(mark_roots);
347        }
348        Value::Io(self.ios.alloc(io, mutable.flag()).into())
349    }
350
351    pub fn get_string(&self, handle: Handle) -> &str {
352        if let Some(Object::String(ptr)) = self.objects.get(handle.idx()) {
353            ptr
354        } else {
355            panic!("Handle {} is not a string!", handle.idx());
356        }
357    }
358
359    pub fn get_string_mut(&mut self, handle: Handle) -> VMResult<&mut String> {
360        if !self.objects.is_mutable(handle.idx()) {
361            return Err(VMError::new_heap("String is not mutable!"));
362        }
363        if let Some(Object::String(ptr)) = self.objects.get_mut(handle.idx()) {
364            Ok(Arc::make_mut(ptr))
365        } else {
366            panic!("Handle {} is not a string!", handle.idx());
367        }
368    }
369
370    pub fn get_vector(&self, handle: Handle) -> &[Value] {
371        if let Some(Object::Vector(v)) = self.objects.get(handle.idx()) {
372            v
373        } else {
374            panic!("Handle {} is not a vector!", handle.idx());
375        }
376    }
377
378    pub fn get_vector_mut(&mut self, handle: Handle) -> VMResult<&mut Vec<Value>> {
379        if !self.objects.is_mutable(handle.idx()) {
380            return Err(VMError::new_heap("Vector is not mutable!"));
381        }
382        if let Some(Object::Vector(v)) = self.objects.get_mut(handle.idx()) {
383            Ok(Arc::make_mut(v))
384        } else {
385            panic!("Handle {} is not a vector!", handle.idx());
386        }
387    }
388
389    pub fn get_map(&self, handle: Handle) -> &VMHashMap {
390        if let Some(Object::Map(map)) = self.objects.get(handle.idx()) {
391            map
392        } else {
393            panic!("Handle {} is not a map!", handle.idx());
394        }
395    }
396
397    pub fn get_map_mut(&mut self, handle: Handle) -> VMResult<&mut VMHashMap> {
398        if !self.objects.is_mutable(handle.idx()) {
399            return Err(VMError::new_heap("Map is not mutable!"));
400        }
401        if let Some(Object::Map(map)) = self.objects.get_mut(handle.idx()) {
402            Ok(Arc::make_mut(map))
403        } else {
404            panic!("Handle {} is not a map!", handle.idx());
405        }
406    }
407
408    pub fn get_bytes(&self, handle: Handle) -> &[u8] {
409        if let Some(Object::Bytes(v)) = self.objects.get(handle.idx()) {
410            v
411        } else {
412            panic!("Handle {} is not bytes!", handle.idx());
413        }
414    }
415
416    pub fn get_pair(&self, handle: Handle) -> (Value, Value) {
417        if let Some(pair) = self.pairs.get(handle.idx()) {
418            (pair.0, pair.1)
419        } else {
420            panic!("Handle {} is not a pair!", handle.idx());
421        }
422    }
423
424    pub fn get_pair_mut(&mut self, handle: Handle) -> VMResult<(&mut Value, &mut Value)> {
425        if !self.pairs.is_mutable(handle.idx()) {
426            return Err(VMError::new_heap("Pair is not mutable!"));
427        }
428        if let Some(pair) = self.pairs.get_mut(handle.idx()) {
429            Ok((&mut pair.0, &mut pair.1))
430        } else {
431            panic!("Handle {} is not a pair!", handle.idx());
432        }
433    }
434
435    pub fn get_pair_mut_override(&mut self, handle: Handle) -> (&mut Value, &mut Value) {
436        if let Some(pair) = self.pairs.get_mut(handle.idx()) {
437            (&mut pair.0, &mut pair.1)
438        } else {
439            panic!("Handle {} is not a pair!", handle.idx());
440        }
441    }
442
443    pub fn get_lambda(&self, handle: Handle) -> Arc<Chunk> {
444        if let Some(Object::Lambda(lambda)) = self.objects.get(handle.idx()) {
445            lambda.clone()
446        } else {
447            panic!("Handle {} is not a lambda!", handle.idx());
448        }
449    }
450
451    pub fn get_closure(&self, handle: Handle) -> (Arc<Chunk>, &[Handle]) {
452        if let Some(Object::Closure(clos))/*lambda, captures))*/ = self.objects.get(handle.idx()) {
453            (clos.0.clone(), &clos.1)
454        } else {
455            panic!("Handle {} is not a closure!", handle.idx());
456        }
457    }
458
459    pub fn get_closure_captures(&self, handle: Handle) -> &[Handle] {
460        if let Some(Object::Closure(clos)) = self.objects.get(handle.idx()) {
461            &clos.1
462        } else {
463            panic!("Handle {} is not a closure!", handle.idx());
464        }
465    }
466
467    pub fn get_continuation(&self, handle: Handle) -> &Continuation {
468        if let Some(cont) = self.continuations.get(handle.idx()) {
469            cont
470        } else {
471            panic!("Handle {} is not a continuation!", handle.idx());
472        }
473    }
474
475    pub fn get_callframe(&self, handle: Handle) -> &CallFrame {
476        if let Some(call_frame) = self.callframes.get(handle.idx()) {
477            call_frame
478        } else {
479            panic!("Handle {} is not a call frame!", handle.idx());
480        }
481    }
482
483    pub fn get_value(&self, handle: Handle) -> Value {
484        if let Some(value) = self.values.get(handle.idx()) {
485            *value
486        } else {
487            panic!("Handle {} is not a value!", handle.idx());
488        }
489    }
490
491    pub fn get_value_mut(&mut self, handle: Handle) -> &mut Value {
492        if let Some(value) = self.values.get_mut(handle.idx()) {
493            value
494        } else {
495            panic!("Handle {} is not a value!", handle.idx());
496        }
497    }
498
499    pub fn get_error(&self, handle: Handle) -> Error {
500        if let Some(error) = self.errors.get(handle.idx()) {
501            *error
502        } else {
503            panic!("Handle {} is not an error!", handle.idx());
504        }
505    }
506
507    pub fn get_io(&self, handle: Handle) -> &HeapIo {
508        if let Some(io) = self.ios.get(handle.idx()) {
509            io
510        } else {
511            panic!("Handle {} is not an io!", handle.idx());
512        }
513    }
514
515    /// If val is on the heap is it still alive after GC
516    /// Return true if val is not a heap object.
517    pub fn is_live(&self, val: Value) -> bool {
518        value_op!(self, val, is_live, true)
519    }
520
521    pub fn immutable(&mut self, val: Value) {
522        value_op!(self, val, immutable, ());
523    }
524
525    pub fn sticky(&mut self, val: Value) {
526        value_op!(self, val, sticky, ());
527    }
528
529    pub fn unsticky(&mut self, val: Value) {
530        value_op!(self, val, unsticky, ());
531    }
532
533    pub fn is_traced_and_set(&mut self, val: Value) -> bool {
534        value_op!(self, val, is_traced_and_set, true)
535    }
536
537    pub fn mark(&mut self, value: Value) {
538        mark!(self, value);
539    }
540
541    fn mark_trace(&mut self, val: Value) {
542        mark!(self, val);
543        self.greys.push(val);
544    }
545
546    fn mark_chunk(&mut self, chunk: &Chunk) {
547        for constant in &chunk.constants {
548            self.mark_trace(*constant);
549        }
550    }
551
552    pub fn mark_call_frame(&mut self, call_frame: &CallFrame) {
553        self.mark_chunk(&call_frame.chunk);
554        if let Some(this_fn) = call_frame.this_fn {
555            self.mark_trace(this_fn);
556        }
557        for defer in &call_frame.defers {
558            self.mark_trace(*defer);
559        }
560        if let Some(on_error) = call_frame.on_error {
561            self.mark_trace(on_error);
562        }
563        self.mark_trace(call_frame.called);
564    }
565
566    fn trace_object(&mut self, obj: &Object) {
567        match obj {
568            Object::String(_) => {}
569            Object::Vector(vec) => {
570                for v in vec.iter() {
571                    self.mark_trace(*v);
572                }
573            }
574            Object::Map(map) => {
575                for (key, val) in map.iter() {
576                    self.mark_trace(key);
577                    self.mark_trace(val);
578                }
579            }
580            Object::Bytes(_) => {}
581            Object::Lambda(chunk) => self.mark_chunk(chunk),
582            Object::Closure(clos) => {
583                self.mark_chunk(&clos.0);
584                for close in clos.1.iter() {
585                    self.mark_trace(Value::Value(*close));
586                }
587            }
588            Object::Empty => panic!("An empty object can not be live!"),
589        }
590    }
591
592    fn trace(&mut self, val: Value) {
593        let props = self.props.take().expect("missing heap props");
594        if let Some(props) = props.get(&val) {
595            // Make sure we don't do anything that can access self.props here since that will panic...
596            // trace any properties for val.
597            for val in props.values() {
598                self.mark_trace(*val);
599            }
600        }
601        self.props = Some(props);
602        match val {
603            Value::CharClusterLong(handle)
604            | Value::String(handle)
605            | Value::Vector(handle)
606            | Value::Map(handle)
607            | Value::Bytes(handle)
608            | Value::List(handle, _)
609            | Value::Lambda(handle)
610            | Value::Closure(handle) => {
611                let obj = self
612                    .objects
613                    .get(handle.idx())
614                    .expect("Invalid object handle!")
615                    .clone();
616                self.trace_object(&obj);
617            }
618
619            Value::Pair(handle) => {
620                let pair = *self.pairs.get(handle.idx()).expect("Invalid error handle!");
621                self.mark_trace(pair.0);
622                self.mark_trace(pair.1);
623            }
624            Value::Value(handle) => {
625                let val = self
626                    .values
627                    .get(handle.idx())
628                    .expect("Invalid error handle!");
629                self.mark_trace(*val);
630            }
631            Value::Error(handle) => {
632                let err = self
633                    .errors
634                    .get(handle.idx())
635                    .expect("Invalid error handle!");
636                self.mark_trace(err.data);
637            }
638            Value::Continuation(handle) => {
639                let k = self
640                    .continuations
641                    .get(handle.idx())
642                    .expect("Invalid continuation handle!")
643                    .clone();
644                self.mark_call_frame(&k.frame);
645                for obj in &k.stack {
646                    self.mark_trace(*obj);
647                }
648            }
649            Value::CallFrame(handle) => {
650                let call_frame = self
651                    .callframes
652                    .get(handle.idx())
653                    .expect("Invalid error handle!")
654                    .clone();
655                self.mark_call_frame(&call_frame)
656            }
657
658            Value::Float(_)
659            | Value::Byte(_)
660            | Value::Int(_)
661            | Value::CodePoint(_)
662            | Value::CharCluster(_, _)
663            | Value::Symbol(_)
664            | Value::Keyword(_)
665            | Value::StringConst(_)
666            | Value::Special(_)
667            | Value::Builtin(_)
668            | Value::Io(_)
669            | Value::True
670            | Value::False
671            | Value::Nil
672            | Value::Undefined => {}
673        }
674    }
675
676    fn initial_mark_call_frame(frame: &CallFrame, greys: &mut Vec<Value>) {
677        for constant in &frame.chunk.constants {
678            greys.push(*constant);
679        }
680        if let Some(this_fn) = frame.this_fn {
681            greys.push(this_fn);
682        }
683        for defer in &frame.defers {
684            greys.push(*defer);
685        }
686        if let Some(on_error) = frame.on_error {
687            greys.push(on_error);
688        }
689        greys.push(frame.called);
690    }
691
692    fn collect<MarkFunc>(&mut self, mut mark_roots: MarkFunc)
693    where
694        MarkFunc: FnMut(&mut Heap) -> VMResult<()>,
695    {
696        self.objects.clear_marks();
697        self.callframes.clear_marks();
698        self.continuations.clear_marks();
699        self.errors.clear_marks();
700        self.pairs.clear_marks();
701        self.values.clear_marks();
702        mark_roots(self).expect("Failed to mark the roots!");
703        let mut greys = vec![];
704        self.callframes.trace_all_live(|frame| {
705            Self::initial_mark_call_frame(frame, &mut greys);
706        });
707        self.continuations.trace_all_live(|k| {
708            Self::initial_mark_call_frame(&k.frame, &mut greys);
709            for obj in &k.stack {
710                greys.push(*obj);
711            }
712        });
713        self.errors.trace_all_live(|err| {
714            greys.push(err.data);
715        });
716        self.pairs.trace_all_live(|pair| {
717            greys.push(pair.0);
718            greys.push(pair.1);
719        });
720        self.values.trace_all_live(|val| {
721            greys.push(*val);
722        });
723        let mut objs = Vec::new();
724        self.objects.trace_all_live(|obj| {
725            // this cloning is not great...
726            objs.push(obj.clone());
727        });
728        for obj in &objs {
729            self.trace_object(obj);
730        }
731        for v in greys.drain(..) {
732            self.mark_trace(v);
733        }
734        while let Some(val) = self.greys.pop() {
735            if !self.is_traced_and_set(val) {
736                self.trace(val);
737            }
738        }
739        // Sweep out collected properties.
740        let mut props = self.props.take().expect("missing heap props");
741        props.retain(|key, _val| self.is_live(*key));
742        self.props = Some(props);
743        self.objects.set_all_dead(Object::Empty);
744    }
745
746    pub fn live_objects(&self) -> usize {
747        self.objects.live_objects()
748            + self.continuations.live_objects()
749            + self.callframes.live_objects()
750            + self.pairs.live_objects()
751            + self.values.live_objects()
752            + self.errors.live_objects()
753    }
754
755    pub fn get_property(&self, value: Value, prop: Interned) -> Option<Value> {
756        if let Some(map) = self.props().get(&value) {
757            if let Some(val) = map.get(&prop) {
758                return Some(*val);
759            }
760        }
761        None
762    }
763
764    pub fn set_property(&mut self, key_value: Value, prop: Interned, value: Value) {
765        if let Some(map) = self.props_mut().get_mut(&key_value) {
766            let map = Arc::make_mut(map);
767            map.insert(prop, value);
768        } else {
769            let mut map = FxHashMap::default();
770            map.insert(prop, value);
771            self.props_mut().insert(key_value, Arc::new(map));
772        }
773    }
774}
775
776#[cfg(test)]
777mod tests {
778    use super::*;
779    use crate::from_i56;
780
781    fn _test_send_sync<T>(_t: T)
782    where
783        T: Send + Sync,
784    {
785    }
786
787    //#[test]
788    //fn test_obj_send_sync() {
789    //    test_send_sync(Object::Value(Value::Nil));
790    //}
791
792    #[test]
793    fn test_basic() -> VMResult<()> {
794        let mut heap = Heap::default();
795        let mark_roots = |_heap: &mut Heap| -> VMResult<()> { Ok(()) };
796        assert!(heap.pairs.capacity() == 512);
797        assert!(heap.live_objects() == 0);
798        for x in 0..512 {
799            heap.alloc_pair(x.into(), Value::Nil, MutState::Mutable, mark_roots);
800        }
801        assert!(heap.pairs.capacity() == 512);
802        assert!(heap.live_objects() == 512);
803        for x in 0..512 {
804            if let (Value::Int(v), Value::Nil) = heap.get_pair(Handle::new(x)) {
805                assert!(x == from_i56(&v) as usize);
806            } else {
807                panic!();
808            }
809        }
810        heap.alloc_pair(512.into(), Value::Nil, MutState::Mutable, mark_roots);
811        assert!(heap.pairs.capacity() == 512);
812        assert!(heap.live_objects() == 1);
813        if let (Value::Int(v), Value::Nil) = heap.get_pair(Handle::new(0)) {
814            assert!(512 == from_i56(&v));
815        } else {
816            panic!();
817        }
818        let mark_roots = |heap: &mut Heap| -> VMResult<()> {
819            for idx in 0..512 {
820                heap.mark(Value::Pair(Handle::new(idx)));
821            }
822            Ok(())
823        };
824        for x in 0..512 {
825            heap.alloc_pair(x.into(), Value::Nil, MutState::Mutable, mark_roots);
826        }
827        assert!(heap.pairs.capacity() == 1024);
828        assert!(heap.live_objects() == 513);
829        for x in 0..513 {
830            if let (Value::Int(v), Value::Nil) = heap.get_pair(Handle::new(x)) {
831                if x == 0 {
832                    assert!(512 == from_i56(&v));
833                } else {
834                    assert!(x - 1 == from_i56(&v) as usize);
835                }
836            } else {
837                panic!();
838            }
839        }
840        let mark_roots = |heap: &mut Heap| -> VMResult<()> {
841            for idx in 0..513 {
842                if idx % 2 == 0 {
843                    heap.mark(Value::Pair(Handle::new(idx)));
844                }
845            }
846            Ok(())
847        };
848        heap.collect(mark_roots);
849        assert!(heap.pairs.capacity() == 1024);
850        assert!(heap.live_objects() == 257);
851        let mark_roots = |_heap: &mut Heap| -> VMResult<()> { Ok(()) };
852        heap.collect(mark_roots);
853        assert!(heap.pairs.capacity() == 1024);
854        assert!(heap.live_objects() == 0);
855        for x in 0..512 {
856            let h = heap.alloc_pair(x.into(), Value::Nil, MutState::Mutable, mark_roots);
857            heap.sticky(h);
858        }
859        heap.collect(mark_roots);
860        assert!(heap.pairs.capacity() == 1024);
861        assert!(heap.live_objects() == 512);
862        for x in 512..1024 {
863            let _h = heap.alloc_pair(x.into(), Value::Nil, MutState::Mutable, mark_roots);
864        }
865        let mark_roots = |heap: &mut Heap| -> VMResult<()> {
866            for idx in 0..1024 {
867                heap.mark(Value::Pair(Handle::new(idx)));
868            }
869            Ok(())
870        };
871        heap.collect(mark_roots);
872        assert!(heap.pairs.capacity() == 1024);
873        assert!(heap.live_objects() == 1024);
874        heap.alloc_string("steve".into(), MutState::Mutable, mark_roots);
875        assert!(heap.pairs.capacity() == 1024);
876        assert!(heap.live_objects() == 1025);
877        Ok(())
878    }
879
880    #[test]
881    fn test_trace_val() -> VMResult<()> {
882        let mut heap = Heap::default();
883
884        assert!(heap.pairs.capacity() == 512);
885        assert!(heap.live_objects() == 0);
886        let outers = std::rc::Rc::new(std::cell::RefCell::new(vec![]));
887        let outers_mark = outers.clone();
888        let mark_roots = |heap: &mut Heap| -> VMResult<()> {
889            for h in outers_mark.borrow().iter() {
890                heap.mark(*h);
891            }
892            Ok(())
893        };
894        for x in 0..256 {
895            let inner = heap.alloc_pair(x.into(), Value::Nil, MutState::Mutable, mark_roots);
896            outers.borrow_mut().push(heap.alloc_pair(
897                inner,
898                Value::Nil,
899                MutState::Mutable,
900                mark_roots,
901            ));
902        }
903        assert!(heap.pairs.capacity() == 512);
904        assert!(heap.live_objects() == 512);
905        for (i, h) in outers.borrow().iter().enumerate() {
906            if let (Value::Pair(inner), Value::Nil) = heap.get_pair(h.get_handle().unwrap()) {
907                if let (Value::Int(v), Value::Nil) = heap.get_pair(inner) {
908                    assert!(i == from_i56(&v) as usize);
909                } else {
910                    panic!();
911                }
912            } else {
913                panic!();
914            }
915        }
916        heap.collect(mark_roots);
917        assert_eq!(heap.pairs.capacity(), 512);
918        assert_eq!(heap.live_objects(), 512);
919        /* XXXSLS
920        for h in outers.borrow().iter() {
921            //let data = Box::new("bloop".to_string());
922            //let d = Box::into_raw(data) as usize;
923            heap.replace(h.get_handle().unwrap(), Object::String(Arc::new("bloop".into())));
924        }
925        heap.collect(mark_roots);
926        assert!(heap.capacity() == 512);
927        assert!(heap.live_objects() == 256);
928        for h in outers.borrow().iter() {
929            let sstr = heap.get_string(h.get_handle().unwrap());
930            assert!(sstr == "bloop");
931            i += 1;
932        }
933        */
934        Ok(())
935    }
936
937    #[test]
938    fn test_trace_vec() -> VMResult<()> {
939        let mut heap = Heap::default();
940
941        assert!(heap.pairs.capacity() == 512);
942        assert!(heap.live_objects() == 0);
943        let outers = std::rc::Rc::new(std::cell::RefCell::new(vec![]));
944        let outers_mark = outers.clone();
945        let mark_roots = |heap: &mut Heap| -> VMResult<()> {
946            for h in outers_mark.borrow().iter() {
947                heap.mark(*h);
948            }
949            Ok(())
950        };
951        let mut v = vec![];
952        for x in 0..256 {
953            let inner = heap.alloc_pair(x.into(), Value::Nil, MutState::Mutable, mark_roots);
954            v.push(inner);
955        }
956        outers.borrow_mut().push(Value::Vector(heap.alloc(
957            Object::Vector(Arc::new(v)),
958            MutState::Mutable.flag(),
959            mark_roots,
960        )));
961        assert!(heap.pairs.capacity() == 512);
962        assert!(heap.live_objects() == 257);
963        for h in outers.borrow().iter() {
964            let v = heap.get_vector(h.get_handle().unwrap());
965            for (i, hv) in v.iter().enumerate() {
966                if let Value::Pair(hv) = hv {
967                    if let (Value::Int(v), Value::Nil) = heap.get_pair(*hv) {
968                        assert!(i == from_i56(&v) as usize);
969                    } else {
970                        panic!();
971                    }
972                } else {
973                    panic!();
974                }
975            }
976        }
977        heap.collect(mark_roots);
978        assert_eq!(heap.pairs.capacity(), 512);
979        assert_eq!(heap.live_objects(), 257);
980        for h in outers.borrow().iter() {
981            let v = heap.get_vector(h.get_handle().unwrap());
982            for (i, hv) in v.iter().enumerate() {
983                if let Value::Pair(hv) = hv {
984                    if let (Value::Int(v), Value::Nil) = heap.get_pair(*hv) {
985                        assert!(i == from_i56(&v) as usize);
986                    } else {
987                        panic!();
988                    }
989                } else {
990                    panic!();
991                }
992            }
993        }
994        /* XXXSLS
995        for h in outers.borrow().iter() {
996            //let data = Box::new("bloop".to_string());
997            //let d = Box::into_raw(data) as usize;
998            //heap.replace(*h, Object::StringMut(d));
999            heap.replace(h.get_handle().unwrap(), Object::String(Arc::new("bloop".into())));
1000        }
1001        heap.collect(mark_roots);
1002        assert!(heap.capacity() == 512);
1003        assert!(heap.live_objects() == 1);
1004        for h in outers.borrow().iter() {
1005            let sstr = heap.get_string(h.get_handle().unwrap());
1006            assert!(sstr == "bloop");
1007        }
1008        */
1009        Ok(())
1010    }
1011
1012    #[test]
1013    fn test_trace_pair() -> VMResult<()> {
1014        let mut heap = Heap::default();
1015        assert!(heap.pairs.capacity() == 512);
1016        assert!(heap.live_objects() == 0);
1017        let outers = std::rc::Rc::new(std::cell::RefCell::new(vec![]));
1018        let outers_mark = outers.clone();
1019        let mark_roots = |heap: &mut Heap| -> VMResult<()> {
1020            for h in outers_mark.borrow().iter() {
1021                heap.mark(*h);
1022            }
1023            Ok(())
1024        };
1025        outers.borrow_mut().push(heap.alloc_pair(
1026            1.into(),
1027            2.into(),
1028            MutState::Mutable,
1029            mark_roots,
1030        ));
1031        let car_h = heap.alloc_pair(3.into(), Value::Nil, MutState::Mutable, mark_roots);
1032        let cdr_h = heap.alloc_pair(4.into(), Value::Nil, MutState::Mutable, mark_roots);
1033        outers
1034            .borrow_mut()
1035            .push(heap.alloc_pair(car_h, 2.into(), MutState::Mutable, mark_roots));
1036        outers
1037            .borrow_mut()
1038            .push(heap.alloc_pair(1.into(), cdr_h, MutState::Mutable, mark_roots));
1039        outers
1040            .borrow_mut()
1041            .push(heap.alloc_pair(car_h, cdr_h, MutState::Mutable, mark_roots));
1042        assert_eq!(heap.pairs.capacity(), 512);
1043        assert_eq!(heap.live_objects(), 6);
1044        heap.collect(mark_roots);
1045        assert_eq!(heap.pairs.capacity(), 512);
1046        assert_eq!(heap.live_objects(), 6);
1047        for (i, h) in outers.borrow().iter().enumerate() {
1048            let (car, cdr) = heap.get_pair(h.get_handle().unwrap());
1049            if i == 0 {
1050                let (car, cdr) = if let Value::Int(car) = car {
1051                    if let Value::Int(cdr) = cdr {
1052                        (from_i56(&car), from_i56(&cdr))
1053                    } else {
1054                        (from_i56(&car), 0)
1055                    }
1056                } else {
1057                    (0, 0)
1058                };
1059                assert!(car == 1);
1060                assert!(cdr == 2);
1061            } else if i == 1 {
1062                let (car, cdr) = if let Value::Pair(car_h) = car {
1063                    if let (Value::Int(car), Value::Nil) = heap.get_pair(car_h) {
1064                        if let Value::Int(cdr) = cdr {
1065                            (from_i56(&car), from_i56(&cdr))
1066                        } else {
1067                            (from_i56(&car), 0)
1068                        }
1069                    } else {
1070                        (0, 0)
1071                    }
1072                } else {
1073                    (0, 0)
1074                };
1075                assert_eq!(car, 3);
1076                assert_eq!(cdr, 2);
1077            } else if i == 2 {
1078                let (car, cdr) = if let Value::Pair(cdr_h) = cdr {
1079                    if let (Value::Int(cdr), Value::Nil) = heap.get_pair(cdr_h) {
1080                        if let Value::Int(car) = car {
1081                            (from_i56(&car), from_i56(&cdr))
1082                        } else {
1083                            (0, from_i56(&cdr))
1084                        }
1085                    } else {
1086                        (0, 0)
1087                    }
1088                } else {
1089                    (0, 0)
1090                };
1091                assert!(car == 1);
1092                assert!(cdr == 4);
1093            } else if i == 3 {
1094                let (car, cdr) = if let Value::Pair(car_h) = car {
1095                    if let (Value::Int(car), Value::Nil) = heap.get_pair(car_h) {
1096                        if let Value::Pair(cdr_h) = cdr {
1097                            if let (Value::Int(cdr), Value::Nil) = heap.get_pair(cdr_h) {
1098                                (from_i56(&car), from_i56(&cdr))
1099                            } else {
1100                                (from_i56(&car), 0)
1101                            }
1102                        } else {
1103                            (0, 0)
1104                        }
1105                    } else {
1106                        (0, 0)
1107                    }
1108                } else {
1109                    (0, 0)
1110                };
1111                assert!(car == 3);
1112                assert!(cdr == 4);
1113            } else {
1114                panic!()
1115            }
1116        }
1117
1118        Ok(())
1119    }
1120}
slvm/heap.rs

slvm/
heap.rs
