elly_core/

ast.rs

//! The Elly AST and its s-expression dump.
//!
//! `to_sexp` provides a compact parenthesized form for parse golden tests. Leaf text
//! uses [`Text`] (inline/`Rc` handle) to make the AST `'static` and independent of
//! Muon source lifetimes; structure is `alloc`ated.
//!
//! Patterns are first-class AST nodes (see `docs/done/2026-07-26_elly-patterns-native.md`)
//! used by `&`-abstractions, `let` bindings, and `__match` clauses. The evaluator
//! interprets [`Pattern`] nodes directly; the AST rephrases Muon syntax without
//! compiling patterns, which is deferred to the VM.

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

use num_bigint::BigInt;

pub use crate::eval::Builtin;
pub use crate::module::ModuleData;

/// An owned, cheap-clone text leaf using hipstr's `Local` (`Rc`) backend.
/// Short strings (≤ 23 bytes on 64-bit) are inlined; longer strings use a shared
/// `Rc<str>` slice. This ensures `Expr` and `Value` are `'static` and independent
/// of the Muon source. Host tags are stored via [`Text::from_static`].
pub type Text = hipstr::LocalHipStr<'static>;

/// An Elly expression for the initial subset. Strings and records are deferred
/// per the spec.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Expr {
    /// Arbitrary-precision integer literal parsed from tokens (`0`, `-123`, `0xCAFE`).
    Int(BigInt),
    /// The unit value `()`. Used as a nullary marker in chains (`f ()`), standalone,
    /// or as empty-value sugar in maps (`{ .k: }`). Matches [`Pattern::Unit`].
    /// Rendered as `()`.
    Unit,
    /// Runtime list literal from Muon `#`-prefixed brackets (`#[…]`). Supports
    /// any arity, including empty `#[ ]` or single-element `#[e]`. Grouping
    /// parentheses `(…)` are handled at parse time.
    List(Vec<Expr>),
    /// Unresolved reference to a binding or free name. The resolver rewrites
    /// in-scope names to [`Expr::Local`] and rejects others. Evaluator only
    /// sees `Local`.
    Name(Text),
    /// Resolved reference using a de Bruijn `index`. The environment is a cons
    /// list of bindings (innermost first); `index` is the distance from the top.
    /// The original `name` is boxed and kept for rendering to keep `Expr` at four words.
    Local { name: Box<Text>, index: u32 },
    /// A `__`-builtin resolved at parse time via `Builtin::from_name`. Since `__`
    /// names are unbindable, this avoids environment lookups at runtime. Renders
    /// as the `Name` it replaces.
    Builtin(Builtin),
    /// Reference to an item in the enclosing module. Resolved by
    /// `resolve_module_bodies`. Evaluated via the home module in the environment.
    /// `index` is the item's position in the sorted item table. `depth` is the
    /// number of [`Module`](crate::EnvNode::Module) terminals to skip. `name` is
    /// boxed for size.
    ModItem {
        name: Box<Text>,
        index: u32,
        depth: u32,
    },
    /// Recursive binding group: `recur (a = va, b = vb) e`. Bindings are simultaneous
    /// and mutually visible. The group is treated as a module where bindings are
    /// items and the scoped expression is the module body. See
    /// `docs/done/2026-08-13_elly-recur.md`.
    Recur(Rc<ModuleData>),
    /// Dotted literal (`.foo`, `.0`), stored without the leading dot.
    Symbol(Text),
    /// UTF-8 string literal decoded from Muon `<str>`. Evaluates to `Value::Str`.
    /// Rendered as a quoted literal.
    Str(Text),
    /// Flattened call spine: index 0 is the callee, `[1..]` are arguments. Covers
    /// both standard and spread calls. Evaluated via `apply_n` in `eval.rs`. Holds
    /// at least two elements; currying is handled by the evaluator.
    App(Box<[Expr]>),
    /// Abstraction `&<pattern> body`. The `Lambda` (patterns and body) is shared
    /// via `Rc`. Multiple `&` parameters are collected into one `Lambda`. Evaluator
    /// creates closures by capturing the environment. Renders as nested `(abs …)`
    /// for stability.
    Abs(Rc<Lambda>),
    /// Map literal from Muon `#{ … }`. Entries are (key, value) pairs in source
    /// order. Keys are evaluated at runtime.
    Map(Vec<(Expr, Expr)>),
    /// Reference to the home module: `Self`, `#Self(…)`, or `x.Self`. Found via the
    /// environment's terminal. `depth` is the number of `Module` terminals to skip.
    /// See `docs/done/2026-09-11_elly-v1-self.md`.
    Home { leaf: HomeLeaf, depth: u32 },
    /// Sequence `{ c0, c1, …, e }`, also the target for `let`. Clauses are evaluated
    /// sequentially in a shared scope; the last clause's value is the block's result.
    /// Represented explicitly to support future effects (e.g., `break`, `defer`).
    /// Boxed to keep `Expr` at four words.
    Block(Box<[(Option<Pattern>, Expr)]>),
    /// Matching construct `case <subject> { &p0 b0, ... }`. Evaluates subject once
    /// and executes the first matching arm's body. Raises `.no_match` if no arms
    /// match. Subjectless cases are lowered to `&__arg (case __arg { ... })`.
    Case {
        subject: Rc<Expr>,
        cases: Box<[(Pattern, Expr)]>,
    },
}

