elly_core/

eval.rs

//! A naive, tree-walking evaluator for the first Elly subset.
//!
//! Call-by-value (the spec defers the strategy choice). Environments are a
//! persistent linked list of bindings shared via `Rc`, so closures capture
//! their defining environment cheaply.

use alloc::borrow::Cow;
use alloc::boxed::Box;
use alloc::rc::Rc;
use alloc::string::{String, ToString};
use alloc::vec::Vec;
use core::cell::{Cell, OnceCell};
use core::cmp::Ordering;
use core::hash::{Hash, Hasher};

use num_bigint::{BigInt, Sign};
use rpds::{HashTrieMap, Vector};

use crate::ast::{
    json_str, recur_body, Capture, Captures, Expr, HomeLeaf, Lambda, MapKey, Pattern, ProtoRef,
    Rest, Text, TyKind,
};
use crate::parse::{ImportSpec, ModuleName};

/// A loaded module: an immutable table of **unevaluated** item bodies
/// ("dehydrated code"), sorted by name. Built once by [`crate::compile_module`]
/// and then frozen behind an `Rc`. Sibling references inside the bodies are
/// compiled to [`Expr::ModItem`] — a sink resolved through the home module carried
/// in the environment ([`EnvNode::Module`]), not through any registry — so a
/// `ModuleData` owns nothing but `Expr`s and never points back at a value, and
/// the value heap stays acyclic. See `docs/done/2026-08-07_elly-modules-v0.md`.
///
/// A sibling reference reaches its body by `index` (a direct slice index, the hot
/// path); an outside `M.name` access, which has only a name, binary-searches.
#[derive(Debug, PartialEq, Eq)]
pub struct ModuleData {
    items: Box<[(Text, Expr)]>,
    /// The bodies this module declares with `local` — its **private** bindings —
    /// name-sorted. They are members exactly as the items are, materialized the
    /// same way and addressed by the same index space, immediately after the
    /// items: a [`ModItem`](Expr::ModItem) index at or past `items.len()` and
    /// below [`len`](Self::len) addresses `locals[index - items.len()]`.
    ///
    /// **Privacy is what this second table is.** An outside `M.name` access
    /// binary-searches the items ([`index_of`](Self::index_of)) and a sibling
    /// reference carries an index the resolver assigned, so a table the resolver
    /// can address and `index_of` does not search is unreachable from outside by
    /// construction — no flag to consult and no check to run.
    ///
    /// The locals sit *before* the iotas rather than after them because a local's
    /// body may be a lambda, and a materialized lambda takes its identity from
    /// `id_base + index` — so every id-bearing member has to be inside the block
    /// [`instantiate`] reserves. See `docs/done/2026-08-13_elly-modules-local.md`.
    locals: Box<[(Text, Expr)]>,
    /// The names this module declares with `const` — its **iotas** — name-sorted.
    /// They are members alongside the items and share one address space: a
    /// [`ModItem`](Expr::ModItem) index at or past [`len`](Self::len) addresses
    /// `iotas[index - len()]`.
    ///
    /// An iota takes no frame slot and reserves no id. "Iota *i* of instance *X*"
    /// is determined by the pair, and the declaration is inert code, so the value
    /// is derived on reference — the same way a function item's identity is
    /// derived from `id_base + index` rather than allocated up front. Only the
    /// name is stored, and only so the value can render itself.
    iotas: Box<[Text]>,
    /// The names of the module's **frame** slots, in the order the bodies index
    /// them — the module's import signature. Kept for the arity check in
    /// [`instantiate`] and for a host that wants to know what a compiled module
    /// asks to be instantiated against. Empty for a module with no frame.
    ///
    /// The module's own imports come first, one slot each, followed by whatever
    /// frame names the compile was given.
    frame_names: Box<[Text]>,
    /// The specs of the leading frame slots — what this module imports, in slot
    /// order, so `imports[i]` is the spec of the slot `frame_names[i]` names. The
    /// const stage resolves each one and fills the slot with the instance (see
    /// [`crate::load_module`]).
    imports: Box<[ImportSpec]>,
    /// The module's **body**: one expression evaluated in the module's own
    /// environment, by whoever holds the module rather than by the module itself.
    /// Two things share the slot, differing only in who evaluates it and when:
    ///
    /// - a [`recur`](Expr::Recur) group's body, run immediately after the
    ///   terminal is built ([`recur`]);
    /// - a module source's `__main`, run by a *runner* pointed at that source,
    ///   and skipped for the same module reached by an `import`.
    ///
    /// It is kept beside the tables rather than appended to one as an anonymous
    /// item because the tables are name-sorted and binary-searched, so a nameless
    /// entry would be a hole in the one invariant `ModuleData` has. Staying out of
    /// the member index space is also what makes it unnameable: an outside
    /// `M.__main` is symbol projection into `items`, and there is nothing there to
    /// find. See `docs/done/2026-08-14_elly-run.md`.
    body: Option<Expr>,
    /// The canonical name this code came from, when a host named it. It belongs
    /// here rather than on the instance: it is a property of the code, and one
    /// compiled module may be instantiated many times. `None` for a module the
    /// host compiled without naming (and for a [`recur`](Expr::Recur) group, which
    /// came from no source of its own).
    name: Option<ModuleName>,
}

impl ModuleData {
    /// Freeze a module's resolved bindings into its item table. The bindings arrive
    /// sorted by name from [`crate::resolve::resolve_module_bodies`], which is what
    /// the `ModItem` indexes in the bodies count against, so the order is kept.
    pub(crate) fn from_bindings(
        bindings: alloc::vec::Vec<(Text, Expr)>,
        locals: alloc::vec::Vec<(Text, Expr)>,
        iotas: Box<[Text]>,
        frame_names: Box<[Text]>,
        imports: Box<[ImportSpec]>,
        body: Option<Expr>,
        name: Option<ModuleName>,
    ) -> ModuleData {
        debug_assert!(
            bindings
                .windows(2)
                .all(|w| w[0].0.as_str() < w[1].0.as_str()),
            "module bindings must be sorted by name and distinct"
        );
        debug_assert!(
            locals.windows(2).all(|w| w[0].0.as_str() < w[1].0.as_str()),
            "module locals must be sorted by name and distinct"
        );
        debug_assert!(
            iotas.windows(2).all(|w| w[0].as_str() < w[1].as_str()),
            "module iotas must be sorted by name and distinct"
        );
        debug_assert!(
            imports.len() <= frame_names.len(),
            "every import is a frame slot"
        );
        ModuleData {
            items: bindings.into_boxed_slice(),
            locals: locals.into_boxed_slice(),
            iotas,
            frame_names,
            imports,
            body,
            name,
        }
    }

    /// The item table, name-sorted: what a [`recur`](Expr::Recur) renders and what
    /// the resolver walks. The hot paths index it by position ([`item`](Self::item))
    /// or binary-search it ([`index_of`](Self::index_of)) instead.
    pub(crate) fn items(&self) -> &[(Text, Expr)] {
        &self.items
    }

    /// The item bodies, for the resolution pass to rewrite in place. A
    /// [`recur`](Expr::Recur)'s group is built at parse and resolved with the rest
    /// of the tree, so its bodies are still open when the `ModuleData` exists —
    /// unlike a file module's, which are resolved before
    /// [`from_bindings`](Self::from_bindings) freezes them.
    pub(crate) fn items_mut(&mut self) -> &mut [(Text, Expr)] {
        &mut self.items
    }

    /// The body at `index` — the position a [`Expr::ModItem`] carries — covering
    /// the items and then the [locals](Self::locals), which are one index space.
    /// `None` for an index at or past [`len`](Self::len), which is an iota.
    fn item(&self, index: u32) -> Option<&Expr> {
        let index = index as usize;
        match self.items.get(index) {
            Some((_, body)) => Some(body),
            None => self
                .locals
                .get(index - self.items.len())
                .map(|(_, body)| body),
        }
    }

    /// The position of `name` in the sorted table — the index an
    /// [`Expr::ModItem`] would carry — found by binary search. An outside
    /// `M.name` access has only a name, so it starts here and then goes through
    /// [`item`](Self::item) like a sibling reference does.
    fn index_of(&self, name: &str) -> Option<u32> {
        self.items
            .binary_search_by(|(n, _)| n.as_str().cmp(name))
            .ok()
            .map(|i| i as u32)
    }

    /// How many **id-bearing** members the module has — its items and its
    /// [locals](Self::locals) — which is also where the *iota* half of the member
    /// address space begins, and the size of the id block [`instantiate`]
    /// reserves. Iotas mint no id, so they are not counted.
    fn len(&self) -> usize {
        self.items.len() + self.locals.len()
    }

    /// The name of the iota at `index`, counted from the start of the iota table
    /// (so `member index - len()`). `None` for an index past the declarations,
    /// which is what makes a stale member address a `.missing_property` rather
    /// than a panic.
    fn iota(&self, index: u32) -> Option<&Text> {
        self.iotas.get(index as usize)
    }

    /// The module's item names, in sorted order — its **public** listing, and the
    /// only names an outside `M.name` access can reach.
    pub fn item_names(&self) -> Vec<&Text> {
        self.items.iter().map(|(n, _)| n).collect()
    }

    /// The names the module declares with `local`, in sorted order. A local
    /// appears here and nowhere else — it is not an item, so it is not reachable
    /// as `M.name` from outside — which is the same shape a private
    /// [iota](Self::iota_names) has, and it is offered for the same reason: a
    /// host's introspection (a debugger, a const stage) wants to see what a
    /// module declares, while the language gives no way to reach it.
    pub fn local_names(&self) -> Vec<&Text> {
        self.locals.iter().map(|(n, _)| n).collect()
    }

    /// The names the module declares with `const`, in sorted order. A **private**
    /// iota appears here and nowhere else — it is not an item, so it is not
    /// reachable as `M.name` from outside.
    pub fn iota_names(&self) -> &[Text] {
        &self.iotas
    }

    /// The names of the module's frame slots, in slot order — what it must be
    /// instantiated against (see [`instantiate`]). Empty for a module with no
    /// frame.
    pub fn frame_names(&self) -> &[Text] {
        &self.frame_names
    }

    /// The specs of the module's imports, in slot order: `imports()[i]` is what
    /// `frame_names()[i]` was imported from. The list is a **static, auditable**
    /// account of every module this one can reach, readable without running
    /// anything — which is the point of writing an import rather than calling a
    /// loader.
    pub fn imports(&self) -> &[ImportSpec] {
        &self.imports
    }

    /// The module's [body](Self::body), if it has one: a `recur` group's body, or
    /// the `__main` a source declared. A runner reads it here and evaluates it in
    /// the instance's own environment (see [`crate::eval_main`]); everything else
    /// leaves it alone, which is what makes an *imported* `__main` inert.
    pub fn body(&self) -> Option<&Expr> {
        self.body.as_ref()
    }

    /// The body, for the resolution pass to rewrite in place — the counterpart of
    /// [`items_mut`](Self::items_mut), and needed for the same reason: a
    /// [`recur`](Expr::Recur)'s group is built at parse, so its body is still open
    /// when the `ModuleData` exists.
    pub(crate) fn body_mut(&mut self) -> Option<&mut Expr> {
        self.body.as_mut()
    }

    /// The canonical name the module's code came from, when a host named it —
    /// what `__Mod.name` reports and what the const stage deduplicates instances
    /// by. `None` for code no host named.
    pub fn name(&self) -> Option<&ModuleName> {
        self.name.as_ref()
    }
}

/// **Instantiate** a compiled module: build its [`Module`](EnvNode::Module)
/// terminal — the environment its item bodies run in — and hand it back as the
/// [`Value::Module`] that *is* that terminal.
///
/// This is where a module gets an identity. The `Rc` is fresh per call, so two
/// instantiations of the same [`ModuleData`] are distinct objects, and one
/// instance is equal to itself across accesses. It is also where the module's
/// **id block** is reserved: one bump of the context's id source covering every
/// item, so materializing item `i` can stamp its closure with the stable
/// `id_base + i` rather than a fresh id (see `materialize_body` and
/// `docs/done/2026-08-13_elly-modules-env.md`).
///
/// `frame` supplies the module's outer values, positionally, against the names
/// [`ModuleData::frame_names`] recorded at compile time — the module's import
/// signature, filled in. A length mismatch raises `.module_arity` rather than
/// going through: it is memory-safe (indices are checked) but silently wrong, so
/// it is worth catching where the mistake is. A module with no frame takes an
/// empty slice.
///
/// The values are copied into a flat [`Frame`](EnvNode::Frame) node, which is the
/// shape a fixed slot list wants. The terminal's `frame` is a plain `Env`, so a
/// consumer that needs a cons chain instead — `recur`, whose frame *is* the
/// enclosing lexical environment — builds the terminal directly rather than
/// through here.
pub fn instantiate(data: Rc<ModuleData>, frame: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    if frame.len() != data.frame_names.len() {
        return Err(raise_sym("module_arity"));
    }
    let id_base = ctx.reserve_ids(data.len() as u64);
    let frame = if frame.is_empty() {
        None
    } else {
        Some(Rc::new(EnvNode::Frame {
            vals: frame.to_vec().into_boxed_slice(),
            home: None,
        }))
    };
    Ok(Value::Module(Rc::new(EnvNode::Module {
        data,
        id_base,
        frame,
    })))
}

/// Evaluate a module instance's **body** — the `__main` its source declared — in
/// the module's own environment, and hand back the result. `Ok(None)` for a
/// module that declares none, which is what a library is.
///
/// This is the whole of what makes a module *runnable*, and it is a call rather
/// than a phase of loading: [`crate::load_module`] instantiates every module it
/// reaches and evaluates none of them, so a `__main` in an imported module is
/// inert and only the module a runner was pointed at ever gets here. That is the
/// Python `if __name__ == "__main__"` semantics, arrived at structurally.
///
/// The body runs in the instance's own [`Module`](EnvNode::Module) terminal, so
/// it reaches the module's members exactly as an item body does. It is not a
/// member itself, so it claims no reserved id: a closure it builds mints one from
/// `ctx` the ordinary way. A non-module `instance` raises `.not_a_module`.
///
/// The result is handed back rather than interpreted. What a runner does with it
/// — apply it to the root capability, report a still-partial closure — is the
/// runner's policy; 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(raise_sym("not_a_module"));
    };
    let EnvNode::Module { data, .. } = &**home else {
        unreachable!("a module value always holds a module terminal")
    };
    match data.body() {
        Some(body) => eval_env(body, &Some(Rc::clone(home)), ctx).map(Some),
        None => Ok(None),
    }
}

/// The thin evaluation context threaded through the tree-walker: the unique-id
/// source (closure identities) and the builtin module cache. It carries **no**
/// module registry and no loader — a module's imports are resolved before
/// evaluation begins (see [`crate::load_module`]), and a loaded module is an
/// ordinary `Rc`-held value, kept alive only by whatever holds it.
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],
}

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

    /// A context **resuming** an id source at `ids`, so identities it mints
    /// continue where an earlier context left off.
    ///
    /// A host that builds a fresh `Ctx` per call and hands values out between
    /// them — the Python bindings do exactly this — needs it: a module reserves
    /// its item id block when it is instantiated (see [`instantiate`]), and the
    /// programs that later use it mint closure ids from a *different* context. If
    /// both started at zero, an item and an unrelated closure would get the same
    /// id and `__eq` would call them equal. The host reads
    /// [`ids_used`](Self::ids_used) back when the context is done and seeds the
    /// next one with it.
    ///
    /// The counter is carried by value rather than shared behind an `Rc`: the
    /// pointer chase it would add to every closure mint costs ~2% on `fib_naive`,
    /// and only the host needs the continuity.
    pub fn with_ids(ids: u64) -> Self {
        Ctx {
            ids: Cell::new(ids),
            modules: core::array::from_fn(|_| OnceCell::new()),
        }
    }

    /// How far this context's id source has run — the value to seed a successor
    /// with (see [`with_ids`](Self::with_ids)).
    pub fn ids_used(&self) -> u64 {
        self.ids.get()
    }

    /// Mint the next unique id from the runtime's id source. Each `&`-abstraction
    /// (and each partial application) stamps its closure with one, giving callables
    /// an identity for equality/order.
    fn next_id(&self) -> u64 {
        let n = self.ids.get();
        self.ids.set(n + 1);
        n
    }

    /// Reserve a **block** of `n` consecutive ids and return its base. Used by
    /// [`instantiate`] to give a module's items stable identities: the ids come
    /// from the same monotone source as [`next_id`](Self::next_id), so a block
    /// cannot alias another block or any individually minted id.
    fn reserve_ids(&self, n: u64) -> u64 {
        let base = self.ids.get();
        self.ids.set(base + n);
        base
    }

    /// The value of a builtin module (`__Int`, `__Map`, …), instantiated on first
    /// reference and cached for the life of the context.
    ///
    /// The module is an ordinary [`ModuleData`] whose item bodies are
    /// [`Expr::Builtin`] leaves, so materializing `__Int.add` runs the same code an
    /// `M.name` access on a loaded module runs, and yields the unsaturated
    /// [`Value::Builtin`] a direct reference would. Nothing here is on the hot path:
    /// a *written* `__Int.add` is folded to its member at resolve, and this is what
    /// the remaining dynamic uses — the module as a value — go through.
    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();
                // 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(),
                    Box::new([]),
                    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())),
                ));
                instantiate(data, &[], self).expect("a builtin module has no frame")
            })
            .clone()
    }
}

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

