elly_core/

ast.rs

//! The Elly AST and its s-expression dump.
//!
//! `to_sexp` emits a compact parenthesized form used by the parse golden
//! tests so they read close to `docs/elly-spec.md`. Leaves own their text as
//! [`Text`] (a cheap-clone inline/`Rc` handle), so the AST is `'static` — no
//! longer tied to the Muon source lifetime; structure is `alloc`ated.
//!
//! **Patterns are first-class AST** (see `docs/done/2026-07-26_elly-patterns-native.md`):
//! an `&`-abstraction, a `let` binding, and a `__match` clause all bind through
//! the same [`Pattern`] node, which the evaluator interprets directly (a native
//! matcher, not a lowering to eliminator builtins). The AST *rephrases* Muon
//! into Elly's own syntax; it does not *compile* patterns into anything else —
//! that is a later (VM) pass's job.

use alloc::boxed::Box;
use alloc::format;
use alloc::rc::Rc;
use alloc::string::{String, ToString};
use alloc::vec::Vec;

use num_bigint::BigInt;

use crate::eval::{Builtin, ModuleData};

/// An owned, cheap-clone text leaf — hipstr's single-threaded `Local` (`Rc`)
/// backend: **inline** for short strings (≤ 23 bytes on 64-bit), else a shared
/// `Rc<str>` slice, an **O(1) clone** either way. Replaces the former `&'a str`
/// source borrow so `Expr`/`Value` are `'static` and no longer tied to the Muon
/// source (see `docs/todo/elly-impl-expr-repr-v1.md`). A `'static` host tag is
/// stored for free via [`Text::from_static`](hipstr::string::HipStr::from_static).
pub type Text = hipstr::LocalHipStr<'static>;

