elly_core/

eval_env.rs

//! Evaluation environment and context: the persistent [`EnvNode`] chain, the
//! [`Ctx`] threading the unique-id source and builtin-module cache, and [`instantiate`],
//! which builds a module instance's environment terminal. The tree-walker in `eval.rs`
//! reads bindings via [`lookup`], conses them with [`bind`], and captures closures
//! via [`capture_env`].

use alloc::boxed::Box;
use alloc::rc::Rc;
use alloc::vec::Vec;
use core::cell::{Cell, OnceCell};

use crate::ast::{Capture, Expr, ModuleData, Text};
use crate::{HomeLeaf, Raised};

use crate::builtins::NMODULES;
use crate::eval::{self, Builtin};
use crate::value::Value;

/// A shared, persistent environment: a nameless cons list of the running
/// activation's bindings (innermost first) on top of the closure's captured
/// [`Frame`](EnvNode::Frame). A resolved reference ([`Expr::Local`](crate::Expr))
/// reaches its value by walking its de Bruijn `index` over `next` links and
/// cloning the cell's value — a pointer chase without name comparison or
/// per-link cloning. Indices beyond the consed cells land in the frame array.
/// The resolver (`resolve.rs`) assigns each reference the exact number of cells
/// between it and its binder.
#[derive(Debug)]
#[cfg_attr(not(feature = "stats-env"), derive(Clone))]
pub struct Env(Option<EnvRef>);

/// With `stats-env`, cloning passes the caller's location on to [`EnvRef`]'s clone,
/// which a derived impl (through `Option::clone`) would lose.
#[cfg(feature = "stats-env")]
impl Clone for Env {
    #[track_caller]
    #[inline]
    fn clone(&self) -> Self {
        match &self.0 {
            Some(node) => Env(Some(node.clone())),
            None => Env(None),
        }
    }
}

impl Env {
    pub const EMPTY: Env = Env(None);

    /// Cons one binding of `val` onto `env`.
    pub fn bind(self, val: Value) -> Self {
        Self(Some(EnvRef::new(EnvNode::Cons { val, next: self })))
    }

    /// [`bind`](Self::bind) in the evaluator: the cell comes from `ctx`'s free
    /// list when it has one.
    #[inline]
    pub(crate) fn bind_in(self, val: Value, ctx: &Ctx) -> Self {
        Self(Some(ctx.alloc(EnvNode::Cons { val, next: self })))
    }

    /// Cons one binding of `val` onto `env`.
    pub(crate) fn frame(self, vals: Box<[Value]>) -> Self {
        Self(Some(EnvRef::new(EnvNode::Frame { vals, home: self })))
    }

    pub(crate) fn from_ref(node: EnvRef) -> Self {
        Self(Some(node))
    }

    pub fn clone_ref(&self) -> Option<EnvRef> {
        self.0.clone()
    }

    pub(crate) fn as_module(&self) -> Option<(&Rc<ModuleData>, u64)> {
        match self.0.as_deref() {
            Some(EnvNode::Module { data, id_base, .. }) => Some((data, *id_base)),
            _ => None,
        }
    }

    /// Resolves a de Bruijn `index` to a cloned value by walking `next` links.
    /// If the walk reaches the [`Frame`], the remaining index selects `vals[rest]`.
    /// The resolver ensures the index lands on a live cell or frame slot.
    ///
    /// [`Module`](EnvNode::Module) terminals are passed through uncounted; a module
    /// body's reference to an import or prelude value is a `Local` whose index runs
    /// into the frame.
    ///
    /// [`Frame`]: EnvNode::Frame
    pub(crate) fn lookup(&self, index: u32) -> Value {
        let mut cur = self;
        let mut rest = index as usize;
        loop {
            match cur
                .0
                .as_deref()
                .expect("resolved index walked past the environment")
            {
                EnvNode::Cons { val, next } => {
                    if rest == 0 {
                        return val.clone();
                    }
                    rest -= 1;
                    cur = next;
                }
                EnvNode::Frame { vals, .. } => match vals.get(rest) {
                    Some(val) => return val.clone(),
                    None => unreachable!("resolved index walked past the captured frame"),
                },
                EnvNode::Module { frame, .. } => cur = frame,
            }
        }
    }

    /// Returns the environment's terminal: either `None` or the [`Module`](EnvNode::Module)
    /// node. A closure built here carries it as its frame's `home`, ensuring a module
    /// item's body can find its module without new allocations.
    fn find_home(&self) -> Env {
        let mut cur = self;
        loop {
            match cur.0.as_deref() {
                Some(EnvNode::Cons { next, .. }) => cur = next,
                Some(EnvNode::Frame { home, .. }) => return home.clone(),
                Some(EnvNode::Module { .. }) => return cur.clone(),
                None => return Env::EMPTY,
            }
        }
    }

