elly_core/

resolve.rs

//! Name resolution: a static pass over the parsed AST that turns each in-scope
//! [`Expr::Name`] into a de Bruijn-indexed [`Expr::Local`] and rejects free
//! variables before evaluation.
//!
//! Every binding in Elly comes from one place — a [`crate::ast::Lambda`]
//! head matched against arguments — and there is no global/prelude environment
//! (builtins are hoisted to [`Expr::Builtin`] at parse). So every `Expr::Name`
//! either resolves to an enclosing `&`-binding or is **unbound**, and that is
//! decidable statically. [`resolve`] rewrites the tree in place and returns
//! [`ParseError::UnboundName`] on the first free name; wiring it into
//! `elly::parse` turns an unbound reference into a parse-time error instead of a
//! runtime `.unbound_name` raise.
//!
//! ## de Bruijn indices, per activation
//!
//! The runtime environment of a lambda activation is a nameless cons list of the
//! bindings that activation's head made — innermost/most-recent first — sitting on
//! the closure's captured **frame** (see `EnvNode` in `eval.rs`). The resolver
//! mirrors that shape with a stack of [`Level`]s, one per enclosing
//! `&`-abstraction, each holding the names its head binds (`locals`, in bind order)
//! and the free variables it captures (`captures`, in frame-slot order).
//!
//! A reference is resolved against the *innermost* level:
//!
//! 1. bound by this level's head → `locals.len() - 1 - pos` of the binder's
//!    (rightmost, so most recent) occurrence: the number of cells the matcher will
//!    have consed between the reference and its binder. A duplicate bind (`[a, a]`)
//!    pushes twice; the later one shadows, reproducing the old last-one-wins;
//! 2. already captured by this level → `locals.len() + slot`: the walk runs off the
//!    consed cells and lands in the frame at `slot`;
//! 3. otherwise → resolve it in the **parent** level (recursively, so a name may be
//!    captured down through several lambdas), record that outer index as a new
//!    capture slot of this level, and use `locals.len() + slot` as in (2).
//!
//! Step 3 is what fills [`Lambda::captures`](crate::ast::Lambda::captures): the
//! outer indices, in the enclosing activation's coordinates *at the point the `Abs`
//! is evaluated*, of the values to copy into the closure's frame. Those coordinates
//! are stable while the inner lambda is walked — the parent's `locals` do not change
//! during it — and a capture slot, once assigned, is never renumbered.
//!
//! At the outermost level there is no parent, so a name unknown there is unbound
//! ([`resolve`]), auto-bound into the root frame ([`resolve_open`]), or found in the
//! prelude ([`resolve_prelude`]).
//!
//! The walk mirrors the evaluator's *binding order* exactly (see `match_pattern`
//! in `eval.rs`): a list pattern binds its rest before its elements, a map pattern
//! evaluates all lookup keys before binding any value pattern, and an `= expr` /
//! `< expr` / `> expr` comparand (and a map lookup key) resolves against the names
//! bound *before* it — including earlier binders in the same pattern, e.g.
//! `&[a, = a]`. Getting this order right is what makes "accepted here" ⟺ "not an
//! unbound raise there", and puts each reference's index where the matcher will
//! have consed the value.
//!
//! ## Or-arms
//!
//! Both arms of `(p | q)` must bind the **same names in the same order**: under a
//! nameless cons list a reference after the or-pattern reads one fixed index
//! whichever arm matched, so the two arms must cons an identical binding sequence.
//! The resolver has that order naturally — it walks each arm and compares the
//! names they push — and rejects a mismatch with [`ParseError::OrBindersMismatch`]
//! (this tightens the old same-*set* rule to same-*sequence*; reordered arms like
//! `[x, y] | [y, x]` are now an error).
//!
//! An arm may also *capture* — `&([a, = x] | [a, = y])` reads two outer names — and
//! a capture is not undone when the left arm's locals are rolled back: a frame slot
//! is assigned once and holds whichever value the enclosing scope had, regardless of
//! which arm runs. Only the arms' `locals` take part in the sequence check.

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

use crate::ast::{Capture, Captures, Expr, Lambda, MapKey, Pattern, ProtoRef, Rest, Text};
use crate::eval::{Builtin, ModuleData};
use crate::parse::ParseError;

/// Rebuild a call spine `[<module>, .member, rest…]` around the member's own
/// builtin leaf: `__Int.add x y` becomes `__Int.add` applied to `x y`, and a bare
/// `__Int.add` becomes the leaf itself.
///
/// The remaining arguments are **moved** out of the old spine — each swapped for
/// the copyable leaf rather than cloned — so folding a call whose arguments are
/// large subtrees copies no tree.
fn fold_member(items: &mut [Expr], op: Builtin) -> Expr {
    let rest = &mut items[2..];
    if rest.is_empty() {
        return Expr::Builtin(op);
    }
    let mut spine: Vec<Expr> = Vec::with_capacity(rest.len() + 1);
    spine.push(Expr::Builtin(op));
    for arg in rest {
        spine.push(core::mem::replace(arg, Expr::Builtin(op)));
    }
    Expr::App(spine.into_boxed_slice())
}

