lambda-ref-cat 0.1.0

Lambda calculus with mutable reference cells and a pure-functional mark-sweep garbage collector, built on comp-cat-rs. Spike 2 of a web-engine reformulation targeting Tauri.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

//! Mark-sweep garbage collection.
//!
//! Roots for collection are the active environment and any explicitly named
//! "live" values (such as the value an evaluator just produced).  Marking is
//! a fold over reachable [`Address`]es; sweeping is delegated to
//! [`Heap::retain`].  Both phases are pure functions: no `mut`, no interior
//! mutability, no `Rc`/`Arc`.
//!
//! Address reachability is the transitive closure of:
//!
//! 1. Each binding in `env` is reachable.
//! 2. Each value in `roots` is reachable.
//! 3. From any [`Value::Closure`], every binding in its captured environment
//!    is reachable.
//! 4. From any [`Value::Ref`] whose address is in the heap, the value at that
//!    address is reachable.
//!
//! Dangling references (a [`Value::Ref`] whose address has no heap entry)
//! are tolerated by the collector: the address is still marked live, since
//! sweeping cannot create or resolve a dangling ref, only preserve it.

use std::collections::BTreeSet;

use crate::env::Env;
use crate::heap::{Address, Heap};
use crate::value::Value;

/// Result of looking up an address in the heap.
enum Lookup<'a> {
    Dangling,
    Found(&'a Value),
}

fn lookup(heap: &Heap, address: Address) -> Lookup<'_> {
    heap.load(address).map_or(Lookup::Dangling, Lookup::Found)
}

/// Compute the set of addresses reachable from `roots` and `env` through
/// `heap`.
#[must_use]
pub fn reachable(roots: &[&Value], env: &Env, heap: &Heap) -> BTreeSet<Address> {
    let from_env = mark_env(env, heap, BTreeSet::new());
    roots
        .iter()
        .fold(from_env, |acc, &value| mark_value(value, heap, acc))
}

/// Retain only the cells reachable from `roots` and `env`, returning the
/// resulting heap.  The next-address counter is preserved so old addresses
/// continue to detect as dangling rather than colliding with newly-allocated
/// cells.
#[must_use]
pub fn collect(roots: &[&Value], env: &Env, heap: &Heap) -> Heap {
    heap.retain(&reachable(roots, env, heap))
}

fn mark_env(env: &Env, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
    match env {
        Env::Empty => live,
        Env::Cons { value, rest, .. } => {
            let live = mark_value(value, heap, live);
            mark_env(rest, heap, live)
        }
    }
}

fn mark_value(value: &Value, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
    match value {
        Value::Closure { env: capture, .. } => mark_env(capture, heap, live),
        Value::Ref(address) => mark_reference(*address, heap, live),
    }
}

fn mark_reference(address: Address, heap: &Heap, live: BTreeSet<Address>) -> BTreeSet<Address> {
    if live.contains(&address) {
        live
    } else {
        let extended: BTreeSet<Address> =
            live.into_iter().chain(std::iter::once(address)).collect();
        match lookup(heap, address) {
            Lookup::Dangling => extended,
            Lookup::Found(value) => mark_value(value, heap, extended),
        }
    }
}