elly_core/eval/

mod.rs

//! Naive tree-walking evaluator for the first Elly subset.
//!
//! Uses call-by-value evaluation. Environments are persistent linked lists of
//! bindings shared via `Rc` for efficient closure capture. The tree it walks is
//! a [`StaticChunk`](crate::code::StaticChunk): every node is read by its id
//! through the realm's chunk table, and the chunk being run is passed along as
//! `at`, the current-chunk register.
//!
//! What runs lives here, with the values and environments it builds: the
//! environment chain (`env`), pattern matching (`patmatch`), running the
//! builtins (`builtin`), and raised errors with what they leave as they
//! unwind (`error`). The static surface of the language (code, parsing,
//! modules, sources) is outside `eval/`.

pub(crate) mod builtin;
pub(crate) mod env;
#[cfg(feature = "stats-env")]
pub mod env_stats;
pub(crate) mod error;
mod patmatch;

use alloc::boxed::Box;
use alloc::rc::Rc;
use alloc::vec::Vec;

use rpds::{HashTrieMap, Vector};

use crate::code::{ChunkId, LambdaId, ModId, Node, NodeId, Pat, PatId, Plan, Run};

use crate::builtins::Builtin;
use crate::eval::env::{Env, EnvNode, EnvRef};
use crate::eval::error::Raised;
use crate::eval::patmatch::{match_pat, match_pattern};
use crate::sym::{Projection, Sym};
use crate::value::Value;
use crate::Ctx;

// ---------------------------------------------------------------------------
// The realm's run-time state
// ---------------------------------------------------------------------------

impl Ctx {
    /// 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
    }

    /// 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 live in the [`ELLY`](ChunkId::ELLY) chunk, with builtin
    /// leaves as item 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(|| {
                instantiate_module(ChunkId::ELLY, ModId::builtin(slot), &[], self)
                    .expect("a builtin module has no frame")
            })
            .clone()
    }
}

/// Evaluates the `__main` body of a module instance in its own environment.
/// Returns `Ok(None)` if no body is declared (e.g., a library).
///
/// This implements "runnable" module semantics: [`crate::load_module`] instantiates
/// modules without evaluating their bodies, ensuring `__main` is only executed
/// when explicitly targeted by a runner.
///
/// The body executes in the instance's [`Module`](EnvNode::Module) terminal.
/// As it is not a member, it has no reserved ID. Non-module instances raise
/// `.not_a_module`. Result interpretation is handled by the runner; see
/// `docs/done/2026-08-14_elly-run.md`.
pub fn eval_main(instance: &Value, ctx: &Ctx) -> Result<Option<Value>, Raised> {
    let Value::Module(home) = instance else {
        return Err(Raised::symbol(Sym::NOT_A_MODULE));
    };
    let EnvNode::Module { chunk, module, .. } = **home else {
        unreachable!("a module value always holds a module terminal")
    };
    let body = ctx.chunk(chunk).module(module).body;
    let Some(body) = body.get() else {
        return Ok(None);
    };
    ctx.clear_unwind();
    let result = eval(chunk, body, &Env::from_ref(home.clone()), ctx)?;
    Ok(Some(result))
}

/// Apply a value to a single argument in the realm `ctx` — the public entry
/// point behind a host's "call this value" surface (e.g. the Python bindings'
/// `elly.Fun.__call__`).
///
/// This is the same application step the evaluator uses internally (`apply_n`
/// with one argument): a closure call, list projection, or one step toward
/// saturating a builtin. `f` and `arg` must belong to `ctx`; closures minted by
/// the call continue its id source.
pub fn apply_with(f: &Value, arg: Value, ctx: &Ctx) -> Result<Value, Raised> {
    ctx.clear_unwind();
    apply1(f.clone(), arg, ctx)
}

/// Runs an expression chunk (see [`Ctx::parse`]) in `env`: its top module's
/// body, with no module terminal around it. Public entry point for host
/// evaluation (e.g., `elly.Env.eval`).
pub fn eval_env(chunk: ChunkId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
    let body = {
        let code = ctx.chunk(chunk);
        let top = code.module(code.top());
        assert!(
            top.members.len == 0 && top.frame.len == 0,
            "only an expression chunk runs on its own"
        );
        top.body
    };
    ctx.clear_unwind();
    eval(chunk, body, env, ctx)
}