/// An **object**: a payload and the prototype that gives it its type. Behind the
/// `Rc` a [`Value::Object`] carries, so an object is one payload word and a clone
/// is one refcount bump.
///
/// `proto` holds exactly what a [`Value::Module`] holds — the
/// [`Module`](EnvNode::Module) terminal that *is* the instance — so a prototype is
/// code plus the environment that code runs in, and a method dispatched on an
/// object runs in the same environment `M.name` would give it. It is also the same
/// handle a [`Value::Iota`]'s `home` is, so an object and an iota answer the
/// nominal question (`as <Module>`, `__proto x`) identically.
///
/// `data` is one slot holding any value. Records with named fields are a later
/// feature; a map payload is the v0 idiom for several fields. It is reachable only
/// from the module's own code, through [`__value`](crate::HomeLeaf::Value) — so a
/// module may change its representation without changing its interface. See
/// `docs/done/2026-08-15_elly-objects-v0.md`.
#[derive(Debug)]
pub struct ObjectData {
    proto: Rc<EnvNode>,
    data: Value,
}

impl ObjectData {
    /// The object's prototype, as the module value it is.
    pub fn proto(&self) -> Value {
        Value::Module(Rc::clone(&self.proto))
    }

    /// The object's payload. Public to Rust because a debugger and an embedding
    /// host sit outside the language's module scope; no *builtin* hands it out,
    /// so Elly code cannot reach it except through its own module's `__value`.
    pub fn data(&self) -> &Value {
        &self.data
    }
}

/// A runtime value.
#[derive(Debug, Clone)]
pub enum Value {
    /// A machine-word integer — the **canonical** representation for any integer
    /// that fits in `i64`. Inline (one word, no heap), so the common arithmetic
    /// path neither allocates nor sets the enum width. The invariant "an integer
    /// is [`Value::BigInt`] *iff* it does not fit `i64`" is what makes equality and
    /// hashing well-defined (no value has two representations); it is maintained by
    /// routing every wide result through [`Value::from_bigint`].
    I64(i64),
    /// An arbitrary-precision integer, used **only** for magnitudes outside `i64`.
    /// Behind an `Rc` so the ~4-word `BigInt` does not widen `Value` (one word) *and*
    /// cloning a wide value is a refcount bump rather than a digit-vector copy — the
    /// big ints are immutable, so sharing is sound. A value here is always
    /// `|n| > i64::MAX` by the canonical invariant (see [`Value::I64`]).
    BigInt(Rc<BigInt>),
    /// A symbol literal, stored *without* its dot (`foo` for `.foo`) as an owned
    /// cheap-clone [`Text`]; the dot is re-added when displayed.
    Symbol(Text),
    /// An owned, immutable, cheap-clone UTF-8 string ([`Text`]). Equality and order
    /// are Rust's `&str` (byte order over UTF-8 *is* Unicode scalar-value order, so
    /// lexicographic comparison is a plain `str::cmp`). Rendered quoted / re-escaped.
    Str(Text),
    /// A runtime list of any arity, backed by an immutable `rpds::Vector`
    /// (cheap structural-sharing clone / append, O(log n) random access). The
    /// empty list is **unit** — there is no separate `Unit` value.
    List(Vector<Value>),
    /// A closure capturing its defining environment over shared `code`. `id` is a
    /// per-runtime unique identity minted when the closure is built (an
    /// `&`-abstraction evaluating, or a *partial* application producing a new
    /// closure), so closures compare by *identity* (two separately-created `&x x`
    /// are distinct, and `f x` twice yields two unequal partials) rather than by
    /// structure — the shared `code` `Rc` is invisible to `__eq`. `code` is the
    /// abstraction's `Lambda` (parameter patterns + body); `applied` counts the
    /// parameters already bound into `env`, so the remaining ones are
    /// `code.head[applied..]`. A partial application is one `Rc::clone(code)` plus
    /// a bumped `applied` and an extended `env` — no per-partial `Lambda`
    /// allocation. Applying the closure *matches* the next arguments against those
    /// remaining patterns (see `apply_n`).
    Closure {
        id: u64,
        code: Rc<Lambda>,
        applied: u8,
        env: Env,
    },
    /// An immutable, persistent, **unordered** map from keys to values, backed by
    /// `rpds::HashTrieMap` (cheap structural-sharing `with`; unspecified iteration
    /// order, stable within a build). Any value is a key; keys are identified by
    /// structural value equality (see `impl PartialEq` / `impl Hash`). See the
    /// *maps* section of `docs/elly-spec.md`.
    Map(HashTrieMap<Value, Value>),
    /// A partially-applied builtin: a native `__…` operation plus the arguments
    /// gathered so far. Invoked once `args.len()` reaches the op's arity.
    Builtin { op: Builtin, args: Vec<Value> },
    /// A partially-applied **host function**: a callback the embedder supplied
    /// ([`HostFn`]) plus the arguments gathered so far, shaped exactly like
    /// [`Builtin`](Value::Builtin) and fired the same way — so a host callback
    /// curries, over-applies and partially applies like everything else, with no
    /// application path of its own.
    ///
    /// This is the whole FFI boundary in the calling direction, and it is a
    /// *value* rather than an `Expr` variant deliberately: a host function
    /// carries its own code, so it stays meaningful wherever it is handed. The
    /// alternative — an index into a table on the [`Ctx`] — would misdispatch as
    /// soon as a value outlived the context that made it, which a host building a
    /// fresh `Ctx` per call does by design (see [`Ctx::with_ids`]).
    ///
    /// Identity is the `Rc` pointer plus the applied arguments, matching
    /// `Builtin`'s "same operation, equal arguments". The name
    /// [`Value::HostObj`] is deliberately left unused, for opaque host handles.
    ///
    /// The applied prefix is a `Box<[Value]>` rather than the `Vec` the builtin
    /// arm carries, for width: an `Rc` plus a `Vec` is four payload words and
    /// would take `Value` from four words to five, which the size goldens pin
    /// (`tests/sizes.rs`) and which `docs/done/2026-08-13_elly-modules-env.md`
    /// measured the cost of. It is not a slower shape — the builtin path clones
    /// its `Vec` on every partial application, and `Vec::clone` allocates
    /// `capacity == len`, so both are one allocation per curried step.
    ///
    /// [`Value::HostObj`]: Value
    HostFn {
        code: Rc<HostFn>,
        args: Box<[Value]>,
    },
    /// A **module instance**: the module's own [`Module`](EnvNode::Module)
    /// terminal — the environment its item bodies run in. The value *is* the
    /// terminal rather than holding a [`ModuleData`]
    /// beside one, so a module's code and the environment it was instantiated
    /// against cannot be recombined, and materializing an item reuses this node
    /// instead of allocating a fresh one. One payload word, so `Value` stays four
    /// words. Applied to a symbol it *materializes* that item (see
    /// `apply1`/`apply_n`). Identity is the `Rc` **pointer** (like a closure's
    /// identity), not the item contents — two separate loads compare unequal; a
    /// content-addressed brand is deferred (see
    /// `docs/done/2026-08-13_elly-modules-env.md`).
    Module(Rc<EnvNode>),
    /// An **iota**: an atomic identity a module declared with `const`, equal to
    /// itself and to nothing else. It has no structure and no payload, so there
    /// is nothing to read out of it and nothing outside the module can conjure
    /// one — reaching it means reaching the module.
    ///
    /// Identity is the pair (instance, position): `home` is the instance's
    /// [`Module`](EnvNode::Module) terminal — the very node a [`Value::Module`]
    /// holds — and `index` the iota's position in
    /// [`ModuleData::iota_names`]. Nothing is minted and no id is reserved; the
    /// value is *derived* whenever the declaration is referenced, so two
    /// references to one iota of one instance are equal while two instantiations
    /// of the same module mint disjoint sets. See
    /// `docs/done/2026-08-13_elly-modules-iotas.md`.
    Iota { home: Rc<EnvNode>, index: u32 },
    /// An **object**: a payload plus the prototype module that gives it its type
    /// (see [`ObjectData`]). Built only by the [`__new`](crate::HomeLeaf::New) leaf
    /// of the module that owns the type, so a value of a type is minted by that
    /// type's own code and nowhere else.
    ///
    /// Applied to a symbol it **dispatches**: the name is materialized out of the
    /// prototype and applied to the object itself, so `x.m a` is the module's `m`
    /// with the receiver already bound (see `apply1`/`apply_n`). Compared by
    /// contents over the payload and by identity over the prototype, so objects
    /// are usable as map keys.
    Object(Rc<ObjectData>),
}

/// Structural value equality, eliminated by `__eq` (see the *equality* section of
/// `docs/elly-spec.md`). Data compares structurally (integers mathematically,
/// symbols/strings by text, lists elementwise, maps by content regardless of
/// build order); callables compare by identity — builtins by operation then
/// applied arguments, closures by their unique id. Values of different kinds are
/// never equal. There is no total order over all values: the `<` / `>` ordering
/// patterns compare only within `Int` / `Str` (see `order_match`).
impl PartialEq for Value {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Value::I64(a), Value::I64(b)) => a == b,
            (Value::BigInt(a), Value::BigInt(b)) => a == b,
            // An `I64` and a `BigInt` never compare equal: by the canonical
            // invariant they partition the integers (a `BigInt` never fits `i64`),
            // so they cannot denote the same number.
            (Value::Symbol(a), Value::Symbol(b)) => a == b,
            (Value::Str(a), Value::Str(b)) => a == b,
            (Value::List(a), Value::List(b)) => a == b,
            // `HashTrieMap`'s own `PartialEq` is content-based (order-independent).
            (Value::Map(a), Value::Map(b)) => a == b,
            // Same operation and equal applied arguments.
            (Value::Builtin { op: o1, args: a1 }, Value::Builtin { op: o2, args: a2 }) => {
                o1 == o2 && a1 == a2
            }
            // The same reading for a host callback, with the allocation standing
            // in for the operation: a `HostFn` has no structure to compare, so
            // two of one name are two functions.
            (
                Value::HostFn {
                    code: c1, args: a1, ..
                },
                Value::HostFn {
                    code: c2, args: a2, ..
                },
            ) => Rc::ptr_eq(c1, c2) && a1 == a2,
            (Value::Closure { id: i1, .. }, Value::Closure { id: i2, .. }) => i1 == i2,
            // A module value is its instance's identity: the terminal's `Rc`
            // pointer, not the item contents (mirrors the closure "compare by
            // identity" precedent).
            (Value::Module(a), Value::Module(b)) => Rc::ptr_eq(a, b),
            // An iota is the instance it was declared by plus its position, so
            // two iotas of one instance differ and one iota of two instantiations
            // does too.
            (
                Value::Iota {
                    home: a, index: i, ..
                },
                Value::Iota {
                    home: b, index: j, ..
                },
            ) => i == j && Rc::ptr_eq(a, b),
            // An object is its prototype by *identity* and its payload by
            // *contents* — the nominal/structural mix objects are for. The payload
            // half is what makes two accesses of one data item compare equal, and
            // what lets an object be a map key.
            (Value::Object(a), Value::Object(b)) => {
                Rc::ptr_eq(&a.proto, &b.proto) && a.data == b.data
            }
            _ => false,
        }
    }
}

impl Eq for Value {}

/// A `Hash` consistent with the structural `PartialEq` above — required because a
/// `Value` is a `HashTrieMap` key. A per-variant discriminant is mixed in first,
/// so the symbol `.0`, the integer `0`, and the string `"0"` cannot collide by
/// construction. A `Map` key hashes **order-independently** (each entry folded
/// through a fresh sub-hasher, the results summed) so two equal maps built in
/// different insertion orders — or with hash-colliding keys — still hash equal.
impl Hash for Value {
    fn hash<H: Hasher>(&self, state: &mut H) {
        core::mem::discriminant(self).hash(state);
        match self {
            Value::I64(n) => n.hash(state),
            Value::BigInt(n) => n.hash(state),
            Value::Symbol(s) => s.hash(state),
            Value::Str(s) => s.hash(state),
            Value::List(vs) => {
                for v in vs.iter() {
                    v.hash(state);
                }
            }
            Value::Map(m) => {
                let mut acc: u64 = 0;
                for (k, v) in m.iter() {
                    let mut h = FnvHasher::new();
                    k.hash(&mut h);
                    v.hash(&mut h);
                    acc = acc.wrapping_add(h.finish());
                }
                acc.hash(state);
            }
            Value::Builtin { op, args } => {
                op.hash(state);
                for a in args {
                    a.hash(state);
                }
            }
            Value::HostFn { code, args } => {
                (Rc::as_ptr(code) as usize).hash(state);
                for a in args {
                    a.hash(state);
                }
            }
            Value::Closure { id, .. } => id.hash(state),
            // Hash by the same identity used for equality: the terminal's pointer.
            Value::Module(home) => (Rc::as_ptr(home) as usize).hash(state),
            Value::Iota { home, index } => {
                (Rc::as_ptr(home) as usize).hash(state);
                index.hash(state);
            }
            // Mirrors the equality above: the prototype's pointer, the payload's
            // contents.
            Value::Object(obj) => {
                (Rc::as_ptr(&obj.proto) as usize).hash(state);
                obj.data.hash(state);
            }
        }
    }
}

/// A minimal, deterministic, no_std FNV-1a `Hasher` used only to fold a map's
/// entries into an order-independent digest (see `impl Hash for Value`). Not the
/// hasher the `HashTrieMap` itself uses.
struct FnvHasher(u64);

impl FnvHasher {
    fn new() -> Self {
        FnvHasher(0xcbf2_9ce4_8422_2325)
    }
}

impl Hasher for FnvHasher {
    fn finish(&self) -> u64 {
        self.0
    }
    fn write(&mut self, bytes: &[u8]) {
        for &b in bytes {
            self.0 ^= u64::from(b);
            self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
        }
    }
}

/// A **host function**: a native callback the embedder hands the runtime as a
/// value, behind the `Rc` a [`Value::HostFn`] carries.
///
/// It is what a builtin is, minus the compile-time enum: a name, an arity, and
/// code. The evaluator gathers arguments against `arity` and calls `f` once they
/// are all there, so a host callback is strict and curried like everything else,
/// and the host writes an ordinary Rust closure rather than an application
/// protocol.
///
/// The `Ctx` reaches `f` so a callback that is handed an Elly callable can call
/// it back ([`apply_with`]) under the same id source; without it a closure the
/// callback minted would collide with one the program already holds.
///
/// **Arity is at least 1.** A zero-argument callback could never fire — nothing
/// applies a value to no arguments — so a host that wants a constant supplies
/// the value itself.
pub struct HostFn {
    name: Text,
    arity: usize,
    f: Box<HostCall>,
}

/// The contract a host callback signs: a whole call's arguments — exactly
/// [`arity`](HostFn::arity) of them, since the evaluator gathers before it fires
/// — plus the [`Ctx`], answering a value or a [`Raised`].
pub type HostCall = dyn Fn(&[Value], &Ctx) -> Result<Value, Raised>;

impl HostFn {
    /// A host function called as `name`, taking `arity` arguments.
    ///
    /// The name is for rendering and diagnostics only — identity is the
    /// allocation, so two `HostFn`s of one name are two functions.
    ///
    /// Panics on `arity == 0`, which is not a function the runtime could ever
    /// call (see the type's docs).
    pub fn new(
        name: impl Into<Text>,
        arity: usize,
        f: impl Fn(&[Value], &Ctx) -> Result<Value, Raised> + 'static,
    ) -> HostFn {
        assert!(arity > 0, "a host function takes at least one argument");
        HostFn {
            name: name.into(),
            arity,
            f: Box::new(f),
        }
    }

    /// The name the function renders under.
    pub fn name(&self) -> &Text {
        &self.name
    }