/// Home-module leaf types: the module itself (`Self`), construction
/// (`#Self(…)`), or payload read (`x.Self`). These share the same resolution
/// machinery (one walk to the terminal) and differ only in their eval result.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HomeLeaf {
    /// `Self` — the home module as a `Value::Module`.
    Module,
    /// `#Self(…)` / `#Self …` — the object constructor for the home module.
    /// Always the callee of an [`App`](Expr::App). Renders as `(new …)`.
    New,
    /// `x.Self` — the payload reader for the home module. Always the callee
    /// of an [`App`](Expr::App). In patterns, spelled as [`Pattern::Unwrap`].
    Value,
}

impl HomeLeaf {
    /// The name reported by the resolver for leaves outside a module body.
    pub fn name(self) -> &'static str {
        "Self"
    }
}
// TODO: annotate expressions with source spans
// TODO: do not hardcode `Vec`/`Box`

/// Returns the body of a `recur` group. Required by grammar; `ModuleData`
/// uses `Option` because standalone modules may lack one.
pub(crate) fn recur_body(data: &ModuleData) -> &Expr {
    data.body().expect("a recur group always has a body")
}

/// The code of an abstraction: parameter patterns and body. Shared via `Rc`
/// between [`Expr::Abs`] and `Value::Closure`. Arity is `head.len()`, capped
/// at 255. Every abstraction binds at least one parameter.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Lambda {
    pub head: Box<[Pattern]>,
    pub body: Expr,
    /// Environment capture strategy, determined by the resolver.
    pub captures: Captures,
}

impl Lambda {
    /// Number of parameters bound before the body executes.
    pub fn arity(&self) -> usize {
        self.head.len()
    }
}

/// Environment capture strategy for a [`Lambda`] closure.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Captures {
    /// Unresolved state from the parser. Refused by the evaluator.
    Unresolved,
    /// Share the defining environment by reference. Used when the closure
    /// cannot outlive its creator (e.g., direct applications, `__match` arms,
    /// or `__Int.for` callbacks), avoiding frame allocation.
    Chain,
    /// Capture free variables into a fresh frame, sorted by `outer` index.
    /// This is the default for escaping closures. An empty plan is a closed lambda.
    Frame(Box<[Capture]>),
}

/// A captured free variable: `outer` is the de Bruijn index in the enclosing
/// activation at evaluation; `slot` is its position in the closure's frame.
/// The plan is sorted by `outer` so the evaluator fills the frame in one
/// linear walk of the environment.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Capture {
    pub outer: u32,
    pub slot: u32,
}