/// Evaluates node `id` of chunk `at` in `env`.
pub(crate) fn eval(at: ChunkId, id: NodeId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
    match ctx.node(at, id) {
        // Resolved reference: look up value by index.
        Node::Local { index, .. } => Ok(env.lookup(index)),
        // Module sibling reference (see [`mod_item`]).
        Node::ModItem { index, depth, .. } => mod_item(env, index, depth, ctx),
        // Home-module leaf (see [`home_leaf`]).
        Node::Home { leaf, depth } => env.home_leaf(leaf, depth),
        // Recursive binding group (see [`recur`]).
        Node::Recur(group) => recur(at, group, env, ctx),
        // Block evaluation (see [`eval_block`]). Outlined to optimize I-cache.
        Node::Block { len, binds, exprs } => eval_block(at, len, binds, exprs, env, ctx),
        // Builtin operation. 0-arity builtins execute immediately; others return
        // a `Builtin` awaiting arguments.
        Node::Builtin(op) => {
            if op.arity() == 0 {
                builtin::invoke(op, &[], ctx)
            } else {
                // Avoid `with_capacity` to prevent unnecessary allocations during
                // curried application cloning.
                Ok(Value::Builtin {
                    op,
                    args: Vec::new(),
                })
            }
        }
        Node::Int(n) => Ok(Value::I64(n)),
        // A chunk keeps only the integers that do not fit `i64` as big ones.
        Node::BigInt(n) => Ok(Value::BigInt(Rc::new(ctx.chunk(at).int(n).clone()))),
        Node::Symbol(s) => Ok(Value::Symbol(s)),
        // String handles are shared and pre-decoded.
        Node::Str(s) => Ok(Value::Str(ctx.chunk(at).str(s).clone())),
        Node::Unit => Ok(Value::Unit),
        Node::List { len, elems } => {
            ctx.check_run(at, Run::List, elems, len);
            let mut vs = Vector::new();
            for i in 0..len {
                let elem = eval(at, elems.nth(i), env, ctx)?;
                vs.push_back_mut(elem);
            }
            Ok(Value::List(vs))
        }
        // Map literal: evaluate keys and values in source order. Later entries
        // with the same key overwrite previous ones.
        Node::Map { len, entries } => {
            ctx.check_run(at, Run::Map, entries, 2 * len);
            let mut m = HashTrieMap::new();
            for i in 0..len {
                let kv = eval(at, entries.nth(i), env, ctx)?;
                let vv = eval(at, entries.nth(len + i), env, ctx)?;
                m.insert_mut(kv, vv);
            }
            Ok(Value::Map(m))
        }
        // Closure creation: captures free variables according to the resolution plan.
        Node::Abs(code) => Ok(closure(at, code, ctx.next_id(), env, ctx)),
        // Call-by-value application. Callee and arguments are evaluated strictly
        // left-to-right. Small arities (≤ 4) are handled on the stack to avoid
        // heap allocation for the argument buffer.
        Node::App { len, args } => {
            ctx.check_run(at, Run::App, args, len);
            let callee = eval(at, args, env, ctx)?;
            // The call passes itself down as the site an error from the call
            // itself, not from evaluating its operands, unwinds through: the
            // callee records it, so that this stays a tail call.
            match len - 1 {
                1 => {
                    let arg = eval(at, args.nth(1), env, ctx)?;
                    apply1_at(callee, arg, at, id, ctx)
                }
                2 => {
                    let va = eval(at, args.nth(1), env, ctx)?;
                    let vb = eval(at, args.nth(2), env, ctx)?;
                    apply_n_at(callee, &[va, vb], at, id, ctx)
                }
                3 => {
                    let va = eval(at, args.nth(1), env, ctx)?;
                    let vb = eval(at, args.nth(2), env, ctx)?;
                    let vc = eval(at, args.nth(3), env, ctx)?;
                    apply_n_at(callee, &[va, vb, vc], at, id, ctx)
                }
                4 => {
                    let va = eval(at, args.nth(1), env, ctx)?;
                    let vb = eval(at, args.nth(2), env, ctx)?;
                    let vc = eval(at, args.nth(3), env, ctx)?;
                    let vd = eval(at, args.nth(4), env, ctx)?;
                    apply_n_at(callee, &[va, vb, vc, vd], at, id, ctx)
                }
                n => {
                    let mut argv: Vec<Value> = Vec::with_capacity(n as usize);
                    for i in 1..len {
                        argv.push(eval(at, args.nth(i), env, ctx)?);
                    }
                    apply_n_at(callee, &argv, at, id, ctx)
                }
            }
        }
        // Subject is evaluated once, then arms are tried in order. It comes
        // after the arm bodies in the run.
        Node::Case { len, conds, exprs } => {
            ctx.check_run(at, Run::Case, exprs, len + 1);
            let subj = eval(at, exprs.nth(len), env, ctx)?;
            run_arms(at, &subj, len, conds, exprs, env, ctx)
        }
        #[cfg(debug_assertions)]
        Node::Barrier { .. } => unreachable!("a barrier is not an operand"),
    }
}