    /// Walks to the module terminal at `depth` and returns a home-module leaf.
    ///
    /// Leaf addresses the terminal itself rather than a member. The constructor `#Self()`
    /// and `.Self` (unwrapping inner data) are object builtins pre-applied to the module,
    /// returning a partial application that takes one remaining argument.
    #[inline(never)]
    pub(crate) fn home_leaf(&self, leaf: HomeLeaf, depth: u32) -> Result<Value, eval::Raised> {
        let (_, home, _, _) = self
            .find_module(depth)
            .ok_or_else(|| Raised::no_match("no_module"))?;
        let home = Value::Module(home.clone());
        Ok(match leaf {
            HomeLeaf::Module => home,
            HomeLeaf::New => Value::Builtin {
                op: Builtin::ObjNew,
                args: alloc::vec![home],
            },
            HomeLeaf::Value => Value::Builtin {
                op: Builtin::ObjValue,
                args: alloc::vec![home],
            },
        })
    }

    pub(crate) fn find_module(
        &self,
        mut depth: u32,
    ) -> Option<(&Env, &EnvRef, &Rc<ModuleData>, u64)> {
        let mut cur = self;
        while let Some(node) = &cur.0 {
            match &**node {
                EnvNode::Cons { next, .. } => cur = next,
                EnvNode::Frame { home, .. } => cur = home,
                EnvNode::Module {
                    data,
                    id_base,
                    frame,
                } => {
                    if depth == 0 {
                        return Some((cur, node, data, *id_base));
                    }
                    depth -= 1;
                    cur = frame;
                }
            }
        }
        None
    }

    /// Builds the environment for a capturing closure from its resolved `plan`.
    /// Outlined from `eval_env` to optimize instruction cache for deep-recursion
    /// benchmarks.
    #[inline(never)]
    pub(crate) fn capture_env(&self, plan: &[Capture], ctx: &Ctx) -> Self {
        match plan {
            [] => self.find_home(),
            // A one-value frame *is* a `Cons` onto the terminal: index 0 is the capture
            // and the walk ends there either way. Reusing the node the environment
            // already has costs one allocation instead of two (node + values), and
            // retains exactly the one value — worth a case of its own because a single
            // capture is the common escaping closure (`&v (x x) v` in a Z-combinator
            // recursion). Two or more go through a frame: the values then share one
            // allocation and one walk, which conses cannot.
            [c] => {
                let (val, next) = lookup_and_home(self, c.outer);
                next.bind_in(val, ctx)
            }
            _ => {
                let (vals, home) = build_frame_and_home(self, plan);
                home.frame(vals)
            }
        }
    }
}

/// A shared reference to an [`EnvNode`]: every handle on a node — an [`Env`] link,
/// a [`Value::Module`], an iota's or object's prototype — goes through it.
///
/// Today it is a bare `Rc`, but as the one place nodes are allocated, cloned and
/// compared, it is where to hook instrumentation (see [`stats_env`]) or to try
/// another representation (a plain `Box`, a pool). It must stay one non-null word
/// so `Option<EnvRef>` keeps the niche.
#[derive(Debug)]
#[cfg_attr(not(feature = "stats-env"), derive(Clone))]
#[repr(transparent)]
pub struct EnvRef(Rc<Shared>);

/// What an [`EnvRef`] points at: the node itself, or with `stats-env` the node
/// plus the highest reference count it has reached.
#[cfg(not(feature = "stats-env"))]
type Shared = EnvNode;
#[cfg(feature = "stats-env")]
type Shared = stats_env::Tracked;

impl EnvRef {
    #[inline]
    pub(crate) fn new(node: EnvNode) -> Self {
        #[cfg(feature = "stats-env")]
        let node = stats_env::Tracked::new(node);
        Self(Rc::new(node))
    }

    /// Whether `a` and `b` are the same node: the identity of a module instance.
    #[inline]
    pub fn ptr_eq(a: &Self, b: &Self) -> bool {
        Rc::ptr_eq(&a.0, &b.0)
    }

    /// The node's address, for hashing by identity.
    #[inline]
    pub fn as_ptr(this: &Self) -> *const EnvNode {
        &**this
    }

    /// Whether this is the node's only reference, so it dies with this handle.
    #[inline]
    fn is_unique(&self) -> bool {
        Rc::strong_count(&self.0) == 1 && Rc::weak_count(&self.0) == 0
    }

    /// The node, if this is its only reference: it can then be rewritten in
    /// place, which is how [`Ctx`] recycles the allocation.
    #[inline]
    fn unique(&mut self) -> Option<&mut EnvNode> {
        #[cfg(feature = "stats-env")]
        return Rc::get_mut(&mut self.0).map(|t| &mut t.node);
        #[cfg(not(feature = "stats-env"))]
        Rc::get_mut(&mut self.0)
    }
}

impl core::ops::Deref for EnvRef {
    type Target = EnvNode;

    #[inline]
    fn deref(&self) -> &EnvNode {
        #[cfg(feature = "stats-env")]
        return &self.0.node;
        #[cfg(not(feature = "stats-env"))]
        &self.0
    }
}