/// A pattern: the left-hand side of a binding (`&<pat> …`, `let (<pat> = …)`,
/// or a `__match` clause). Matched by the evaluator's native matcher
/// (`match_pattern` in `eval.rs`). `Bind`/`Discard` are irrefutable.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Pattern {
    /// `_` — matches any value without binding.
    Discard,
    /// `name` — binds the subject to `name`. A cell is consed onto the environment;
    /// names are resolved to de Bruijn indices at parse time.
    Bind(Text),
    /// `name = <pat>` — binds the subject to `name`, then matches `<pat>` against
    /// the same subject.
    At(Text, Box<Pattern>),
    /// `= <expr>` — matches if the subject equals the value of `<expr>`.
    /// Evaluation errors propagate; they are not refutations.
    Equal(Expr),
    /// `< <expr>` — matches if the subject is ordered before the value of `<expr>`.
    /// Only defined for comparable kinds (e.g., `Int`); others refute with `.not_int`.
    Less(Expr),
    /// `> <expr>` — matches if the subject is ordered after the value of `<expr>`.
    Greater(Expr),
    /// `<pat> as <Proto>` — matches if the subject's prototype is `<Proto>`, then
    /// matches `<pat>` against the subject.
    Type(ProtoRef, Box<Pattern>),
    /// `Self <pat>` — matches if the subject is an object of the home module and
    /// its payload matches `<pat>`. Prototype check is implicit.
    /// `depth` is the distance to the home module terminal.
    Unwrap { depth: u32, inner: Box<Pattern> },
    /// `(p1 | p2)` — tries arms sequentially. Both arms must bind the same names.
    /// Once an arm matches, the pattern is committed (no backtracking).
    Or(Box<Pattern>, Box<Pattern>),
    /// `&()` — matches only the unit value.
    Unit,
    /// `[p0, ...]` list pattern. `rest` handles the remainder: `None` for exact
    /// arity, `Some(Discard)` for minimum arity, or `Some(Bind(name))` to bind.
    List {
        elems: Vec<Pattern>,
        rest: Option<Box<Pattern>>,
    },
    /// `{ k0: p0, ... }` map pattern. `rest` handles the remainder similarly to lists.
    Map {
        entries: Vec<(MapKey, Pattern)>,
        rest: Option<Box<Pattern>>,
    },
    /// `<pat> when (<cond>)` guarded pattern. Matches `inner`, then the guard.
    /// Plain guards must be `Bool`; pattern guards match `gpat` against the condition.
    When {
        inner: Box<Pattern>,
        when: (Option<Box<Pattern>>, Expr),
    },
}

/// Map-pattern key. `Lookup` probes a concrete key; `Capture` peels the first
/// remaining entry and matches its key against the pattern.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum MapKey {
    Lookup(Expr),
    Capture(Box<Pattern>),
}

/// Prototype used in `as <Proto>` patterns.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ProtoRef {
    /// Fast form: a reference to a builtin module prototype (e.g., `Int`).
    /// Compiles to a discriminant test [`TyKind`].
    Kind(TyKind),
    /// Any other prototype, evaluated at match time and required to be a module.
    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),
        }
    }
}

/// Value kinds with builtin module prototypes, allowing `as <Proto>` to
/// compile to a discriminant test (see [`ProtoRef::Kind`]).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TyKind {
    Int,
    Sym,
    Str,
    List,
    Map,
    Fun,
    /// Module value (prototype `__Mod`).
    Mod,
    /// Unit value (prototype `__Unit`).
    Unit,
    /// Boolean (iota of `__Bool`).
    Bool,
}