/// A closure over lambda `code` of chunk `at`, with identity `id`: captures
/// free variables according to the resolution plan. `Plan::Chain` shares the
/// environment; `Plan::Frame` creates a new frame.
#[inline]
fn closure(at: ChunkId, code: LambdaId, id: u64, env: &Env, ctx: &Ctx) -> Value {
    let lambda = ctx.lambda(at, code);
    let env = match lambda.captures {
        Plan::Chain => env.clone(),
        // Capturing clones values and allocates cells but runs no code, so it
        // cannot add a chunk while the plan is borrowed.
        Plan::Frame(plan) => env.capture_env(ctx.chunk(at).captures(plan), ctx),
    };
    Value::Closure {
        id,
        chunk: at,
        lambda: code,
        applied: 0,
        arity: lambda.head.len as u8,
        env,
    }
}

/// Tries case arms in order. `NoMatch` refutations fall through; other errors propagate.
/// If no arms match, `.no_match` is raised.
#[inline(never)]
fn run_arms(
    at: ChunkId,
    subj: &Value,
    len: u32,
    conds: PatId,
    bodies: NodeId,
    env: &Env,
    ctx: &Ctx,
) -> Result<Value, Raised> {
    ctx.check_pat_run(at, Run::Case, conds, len);
    for i in 0..len {
        match match_pattern(at, conds.nth(i), subj, env.clone(), ctx) {
            // Not released explicitly: only 0.05% of node deaths happen here, and
            // holding the result across a release grows this recursive frame.
            Ok(arm_env) => {
                // What the arms before this one refuted explains nothing now.
                if i > 0 {
                    ctx.caught();
                }
                return eval(at, bodies.nth(i), &arm_env, ctx);
            }
            Err(Raised::NoMatch(_)) => ctx.caught(),
            Err(e) => return Err(e),
        }
    }
    Err(ctx.no_arm_matched(at, bodies.nth(len), subj))
}

/// Specialized path for single-argument application. Used by the call spine,
/// fold builtins, and match clauses. Binds one parameter, produces a partial
/// closure, gathers a builtin argument, or projects a list.
#[inline(always)]
pub(crate) fn apply1(fv: Value, av: Value, ctx: &Ctx) -> Result<Value, Raised> {
    apply1_at(fv, av, ChunkId::NONE, NodeId::NONE, ctx)
}