/// An Elly expression in the first subset. Strings and records are deferred
/// (see the spec), so there is no variant for them yet.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
    /// An arbitrary-precision integer literal, parsed from the token (`0`, `-123`,
    /// `0xCAFE`); see the *integers* section of the spec.
    Int(BigInt),
    /// A runtime list literal from a Muon `<list>` (`[…]`), of *any* arity: `[]`
    /// (the empty list, which is unit), `[e]` (a genuine 1-list, distinct from
    /// `e`), or `[e0, e1, …]`. Parens `(…)` never produce this — they are
    /// grouping / argument spread at parse time (see `parse.rs`).
    List(Vec<Expr>),
    /// A bare name: a reference to an enclosing `&`-binding, else a free name.
    /// Produced by the parser as the *unresolved* form; the resolution pass
    /// (`resolve.rs`) rewrites every in-scope `Name` into a [`Expr::Local`] and
    /// rejects the rest. Tooling that wants the raw, pre-resolution tree
    /// (`parse_open`) keeps seeing `Name`; the evaluator only ever sees `Local`.
    Name(Text),
    /// A **resolved** reference: a flat de Bruijn `index` produced by the resolver
    /// from a [`Expr::Name`]. The environment is a nameless cons list of bindings
    /// (one cell per bound name, innermost first), and `index` counts cells to walk
    /// from the top (0 = the most recent binding) — so the evaluator's lookup is a
    /// pointer chase with no string compare and no per-link clone. The original
    /// `name` is kept only for rendering, **boxed** so it does not widen `Expr` past
    /// four words (it is read solely by `to_sexp` / `to_json`): a `Local` then
    /// prints exactly like the `Name` it replaced (`(name foo)` / `{"name":"foo"}`),
    /// so the goldens are unchanged.
    Local { name: Box<Text>, index: u32 },
    /// A `__`-builtin resolved **at parse** (see `Builtin::from_name`). `__` names
    /// are un-bindable, so a reference like `__Int.add` never depends on the
    /// environment; resolving it here turns each call into a direct dispatch rather
    /// than a failing env walk plus a name match at eval. Rendered exactly like the
    /// `Name` it replaces (`(name __Int.add)` / `{"name":"__Int.add"}`) so the
    /// goldens are unchanged.
    Builtin(Builtin),
    /// A **module sibling reference**: a name that resolved not to a lexical
    /// binding but to another item of the enclosing module (see
    /// `docs/done/2026-08-07_elly-modules-v0.md`). Produced only by the module resolver
    /// (`resolve::resolve_module_bodies`), never by `parse`; it is a *sink* — it
    /// carries no module reference and is resolved at eval through the home module
    /// carried in the environment (`EnvNode::Module`).
    ///
    /// `index` is the item's position in the home module's (name-sorted) item
    /// table, assigned at resolve so eval indexes straight into it with no name
    /// compare — the module-tier analogue of a `Local`'s de Bruijn index. `name` is
    /// kept for rendering only (boxed to keep `Expr` at four words). Renders
    /// `(moditem factorial)` / `{"moditem":"factorial"}`.
    /// `depth` is how many [`Module`](crate::EnvNode::Module) terminals the walk
    /// **skips** before the one that owns this item. A program with one module has
    /// no nesting and every `ModItem` carries `0`; a [`recur`](Expr::Recur) inside
    /// a module body puts a second terminal on the chain, and a reference to the
    /// module's own item from inside the `recur` has to step over the `recur`'s.
    /// It is the barrier-stack distance the resolver measured, not rendered (like
    /// a `Local`'s index, it is derived addressing).
    ModItem {
        name: Box<Text>,
        index: u32,
        depth: u32,
    },
    /// A **recursive binding group as an expression**: `recur (a = va, b = vb) e`.
    /// The bindings are *simultaneous* — each sees all of them, itself included —
    /// which is what separates it from `let`, whose group is sequential and
    /// desugars to nested [`App`](Expr::App)/[`Abs`](Expr::Abs) with no node of its
    /// own.
    ///
    /// The group is a module — the whole of one, body included: the bindings are
    /// its (name-sorted) item table, and they reach each other as
    /// [`ModItem`](Expr::ModItem)s *through the terminal* rather than by
    /// capturing references to each other, the edge that would cycle. The
    /// expression the group scopes over is the [`ModuleData`'s own
    /// body](crate::ModuleData::body), the slot a module source fills with
    /// `__main`. Evaluating this builds the terminal over the current environment
    /// (the cons-shaped frame) and runs that body under it; see
    /// `docs/done/2026-08-13_elly-recur.md` and `docs/done/2026-08-14_elly-run.md`.
    Recur(Rc<ModuleData>),
    /// A `.`-prefixed literal (`.foo`, `.0`), stored *without* the dot — the dot
    /// is the Muon sigil and is re-added when displayed / dumped.
    Symbol(Text),
    /// A string literal, **decoded** at parse from a Muon `<str>` (JSON/Muon
    /// escapes resolved, `\uXXXX` surrogate pairs combined) into owned UTF-8. It
    /// is self-evaluating: eval clones the handle into `Value::Str`. Rendered as
    /// the bare quoted, re-escaped literal (`"foo"`) — the quotes already mark it
    /// apart from `.foo` / `foo`, so no `(str …)` wrapper.
    Str(Text),
    /// Application: a **flattened call spine** whose element 0 is the callee and
    /// `[1..]` the arguments. A source spine `f a b c` and a spread call `f(a, b)`
    /// both parse into one node with a known call-site arity, so the evaluator
    /// binds a whole call's arguments in one pass (see `apply_n` in `eval.rs`).
    /// Always holds at least a callee and one argument (two elements); currying is
    /// recovered by `apply_n`'s over-application loop, so a flat spine is
    /// semantically identical to the left-nested binary applications it replaced —
    /// which is exactly how it is re-rendered in `to_sexp` / `to_json`.
    App(Box<[Expr]>),
    /// Abstraction `&<pattern> body`: the one universal binding form, its *code*
    /// (`Lambda`: the parameter patterns and the body) shared behind `Rc`. A run
    /// of `&p0 &p1 …` is collected at parse into one multi-parameter `Lambda`
    /// (arity `head.len()`), so applying it *matches* a whole call's arguments in
    /// one pass. The evaluator builds a closure by cloning the `Rc<Lambda>` and
    /// capturing the environment, rather than deep-cloning the subtree. Rendered as
    /// nested `(abs p0 (abs p1 …))` — the curried reading the collected head stands
    /// for — to keep the goldens stable.
    Abs(Rc<Lambda>),
    /// A map literal from a Muon `<block>` (`{ … }`): its entries as
    /// (key-expr, value-expr) pairs, in source order. Keys stay expressions
    /// until eval, so computed keys (`(expr)`) just evaluate like any other
    /// expression; see the *maps* section of the spec.
    Map(Vec<(Expr, Expr)>),
    /// A **home-module leaf**: `__module`, `__new` or `__value`, each reading the
    /// module the body it sits in was written in (see [`HomeLeaf`]). Like a
    /// [`ModItem`](Expr::ModItem) it is a *sink* — it carries no module reference
    /// and finds its module through the environment's terminal at eval — and like
    /// one it costs a leaf and no capture slot.
    ///
    /// `depth` is how many [`Module`](crate::EnvNode::Module) terminals to step
    /// over before the module: a leaf names the nearest terminal *written as a
    /// module*, so a [`recur`](Expr::Recur) between the leaf and its module is
    /// stepped over and a method that loops internally still constructs objects of
    /// its own type. The resolver measures it (the same barrier-stack distance a
    /// `ModItem` carries) and rejects a leaf with no module on the stack; it is
    /// derived addressing, so it is not rendered. See
    /// `docs/done/2026-08-15_elly-objects-v0.md`.
    Home { leaf: HomeLeaf, depth: u32 },
}