#[cfg(feature = "stats-env")]
impl Clone for EnvRef {
    #[track_caller]
    #[inline]
    fn clone(&self) -> Self {
        let rc = Rc::clone(&self.0);
        stats_env::cloned(
            &rc.max,
            Rc::strong_count(&rc),
            core::panic::Location::caller(),
        );
        Self(rc)
    }
}

#[cfg(feature = "stats-env")]
impl Drop for EnvRef {
    #[inline]
    fn drop(&mut self) {
        // A free cell (peak 0) was counted when it was recycled.
        if Rc::strong_count(&self.0) == 1 && self.0.max.get() != 0 {
            // A death under `Ctx::release` is explicit; any other is implicit.
            if !stats_env::freed(self.0.max.get()) {
                #[cfg(feature = "stats-env-drops")]
                stats_env::died();
            }
        }
    }
}

/// Per-thread environment statistics, built only with the `stats-env` feature:
/// the [`EnvNode`]s allocated by kind, how often an [`EnvRef`] is cloned, and a
/// histogram of the highest reference count each node reached before it was freed.
///
/// The reference count includes clones the evaluator holds only on the Rust stack
/// for the length of a call (a block's or match arm's copy of its environment, a
/// module turned into a temporary `Env`), so a count of 2 or 3 is partly borrow-like.
/// Nodes still alive when the counts are read are not in the histogram.
///
/// Clones are also counted by call site ([`sites`]), passed down with
/// `#[track_caller]` through [`Env`](super::Env)'s and [`EnvRef`](super::EnvRef)'s
/// `clone`. A clone made by cloning a [`Value`](crate::Value) that holds an
/// environment (a closure, a module) stops at `Value`'s derived `Clone`, so all of
/// those share one site in `value.rs`.
///
/// With `stats-env-drops`, deaths are also counted by where they happen
/// ([`drop_sites`](stats_env::drop_sites)): `Drop` has no caller location, so each
/// death walks the stack, and the report skips the drop glue to name the function
/// whose scope ended.
///
/// Tracking the maximum adds a word to every node's allocation.
#[cfg(feature = "stats-env")]
pub mod stats_env {
    use super::EnvNode;
    use core::cell::{Cell, RefCell};
    use core::panic::Location;
    use std::collections::BTreeMap;
    use std::vec::Vec;

    /// Histogram buckets: bucket `0` holds nodes whose count never exceeded 1, and
    /// bucket `b > 0` those whose maximum was in `2^(b-1) + 1 ..= 2^b`; the last
    /// bucket takes everything above.
    pub const BUCKETS: usize = 24;

    /// A snapshot of the counters since the last [`reset`].
    #[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
    pub struct Counts {
        pub cons: u64,
        pub frame: u64,
        pub module: u64,
        /// [`EnvRef`](super::EnvRef) clones, of any node.
        pub clones: u64,
        /// Freed nodes by the highest reference count they reached (see [`BUCKETS`]).
        pub max_shared: [u64; BUCKETS],
        /// Of the freed nodes, those that died inside
        /// [`Ctx::release`](super::Ctx::release); the rest died implicitly.
        pub released: u64,
        /// Of the allocated nodes, those placed in a recycled free cell.
        pub reused: u64,
    }

    /// A node and the highest reference count it has reached.
    #[derive(Debug)]
    pub(super) struct Tracked {
        pub(super) node: EnvNode,
        pub(super) max: Cell<u32>,
    }

    impl Tracked {
        #[inline]
        pub(super) fn new(node: EnvNode) -> Self {
            allocated(&node);
            Tracked {
                node,
                max: Cell::new(1),
            }
        }

        /// The node was rewritten as a free cell: it died here (inside
        /// [`Ctx::release`](super::Ctx::release)), and a peak of 0 marks it free.
        #[inline]
        pub(super) fn recycled(&self) {
            freed(self.max.get());
            self.max.set(0);
        }

        /// A free cell now holds `self.node`, allocated without the allocator.
        #[inline]
        pub(super) fn reused(&self) {
            allocated(&self.node);
            self.max.set(1);
            STATS.with(|s| s.reused.set(s.reused.get() + 1));
        }
    }

    /// Counts a node by kind, whether newly allocated or reusing a free cell.
    #[inline]
    fn allocated(node: &EnvNode) {
        STATS.with(|s| {
            let kind = match node {
                EnvNode::Cons { .. } => &s.cons,
                EnvNode::Frame { .. } => &s.frame,
                EnvNode::Module { .. } => &s.module,
            };
            kind.set(kind.get() + 1);
        });
    }

    /// The clones made at one call site.
    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
    pub struct Site {
        pub file: &'static str,
        pub line: u32,
        pub column: u32,
        pub clones: u64,
        /// Clones that raised their node's highest count: the site that set the
        /// maximum, as opposed to a copy taken while another reference was already
        /// counting.
        pub raised_max: u64,
    }