/// [`apply1`] for application node `call` of chunk `at`, which an error from
/// the call unwinds through, or [`NodeId::NONE`] for an application with no
/// node, such as a builtin's callback.
fn apply1_at(fv: Value, av: Value, at: ChunkId, call: NodeId, ctx: &Ctx) -> Result<Value, Raised> {
    match fv {
        Value::Closure {
            chunk,
            lambda,
            applied,
            arity,
            env,
            ..
        } => {
            let code = ctx.lambda(chunk, lambda);
            ctx.check_pat_run(chunk, Run::Head, code.head.first, code.head.len);
            // Bind argument and extend environment.
            let pat = code.head.first.nth(u32::from(applied));
            let call_env = match match_pattern(chunk, pat, &av, env, ctx) {
                Ok(env) => env,
                Err(r) => {
                    let pat = code.head.first.nth(u32::from(applied));
                    return Err(unbound(r, chunk, pat, &av, at, call, ctx));
                }
            };
            if applied + 1 < arity {
                // Return partial closure with updated applied count and environment.
                return Ok(Value::Closure {
                    id: ctx.next_id(),
                    chunk,
                    lambda,
                    applied: applied + 1,
                    arity,
                    env: call_env,
                });
            }
            let result = eval(chunk, code.body, &call_env, ctx);
            ctx.release(call_env);
            traced(result, at, call, ctx)
        }
        Value::Builtin {
            op,
            args: mut gathered,
        } => {
            // Unary builtins saturate from the stack.
            if gathered.is_empty() && op.arity() == 1 {
                return traced(builtin::invoke(op, &[av], ctx), at, call, ctx);
            }
            gathered.push(av);
            if gathered.len() == op.arity() {
                traced(builtin::invoke(op, &gathered, ctx), at, call, ctx)
            } else {
                Ok(Value::Builtin { op, args: gathered })
            }
        }
        Value::HostFn {
            code,
            args: gathered,
        } => {
            if gathered.is_empty() && code.arity == 1 {
                return traced((code.f)(&[av], ctx), at, call, ctx);
            }
            let gathered = extended(&gathered, &[av]);
            if gathered.len() == code.arity {
                traced((code.f)(&gathered, ctx), at, call, ctx)
            } else {
                Ok(Value::HostFn {
                    code,
                    args: gathered,
                })
            }
        }
        // Materialize item when a module is applied to a symbol.
        Value::Module(home) => {
            let result = match av {
                Value::Symbol(s) => materialize(&Env::from_ref(home), s, ctx),
                _ => Err(Raised::symbol(Sym::NOT_APPLICABLE)),
            };
            traced(result, at, call, ctx)
        }
        // Dispatch via prototype for all other types.
        fv => traced(receiver(fv, &av, &[], ctx), at, call, ctx),
    }
}

/// The error from matching `arg` against parameter `pat` of chunk `chunk`,
/// recorded as unwinding through application node `call` of chunk `at`. A
/// refutation escapes the parameter there, and says so if the call has a
/// node: a builtin applying a callback, as `__match` does its clauses, may
/// catch it.
#[cold]
#[inline(never)]
fn unbound(
    raised: Raised,
    chunk: ChunkId,
    pat: PatId,
    arg: &Value,
    at: ChunkId,
    call: NodeId,
    ctx: &Ctx,
) -> Raised {
    if call == NodeId::NONE {
        return raised;
    }
    ctx.unwound(at, call);
    ctx.escaped(raised, chunk, pat, arg)
}

/// `result`, recording an error as unwinding through application node `call`
/// of chunk `at`.
#[inline(always)]
fn traced(
    result: Result<Value, Raised>,
    at: ChunkId,
    call: NodeId,
    ctx: &Ctx,
) -> Result<Value, Raised> {
    if result.is_err() {
        ctx.unwound(at, call);
    }
    result
}

/// Applies a value to multiple arguments. Handles closures (multi-parameter
/// matching), builtins (gather until saturation), and list projections.
/// Over-application results loop onto the returned value.
///
/// Arguments are evaluated strictly left-to-right before matching patterns
/// left-to-right, ensuring evaluation errors surface before pattern refutations.
/// See `docs/done/2026-08-02_perf-less-currying.md` §3.
#[inline(always)]
fn apply_n(fv: Value, args: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    apply_n_at(fv, args, ChunkId::NONE, NodeId::NONE, ctx)
}