    /// How many arguments it is called with.
    pub fn arity(&self) -> usize {
        self.arity
    }
}

/// The callback is not `Debug`, so the derive cannot apply; the shape a
/// `Value::HostFn` shows is its name and arity, which is what identifies it in a
/// dump anyway.
impl core::fmt::Debug for HostFn {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_struct("HostFn")
            .field("name", &self.name)
            .field("arity", &self.arity)
            .finish_non_exhaustive()
    }
}

/// A native builtin operation in the reserved `__` namespace. All are curried;
/// see the *integers* section of `docs/elly-spec.md`.
#[allow(clippy::enum_variant_names)]
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Builtin {
    IntAdd,
    IntSub,
    IntMul,
    IntPow,
    IntDivrem,
    IntFor,
    ErrRaise,
    ErrCatch,
    Match,
    ListSize,
    ListGet,
    ListAppend,
    ListWith,
    ListSplit,
    Eq,
    MapNil,
    MapWith,
    MapGet,
    MapGets,
    MapFor,
    MapMerge,
    MapCat,
    MapWithout,
    MapSize,
    IntStr,
    StrPack,
    StrUnpack,
    SymFrom,
    SymStr,
    ModName,
    /// `__proto v` — the prototype of *any* value: an object's own, and the
    /// builtin module for every other kind. A bare builtin, like `__eq` and
    /// `__match`, because it cuts across kinds rather than belonging to one. It is
    /// total, so it is the classifier `as <Proto>` and the objects design are
    /// written against, and it grants nothing: a module value carries no authority
    /// to construct with it or to unwrap against it.
    Proto,
    /// The object **constructor**, `(prototype, payload)`. Not reachable by name:
    /// it is absent from [`from_name`](Builtin::from_name) and from
    /// [`ALL`](Builtin::ALL), and the only route to a value of it is the
    /// [`__new`](crate::HomeLeaf::New) leaf, which supplies the prototype from the
    /// module the body is written in. So there is no way to mint an object of a
    /// type you are not writing.
    ObjNew,
    /// The object **payload reader**, `(prototype, object)` — reached the same one
    /// way, through [`__value`](crate::HomeLeaf::Value), and refusing an object
    /// whose prototype is not the one supplied (`.foreign_object`), so a method
    /// cannot unwrap a value that merely passed through it.
    ObjValue,
    // The **builtin modules** — a 0-arity builtin each, naming the module that
    // gathers the operations above as its items (see [`MODULES`]).
    Int,
    Str,
    Sym,
    List,
    Map,
    Err,
    Mod,
    /// `__Fun`, the prototype of every callable kind — a closure, a builtin, and
    /// a host function. It has no items yet: `docs/todo/elly-function-arity.md`
    /// is what gives it `nargs` / `nfree` / `nrets`. It exists for the totality of
    /// [`Proto`](Builtin::Proto), which is enough on its own to make it a module.
    Fun,
}

/// A builtin module's item table: `(item name, the builtin it names)`, **sorted
/// by name** — the order a [`ModuleData`] wants, and what
/// [`member`](Builtin::member) binary-searches.
type Members = &'static [(&'static str, Builtin)];

/// The **builtin modules**, in cache-slot order (see [`Ctx::builtin_module`]):
/// the 0-arity builtin naming each module, its shadowable bare alias, and its
/// items. The `__<Ns>_<op>` naming convention the flat builtins used to spell out
/// lives here instead — `__Int.add` is the module `__Int`'s item `add` — so this
/// table is the whole of the `__` namespace's structure.
///
/// `__match`, `__eq` and `__proto` are not in it: they cut across kinds and
/// belong to no module.
const MODULES: &[(Builtin, &str, Members)] = &[
    (
        Builtin::Int,
        "Int",
        &[
            ("add", Builtin::IntAdd),
            ("divrem", Builtin::IntDivrem),
            ("for", Builtin::IntFor),
            ("mul", Builtin::IntMul),
            ("pow", Builtin::IntPow),
            ("str", Builtin::IntStr),
            ("sub", Builtin::IntSub),
        ],
    ),
    (
        Builtin::Str,
        "Str",
        &[("pack", Builtin::StrPack), ("unpack", Builtin::StrUnpack)],
    ),
    (
        Builtin::Sym,
        "Sym",
        &[("from", Builtin::SymFrom), ("str", Builtin::SymStr)],
    ),
    (
        Builtin::List,
        "List",
        &[
            ("append", Builtin::ListAppend),
            ("get", Builtin::ListGet),
            ("size", Builtin::ListSize),
            ("split", Builtin::ListSplit),
            ("with", Builtin::ListWith),
        ],
    ),
    (
        Builtin::Map,
        "Map",
        &[
            ("cat", Builtin::MapCat),
            ("for", Builtin::MapFor),
            ("get", Builtin::MapGet),
            ("gets", Builtin::MapGets),
            ("merge", Builtin::MapMerge),
            ("nil", Builtin::MapNil),
            ("size", Builtin::MapSize),
            ("with", Builtin::MapWith),
            ("without", Builtin::MapWithout),
        ],
    ),
    (
        Builtin::Err,
        "Err",
        &[("catch", Builtin::ErrCatch), ("raise", Builtin::ErrRaise)],
    ),
    (Builtin::Mod, "Mod", &[("name", Builtin::ModName)]),
    // No items yet, and a module all the same: it is the prototype the three
    // callable kinds answer `__proto` with (see [`Builtin::Fun`]).
    (Builtin::Fun, "Fun", &[]),
];

/// How many builtin modules there are — the width of the [`Ctx`] cache.
const NMODULES: usize = MODULES.len();

impl Builtin {
    /// Every **nameable** builtin, in declaration order — the source of truth for
    /// tooling that needs to enumerate the `__` namespace (e.g. the bench suite's
    /// coverage check). Keep in sync with the enum: a new variant forces an arm in
    /// the exhaustive `name`/`arity` matches just below, which sit next to this
    /// list.
    ///
    /// [`ObjNew`](Builtin::ObjNew) and [`ObjValue`](Builtin::ObjValue) are
    /// deliberately absent: no name reaches them, only the home-module leaves, so
    /// listing them would claim a `__` name that does not resolve. They still
    /// render under one ([`name`](Builtin::name)) — a partially-applied `__new` has
    /// to say what it is.
    pub const ALL: &'static [Builtin] = &[
        Builtin::IntAdd,
        Builtin::IntSub,
        Builtin::IntMul,
        Builtin::IntPow,
        Builtin::IntDivrem,
        Builtin::IntFor,
        Builtin::ErrRaise,
        Builtin::ErrCatch,
        Builtin::Match,
        Builtin::ListSize,
        Builtin::ListGet,
        Builtin::ListAppend,
        Builtin::ListWith,
        Builtin::ListSplit,
        Builtin::Eq,
        Builtin::MapNil,
        Builtin::MapWith,
        Builtin::MapGet,
        Builtin::MapGets,
        Builtin::MapFor,
        Builtin::MapMerge,
        Builtin::MapCat,
        Builtin::MapWithout,
        Builtin::MapSize,
        Builtin::IntStr,
        Builtin::StrPack,
        Builtin::StrUnpack,
        Builtin::SymFrom,
        Builtin::SymStr,
        Builtin::ModName,
        Builtin::Proto,
        Builtin::Int,
        Builtin::Str,
        Builtin::Sym,
        Builtin::List,
        Builtin::Map,
        Builtin::Err,
        Builtin::Mod,
        Builtin::Fun,
    ];

    /// Resolve a `__`-name to its builtin, if any: a bare name (`__eq`, `__match`),
    /// a builtin **module** (`__Int`), or a module **member** in the dotted form
    /// [`name`](Self::name) renders (`__Int.add`).
    ///
    /// A `<sym>` token can never contain a `.` — the dot is a Muon sigil — so the
    /// dotted case is not what the parser hits; it is how tooling, and the
    /// `Builtin::ALL` round-trip, read a rendered name back. The parser reaches a
    /// member through [`member`](Self::member) instead, once the resolver has folded
    /// `__Int .add` (see `resolve.rs`).
    pub fn from_name(name: &str) -> Option<Builtin> {
        if let Some((ns, item)) = name.split_once('.') {
            return Builtin::from_name(ns)?.member(item);
        }
        Some(match name {
            "__match" => Builtin::Match,
            "__eq" => Builtin::Eq,
            "__proto" => Builtin::Proto,
            "__Int" => Builtin::Int,
            "__Str" => Builtin::Str,
            "__Sym" => Builtin::Sym,
            "__List" => Builtin::List,
            "__Map" => Builtin::Map,
            "__Err" => Builtin::Err,
            "__Mod" => Builtin::Mod,
            "__Fun" => Builtin::Fun,
            _ => return None,
        })
    }

    /// The builtin module this bare **alias** names, if any: `Int` → `__Int`. The
    /// aliases are the resolver's bottom tier — the language's prelude — consulted
    /// after everything a name could be lexically bound to, so they shadow by
    /// construction (see `resolve.rs`).
    pub fn from_alias(name: &str) -> Option<Builtin> {
        MODULES
            .iter()
            .find(|(_, alias, _)| *alias == name)
            .map(|(op, _, _)| *op)
    }

    /// This builtin module's items, or `None` for anything that is not one.
    fn items(self) -> Option<Members> {
        MODULES
            .iter()
            .find(|(op, _, _)| *op == self)
            .map(|(_, _, items)| *items)
    }

    /// The builtin module's cache slot in a [`Ctx`], or `None` for anything that is
    /// not one. Positional, so it is the same slot for the life of the process.
    fn module_slot(self) -> Option<usize> {
        MODULES.iter().position(|(op, _, _)| *op == self)
    }

    /// The item `name` of this builtin **module**, if it has one: `__Int`'s `add`
    /// is `__Int.add` is [`Builtin::IntAdd`]. `None` for a name the module does not
    /// hold, and for any builtin that is not a module — which is what makes it safe
    /// to ask on every callee of a call spine (see the fold in `resolve.rs`).
    pub fn member(self, name: &str) -> Option<Builtin> {
        let items = self.items()?;
        items
            .binary_search_by(|(item, _)| (*item).cmp(name))
            .ok()
            .map(|i| items[i].1)
    }

    /// The value kind this builtin **module** is the prototype of, if it is one —
    /// what lets an `as <Proto>` pattern naming it compile to a discriminant test
    /// (see [`crate::ProtoRef`]).
    ///
    /// `None` for anything that is not a module, and for `__Err`: it is a
    /// namespace of operations, and no value answers `__proto` with it, so `as
    /// Err` is rejected rather than compiled into a check that cannot hold.
    pub fn proto_kind(self) -> Option<TyKind> {
        Some(match self {
            Builtin::Int => TyKind::Int,
            Builtin::Str => TyKind::Str,
            Builtin::Sym => TyKind::Sym,
            Builtin::List => TyKind::List,
            Builtin::Map => TyKind::Map,
            Builtin::Mod => TyKind::Mod,
            Builtin::Fun => TyKind::Fun,
            _ => return None,
        })
    }

    /// How many arguments the op consumes before it fires. A `0`-arity op is a
    /// bare **value**: it fires the moment its name is referenced, with no
    /// arguments. `__Map.nil` is the empty map; a builtin **module** is its module
    /// value.
    fn arity(self) -> usize {
        match self {
            Builtin::MapNil
            | Builtin::Int
            | Builtin::Str
            | Builtin::Sym
            | Builtin::List
            | Builtin::Map
            | Builtin::Err
            | Builtin::Mod
            | Builtin::Fun => 0,
            Builtin::Proto
            | Builtin::ErrRaise
            | Builtin::ListSize
            | Builtin::MapSize
            | Builtin::IntStr
            | Builtin::StrPack
            | Builtin::StrUnpack
            | Builtin::SymFrom
            | Builtin::SymStr
            | Builtin::ModName => 1,
            Builtin::IntAdd
            | Builtin::IntSub
            | Builtin::IntMul
            | Builtin::IntPow
            | Builtin::IntDivrem => 2,
            // `__match clauses val`: strict in the clause list and the subject.
            // `__new proto data` / `__value proto obj` — the prototype is the
            // first argument, and the home-module leaf has already supplied it.
            Builtin::ObjNew
            | Builtin::ObjValue
            | Builtin::Match
            | Builtin::ErrCatch
            | Builtin::ListGet
            | Builtin::ListAppend
            | Builtin::ListSplit
            | Builtin::MapGet
            | Builtin::MapGets
            | Builtin::MapCat
            | Builtin::MapWithout => 2,
            Builtin::ListWith | Builtin::MapWith | Builtin::MapFor | Builtin::MapMerge => 3,
            Builtin::IntFor | Builtin::Eq => 4,
        }
    }

    /// Whether argument `i` is a **callback**: a value this builtin only ever
    /// *applies*, never stores in its result. A literal `&`-abstraction written
    /// straight into such a position cannot outlive the call, so the resolver gives
    /// it [`Captures::Chain`] — it shares the defining environment instead of
    /// copying a frame (see `resolve.rs`, and
    /// `docs/done/2026-08-14_elly-perf-closure-capture.md`).
    ///
    /// Keep this in step with the arms of [`invoke`]: an argument listed here must be
    /// reached only through `apply1` / `apply_n` there. Storing positions
    /// (`__List.with`'s element, `__Map.with`'s value) are deliberately absent — a
    /// closure put into a list or a map does outlive the call.
    pub(crate) fn applies_arg(self, i: usize) -> bool {
        match self {
            // `__Err.catch handler thunk` — both are run by the catch.
            Builtin::ErrCatch => i == 0 || i == 1,
            // `__eq a b then else` — one of the two branches is forced.
            Builtin::Eq => i == 2 || i == 3,
            // `__Int.for from to init f` — the fold callback.
            Builtin::IntFor => i == 3,
            // `__Map.for m init f` / `__Map.merge m1 m2 f` — the fold callbacks.
            Builtin::MapFor | Builtin::MapMerge => i == 2,
            _ => false,
        }
    }

    /// Whether argument `i` is a **list of callbacks**: a list this builtin only
    /// applies the elements of. Only `__match`'s clause list, whose clauses are tried
    /// against the subject in order. When such an argument is written as a *literal*
    /// list, each literal abstraction in it gets [`Captures::Chain`] — this is the
    /// per-call closure minting the capture change made expensive.
    pub(crate) fn applies_elements_of(self, i: usize) -> bool {
        matches!(self, Builtin::Match) && i == 0
    }

    /// The reserved `__`-name this builtin is referenced by: a module member is
    /// **dotted** (`__Int.add`), which is how it is written and how it renders.
    pub fn name(self) -> &'static str {
        match self {
            Builtin::IntAdd => "__Int.add",
            Builtin::IntSub => "__Int.sub",
            Builtin::IntMul => "__Int.mul",
            Builtin::IntPow => "__Int.pow",
            Builtin::IntDivrem => "__Int.divrem",
            Builtin::IntFor => "__Int.for",
            Builtin::ErrRaise => "__Err.raise",
            Builtin::ErrCatch => "__Err.catch",
            Builtin::Match => "__match",
            Builtin::ListSize => "__List.size",
            Builtin::ListGet => "__List.get",
            Builtin::ListAppend => "__List.append",
            Builtin::ListWith => "__List.with",
            Builtin::ListSplit => "__List.split",
            Builtin::Eq => "__eq",
            Builtin::MapNil => "__Map.nil",
            Builtin::MapWith => "__Map.with",
            Builtin::MapGet => "__Map.get",
            Builtin::MapGets => "__Map.gets",
            Builtin::MapFor => "__Map.for",
            Builtin::MapMerge => "__Map.merge",
            Builtin::MapCat => "__Map.cat",
            Builtin::MapWithout => "__Map.without",
            Builtin::MapSize => "__Map.size",
            Builtin::IntStr => "__Int.str",
            Builtin::StrPack => "__Str.pack",
            Builtin::StrUnpack => "__Str.unpack",
            Builtin::SymFrom => "__Sym.from",
            Builtin::SymStr => "__Sym.str",
            Builtin::ModName => "__Mod.name",
            Builtin::Proto => "__proto",
            // The two capabilities render under the leaf that produced them —
            // there is no other way to hold one, so this is the name a reader
            // wrote (see [`ALL`](Builtin::ALL) for why they are not in it).
            Builtin::ObjNew => "__new",
            Builtin::ObjValue => "__value",
            Builtin::Int => "__Int",
            Builtin::Str => "__Str",
            Builtin::Sym => "__Sym",
            Builtin::List => "__List",
            Builtin::Map => "__Map",
            Builtin::Err => "__Err",
            Builtin::Mod => "__Mod",
            Builtin::Fun => "__Fun",
        }
    }
}