/// Which of the three [home-module leaves](Expr::Home) a reference is. They share
/// one variant because they share the whole of their machinery — one walk to the
/// terminal, one parse clause each, no capture — and differ only in what they
/// evaluate to once it is found.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HomeLeaf {
    /// `__module` — the home module itself, a `Value::Module`.
    Module,
    /// `__new` — the object constructor over the home module: the object builtin
    /// with the module already applied, so what is left takes the payload.
    New,
    /// `__value` — the payload reader over the home module, the same shape. In
    /// *pattern* position the name is [`Pattern::Unwrap`] instead.
    Value,
}

impl HomeLeaf {
    /// The reserved name this leaf is written and rendered as.
    pub fn name(self) -> &'static str {
        match self {
            HomeLeaf::Module => "__module",
            HomeLeaf::New => "__new",
            HomeLeaf::Value => "__value",
        }
    }
}
// TODO: annotate expressions with source spans
// TODO: do not hardcode `Vec`/`Box`

/// The body of a [`recur`](Expr::Recur) group. It is an `Option` on
/// [`ModuleData`] because a *module* may decline to declare one, but a group's is
/// required by the grammar ([`ParseError::RecurMissingBody`]) — so every
/// `Expr::Recur` has one, and the two readers that would otherwise both unwrap
/// (`to_sexp`/`to_json` here, [`eval`](crate::eval) there) say why once.
///
/// [`ParseError::RecurMissingBody`]: crate::ParseError::RecurMissingBody
pub(crate) fn recur_body(data: &ModuleData) -> &Expr {
    data.body().expect("a recur group always has a body")
}

/// The *code* of an abstraction: the parameter patterns and the body. Shared
/// behind `Rc` between the [`Expr::Abs`] that builds a closure and the
/// `Value::Closure` that captures an environment over it, so a partial
/// application is one `Rc::clone` (plus a bumped `applied` counter and an
/// extended environment) rather than a fresh `Lambda` allocation. The **arity is
/// `head.len()`** — collected greedily at parse from a run of `&p0 &p1 …` — and
/// is capped at 255 (see `parse.rs`). `head` is non-empty: every abstraction
/// binds at least one parameter.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Lambda {
    pub head: Box<[Pattern]>,
    pub body: Expr,
    /// How a closure over this lambda gets its environment: see [`Captures`].
    /// Derived data, not syntax — it is not rendered by `to_sexp` / `to_json`.
    pub captures: Captures,
}

impl Lambda {
    /// The number of parameters this abstraction binds before its body runs.
    pub fn arity(&self) -> usize {
        self.head.len()
    }
}

/// How a closure over a [`Lambda`] gets the environment its body runs in — decided
/// per abstraction by the resolver, and the *only* thing that distinguishes the two
/// closure representations (both are semantically identical; environments are
/// immutable, so reading a value now or later gives the same answer).
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Captures {
    /// Not yet resolved — the state the parser leaves behind. The evaluator refuses
    /// it rather than silently reading the wrong slots (the same posture as an
    /// unresolved [`Expr::Name`] at eval).
    Unresolved,
    /// **Share** the defining environment by reference: no frame, no allocation, and
    /// the body's indices keep counting into the enclosing activation's chain.
    ///
    /// Chosen where a closure cannot outlive the call that creates it, so retaining
    /// the chain retains nothing observable: the callee of a direct application
    /// (every `let`), and a literal `&`-abstraction handed straight to a builtin that
    /// only *applies* it — a `__match` clause, an `__Err.catch` or `__eq` branch, a
    /// `__Int.for` / `__Map.for` / `__Map.merge` callback. Elly mints these on every
    /// call, and making each one copy a frame is what a measured 10–28% regression
    /// was made of (see `docs/done/2026-08-14_elly-perf-closure-capture.md`).
    Chain,
    /// **Capture** these free variables into a fresh frame, one [`Capture`] each,
    /// **sorted by `outer`** (see `Capture` for why). The closure then retains only
    /// what its body uses, and a reference into an enclosing scope is one index into
    /// the frame (see `EnvNode::Frame` in `eval.rs`). This is the default — every
    /// abstraction whose closure may escape. An empty plan is a *closed* lambda: it
    /// captures nothing and allocates no frame.
    Frame(Box<[Capture]>),
}