/// [`apply_n`] for application node `call` of chunk `at` (see
/// [`apply1_at`]).
fn apply_n_at(
    mut fv: Value,
    mut args: &[Value],
    at: ChunkId,
    call: NodeId,
    ctx: &Ctx,
) -> Result<Value, Raised> {
    while !args.is_empty() {
        match fv {
            // Matches arguments against remaining patterns left-to-right.
            // If arguments are exhausted, returns a partial closure with a fresh ID.
            // Otherwise, executes the body and loops leftover arguments onto the result.
            // Pattern misses raise `NoMatch`.
            Value::Closure {
                chunk,
                lambda,
                applied,
                arity,
                env,
                ..
            } => {
                let code = ctx.lambda(chunk, lambda);
                ctx.check_pat_run(chunk, Run::Head, code.head.first, code.head.len);
                let remaining = usize::from(arity - applied);
                let take = remaining.min(args.len());
                // Thread the env through each parameter match, consing bindings
                // onto the closure's captured (or partially-applied) env.
                let mut call_env = env;
                let first = code.head.first.nth(u32::from(applied));
                for (i, arg) in args[..take].iter().enumerate() {
                    let matched = match_pattern(chunk, first.nth(i as u32), arg, call_env, ctx);
                    call_env = match matched {
                        Ok(env) => env,
                        Err(r) => {
                            let pat = first.nth(i as u32);
                            return Err(unbound(r, chunk, pat, arg, at, call, ctx));
                        }
                    };
                }
                if take < remaining {
                    // Partial: no body runs yet; mint a fresh identity.
                    return Ok(Value::Closure {
                        id: ctx.next_id(),
                        chunk,
                        lambda,
                        applied: applied + take as u8,
                        arity,
                        env: call_env,
                    });
                }
                let result = eval(chunk, code.body, &call_env, ctx);
                ctx.release(call_env);
                fv = traced(result, at, call, ctx)?;
                args = &args[take..];
            }
            // Gathers arguments and invokes once saturated, looping leftovers onto the result.
            // If the argument spine satisfies the arity immediately, it invokes directly
            // from the slice to avoid `Value::Builtin` allocation.
            Value::Builtin {
                op,
                args: mut gathered,
            } => {
                let arity = op.arity();
                if gathered.is_empty() && args.len() >= arity {
                    fv = traced(builtin::invoke(op, &args[..arity], ctx), at, call, ctx)?;
                    args = &args[arity..];
                } else {
                    let take = (arity - gathered.len()).min(args.len());
                    gathered.extend(args[..take].iter().cloned());
                    if gathered.len() < arity {
                        return Ok(Value::Builtin { op, args: gathered });
                    }
                    fv = traced(builtin::invoke(op, &gathered, ctx), at, call, ctx)?;
                    args = &args[take..];
                }
            }
            // Similar gather-and-fire loop as builtins, dispatching via the host callback.
            Value::HostFn {
                code,
                args: gathered,
            } => {
                let arity = code.arity;
                if gathered.is_empty() && args.len() >= arity {
                    fv = traced((code.f)(&args[..arity], ctx), at, call, ctx)?;
                    args = &args[arity..];
                } else {
                    let take = (arity - gathered.len()).min(args.len());
                    let gathered = extended(&gathered, &args[..take]);
                    if gathered.len() < arity {
                        return Ok(Value::HostFn {
                            code,
                            args: gathered,
                        });
                    }
                    fv = traced((code.f)(&gathered, ctx), at, call, ctx)?;
                    args = &args[take..];
                }
            }
            // Materializes an item when applied to a symbol; leftovers loop onto the result.
            Value::Module(home) => {
                let result = match &args[0] {
                    Value::Symbol(s) => materialize(&Env::from_ref(home), *s, ctx),
                    _ => Err(Raised::symbol(Sym::NOT_APPLICABLE)),
                };
                fv = traced(result, at, call, ctx)?;
                args = &args[1..];
            }
            // Dispatches by passing the entire remaining argument spine to the
            // method in one call (see [`receiver`]).
            fv => return traced(receiver(fv, &args[0], &args[1..], ctx), at, call, ctx),
        }
    }
    Ok(fv)
}