/// A shared, persistent environment: a **nameless** cons list of the bindings the
/// running activation has made (innermost/most-recent 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` `next` links and cloning the cell's value — a pointer chase, no name
/// compare and no per-link clone (contrast the old name-keyed cons list) — and an
/// index that runs past the consed cells lands in the frame, an array index. The
/// resolver (`resolve.rs`) assigns each reference the exact number of cells
/// between it and its binder, in the same order the matcher conses them.
pub type Env = Option<Rc<EnvNode>>;

/// 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`, not a
/// node — [`Env`] is an `Option<Rc<EnvNode>>`, which the null-pointer niche keeps
/// one word wide, so ending a chain costs no allocation and no refcount traffic. A lambda activation conses one `Cons`
/// per name its head binds — zero for a binder-less head (`&_`, `&(< 2)`) — so a
/// partial application's environment is just the consed prefix, shared with later
/// partials by `Rc` refcount (no copy-on-write). Names are not stored: references
/// were resolved to a de Bruijn index against this list's shape.
#[derive(Debug)]
pub enum EnvNode {
    Cons {
        val: Value,
        next: Env,
    },
    /// The **home terminal** of a module item's environment: it carries the item's
    /// module in place of the empty terminal, so a [`Expr::ModItem`] sibling
    /// reference resolves
    /// by walking out to it (see the `ModItem` arm of [`eval_env`]). It binds no
    /// name and is not counted by de Bruijn `Local` indices — a valid index always
    /// lands on a `Cons` or a `Frame` before reaching here. A materialized closure
    /// captures an environment ending in this node, which is how it keeps its module
    /// alive (an `Rc` edge closure → module, with no edge back — see
    /// `docs/done/2026-08-07_elly-modules-v0.md`).
    ///
    /// This node **is** the module instance: [`Value::Module`] is a handle on it,
    /// minted by [`instantiate`]. So the value and the environment its items run
    /// in are one allocation, and `M.name` from outside runs the body in exactly
    /// the environment a sibling reference would.
    ///
    /// `id_base` is the module's reserved id block: item `i` stamps the closure it
    /// materializes to with `id_base + i`, so `M.f == M.f` (see
    /// `materialize_body`).
    ///
    /// `frame` is the environment the module was **instantiated against** — its
    /// imports, host prelude and module-minted identities, in the slot order
    /// [`ModuleData::frame_names`] fixed at compile time. A de Bruijn index walks
    /// *through* this node into `frame` **without counting it**, so a frame
    /// reference is an ordinary [`Expr::Local`] and needs no variant of its own.
    /// The node binds no name itself, which is what makes passing the walk on
    /// consistent rather than an off-by-one.
    ///
    /// The shape of `frame` is deliberately left open: it is an `Env`, so a flat
    /// [`Frame`](EnvNode::Frame) (named imports — a fixed slot list) and a cons
    /// chain (`recur` — the frame *is* the enclosing lexical environment) are both
    /// reachable through one code path. `None` is a module with no frame, which is
    /// every module compiled by [`crate::compile_module`].
    ///
    /// Holding an environment is what gives up modules v0's *structural*
    /// acyclicity — a `ModuleData` could hold no `Value`, so no cycle was
    /// expressible — for a
    /// *temporal* one: a frame holds only values that existed before the frame did,
    /// and immutability means none of them can later be made to point back at it.
    /// See `docs/done/2026-08-13_elly-modules-env.md`.
    Module {
        data: Rc<ModuleData>,
        id_base: u64,
        frame: Env,
    },
    /// A closure's captured **frame**: the values of the free variables its body
    /// actually uses, copied in at closure creation in the slot order
    /// `Lambda::captures` fixed at resolve. It **terminates**
    /// the de Bruijn walk: an index that runs off the consed cells selects
    /// `vals[remaining]` (see `lookup`), so a reference into an enclosing scope
    /// costs a walk over the activation's own bindings plus one array index —
    /// never a walk over the whole enclosing program — and a closure retains only
    /// what it uses.
    ///
    /// `home` carries the environment's terminal (`None`, or the
    /// [`Module`](EnvNode::Module) node of
    /// the module item this closure came from) on past the frame, so a `ModItem`
    /// inside the body still finds its module — and finds the *same* node, so
    /// materializing an item allocates no environment. Nothing addresses `home` by
    /// index: the frame is the last indexable node.
    ///
    /// The values live inline behind the environment's own `Rc`, so a frame is one
    /// allocation and is shared by refcount exactly as the captured cons tail used
    /// to be.
    Frame {
        vals: Box<[Value]>,
        home: Env,
    },
}

/// A value unwinding through the single error channel (see the *errors* section
/// of `docs/elly-spec.md`). Evaluation returns `Result<Value, Raised>`; a raise
/// unwinds the `?` chain up to the nearest boundary. Two **kinds** unwind
/// together, differing only in what catches them:
///
/// - `Error(v)` — a genuine failure: a host abort (`raise_sym`) or an explicit
///   `__Err.raise v`. Propagates past `__match`.
/// - `NoMatch(v)` — a **pattern refutation** produced by `match_pattern` on a
///   structural miss. `v` is the *original* descriptive error the refutation
///   stands for (e.g. `.list_size_mismatch`, or `.no_match` for a bare `=`/`as`
///   miss). Only `__match` singles it out — catching it, discarding `v`, and
///   falling through to its fallback. Every **other** boundary (`__Err.catch`,
///   the top level) treats it exactly as `Error(v)`, so an *uncaught* refutation
///   surfaces as its original error `v` rather than an opaque signal.
///
/// The kinds are distinguished by construction, not by an inspectable tag: user
/// code only ever raises `Error` (via `__Err.raise`), so it cannot forge a
/// `NoMatch` and fool `__match` (unlike a bare `.no_match` symbol would).
#[derive(Debug, Clone)]
pub enum Raised {
    /// A genuine error, propagated by `__match`.
    Error(Value),
    /// A pattern refutation carrying the original error it decays to when uncaught.
    NoMatch(Value),
}

impl Raised {
    /// The carried payload, regardless of kind (an uncaught refutation *is* its
    /// original error).
    pub fn value(&self) -> &Value {
        match self {
            Raised::Error(v) | Raised::NoMatch(v) => v,
        }
    }

    /// Consume into the carried payload.
    pub fn into_value(self) -> Value {
        match self {
            Raised::Error(v) | Raised::NoMatch(v) => v,
        }
    }
}

/// Raise one of the host-failure symbol tags (stored without its leading dot) as
/// a genuine `Error`. The tag is a `'static` literal, so it becomes a
/// zero-cost borrowed [`Text`] via `from_static`.
fn raise_sym(tag: &'static str) -> Raised {
    Raised::Error(Value::Symbol(Text::from_static(tag)))
}

/// The unit value: the empty list `[]`. Fed by the nullary marker `()` and used
/// to force the `__Int.*` / `__Err.catch` branch thunks.
fn unit() -> Value {
    Value::List(Vector::new())
}

/// Evaluate an expression in the empty environment.
///
/// The [`Ctx`] threaded through evaluation carries the per-runtime **unique-id
/// source**: each `&`-abstraction stamps its closure with the next id, giving
/// callables an identity for equality/order.
pub fn eval(expr: &Expr) -> Result<Value, Raised> {
    let ctx = Ctx::new();
    eval_env(expr, &None, &ctx)
}

/// Apply a value to a single argument — 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. Since values are `'static`-owned, `f` and `arg` may come
/// from different programs. A fresh [`Ctx`] is used, mirroring [`eval`], so any
/// closures minted while running the application are stamped from its id source.
/// Use [`apply_with`] to apply under a context whose ids continue an earlier
/// one's.
pub fn apply(f: &Value, arg: Value) -> Result<Value, Raised> {
    apply_with(f, arg, &Ctx::new())
}

/// Apply a value to a single argument under a caller-supplied [`Ctx`]. Identical
/// to [`apply`] except that the context comes from the caller, so the identities
/// minted by the call continue that context's id source instead of restarting at
/// zero. A host that hands callables out and takes them back needs it (e.g.
/// `elly.Fun.__call__` on a closure materialized out of a module), or an item and
/// an unrelated closure could be handed the same id.
pub fn apply_with(f: &Value, arg: Value, ctx: &Ctx) -> Result<Value, Raised> {
    apply1(f.clone(), arg, ctx)
}

/// Evaluate an expression in a given `env` with a `Ctx` (carrying the unique-id
/// source). The public entry behind a host's "eval with environment" surface
/// (e.g. `elly.Env.eval`); [`eval`] is a thin wrapper around it.
pub fn eval_env(expr: &Expr, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
    match expr {
        // A resolved reference: walk `index` cons links and clone the cell's
        // value. The resolver (`resolve.rs`) guarantees the index is in range, so
        // this neither compares names nor walks past the target.
        Expr::Local { index, .. } => Ok(lookup(env, *index)),
        // Names are rewritten to `Expr::Local` by the resolver before eval, and
        // `elly::parse` always resolves, so a bare `Name` never reaches here.
        Expr::Name(n) => unreachable!("unresolved name {:?} reached eval", n),
        // A module sibling reference; outlined whole (see [`mod_item`]).
        Expr::ModItem { index, depth, .. } => mod_item(env, *index, *depth, ctx),
        // A home-module leaf; outlined for the same reason (see [`home_leaf`]).
        Expr::Home { leaf, depth } => home_leaf(env, *leaf, *depth),
        // A recursive binding group; outlined (see [`recur`]).
        Expr::Recur(r) => recur(r, env, ctx),
        // A parse-resolved builtin. A 0-arity builtin (`__Map.nil`) is a value: it
        // fires immediately with no arguments rather than sitting as an unsaturated
        // `Builtin`; any other arity yields a `Builtin` awaiting its arguments.
        Expr::Builtin(op) => {
            if op.arity() == 0 {
                invoke(*op, &[], ctx)
            } else {
                // `Vec::new()`, not `Vec::with_capacity(op.arity())`: reserving here
                // is a measured pessimization. This value is created empty and then
                // *cloned* by each curried application, and `Vec::clone` allocates
                // `capacity == len` — so the reserved buffer is dropped before the
                // first `push` ever happens, and the push re-allocates. Reserving
                // costs one extra malloc/free per builtin reference: +25% to +105%
                // allocations and +5% to +23% time across the eval suite.
                Ok(Value::Builtin {
                    op: *op,
                    args: Vec::new(),
                })
            }
        }
        Expr::Int(n) => Ok(Value::from_bigint_ref(n)),
        Expr::Symbol(s) => Ok(Value::Symbol(s.clone())),
        // Self-evaluating: clone the shared, already-decoded handle.
        Expr::Str(s) => Ok(Value::Str(s.clone())),
        Expr::List(elems) => {
            let mut vs = Vector::new();
            for e in elems {
                vs.push_back_mut(eval_env(e, env, ctx)?);
            }
            Ok(Value::List(vs))
        }
        // A map literal: evaluate each key and value (source order), inserting
        // into a fresh map. A later entry with an equal key overwrites.
        Expr::Map(entries) => {
            let mut m = HashTrieMap::new();
            for (k, v) in entries {
                let kv = eval_env(k, env, ctx)?;
                let vv = eval_env(v, env, ctx)?;
                m.insert_mut(kv, vv);
            }
            Ok(Value::Map(m))
        }
        // Build a closure over the shared `code`, capturing **only** the free
        // variables the body uses: the resolved capture plan says where to read each
        // one from in *this* environment and which frame slot it fills (see
        // `capture_env` and `EnvNode::Frame`). A closed abstraction captures nothing
        // and allocates no frame — it runs directly on the environment's terminal,
        // which is also how a module item's closure keeps its module alive. An
        // abstraction the resolver marked `Chain` — one the call it sits in consumes,
        // so it cannot outlive its environment — shares that environment outright.
        Expr::Abs(code) => {
            let env = match &code.captures {
                Captures::Chain => env.clone(),
                Captures::Frame(plan) => capture_env(env, plan),
                Captures::Unresolved => unreachable!("unresolved abstraction reached eval"),
            };
            Ok(Value::Closure {
                id: ctx.next_id(),
                code: Rc::clone(code),
                applied: 0,
                env,
            })
        }
        // Call-by-value over a flattened spine: evaluate the callee, then every
        // argument strictly left-to-right, then apply the whole call at once. The
        // argument values are gathered on the **stack** for the common small
        // arities (every builtin is ≤ 4, and Z-recursion is 1-argument-dominant),
        // so a call allocates no heap argument buffer; only a spine of five or
        // more arguments falls back to a `Vec`.
        Expr::App(items) => {
            let callee = eval_env(&items[0], env, ctx)?;
            let arg_exprs = &items[1..];
            match arg_exprs {
                [a] => apply1(callee, eval_env(a, env, ctx)?, ctx),
                [a, b] => {
                    let va = eval_env(a, env, ctx)?;
                    let vb = eval_env(b, env, ctx)?;
                    apply_n(callee, &[va, vb], ctx)
                }
                [a, b, c] => {
                    let va = eval_env(a, env, ctx)?;
                    let vb = eval_env(b, env, ctx)?;
                    let vc = eval_env(c, env, ctx)?;
                    apply_n(callee, &[va, vb, vc], ctx)
                }
                [a, b, c, d] => {
                    let va = eval_env(a, env, ctx)?;
                    let vb = eval_env(b, env, ctx)?;
                    let vc = eval_env(c, env, ctx)?;
                    let vd = eval_env(d, env, ctx)?;
                    apply_n(callee, &[va, vb, vc, vd], ctx)
                }
                _ => {
                    let mut argv: Vec<Value> = Vec::with_capacity(arg_exprs.len());
                    for a in arg_exprs {
                        argv.push(eval_env(a, env, ctx)?);
                    }
                    apply_n(callee, &argv, ctx)
                }
            }
        }
    }
}

/// Apply a value to a single argument — the tight one-argument application path,
/// used by the single-argument call spine (the dominant shape), the fold builtins
/// (`__Int.for`, `__Map.*`), `__eq`, `__Err.catch`, and `__match` clauses. One
/// argument can never *over-*apply (a saturating call leaves nothing left over),
/// so this needs no loop or slice bookkeeping: it either binds the one remaining
/// parameter and runs the body, produces a partial closure (still more parameters
/// to come), gathers one argument onto a builtin, or projects a list.
fn apply1(fv: Value, av: Value, ctx: &Ctx) -> Result<Value, Raised> {
    match fv {
        Value::Closure {
            code, applied, env, ..
        } => {
            let start = applied as usize;
            // Match the one argument against the next parameter, consing its
            // bindings onto the closure's (captured or partially-applied) env.
            let call_env = match_pattern(&code.head[start], &av, env, ctx)?;
            if start + 1 < code.head.len() {
                // Still parameters to come: a fresh-id partial closure carrying
                // the consed prefix as its env (shared with siblings by refcount).
                return Ok(Value::Closure {
                    id: ctx.next_id(),
                    code,
                    applied: applied + 1,
                    env: call_env,
                });
            }
            eval_env(&code.body, &call_env, ctx)
        }
        Value::Builtin {
            op,
            args: mut gathered,
        } => {
            // A fresh unary builtin saturates from the stack — no `Vec`.
            if gathered.is_empty() && op.arity() == 1 {
                return invoke(op, &[av], ctx);
            }
            gathered.push(av);
            if gathered.len() == op.arity() {
                invoke(op, &gathered, ctx)
            } else {
                Ok(Value::Builtin { op, args: gathered })
            }
        }
        // A host callback gathers exactly as a builtin does; only the dispatch at
        // the end differs (an `Rc`'d closure rather than the `invoke` match).
        Value::HostFn {
            code,
            args: gathered,
        } => {
            if gathered.is_empty() && code.arity == 1 {
                return (code.f)(&[av], ctx);
            }
            let gathered = extended(&gathered, &[av]);
            if gathered.len() == code.arity {
                (code.f)(&gathered, ctx)
            } else {
                Ok(Value::HostFn {
                    code,
                    args: gathered,
                })
            }
        }
        // A module applied to a symbol materializes that item; a non-symbol
        // argument is not applicable (v0 has no `x arg` module call form).
        Value::Module(home) => match av {
            Value::Symbol(s) => materialize(&home, &s, ctx),
            _ => Err(raise_sym("not_applicable")),
        },
        // Everything else applied to a symbol **dispatches** through its
        // prototype (see [`receiver`]) — an object through its own, every other
        // kind through the builtin module for it.
        fv => receiver(fv, &av, &[], ctx),
    }
}