/// One captured free variable: **where to read it** (`outer` — a de Bruijn index in
/// the *enclosing* activation, at the point the [`Expr::Abs`] is evaluated) and
/// **where it goes** (`slot` — its position in the closure's frame).
///
/// The two are separate because the resolver fixes `slot` at a free variable's
/// first use, while `outer` only falls out of resolving it in the enclosing scopes;
/// re-ordering the frame to match would mean renumbering references already emitted
/// into the body. Instead the resolver sorts the *plan* by `outer`, so the
/// evaluator fills the whole frame in **one** walk of the defining environment
/// (ascending indices, never restarting) and writes each value to its `slot`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Capture {
    pub outer: u32,
    pub slot: u32,
}

/// A **pattern**: the left-hand side of any binding (`&<pat> …`, `let (<pat> =
/// …)`, a `__match` clause). Matched against a value by the evaluator's native
/// matcher (`match_pattern` in `eval.rs`), which either extends the environment
/// or refutes. `Bind`/`Discard` are irrefutable; every other shape may refute.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Pattern {
    /// `_` — matches anything, binds nothing.
    Discard,
    /// `name` — binds the subject to `name`. The matcher conses one cell carrying
    /// the subject onto the environment; the name itself is not stored at runtime
    /// (references to it were resolved to a de Bruijn index).
    Bind(Text),
    /// `name = <pat>` — binds the subject to `name`, then matches `<pat>` against
    /// the same subject.
    At(Text, Box<Pattern>),
    /// `= <expr>` (and its `.sym` sugar) — matches iff the subject equals the
    /// value of `<expr>`; binds nothing. Evaluating `<expr>` may raise a real
    /// error, which propagates (it is not a refutation).
    Equal(Expr),
    /// `< <expr>` — matches iff the subject is (strictly) ordered before the value
    /// of `<expr>`; binds nothing. Ordering is defined only within a comparable
    /// kind (`Int` for now, later `Str`), so a subject/bound that are not both of
    /// one such kind refute with `.not_int` (a refutation, not a host raise).
    Less(Expr),
    /// `> <expr>` — the mirror of [`Less`](Pattern::Less): matches iff the subject
    /// is ordered after the value of `<expr>`.
    Greater(Expr),
    /// `<pat> as <Proto>` / `(as <Proto>) <pat>` — matches iff the subject's
    /// prototype is `<Proto>`, then matches `<pat>` against the (narrowed)
    /// subject. See [`ProtoRef`] for the two forms the prototype takes.
    Type(ProtoRef, Box<Pattern>),
    /// `__value <pat>` — matches iff the subject is an **object of the home
    /// module** and its payload matches `<pat>`, binding what the inner pattern
    /// binds. It is the pattern side of the [`__value`](HomeLeaf::Value) leaf, and
    /// the prototype check is implicit for the same reason the leaf's is:
    /// unwrapping a foreign object has no sound reading.
    ///
    /// It holds no reference — the module is implicit, exactly as it is for
    /// `__new` — so the pattern grammar stays closed. `depth` is the leaf's, and
    /// the matcher walks the environment to that terminal and compares the
    /// prototype by pointer before descending.
    Unwrap { depth: u32, inner: Box<Pattern> },
    /// `(p1 | p2)` — try the left arm, on refutation try the right. Both arms bind
    /// the same set of names (checked at parse time). **Committed**: once an arm's
    /// pattern matches, a later failure does not backtrack into the other arm.
    Or(Box<Pattern>, Box<Pattern>),
    /// `[p0, …]` with an optional trailing rest — a fixed-arity list pattern.
    List(Vec<Pattern>, Rest),
    /// `{ k0: p0, … }` — a map pattern of (key, value pattern) entries.
    /// `Rest::None` is **closed** (exactly these keys); `Rest::Anon`/`Named` open
    /// it (at least these keys; `Named` binds the remainder map).
    Map(Vec<(MapKey, Pattern)>, Rest),
}

/// A map-pattern entry's key. A **lookup** key (`.sym`, bare `sym`, `(= expr)`)
/// names a concrete key to probe. A **capture** key (a binder pattern in key
/// position, e.g. `(k)` / `(_)`) instead *peels* the smallest remaining entry and
/// matches its key against the pattern — the map analogue of `[a, ...rest]`.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MapKey {
    Lookup(Expr),
    Capture(Box<Pattern>),
}