/// Resolve a whole program against an empty scope: every free name is rejected
/// with [`ParseError::UnboundName`]. This is what `elly::parse` runs, so an
/// unbound reference is a parse-time error. Rewrites `expr` in place (names →
/// de Bruijn locals).
pub fn resolve(expr: &mut Expr) -> Result<(), ParseError> {
    Resolver::new(Vec::new(), false, Vec::new()).walk(expr)
}

/// Resolve each body of a module's bindings in place (name → de Bruijn `Local`,
/// sibling item → [`Expr::ModItem`], else [`ParseError::UnboundName`]). The item
/// names form an extra reference tier consulted **after** lexical scope and before
/// the unbound check, so a body may refer to any sibling regardless of source
/// order — the basis of order-independent, mutually recursive top-level
/// definitions (see `docs/done/2026-08-07_elly-modules-v0.md`). Called by
/// [`crate::compile_module`] after [`crate::parse::parse_module`].
///
/// The bindings are first **sorted by name**: that order is the module's item
/// table, and a sibling reference records its position there as the `ModItem`
/// index, so neither this pass nor eval compares names down a list. `parse_module`
/// rejects duplicates, so the names are distinct and the order is total.
///
/// A name in a module body is looked for in this order: the enclosing `&`/`let`
/// binders, then the module's `imports`, then its own members — `iotas` before
/// items and locals — then the rest of the `frame`, then the builtin module
/// aliases. Anything found in the frame — imports and the outer values alike —
/// becomes an ordinary `Local` whose index walks *past* the module terminal into
/// the frame, so it costs one indexed lookup and evaluates nothing.
///
/// `locals` are the module's `local` declarations: members exactly as the items
/// are — so a body reaches one the same way, and a local's own body is resolved
/// here alongside the items' — differing only in being addressed *after* the
/// items, which is where an outside `M.name` access stops looking. They are
/// sorted here as the bindings are, and the two orders concatenated are the
/// module's id-bearing address space.
///
/// `main` is the module's `__main`, when a source declared one: the **reserved
/// moditem** a runner evaluates. It is resolved here, with the item bodies and
/// against the same tiers, because it is written in the module's own scope. It
/// is not a member, so it claims no index and shifts nothing — the member
/// address space is exactly what it was before a source grew one.
///
/// `imports` names the module's own imports and `frame` whatever the compile was
/// given (a host prelude); together, imports first, they are the frame the module
/// is instantiated against. `iotas` names its `const` declarations, which take no
/// slot: they are members addressed *past* the items and the locals, so an iota's
/// `ModItem` index is `items.len() + locals.len() + its position`. Pass empty
/// slices for a module with none of them.
///
/// **Iotas are looked for before items** for the reason imports are: the
/// re-exporting form `false = const` is one declaration yielding both an iota and
/// an item forwarding it, and a sibling reference wants the iota rather than the
/// item that would evaluate to it.
///
/// **Imports are looked for before items** because of the re-exporting form
/// `Foo = import "spec"`, which is one declaration that yields both a frame slot
/// and an item forwarding it. Searching items first would send every body's `Foo`
/// through the forwarding item, evaluating it to reach the slot the body wanted;
/// finding the slot directly means each reference reads the one instance and the
/// item is left for `M.Foo` from outside. No other name can be both, since
/// `parse_module` rejects an import and an item that share one.
pub fn resolve_module_bodies(
    bindings: &mut [(Text, Expr)],
    locals: &mut [(Text, Expr)],
    main: Option<&mut Expr>,
    imports: &[Text],
    iotas: &[Text],
    frame: &[Text],
) -> Result<(), ParseError> {
    bindings.sort_by(|(a, _), (b, _)| a.as_str().cmp(b.as_str()));
    locals.sort_by(|(a, _), (b, _)| a.as_str().cmp(b.as_str()));
    let members = Barrier::Module {
        items: bindings.iter().map(|(n, _)| n.clone()).collect(),
        locals: locals.iter().map(|(n, _)| n.clone()).collect(),
        iotas: iotas.to_vec(),
    };
    let mut slots: Vec<Text> = imports.to_vec();
    slots.extend_from_slice(frame);
    let bodies = bindings
        .iter_mut()
        .chain(locals.iter_mut())
        .map(|(_, body)| body)
        // The module's own body — `__main`, when a source declared one — is
        // resolved here rather than by a later pass because it is written in the
        // same scope the item bodies are, and reaches the same three tiers.
        .chain(main);
    for body in bodies {
        Resolver::new(slots.clone(), false, alloc::vec![members.clone()])
            .with_imports(imports.len())
            .walk(body)?;
    }
    Ok(())
}

