elly_core/eval/

env.rs

//! Evaluation environment: the persistent [`EnvNode`] chain, and the realm's
//! free list of environment cells, which [`Ctx::release`] fills and
//! [`Ctx::alloc`] reuses. The tree-walker in `eval/mod.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 crate::builtins::Builtin;
use crate::code::{Capture, ChunkId, ModId};
use crate::sym::Sym;
use crate::value::Value;
use crate::{Ctx, HomeLeaf, Raised};

/// 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 ([`Node::Local`](crate::code::Node::Local))
/// 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()
    }

    /// The chunk and module of a [`Module`](EnvNode::Module) node, and its id
    /// block's base.
    pub(crate) fn as_module(&self) -> Option<(ChunkId, ModId, u64)> {
        match self.0.as_deref() {
            Some(EnvNode::Module {
                chunk,
                module,
                id_base,
                ..
            }) => Some((*chunk, *module, *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, Raised> {
        let (_, home, _) = self
            .find_module(depth)
            .ok_or_else(|| Raised::no_match(Sym::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],
            },
        })
    }

    /// The module terminal `depth` terminals out: the environment that ends in
    /// it, the node itself, and its chunk, module and id block's base.
    pub(crate) fn find_module(
        &self,
        mut depth: u32,
    ) -> Option<(&Env, &EnvRef, (ChunkId, ModId, 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 {
                    chunk,
                    module,
                    id_base,
                    frame,
                } => {
                    if depth == 0 {
                        return Some((cur, node, (*chunk, *module, *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 `env_stats`) 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 = crate::eval::env_stats::Tracked;

impl EnvRef {
    #[inline]
    pub(crate) fn new(node: EnvNode) -> Self {
        #[cfg(feature = "stats-env")]
        let node = crate::eval::env_stats::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);
        crate::eval::env_stats::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 !crate::eval::env_stats::freed(self.0.max.get()) {
                #[cfg(feature = "stats-env-drops")]
                crate::eval::env_stats::died();
            }
        }
    }
}

/// 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 [`Node::ModItem`](crate::code::Node::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`).
    ///
    /// `chunk` and `module` locate the module's code in the realm.
    ///
    /// `frame` is the environment the module was instantiated against (imports,
    /// host prelude, and identities), with slot order fixed by the module's
    /// 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 {
        chunk: ChunkId,
        module: ModId,
        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 {}

// ---------------------------------------------------------------------------
// The realm's free list of environment cells
// ---------------------------------------------------------------------------

/// 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 {
    /// 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/done/2026-09-29_elly-perf-env-stats.md`.
    #[inline]
    pub(crate) fn release(&self, env: Env) {
        #[cfg(feature = "stats-env")]
        crate::eval::env_stats::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 { frame, .. } => 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
    }

    /// Frees the cells of the free list iteratively, as the realm drops:
    /// dropping the list whole would recurse once per cell.
    pub(crate) fn free_cells(&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,
            };
        }
    }
}

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