/// A pattern's trailing rest: none, an anonymous `...` (ignore the remainder), or
/// a named `...rest` (bind it to the remainder). For a list, `None` is an exact
/// arity; for a map, `None` is a closed key set — either way a rest opens it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Rest {
    None,
    Anon,
    /// `...name` — binds the remainder (list tail / leftover map) to `name`; the
    /// matcher conses one cell carrying the remainder onto the environment.
    Named(Text),
}

/// The prototype an `as <Proto>` pattern narrows to. One rule covers both forms —
/// the subject matches iff its prototype *is* the named module — and they differ
/// only in how much of the work is left to run time.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ProtoRef {
    /// The **compiled fast form**: a reference the resolver recognized as the
    /// builtin module that is some value kind's prototype, so the check is the
    /// discriminant test [`TyKind`] always was rather than an eval plus a pointer
    /// compare. `as Int` takes this path, alias or `__`-spelling alike.
    Kind(TyKind),
    /// Any other prototype, named by an **atom** — a module item, a local, a
    /// frame slot, or `__module`. Resolved like an [`Equal`](Pattern::Equal)
    /// comparand, evaluated at match time, and required to be a module value.
    Ref(Expr),
}

impl ProtoRef {
    /// Render the reference: a kind by its bare name (`Int`), so the existing
    /// goldens are unchanged, and anything else as the expression it is.
    fn write_sexp(&self, out: &mut String) {
        match self {
            ProtoRef::Kind(ty) => out.push_str(ty.name()),
            ProtoRef::Ref(expr) => expr.write_sexp(out),
        }
    }

    fn write_json(&self, out: &mut String) {
        match self {
            ProtoRef::Kind(ty) => json_str(ty.name(), out),
            ProtoRef::Ref(expr) => expr.write_json(out),
        }
    }
}

/// The value kinds whose prototype is a **builtin module**, so that `as <Proto>`
/// against it compiles to a discriminant test (see [`ProtoRef::Kind`]).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TyKind {
    Int,
    Sym,
    Str,
    List,
    Map,
    Fun,
    /// A module value, whose prototype is `__Mod`. It has no `as Mod` history —
    /// the kind set was closed before modules existed — and is here because
    /// `__Mod` is a builtin module like the rest, so the fast form covers it.
    Mod,
}

impl TyKind {
    /// The spelling used in the `as <Proto>` surface and the dumps.
    pub fn name(self) -> &'static str {
        match self {
            TyKind::Int => "Int",
            TyKind::Sym => "Sym",
            TyKind::Str => "Str",
            TyKind::List => "List",
            TyKind::Map => "Map",
            TyKind::Fun => "Fun",
            TyKind::Mod => "Mod",
        }
    }
}

impl Expr {
    /// Serialize to a compact s-expression, e.g. `(app (name f) (name x))`.
    pub fn to_sexp(&self) -> String {
        let mut out = String::new();
        self.write_sexp(&mut out);
        out
    }

    // TODO: replace with impl de::Deserialize, impl ser::Serialize
    /// Serialize to compact, tagged JSON, e.g.
    /// `{"app":[{"name":"f"},{"name":"x"}]}`. Parallels `muon::Seq::to_json`;
    /// used by the `elly-wasm` playground to render the AST as a tree.
    pub fn to_json(&self) -> String {
        let mut out = String::new();
        self.write_json(&mut out);
        out
    }