/// Resolve an **open** term: a free name is not rejected but auto-bound below the
/// whole scope, so the pass runs to completion on a fragment. Used by tooling and
/// by the parse golden suite, which resolves open terms (their s-expressions read
/// like the spec) without a rejection — the real index assignment and or-arm
/// agreement still run, and names render by name, so the goldens do not change.
/// Prefer [`resolve`] for a whole program.
pub fn resolve_open(expr: &mut Expr) -> Result<(), ParseError> {
    Resolver::new(Vec::new(), true, Vec::new()).walk(expr)
}

/// Resolve `expr` against a named outer `prelude` (insertion order): a reference
/// to `prelude[i]` becomes the index `i` of the root frame — reached directly at
/// the top level, or through a lambda's capture list from inside one — and any name
/// neither in scope nor in `prelude` is `UnboundName`. Like `resolve_open` but the
/// root frame is fixed and complete (no auto-bind). Used by `elly::parse_preluded`,
/// whose caller supplies the prelude values in that same order.
pub fn resolve_prelude(expr: &mut Expr, prelude: &[Text]) -> Result<(), ParseError> {
    Resolver::new(prelude.to_vec(), false, Vec::new()).walk(expr)
}

/// One lambda activation's compile-time scope: the names its head binds and the
/// frame it captures. The resolver keeps a stack of these, one per enclosing
/// `&`-abstraction, plus a root level standing for the environment the whole term
/// is evaluated in (see the module docs).
struct Level {
    /// The names this activation's head binds, in cons order (most recent last),
    /// one entry per cell the matcher conses. Usually empty for the root level,
    /// but not always: a [`Captures::Chain`] abstraction opens no level, so a
    /// top-level `(&x …) v` binds `x` into the root.
    locals: Vec<Text>,
    /// The free names this lambda captures, in frame-slot order. For the root
    /// level these are the prelude / auto-bound names instead.
    captures: Vec<Text>,
    /// Parallel to `captures`: each capture's index in the **enclosing**
    /// activation's coordinates, i.e. what the closure looks up when it is built.
    /// This is the list stored into [`Lambda::captures`](crate::ast::Lambda) when
    /// the level pops. Unused (and empty) for the root level, which is nobody's
    /// closure.
    outer: Vec<u32>,
}

impl Level {
    fn new() -> Level {
        Level {
            locals: Vec::new(),
            captures: Vec::new(),
            outer: Vec::new(),
        }
    }
}

/// One terminal's **member set**: the names reachable through it, which is what a
/// [`Expr::ModItem`] addresses. A module's parts share one index space — items,
/// then locals, then iotas — so `index` is a member's position in that space,
/// `items.len()` is where the private bindings begin and
/// `items.len() + locals.len()` where the iotas do.
///
/// Each part is name-sorted, so a lookup is three binary searches at most. The
/// order they are searched in is free: the names are disjoint, since a module
/// declares each of them once. Iotas go first for the reason
/// [`resolve_module_bodies`] gives.
///
/// **The two kinds are distinguished here** because a terminal reached by walking
/// out is not always the one a construct means: the home-module leaves —
/// `__module`, `__new`, `__value` — name the nearest terminal *written as a
/// module*, stepping over any group in between, so the stack has to say which of
/// its entries is which. The kind is known at both construction sites and nowhere
/// derivable afterwards: a group has no canonical name, but neither need a module
/// (a host may compile one unnamed), and a group's locals and iotas are empty, but
/// so are an empty module's. See `docs/done/2026-08-15_elly-objects-v0.md`.
#[derive(Clone)]
enum Barrier {
    /// A [`recur`](Expr::Recur) group's bindings. They are members exactly as a
    /// module's items are, and a group may declare neither a local
    /// ([`ParseError::MisplacedLocal`]) nor an iota, so the index space is the
    /// item table alone.
    Group { items: Vec<Text> },
    /// A module's declarations, in the one index space described above.
    Module {
        items: Vec<Text>,
        locals: Vec<Text>,
        iotas: Vec<Text>,
    },
}

impl Barrier {
    /// `name`'s position in the member index space, or `None`.
    fn member(&self, name: &str) -> Option<u32> {
        let (items, locals, iotas) = match self {
            Barrier::Group { items } => return search(items, name),
            Barrier::Module {
                items,
                locals,
                iotas,
            } => (items, locals, iotas),
        };
        if let Some(i) = search(iotas, name) {
            return Some(i + (items.len() + locals.len()) as u32);
        }
        if let Some(i) = search(items, name) {
            return Some(i);
        }
        search(locals, name).map(|i| i + items.len() as u32)
    }

    /// The error a binder taking `name` earns, or `None` if the name is not
    /// declared here — the answer [`check_shadow`](Resolver::check_shadow) reports.
    /// Which of the three it is is the whole reason this is not `member`.
    fn shadow_error(&self, name: &Text) -> Option<ParseError> {
        match self {
            Barrier::Group { items } => {
                search(items, name.as_str()).map(|_| ParseError::ShadowsItem(name.clone()))
            }
            Barrier::Module {
                items,
                locals,
                iotas,
            } => {
                if search(iotas, name.as_str()).is_some() {
                    return Some(ParseError::ShadowsIota(name.clone()));
                }
                if search(items, name.as_str()).is_some() {
                    return Some(ParseError::ShadowsItem(name.clone()));
                }
                search(locals, name.as_str()).map(|_| ParseError::ShadowsLocal(name.clone()))
            }
        }
    }
}