impl TyKind {
    /// Spelling used in `as <Proto>` surface and 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",
            TyKind::Unit => "Unit",
            TyKind::Bool => "Bool",
        }
    }
}

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"}]}`.
    /// Used by the `elly-wasm` playground to render the AST.
    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) => {
                // Emit as bare number if it fits in f64 [-2^53, 2^53] exactly;
                // otherwise emit as a tagged decimal string 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('}');
                }
            }
            // Name, Local, and Builtin all 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('}');
            }
            Expr::Builtin(op) => {
                out.push_str("{\"name\":");
                json_str(op.name(), out);
                out.push('}');
            }
            // Home leaves render as `{"self":true}`, `{"new":true}`, or `{"value":true}`.
            // Depth is derived and not rendered.
            Expr::Home { leaf, .. } => match leaf {
                HomeLeaf::Module => out.push_str("{\"self\":true}"),
                HomeLeaf::New => out.push_str("{\"new\":true}"),
                HomeLeaf::Value => out.push_str("{\"value\":true}"),
            },
            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 to preserve stored arity.
            Expr::App(items) => write_app_json(items, out),
            // Render collected head as nested single-parameter abstractions.
            Expr::Abs(code) => write_abs_json(&code.head, &code.body, out),
            Expr::Unit => out.push_str("{\"unit\":true}"),
            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("]}");
            }
            // `{"block":[<clause>…]}`. Binds are `{"bind":{"pat":…,"value":…}}`,
            // others are the expression itself, in evaluation order.
            Expr::Block(clauses) => {
                out.push_str("{\"block\":[");
                for (i, (pat, value)) in clauses.iter().enumerate() {
                    if i > 0 {
                        out.push(',');
                    }
                    if let Some(pat) = pat {
                        out.push_str("{\"bind\":{\"pat\":");
                        pat.write_json(out);
                        out.push_str(",\"value\":");
                        value.write_json(out);
                        out.push_str("}}");
                    } else {
                        value.write_json(out);
                    }
                }
                out.push_str("]}");
            }
            // `{"case":{"subject":…,"arms":[{"pat":…,"body":…}, …]}}`.
            Expr::Case { subject, cases } => {
                out.push_str("{\"case\":{\"subject\":");
                subject.write_json(out);
                out.push_str(",\"arms\":[");
                for (i, (pat, body)) in cases.iter().enumerate() {
                    if i > 0 {
                        out.push(',');
                    }
                    out.push_str("{\"pat\":");
                    pat.write_json(out);
                    out.push_str(",\"body\":");
                    body.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(')');
            }
            // Name, Local, and Builtin all 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(')');
            }
            Expr::Builtin(op) => {
                out.push_str("(name ");
                out.push_str(op.name());
                out.push(')');
            }
            // Home leaves render as `(self)`, `(new)`, or `(value)`.
            // Depth is derived and not rendered.
            Expr::Home { leaf, .. } => match leaf {
                HomeLeaf::Module => out.push_str("(self)"),
                HomeLeaf::New => out.push_str("(new)"),
                HomeLeaf::Value => out.push_str("(value)"),
            },
            Expr::ModItem { name, .. } => {
                out.push_str("(moditem ");
                out.push_str(name.as_str());
                out.push(')');
            }
            // `(recur (bind a …) (bind b …) <body>)` — bindings in sorted order, then body.
            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(')');
            }
            // Strings are rendered as bare quoted literals.
            Expr::Str(s) => json_str(s, out),
            // Render the call spine flat to preserve stored arity.
            Expr::App(items) => write_app_sexp(items, out),
            // Render collected head as nested single-parameter abstractions.
            Expr::Abs(code) => write_abs_sexp(&code.head, &code.body, out),
            Expr::Unit => out.push_str("(unit)"),
            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(')');
            }
            // `(block (bind <pat> <value>) … <value>)` — clauses in evaluation order.
            Expr::Block(clauses) => {
                out.push_str("(block");
                for (pat, expr) in clauses.iter() {
                    out.push(' ');
                    if let Some(pat) = pat {
                        out.push_str("(bind ");
                        pat.write_sexp(out);
                        out.push(' ');
                        expr.write_sexp(out);
                        out.push(')');
                    } else {
                        expr.write_sexp(out);
                    }
                }
                out.push(')');
            }
            // `(case <subject> (arm <pat> <body>) …)`.
            Expr::Case { subject, cases } => {
                out.push_str("(case ");
                subject.write_sexp(out);
                for (pat, body) in cases.iter() {
                    out.push_str(" (arm ");
                    pat.write_sexp(out);
                    out.push(' ');
                    body.write_sexp(out);
                    out.push(')');
                }
                out.push(')');
            }
        }
    }
}

/// Renders a flat call spine `[callee, a0, a1, …]` as `(app callee a0 a1)`, preserving
/// stored arity. `#Self(…)` and `x.Self` render as `(new a0)` and `(value a0)`.
fn write_app_sexp(items: &[Expr], out: &mut String) {
    let (open, body) = match &items[0] {
        Expr::Home {
            leaf: HomeLeaf::New,
            ..
        } => ("(new", &items[1..]),
        Expr::Home {
            leaf: HomeLeaf::Value,
            ..
        } => ("(value", &items[1..]),
        _ => ("(app", items),
    };
    out.push_str(open);
    for it in body {
        out.push(' ');
        it.write_sexp(out);
    }
    out.push(')');
}