/// Concatenates `prefix` and `more` into a single allocation.
/// Used by [`Value::HostFn`] for efficient argument gathering during partial application.
fn extended(prefix: &[Value], more: &[Value]) -> Box<[Value]> {
    let mut all = Vec::with_capacity(prefix.len() + more.len());
    all.extend_from_slice(prefix);
    all.extend_from_slice(more);
    all.into_boxed_slice()
}

/// Returns the prototype of a value. Objects use their own prototype; others
/// use the corresponding builtin module, providing a nominal type for all values.
///
/// Iotas resolve to their declaring module, allowing them to be treated as
/// objects of that module. Callables (closures, builtins, host functions)
/// resolve to `__Fun`.
pub(crate) fn proto_of(v: &Value, ctx: &Ctx) -> Value {
    match v {
        Value::Object(obj) => obj.proto(),
        Value::Iota { home, .. } => Value::Module(home.clone()),
        Value::I64(_) | Value::BigInt(_) => ctx.builtin_module(Builtin::Int),
        Value::Symbol(_) => ctx.builtin_module(Builtin::Sym),
        Value::Str(_) => ctx.builtin_module(Builtin::Str),
        Value::Unit => ctx.builtin_module(Builtin::Unit),
        Value::List(_) => ctx.builtin_module(Builtin::List),
        Value::Map(_) => ctx.builtin_module(Builtin::Map),
        Value::Closure { .. } | Value::Builtin { .. } | Value::HostFn { .. } => {
            ctx.builtin_module(Builtin::Fun)
        }
        Value::Module(_) => ctx.builtin_module(Builtin::Mod),
    }
}

/// Whether `value`'s prototype is the module node `expr` of chunk `at` names —
/// the general form of an
/// `as <Proto>` pattern, where [`ProtoRef::Kind`] is the compiled one. A reference
/// that is not a module raises `.not_a_module`: it is a mistake about the pattern
/// rather than about the subject, so it is a real error and not a refutation.
///
/// Outlined for the reason [`receiver`] is: `match_pattern` is on every call's
/// path, and its arms pay for each other's code size.
#[inline(never)]
pub(crate) fn proto_is(
    at: ChunkId,
    expr: NodeId,
    value: &Value,
    env: &Env,
    ctx: &Ctx,
) -> Result<bool, Raised> {
    let expected = eval(at, expr, env, ctx)?;
    if !matches!(expected, Value::Module(_)) {
        return Err(Raised::symbol(Sym::NOT_A_MODULE));
    }
    Ok(proto_of(value, ctx) == expected)
}

/// Resolves a module sibling reference by walking to the home module and
/// materializing the item at `index`.
///
/// The index is assigned during resolution against the module's sorted table,
/// enabling direct slice access. Only module-item bodies contain `ModItem`,
/// and they always run under a `Module` home terminal, which is found by
/// walking through captured frames.
///
/// Outlined to maintain I-cache residency of `eval_env`.
///
/// If the index is past the item table, it is treated as an iota, which is
/// derived as a pair of the terminal and position.
///
/// `depth` specifies how many terminals to skip to find the owning module.
/// A `recur` group nested in a module body adds a terminal to the chain, requiring
/// a skip for the enclosing module's items.
#[inline(never)]
fn mod_item(env: &Env, index: u32, depth: u32, ctx: &Ctx) -> Result<Value, Raised> {
    let (env, home, (chunk, module, id_base)) = env
        .find_module(depth)
        .ok_or_else(|| Raised::symbol(Sym::NO_MODULE))?;
    let member = ctx.chunk(chunk).member(module, index);
    let Some(member) = member else {
        // Handle iotas: derived from terminal identity and index.
        let code = ctx.chunk(chunk);
        let index = index - code.member_len(module);
        if code.iota(module, index).is_none() {
            return Err(Raised::symbol(Sym::MISSING_PROPERTY));
        }
        return Ok(Value::Iota {
            home: home.clone(),
            index,
        });
    };
    materialize_body(chunk, member.node, env, id_base, index, ctx)
}

