lambda_throw_cat/
gc.rs

1//! Mark-sweep garbage collection.
2//!
3//! Spike 3 extends spike 2's reachability rules with two new edges:
4//!
5//! 5. From any [`Value::Object`], every property value is reachable.
6//! 6. From any [`Value::Object`] with `Some(prototype)`, the prototype
7//!    address is reachable.
8//!
9//! Both edges are pure-functional traversals identical in shape to the
10//! reference edge: gather addresses into an immutable [`BTreeSet`], then
11//! delegate sweeping to [`Heap::retain`].
12
13use std::collections::BTreeSet;
14
15use crate::env::Env;
16use crate::heap::{Address, Heap};
17use crate::value::Value;
18
19/// Result of looking up an address in the heap.
20enum Lookup<'a> {
21    Dangling,
22    Found(&'a Value),
23}
24
25fn lookup(heap: &Heap, address: Address) -> Lookup<'_> {
26    heap.load(address).map_or(Lookup::Dangling, Lookup::Found)
27}
28
29/// Compute the set of addresses reachable from `roots` and `env` through
30/// `heap`.
31#[must_use]
32pub fn reachable(roots: &[&Value], env: &Env, heap: &Heap) -> BTreeSet<Address> {
33    let from_env = mark_env(env, heap, BTreeSet::new());
34    roots
35        .iter()
36        .fold(from_env, |acc, &value| mark_value(value, heap, acc))
37}
38
39/// Retain only the cells reachable from `roots` and `env`.
40#[must_use]
41pub fn collect(roots: &[&Value], env: &Env, heap: &Heap) -> Heap {
42    heap.retain(&reachable(roots, env, heap))
43}
44
45fn mark_env(env: &Env, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
46    match env {
47        Env::Empty => live,
48        Env::Cons { value, rest, .. } => {
49            let live = mark_value(value, heap, live);
50            mark_env(rest, heap, live)
51        }
52    }
53}
54
55fn mark_value(value: &Value, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
56    match value {
57        Value::Closure { env: capture, .. } => mark_env(capture, heap, live),
58        Value::Ref(address) => mark_reference(*address, heap, live),
59        Value::Object {
60            properties,
61            prototype,
62        } => mark_object(properties, *prototype, heap, live),
63    }
64}
65
66fn mark_object(
67    properties: &std::collections::BTreeMap<crate::syntax::VarName, Value>,
68    prototype: Option<Address>,
69    heap: &Heap,
70    live: BTreeSet<Address>,
71) -> BTreeSet<Address> {
72    let with_proto = prototype
73        .iter()
74        .copied()
75        .fold(live, |acc, addr| mark_reference(addr, heap, acc));
76    properties
77        .values()
78        .fold(with_proto, |acc, v| mark_value(v, heap, acc))
79}
80
81fn mark_reference(address: Address, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
82    if live.contains(&address) {
83        live
84    } else {
85        let extended: BTreeSet<Address> =
86            live.into_iter().chain(std::iter::once(address)).collect();
87        match lookup(heap, address) {
88            Lookup::Dangling => extended,
89            Lookup::Found(value) => mark_value(value, heap, extended),
90        }
91    }
92}
lambda_throw_cat/gc.rs

lambda_throw_cat/
gc.rs