/// Renders a collected head `[p0, p1, …]` over `body` as nested `(abs p0 (abs p1 body))`.
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(')');
}

/// JSON twin of [`write_app_sexp`]: `{"app":[callee, a0, a1, …]}`, with the same
/// special cases for `new` and `value` spines.
fn write_app_json(items: &[Expr], out: &mut String) {
    let (tag, body) = match &items[0] {
        Expr::Home {
            leaf: HomeLeaf::New,
            ..
        } => ("new", &items[1..]),
        Expr::Home {
            leaf: HomeLeaf::Value,
            ..
        } => ("value", &items[1..]),
        _ => ("app", items),
    };
    out.push_str("{\"");
    out.push_str(tag);
    out.push_str("\":[");
    for (i, it) in body.iter().enumerate() {
        if i > 0 {
            out.push(',');
        }
        it.write_json(out);
    }
    out.push_str("]}");
}

/// JSON twin of [`write_abs_sexp`]: nested `{"abs":{"param":…,"body":…}}`.
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 a compact s-expression. `Bind`/`Discard` render as names;
    /// structured patterns are tagged (e.g., `(list a ...rest)`).
    fn write_sexp(&self, out: &mut String) {
        match self {
            Pattern::Discard => out.push('_'),
            Pattern::Unit => out.push_str("(unit)"),
            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);
                }
                write_rest_sexp(rest, 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(')');
                }
                write_rest_sexp(rest, out);
                out.push(')');
            }
            // `(when <inner> <cond>)` for plain guards; `(when <inner> (bind <gpat> <cond>))`
            // for pattern guards.
            Pattern::When {
                inner,
                when: (guard, cond),
            } => {
                out.push_str("(when ");
                inner.write_sexp(out);
                out.push(' ');
                match guard {
                    None => cond.write_sexp(out),
                    Some(gpat) => {
                        out.push_str("(bind ");
                        gpat.write_sexp(out);
                        out.push(' ');
                        cond.write_sexp(out);
                        out.push(')');
                    }
                }
                out.push(')');
            }
        }
    }

    fn write_json(&self, out: &mut String) {
        match self {
            Pattern::Discard => out.push_str("{\"discard\":true}"),
            Pattern::Unit => out.push_str("{\"unit\":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\":");
                write_rest_json(rest, 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\":");
                write_rest_json(rest, out);
                out.push_str("}}");
            }
            Pattern::When {
                inner,
                when: (guard, cond),
            } => {
                out.push_str("{\"when\":{\"inner\":");
                inner.write_json(out);
                out.push_str(",\"guard\":");
                match guard {
                    None => out.push_str("null"),
                    Some(gpat) => gpat.write_json(out),
                }
                out.push_str(",\"cond\":");
                cond.write_json(out);
                out.push_str("}}");
            }
        }
    }
}

/// Renders the trailing rest as `...` followed by the pattern (if not `Discard`).
fn write_rest_sexp(rest: &Option<Box<Pattern>>, out: &mut String) {
    if let Some(p) = rest {
        out.push_str(" ...");
        if !matches!(**p, Pattern::Discard) {
            p.write_sexp(out);
        }
    }
}

/// Renders `null` for closed patterns, otherwise the rest pattern's JSON.
fn write_rest_json(rest: &Option<Box<Pattern>>, out: &mut String) {
    match rest {
        None => out.push_str("null"),
        Some(p) => p.write_json(out),
    }
}

impl MapKey {
    fn write_sexp(&self, out: &mut String) {
        match self {
            // Lookup key: a plain expression.
            MapKey::Lookup(expr) => expr.write_sexp(out),
            // Capture key: matches the peeled key against a pattern.
            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('}');
            }
        }
    }
}

/// Returns true if `n` is exactly representable as an `f64` (within [-2^53, 2^53]).
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)
}

/// Writes `s` as a quoted and escaped JSON string literal.
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('"');
}