/// `name`'s position in one name-sorted member part, or `None`.
fn search(part: &[Text], name: &str) -> Option<u32> {
    part.binary_search_by(|it| it.as_str().cmp(name))
        .ok()
        .map(|i| i as u32)
}

/// A lexical resolver: a stack of [`Level`]s, innermost last, with `levels[0]` the
/// root. `auto_bind` selects the behaviour on a name unknown at the root — reject
/// it ([`resolve`]) or absorb it into the root frame ([`resolve_open`]).
struct Resolver {
    levels: Vec<Level>,
    auto_bind: bool,
    /// The enclosing **member sets**, outermost first — one per module terminal on
    /// the environment chain: a file module's items and iotas, then one per
    /// enclosing [`recur`](Expr::Recur), each saying which of the two it is.
    /// Together they are the reference tier
    /// between the lexical scope and the root frame, scanned innermost-first so a
    /// nested `recur`'s bindings shadow an outer group's, and the stack distance to
    /// the set that answers is the [`Expr::ModItem`] `depth`. Empty for an ordinary
    /// program outside any module — where a `recur` still pushes a set, so a stack
    /// one deep is not a module by itself.
    ///
    /// The names are cloned in rather than borrowed: the sets live inside the very
    /// tree being rewritten, and a `recur`'s bodies are walked mutably while its
    /// own set is on the stack. A group is small and resolution runs once.
    barriers: Vec<Barrier>,
    /// How many of the root frame's leading slots are the module's own **imports**
    /// — the slots looked for *before* the item sets rather than after them (see
    /// [`resolve_module_bodies`]). Zero everywhere else, which puts the whole root
    /// frame after the items as before.
    imports: usize,
}

/// What a name resolved to: a de Bruijn index into the environment, or a sibling
/// item of the enclosing module. The two are different *kinds* of reference, not
/// two indices — an item is not a value in the environment and costs no capture
/// slot — so [`reference`](Resolver::reference) reports which it found rather than
/// returning an index that the caller would have to interpret.
///
/// [`reference`]: Resolver::reference
enum Ref {
    Local(u32),
    /// An item of an enclosing group: its position in that group's sorted table,
    /// and how many module terminals lie between the reference and the group.
    Item {
        index: u32,
        depth: u32,
    },
    /// A **builtin module** reached through its bare alias (`Int` → `__Int`): the
    /// resolver's bottom tier, below everything a name could be bound to. Like an
    /// `Item` it is not a value in the environment, so it costs no capture slot; it
    /// is a leaf, so it costs nothing at all.
    Builtin(Builtin),
}

impl Resolver {
    /// A resolver whose root frame holds `root` (a prelude, or empty).
    fn new(root: Vec<Text>, auto_bind: bool, barriers: Vec<Barrier>) -> Resolver {
        Resolver {
            levels: alloc::vec![Level {
                locals: Vec::new(),
                captures: root,
                outer: Vec::new(),
            }],
            auto_bind,
            barriers,
            imports: 0,
        }
    }

    /// Mark the first `n` root frame slots as the module's imports, so a name they
    /// hold is found before the item sets are searched.
    fn with_imports(mut self, n: usize) -> Resolver {
        self.imports = n;
        self
    }
    /// The innermost level — the activation a reference resolves against first.
    fn depth(&self) -> usize {
        self.levels.len() - 1
    }

    /// Bind `name`, pushing one cell onto the innermost activation (the matcher
    /// conses one cell to match) — unless it is a **declared** name, which no
    /// binder may take ([`check_shadow`](Self::check_shadow)).
    fn bind(&mut self, name: &Text) -> Result<(), ParseError> {
        self.check_shadow(name)?;
        let li = self.depth();
        self.levels[li].locals.push(name.clone());
        Ok(())
    }

    /// **A declared name is fixed over the whole module.** An import, an iota, an
    /// item and a `local` are declarations, and a declaration's name means one
    /// thing throughout the scope that declares it, so a binder — a pattern
    /// binder, a `let` binding, a `recur` binding alike — may not take one.
    ///
    /// This runs opposite to [`walk_recur`](Self::walk_recur)'s rejection, which
    /// stops a group *binding* from shadowing a name already in scope; here an
    /// outer declaration stops an inner *binder*. Between them a declared name is
    /// unshadowable from either side.
    ///
    /// What a module may still shadow is what it did not declare: the frame names
    /// a host supplied (a prelude) and the bare builtin aliases (`Int`, `Str`) —
    /// both ambient, neither visible in the source as a declaration.
    ///
    /// The cost is the one the `recur` rule already carries, at a wider radius:
    /// legality of a body depends on the module's declarations, so adding an
    /// import or a `const` can break a body that did not change. The trade is that
    /// fixing a local name is a lexically scoped, mechanically checkable rename,
    /// while accidental shadowing is silent and reads as working code. See
    /// `docs/done/2026-08-13_elly-modules-iotas.md`.
    fn check_shadow(&self, name: &Text) -> Result<(), ParseError> {
        // The module's imports: the leading root frame slots (the rest of the
        // frame is the host's, and stays shadowable).
        if self.levels[0].captures[..self.imports]
            .iter()
            .any(|n| n.as_str() == name.as_str())
        {
            return Err(ParseError::ShadowsImport(name.clone()));
        }
        for members in &self.barriers {
            if let Some(err) = members.shadow_error(name) {
                return Err(err);
            }
        }
        Ok(())
    }

