lambda_ref_cat/
gc.rs

1//! Mark-sweep garbage collection.
2//!
3//! Roots for collection are the active environment and any explicitly named
4//! "live" values (such as the value an evaluator just produced).  Marking is
5//! a fold over reachable [`Address`]es; sweeping is delegated to
6//! [`Heap::retain`].  Both phases are pure functions: no `mut`, no interior
7//! mutability, no `Rc`/`Arc`.
8//!
9//! Address reachability is the transitive closure of:
10//!
11//! 1. Each binding in `env` is reachable.
12//! 2. Each value in `roots` is reachable.
13//! 3. From any [`Value::Closure`], every binding in its captured environment
14//!    is reachable.
15//! 4. From any [`Value::Ref`] whose address is in the heap, the value at that
16//!    address is reachable.
17//!
18//! Dangling references (a [`Value::Ref`] whose address has no heap entry)
19//! are tolerated by the collector: the address is still marked live, since
20//! sweeping cannot create or resolve a dangling ref, only preserve it.
21
22use std::collections::BTreeSet;
23
24use crate::env::Env;
25use crate::heap::{Address, Heap};
26use crate::value::Value;
27
28/// Result of looking up an address in the heap.
29enum Lookup<'a> {
30    Dangling,
31    Found(&'a Value),
32}
33
34fn lookup(heap: &Heap, address: Address) -> Lookup<'_> {
35    heap.load(address).map_or(Lookup::Dangling, Lookup::Found)
36}
37
38/// Compute the set of addresses reachable from `roots` and `env` through
39/// `heap`.
40#[must_use]
41pub fn reachable(roots: &[&Value], env: &Env, heap: &Heap) -> BTreeSet<Address> {
42    let from_env = mark_env(env, heap, BTreeSet::new());
43    roots
44        .iter()
45        .fold(from_env, |acc, &value| mark_value(value, heap, acc))
46}
47
48/// Retain only the cells reachable from `roots` and `env`, returning the
49/// resulting heap.  The next-address counter is preserved so old addresses
50/// continue to detect as dangling rather than colliding with newly-allocated
51/// cells.
52#[must_use]
53pub fn collect(roots: &[&Value], env: &Env, heap: &Heap) -> Heap {
54    heap.retain(&reachable(roots, env, heap))
55}
56
57fn mark_env(env: &Env, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
58    match env {
59        Env::Empty => live,
60        Env::Cons { value, rest, .. } => {
61            let live = mark_value(value, heap, live);
62            mark_env(rest, heap, live)
63        }
64    }
65}
66
67fn mark_value(value: &Value, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
68    match value {
69        Value::Closure { env: capture, .. } => mark_env(capture, heap, live),
70        Value::Ref(address) => mark_reference(*address, heap, live),
71    }
72}
73
74fn mark_reference(address: Address, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
75    if live.contains(&address) {
76        live
77    } else {
78        let extended: BTreeSet<Address> =
79            live.into_iter().chain(std::iter::once(address)).collect();
80        match lookup(heap, address) {
81            Lookup::Dangling => extended,
82            Lookup::Found(value) => mark_value(value, heap, extended),
83        }
84    }
85}
lambda_ref_cat/gc.rs

lambda_ref_cat/
gc.rs