/// Evaluates a `recur` group by creating a `Module` terminal over the
/// current environment and executing the body.
///
/// This is instantiation with a cons-shaped frame, avoiding copies by
/// sharing the lexical environment. ID blocks are reserved per evaluation,
/// ensuring different activations of the same `recur` group have distinct
/// item identities. Bindings are materialized on reference.
#[inline(never)]
fn recur(at: ChunkId, group: ModId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
    let (len, body) = {
        let code = ctx.chunk(at);
        (code.member_len(group), code.module(group).body)
    };
    let home = EnvRef::new(EnvNode::Module {
        chunk: at,
        module: group,
        id_base: ctx.reserve_ids(u64::from(len)),
        frame: env.clone(),
    });
    eval(at, body, &Env::from_ref(home), ctx)
}

/// Evaluates a block by threading the environment through clauses.
/// Bindings extend the environment for subsequent clauses; other clauses
/// execute for effect. The value of the final clause is returned.
fn eval_block(
    at: ChunkId,
    len: u32,
    binds: PatId,
    exprs: NodeId,
    env: &Env,
    ctx: &Ctx,
) -> Result<Value, Raised> {
    let Some(last) = len.checked_sub(1) else {
        return Ok(Value::Unit);
    };
    ctx.check_pat_run(at, Run::Block, binds, len);
    ctx.check_run(at, Run::Block, exprs, len);
    let mut env = env.clone();
    for i in 0..last {
        match ctx.pat(at, binds.nth(i)) {
            Pat::None => {
                eval(at, exprs.nth(i), &env, ctx)?;
            }
            pat => {
                let v = eval(at, exprs.nth(i), &env, ctx)?;
                env = match_pat(at, pat, &v, env, ctx)
                    .map_err(|r| ctx.escaped(r, at, binds.nth(i), &v))?;
            }
        }
    }
    match ctx.pat(at, binds.nth(last)) {
        Pat::None => {
            let result = eval(at, exprs.nth(last), &env, ctx);
            ctx.release(env);
            result
        }
        pat => {
            let v = eval(at, exprs.nth(last), &env, ctx)?;
            let env = match_pat(at, pat, &v, env, ctx)
                .map_err(|r| ctx.escaped(r, at, binds.nth(last), &v))?;
            ctx.release(env);
            Ok(v)
        }
    }
}

/// Instantiates a compiled module, the top module of `chunk` (see
/// [`Ctx::compile_module`]), giving it its identity.
///
/// `frame` provides outer values against the module's frame names. A length
/// mismatch raises `.module_arity`.
pub fn instantiate(chunk: ChunkId, frame: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    let top = ctx.chunk(chunk).top();
    instantiate_module(chunk, top, frame, ctx)
}

/// Instantiates module `module` of chunk `chunk`, creating its
/// [`Module`](EnvNode::Module) terminal and returning it as a [`Value::Module`].
///
/// This assigns the module an identity (fresh `Rc`) and reserves its ID block
/// so items can be stamped with stable IDs (see `materialize_body`).
///
/// `frame` provides outer values against the module's frame names. A length
/// mismatch raises `.module_arity`. The frame is stored as a flat
/// [`Frame`](EnvNode::Frame), though `recur` builds the terminal directly.
pub(crate) fn instantiate_module(
    chunk: ChunkId,
    module: ModId,
    frame: &[Value],
    ctx: &Ctx,
) -> Result<Value, Raised> {
    let (frame_len, len) = {
        let code = ctx.chunk(chunk);
        (code.module(module).frame.len, code.member_len(module))
    };
    if frame.len() != frame_len as usize {
        return Err(Raised::symbol(Sym::MODULE_ARITY));
    }
    let id_base = ctx.reserve_ids(u64::from(len));
    let frame = if frame.is_empty() {
        Env::EMPTY
    } else {
        Env::EMPTY.frame(Box::from(frame))
    };
    Ok(Value::Module(EnvRef::new(EnvNode::Module {
        chunk,
        module,
        id_base,
        frame,
    })))
}