    fn write_json(&self, out: &mut String) {
        match self {
            Expr::Int(n) => {
                // f64 (JSON's only number type) represents every integer in
                // [-2^53, 2^53] exactly. Within that range emit a bare number so
                // the playground shows it as-is; outside it, fall back to a
                // decimal *string* tagged `Int` to avoid precision loss.
                if fits_f64_exactly(n) {
                    out.push_str(&n.to_string());
                } else {
                    out.push_str("{\"Int\":");
                    json_str(&n.to_string(), out);
                    out.push('}');
                }
            }
            // A `Name` (unresolved) and a `Local` (resolved) both render by name.
            Expr::Name(n) => {
                out.push_str("{\"name\":");
                json_str(n, out);
                out.push('}');
            }
            Expr::Local { name, .. } => {
                out.push_str("{\"name\":");
                json_str(name.as_str(), out);
                out.push('}');
            }
            // A parse-resolved builtin renders as the `Name` it stands in for.
            Expr::Builtin(op) => {
                out.push_str("{\"name\":");
                json_str(op.name(), out);
                out.push('}');
            }
            // A home-module leaf renders as the reserved name it was written as,
            // for the reason a `Local` and a `Builtin` do: the depth beside it is
            // derived addressing, not syntax.
            Expr::Home { leaf, .. } => {
                out.push_str("{\"name\":");
                json_str(leaf.name(), out);
                out.push('}');
            }
            Expr::ModItem { name, .. } => {
                out.push_str("{\"moditem\":");
                json_str(name.as_str(), out);
                out.push('}');
            }
            Expr::Recur(data) => {
                out.push_str("{\"recur\":[");
                for (i, (name, body)) in data.items().iter().enumerate() {
                    if i > 0 {
                        out.push(',');
                    }
                    out.push('[');
                    json_str(name.as_str(), out);
                    out.push(',');
                    body.write_json(out);
                    out.push(']');
                }
                out.push_str("],\"body\":");
                recur_body(data).write_json(out);
                out.push('}');
            }
            Expr::Symbol(s) => {
                let mut dotted = String::from(".");
                dotted.push_str(s);
                out.push_str("{\"sym\":");
                json_str(&dotted, out);
                out.push('}');
            }
            Expr::Str(s) => {
                out.push_str("{\"str\":");
                json_str(s, out);
                out.push('}');
            }
            // Render the call spine flat, preserving the arity the AST stores.
            Expr::App(items) => write_app_json(items, out),
            // Re-render the collected head as nested single-parameter abstractions.
            Expr::Abs(code) => write_abs_json(&code.head, &code.body, out),
            Expr::List(elems) => {
                out.push_str("{\"list\":[");
                for (i, e) in elems.iter().enumerate() {
                    if i > 0 {
                        out.push(',');
                    }
                    e.write_json(out);
                }
                out.push_str("]}");
            }
            Expr::Map(entries) => {
                out.push_str("{\"map\":[");
                for (i, (k, v)) in entries.iter().enumerate() {
                    if i > 0 {
                        out.push(',');
                    }
                    out.push('[');
                    k.write_json(out);
                    out.push(',');
                    v.write_json(out);
                    out.push(']');
                }
                out.push_str("]}");
            }
        }
    }

    fn write_sexp(&self, out: &mut String) {
        match self {
            Expr::Int(n) => {
                out.push_str("(int ");
                out.push_str(&n.to_string());
                out.push(')');
            }
            // A `Name` (unresolved) and a `Local` (resolved) both render by name.
            Expr::Name(n) => {
                out.push_str("(name ");
                out.push_str(n);
                out.push(')');
            }
            Expr::Local { name, .. } => {
                out.push_str("(name ");
                out.push_str(name.as_str());
                out.push(')');
            }
            // A parse-resolved builtin renders as the `Name` it stands in for.
            Expr::Builtin(op) => {
                out.push_str("(name ");
                out.push_str(op.name());
                out.push(')');
            }
            Expr::Home { leaf, .. } => {
                out.push_str("(name ");
                out.push_str(leaf.name());
                out.push(')');
            }
            Expr::ModItem { name, .. } => {
                out.push_str("(moditem ");
                out.push_str(name.as_str());
                out.push(')');
            }
            // `(recur (bind a …) (bind b …) <body>)` — the bindings in the table's
            // sorted order, then the body, so the group reads as one form.
            Expr::Recur(data) => {
                out.push_str("(recur");
                for (name, body) in data.items() {
                    out.push_str(" (bind ");
                    out.push_str(name.as_str());
                    out.push(' ');
                    body.write_sexp(out);
                    out.push(')');
                }
                out.push(' ');
                recur_body(data).write_sexp(out);
                out.push(')');
            }
            Expr::Symbol(s) => {
                out.push_str("(sym .");
                out.push_str(s);
                out.push(')');
            }
            // A string leaf is the bare quoted, re-escaped literal — the quotes
            // already set it apart from `(sym .foo)` / `(name foo)`, so no wrapper.
            Expr::Str(s) => json_str(s, out),
            // Render the call spine flat, preserving the arity the AST stores.
            Expr::App(items) => write_app_sexp(items, out),
            // Re-render the collected head as nested single-parameter abstractions.
            Expr::Abs(code) => write_abs_sexp(&code.head, &code.body, out),
            Expr::List(elems) => {
                out.push_str("(list");
                for e in elems {
                    out.push(' ');
                    e.write_sexp(out);
                }
                out.push(')');
            }
            Expr::Map(entries) => {
                out.push_str("(map");
                for (k, v) in entries {
                    out.push_str(" (entry ");
                    k.write_sexp(out);
                    out.push(' ');
                    v.write_sexp(out);
                    out.push(')');
                }
                out.push(')');
            }
        }
    }
}