    /// Resolve a reference against level `li` and everything enclosing it, to the de
    /// Bruijn index it reads *at that level*: a walk over the cells the level's head
    /// conses, running on into the level's captured frame. A name bound further out
    /// is captured into every level between it and here (see the module docs), which
    /// is what builds the capture lists. At the root a name unknown to the frame is
    /// unbound, or absorbed into it under `auto_bind`.
    ///
    /// A failure leaves no trace: the capture is recorded only once the enclosing
    /// levels have all resolved the name, so an `UnboundName` cannot leave a
    /// half-captured frame behind.
    ///
    /// The module's **items** are searched at the root, after the whole lexical
    /// stack and before the root frame: an item wins over a frame name, matching
    /// the inner-before-outer rule everywhere else. An item reports [`Ref::Item`],
    /// which passes back out through the enclosing levels *without* recording a
    /// capture — an item is resolved at eval through the terminal the environment
    /// carries, so it occupies no frame slot. The module's **imports** are the
    /// leading root frame slots and are searched ahead of the items, for the reason
    /// [`resolve_module_bodies`] gives.
    ///
    /// Scanning every barrier at the root — rather than interleaving each with the
    /// levels it sits between — is sound because a declared name and a bound one
    /// are disjoint: an item may not shadow a name already in scope (see
    /// [`walk_recur`](Self::walk_recur)) and no binder may take a declared one (see
    /// [`check_shadow`](Self::check_shadow)). So a member name is never found in a
    /// level's locals at all, and the order the two tiers are scanned in cannot
    /// change an answer.
    fn reference(&mut self, name: &str, li: usize) -> Result<Ref, ParseError> {
        let lvl = &self.levels[li];
        if let Some(pos) = lvl.locals.iter().rposition(|n| n.as_str() == name) {
            return Ok(Ref::Local((lvl.locals.len() - 1 - pos) as u32));
        }
        if li == 0 {
            // The module's own imports, ahead of its items: a re-exported import
            // is both, and its bodies want the frame slot rather than the item
            // that forwards it (see `resolve_module_bodies`).
            let root = &self.levels[0];
            if let Some(slot) = root.captures[..self.imports]
                .iter()
                .position(|n| n.as_str() == name)
            {
                return Ok(Ref::Local((root.locals.len() + slot) as u32));
            }
            // Innermost group first; the distance back to it is the terminal depth
            // the reference has to walk. Each half is sorted, so a tier is at most
            // two binary searches.
            for (i, members) in self.barriers.iter().enumerate().rev() {
                if let Some(index) = members.member(name) {
                    return Ok(Ref::Item {
                        index,
                        depth: (self.barriers.len() - 1 - i) as u32,
                    });
                }
            }
            // The root frame is reached the same way any level's is: past the
            // cells this level has consed. Those are usually none, but a
            // top-level chain abstraction — `(&x …) v`, i.e. every `let` — binds
            // into the root level rather than opening one of its own.
            let root = &mut self.levels[0];
            if let Some(slot) = root.captures.iter().position(|n| n.as_str() == name) {
                return Ok(Ref::Local((root.locals.len() + slot) as u32));
            }
            // The bottom tier: a builtin module under its bare alias. Consulted
            // after every tier that could *bind* the name — and before the
            // auto-bind, so an open term reads `Int` as the module rather than
            // absorbing it into the root frame.
            if let Some(op) = Builtin::from_alias(name) {
                return Ok(Ref::Builtin(op));
            }
            if !self.auto_bind {
                return Err(ParseError::UnboundName(Text::from(name)));
            }
            let slot = root.captures.len();
            root.captures.push(Text::from(name));
            return Ok(Ref::Local((root.locals.len() + slot) as u32));
        }
        if let Some(slot) = lvl.captures.iter().position(|n| n.as_str() == name) {
            return Ok(Ref::Local((lvl.locals.len() + slot) as u32));
        }
        // Not known here: resolve it one level out, then capture it into this
        // level's frame at a fresh slot.
        let outer = match self.reference(name, li - 1)? {
            leaf @ (Ref::Item { .. } | Ref::Builtin(_)) => return Ok(leaf),
            Ref::Local(outer) => outer,
        };
        let lvl = &mut self.levels[li];
        let slot = lvl.captures.len();
        lvl.captures.push(Text::from(name));
        lvl.outer.push(outer);
        Ok(Ref::Local((lvl.locals.len() + slot) as u32))
    }