/// Apply a value to a whole call's arguments at once — the single runtime
/// application entry. Covers closures (a multi-parameter match via the `applied`
/// counter), builtins (gathered until saturation), and the list-projection
/// fallback; **over-application loops onto the result**, so a flat spine behaves
/// exactly like the curried applications it stands for.
///
/// Evaluation is strict and fully specified: the caller has already evaluated
/// every argument left-to-right (see [`eval_env`]'s `App` arm), and this then
/// *matches* the patterns left-to-right. An argument-evaluation error therefore
/// surfaces before any pattern refutation — the intentional, documented order
/// (see `docs/done/2026-08-02_perf-less-currying.md` §3).
fn apply_n(mut fv: Value, mut args: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    while !args.is_empty() {
        match fv {
            // Applying an abstraction *matches* the next arguments against its
            // remaining patterns (`code.head[applied..]`), left-to-right. Binding
            // the whole call at once: if the arguments run out first it is a
            // partial (a fresh-id closure with the bound prefix in `env`); once the
            // head saturates, the body runs in the extended environment and any
            // leftover arguments loop onto its result. A pattern miss raises
            // `NoMatch` (caught by `__match`, else decaying to the refutation tag).
            Value::Closure {
                code, applied, env, ..
            } => {
                let start = applied as usize;
                let remaining = code.head.len() - start;
                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;
                for (pat, arg) in code.head[start..start + take].iter().zip(&args[..take]) {
                    call_env = match_pattern(pat, arg, call_env, ctx)?;
                }
                if take < remaining {
                    // Partial: no body runs yet; mint a fresh identity.
                    return Ok(Value::Closure {
                        id: ctx.next_id(),
                        code,
                        applied: applied + take as u8,
                        env: call_env,
                    });
                }
                fv = eval_env(&code.body, &call_env, ctx)?;
                args = &args[take..];
            }
            // Gather arguments toward the op's arity; invoke once saturated and
            // loop any leftover onto the result. When the incoming spine already
            // supplies the whole arity (the common case — a builtin freshly
            // referenced then applied), invoke **straight from the stack slice**,
            // building no `Value::Builtin { args: Vec }` at all.
            Value::Builtin {
                op,
                args: mut gathered,
            } => {
                let arity = op.arity();
                if gathered.is_empty() && args.len() >= arity {
                    fv = invoke(op, &args[..arity], 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 = invoke(op, &gathered, ctx)?;
                    args = &args[take..];
                }
            }
            // Same gather-and-fire loop as the builtin arm above, dispatching
            // through the callback the value carries.
            Value::HostFn {
                code,
                args: gathered,
            } => {
                let arity = code.arity;
                if gathered.is_empty() && args.len() >= arity {
                    fv = (code.f)(&args[..arity], 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 = (code.f)(&gathered, ctx)?;
                    args = &args[take..];
                }
            }
            // A module applied to a symbol materializes that item; any
            // leftover arguments loop onto the materialized value (e.g.
            // `M.factorial 5`).
            Value::Module(home) => {
                match &args[0] {
                    Value::Symbol(s) => fv = materialize(&home, s, ctx)?,
                    _ => return Err(raise_sym("not_applicable")),
                }
                args = &args[1..];
            }
            // Dispatch, taking the **whole** rest of the spine with it: the
            // receiver and the method's own arguments go to the method in one
            // call, so `x .m a b` binds them in one pass and never builds the
            // partial `x.m` would be (see [`receiver`]).
            fv => return receiver(fv, &args[0], &args[1..], ctx),
        }
    }
    Ok(fv)
}

/// `prefix` followed by `more`, in one allocation — how a [`Value::HostFn`]
/// gathers the next curried argument onto the ones it already holds. Sized up
/// front, so a partial application costs exactly one `malloc` and no realloc.
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()
}

/// Run a fully-applied builtin over its arguments. Borrows the argument slice
/// (every arm reads by reference or clones what it keeps), so a spine that
/// saturates a builtin exactly can invoke straight from the caller's stack
/// arguments — no `Value::Builtin { args: Vec }` need be built or torn down.
fn invoke(op: Builtin, args: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    match op {
        Builtin::IntAdd => int_arith(&args[0], &args[1], i64::checked_add, |a, b| a + b),
        Builtin::IntSub => int_arith(&args[0], &args[1], i64::checked_sub, |a, b| a - b),
        Builtin::IntMul => int_arith(&args[0], &args[1], i64::checked_mul, |a, b| a * b),
        // `x ^ y`, `y >= 0`. A negative exponent has no integer value.
        Builtin::IntPow => {
            let e =
                u32::try_from(&*as_big(&args[1])?).map_err(|_| raise_sym("negative_exponent"))?;
            // Small-base fast path: `i64::checked_pow`, promoting on overflow.
            if let Value::I64(x) = &args[0] {
                if let Some(z) = x.checked_pow(e) {
                    return Ok(Value::I64(z));
                }
            }
            Ok(Value::from_bigint(as_big(&args[0])?.pow(e)))
        }
        Builtin::IntDivrem => {
            // Fast path: both operands fit `i64`. `i64::MIN / -1` overflows, so on a
            // `None` from either `checked_*` we fall through to the `BigInt` path.
            if let (Value::I64(x), Value::I64(y)) = (&args[0], &args[1]) {
                if *y == 0 {
                    return Err(raise_sym("div_by_zero"));
                }
                if let (Some(q), Some(r)) = (x.checked_div_euclid(*y), x.checked_rem_euclid(*y)) {
                    let mut t = Vector::new();
                    t.push_back_mut(Value::I64(q));
                    t.push_back_mut(Value::I64(r));
                    return Ok(Value::List(t));
                }
            }
            let (q, r) = div_rem_euclid(&*as_big(&args[0])?, &*as_big(&args[1])?)?;
            let mut t = Vector::new();
            t.push_back_mut(Value::from_bigint(q));
            t.push_back_mut(Value::from_bigint(r));
            Ok(Value::List(t))
        }
        // ascending fold over `[from, to)`, index first: `onEach i acc`.
        // `from >= to` runs zero iterations and returns the initial state.
        Builtin::IntFor => {
            let f = &args[3];
            let mut acc = args[2].clone();
            // Fast path: both bounds fit `i64` — an inline counter, no per-iteration
            // `BigInt` allocation. (`i` only ever reaches `to <= i64::MAX`, so the
            // `i += 1` after the last iteration cannot overflow.)
            if let (Value::I64(from), Value::I64(to)) = (&args[0], &args[1]) {
                let (from, to) = (*from, *to);
                let mut i = from;
                while i < to {
                    let with_i = apply1(f.clone(), Value::I64(i), ctx)?;
                    acc = apply1(with_i, acc, ctx)?;
                    i += 1;
                }
                return Ok(acc);
            }
            // General path: a bound is a wide `BigInt` (an astronomically long loop).
            let to = as_big(&args[1])?.into_owned();
            let mut i = as_big(&args[0])?.into_owned();
            while i < to {
                let with_i = apply1(f.clone(), Value::from_bigint(i.clone()), ctx)?;
                acc = apply1(with_i, acc, ctx)?;
                i += 1;
            }
            Ok(acc)
        }
        // `onEqual () if a == b else onDiff ()` — structural for data, by identity
        // for callables (see `impl PartialEq for Value`). Nullary-thunk branches, so only
        // the taken side runs; the operands may be any values and never raise.
        Builtin::Eq => {
            let taken = if args[0] == args[1] {
                &args[2]
            } else {
                &args[3]
            };
            apply1(taken.clone(), args[0].clone(), ctx)
        }
        // Raise the (already-evaluated) argument as a genuine error, unwinding to
        // the nearest catch.
        Builtin::ErrRaise => Err(Raised::Error(args[0].clone())),
        // Force the wrapped thunk; on *any* raise, hand the payload to the handler
        // — `__Err.catch` is the universal boundary, so it catches a refutation
        // too, delivering the original error it decayed to. A raise from the
        // handler itself propagates (not re-caught here).
        Builtin::ErrCatch => match apply1(args[1].clone(), unit(), ctx) {
            Ok(v) => Ok(v),
            Err(r) => apply1(args[0].clone(), r.into_value(), ctx),
        },
        // The refutable form: `__match clauses val`. Try each clause (a matcher,
        // typically `&(<pat>) <body>`) against `val` in order; the first whose
        // pattern *matches* returns its body's value, and no later clause runs. A
        // clause that *refutes* (a `NoMatch`) is skipped and the next is tried;
        // every other raise — a real `Error` from the body or a `= <expr>`
        // sub-expression — propagates. Falling off the end (an empty list, or all
        // clauses refuting) itself refutes `.no_match`, so an uncaught `__match`
        // surfaces `.no_match` while a nested one can still be caught by an outer
        // matcher. `__match` is the *only* boundary
        // that singles out `NoMatch` (which user code cannot forge), making "only
        // pattern mismatches fall through" exact. See `docs/elly-spec.md` § patterns.
        Builtin::Match => {
            for clause in list(&args[0])?.iter() {
                match apply1(clause.clone(), args[1].clone(), ctx) {
                    Ok(v) => return Ok(v),
                    Err(Raised::NoMatch(_)) => continue,
                    Err(e) => return Err(e),
                }
            }
            Err(Raised::NoMatch(Value::Symbol(Text::from_static(
                "no_match",
            ))))
        }
        // Element count of a list.
        Builtin::ListSize => Ok(Value::I64(list(&args[0])?.len() as i64)),
        // Element at a 0-based integer index; out of range (or negative) raises
        // `.projection_out_of_range`, generalizing `.N` projection to a computed
        // index.
        Builtin::ListGet => {
            let t = list(&args[0])?;
            index_of(&args[1])?
                .and_then(|idx| t.get(idx))
                .cloned()
                .ok_or_else(|| raise_sym("projection_out_of_range"))
        }
        // Concatenate two lists: `[a…] ++ [b…]`.
        Builtin::ListAppend => {
            let mut r = list(&args[0])?.clone();
            for e in list(&args[1])?.iter() {
                r.push_back_mut(e.clone());
            }
            Ok(Value::List(r))
        }
        // Replace the element at index `i` with `v`, returning a new list;
        // out of range (or a negative index) raises `.projection_out_of_range`.
        Builtin::ListWith => {
            let t = list(&args[0])?;
            let v = args[2].clone();
            index_of(&args[1])?
                .and_then(|idx| t.set(idx, v))
                .map(Value::List)
                .ok_or_else(|| raise_sym("projection_out_of_range"))
        }
        // Split a list at position `n` into `[left, right]` (left holds the
        // first `n` elements). `n` must be in `[0, size]`, else
        // `.projection_out_of_range`.
        Builtin::ListSplit => {
            let t = list(&args[1])?;
            let n = index_of(&args[0])?
                .filter(|&n| n <= t.len())
                .ok_or_else(|| raise_sym("projection_out_of_range"))?;
            let mut left = Vector::new();
            let mut right = Vector::new();
            for (idx, e) in t.iter().enumerate() {
                if idx < n {
                    left.push_back_mut(e.clone());
                } else {
                    right.push_back_mut(e.clone());
                }
            }
            let mut pair = Vector::new();
            pair.push_back_mut(Value::List(left));
            pair.push_back_mut(Value::List(right));
            Ok(Value::List(pair))
        }
        // The empty map (a 0-arity value; `args` is empty).
        Builtin::MapNil => Ok(Value::Map(HashTrieMap::new())),
        // `m` with `k` bound to `v` (overwriting any prior binding). Any value is
        // a key — no key restriction, no bad-key error.
        Builtin::MapWith => {
            let m = map(&args[0])?;
            Ok(Value::Map(m.insert(args[1].clone(), args[2].clone())))
        }
        // Value at `k`; a missing key raises `.missing_key` (a catchable tag).
        Builtin::MapGet => {
            let m = map(&args[0])?;
            m.get(&args[1])
                .cloned()
                .ok_or_else(|| raise_sym("missing_key"))
        }
        // Parallel projection: a list of the values for a list of keys; any
        // missing key raises `.missing_key`.
        Builtin::MapGets => {
            let m = map(&args[0])?;
            let mut out = Vector::new();
            for k in list(&args[1])?.iter() {
                let v = m.get(k).cloned().ok_or_else(|| raise_sym("missing_key"))?;
                out.push_back_mut(v);
            }
            Ok(Value::List(out))
        }
        // Fold over the map (unspecified order): `onEach key value state -> state`.
        Builtin::MapFor => {
            let m = map(&args[0])?;
            let f = &args[2];
            let mut acc = args[1].clone();
            for (k, v) in m.iter() {
                let with_k = apply1(f.clone(), k.clone(), ctx)?;
                let with_v = apply1(with_k, v.clone(), ctx)?;
                acc = apply1(with_v, acc, ctx)?;
            }
            Ok(acc)
        }
        // Generic merge over the union of keys. For each key the callback gets the
        // key and each side's value as an option (`[]` none / `[v]` some) and
        // returns an option — `[]` drops the key, `[v]` sets it.
        Builtin::MapMerge => {
            let m1 = map(&args[0])?;
            let m2 = map(&args[1])?;
            let f = &args[2];
            let mut result = HashTrieMap::new();
            // Every key in the union, visited once (order unspecified): all of
            // `m1`'s keys, then `m2`'s keys that `m1` lacks.
            let union = m1.keys().chain(m2.keys().filter(|k| !m1.contains_key(*k)));
            for k in union {
                let k = k.clone();
                let with_k = apply1(f.clone(), k.clone(), ctx)?;
                let with_l = apply1(with_k, option(m1.get(&k)), ctx)?;
                let out = apply1(with_l, option(m2.get(&k)), ctx)?;
                if let Some(v) = un_option(&out)? {
                    result.insert_mut(k, v);
                }
            }
            Ok(Value::Map(result))
        }
        // Union with `b` winning on a key conflict (a `__Map.merge` special case).
        Builtin::MapCat => {
            let mut r = map(&args[0])?.clone();
            for (k, v) in map(&args[1])?.iter() {
                r.insert_mut(k.clone(), v.clone());
            }
            Ok(Value::Map(r))
        }
        // `m` with `k` removed (a no-op if absent); the persistent-update
        // counterpart of `__Map.with`.
        Builtin::MapWithout => {
            let m = map(&args[0])?;
            Ok(Value::Map(m.remove(&args[1])))
        }
        // Element count of a map, symmetric with `__List.size`.
        Builtin::MapSize => Ok(Value::I64(map(&args[0])?.size() as i64)),
        // Canonical signed decimal of an integer (`15` → `"15"`); the Int half of
        // the scalar→text bridge. A non-int raises `.not_an_int`.
        Builtin::IntStr => {
            let s = match &args[0] {
                Value::I64(x) => x.to_string(),
                Value::BigInt(n) => n.to_string(),
                _ => return Err(raise_sym("not_an_int")),
            };
            Ok(Value::Str(Text::from(s.as_str())))
        }
        // Build a string from a list of **codepoints** (Unicode scalar values). A
        // non-int element raises `.not_an_int`; a value outside `0..=0x10FFFF` or in
        // the surrogate range raises `.bad_codepoint`.
        Builtin::StrPack => {
            let t = list(&args[0])?;
            let mut s = String::new();
            for elem in t.iter() {
                let code = match elem {
                    Value::I64(x) => u32::try_from(*x).ok(),
                    Value::BigInt(n) => u32::try_from(&**n).ok(),
                    _ => return Err(raise_sym("not_an_int")),
                };
                let cp = code
                    .and_then(char::from_u32)
                    .ok_or_else(|| raise_sym("bad_codepoint"))?;
                s.push(cp);
            }
            Ok(Value::Str(Text::from(s.as_str())))
        }
        // Explode a string into a list of its codepoints — the inverse of
        // `__Str.pack`. A non-string raises `.not_a_str`.
        Builtin::StrUnpack => {
            let mut t = Vector::new();
            for ch in str_ref(&args[0])?.chars() {
                t.push_back_mut(Value::I64(ch as i64));
            }
            Ok(Value::List(t))
        }
        // Intern a string as a symbol (`"foo"` → `.foo`); the string→symbol half of
        // the text bridge. The text must be a single Muon `<sym>` segment — the
        // only form that re-parses from `.<text>` — else `.bad_symbol`. A
        // non-string raises `.not_a_str`.
        Builtin::SymFrom => {
            let s = str_ref(&args[0])?;
            if is_sym_segment(s) {
                Ok(Value::Symbol(s.clone()))
            } else {
                Err(raise_sym("bad_symbol"))
            }
        }
        // A symbol's text without the dot (`.foo` → `"foo"`); the Sym half of the
        // scalar→text bridge and the inverse of `__Sym.from`. A non-symbol raises
        // `.not_a_sym`.
        Builtin::SymStr => match &args[0] {
            Value::Symbol(s) => Ok(Value::Str(s.clone())),
            _ => Err(raise_sym("not_a_sym")),
        },
        // The canonical name a module's code came from (see [`ModuleData::name`]).
        Builtin::ModName => match &args[0] {
            Value::Module(node) => match node.as_ref() {
                EnvNode::Module { data, .. } => Ok(match data.name() {
                    Some(name) => Value::Str(name.clone()),
                    // The host never named this code, so there is no name to
                    // report and the unit says so.
                    None => unit(),
                }),
                _ => Err(raise_sym("not_a_module")),
            },
            _ => Err(raise_sym("not_a_module")),
        },
        // The prototype of any value at all (see [`proto_of`]).
        Builtin::Proto => Ok(proto_of(&args[0], ctx)),
        // `__new proto data` — an object of the prototype the leaf supplied. The
        // prototype slot takes a module and nothing else, which is what keeps a
        // prototype a const-time entity with a known item table.
        Builtin::ObjNew => {
            let Value::Module(proto) = &args[0] else {
                return Err(raise_sym("not_a_module"));
            };
            Ok(Value::Object(Rc::new(ObjectData {
                proto: Rc::clone(proto),
                data: args[1].clone(),
            })))
        }
        // `__value proto obj` — the payload, provided the object is of that
        // prototype. A non-object is `.not_an_object`; an object of another
        // prototype is `.foreign_object`, so a method cannot unwrap a value that
        // merely passed through it.
        Builtin::ObjValue => {
            let Value::Module(proto) = &args[0] else {
                return Err(raise_sym("not_a_module"));
            };
            let Value::Object(obj) = &args[1] else {
                return Err(raise_sym("not_an_object"));
            };
            if !Rc::ptr_eq(&obj.proto, proto) {
                return Err(raise_sym("foreign_object"));
            }
            Ok(obj.data.clone())
        }
        // A builtin module names itself: 0-arity, so a reference *is* the module
        // value (see [`Ctx::builtin_module`]).
        Builtin::Int
        | Builtin::Str
        | Builtin::Sym
        | Builtin::List
        | Builtin::Map
        | Builtin::Err
        | Builtin::Mod
        | Builtin::Fun => Ok(ctx.builtin_module(op)),
    }
}

/// The **prototype** of any value: an object's own, and the builtin module for
/// every other kind — which is what makes [`__proto`](Builtin::Proto) total and
/// gives every value a nominal type.
///
/// An **iota**'s prototype is the module that declared it, the same answer an
/// object of that module gives: an iota is an identity a module minted, so `x as
/// Bool` holds for `Bool`'s iotas as it does for its objects. That is what lets a
/// type range over both.
///
/// The three **callable** kinds — a closure, a builtin, a host function — answer
/// with the one `__Fun`. They are one nominal type, the way two closures of
/// different arity are.
fn proto_of(v: &Value, ctx: &Ctx) -> Value {
    match v {
        Value::Object(obj) => obj.proto(),
        Value::Iota { home, .. } => Value::Module(Rc::clone(home)),
        Value::I64(_) | Value::BigInt(_) => ctx.builtin_module(Builtin::Int),
        Value::Symbol(_) => ctx.builtin_module(Builtin::Sym),
        Value::Str(_) => ctx.builtin_module(Builtin::Str),
        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),
    }
}