    type SiteKey = (&'static str, u32, u32);

    struct Stats {
        cons: Cell<u64>,
        frame: Cell<u64>,
        module: Cell<u64>,
        clones: Cell<u64>,
        max_shared: [Cell<u64>; BUCKETS],
        released: Cell<u64>,
        reused: Cell<u64>,
        /// Set while [`Ctx::release`](super::Ctx::release) drops an environment.
        releasing: Cell<bool>,
        /// `(clones, raised_max)` by call site.
        sites: RefCell<BTreeMap<SiteKey, (u64, u64)>>,
        /// Deaths by the return addresses on the stack when they happened.
        #[cfg(feature = "stats-env-drops")]
        deaths: RefCell<drops::Deaths>,
    }

    std::thread_local! {
        static STATS: Stats = const {
            Stats {
                cons: Cell::new(0),
                frame: Cell::new(0),
                module: Cell::new(0),
                clones: Cell::new(0),
                max_shared: [const { Cell::new(0) }; BUCKETS],
                released: Cell::new(0),
                reused: Cell::new(0),
                releasing: Cell::new(false),
                sites: RefCell::new(BTreeMap::new()),
                #[cfg(feature = "stats-env-drops")]
                deaths: RefCell::new(drops::Deaths::with_hasher(
                    std::hash::BuildHasherDefault::new(),
                )),
            }
        };
    }

    /// A clone at `at` brought the count to `count`.
    #[inline]
    pub(super) fn cloned(max: &Cell<u32>, count: usize, at: &'static Location<'static>) {
        let count = u32::try_from(count).unwrap_or(u32::MAX);
        let raised = count > max.get();
        if raised {
            max.set(count);
        }
        STATS.with(|s| {
            s.clones.set(s.clones.get() + 1);
            let mut sites = s.sites.borrow_mut();
            let site = sites
                .entry((at.file(), at.line(), at.column()))
                .or_default();
            site.0 += 1;
            site.1 += u64::from(raised);
        });
    }

    /// The last reference to a node whose count peaked at `max` is going away.
    /// Returns whether it dies inside [`Ctx::release`](super::Ctx::release).
    #[inline]
    pub(super) fn freed(max: u32) -> bool {
        let bucket = ((u32::BITS - (max.max(1) - 1).leading_zeros()) as usize).min(BUCKETS - 1);
        STATS.with(|s| {
            let slot = &s.max_shared[bucket];
            slot.set(slot.get() + 1);
            let releasing = s.releasing.get();
            if releasing {
                s.released.set(s.released.get() + 1);
            }
            releasing
        })
    }

    /// Runs `f` with every node death counted as released, cascades included.
    #[inline]
    pub(super) fn releasing(f: impl FnOnce()) {
        STATS.with(|s| s.releasing.set(true));
        f();
        STATS.with(|s| s.releasing.set(false));
    }

    /// This thread's counts so far.
    pub fn get() -> Counts {
        STATS.with(|s| Counts {
            cons: s.cons.get(),
            frame: s.frame.get(),
            module: s.module.get(),
            clones: s.clones.get(),
            max_shared: core::array::from_fn(|b| s.max_shared[b].get()),
            released: s.released.get(),
            reused: s.reused.get(),
        })
    }

    /// This thread's clones by call site, most clones first.
    pub fn sites() -> Vec<Site> {
        let mut out: Vec<Site> = STATS.with(|s| {
            s.sites
                .borrow()
                .iter()
                .map(|(&(file, line, column), &(clones, raised_max))| Site {
                    file,
                    line,
                    column,
                    clones,
                    raised_max,
                })
                .collect()
        });
        out.sort_by_key(|s| core::cmp::Reverse(s.clones));
        out
    }

    /// Zeroes this thread's counts, per-site ones included, and returns what the
    /// totals were.
    pub fn reset() -> Counts {
        let counts = get();
        STATS.with(|s| {
            for c in [
                &s.cons,
                &s.frame,
                &s.module,
                &s.clones,
                &s.released,
                &s.reused,
            ] {
                c.set(0);
            }
            for c in &s.max_shared {
                c.set(0);
            }
            s.sites.borrow_mut().clear();
            #[cfg(feature = "stats-env-drops")]
            s.deaths.borrow_mut().clear();
        });
        counts
    }

    /// The last reference to a node is going away implicitly: record the stack.
    #[cfg(feature = "stats-env-drops")]
    #[inline(never)]
    pub(super) fn died() {
        let stack = drops::capture();
        STATS.with(|s| *s.deaths.borrow_mut().entry(stack).or_default() += 1);
    }

    /// Where nodes died since the last [`reset`], most deaths first.
    #[cfg(feature = "stats-env-drops")]
    pub fn drop_sites() -> Vec<drops::DropSite> {
        STATS.with(|s| drops::summarize(&s.deaths.borrow()))
    }

    /// Stack capture and its symbolization for [`drop_sites`].
    #[cfg(feature = "stats-env-drops")]
    pub mod drops {
        use core::cell::RefCell;
        use std::collections::HashMap;
        use std::hash::{BuildHasherDefault, DefaultHasher};
        use std::string::{String, ToString};
        use std::vec::Vec;

        /// Frames kept per death: enough to climb out of the drop glue of a
        /// node that dies because its parent did, a few levels deep.
        const DEPTH: usize = 32;

        /// Return addresses, innermost first, zero-padded.
        pub(in super::super) type Stack = [usize; DEPTH];

        /// Deaths by stack; a fixed hasher so the map can start in a `const`.
        pub(in super::super) type Deaths = HashMap<Stack, u64, BuildHasherDefault<DefaultHasher>>;

        /// What was being destroyed when the node died, innermost first.
        #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
        pub enum Via {
            /// The handle itself went out of scope or was overwritten.
            Direct,
            /// A [`Value`](crate::Value) holding it (a closure, a module, a list
            /// of those) was destroyed.
            Value,
            /// An [`EnvNode`](crate::EnvNode) holding it died first: the cascade
            /// down a chain.
            Node,
        }

        /// Nodes that died at one place.
        #[derive(Debug, Clone, PartialEq, Eq)]
        pub struct DropSite {
            /// `function (file:line)` of the first frame outside drop glue, or
            /// `?` when every captured frame was glue.
            pub site: String,
            pub via: Via,
            pub deaths: u64,
        }

        /// Walks the frame-pointer chain, which the Apple arm64 ABI mandates:
        /// two loads per frame, where unwinding tables cost tens of microseconds
        /// a death.
        #[cfg(all(target_arch = "aarch64", target_vendor = "apple"))]
        #[inline(never)]
        pub(in super::super) fn capture() -> Stack {
            let mut stack = [0; DEPTH];
            let mut fp: usize;
            // SAFETY: reads this frame's own frame pointer.
            unsafe { core::arch::asm!("mov {}, x29", out(reg) fp) };
            for slot in &mut stack {
                if fp == 0 || !fp.is_multiple_of(16) {
                    break;
                }
                // SAFETY: a frame record is `[previous fp, return address]`, and
                // the chain ends at a null or non-ascending pointer.
                let (next, ret) = unsafe { (*(fp as *const usize), *((fp + 8) as *const usize)) };
                *slot = ret;
                if next <= fp {
                    break;
                }
                fp = next;
            }
            stack
        }

        #[cfg(not(all(target_arch = "aarch64", target_vendor = "apple")))]
        pub(in super::super) fn capture() -> Stack {
            let mut stack = [0; DEPTH];
            let mut i = 0;
            // SAFETY: the stats are per thread and the capture does not unwind.
            unsafe {
                backtrace::trace_unsynchronized(|frame| {
                    stack[i] = frame.ip() as usize;
                    i += 1;
                    i < DEPTH
                });
            }
            stack
        }

        /// One symbol at an address; an inlined call contributes several,
        /// innermost first.
        #[derive(Clone)]
        struct Sym {
            name: String,
            at: String,
        }

        std::thread_local! {
            /// Symbolization is slow and addresses repeat across benches.
            static RESOLVED: RefCell<HashMap<usize, Vec<Sym>>> = RefCell::new(HashMap::new());
        }

        fn resolve(ip: usize) -> Vec<Sym> {
            RESOLVED.with(|r| {
                r.borrow_mut()
                    .entry(ip)
                    .or_insert_with(|| {
                        let mut syms = Vec::new();
                        // A return address points past the call; step back into it.
                        let pc = ip.saturating_sub(1) as *mut core::ffi::c_void;
                        backtrace::resolve(pc, |sym| {
                            let name = sym
                                .name()
                                .map_or_else(|| "?".to_string(), |n| std::format!("{n:#}"));
                            let file = sym
                                .filename()
                                .map(|f| f.to_string_lossy().into_owned())
                                .unwrap_or_default();
                            let file = file.find("src/").map_or(&file[..], |i| &file[i..]);
                            let at = match sym.lineno() {
                                Some(line) => std::format!("{file}:{line}"),
                                None => file.to_string(),
                            };
                            syms.push(Sym { name, at });
                        });
                        syms
                    })
                    .clone()
            })
        }

        /// The compiler's drop glue for a type (`drop_glue` in newer toolchains).
        fn is_drop_glue(name: &str) -> bool {
            name.contains("drop_in_place") || name.contains("drop_glue")
        }

        /// Frames that only carry the destruction along: drop glue, `Drop`
        /// impls, `mem::drop`, and this instrumentation.
        fn is_glue(name: &str) -> bool {
            is_drop_glue(name)
                || name.contains("as core::ops::drop::Drop>::drop")
                || name.contains("drop_slow")
                || name.starts_with("core::mem::drop")
                || name.contains("stats_env")
                || name.contains("backtrace")
        }

        /// The container a drop-glue frame is destroying, if it is one of ours.
        fn container(name: &str) -> Option<Via> {
            if !is_drop_glue(name) {
                None
            } else if name.contains("eval_env::EnvNode") || name.contains("stats_env::Tracked") {
                Some(Via::Node)
            } else if name.contains("value::Value") {
                Some(Via::Value)
            } else {
                None
            }
        }

        fn classify(stack: &Stack) -> (String, Via) {
            let mut via = None;
            for &ip in stack.iter().take_while(|&&ip| ip != 0) {
                for sym in resolve(ip) {
                    if is_glue(&sym.name) || sym.at.contains("/backtrace-") {
                        via = via.or_else(|| container(&sym.name));
                        continue;
                    }
                    return (
                        std::format!("{} ({})", sym.name, sym.at),
                        via.unwrap_or(Via::Direct),
                    );
                }
            }
            ("?".to_string(), via.unwrap_or(Via::Direct))
        }

        pub(in super::super) fn summarize(deaths: &Deaths) -> Vec<DropSite> {
            let mut by_site: HashMap<(String, Via), u64> = HashMap::new();
            for (stack, &n) in deaths {
                *by_site.entry(classify(stack)).or_default() += n;
            }
            let mut out: Vec<DropSite> = by_site
                .into_iter()
                .map(|((site, via), deaths)| DropSite { site, via, deaths })
                .collect();
            out.sort_by(|a, b| b.deaths.cmp(&a.deaths).then_with(|| a.site.cmp(&b.site)));
            out
        }
    }
}

/// One link of the environment list: a single binding carrying its `val` inline,
/// or the frame that terminates the walk. The empty environment is `None`.
/// [`Env`] is an `Option<EnvRef>`, utilizing the null-pointer niche to remain
/// one word wide, avoiding allocation and refcount traffic when ending a chain.
/// Lambda activations cons one `Cons` per bound name (zero for binder-less heads);
/// partial application environments share the consed prefix via `Rc`.
/// References are resolved to de Bruijn indices against this list's shape.
#[derive(Debug)]
pub enum EnvNode {
    Cons {
        val: Value,
        next: Env,
    },
    /// Module instance terminal: carries the item's module instead of the
    /// empty terminal, allowing [`Expr::ModItem`] sibling references to resolve
    /// by walking out (see [`crate::eval::eval_env`]). It binds no name and is not
    /// counted by de Bruijn `Local` indices. Materialized closures capture an
    /// environment ending in this node to keep the module alive.
    ///
    /// This node is the module instance; [`Value::Module`] is a handle to it,
    /// created by `instantiate`. `M.name` runs the body in this environment.
    ///
    /// `id_base` is the module's reserved ID block: item `i` stamps its closure
    /// with `id_base + i`, ensuring `M.f == M.f` (see `materialize_body`).
    ///
    /// `frame` is the environment the module was instantiated against (imports,
    /// host prelude, and identities), with slot order fixed by
    /// [`ModuleData::frame_names`]. De Bruijn indices walk through this node into
    /// `frame` without counting the node itself. The frame can be a flat
    /// [`Frame`](EnvNode::Frame) or a cons chain (`recur`).
    ///
    /// This structure ensures temporal acyclicity: a frame holds only values
    /// existing before the frame, and immutability prevents them from pointing
    /// back to the frame.
    Module {
        data: Rc<ModuleData>,
        id_base: u64,
        frame: Env,
    },
    /// A closure's captured frame: values of free variables used by the body,
    /// copied at creation in the order fixed by `Lambda::captures`. This terminates
    /// the de Bruijn walk: an index beyond the consed cells selects `vals[remaining]`
    /// (see `lookup`), allowing references to enclosing scopes to avoid walking
    /// the entire program.
    ///
    /// `home` stores the environment terminal (`None` or the [`Module`](EnvNode::Module)
    /// node) beyond the frame, so `ModItem` references in the body can still find
    /// the module without new allocations.
    ///
    /// Values are stored inline behind the environment's `Rc`, making the frame
    /// a single allocation.
    Frame {
        vals: Box<[Value]>,
        home: Env,
    },
}

impl EnvNode {}

/// Evaluation context threaded through the tree-walker: includes the unique-id
/// source for closure identities and the builtin module cache. It does not hold
/// a module registry or loader; imports are resolved before evaluation
/// ([`crate::load_module`]), and loaded modules are `Rc`-held values.
pub struct Ctx {
    ids: Cell<u64>,
    /// The instantiated [builtin modules](MODULES), one slot each, built on first
    /// reference. Caching them here is what gives `__Int` an identity: every
    /// reference in one evaluation yields the *same* module value, so
    /// `__eq __Int Int` holds. Two different contexts hold non-identical `__Int`s —
    /// v0's "two loads are unrelated modules" caveat, which a content-addressed
    /// module brand would retire.
    modules: [OnceCell<Value>; NMODULES],
    /// Environment cells recycled by [`release`](Self::release), linked through
    /// their own `next`, and how many there are (at most [`FREE_CAP`]).
    free: Cell<Env>,
    free_len: Cell<u32>,
}

/// The most free cells a [`Ctx`] keeps. Beyond it, released nodes go back to the
/// allocator; the cap bounds what an evaluation holds on to after a deep
/// recursion unwinds.
const FREE_CAP: u32 = 4096;

impl Ctx {
    /// A context with a fresh id source. Used by [`crate::eval::eval`] and [`crate::eval::apply`].
    pub fn new() -> Self {
        Ctx {
            ids: Cell::new(0),
            modules: core::array::from_fn(|_| OnceCell::new()),
            free: Cell::new(Env::EMPTY),
            free_len: Cell::new(0),
        }
    }