    fn walk(&mut self, expr: &mut Expr) -> Result<(), ParseError> {
        match expr {
            // Leaves that reference no name.
            Expr::Int(_) | Expr::Symbol(_) | Expr::Str(_) | Expr::Builtin(_) => Ok(()),
            // A home-module leaf: the depth to its module is the only thing it
            // needs, and it is the same barrier-stack distance a `ModItem`
            // measures — counted from the nearest *module* barrier rather than
            // from the nearest barrier of either kind.
            Expr::Home { leaf, depth } => {
                *depth = Self::home_depth(&self.barriers)
                    .ok_or_else(|| ParseError::OutsideModule(Text::from(leaf.name())))?;
                Ok(())
            }
            // Already resolved: a leaf this pass leaves alone (`ModItem` is produced
            // by the module resolver itself and is likewise resolved). Resolution
            // runs **once** per program and is not idempotent — a second pass sees
            // only `Local`s, finds no free names, and would hand every lambda an
            // empty capture list while its body still indexes a frame.
            Expr::Local { .. } | Expr::ModItem { .. } => Ok(()),
            // Rewrite an in-scope name into a resolved local; the name is kept for
            // rendering, so the s-expressions are unchanged. A name that is not
            // lexically bound but is a sibling module item becomes a `ModItem`
            // (the module tier, consulted only when resolving a module body).
            Expr::Name(n) => {
                let name = n.clone();
                *expr = match self.reference(&name, self.depth())? {
                    Ref::Local(index) => Expr::Local {
                        name: Box::new(name),
                        index,
                    },
                    Ref::Item { index, depth } => Expr::ModItem {
                        name: Box::new(name),
                        index,
                        depth,
                    },
                    Ref::Builtin(op) => Expr::Builtin(op),
                };
                Ok(())
            }
            Expr::List(elems) => {
                for e in elems.iter_mut() {
                    self.walk(e)?;
                }
                Ok(())
            }
            Expr::Map(entries) => {
                for (k, v) in entries.iter_mut() {
                    self.walk(k)?;
                    self.walk(v)?;
                }
                Ok(())
            }
            // A call spine. Two argument shapes hold abstractions that the call
            // *consumes* — they cannot outlive it — so those resolve as
            // [`Captures::Chain`] (see `consumed_by`):
            //
            //  - the callee itself, when it is a literal abstraction: `(&x b) v`,
            //    which is every `let`;
            //  - a literal abstraction handed to a builtin that only applies it (an
            //    `__Err.catch` branch, an `__Int.for` callback), including the
            //    elements of a literal clause list (`__match [&p e, …] x`).
            Expr::App(items) => {
                let callee = &mut items[0];
                match callee {
                    Expr::Abs(code) => self.walk_abs(code, Captures::Chain)?,
                    _ => self.walk(callee)?,
                }
                // `__Int.add x y` — a builtin module applied to a literal member
                // symbol — folds to the member's own leaf, dropping the symbol from
                // the spine, so the written form costs exactly what the old flat
                // `__Int.add` did. The alias spelling (`Int.add`) folds too: the
                // callee walk above has just rewritten `Int` to its module builtin.
                //
                // Before the arguments are walked, because both of the things that
                // depend on the callee's builtin — which arguments it *applies*
                // (`applies_arg`, below) and where those arguments sit — are the
                // member's, not the module's.
                if let (Expr::Builtin(ns), Some(Expr::Symbol(m))) = (&items[0], items.get(1)) {
                    if let Some(op) = ns.member(m) {
                        *expr = fold_member(items, op);
                        return self.walk(expr);
                    }
                }
                let (callee, args) = items.split_first_mut().expect("a call spine has a callee");
                // The callee's builtin, if it is one: what consumes the argument
                // shapes below.
                let consumer = match callee {
                    Expr::Builtin(op) => Some(*op),
                    _ => None,
                };
                for (i, arg) in args.iter_mut().enumerate() {
                    match (consumer, &mut *arg) {
                        (Some(op), Expr::Abs(code)) if op.applies_arg(i) => {
                            self.walk_abs(code, Captures::Chain)?
                        }
                        (Some(op), Expr::List(elems)) if op.applies_elements_of(i) => {
                            for e in elems.iter_mut() {
                                match e {
                                    Expr::Abs(code) => self.walk_abs(code, Captures::Chain)?,
                                    _ => self.walk(e)?,
                                }
                            }
                        }
                        _ => self.walk(arg)?,
                    }
                }
                Ok(())
            }
            // An abstraction reached anywhere else may escape, so it captures.
            Expr::Abs(code) => self.walk_abs(code, Captures::Frame(Box::new([]))),
            Expr::Recur(r) => self.walk_recur(r),
        }
    }