/// Borrow either integer variant as a `BigInt`, or raise `.not_an_int`. A
/// [`Value::BigInt`] is borrowed *without* cloning; only the [`Value::I64`] case
/// materializes (an unavoidable small allocation, and only on the wide/mixed slow
/// path — the `i64` fast paths in `invoke` avoid it entirely).
fn as_big(v: &Value) -> Result<Cow<'_, BigInt>, Raised> {
    match v {
        Value::I64(x) => Ok(Cow::Owned(BigInt::from(*x))),
        Value::BigInt(n) => Ok(Cow::Borrowed(n)),
        _ => Err(raise_sym("not_an_int")),
    }
}

/// Shared shape for the binary `+ - *` builtins: an `i64` fast path (the `checked`
/// op, promoting to `BigInt` on overflow) with a `BigInt` fallback for wide
/// operands. The fallback borrows its operands (reference arithmetic, so a wide
/// `a + b` allocates only the result — matching the pre-split cost) and normalizes
/// through [`Value::from_bigint`], preserving the canonical `I64`-if-it-fits invariant.
fn int_arith(
    a: &Value,
    b: &Value,
    small: impl Fn(i64, i64) -> Option<i64>,
    big: impl Fn(&BigInt, &BigInt) -> BigInt,
) -> Result<Value, Raised> {
    if let (Value::I64(x), Value::I64(y)) = (a, b) {
        if let Some(z) = small(*x, *y) {
            return Ok(Value::I64(z));
        }
    }
    Ok(Value::from_bigint(big(&*as_big(a)?, &*as_big(b)?)))
}

/// Borrow a value as a list, or raise `.not_a_list` — the strict-argument
/// check shared by the `__List.*` builtins.
fn list(v: &Value) -> Result<&Vector<Value>, Raised> {
    match v {
        Value::List(t) => Ok(t),
        _ => Err(raise_sym("not_a_list")),
    }
}

/// Borrow a value as a string, or raise `.not_a_str` — the strict-argument check
/// shared by the `__Str.*` / `__Sym.*` builtins.
fn str_ref(v: &Value) -> Result<&Text, Raised> {
    match v {
        Value::Str(s) => Ok(s),
        _ => Err(raise_sym("not_a_str")),
    }
}

/// Is `s` a single Muon `<sym>` — a non-empty run of symchars (`[0-9A-Za-z_+-]`)?
/// This is exactly the text that `.<s>` lexes back as one symbol, so it is the
/// admissible domain of `__Sym.from`. Anything with a space, a `.`, a quote, or
/// any other non-symchar (or the empty string) is rejected.
fn is_sym_segment(s: &str) -> bool {
    !s.is_empty()
        && s.bytes()
            .all(|c| c.is_ascii_alphanumeric() || matches!(c, b'_' | b'-' | b'+'))
}

/// Borrow a value as a map, or raise `.not_a_map` — the strict-argument check
/// shared by the `__Map.*` builtins.
fn map(v: &Value) -> Result<&HashTrieMap<Value, Value>, Raised> {
    match v {
        Value::Map(m) => Ok(m),
        _ => Err(raise_sym("not_a_map")),
    }
}

/// Encode an optional map value as `__Map.merge`'s option: `[]` (none) or `[v]`
/// (some). Fed to the merge callback for each side of a key.
fn option(v: Option<&Value>) -> Value {
    match v {
        None => unit(),
        Some(v) => {
            let mut t = Vector::new();
            t.push_back_mut(v.clone());
            Value::List(t)
        }
    }
}

/// Decode a `__Map.merge` callback result as an option: `[]` → `None` (drop the
/// key), `[v]` → `Some(v)` (set it). A non-list raises `.not_a_list`; any other
/// arity raises `.list_size_mismatch`.
fn un_option(v: &Value) -> Result<Option<Value>, Raised> {
    let t = list(v)?;
    match t.len() {
        0 => Ok(None),
        1 => Ok(Some(t.get(0).unwrap().clone())),
        _ => Err(raise_sym("list_size_mismatch")),
    }
}

/// Read an integer value as a 0-based index. A non-integer raises `.not_an_int`;
/// a negative or out-of-`usize` value yields `None` (the caller decides the
/// out-of-range error). Shared by `__List.get` / `__List.with` / `__List.split`.
fn index_of(v: &Value) -> Result<Option<usize>, Raised> {
    match v {
        // A negative `i64` fails `usize::try_from` → `None` (out of range).
        Value::I64(x) => Ok(usize::try_from(*x).ok()),
        Value::BigInt(n) => Ok(u64::try_from(&**n)
            .ok()
            .and_then(|u| usize::try_from(u).ok())),
        _ => Err(raise_sym("not_an_int")),
    }
}

/// Euclidean quotient/remainder: `a = b*q + r` with `0 <= r < |b|`. `b == 0`
/// raises `.div_by_zero`.
fn div_rem_euclid(a: &BigInt, b: &BigInt) -> Result<(BigInt, BigInt), Raised> {
    if b.sign() == Sign::NoSign {
        return Err(raise_sym("div_by_zero"));
    }
    let q = a / b; // truncated toward zero
    let r = a - &q * b;
    // Truncated `r` carries the sign of `a`; nudge it into `[0, |b|)`.
    Ok(if r.sign() == Sign::Minus {
        if b.sign() == Sign::Plus {
            (q - 1, r + b)
        } else {
            (q + 1, r - b)
        }
    } else {
        (q, r)
    })
}

/// Resolve a de Bruijn `index` to a clone of its value: walk cons links along
/// `next`, counting the index down; a walk that reaches the closure's [`Frame`]
/// with `rest` left selects `vals[rest]` — the enclosing scope, flattened to one
/// array index. The resolver guarantees the index lands on a live cell or a live
/// frame slot, so the other arms are unreachable in a resolved program.
///
/// A [`Module`](EnvNode::Module) terminal is passed **through, uncounted**, into
/// the module's frame: the node binds no name, so a module body's reference to an
/// import or a prelude value is an ordinary `Local` whose index simply runs off
/// the lexical cells and continues into the frame.
///
/// [`Frame`]: EnvNode::Frame
fn lookup(env: &Env, index: u32) -> Value {
    let mut cur = env;
    let mut rest = index as usize;
    loop {
        match cur.as_deref() {
            Some(EnvNode::Cons { val, next }) => {
                if rest == 0 {
                    return val.clone();
                }
                rest -= 1;
                cur = next;
            }
            Some(EnvNode::Frame { vals, .. }) => match vals.get(rest) {
                Some(val) => return val.clone(),
                None => unreachable!("resolved index walked past the captured frame"),
            },
            None => unreachable!("resolved index walked past the environment"),
            Some(EnvNode::Module { frame, .. }) => cur = frame,
        }
    }
}

/// The environment a capturing closure runs on, built from its resolved `plan`.
/// Outlined from `eval_env`, which is instruction-cache resident: the deep-recursion
/// benches (`rec_deep`, `mod_rec_deep`) pay for growing it.
#[inline(never)]
fn capture_env(env: &Env, plan: &[Capture]) -> Env {
    match plan {
        [] => env_home(env),
        // 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(env, c.outer);
            Some(Rc::new(EnvNode::Cons { val, next }))
        }
        _ => {
            let (vals, home) = build_frame_and_home(env, plan);
            Some(Rc::new(EnvNode::Frame { vals, home }))
        }
    }
}

/// [`lookup`] and [`env_home`] over **one** walk, for the one-capture closure the
/// `Abs` arm builds: the value at `index`, and the terminal the chain ends in.
/// Resuming the terminal walk from the cell the index landed on rather than from
/// `env` gives the same node — a chain is linear, so every walk out of it passes
/// through that cell — while skipping the links already crossed.
///
/// **Unless the index walked through the terminal.** Once a `Local` can pass
/// through a [`Module`](EnvNode::Module) node into its frame, the cell the index
/// stopped on may lie *inside* that frame, and resuming from there yields the
/// frame's own terminal rather than the module's. So the walk remembers the first
/// `Module` it passes and answers with that: it is exactly what
/// [`env_home`] would have returned from `env`, without walking twice.
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.as_deref() {
            Some(EnvNode::Cons { val, next }) => {
                if rest == 0 {
                    break val.clone();
                }
                rest -= 1;
                cur = next;
            }
            Some(EnvNode::Frame { vals, .. }) => match vals.get(rest) {
                Some(val) => break val.clone(),
                None => unreachable!("resolved index walked past the captured frame"),
            },
            None => unreachable!("resolved index walked past the environment"),
            Some(EnvNode::Module { frame, .. }) => {
                if passed.is_none() {
                    passed = Some(cur);
                }
                cur = frame;
            }
        }
    };
    let home = match passed {
        Some(home) => home.clone(),
        None => env_home(cur),
    };
    (val, home)
}

/// Build a closure's captured frame from its resolved `plan` (see [`Capture`]) in
/// **one** walk of the defining environment: the plan is sorted by `outer`, so the
/// walk only ever moves forward — it advances to each capture's cell in turn and
/// writes the value to that capture's `slot`. Once the walk reaches the enclosing
/// [`Frame`](EnvNode::Frame) it stops moving: every remaining capture reads that
/// frame by direct index (`outer - depth`), the common case for a name from
/// further out than the immediate activation.
///
/// The frame is filled out of order (slot order is fixed at a free variable's first
/// use, not by its index), so it starts as a cheap placeholder fill; the resolver
/// guarantees each slot is written exactly once.
///
/// The walk also yields the chain's terminal, which the caller needs for the
/// frame's `home`: it is taken from where the last capture left the walk, not from
/// `env`, so the links the plan already crossed are not crossed twice — except
/// when the walk passed a [`Module`](EnvNode::Module) node, which it remembers for
/// the same reason [`lookup_and_home`] does.
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.as_deref() {
                Some(EnvNode::Cons { val, next }) => {
                    if depth == cap.outer {
                        vals[cap.slot as usize] = val.clone();
                        break;
                    }
                    depth += 1;
                    cur = next;
                }
                Some(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.
                Some(EnvNode::Module { frame, .. }) => {
                    if passed.is_none() {
                        passed = Some(cur);
                    }
                    cur = frame;
                }
                None => unreachable!("capture index walked past the environment"),
            }
        }
    }
    let home = match passed {
        Some(home) => home.clone(),
        None => env_home(cur),
    };
    (vals.into_boxed_slice(), home)
}

/// The environment's **terminal**: the empty environment (`None`) or the
/// [`Module`](EnvNode::Module) node a chain ends in, past any consed bindings and any
/// captured frame. A closure built here carries it on as its frame's `home`, so a
/// module item's body reached from inside the closure still finds its module (and
/// finds the same node, so no environment is allocated to run it).
fn env_home(env: &Env) -> Env {
    let mut cur = env;
    loop {
        match cur.as_deref() {
            Some(EnvNode::Cons { next, .. }) => cur = next,
            Some(EnvNode::Frame { home, .. }) => return home.clone(),
            Some(EnvNode::Module { .. }) => return cur.clone(),
            None => return None,
        }
    }
}

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

/// Materialize the module item at `index`: evaluate its stored body against
/// `home` — the [`Module`](EnvNode::Module) terminal alone, no lexical bindings —
/// yielding a value, typically a closure that captures `home` and so keeps the
/// module alive. Shared by `ModItem` resolution and module-applied-to-symbol
/// dispatch; an index outside the table raises `.missing_property`.
///
/// An item **whose body is a literal abstraction** is stamped with the item's
/// reserved id (`id_base + index`, see [`instantiate`]) instead of the fresh one
/// the `Abs` arm minted, so two accesses of one item produce *equal* closures.
/// They are interchangeable in every other respect already — same `Rc<Lambda>`
/// out of the `ModuleData`, same terminal, `applied: 0` — so the stamp is the
/// whole of what makes `M.f == M.f` hold, retiring v0's
/// `Test.factorial != Test.factorial` wart.
///
/// The stamp is keyed on the body's *shape*, not on the result being a closure,
/// so an item that merely forwards a callable keeps that callable's identity:
/// `g = f` materializes to the very same value `f` does, and `M.g == M.f`. Only
/// an item that *is* a function definition claims the item's own identity.
/// Anything else — a data item, a closure nested inside one (`pair = [&x x]`) —
/// is returned untouched.
///
/// A module **sibling reference** ([`Expr::ModItem`]): walk out to the home
/// module carried at the base of the environment ([`EnvNode::Module`]) and
/// materialize the item at `index` (evaluate its stored body, then
/// `materialize_body`). The index was assigned at resolve against this very module's
/// sorted table, so the lookup is a slice index with no name compare, and it is
/// in range. Only module-item bodies contain `ModItem`, and they always run under
/// a `Module` home terminal, so the walk finds one — through a closure's captured
/// frame, which carries the terminal on as its `home` (see [`EnvNode::Frame`]).
/// Handing the body the terminal the walk stopped on, rather than allocating a
/// fresh `Module` node, gives it exactly the module's static environment with no
/// lexical bindings — the `Cons`es and frames are stripped by the walk — while
/// saving an allocation per reference.
///
/// Outlined **whole**, walk included, and worth being deliberate about:
/// [`eval_env`] is instruction-cache resident, and growing this arm in place cost
/// ~9% on `rec_deep` — a benchmark that loads no module at all — and ~17% on
/// `mod_rec_deep`. Leaving one call in the arm is both smaller than the walk it
/// replaces and faster than either inlined form.
///
/// A member index at or past the item table is an **iota** — see
/// [`ModuleData::iota_names`] — and needs no materialization at all: the value is
/// the terminal this walk just found plus the position, so the arm falls out of
/// the same walk, the same bounds compare, and one refcount bump.
///
/// `depth` is how many terminals to **step over** before the owning one: a
/// [`recur`](Expr::Recur) nested in a module body puts two on the chain, and the
/// module's own items have to skip the `recur`'s. A step crosses into the skipped
/// terminal's frame, which is where the enclosing module sits. It is `0` for every
/// reference in a program with no nesting, so the common path is the loop it was
/// before.
#[inline(never)]
fn mod_item(env: &Env, index: u32, depth: u32, ctx: &Ctx) -> Result<Value, Raised> {
    let mut cur = env;
    let mut depth = depth;
    let (data, id_base) = loop {
        match cur.as_deref() {
            Some(EnvNode::Cons { next, .. }) => cur = next,
            Some(EnvNode::Frame { home, .. }) => cur = home,
            Some(EnvNode::Module {
                data,
                id_base,
                frame,
            }) => {
                if depth == 0 {
                    break (&**data, *id_base);
                }
                depth -= 1;
                cur = frame;
            }
            None => return Err(raise_sym("no_module")),
        }
    };
    let Some(body) = data.item(index) else {
        // Past the item table: an iota, addressed by the same member index space.
        // Derived here rather than stored anywhere — the terminal the walk landed
        // on *is* the identity, so this is a bounds compare and a refcount bump.
        let index = index - data.len() as u32;
        if data.iota(index).is_none() {
            return Err(raise_sym("missing_property"));
        }
        let home = cur.clone().expect("the walk stopped on a module terminal");
        return Ok(Value::Iota { home, index });
    };
    materialize_body(body, cur, id_base, index, ctx)
}