/// Render a flat call spine `[callee, a0, a1, …]` (≥ 2 elements) as the flat
/// s-expression `(app callee a0 a1)` — the arity is shown as the AST stores it,
/// not re-curried into left-nested binary `(app (app callee a0) a1)` forms.
fn write_app_sexp(items: &[Expr], out: &mut String) {
    out.push_str("(app");
    for it in items {
        out.push(' ');
        it.write_sexp(out);
    }
    out.push(')');
}

/// Render a collected head `[p0, p1, …]` (non-empty) over `body` as the nested
/// `(abs p0 (abs p1 body))` it stands for.
fn write_abs_sexp(head: &[Pattern], body: &Expr, out: &mut String) {
    out.push_str("(abs ");
    head[0].write_sexp(out);
    out.push(' ');
    if head.len() == 1 {
        body.write_sexp(out);
    } else {
        write_abs_sexp(&head[1..], body, out);
    }
    out.push(')');
}

/// The tagged-JSON twin of [`write_app_sexp`]: `{"app":[callee, a0, a1, …]}`, the
/// whole spine flat so the AST view shows the call's arity as stored.
fn write_app_json(items: &[Expr], out: &mut String) {
    out.push_str("{\"app\":[");
    for (i, it) in items.iter().enumerate() {
        if i > 0 {
            out.push(',');
        }
        it.write_json(out);
    }
    out.push_str("]}");
}

/// The tagged-JSON twin of [`write_abs_sexp`]: `{"abs":{"param":…,"body":…}}` nested.
fn write_abs_json(head: &[Pattern], body: &Expr, out: &mut String) {
    out.push_str("{\"abs\":{\"param\":");
    head[0].write_json(out);
    out.push_str(",\"body\":");
    if head.len() == 1 {
        body.write_json(out);
    } else {
        write_abs_json(&head[1..], body, out);
    }
    out.push_str("}}");
}

impl Pattern {
    /// Serialize a pattern to the same compact s-expression family as `Expr`.
    /// A bare `Bind`/`Discard` renders as just its name (`a`, `_`) so the common
    /// `&x` reads `(abs x …)`; structured patterns are tagged forms
    /// (`(list a ...rest)`, `(at n <p>)`, `(as Int <p>)`, `(eq <expr>)`, …).
    fn write_sexp(&self, out: &mut String) {
        match self {
            Pattern::Discard => out.push('_'),
            Pattern::Bind(name) => out.push_str(name),
            Pattern::At(name, inner) => {
                out.push_str("(at ");
                out.push_str(name);
                out.push(' ');
                inner.write_sexp(out);
                out.push(')');
            }
            Pattern::Equal(expr) => {
                out.push_str("(eq ");
                expr.write_sexp(out);
                out.push(')');
            }
            Pattern::Less(expr) => {
                out.push_str("(lt ");
                expr.write_sexp(out);
                out.push(')');
            }
            Pattern::Greater(expr) => {
                out.push_str("(gt ");
                expr.write_sexp(out);
                out.push(')');
            }
            Pattern::Type(proto, inner) => {
                out.push_str("(as ");
                proto.write_sexp(out);
                out.push(' ');
                inner.write_sexp(out);
                out.push(')');
            }
            Pattern::Unwrap { inner, .. } => {
                out.push_str("(unwrap ");
                inner.write_sexp(out);
                out.push(')');
            }
            Pattern::Or(left, right) => {
                out.push_str("(or ");
                left.write_sexp(out);
                out.push(' ');
                right.write_sexp(out);
                out.push(')');
            }
            Pattern::List(elems, rest) => {
                out.push_str("(list");
                for e in elems {
                    out.push(' ');
                    e.write_sexp(out);
                }
                rest.write_sexp(out);
                out.push(')');
            }
            Pattern::Map(entries, rest) => {
                out.push_str("(map");
                for (key, vpat) in entries {
                    out.push_str(" (entry ");
                    key.write_sexp(out);
                    out.push(' ');
                    vpat.write_sexp(out);
                    out.push(')');
                }
                rest.write_sexp(out);
                out.push(')');
            }
        }
    }