    /// How many terminals a [home-module leaf](crate::HomeLeaf) written here has
    /// to **step over** to reach its module: the barriers are scanned
    /// innermost-first for the nearest one written as a module, and the answer is
    /// the number of groups passed on the way.
    ///
    /// `None` is "outside a module body", and the one test covers both ways of
    /// being outside: a term with no barriers at all, and a `recur` in a program
    /// that is not a module, where every barrier on the stack is a group.
    ///
    /// Written as a search rather than a test on the outermost barrier because
    /// anonymous modules (`docs/todo/elly-modules-anon.md`) will make a module
    /// barrier reachable anywhere on the stack — and because the search says what
    /// the rule *is*.
    fn home_depth(barriers: &[Barrier]) -> Option<u32> {
        barriers
            .iter()
            .rev()
            .position(|b| matches!(b, Barrier::Module { .. }))
            .map(|d| d as u32)
    }

    /// Is `name` reachable from here without binding anything new? A read-only
    /// probe over the lexical stack, the enclosing item sets and the root frame —
    /// it records no capture and never auto-binds, so asking is free of side
    /// effects (unlike [`reference`](Self::reference), which builds capture lists
    /// as it goes).
    fn in_scope(&self, name: &str) -> bool {
        let lexical = self.levels.iter().any(|lvl| {
            lvl.locals.iter().any(|n| n.as_str() == name)
                || lvl.captures.iter().any(|n| n.as_str() == name)
        });
        lexical || self.barriers.iter().any(|m| m.member(name).is_some())
    }

    /// Resolve a [`recur`](Expr::Recur): its group becomes a barrier, its binding
    /// bodies and then its body resolve under it.
    ///
    /// **A binding may not shadow a name already in scope.** `recur`'s bindings are
    /// simultaneous, so inside the group a shadowed name means the group's own
    /// binding, never the outer one — `recur (x = f x) …` under an enclosing `x`
    /// self-references where the identical `let` line reads the outer value. The two
    /// forms would look alike and mean opposite things, so the shadow is refused
    /// ([`ParseError::RecurShadowsOuter`]) rather than silently resolved. The cost
    /// is that legality depends on the whole enclosing scope: a new import or
    /// prelude name can break an inner `recur` that did not change.
    ///
    /// The reverse direction is refused too, by the rule covering every binder:
    /// a binder *inside* the group may not take a binding's name either (see
    /// [`check_shadow`](Self::check_shadow)). Together the two make a group's
    /// names mean one thing throughout it.
    ///
    /// No level is pushed. A barrier is not an activation — nothing is bound by
    /// crossing the terminal and nothing is captured through it, so the group's
    /// bodies keep counting into the enclosing level's chain and land on the same
    /// indices they would have had inline at the `recur` site.
    fn walk_recur(&mut self, group: &mut Rc<ModuleData>) -> Result<(), ParseError> {
        let names: Vec<Text> = group.items().iter().map(|(n, _)| n.clone()).collect();
        for name in &names {
            if self.in_scope(name) {
                return Err(ParseError::RecurShadowsOuter(name.clone()));
            }
        }
        self.barriers.push(Barrier::Group { items: names });
        let data = Rc::get_mut(group).expect("the group is uniquely owned at resolve time");
        for (_, body) in data.items_mut() {
            self.walk(body)?;
        }
        // The bindings are walked before the body, matching the order the evaluator
        // binds in: a chain abstraction in the body extends this level's locals, and
        // must not be visible to the bodies that precede it.
        let body = data.body_mut().expect("a recur group always has a body");
        self.walk(body)?;
        // An error aborts the whole pass (the resolver is dropped with it), so the
        // stack need not be unwound on the way out.
        self.barriers.pop();
        Ok(())
    }

    /// Resolve an abstraction, `how` selecting the environment its closures get.
    ///
    /// [`Captures::Frame`] opens a **new activation level** for the head's
    /// parameters: resolve each parameter in binding order (so a later parameter's
    /// embedded expression sees the earlier ones), then the body; popping the level
    /// yields the free variables the walk found, in frame-slot order and addressed in
    /// the *enclosing* activation's coordinates — the plan the evaluator reads to
    /// build the frame. (The plan passed in is ignored; only the variant selects.)
    ///
    /// [`Captures::Chain`] opens **no** level: the head's binders extend the
    /// enclosing activation, and the body's references keep counting into its chain —
    /// exactly what the evaluator does when it conses this closure's arguments onto
    /// the environment it shares. Nothing is captured, so nothing is copied.
    fn walk_abs(&mut self, code: &mut Rc<Lambda>, how: Captures) -> Result<(), ParseError> {
        let lam = Rc::get_mut(code).expect("the lambda is uniquely owned at resolve time");
        if let Captures::Chain = how {
            let li = self.depth();
            let base = self.levels[li].locals.len();
            for pat in lam.head.iter_mut() {
                self.walk_pattern(pat)?;
            }
            self.walk(&mut lam.body)?;
            self.levels[li].locals.truncate(base);
            lam.captures = Captures::Chain;
            return Ok(());
        }
        self.levels.push(Level::new());
        for pat in lam.head.iter_mut() {
            self.walk_pattern(pat)?;
        }
        // An error aborts the whole pass (the resolver is dropped with it), so the
        // level stack need not be unwound on the way out.
        self.walk(&mut lam.body)?;
        let level = self.levels.pop().expect("the level just pushed");
        lam.captures = Captures::Frame(Self::capture_plan(&level.outer));
        Ok(())
    }