    /// A context resuming an id source at `ids` so identities continue from
    /// an earlier context. This is required when a host builds a fresh `Ctx` per
    /// call but shares values between them (e.g., Python bindings). Without this,
    /// a module's reserved id block and subsequent closure IDs could alias,
    /// causing `__eq` to incorrectly identify them as equal. The counter is
    /// carried by value to avoid a pointer chase during closure minting.
    pub fn with_ids(ids: u64) -> Self {
        Ctx {
            ids: Cell::new(ids),
            modules: core::array::from_fn(|_| OnceCell::new()),
            free: Cell::new(Env::EMPTY),
            free_len: Cell::new(0),
        }
    }

    /// Returns the current id source value to seed a successor context
    /// (see [`with_ids`](Self::with_ids)).
    pub fn ids_used(&self) -> u64 {
        self.ids.get()
    }

    /// Mints the next unique id for a closure's identity, used for equality
    /// and ordering.
    pub(crate) fn next_id(&self) -> u64 {
        let n = self.ids.get();
        self.ids.set(n + 1);
        n
    }

    /// Hands back an environment whose scope ends here. The hot scope ends of
    /// activation environments (a closure body's, a block's) call this instead of
    /// dropping implicitly, so that the nodes dying with it become free cells for
    /// [`alloc`](Self::alloc). Other drops stay implicit and go to the allocator.
    /// See `docs/todo/elly-perf-env-stats.md`.
    #[inline]
    pub(crate) fn release(&self, env: Env) {
        #[cfg(feature = "stats-env")]
        stats_env::releasing(|| self.release_inner(env));
        #[cfg(not(feature = "stats-env"))]
        self.release_inner(env);
    }

