lambda-throw-cat 0.1.0

Lambda calculus with records, prototype chains, ref cells, GC, and non-local control flow via throw/try/catch. Outcome::Normal/Thrown is threaded purely-functionally through every reduction. Spike 4 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
86
87
88
89
90
91
92

//! Mark-sweep garbage collection.
//!
//! Spike 3 extends spike 2's reachability rules with two new edges:
//!
//! 5. From any [`Value::Object`], every property value is reachable.
//! 6. From any [`Value::Object`] with `Some(prototype)`, the prototype
//!    address is reachable.
//!
//! Both edges are pure-functional traversals identical in shape to the
//! reference edge: gather addresses into an immutable [`BTreeSet`], then
//! delegate sweeping to [`Heap::retain`].

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`.
#[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),
        Value::Object {
            properties,
            prototype,
        } => mark_object(properties, *prototype, heap, live),
    }
}

fn mark_object(
    properties: &std::collections::BTreeMap<crate::syntax::VarName, Value>,
    prototype: Option<Address>,
    heap: &Heap,
    live: BTreeSet<Address>,
) -> BTreeSet<Address> {
    let with_proto = prototype
        .iter()
        .copied()
        .fold(live, |acc, addr| mark_reference(addr, heap, acc));
    properties
        .values()
        .fold(with_proto, |acc, v| mark_value(v, heap, acc))
}

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),
        }
    }
}