    fn write_json(&self, out: &mut String) {
        match self {
            Pattern::Discard => out.push_str("{\"discard\":true}"),
            Pattern::Bind(name) => {
                out.push_str("{\"bind\":");
                json_str(name, out);
                out.push('}');
            }
            Pattern::At(name, inner) => {
                out.push_str("{\"at\":[");
                json_str(name, out);
                out.push(',');
                inner.write_json(out);
                out.push_str("]}");
            }
            Pattern::Equal(expr) => {
                out.push_str("{\"eq\":");
                expr.write_json(out);
                out.push('}');
            }
            Pattern::Less(expr) => {
                out.push_str("{\"lt\":");
                expr.write_json(out);
                out.push('}');
            }
            Pattern::Greater(expr) => {
                out.push_str("{\"gt\":");
                expr.write_json(out);
                out.push('}');
            }
            Pattern::Type(proto, inner) => {
                out.push_str("{\"as\":[");
                proto.write_json(out);
                out.push(',');
                inner.write_json(out);
                out.push_str("]}");
            }
            Pattern::Unwrap { inner, .. } => {
                out.push_str("{\"unwrap\":");
                inner.write_json(out);
                out.push('}');
            }
            Pattern::Or(left, right) => {
                out.push_str("{\"or\":[");
                left.write_json(out);
                out.push(',');
                right.write_json(out);
                out.push_str("]}");
            }
            Pattern::List(elems, rest) => {
                out.push_str("{\"listpat\":{\"elems\":[");
                for (i, e) in elems.iter().enumerate() {
                    if i > 0 {
                        out.push(',');
                    }
                    e.write_json(out);
                }
                out.push_str("],\"rest\":");
                rest.write_json(out);
                out.push_str("}}");
            }
            Pattern::Map(entries, rest) => {
                out.push_str("{\"mappat\":{\"entries\":[");
                for (i, (key, vpat)) in entries.iter().enumerate() {
                    if i > 0 {
                        out.push(',');
                    }
                    out.push('[');
                    key.write_json(out);
                    out.push(',');
                    vpat.write_json(out);
                    out.push(']');
                }
                out.push_str("],\"rest\":");
                rest.write_json(out);
                out.push_str("}}");
            }
        }
    }
}

impl Rest {
    /// Append a trailing rest to an s-expression list/map form: nothing for
    /// `None`, ` ...` for `Anon`, ` ...name` for `Named`.
    fn write_sexp(&self, out: &mut String) {
        match self {
            Rest::None => {}
            Rest::Anon => out.push_str(" ..."),
            Rest::Named(name) => {
                out.push_str(" ...");
                out.push_str(name);
            }
        }
    }

    fn write_json(&self, out: &mut String) {
        match self {
            Rest::None => out.push_str("null"),
            Rest::Anon => out.push_str("\"...\""),
            Rest::Named(name) => {
                out.push_str("{\"named\":");
                json_str(name, out);
                out.push('}');
            }
        }
    }
}

impl MapKey {
    fn write_sexp(&self, out: &mut String) {
        match self {
            // A lookup key is a plain expression (`.a`, a computed `(name k)`).
            MapKey::Lookup(expr) => expr.write_sexp(out),
            // A capture key wraps a pattern that matches the peeled key.
            MapKey::Capture(kpat) => {
                out.push_str("(capture ");
                kpat.write_sexp(out);
                out.push(')');
            }
        }
    }

    fn write_json(&self, out: &mut String) {
        match self {
            MapKey::Lookup(expr) => {
                out.push_str("{\"lookup\":");
                expr.write_json(out);
                out.push('}');
            }
            MapKey::Capture(kpat) => {
                out.push_str("{\"capture\":");
                kpat.write_json(out);
                out.push('}');
            }
        }
    }
}

/// Whether `n` is exactly representable as an `f64`: every integer in
/// `[-2^53, 2^53]` is (2^53 is the largest magnitude with no representation gap).
fn fits_f64_exactly(n: &BigInt) -> bool {
    const LIMIT: i64 = 1 << 53; // 2^53 == 9_007_199_254_740_992
    *n >= BigInt::from(-LIMIT) && *n <= BigInt::from(LIMIT)
}

/// Write `s` as a JSON string literal (quoted and escaped). Shared with `eval.rs`
/// so a `Value::Str`'s display re-escapes identically to an `Expr::Str`'s dumps.
pub(crate) fn json_str(s: &str, out: &mut String) {
    out.push('"');
    for ch in s.chars() {
        match ch {
            '"' => out.push_str("\\\""),
            '\\' => out.push_str("\\\\"),
            '\n' => out.push_str("\\n"),
            '\r' => out.push_str("\\r"),
            '\t' => out.push_str("\\t"),
            c if (c as u32) < 0x20 => out.push_str(&format!("\\u{:04x}", c as u32)),
            c => out.push(c),
        }
    }
    out.push('"');
}