    #[inline]
    fn release_inner(&self, env: Env) {
        // A shared node only loses a reference: nothing to recycle.
        if let Some(node) = env.0 {
            if node.is_unique() {
                self.recycle(node);
            }
        }
    }

    /// Walks down from `node` while each node dies with the reference in hand,
    /// rewriting it in place as a free cell (every variant shares the one `Rc`
    /// allocation) and following its link: `next`, a frame's `home`, a module's
    /// `frame`. The rest of a node (its value, a frame's slice, a module's data)
    /// is dropped normally. Stops at a shared node or a full list, which then
    /// drops as usual.
    #[inline(never)]
    fn recycle(&self, node: EnvRef) {
        let mut free = self.free.replace(Env::EMPTY);
        let mut len = self.free_len.get();
        let mut cur = Some(node);
        while let Some(mut node) = cur {
            if len >= FREE_CAP {
                break;
            }
            let Some(slot) = node.unique() else { break };
            let free_cell = EnvNode::Cons {
                val: Value::Unit,
                next: free,
            };
            let old = core::mem::replace(slot, free_cell);
            #[cfg(feature = "stats-env")]
            node.0.recycled();
            free = Env(Some(node));
            len += 1;
            cur = match old {
                EnvNode::Cons { val, next } => {
                    drop(val);
                    next.0
                }
                EnvNode::Frame { vals, home } => {
                    drop(vals);
                    home.0
                }
                EnvNode::Module { data, frame, .. } => {
                    drop(data);
                    frame.0
                }
            };
        }
        self.free.set(free);
        self.free_len.set(len);
    }