/// Walk out to the [`Module`](EnvNode::Module) terminal `depth` steps in and hand
/// back one of the three [home-module leaves](crate::HomeLeaf) over it.
///
/// The walk is [`mod_item`]'s without the table index: a leaf addresses the
/// terminal itself rather than a member of it. `depth` is how many terminals to
/// step over, and it is the resolver that decided which one to land on — a leaf
/// names the nearest terminal *written as a module*, and eval learns no kind, so
/// the count is all it needs.
///
/// `__new` and `__value` are the object builtins **pre-applied to the module**,
/// which is an ordinary partial application: what comes back takes the one
/// remaining argument through the existing currying path, with no evaluation
/// machinery of its own. Being values, they can be handed out — a module that
/// exports `mint = __new` has given away construction deliberately.
#[inline(never)]
fn home_leaf(env: &Env, leaf: HomeLeaf, depth: u32) -> Result<Value, Raised> {
    let mut cur = env;
    let mut depth = depth;
    let home = loop {
        match cur.as_deref() {
            Some(EnvNode::Cons { next, .. }) => cur = next,
            Some(EnvNode::Frame { home, .. }) => cur = home,
            Some(EnvNode::Module { frame, .. }) => {
                if depth == 0 {
                    break cur.clone().expect("the walk stopped on a module terminal");
                }
                depth -= 1;
                cur = frame;
            }
            None => return Err(raise_sym("no_module")),
        }
    };
    let op = match leaf {
        HomeLeaf::Module => return Ok(Value::Module(home)),
        HomeLeaf::New => Builtin::ObjNew,
        HomeLeaf::Value => Builtin::ObjValue,
    };
    Ok(Value::Builtin {
        op,
        args: alloc::vec![Value::Module(home)],
    })
}

/// Evaluate a [`recur`](Expr::Recur): build a [`Module`](EnvNode::Module) terminal
/// over the **current environment** and run the body under it.
///
/// This is instantiation with a cons-shaped frame. Where [`instantiate`] copies a
/// fixed slot list into a flat [`Frame`](EnvNode::Frame), here the frame *is* the
/// enclosing lexical environment, shared by one refcount bump — so entering a
/// `recur` allocates exactly one node and copies nothing. A binding's reference to
/// an enclosing name is then the same de Bruijn index it would have had inline at
/// the `recur` site, because the terminal is not counted by the walk.
///
/// The id block is reserved **per evaluation**, so two activations of the same
/// `recur` mint different item identities — which is the wanted semantics: they
/// close over different frames and are not the same function.
///
/// Nothing is forced at entry. The bindings stay dehydrated in the table and are
/// materialized on reference, so a group may hold a body that would raise, or one
/// that only makes sense after another has run.
#[inline(never)]
fn recur(group: &Rc<ModuleData>, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
    let home = Some(Rc::new(EnvNode::Module {
        id_base: ctx.reserve_ids(group.len() as u64),
        data: Rc::clone(group),
        frame: env.clone(),
    }));
    eval_env(recur_body(group), &home, ctx)
}

/// Evaluate item `index`'s `body` in its module terminal `home` — the shared tail
/// of both materialization paths, the `ModItem` walk ([`mod_item`]) and the
/// by-name `M.name` access ([`materialize`]).
///
/// A **function item** — a body that is a literal abstraction, the overwhelmingly
/// common shape — is built here directly, taking the id reserved for it at
/// instantiation (`id_base + index`, see [`instantiate`]) rather than a fresh one.
/// Two accesses of one item then produce *equal* closures: they are
/// interchangeable in every other respect already — same `Rc<Lambda>` out of the
/// `ModuleData`, same terminal, `applied: 0` — so this is the whole of what
/// retires v0's `Test.factorial != Test.factorial` wart.
///
/// Building it here rather than stamping over what [`eval_env`]'s `Abs` arm
/// returns is what makes the fix free: it skips a dispatch through `eval_env`
/// *and* the `Ctx` counter write, paying for the terminal walk that precedes it.
/// Handing the value back out of `eval_env` to overwrite its `id` costs ~4% on
/// `mod_fib_naive` instead — taking `&mut` on the result forces it to memory.
///
/// The identity is keyed on the body's *shape*, not on the result being a
/// closure, so an item that merely forwards a callable keeps that callable's
/// identity: `g = f` materializes to the very same value `f` does, and
/// `M.g == M.f`. Only an item that *is* a function definition claims the item's
/// own identity. Anything else — a data item, a closure nested inside one
/// (`pair = [&x x]`) — goes through `eval_env` untouched.
#[inline]
fn materialize_body(
    body: &Expr,
    home: &Env,
    id_base: u64,
    index: u32,
    ctx: &Ctx,
) -> Result<Value, Raised> {
    if let Expr::Abs(code) = body {
        let env = match &code.captures {
            Captures::Chain => home.clone(),
            Captures::Frame(plan) => capture_env(home, plan),
            Captures::Unresolved => unreachable!("unresolved abstraction reached eval"),
        };
        return Ok(Value::Closure {
            id: id_base + index as u64,
            code: Rc::clone(code),
            applied: 0,
            env,
        });
    }
    eval_env(body, home, ctx)
}

/// Materialize the item **named** `name` out of the module object whose terminal
/// is `home`: binary-search the name to its index, then evaluate its body in that
/// terminal and stamp it exactly as the `ModItem` arm of [`eval_env`] does for a
/// sibling reference. Reusing the object's own node — the object *is* the
/// terminal — means an `M.name` access allocates no environment (v0 built a fresh
/// `Module` node per access); it costs one refcount bump to make the `Env` the
/// evaluator takes. A name absent from the module raises `.missing_property`.
fn materialize(home: &Rc<EnvNode>, name: &Text, ctx: &Ctx) -> Result<Value, Raised> {
    let EnvNode::Module { data, id_base, .. } = &**home else {
        unreachable!("a module object always holds a module terminal")
    };
    let index = data
        .index_of(name)
        .ok_or_else(|| raise_sym("missing_property"))?;
    let body = data.item(index).expect("index_of returned a live index");
    materialize_body(body, &Some(Rc::clone(home)), *id_base, index, ctx)
}

/// Apply a **receiver** to a symbol: the dispatch arm of `apply1` / `apply_n`,
/// covering every value kind that is neither callable nor a module.
///
/// The rule is one line — the symbol names a member of the receiver's prototype,
/// and the receiver is passed to it — and [`proto_of`] is what makes it total: an
/// object dispatches through its own prototype, and every other kind through the
/// builtin module for it, so `2 .add 3` reaches `__Int.add 2 3` through the
/// receiver rather than by being written out.
///
/// **List projection wins over dispatch**, for now. A numeric symbol on a list
/// projects as it always has; any other symbol dispatches to `__List` instead of
/// raising `.bad_projection`. The two symbol spaces are syntactically disjoint
/// (`.0` versus `.get`), so nothing shadows. The coexistence is temporary: `.N`
/// projection is a vestige of `( … )`-as-tuple, and a real projection syntax
/// (TODO.md) would leave the symbol space on a list to dispatch alone.
///
/// A non-symbol argument raises `.not_applicable` — there is no `x arg` call form
/// for a non-callable.
///
/// **Outlined**, like [`mod_item`] and for the same reason: it sits in the
/// fall-through arm of `apply1` and `apply_n`, which are as instruction-cache
/// resident as [`eval_env`] is. Letting it inline there cost ~17% on `rec_deep`
/// — a benchmark that dispatches on nothing at all — and nothing else moved (see
/// `docs/done/2026-08-13_elly-modules-env.md` on that measurement).
#[inline(never)]
fn receiver(this: Value, name: &Value, rest: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
    let Value::Symbol(s) = name else {
        return Err(raise_sym("not_applicable"));
    };
    if let Value::List(elems) = &this {
        if is_index(s) {
            let projected = project(elems, s)?;
            return apply_n(projected, rest, ctx);
        }
    }
    let proto = match &this {
        Value::Object(obj) => Rc::clone(&obj.proto),
        other => match proto_of(other, ctx) {
            Value::Module(home) => home,
            _ => unreachable!("a prototype is always a module value"),
        },
    };
    dispatch(&proto, this, s, rest, ctx)
}

/// **Dispatch** a method: materialize `name` out of `proto` and apply it to the
/// receiver, followed by `rest` — the remaining arguments of the call spine.
///
/// ```text
/// x .m a b   ≡   (materialize (proto of x) .m) x a b
/// ```
///
/// So `x.m` is the method with `self` already bound, and the method's own
/// parameters follow. The lookup is the very same [`materialize`] a written
/// `M.name` runs — one binary search over the item table — which is why a
/// [`local`](ModuleData::local_names) is a private method for free: it is not in
/// that table, so `x.helper` and `M.helper` both answer `.missing_property`.
///
/// The whole spine goes in one call rather than binding the receiver and looping,
/// so a two-parameter method never builds the partial `x.m` would be. The small
/// arities gather on the stack, as [`eval_env`]'s call spine does; only a spine of
/// four or more arguments past the receiver falls back to a `Vec`.
///
/// A name absent from the prototype's item table raises `.missing_property`, and
/// an item that materializes to a non-callable falls through to ordinary
/// application — both mirroring module access.
fn dispatch(
    proto: &Rc<EnvNode>,
    this: Value,
    name: &Text,
    rest: &[Value],
    ctx: &Ctx,
) -> Result<Value, Raised> {
    let method = materialize(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)
        }
    }
}

/// Whether `sym` (a symbol's text, stored without its dot) is a **projection**
/// index — all ASCII digits, so `.0` and `.12` are projections while `.get` and
/// `.size` are member names. The two spaces are disjoint by shape, which is what
/// lets a list carry both (see [`receiver`]).
fn is_index(sym: &str) -> bool {
    !sym.is_empty() && sym.bytes().all(|b| b.is_ascii_digit())
}

/// The refutation `⟂` a pattern probe reaches on a structural miss: a `NoMatch`
/// carrying `tag` (stored without its dot) as the *original* error it stands for.
/// `__match` catches it and falls through; uncaught, it decays to `.tag`.
fn no_match(tag: &'static str) -> Raised {
    Raised::NoMatch(Value::Symbol(Text::from_static(tag)))
}

/// Whether `value`'s prototype is the module `expr` 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)]
fn proto_is(expr: &Expr, value: &Value, env: &Env, ctx: &Ctx) -> Result<bool, Raised> {
    let expected = eval_env(expr, env, ctx)?;
    if !matches!(expected, Value::Module(_)) {
        return Err(raise_sym("not_a_module"));
    }
    Ok(proto_of(value, ctx) == expected)
}

/// The payload of `value`, provided it is an object whose prototype is the home
/// module `depth` terminals out — the whole of what a [`Unwrap`](Pattern::Unwrap)
/// pattern tests before descending into the pattern it wraps. Refutes
/// `.not_an_object` / `.foreign_object`, the tags the `__value` *expression*
/// raises, since unwrapping a foreign object has no other sound reading.
#[inline(never)]
fn unwrapped(value: &Value, env: &Env, depth: u32) -> Result<Value, Raised> {
    let Value::Object(obj) = value else {
        return Err(no_match("not_an_object"));
    };
    let Value::Module(home) = home_leaf(env, HomeLeaf::Module, depth)? else {
        unreachable!("the module leaf always yields a module value")
    };
    if !Rc::ptr_eq(&obj.proto, &home) {
        return Err(no_match("foreign_object"));
    }
    Ok(obj.data.clone())
}

/// Match `value` against `pat`, consing any bindings onto `env` and returning the
/// extended environment, or a `Raised` on a miss. Bindings cons in the exact order
/// the resolver assigned de Bruijn indices, so an embedded `= <expr>` / map key
/// resolves against the env built so far (including names bound earlier in the same
/// pattern, `&[a, = a]`). A structural mismatch is a `NoMatch(tag)` refutation
/// (reproducing the same tags the old eliminator desugaring raised: `.not_a_list`,
/// `.list_size_mismatch`, `.not_a_map`, `.missing_key`, `.map_size_mismatch`,
/// `.no_match`); a real `Error` from an embedded expression propagates.
/// `Bind`/`Discard` are irrefutable; every other shape may refute.
fn match_pattern(pat: &Pattern, value: &Value, env: Env, ctx: &Ctx) -> Result<Env, Raised> {
    match pat {
        // `_` — matches anything, binds nothing.
        Pattern::Discard => Ok(env),
        // `name` — cons the subject.
        Pattern::Bind(_) => Ok(bind(value.clone(), env)),
        // `name = pat` — cons the whole subject, then match the inner pattern
        // against the same value.
        Pattern::At(_, inner) => match_pattern(inner, value, bind(value.clone(), env), ctx),
        // `= <ref>` — match iff the subject equals the comparand's value. The
        // comparand is a name or literal (a closed pattern grammar); evaluating a
        // name reads the env and raises only if genuinely unbound (rejected at parse
        // now), a normal reference `Error` that propagates; a plain inequality
        // refutes with the bare `.no_match` tag.
        Pattern::Equal(expr) => {
            let expected = eval_env(expr, &env, ctx)?;
            if *value == expected {
                Ok(env)
            } else {
                Err(no_match("no_match"))
            }
        }
        // `< <ref>` / `> <ref>` — ordered comparison. Ordering is defined only
        // within a comparable kind (`Int` today; `Str` later), so unless the
        // subject and the bound are both of one such kind this refutes `.not_int`
        // rather than raising; an in-kind comparison that does not hold refutes
        // the plain `.no_match`.
        Pattern::Less(expr) => {
            let bound = eval_env(expr, &env, ctx)?;
            order_match(value, &bound, Ordering::Less)?;
            Ok(env)
        }
        Pattern::Greater(expr) => {
            let bound = eval_env(expr, &env, ctx)?;
            order_match(value, &bound, Ordering::Greater)?;
            Ok(env)
        }
        // `pat as <Proto>` — narrow by prototype, then match the inner pattern; a
        // value of another prototype refutes `.no_match`.
        //
        // The compiled form is a discriminant test and never raises. The general
        // form evaluates its reference — an atom, resolved before the inner
        // pattern — and requires a *module*: a non-module reference is a real
        // error rather than a refutation, since it is a mistake about the pattern
        // rather than about the subject.
        Pattern::Type(proto, inner) => {
            let matched = match proto {
                ProtoRef::Kind(ty) => ty_matches(*ty, value),
                ProtoRef::Ref(expr) => proto_is(expr, value, &env, ctx)?,
            };
            if matched {
                match_pattern(inner, value, env, ctx)
            } else {
                Err(no_match("no_match"))
            }
        }
        // `__value <pat>` — an object of the home module, unwrapped. The prototype
        // check is the one `__value` the expression performs, and refutes with the
        // same two tags; the payload then goes to the inner pattern. Outlined, so
        // the arm costs the matcher one call (see [`unwrapped`]).
        Pattern::Unwrap { depth, inner } => {
            let data = unwrapped(value, &env, *depth)?;
            match_pattern(inner, &data, env, ctx)
        }
        // `(p1 | p2)` — committed: the first arm whose pattern matches wins (a
        // later failure in the body does not backtrack). A refuting left arm falls
        // through to the right, matched against the *original* env; both arms cons
        // the same binding sequence (checked by the resolver), so a reference after
        // the or-pattern reads one fixed index whichever arm matched. A real error
        // propagates.
        Pattern::Or(left, right) => match match_pattern(left, value, env.clone(), ctx) {
            Ok(e) => Ok(e),
            Err(Raised::NoMatch(_)) => match_pattern(right, value, env, ctx),
            Err(e) => Err(e),
        },
        Pattern::List(elems, rest) => match_list(elems, rest, value, env, ctx),
        Pattern::Map(entries, rest) => match_map(entries, rest, value, env, ctx),
    }
}