    /// Turn a finished level's captures into the lambda's frame-building plan:
    /// `outer[slot]` is where slot `slot` reads from, and the plan is **sorted by
    /// `outer`** so the evaluator fills the frame in one ascending walk of the
    /// defining environment. The outer indices are distinct (a name is captured into
    /// a level at most once), so the order is total and the sort deterministic.
    fn capture_plan(outer: &[u32]) -> Box<[Capture]> {
        let mut plan: Vec<Capture> = outer
            .iter()
            .enumerate()
            .map(|(slot, &outer)| Capture {
                outer,
                slot: slot as u32,
            })
            .collect();
        plan.sort_unstable_by_key(|c| c.outer);
        plan.into_boxed_slice()
    }

    /// Resolve a pattern: push its binders (assigning their de Bruijn positions)
    /// and resolve its embedded expressions, in the exact order the evaluator's
    /// matcher conses.
    fn walk_pattern(&mut self, pat: &mut Pattern) -> Result<(), ParseError> {
        match pat {
            Pattern::Discard => Ok(()),
            Pattern::Bind(name) => self.bind(name),
            // `name = <pat>` conses the name before matching the inner pattern.
            Pattern::At(name, inner) => {
                self.bind(name)?;
                self.walk_pattern(inner)
            }
            // Comparands see the bindings made before them (no new binding).
            Pattern::Equal(e) | Pattern::Less(e) | Pattern::Greater(e) => self.walk(e),
            // `<pat> as <Proto>` narrows, then matches the inner pattern. The
            // prototype reference is resolved **before** the inner pattern, the
            // order an `= <ref>` comparand uses and for the same reason: it sees
            // only the bindings made before it.
            //
            // A reference that lands on a builtin module is folded to the
            // compiled form here, where both spellings have arrived — the written
            // `__Int` from parse, and the alias `Int` from the walk just above.
            Pattern::Type(proto, inner) => {
                if let ProtoRef::Ref(expr) = proto {
                    self.walk(expr)?;
                    if let Expr::Builtin(op) = expr {
                        match op.proto_kind() {
                            Some(kind) => *proto = ProtoRef::Kind(kind),
                            None => return Err(ParseError::NotAPrototype(Text::from(op.name()))),
                        }
                    }
                }
                self.walk_pattern(inner)
            }
            // `__value <pat>` takes the same depth the leaf does, and holds no
            // reference of its own — the module is implicit.
            Pattern::Unwrap { depth, inner } => {
                *depth = Self::home_depth(&self.barriers)
                    .ok_or_else(|| ParseError::OutsideModule(Text::from("__value")))?;
                self.walk_pattern(inner)
            }
            // Both arms must cons the same binding sequence — same names, same
            // order — so a later reference reads one fixed index whichever arm
            // matched. Walk the left arm, capture the names it pushed, reset, walk
            // the right arm, and require the sequences to be equal.
            Pattern::Or(left, right) => {
                let li = self.depth();
                let base = self.levels[li].locals.len();
                self.walk_pattern(left)?;
                let left_names: Vec<Text> = self.levels[li].locals[base..].to_vec();
                self.levels[li].locals.truncate(base);
                self.walk_pattern(right)?;
                if self.levels[li].locals[base..] != left_names[..] {
                    return Err(ParseError::OrBindersMismatch);
                }
                Ok(())
            }
            // A list pattern conses its rest first, then its elements left to right.
            Pattern::List(elems, rest) => {
                if let Rest::Named(name) = rest {
                    self.bind(name)?;
                }
                for e in elems.iter_mut() {
                    self.walk_pattern(e)?;
                }
                Ok(())
            }
            // A map pattern evaluates every lookup key first (in the scope before
            // any of this pattern's bindings), then matches lookup value patterns,
            // then captures (key then value), then conses a named rest last.
            Pattern::Map(entries, rest) => {
                for (key, _) in entries.iter_mut() {
                    if let MapKey::Lookup(ke) = key {
                        self.walk(ke)?;
                    }
                }
                for (key, vpat) in entries.iter_mut() {
                    if let MapKey::Lookup(_) = key {
                        self.walk_pattern(vpat)?;
                    }
                }
                for (key, vpat) in entries.iter_mut() {
                    if let MapKey::Capture(kpat) = key {
                        self.walk_pattern(kpat)?;
                        self.walk_pattern(vpat)?;
                    }
                }
                if let Rest::Named(name) = rest {
                    self.bind(name)?;
                }
                Ok(())
            }
        }
    }
}