    /// A node holding `node`: a free cell rewritten in place if there is one,
    /// otherwise a new allocation.
    #[inline]
    pub(crate) fn alloc(&self, node: EnvNode) -> EnvRef {
        let Some(mut cell) = self.free.replace(Env::EMPTY).0 else {
            return EnvRef::new(node);
        };
        let slot = cell.unique().expect("a free cell has one reference");
        let EnvNode::Cons { next, .. } = core::mem::replace(slot, node) else {
            unreachable!("a free cell is a `Cons`")
        };
        self.free.set(next);
        self.free_len.set(self.free_len.get() - 1);
        #[cfg(feature = "stats-env")]
        cell.0.reused();
        cell
    }

    /// Reserves a block of `n` consecutive ids and returns the base. Used by
    /// [`instantiate`] to give module items stable identities, preventing alias
    /// with individually minted ids.
    pub(crate) fn reserve_ids(&self, n: u64) -> u64 {
        let base = self.ids.get();
        self.ids.set(base + n);
        base
    }

    /// Gets a builtin module (`__Int`, `__Map`, etc.), instantiated on first
    /// reference and cached.
    ///
    /// Builtin modules are [`ModuleData`] with [`Expr::Builtin`] bodies. A written
    /// `__Int.add` is folded to its member at resolve, but this method handles
    /// remaining dynamic uses of the module as a value.
    pub(crate) fn builtin_module(&self, op: Builtin) -> Value {
        let slot = op.module_slot().expect("a builtin module");
        self.modules[slot]
            .get_or_init(|| {
                let items = op.items().expect("a builtin module has items");
                let bindings = items
                    .iter()
                    .map(|(name, op)| (Text::from_static(name), Expr::Builtin(*op)))
                    .collect();
                // The module's `const` declarations, name-sorted (the table already
                // is). Only `__Bool` has any; they populate the iota table an
                // iota's `<const .name>` rendering reads. The re-exporting `true` /
                // `false` items above forward to these by way of their arity-0
                // builtins, so the two spellings land on the same iota.
                let iotas = op
                    .iotas()
                    .expect("a builtin module has an iota list")
                    .iter()
                    .map(|n| Text::from_static(n))
                    .collect();
                // A builtin module is named after itself, so `__Mod.name __Int`
                // answers `"__Int"` — the same question a loaded module answers
                // with the name its source was resolved under.
                let data = Rc::new(ModuleData::from_bindings(
                    bindings,
                    Vec::new(),
                    iotas,
                    Box::new([]),
                    Box::new([]),
                    // A builtin module is a table of operations and nothing else:
                    // there is no source to have written a `__main` in.
                    None,
                    Some(Text::from_static(op.name())),
                ));
                eval::instantiate(data, &[], self).expect("a builtin module has no frame")
            })
            .clone()
    }
}

/// Frees the cells iteratively: dropping the list whole would recurse once per
/// cell.
impl Drop for Ctx {
    fn drop(&mut self) {
        let mut cur = self.free.replace(Env::EMPTY).0;
        while let Some(mut cell) = cur {
            cur = match cell.unique() {
                Some(EnvNode::Cons { next, .. }) => core::mem::replace(next, Env::EMPTY).0,
                _ => None,
            };
        }
    }
}

impl Default for Ctx {
    fn default() -> Self {
        Self::new()
    }
}

/// Performs a single walk to retrieve both the value at `index` and the
/// environment terminal. Resuming from the landing cell avoids re-walking links.
///
/// If the walk passes a [`Module`](EnvNode::Module) node, that node is returned
/// as the home, ensuring the resulting environment doesn't unexpectedly shift to
/// the module's own frame terminal.
fn lookup_and_home(env: &Env, index: u32) -> (Value, Env) {
    let mut cur = env;
    let mut rest = index as usize;
    let mut passed: Option<&Env> = None;
    let val = loop {
        match cur
            .0
            .as_deref()
            .expect("resolved index walked past the environment")
        {
            EnvNode::Cons { val, next } => {
                if rest == 0 {
                    break val.clone();
                }
                rest -= 1;
                cur = next;
            }
            EnvNode::Frame { vals, .. } => match vals.get(rest) {
                Some(val) => break val.clone(),
                None => unreachable!("resolved index walked past the captured frame"),
            },
            EnvNode::Module { frame, .. } => {
                if passed.is_none() {
                    passed = Some(cur);
                }
                cur = frame;
            }
        }
    };
    let home = match passed {
        Some(home) => home.clone(),
        None => cur.find_home(),
    };
    (val, home)
}

/// Builds a closure's captured frame from its resolved `plan` in one walk of
/// the defining environment. The plan is sorted by `outer`, so the walk only
/// moves forward, advancing to each capture's cell and writing the value to the
/// slot. Captures reaching the enclosing [`Frame`](EnvNode::Frame) use direct
/// indexing (`outer - depth`).
///
/// The frame is filled out of order (slot order is fixed at first use). The walk
/// also retrieves the chain's terminal for the frame's `home`, remembering any
/// [`Module`](EnvNode::Module) nodes passed.
fn build_frame_and_home(env: &Env, plan: &[Capture]) -> (Box<[Value]>, Env) {
    let mut vals: Vec<Value> = alloc::vec![Value::I64(0); plan.len()];
    let mut cur = env;
    let mut depth = 0u32;
    let mut passed: Option<&Env> = None;
    for cap in plan {
        loop {
            match cur
                .0
                .as_deref()
                .expect("capture index walked past the environment")
            {
                EnvNode::Cons { val, next } => {
                    if depth == cap.outer {
                        vals[cap.slot as usize] = val.clone();
                        break;
                    }
                    depth += 1;
                    cur = next;
                }
                EnvNode::Frame { vals: outer, .. } => {
                    match outer.get((cap.outer - depth) as usize) {
                        Some(val) => vals[cap.slot as usize] = val.clone(),
                        None => unreachable!("capture index walked past the captured frame"),
                    }
                    break;
                }
                // The terminal binds no name, so it is crossed without advancing
                // `depth`: a capture of a module's frame value counts only the
                // lexical cells between it and the reference.
                EnvNode::Module { frame, .. } => {
                    if passed.is_none() {
                        passed = Some(cur);
                    }
                    cur = frame;
                }
            }
        }
    }
    let home = match passed {
        Some(home) => home.clone(),
        None => cur.find_home(),
    };
    (vals.into_boxed_slice(), home)
}