/// Evaluates an item's body, node `body` of `chunk`, in its module terminal.
/// This is the common path for [`mod_item`] and [`materialize`].
///
/// Literal abstraction bodies are built directly with the item's reserved
/// ID (`id_base + index`), ensuring multiple accesses produce equal closures.
/// This avoids `eval` dispatch and `Ctx` counter writes for performance.
///
/// Only function definitions claim the item's identity. Forwarded callables
/// retain their original identity, while data items or nested closures are
/// processed via `eval`.
#[inline]
fn materialize_body(
    chunk: ChunkId,
    body: NodeId,
    env: &Env,
    id_base: u64,
    index: u32,
    ctx: &Ctx,
) -> Result<Value, Raised> {
    if let Node::Abs(code) = ctx.node(chunk, body) {
        return Ok(closure(chunk, code, id_base + u64::from(index), env, ctx));
    }
    eval(chunk, body, env, ctx)
}

/// Materializes the item named `name` from the module object `home`.
/// Binary-searches for the index and evaluates the body in the terminal.
/// Uses the object's own node as the terminal to avoid environment allocation.
/// Raises `.missing_property` if the name is absent.
fn materialize(env: &Env, name: Sym, ctx: &Ctx) -> Result<Value, Raised> {
    let (chunk, module, id_base) = env
        .as_module()
        .expect("a module object always holds a module terminal");
    let member = {
        let code = ctx.chunk(chunk);
        code.index_of(module, name)
            .map(|index| (index, code.member(module, index)))
    };
    let Some((index, Some(member))) = member else {
        return Err(Raised::symbol(Sym::MISSING_PROPERTY));
    };
    materialize_body(chunk, member.node, env, id_base, index, ctx)
}

/// Applies a receiver to a symbol. This is the dispatch path for all non-callable,
/// non-module values. The symbol identifies a member of the receiver's prototype,
/// and the receiver is passed as an argument. [`proto_of`] ensures this is total.
///
/// List projection takes precedence: numeric symbols on lists project indices.
/// Other symbols dispatch to `__List`.
///
/// Non-symbol arguments raise `.not_applicable`.
///
/// Outlined to maintain I-cache residency in `apply1` and `apply_n`.
#[inline(never)]
fn receiver(this: Value, name: &Value, rest: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    let Value::Symbol(s) = name else {
        return Err(Raised::symbol(Sym::NOT_APPLICABLE));
    };
    let s = *s;
    if let Value::List(elems) = &this {
        let index = match ctx.projection(s) {
            Projection::Name => None,
            Projection::Index(i) => Some(i),
            Projection::TooLarge => return Err(Raised::symbol(Sym::BAD_PROJECTION)),
        };
        if let Some(index) = index {
            let projected = elems
                .get(index as usize)
                .cloned()
                .ok_or_else(|| Raised::symbol(Sym::PROJECTION_OUT_OF_RANGE))?;
            return apply_n(projected, rest, ctx);
        }
    }
    let proto = if let Value::Object(obj) = &this {
        obj.proto.clone()
    } else if let Value::Module(home) = proto_of(&this, ctx) {
        home
    } else {
        unreachable!("a prototype is always a module value")
    };
    dispatch(proto, this, s, rest, ctx)
}

/// Dispatches a method by materializing `name` from `proto` and applying it
/// to the receiver and any remaining arguments.
///
/// Example: `x .m a b` is equivalent to `(materialize (proto of x) .m) x a b`.
///
/// The lookup is a binary search over the item table, ensuring locals are private.
/// Arguments are handled similarly to the call spine in `eval_env`, with small
/// arities processed on the stack.
fn dispatch(
    proto: EnvRef,
    this: Value,
    name: Sym,
    rest: &[Value],
    ctx: &Ctx,
) -> Result<Value, Raised> {
    let method = materialize(&Env::from_ref(proto), name, ctx)?;
    match rest {
        [] => apply1(method, this, ctx),
        [a] => apply_n(method, &[this, a.clone()], ctx),
        [a, b] => apply_n(method, &[this, a.clone(), b.clone()], ctx),
        [a, b, c] => apply_n(method, &[this, a.clone(), b.clone(), c.clone()], ctx),
        _ => {
            let mut all: Vec<Value> = Vec::with_capacity(rest.len() + 1);
            all.push(this);
            all.extend_from_slice(rest);
            apply_n(method, &all, ctx)
        }
    }
}