Skip to main content

elly_core/eval/
mod.rs

1//! Naive tree-walking evaluator for the first Elly subset.
2//!
3//! Uses call-by-value evaluation. Environments are persistent linked lists of
4//! bindings shared via `Rc` for efficient closure capture. The tree it walks is
5//! a [`StaticChunk`](crate::code::StaticChunk): every node is read by its id
6//! through the realm's chunk table, and the chunk being run is passed along as
7//! `at`, the current-chunk register.
8//!
9//! What runs lives here, with the values and environments it builds: the
10//! environment chain (`env`), pattern matching (`patmatch`), running the
11//! builtins (`builtin`), and raised errors with what they leave as they
12//! unwind (`error`). The static surface of the language (code, parsing,
13//! modules, sources) is outside `eval/`.
14
15pub(crate) mod builtin;
16pub(crate) mod env;
17#[cfg(feature = "stats-env")]
18pub mod env_stats;
19pub(crate) mod error;
20pub(crate) mod iter;
21mod patmatch;
22
23use alloc::boxed::Box;
24use alloc::rc::Rc;
25use alloc::vec::Vec;
26
27use rpds::{HashTrieMap, Vector};
28
29use crate::code::{ChunkId, LambdaId, ModId, Node, NodeId, Pat, PatId, Plan, Run};
30
31use crate::builtins::Builtin;
32use crate::eval::env::{Env, EnvNode, EnvRef};
33use crate::eval::error::Raised;
34use crate::eval::patmatch::{match_pat, match_pattern};
35use crate::sym::{Projection, Sym};
36use crate::value::Value;
37use crate::Ctx;
38
39// ---------------------------------------------------------------------------
40// The realm's run-time state
41// ---------------------------------------------------------------------------
42
43impl Ctx {
44    /// Mints the next unique id for a closure's identity, used for equality
45    /// and ordering.
46    pub(crate) fn next_id(&self) -> u64 {
47        let n = self.ids.get();
48        self.ids.set(n + 1);
49        n
50    }
51
52    /// Reserves a block of `n` consecutive ids and returns the base. Used by
53    /// [`instantiate`] to give module items stable identities, preventing alias
54    /// with individually minted ids.
55    pub(crate) fn reserve_ids(&self, n: u64) -> u64 {
56        let base = self.ids.get();
57        self.ids.set(base + n);
58        base
59    }
60
61    /// Gets a builtin module (`__Int`, `__Map`, etc.), instantiated on first
62    /// reference and cached.
63    ///
64    /// Builtin modules live in the [`ELLY`](ChunkId::ELLY) chunk, with builtin
65    /// leaves as item bodies. A written `__Int.add` is folded to its member at
66    /// resolve, but this method handles remaining dynamic uses of the module as
67    /// a value.
68    pub(crate) fn builtin_module(&self, op: Builtin) -> Value {
69        let slot = op.module_slot().expect("a builtin module");
70        self.modules[slot]
71            .get_or_init(|| {
72                instantiate_module(ChunkId::ELLY, ModId::builtin(slot), &[], self)
73                    .expect("a builtin module has no frame")
74            })
75            .clone()
76    }
77}
78
79/// Evaluates the `__main` body of a module instance in its own environment.
80/// Returns `Ok(None)` if no body is declared (e.g., a library).
81///
82/// This implements "runnable" module semantics: [`crate::load_module`] instantiates
83/// modules without evaluating their bodies, ensuring `__main` is only executed
84/// when explicitly targeted by a runner.
85///
86/// The body executes in the instance's [`Module`](EnvNode::Module) terminal.
87/// As it is not a member, it has no reserved ID. Non-module instances raise
88/// `.not_a_module`. Result interpretation is handled by the runner; see
89/// `docs/done/2026-08-14_elly-run.md`.
90pub fn eval_main(instance: &Value, ctx: &Ctx) -> Result<Option<Value>, Raised> {
91    let Value::Module(home) = instance else {
92        return Err(Raised::symbol(Sym::NOT_A_MODULE));
93    };
94    let EnvNode::Module { chunk, module, .. } = **home else {
95        unreachable!("a module value always holds a module terminal")
96    };
97    let body = ctx.chunk(chunk).module(module).body;
98    let Some(body) = body.get() else {
99        return Ok(None);
100    };
101    ctx.clear_unwind();
102    let result = eval(chunk, body, &Env::from_ref(home.clone()), ctx)?;
103    Ok(Some(result))
104}
105
106/// Runs a block chunk parsed in the scope of `instance` (see
107/// [`Ctx::parse_block_in_module`]) in its environment, as [`eval_main`] runs
108/// the module's own `__main`, with `args` the values of its binders in order.
109/// Non-module instances raise `.not_a_module`.
110pub fn eval_in_module(
111    chunk: ChunkId,
112    instance: &Value,
113    args: &[Value],
114    ctx: &Ctx,
115) -> Result<Value, Raised> {
116    let Value::Module(home) = instance else {
117        return Err(Raised::symbol(Sym::NOT_A_MODULE));
118    };
119    let body = {
120        let code = ctx.chunk(chunk);
121        code.module(code.top()).body
122    };
123    let env = args.iter().fold(Env::from_ref(home.clone()), |env, arg| {
124        env.bind(arg.clone())
125    });
126    ctx.clear_unwind();
127    eval(chunk, body, &env, ctx)
128}
129
130/// Apply a value to a single argument in the realm `ctx` — the public entry
131/// point behind a host's "call this value" surface (e.g. the Python bindings'
132/// `elly.Fun.__call__`).
133///
134/// This is the same application step the evaluator uses internally (`apply_n`
135/// with one argument): a closure call, list projection, or one step toward
136/// saturating a builtin. `f` and `arg` must belong to `ctx`; closures minted by
137/// the call continue its id source.
138pub fn apply_with(f: &Value, arg: Value, ctx: &Ctx) -> Result<Value, Raised> {
139    ctx.clear_unwind();
140    apply1(f.clone(), arg, ctx)
141}
142
143/// Runs an expression chunk (see [`Ctx::parse`]) in `env`: its top module's
144/// body, with no module terminal around it. Public entry point for host
145/// evaluation (e.g., `elly.Env.eval`).
146pub fn eval_env(chunk: ChunkId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
147    let body = {
148        let code = ctx.chunk(chunk);
149        let top = code.module(code.top());
150        assert!(
151            top.members.len == 0 && top.frame.len == 0,
152            "only an expression chunk runs on its own"
153        );
154        top.body
155    };
156    ctx.clear_unwind();
157    eval(chunk, body, env, ctx)
158}
159
160/// Evaluates node `id` of chunk `at` in `env`.
161pub(crate) fn eval(at: ChunkId, id: NodeId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
162    match ctx.node(at, id) {
163        // Resolved reference: look up value by index.
164        Node::Local { index, .. } => Ok(env.lookup(index)),
165        // Module sibling reference (see [`mod_item`]).
166        Node::ModItem { index, depth, .. } => mod_item(env, index, depth, ctx),
167        // Home-module leaf (see [`home_leaf`]).
168        Node::Home { leaf, depth } => env.home_leaf(leaf, depth),
169        // Recursive binding group (see [`recur`]).
170        Node::Recur(group) => recur(at, group, env, ctx),
171        // Block evaluation (see [`eval_block`]). Outlined to optimize I-cache.
172        Node::Block { len, binds, exprs } => eval_block(at, len, binds, exprs, env, ctx),
173        // Builtin operation. 0-arity builtins execute immediately; others return
174        // a `Builtin` awaiting arguments.
175        Node::Builtin(op) => {
176            if op.arity() == 0 {
177                builtin::invoke(op, &[], ctx)
178            } else {
179                // Avoid `with_capacity` to prevent unnecessary allocations during
180                // curried application cloning.
181                Ok(Value::Builtin {
182                    op,
183                    args: Vec::new(),
184                })
185            }
186        }
187        Node::Int(n) => Ok(Value::I64(n)),
188        // A chunk keeps only the integers that do not fit `i64` as big ones.
189        Node::BigInt(n) => Ok(Value::BigInt(Rc::new(ctx.chunk(at).int(n).clone()))),
190        Node::Symbol(s) => Ok(Value::Symbol(s)),
191        // String handles are shared and pre-decoded.
192        Node::Str(s) => Ok(Value::Str(ctx.chunk(at).str(s).clone())),
193        Node::Unit => Ok(Value::Unit),
194        Node::List { len, elems } => {
195            ctx.check_run(at, Run::List, elems, len);
196            let mut vs = Vector::new();
197            for i in 0..len {
198                let elem = eval(at, elems.nth(i), env, ctx)?;
199                vs.push_back_mut(elem);
200            }
201            Ok(Value::List(vs))
202        }
203        // Map literal: evaluate keys and values in source order. Later entries
204        // with the same key overwrite previous ones.
205        Node::Map { len, entries } => {
206            ctx.check_run(at, Run::Map, entries, 2 * len);
207            let mut m = HashTrieMap::new();
208            for i in 0..len {
209                let kv = eval(at, entries.nth(i), env, ctx)?;
210                let vv = eval(at, entries.nth(len + i), env, ctx)?;
211                m.insert_mut(kv, vv);
212            }
213            Ok(Value::Map(m))
214        }
215        // Closure creation: captures free variables according to the resolution plan.
216        Node::Abs(code) => Ok(closure(at, code, ctx.next_id(), env, ctx)),
217        // Call-by-value application. Callee and arguments are evaluated strictly
218        // left-to-right. Small arities (≤ 4) are handled on the stack to avoid
219        // heap allocation for the argument buffer.
220        Node::App { len, args } => {
221            ctx.check_run(at, Run::App, args, len);
222            let callee = eval(at, args, env, ctx)?;
223            // The call passes itself down as the site an error from the call
224            // itself, not from evaluating its operands, unwinds through: the
225            // callee records it, so that this stays a tail call.
226            match len - 1 {
227                1 => {
228                    let arg = eval(at, args.nth(1), env, ctx)?;
229                    apply1_at(callee, arg, at, id, ctx)
230                }
231                2 => {
232                    let va = eval(at, args.nth(1), env, ctx)?;
233                    let vb = eval(at, args.nth(2), env, ctx)?;
234                    apply_n_at(callee, &[va, vb], at, id, ctx)
235                }
236                3 => {
237                    let va = eval(at, args.nth(1), env, ctx)?;
238                    let vb = eval(at, args.nth(2), env, ctx)?;
239                    let vc = eval(at, args.nth(3), env, ctx)?;
240                    apply_n_at(callee, &[va, vb, vc], at, id, ctx)
241                }
242                4 => {
243                    let va = eval(at, args.nth(1), env, ctx)?;
244                    let vb = eval(at, args.nth(2), env, ctx)?;
245                    let vc = eval(at, args.nth(3), env, ctx)?;
246                    let vd = eval(at, args.nth(4), env, ctx)?;
247                    apply_n_at(callee, &[va, vb, vc, vd], at, id, ctx)
248                }
249                n => {
250                    let mut argv: Vec<Value> = Vec::with_capacity(n as usize);
251                    for i in 1..len {
252                        argv.push(eval(at, args.nth(i), env, ctx)?);
253                    }
254                    apply_n_at(callee, &argv, at, id, ctx)
255                }
256            }
257        }
258        // Subject is evaluated once, then arms are tried in order. It comes
259        // after the arm bodies in the run.
260        Node::Case { len, conds, exprs } => {
261            ctx.check_run(at, Run::Case, exprs, len + 1);
262            let subj = eval(at, exprs.nth(len), env, ctx)?;
263            run_arms(at, &subj, len, conds, exprs, env, ctx)
264        }
265        #[cfg(debug_assertions)]
266        Node::Barrier { .. } => unreachable!("a barrier is not an operand"),
267    }
268}
269
270/// A closure over lambda `code` of chunk `at`, with identity `id`: captures
271/// free variables according to the resolution plan. `Plan::Chain` shares the
272/// environment; `Plan::Frame` creates a new frame.
273#[inline]
274fn closure(at: ChunkId, code: LambdaId, id: u64, env: &Env, ctx: &Ctx) -> Value {
275    let lambda = ctx.lambda(at, code);
276    let env = match lambda.captures {
277        Plan::Chain => env.clone(),
278        // Capturing clones values and allocates cells but runs no code, so it
279        // cannot add a chunk while the plan is borrowed.
280        Plan::Frame(plan) => env.capture_env(ctx.chunk(at).captures(plan), ctx),
281    };
282    Value::Closure {
283        id,
284        chunk: at,
285        lambda: code,
286        applied: 0,
287        arity: lambda.head.len as u8,
288        env,
289    }
290}
291
292/// Tries case arms in order. `NoMatch` refutations fall through; other errors propagate.
293/// If no arms match, `.no_match` is raised.
294#[inline(never)]
295fn run_arms(
296    at: ChunkId,
297    subj: &Value,
298    len: u32,
299    conds: PatId,
300    bodies: NodeId,
301    env: &Env,
302    ctx: &Ctx,
303) -> Result<Value, Raised> {
304    ctx.check_pat_run(at, Run::Case, conds, len);
305    for i in 0..len {
306        match match_pattern(at, conds.nth(i), subj, env.clone(), ctx) {
307            // Not released explicitly: only 0.05% of node deaths happen here, and
308            // holding the result across a release grows this recursive frame.
309            Ok(arm_env) => {
310                // What the arms before this one refuted explains nothing now.
311                if i > 0 {
312                    ctx.caught();
313                }
314                return eval(at, bodies.nth(i), &arm_env, ctx);
315            }
316            Err(Raised::NoMatch(_)) => ctx.caught(),
317            Err(e) => return Err(e),
318        }
319    }
320    Err(ctx.no_arm_matched(at, bodies.nth(len), subj))
321}
322
323/// Specialized path for single-argument application. Used by the call spine,
324/// fold builtins, and match clauses. Binds one parameter, produces a partial
325/// closure, gathers a builtin argument, or projects a list.
326#[inline(always)]
327pub(crate) fn apply1(fv: Value, av: Value, ctx: &Ctx) -> Result<Value, Raised> {
328    apply1_at(fv, av, ChunkId::NONE, NodeId::NONE, ctx)
329}
330
331/// [`apply1`] for application node `call` of chunk `at`, which an error from
332/// the call unwinds through, or [`NodeId::NONE`] for an application with no
333/// node, such as a builtin's callback.
334fn apply1_at(fv: Value, av: Value, at: ChunkId, call: NodeId, ctx: &Ctx) -> Result<Value, Raised> {
335    match fv {
336        Value::Closure {
337            chunk,
338            lambda,
339            applied,
340            arity,
341            env,
342            ..
343        } => {
344            let code = ctx.lambda(chunk, lambda);
345            ctx.check_pat_run(chunk, Run::Head, code.head.first, code.head.len);
346            // Bind argument and extend environment.
347            let pat = code.head.first.nth(u32::from(applied));
348            let call_env = match match_pattern(chunk, pat, &av, env, ctx) {
349                Ok(env) => env,
350                Err(r) => {
351                    let pat = code.head.first.nth(u32::from(applied));
352                    return Err(unbound(r, chunk, pat, &av, at, call, ctx));
353                }
354            };
355            if applied + 1 < arity {
356                // Return partial closure with updated applied count and environment.
357                return Ok(Value::Closure {
358                    id: ctx.next_id(),
359                    chunk,
360                    lambda,
361                    applied: applied + 1,
362                    arity,
363                    env: call_env,
364                });
365            }
366            let result = eval(chunk, code.body, &call_env, ctx);
367            ctx.release(call_env);
368            traced(result, at, call, ctx)
369        }
370        Value::Builtin {
371            op,
372            args: mut gathered,
373        } => {
374            // Unary builtins saturate from the stack.
375            if gathered.is_empty() && op.arity() == 1 {
376                return traced(builtin::invoke(op, &[av], ctx), at, call, ctx);
377            }
378            gathered.push(av);
379            if gathered.len() == op.arity() {
380                traced(builtin::invoke(op, &gathered, ctx), at, call, ctx)
381            } else {
382                Ok(Value::Builtin { op, args: gathered })
383            }
384        }
385        Value::HostFn {
386            code,
387            args: gathered,
388        } => {
389            if gathered.is_empty() && code.arity == 1 {
390                return traced((code.f)(&[av], ctx), at, call, ctx);
391            }
392            let gathered = extended(&gathered, &[av]);
393            if gathered.len() == code.arity {
394                traced((code.f)(&gathered, ctx), at, call, ctx)
395            } else {
396                Ok(Value::HostFn {
397                    code,
398                    args: gathered,
399                })
400            }
401        }
402        // Materialize item when a module is applied to a symbol.
403        Value::Module(home) => {
404            let result = match av {
405                Value::Symbol(s) => materialize(&Env::from_ref(home), s, ctx),
406                _ => Err(Raised::symbol(Sym::NOT_APPLICABLE)),
407            };
408            traced(result, at, call, ctx)
409        }
410        // Dispatch via prototype for all other types.
411        fv => traced(receiver(fv, &av, &[], ctx), at, call, ctx),
412    }
413}
414
415/// The error from matching `arg` against parameter `pat` of chunk `chunk`,
416/// recorded as unwinding through application node `call` of chunk `at`. A
417/// refutation escapes the parameter there, and says so if the call has a
418/// node: a builtin applying a callback, as `__match` does its clauses, may
419/// catch it.
420#[cold]
421#[inline(never)]
422fn unbound(
423    raised: Raised,
424    chunk: ChunkId,
425    pat: PatId,
426    arg: &Value,
427    at: ChunkId,
428    call: NodeId,
429    ctx: &Ctx,
430) -> Raised {
431    if call == NodeId::NONE {
432        return raised;
433    }
434    ctx.unwound(&raised, at, call);
435    ctx.escaped(raised, chunk, pat, arg)
436}
437
438/// `result`, recording an error as unwinding through application node `call`
439/// of chunk `at`.
440#[inline(always)]
441fn traced(
442    result: Result<Value, Raised>,
443    at: ChunkId,
444    call: NodeId,
445    ctx: &Ctx,
446) -> Result<Value, Raised> {
447    if let Err(raised) = &result {
448        ctx.unwound(raised, at, call);
449    }
450    result
451}
452
453/// Applies a value to multiple arguments. Handles closures (multi-parameter
454/// matching), builtins (gather until saturation), and list projections.
455/// Over-application results loop onto the returned value.
456///
457/// Arguments are evaluated strictly left-to-right before matching patterns
458/// left-to-right, ensuring evaluation errors surface before pattern refutations.
459/// See `docs/done/2026-08-02_perf-less-currying.md` §3.
460#[inline(always)]
461fn apply_n(fv: Value, args: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
462    apply_n_at(fv, args, ChunkId::NONE, NodeId::NONE, ctx)
463}
464
465/// [`apply_n`] for application node `call` of chunk `at` (see
466/// [`apply1_at`]).
467fn apply_n_at(
468    mut fv: Value,
469    mut args: &[Value],
470    at: ChunkId,
471    call: NodeId,
472    ctx: &Ctx,
473) -> Result<Value, Raised> {
474    while !args.is_empty() {
475        match fv {
476            // Matches arguments against remaining patterns left-to-right.
477            // If arguments are exhausted, returns a partial closure with a fresh ID.
478            // Otherwise, executes the body and loops leftover arguments onto the result.
479            // Pattern misses raise `NoMatch`.
480            Value::Closure {
481                chunk,
482                lambda,
483                applied,
484                arity,
485                env,
486                ..
487            } => {
488                let code = ctx.lambda(chunk, lambda);
489                ctx.check_pat_run(chunk, Run::Head, code.head.first, code.head.len);
490                let remaining = usize::from(arity - applied);
491                let take = remaining.min(args.len());
492                // Thread the env through each parameter match, consing bindings
493                // onto the closure's captured (or partially-applied) env.
494                let mut call_env = env;
495                let first = code.head.first.nth(u32::from(applied));
496                for (i, arg) in args[..take].iter().enumerate() {
497                    let matched = match_pattern(chunk, first.nth(i as u32), arg, call_env, ctx);
498                    call_env = match matched {
499                        Ok(env) => env,
500                        Err(r) => {
501                            let pat = first.nth(i as u32);
502                            return Err(unbound(r, chunk, pat, arg, at, call, ctx));
503                        }
504                    };
505                }
506                if take < remaining {
507                    // Partial: no body runs yet; mint a fresh identity.
508                    return Ok(Value::Closure {
509                        id: ctx.next_id(),
510                        chunk,
511                        lambda,
512                        applied: applied + take as u8,
513                        arity,
514                        env: call_env,
515                    });
516                }
517                let result = eval(chunk, code.body, &call_env, ctx);
518                ctx.release(call_env);
519                fv = traced(result, at, call, ctx)?;
520                args = &args[take..];
521            }
522            // Gathers arguments and invokes once saturated, looping leftovers onto the result.
523            // If the argument spine satisfies the arity immediately, it invokes directly
524            // from the slice to avoid `Value::Builtin` allocation.
525            Value::Builtin {
526                op,
527                args: mut gathered,
528            } => {
529                let arity = op.arity();
530                if gathered.is_empty() && args.len() >= arity {
531                    fv = traced(builtin::invoke(op, &args[..arity], ctx), at, call, ctx)?;
532                    args = &args[arity..];
533                } else {
534                    let take = (arity - gathered.len()).min(args.len());
535                    gathered.extend(args[..take].iter().cloned());
536                    if gathered.len() < arity {
537                        return Ok(Value::Builtin { op, args: gathered });
538                    }
539                    fv = traced(builtin::invoke(op, &gathered, ctx), at, call, ctx)?;
540                    args = &args[take..];
541                }
542            }
543            // Similar gather-and-fire loop as builtins, dispatching via the host callback.
544            Value::HostFn {
545                code,
546                args: gathered,
547            } => {
548                let arity = code.arity;
549                if gathered.is_empty() && args.len() >= arity {
550                    fv = traced((code.f)(&args[..arity], ctx), at, call, ctx)?;
551                    args = &args[arity..];
552                } else {
553                    let take = (arity - gathered.len()).min(args.len());
554                    let gathered = extended(&gathered, &args[..take]);
555                    if gathered.len() < arity {
556                        return Ok(Value::HostFn {
557                            code,
558                            args: gathered,
559                        });
560                    }
561                    fv = traced((code.f)(&gathered, ctx), at, call, ctx)?;
562                    args = &args[take..];
563                }
564            }
565            // Materializes an item when applied to a symbol; leftovers loop onto the result.
566            Value::Module(home) => {
567                let result = match &args[0] {
568                    Value::Symbol(s) => materialize(&Env::from_ref(home), *s, ctx),
569                    _ => Err(Raised::symbol(Sym::NOT_APPLICABLE)),
570                };
571                fv = traced(result, at, call, ctx)?;
572                args = &args[1..];
573            }
574            // Dispatches by passing the entire remaining argument spine to the
575            // method in one call (see [`receiver`]).
576            fv => return traced(receiver(fv, &args[0], &args[1..], ctx), at, call, ctx),
577        }
578    }
579    Ok(fv)
580}
581
582/// Concatenates `prefix` and `more` into a single allocation.
583/// Used by [`Value::HostFn`] for efficient argument gathering during partial application.
584fn extended(prefix: &[Value], more: &[Value]) -> Box<[Value]> {
585    let mut all = Vec::with_capacity(prefix.len() + more.len());
586    all.extend_from_slice(prefix);
587    all.extend_from_slice(more);
588    all.into_boxed_slice()
589}
590
591/// Returns the prototype of a value. Objects use their own prototype; others
592/// use the corresponding builtin module, providing a nominal type for all values.
593///
594/// Iotas resolve to their declaring module, allowing them to be treated as
595/// objects of that module. Callables (closures, builtins, host functions)
596/// resolve to `__Fun`.
597pub(crate) fn proto_of(v: &Value, ctx: &Ctx) -> Value {
598    match v {
599        Value::Object(obj) => obj.proto(),
600        Value::Iota { home, .. } => Value::Module(home.clone()),
601        Value::I64(_) | Value::BigInt(_) => ctx.builtin_module(Builtin::Int),
602        Value::Symbol(_) => ctx.builtin_module(Builtin::Sym),
603        Value::Str(_) => ctx.builtin_module(Builtin::Str),
604        Value::Unit => ctx.builtin_module(Builtin::Unit),
605        Value::List(_) => ctx.builtin_module(Builtin::List),
606        Value::Map(_) => ctx.builtin_module(Builtin::Map),
607        Value::Closure { .. } | Value::Builtin { .. } | Value::HostFn { .. } => {
608            ctx.builtin_module(Builtin::Fun)
609        }
610        Value::Module(_) => ctx.builtin_module(Builtin::Mod),
611        Value::Iter(_) => ctx.builtin_module(Builtin::Iter),
612    }
613}
614
615/// Whether `value`'s prototype is the module node `expr` of chunk `at` names —
616/// the general form of an
617/// `as <Proto>` pattern, where [`ProtoRef::Kind`] is the compiled one. A reference
618/// that is not a module raises `.not_a_module`: it is a mistake about the pattern
619/// rather than about the subject, so it is a real error and not a refutation.
620///
621/// Outlined for the reason [`receiver`] is: `match_pattern` is on every call's
622/// path, and its arms pay for each other's code size.
623#[inline(never)]
624pub(crate) fn proto_is(
625    at: ChunkId,
626    expr: NodeId,
627    value: &Value,
628    env: &Env,
629    ctx: &Ctx,
630) -> Result<bool, Raised> {
631    let expected = eval(at, expr, env, ctx)?;
632    if !matches!(expected, Value::Module(_)) {
633        return Err(Raised::symbol(Sym::NOT_A_MODULE));
634    }
635    Ok(proto_of(value, ctx) == expected)
636}
637
638/// Resolves a module sibling reference by walking to the home module and
639/// materializing the item at `index`.
640///
641/// The index is assigned during resolution against the module's sorted table,
642/// enabling direct slice access. Only module-item bodies contain `ModItem`,
643/// and they always run under a `Module` home terminal, which is found by
644/// walking through captured frames.
645///
646/// Outlined to maintain I-cache residency of `eval_env`.
647///
648/// If the index is past the item table, it is treated as an iota, which is
649/// derived as a pair of the terminal and position.
650///
651/// `depth` specifies how many terminals to skip to find the owning module.
652/// A `recur` group nested in a module body adds a terminal to the chain, requiring
653/// a skip for the enclosing module's items.
654#[inline(never)]
655fn mod_item(env: &Env, index: u32, depth: u32, ctx: &Ctx) -> Result<Value, Raised> {
656    let (env, home, (chunk, module, id_base)) = env
657        .find_module(depth)
658        .ok_or_else(|| Raised::symbol(Sym::NO_MODULE))?;
659    let member = ctx.chunk(chunk).member(module, index);
660    let Some(member) = member else {
661        // Handle iotas: derived from terminal identity and index.
662        let code = ctx.chunk(chunk);
663        let index = index - code.member_len(module);
664        if code.iota(module, index).is_none() {
665            return Err(Raised::symbol(Sym::MISSING_PROPERTY));
666        }
667        return Ok(Value::Iota {
668            home: home.clone(),
669            index,
670        });
671    };
672    materialize_body(chunk, member.node, env, id_base, index, ctx)
673}
674
675/// Evaluates a `recur` group by creating a `Module` terminal over the
676/// current environment and executing the body.
677///
678/// This is instantiation with a cons-shaped frame, avoiding copies by
679/// sharing the lexical environment. ID blocks are reserved per evaluation,
680/// ensuring different activations of the same `recur` group have distinct
681/// item identities. Bindings are materialized on reference.
682#[inline(never)]
683fn recur(at: ChunkId, group: ModId, env: &Env, ctx: &Ctx) -> Result<Value, Raised> {
684    let (len, body) = {
685        let code = ctx.chunk(at);
686        (code.member_len(group), code.module(group).body)
687    };
688    let home = EnvRef::new(EnvNode::Module {
689        chunk: at,
690        module: group,
691        id_base: ctx.reserve_ids(u64::from(len)),
692        frame: env.clone(),
693    });
694    eval(at, body, &Env::from_ref(home), ctx)
695}
696
697/// Evaluates a block by threading the environment through clauses.
698/// Bindings extend the environment for subsequent clauses; other clauses
699/// execute for effect. The value of the final clause is returned.
700fn eval_block(
701    at: ChunkId,
702    len: u32,
703    binds: PatId,
704    exprs: NodeId,
705    env: &Env,
706    ctx: &Ctx,
707) -> Result<Value, Raised> {
708    let Some(last) = len.checked_sub(1) else {
709        return Ok(Value::Unit);
710    };
711    ctx.check_pat_run(at, Run::Block, binds, len);
712    ctx.check_run(at, Run::Block, exprs, len);
713    let mut env = env.clone();
714    for i in 0..last {
715        match ctx.pat(at, binds.nth(i)) {
716            Pat::None => {
717                eval(at, exprs.nth(i), &env, ctx)?;
718            }
719            pat => {
720                let v = eval(at, exprs.nth(i), &env, ctx)?;
721                env = match_pat(at, pat, &v, env, ctx)
722                    .map_err(|r| ctx.escaped(r, at, binds.nth(i), &v))?;
723            }
724        }
725    }
726    match ctx.pat(at, binds.nth(last)) {
727        Pat::None => {
728            let result = eval(at, exprs.nth(last), &env, ctx);
729            ctx.release(env);
730            result
731        }
732        pat => {
733            let v = eval(at, exprs.nth(last), &env, ctx)?;
734            let env = match_pat(at, pat, &v, env, ctx)
735                .map_err(|r| ctx.escaped(r, at, binds.nth(last), &v))?;
736            ctx.release(env);
737            Ok(v)
738        }
739    }
740}
741
742/// Instantiates a compiled module, the top module of `chunk` (see
743/// [`Ctx::compile_module`]), giving it its identity.
744///
745/// `frame` provides outer values against the module's frame names. A length
746/// mismatch raises `.module_arity`.
747pub fn instantiate(chunk: ChunkId, frame: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
748    let top = ctx.chunk(chunk).top();
749    instantiate_module(chunk, top, frame, ctx)
750}
751
752/// Instantiates module `module` of chunk `chunk`, creating its
753/// [`Module`](EnvNode::Module) terminal and returning it as a [`Value::Module`].
754///
755/// This assigns the module an identity (fresh `Rc`) and reserves its ID block
756/// so items can be stamped with stable IDs (see `materialize_body`).
757///
758/// `frame` provides outer values against the module's frame names. A length
759/// mismatch raises `.module_arity`. The frame is stored as a flat
760/// [`Frame`](EnvNode::Frame), though `recur` builds the terminal directly.
761pub(crate) fn instantiate_module(
762    chunk: ChunkId,
763    module: ModId,
764    frame: &[Value],
765    ctx: &Ctx,
766) -> Result<Value, Raised> {
767    let (frame_len, len) = {
768        let code = ctx.chunk(chunk);
769        (code.module(module).frame.len, code.member_len(module))
770    };
771    if frame.len() != frame_len as usize {
772        return Err(Raised::symbol(Sym::MODULE_ARITY));
773    }
774    let id_base = ctx.reserve_ids(u64::from(len));
775    let frame = if frame.is_empty() {
776        Env::EMPTY
777    } else {
778        Env::EMPTY.frame(Box::from(frame))
779    };
780    Ok(Value::Module(EnvRef::new(EnvNode::Module {
781        chunk,
782        module,
783        id_base,
784        frame,
785    })))
786}
787
788/// Evaluates an item's body, node `body` of `chunk`, in its module terminal.
789/// This is the common path for [`mod_item`] and [`materialize`].
790///
791/// Literal abstraction bodies are built directly with the item's reserved
792/// ID (`id_base + index`), ensuring multiple accesses produce equal closures.
793/// This avoids `eval` dispatch and `Ctx` counter writes for performance.
794///
795/// Only function definitions claim the item's identity. Forwarded callables
796/// retain their original identity, while data items or nested closures are
797/// processed via `eval`.
798#[inline]
799fn materialize_body(
800    chunk: ChunkId,
801    body: NodeId,
802    env: &Env,
803    id_base: u64,
804    index: u32,
805    ctx: &Ctx,
806) -> Result<Value, Raised> {
807    if let Node::Abs(code) = ctx.node(chunk, body) {
808        return Ok(closure(chunk, code, id_base + u64::from(index), env, ctx));
809    }
810    eval(chunk, body, env, ctx)
811}
812
813/// Materializes the item named `name` from the module object `home`.
814/// Binary-searches for the index and evaluates the body in the terminal.
815/// Uses the object's own node as the terminal to avoid environment allocation.
816/// Raises `.missing_property` if the name is absent.
817fn materialize(env: &Env, name: Sym, ctx: &Ctx) -> Result<Value, Raised> {
818    let (chunk, module, id_base) = env
819        .as_module()
820        .expect("a module object always holds a module terminal");
821    let member = {
822        let code = ctx.chunk(chunk);
823        code.index_of(module, name)
824            .map(|index| (index, code.member(module, index)))
825    };
826    let Some((index, Some(member))) = member else {
827        return Err(Raised::symbol(Sym::MISSING_PROPERTY));
828    };
829    materialize_body(chunk, member.node, env, id_base, index, ctx)
830}
831
832/// Applies a receiver to a symbol. This is the dispatch path for all non-callable,
833/// non-module values. The symbol identifies a member of the receiver's prototype,
834/// and the receiver is passed as an argument. [`proto_of`] ensures this is total.
835///
836/// List projection takes precedence: numeric symbols on lists project indices.
837/// Other symbols dispatch to `__List`.
838///
839/// Non-symbol arguments raise `.not_applicable`.
840///
841/// Outlined to maintain I-cache residency in `apply1` and `apply_n`.
842#[inline(never)]
843fn receiver(this: Value, name: &Value, rest: &[Value], ctx: &Ctx) -> Result<Value, Raised> {
844    let Value::Symbol(s) = name else {
845        return Err(Raised::symbol(Sym::NOT_APPLICABLE));
846    };
847    let s = *s;
848    if let Value::List(elems) = &this {
849        let index = match ctx.projection(s) {
850            Projection::Name => None,
851            Projection::Index(i) => Some(i),
852            Projection::TooLarge => return Err(Raised::symbol(Sym::BAD_PROJECTION)),
853        };
854        if let Some(index) = index {
855            let projected = elems
856                .get(index as usize)
857                .cloned()
858                .ok_or_else(|| Raised::symbol(Sym::PROJECTION_OUT_OF_RANGE))?;
859            return apply_n(projected, rest, ctx);
860        }
861    }
862    let proto = if let Value::Object(obj) = &this {
863        obj.proto.clone()
864    } else if let Value::Module(home) = proto_of(&this, ctx) {
865        home
866    } else {
867        unreachable!("a prototype is always a module value")
868    };
869    dispatch(proto, this, s, rest, ctx)
870}
871
872/// Dispatches a method by materializing `name` from `proto` and applying it
873/// to the receiver and any remaining arguments.
874///
875/// Example: `x .m a b` is equivalent to `(materialize (proto of x) .m) x a b`.
876///
877/// The lookup is a binary search over the item table, ensuring locals are private.
878/// Arguments are handled similarly to the call spine in `eval_env`, with small
879/// arities processed on the stack.
880fn dispatch(
881    proto: EnvRef,
882    this: Value,
883    name: Sym,
884    rest: &[Value],
885    ctx: &Ctx,
886) -> Result<Value, Raised> {
887    let method = materialize(&Env::from_ref(proto), name, ctx)?;
888    match rest {
889        [] => apply1(method, this, ctx),
890        [a] => apply_n(method, &[this, a.clone()], ctx),
891        [a, b] => apply_n(method, &[this, a.clone(), b.clone()], ctx),
892        [a, b, c] => apply_n(method, &[this, a.clone(), b.clone(), c.clone()], ctx),
893        _ => {
894            let mut all: Vec<Value> = Vec::with_capacity(rest.len() + 1);
895            all.push(this);
896            all.extend_from_slice(rest);
897            apply_n(method, &all, ctx)
898        }
899    }
900}