/// Match a list pattern: kind (`.not_a_list`), then arity (`.list_size_mismatch`
/// — exact without a rest, a minimum with one), then the fixed prefix element by
/// element, binding a named rest to the remainder. The rest is bound *before* the
/// elements (so an element name shadows it), reproducing the old desugaring's
/// scope order.
fn match_list(
    elems: &[Pattern],
    rest: &Rest,
    value: &Value,
    env: Env,
    ctx: &Ctx,
) -> Result<Env, Raised> {
    let t = match value {
        Value::List(t) => t,
        _ => return Err(no_match("not_a_list")),
    };
    let n = elems.len();
    let has_rest = !matches!(rest, Rest::None);
    if (has_rest && t.len() < n) || (!has_rest && t.len() != n) {
        return Err(no_match("list_size_mismatch"));
    }
    let mut env = env;
    if let Rest::Named(_) = rest {
        let mut rem = Vector::new();
        for e in t.iter().skip(n) {
            rem.push_back_mut(e.clone());
        }
        env = bind(Value::List(rem), env);
    }
    for (i, p) in elems.iter().enumerate() {
        env = match_pattern(p, t.get(i).unwrap(), env, ctx)?;
    }
    Ok(env)
}

/// Match a map pattern in two passes (see
/// `docs/done/2026-07-26_elly-patterns-native.md`): concrete-key **lookups**
/// claim their keys first, then **captures** pop the smallest remaining entry
/// each, then closedness / a named rest apply to what is left. Lookup key
/// expressions all evaluate **once**, in source order, before the kind test —
/// matching the old desugaring, whose key temps were bound outermost.
fn match_map(
    entries: &[(MapKey, Pattern)],
    rest: &Rest,
    value: &Value,
    env: Env,
    ctx: &Ctx,
) -> Result<Env, Raised> {
    // Evaluate every lookup key first (source order, against the incoming env —
    // before any of this pattern's binds); partition into lookups and captures. A
    // lookup key is a name or literal, so it raises only on an unbound name (a
    // normal reference error), which propagates here.
    let mut lookups: Vec<(Value, &Pattern)> = Vec::new();
    let mut captures: Vec<(&Pattern, &Pattern)> = Vec::new();
    for (key, vpat) in entries {
        match key {
            MapKey::Lookup(kexpr) => lookups.push((eval_env(kexpr, &env, ctx)?, vpat)),
            MapKey::Capture(kpat) => captures.push((kpat, vpat)),
        }
    }
    // Kind test after the keys evaluate.
    let m = match value {
        Value::Map(m) => m,
        _ => return Err(no_match("not_a_map")),
    };
    let mut env = env;
    // Pass 1: probe each concrete key, matching its value pattern and claiming
    // the key from the remainder. A missing key refutes `.missing_key`.
    let mut remainder = m.clone();
    for (k, vpat) in &lookups {
        match m.get(k) {
            Some(v) => {
                env = match_pattern(vpat, v, env, ctx)?;
                remainder = remainder.remove(k);
            }
            None => return Err(no_match("missing_key")),
        }
    }
    // Pass 2: each capture pops an unspecified remaining entry (the map is
    // unordered; which entry a capture peels is not a language guarantee),
    // matching the key and value patterns; an empty remainder refutes `.missing_key`.
    for (kpat, vpat) in &captures {
        // Clone the entry out first so the iterator borrow ends before the remove.
        let entry = remainder.iter().next().map(|(k, v)| (k.clone(), v.clone()));
        match entry {
            Some((k, v)) => {
                remainder = remainder.remove(&k);
                env = match_pattern(kpat, &k, env, ctx)?;
                env = match_pattern(vpat, &v, env, ctx)?;
            }
            None => return Err(no_match("missing_key")),
        }
    }
    // Tail: closed → the leftover must be empty; named rest → bind it; anon → drop.
    match rest {
        Rest::None => {
            if remainder.size() != 0 {
                return Err(no_match("map_size_mismatch"));
            }
        }
        Rest::Named(_) => env = bind(Value::Map(remainder), env),
        Rest::Anon => {}
    }
    Ok(env)
}

/// Back the `< expr` / `> expr` ordering patterns: match iff `subject` compares
/// to `bound` as `want` (`Less` / `Greater`). Ordering is defined only within a
/// comparable kind — `Int` for now (later `Str` will join, lexicographically) —
/// so unless both operands share such a kind this refutes `.not_int`; an in-kind
/// comparison that does not hold refutes the plain `.no_match`.
fn order_match(subject: &Value, bound: &Value, want: Ordering) -> Result<(), Raised> {
    let cmp = match (subject, bound) {
        (Value::I64(a), Value::I64(b)) => a.cmp(b),
        (Value::BigInt(a), Value::BigInt(b)) => a.cmp(b),
        // Mixed magnitudes: by the canonical invariant a `BigInt` is `|n| > i64::MAX`
        // and never zero, so its sign alone orders it against any `i64`.
        (Value::I64(_), Value::BigInt(b)) => {
            if b.sign() == Sign::Minus {
                Ordering::Greater
            } else {
                Ordering::Less
            }
        }
        (Value::BigInt(a), Value::I64(_)) => {
            if a.sign() == Sign::Minus {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        }
        (Value::Str(a), Value::Str(b)) => a.cmp(b),
        // Off-kind (not a shared `Int`/`Str` ordering): the refutation tag follows
        // the **comparand** (the bound demands the subject's kind). A `Str` bound
        // refutes `.not_string`; every other bound keeps the Int-only default
        // `.not_int`.
        _ => {
            let tag = if matches!(bound, Value::Str(_)) {
                "not_string"
            } else {
                "not_int"
            };
            return Err(no_match(tag));
        }
    };
    if cmp == want {
        Ok(())
    } else {
        Err(no_match("no_match"))
    }
}

/// Whether `value` is of the value kind `ty` — the total, non-raising test behind
/// an `as <Proto>` pattern whose reference resolved to a builtin module
/// ([`ProtoRef::Kind`]). It is the compiled form of "`__proto value` is that
/// module", so it answers exactly what [`proto_of`] would, without the `Ctx` round
/// trip: `Fun` is any callable, `Mod` a module value, and an *object* is of none
/// of them — its prototype is its own.
fn ty_matches(ty: TyKind, value: &Value) -> bool {
    match ty {
        TyKind::Int => matches!(value, Value::I64(_) | Value::BigInt(_)),
        TyKind::Sym => matches!(value, Value::Symbol(_)),
        TyKind::Str => matches!(value, Value::Str(_)),
        TyKind::List => matches!(value, Value::List(_)),
        TyKind::Map => matches!(value, Value::Map(_)),
        TyKind::Fun => matches!(
            value,
            Value::Closure { .. } | Value::Builtin { .. } | Value::HostFn { .. }
        ),
        TyKind::Mod => matches!(value, Value::Module(_)),
    }
}

/// Project position `sym` (an `N` symbol, stored without its leading dot) out of
/// a list's elements.
fn project(elems: &Vector<Value>, sym: &str) -> Result<Value, Raised> {
    let idx: usize = sym.parse().map_err(|_| raise_sym("bad_projection"))?;
    elems
        .get(idx)
        .cloned()
        .ok_or_else(|| raise_sym("projection_out_of_range"))
}

impl Value {
    /// Build an integer value from a `BigInt`, **demoting** to the inline
    /// [`Value::I64`] form whenever it fits. This is the single choke point that
    /// maintains the canonical invariant — an integer is [`Value::BigInt`] *iff* it
    /// does not fit `i64` — on which `PartialEq`, `Hash`, and ordering all rely, so
    /// every wide arithmetic result must pass through here. Also the constructor
    /// hosts (the Python bindings) use to admit an arbitrary `BigInt`.
    pub fn from_bigint(n: BigInt) -> Value {
        match i64::try_from(&n) {
            Ok(i) => Value::I64(i),
            Err(_) => Value::BigInt(Rc::new(n)),
        }
    }

    /// [`from_bigint`](Value::from_bigint) for a `BigInt` the caller holds by
    /// reference — an `Expr::Int` literal, which the AST owns and eval must not
    /// consume. The `i64` demotion is decided *before* any clone, so a literal that
    /// fits costs no allocation at all; only a genuinely wide one is copied. Cloning
    /// first and demoting after allocated a digit vector per literal evaluation and
    /// dropped it immediately, on a path every arithmetic loop runs.
    pub fn from_bigint_ref(n: &BigInt) -> Value {
        match i64::try_from(n) {
            Ok(i) => Value::I64(i),
            Err(_) => Value::BigInt(Rc::new(n.clone())),
        }
    }

    /// A **host function** as a value, ready to be applied or written into a
    /// module's frame: the constructor a host reaches for instead of building the
    /// [`HostFn`] variant by hand. Unapplied, so the first argument starts the
    /// ordinary currying.
    ///
    /// Panics on `arity == 0` (see [`HostFn`]).
    pub fn host_fn(
        name: impl Into<Text>,
        arity: usize,
        f: impl Fn(&[Value], &Ctx) -> Result<Value, Raised> + 'static,
    ) -> Value {
        Value::HostFn {
            code: Rc::new(HostFn::new(name, arity, f)),
            args: Box::new([]),
        }
    }

    /// A list value from its elements. The backing `rpds::Vector` is an
    /// implementation detail a host should not have to name: matching its version
    /// *and features* against the core's is a real hazard (workspace feature
    /// unification is global), so building one goes through here.
    pub fn list(elems: impl IntoIterator<Item = Value>) -> Value {
        Value::List(elems.into_iter().collect())
    }

    /// A map value from its entries, later entries winning on an equal key. Here
    /// for the reason [`list`](Value::list) is.
    pub fn map(entries: impl IntoIterator<Item = (Value, Value)>) -> Value {
        let mut m = HashTrieMap::new();
        for (k, v) in entries {
            m.insert_mut(k, v);
        }
        Value::Map(m)
    }

    /// The elements of a list value, or `None` for anything else — the reading
    /// counterpart of [`list`](Value::list), so a host can take a list apart
    /// without naming `rpds` either. The iterator knows its length, which is
    /// usually the first thing a caller checks.
    pub fn list_items(&self) -> Option<impl ExactSizeIterator<Item = &Value>> {
        match self {
            Value::List(elems) => Some(elems.iter()),
            _ => None,
        }
    }

    /// How many more arguments a **function-shaped** value wants before it runs:
    /// a closure's unbound parameters, or a builtin's or host function's
    /// ungathered ones. `None` for everything else, *including* the values that
    /// are applicable without being functions — a list and a module both take a
    /// symbol, but that is projection, not a call with arguments outstanding.
    ///
    /// A runner uses it to notice that it under-applied: `__main = &(io, x) …`
    /// applied to one capability yields a partial, and the program quietly does
    /// nothing unless someone says so (see `docs/done/2026-08-14_elly-run.md`).
    pub fn remaining_arity(&self) -> Option<usize> {
        match self {
            Value::Closure { code, applied, .. } => Some(code.head.len() - *applied as usize),
            Value::Builtin { op, args } => Some(op.arity() - args.len()),
            Value::HostFn { code, args } => Some(code.arity - args.len()),
            _ => None,
        }
    }

    /// The compiled module behind a [`Value::Module`], or `None` for anything
    /// else. A module value holds its [`Module`](EnvNode::Module) terminal rather
    /// than the [`ModuleData`] directly, so a host that only wants the item table
    /// (the Python bindings' `Obj.keys` / `in`) reaches it through here instead of
    /// matching on the environment's shape.
    pub fn module_data(&self) -> Option<&Rc<ModuleData>> {
        match self {
            Value::Module(home) => match &**home {
                EnvNode::Module { data, .. } => Some(data),
                _ => unreachable!("a module value always holds a module terminal"),
            },
            _ => None,
        }
    }

    /// The [`ObjectData`] behind a [`Value::Object`], or `None` for anything else
    /// — the payload and the prototype, for a host that wants to look inside one
    /// (the Python bindings' `Object.data` / `.proto`).
    pub fn object_data(&self) -> Option<&Rc<ObjectData>> {
        match self {
            Value::Object(obj) => Some(obj),
            _ => None,
        }
    }

    /// A human-readable rendering used by the eval golden tests.
    pub fn to_display(&self) -> String {
        let mut out = String::new();
        self.write_display(&mut out);
        out
    }

    fn write_display(&self, out: &mut String) {
        match self {
            Value::I64(n) => out.push_str(&n.to_string()),
            Value::BigInt(n) => out.push_str(&n.to_string()),
            Value::Symbol(s) => {
                out.push('.');
                out.push_str(s);
            }
            // A string renders as a quoted, re-escaped literal (`"foo"`), so it
            // reads apart from the symbol `.foo` and the name `foo`.
            Value::Str(s) => json_str(s, out),
            // A list renders with brackets (`[]`, `[.a]`, `[.a, .b]`); the empty
            // list `[]` is unit.
            Value::List(vs) => {
                out.push('[');
                for (i, v) in vs.iter().enumerate() {
                    if i > 0 {
                        out.push_str(", ");
                    }
                    v.write_display(out);
                }
                out.push(']');
            }
            // A map is unordered, so entries render sorted by rendered key text
            // (ties broken by rendered value) for a stable, human-meaningful dump:
            // `{}` empty, else `{ .a: 1, .b: 2 }`.
            Value::Map(m) => {
                if m.is_empty() {
                    out.push_str("{}");
                } else {
                    let mut entries: Vec<(String, String)> = m
                        .iter()
                        .map(|(k, v)| {
                            let mut ks = String::new();
                            k.write_display(&mut ks);
                            let mut vs = String::new();
                            v.write_display(&mut vs);
                            (ks, vs)
                        })
                        .collect();
                    entries.sort();
                    out.push('{');
                    for (i, (ks, vs)) in entries.iter().enumerate() {
                        out.push_str(if i > 0 { ", " } else { " " });
                        out.push_str(ks);
                        out.push_str(": ");
                        out.push_str(vs);
                    }
                    out.push_str(" }");
                }
            }
            Value::Closure { .. } => out.push_str("<closure>"),
            Value::Builtin { op, .. } => {
                out.push_str("<builtin ");
                out.push_str(op.name());
                out.push('>');
            }
            // Named, like a builtin, and by the same reasoning: the name is what
            // a reader can act on. It is the host's, not the language's, so it
            // carries no `__`.
            Value::HostFn { code, .. } => {
                out.push_str("<hostfn ");
                out.push_str(code.name.as_str());
                out.push('>');
            }
            Value::Module(_) => out.push_str("<module>"),
            // Opaque, like a closure, and named only by its own declaration:
            // `<const .true>`. The module it came from is *not* named — a
            // module's canonical name is host-shaped (a resolver path), so
            // printing it would make output depend on how a host names files,
            // and a module value itself does not show one either.
            Value::Iota { home, index } => {
                out.push_str("<const .");
                if let EnvNode::Module { data, .. } = &**home {
                    if let Some(name) = data.iota(*index) {
                        out.push_str(name);
                    }
                }
                out.push('>');
            }
            // The payload beside an unnamed kind: `<object 0>`. Naming the
            // prototype (`<Bool 0>`) waits on modules having a short display name
            // — a canonical name is host-shaped (a resolver path), so printing it
            // would make output depend on how a host names files, which is why an
            // iota renders `<const .true>` and a module `<module>`.
            //
            // The payload *is* shown: a debugger and an embedding host sit outside
            // the language's module scope. No builtin renders a value to a string,
            // so Elly code cannot reach a payload this way.
            Value::Object(obj) => {
                out.push_str("<object ");
                obj.data.write_display(out);
                out.push('>');
            }
        }
    }
}