jetro-core 0.5.12

//! Pure-data opcode and program definitions for the Jetro VM.
//!
//! Holds compiled-program structures (`Opcode`, `Program`, `Compiled*`,
//! `FieldChainData`, comprehension specs, patch ops) and the small helpers
//! that operate only on those structures (`fresh_ics`, `hash_str`,
//! `disable_opcode_fusion`, `Program::new`). Execution and the `VM` struct
//! live in `super::exec`.

use std::{
    collections::hash_map::DefaultHasher,
    hash::{Hash, Hasher},
    sync::atomic::AtomicU64,
    sync::Arc,
    sync::OnceLock,
};

use indexmap::IndexMap;

pub use crate::builtins::BuiltinMethod;
use crate::parse::ast::*;

/// A method call compiled into a `CallMethod` opcode. Lambda/arg bodies are
/// pre-compiled into `sub_progs` exactly once at compile time so the inner
/// loop never re-compiles them. `demand_max_keep` is set by the demand-pass
/// peephole when a `take(n)` follows this call.
#[derive(Debug, Clone)]
pub struct CompiledCall {
    /// Resolved built-in variant; `Unknown` when the name is not a built-in.
    pub method: BuiltinMethod,
    /// Original method name from source, used for error messages and registry lookup.
    pub name: Arc<str>,
    /// Pre-compiled sub-programs for each lambda/expression argument; shared via `Arc`.
    pub sub_progs: Arc<[Arc<Program>]>,
    /// `BodyKernel`-classified form of each sub-program, computed once at
    /// compile time. Higher-order builtins (`.filter`, `.map`, `.any`,
    /// `.all`, `.find`, ...) consult this to dispatch the per-element
    /// hot path through `eval_kernel` for native-speed Rust evaluation,
    /// falling back to the `Program` arm for `BodyKernel::Generic`.
    pub sub_kernels: Arc<[crate::exec::pipeline::BodyKernel]>,
    /// Original un-compiled arguments kept for lambda-param introspection at runtime.
    pub orig_args: Arc<[Arg]>,
    /// When set, `filter`/`map` may stop early after collecting this many results.
    pub demand_max_keep: Option<usize>,
}

/// A field entry inside a `MakeObj` opcode. `Short` is the fast path for
/// `{name}` shorthand — reads from `current` using an inline-cache hint;
/// `KvPath` is the structural fast path for `{key: $.a.b}` chains.
#[derive(Debug, Clone)]
pub enum CompiledObjEntry {
    /// `{name}` shorthand: copies the field from `current`, using `ic` as an
    /// inline-cache slot to remember the last-seen map index.
    Short {
        /// Field name to read from the current object (or variable scope).
        name: Arc<str>,
        /// Inline-cache slot storing the last successful map index + 1 (0 = cold).
        ic: Arc<AtomicU64>,
    },
    /// General `{key: expr}` entry with an optional guard condition.
    Kv {
        /// Output key name.
        key: Arc<str>,
        /// Compiled value expression evaluated against the current environment.
        prog: Arc<Program>,
        /// When true, null values are omitted from the output object.
        optional: bool,
        /// If present, the entry is skipped when the condition evaluates falsy.
        cond: Option<Arc<Program>>,
    },
    /// Structural fast-path for `{key: @.a.b[0]}` — avoids spawning a sub-`exec` call
    /// when the value is a pure chain of field/index steps rooted at `@`.
    KvPath {
        /// Output key name.
        key: Arc<str>,
        /// Ordered field/index steps traversed starting from `current`.
        steps: Arc<[KvStep]>,
        /// When true, null values are omitted from the output object.
        optional: bool,
        /// Per-step inline-cache slots, one per element of `steps`.
        ics: Arc<[AtomicU64]>,
    },
    /// `{(expr): expr}` — both key and value are computed at runtime.
    Dynamic {
        /// Program producing the key; result is coerced to a string.
        key: Arc<Program>,
        /// Program producing the value.
        val: Arc<Program>,
    },
    /// `{...expr}` — shallow-merges all fields from an object value into the output.
    Spread(Arc<Program>),
    /// `{...!expr}` — recursively deep-merges an object value into the output.
    SpreadDeep(Arc<Program>),
}

/// A single traversal step in a `KvPath` entry, representing either a named
/// field access or an integer index into an array.
#[derive(Debug, Clone)]
pub enum KvStep {
    /// Access an object field by name.
    Field(Arc<str>),
    /// Access an array element; negative values count from the end.
    Index(i64),
}

/// A single segment of a compiled format-string (`f"..."`).
/// Segments alternate between literal text and interpolated expressions.
#[derive(Debug, Clone)]
pub enum CompiledFSPart {
    /// A verbatim string fragment that is appended directly to the output buffer.
    Lit(Arc<str>),
    /// An interpolated expression whose result is formatted and inserted at this position.
    Interp {
        /// The compiled sub-program that produces the interpolated value.
        prog: Arc<Program>,
        /// Optional format spec such as `.2f` or `>10`; `None` uses default formatting.
        fmt: Option<FmtSpec>,
    },
}

/// Specifies the destructuring pattern for an object bind step in a pipeline
/// (`... | {a, b, ...rest} -> ...`).
#[derive(Debug, Clone)]
pub struct BindObjSpec {
    /// Named fields that are extracted as individual variables.
    pub fields: Arc<[Arc<str>]>,
    /// If present, remaining fields are collected into this variable as an object.
    pub rest: Option<Arc<str>>,
}

/// A single compiled step inside a `PipelineRun` opcode. Each step either
/// transforms the current pipeline value or captures it into named variables.
#[derive(Debug, Clone)]
pub enum CompiledPipeStep {
    /// Pass the current value through an expression, updating the pipeline value.
    Forward(Arc<Program>),
    /// Bind the current pipeline value to a single named variable.
    BindName(Arc<str>),
    /// Destructure the current object value into named field variables (with optional rest).
    BindObj(Arc<BindObjSpec>),
    /// Destructure the current array value into positional variables by index.
    BindArr(Arc<[Arc<str>]>),
}

/// Compiled specification for a list, set, or generator comprehension
/// (`[expr for vars in iter if cond]`).
#[derive(Debug, Clone)]
pub struct CompSpec {
    /// Expression evaluated for each item to produce the output element.
    pub expr: Arc<Program>,
    /// Variable names bound per iteration; one name for simple loops, two for indexed.
    pub vars: Arc<[Arc<str>]>,
    /// Program whose result is iterated (must yield an array or object).
    pub iter: Arc<Program>,
    /// Optional filter; items for which this evaluates falsy are skipped.
    pub cond: Option<Arc<Program>>,
}

/// Compiled specification for a dictionary comprehension
/// (`{key: val for vars in iter if cond}`).
#[derive(Debug, Clone)]
pub struct DictCompSpec {
    /// Program evaluated to produce each output key; coerced to a string.
    pub key: Arc<Program>,
    /// Program evaluated to produce each output value.
    pub val: Arc<Program>,
    /// Variable names bound per iteration.
    pub vars: Arc<[Arc<str>]>,
    /// Program whose result is iterated (must yield an array or object).
    pub iter: Arc<Program>,
    /// Optional filter; items for which this evaluates falsy are skipped.
    pub cond: Option<Arc<Program>>,
}

/// Single instruction in a compiled `Program`. The VM executes a flat
/// `Arc<[Opcode]>` slice iteratively; no per-opcode stack frames.
#[derive(Debug, Clone)]
pub enum Opcode {
    /// Push the literal `null` value onto the stack.
    PushNull,
    /// Push a boolean literal onto the stack.
    PushBool(bool),
    /// Push a 64-bit integer literal onto the stack.
    PushInt(i64),
    /// Push a 64-bit float literal onto the stack.
    PushFloat(f64),
    /// Push a reference-counted string literal onto the stack.
    PushStr(Arc<str>),

    /// Push the root document value (`$`) onto the stack.
    PushRoot,
    /// Push the current iteration value (`@`) onto the stack.
    PushCurrent,

    /// Pop an object, push the named field (or `null` if absent).
    GetField(Arc<str>),
    /// Pop an array/string, push element at the given index; negative indices count from end.
    GetIndex(i64),
    /// Pop an array, push a sub-slice between the optional start and end
    /// indices, with an optional `step`. `step == None` and `step == Some(1)`
    /// take the existing step-1 fast path; other values walk explicitly.
    GetSlice(Option<i64>, Option<i64>, Option<i64>),
    /// Pop a container; evaluate the inner program to get a key, then index into the container.
    DynIndex(Arc<Program>),
    /// Like `GetField` but propagates `null` receivers silently instead of erroring.
    OptField(Arc<str>),
    /// Collect all descendants matching the given field name via DFS; result is an array.
    Descendant(Arc<str>),
    /// Collect every scalar and object node in the subtree into an array (DFS pre-order).
    DescendAll,
    /// Filter an array or singleton using the predicate sub-program; `@` is each item.
    InlineFilter(Arc<Program>),
    /// Apply a quantifier to the top-of-stack value (`?` for first, `!` for exactly-one).
    Quantifier(QuantifierKind),

    /// Fused `PushRoot` + one-or-more `GetField` steps; avoids repeated stack traffic.
    /// Results are memoised in `root_chain_cache` keyed by `Arc` pointer identity.
    RootChain(Arc<[Arc<str>]>),

    /// Fused run of consecutive `GetField`/`OptField` steps after a non-root value.
    /// Each step has its own inline-cache slot inside `FieldChainData`.
    FieldChain(Arc<FieldChainData>),

    /// Resolve an identifier: looks up a variable, falls back to a field on `current`.
    LoadIdent(Arc<str>),

    /// Pop two values and push their sum (number or string concatenation).
    Add,
    /// Pop two numbers and push their difference.
    Sub,
    /// Pop two numbers and push their product.
    Mul,
    /// Pop two numbers and push their quotient as a float; errors on divide-by-zero.
    Div,
    /// Pop two numbers and push the remainder.
    Mod,
    /// Pop two values and push `true` if they are equal.
    Eq,
    /// Pop two values and push `true` if they are not equal.
    Neq,
    /// Pop two values and push `true` if the left is strictly less than the right.
    Lt,
    /// Pop two values and push `true` if the left is less than or equal to the right.
    Lte,
    /// Pop two values and push `true` if the left is strictly greater than the right.
    Gt,
    /// Pop two values and push `true` if the left is greater than or equal to the right.
    Gte,
    /// Pop two string values and push `true` if either contains the other (case-insensitive).
    Fuzzy,
    /// Pop a value and push its boolean negation.
    Not,
    /// Pop a number and push its arithmetic negation.
    Neg,

    /// Pop a value and push it cast to the given type.
    CastOp(crate::parse::ast::CastType),

    /// Short-circuit AND: pop lhs; if falsy push `false`, else evaluate rhs sub-program.
    AndOp(Arc<Program>),
    /// Short-circuit OR: pop lhs; if truthy push it, else evaluate rhs sub-program.
    OrOp(Arc<Program>),
    /// Null coalescing: pop lhs; if non-null push it, else evaluate rhs sub-program.
    CoalesceOp(Arc<Program>),

    /// Pop receiver and dispatch it with the pre-compiled call descriptor.
    CallMethod(Arc<CompiledCall>),
    /// Like `CallMethod` but silently returns `null` when the receiver is `null`.
    CallOptMethod(Arc<CompiledCall>),

    /// Construct an object literal from the compiled field entries; does not consume the stack.
    MakeObj(Arc<[CompiledObjEntry]>),

    /// Construct an array literal; each element has a compiled program and a spread flag.
    MakeArr(Arc<[(Arc<Program>, bool)]>),

    /// Evaluate a format-string from its compiled parts and push the resulting string.
    FString(Arc<[CompiledFSPart]>),

    /// Pop a value and push a boolean indicating whether it matches the given kind.
    KindCheck {
        /// The kind to test against (e.g. `KindType::Arr`).
        ty: KindType,
        /// When true the boolean result is inverted (`is not`).
        negate: bool,
    },

    /// No-op marker inserted by the pipeline emitter to delimit scope boundaries;
    /// consumed during compilation and stripped from the final program.
    SetCurrent,

    /// Bind `@` (and optionally a named identifier) to the value already on
    /// `env.current`, run `body` in that extended environment, and restore
    /// the previous bindings on exit. Emitted by the AST-level lambda
    /// lowering whenever a single-param lambda body — after `outer` →
    /// `Current` substitution — still references `outer` from inside a
    /// nested lambda. The wrapper makes `env.get_var(outer)` resolve to the
    /// outer iteration item even when the host pipeline stage uses
    /// `swap_current` rather than `push_lam` to advance per row.
    BindLamCurrent {
        /// Identifier bound to the current value for this scope (single-
        /// param lambda parameter name); `None` for anonymous binding.
        name: Option<Arc<str>>,
        /// Lambda body program executed under the extended environment.
        body: Arc<Program>,
    },

    /// Evaluate `base`, then run each `CompiledPipeStep` in sequence, threading
    /// the current value and environment through the pipeline.
    PipelineRun {
        /// The left-hand-side expression whose result seeds the pipeline.
        base: Arc<Program>,
        /// Ordered pipeline steps (forward transforms and bind patterns).
        steps: Arc<[CompiledPipeStep]>,
    },

    /// Pop the initialiser off the stack, bind it to `name`, and evaluate `body`.
    LetExpr {
        /// Variable name introduced for the duration of `body`.
        name: Arc<str>,
        /// Body program evaluated in the extended environment.
        body: Arc<Program>,
    },

    /// Pop the condition, then evaluate either `then_` or `else_` branch.
    IfElse {
        /// Branch evaluated when the condition is truthy.
        then_: Arc<Program>,
        /// Branch evaluated when the condition is falsy.
        else_: Arc<Program>,
    },

    /// Evaluate `body`; on error or null result fall back to `default`.
    TryExpr {
        /// Primary expression to attempt.
        body: Arc<Program>,
        /// Fallback expression evaluated when `body` fails or returns null.
        default: Arc<Program>,
    },
    /// Execute a list comprehension using the given compiled spec.
    ListComp(Arc<CompSpec>),
    /// Execute a dictionary comprehension using the given compiled spec.
    DictComp(Arc<DictCompSpec>),
    /// Execute a set/generator comprehension (deduplication semantics).
    SetComp(Arc<CompSpec>),

    /// Execute a compiled patch expression (`.set`, `.modify`, `.delete`, `.unset`).
    PatchEval(Arc<CompiledPatch>),
    /// Execute a compiled functional update batch.
    UpdateBatchEval(Arc<CompiledUpdateBatch>),

    /// Guard that fires when a `DELETE` sentinel reaches execution outside a patch context.
    DeleteMarkErr,

    /// Execute a compiled pattern-match expression: evaluate the scrutinee,
    /// try each arm's pattern (and optional guard) in order, and run the body
    /// of the first matching arm with its bindings in scope.
    Match(Arc<CompiledMatch>),

    /// Walk every descendant of the receiver in DFS pre-order, run the
    /// compiled match against each, and collect every arm-body result
    /// that is truthy. Falsy bodies and unmatched values (the trailing
    /// `Fail`) are silently dropped. Pushes the resulting `Val::Arr`.
    DeepMatchAll(Arc<CompiledMatch>),

    /// Like `DeepMatchAll` but stops at the first descendant whose
    /// match produces a truthy arm-body result. Pushes the body
    /// directly (not wrapped in an array); pushes `Val::Null` when no
    /// descendant matches.
    DeepMatchFirst(Arc<CompiledMatch>),
}

/// Strategy for producing the scrutinee value of a compiled `match`
/// expression. Most query authors write `match @ with { ... }` (matching
/// the current row) or `match $.path with { ... }` (matching the
/// document root or a navigation chain). The first two cases avoid VM
/// re-entry by reading directly from the runtime environment.
#[derive(Debug, Clone)]
pub enum MatchScrutinee {
    /// Read the current row from `Env::current` (the `@` token).
    Current,
    /// Read the document root from `Env::root` (the `$` token).
    Root,
    /// Evaluate an arbitrary scrutinee program against the current env.
    Program(Arc<Program>),
}

/// Compiled representation of a `match scrutinee with { arms }` expression.
/// Arms are lowered to a flat `MatchOp` instruction stream with explicit
/// jumps between arms; each arm starts with `ResetArm`, which initialises
/// its local slot space and binding cursor. Bodies and guards are stored as
/// separate `Program` pools indexed from the op stream.
#[derive(Debug, Clone)]
pub struct CompiledMatch {
    /// Strategy for evaluating the value being matched.
    pub scrutinee: MatchScrutinee,
    /// Flat instruction stream describing arm tests, captures, guards, and bodies.
    pub ops: Arc<[MatchOp]>,
    /// Pool of pattern literals indexed by `MatchOp::LitEq.lit`.
    pub lits: Arc<[crate::parse::ast::PatLit]>,
    /// Pool of compiled guard sub-programs indexed by `MatchOp::Guard.prog`.
    pub guards: Arc<[Arc<Program>]>,
    /// Pool of compiled body sub-programs indexed by `MatchOp::Body.prog`.
    pub bodies: Arc<[Arc<Program>]>,
    /// Pool of free-standing `Pat` nodes referenced from `MatchOp::TestSubPat`,
    /// used for sub-patterns whose runtime test is more economical to walk
    /// recursively than to flatten (currently `Pat::Or`).
    pub subpats: Arc<[crate::parse::ast::Pat]>,
    /// Maximum number of slots any prelude or arm needs at once. The VM
    /// pre-sizes its slot vector to this value so that prelude ops (which
    /// run before the first `ResetArm`) can write into projection slots
    /// without underflow.
    pub max_slots: u16,
    /// `true` when at least one arm has an unconditional catch-all
    /// pattern (`_` or a bare `Bind`) with no guard. Tooling and
    /// future analysers consume this flag; the runtime always produces
    /// the same non-exhaustive error if every arm misses, regardless of
    /// the flag value.
    #[allow(dead_code)]
    pub is_exhaustive: bool,
    /// Shape summary describing what the structural backend can serve
    /// from a bitmap index without touching the document body. `None`
    /// means the match has no exploitable structure (mixed shapes,
    /// guard-only arms, etc.) and the runtime walks every descendant
    /// directly.
    pub shape_summary: Option<MatchShapeSummary>,
}

/// Compile-time summary of a `match`'s arm shapes, used by deep-search
/// (`..match`) dispatch to pre-filter candidates via a structural
/// bitmap before running the per-arm pattern test.
#[derive(Debug, Clone)]
pub enum MatchShapeSummary {
    /// Every arm is a `Pat::Obj` and the union of leading keys across
    /// arms is the listed set. A document node qualifies as a candidate
    /// when it is an object containing *any* of these keys; the per-arm
    /// runtime then narrows further.
    ObjAnyOfKeys(Arc<[Arc<str>]>),
    /// Every arm tests the same scalar kind. Non-matching kinds can
    /// be skipped entirely.
    KindOnly(crate::parse::ast::KindType),
    /// Every arm tests a numeric range. The union range is the smallest
    /// interval covering all per-arm bounds.
    NumericRange {
        /// Lower bound across all arms (inclusive).
        lo: f64,
        /// Upper bound across all arms.
        hi: f64,
        /// `true` when the upper bound is inclusive (any arm uses `..=`).
        inclusive: bool,
    },
}

/// Slot identifier used by the match instruction stream. Slot 0 always
/// holds the scrutinee; subsequent slots hold sub-projections produced by
/// `LoadField` / `LoadIndex` / `LoadTail`. Slot space is reset at the
/// start of each arm via `ResetArm`.
pub type MatchSlot = u16;

/// Single instruction of the flat match decision machine.
///
/// Execution model: a program counter walks `ops` left to right; each
/// failing test or load jumps to the start of the next arm (or to the
/// trailing `Fail` if no arm remains). Successful tests fall through to the
/// next instruction. `Body` terminates the loop with the body's evaluated
/// result; `Fail` raises a non-exhaustive-match error.
#[derive(Debug, Clone)]
pub enum MatchOp {
    /// Mark the start of a new arm. Clears the binding stack and grows
    /// the slot vector to `slots`. Slots in the range `0..keep_above` are
    /// preserved across arm boundaries; slots at or above `keep_above`
    /// are zeroed. `keep_above >= 1` always — slot 0 (scrutinee) is
    /// always preserved. Values greater than 1 are used by cross-arm
    /// prefix sharing to retain sub-projections (e.g. an object key's
    /// loaded value) across all arms participating in the shared prefix.
    ResetArm {
        /// Number of slots this arm requires (including slot 0).
        slots: u16,
        /// Number of leading slots whose contents must be preserved.
        keep_above: u16,
    },

    /// Verify the value at `slot` has runtime kind `kind`; jump on miss.
    KindCheck {
        /// Slot whose value is being kind-checked.
        slot: MatchSlot,
        /// Target kind.
        kind: crate::parse::ast::KindType,
        /// PC to jump to when the value is not of `kind`.
        else_pc: u32,
    },

    /// Compare the value at `slot` against literal pool entry `lit`; jump on miss.
    LitEq {
        /// Slot whose value is being compared.
        slot: MatchSlot,
        /// Index into `CompiledMatch::lits`.
        lit: u16,
        /// PC to jump to on inequality.
        else_pc: u32,
    },

    /// Test that the value at `slot` is a number in the range `[lo, hi)`
    /// when `inclusive == false`, or `[lo, hi]` when `inclusive == true`.
    /// Non-numeric values fail and jump to `else_pc`.
    RangeCheck {
        /// Slot whose value is being range-tested.
        slot: MatchSlot,
        /// Lower bound (inclusive).
        lo: f64,
        /// Upper bound (semantics determined by `inclusive`).
        hi: f64,
        /// `true` when `hi` is inclusive (`..=` syntax).
        inclusive: bool,
        /// PC to jump to when the value is non-numeric or out of range.
        else_pc: u32,
    },

    /// Verify the value at `slot` is an object (any object representation); jump on miss.
    ObjCheck {
        /// Slot expected to hold an object value.
        slot: MatchSlot,
        /// PC to jump to when the value is not an object.
        else_pc: u32,
    },

    /// Look up `key` in the object value at `src` and store the result into
    /// `dst`. On a missing key (any object representation) jump to `else_pc`.
    LoadField {
        /// Source slot holding the parent object.
        src: MatchSlot,
        /// Object key being projected.
        key: Arc<str>,
        /// Destination slot for the projected value.
        dst: MatchSlot,
        /// PC to jump to when `key` is absent.
        else_pc: u32,
    },

    /// Verify array length at `slot`. When `exact`, must equal `len`;
    /// otherwise must be `>= len`. Accepts any array-like representation.
    LenCheck {
        /// Slot expected to hold an array-like value.
        slot: MatchSlot,
        /// Required length / minimum length.
        len: u32,
        /// `true` for exact length, `false` for `>=` (used with rest patterns).
        exact: bool,
        /// PC to jump to when the length test fails.
        else_pc: u32,
    },

    /// Read element at `idx` from the array-like value at `src` and store
    /// it into `dst`. Caller is responsible for emitting a preceding `LenCheck`.
    LoadIndex {
        /// Source slot holding the array-like value.
        src: MatchSlot,
        /// Zero-based array index to project.
        idx: u32,
        /// Destination slot for the projected element.
        dst: MatchSlot,
    },

    /// Capture the array tail starting at `from` from the value at `src`
    /// into `dst` as a freshly-built `Val::Arr`.
    LoadTail {
        /// Source slot holding the array-like value.
        src: MatchSlot,
        /// First index included in the captured tail.
        from: u32,
        /// Destination slot for the tail array.
        dst: MatchSlot,
    },

    /// Capture the object "rest" — every key/value pair on `src` whose
    /// key is *not* present in `listed_keys` — into `dst` as a freshly
    /// built `Val::Obj`. Emitted by the compiler when an object pattern
    /// binds a named rest marker (`{a: x, ...rest}`).
    LoadObjRest {
        /// Source slot holding the object value.
        src: MatchSlot,
        /// Keys already covered by explicit pattern fields; excluded
        /// from the captured rest object.
        listed_keys: Arc<[Arc<str>]>,
        /// Destination slot for the rest object.
        dst: MatchSlot,
    },

    /// Walk a tree-form sub-pattern at `subpat` against the value at `slot`,
    /// pushing any captured bindings into the arm's binding stack. Used for
    /// sub-patterns (currently `Or`) whose flat representation would expand
    /// the op stream more than a recursive walk.
    TestSubPat {
        /// Slot whose value is being tested.
        slot: MatchSlot,
        /// Index into `CompiledMatch::subpats`.
        subpat: u16,
        /// PC to jump to on test failure.
        else_pc: u32,
    },

    /// Push a binding onto the arm's binding stack: `name` = value at `slot`.
    Bind {
        /// Variable name introduced into the arm body's scope.
        name: Arc<str>,
        /// Slot whose value is captured.
        slot: MatchSlot,
    },

    /// Run guard sub-program at `prog`; jump on falsy / errored result.
    Guard {
        /// Index into `CompiledMatch::guards`.
        prog: u16,
        /// PC to jump to when the guard fails.
        else_pc: u32,
    },

    /// Run body sub-program at `prog` with the arm's bindings in scope and
    /// terminate match evaluation with its result.
    Body {
        /// Index into `CompiledMatch::bodies`.
        prog: u16,
    },

    /// Raise a non-exhaustive-match error. Emitted as the trailing op so a
    /// failed scan over every arm lands here.
    Fail,

    /// Unconditional jump to `target_pc`. Used by literal or-pattern
    /// cascades to skip remaining alternatives once one has matched.
    Jump {
        /// Absolute PC to jump to.
        target_pc: u32,
    },
}

/// A compiled, immutable bytecode program. Shared between the compile cache and
/// the path-resolution cache via `Arc`; cloning is O(1).
#[derive(Debug, Clone)]
pub struct Program {
    /// The flat opcode slice executed by the VM.
    pub ops: Arc<[Opcode]>,
    /// The source expression string this program was compiled from; used for cache keys.
    pub source: Arc<str>,
    /// Stable hash of `source` used for fast equality checks.
    pub id: u64,

    /// `true` when every opcode is a pure structural navigation step; allows the
    /// path-resolution cache to memoize results for this program.
    pub is_structural: bool,

    /// Per-opcode inline-cache slots (one `AtomicU64` per opcode); used by `GetField`
    /// and `OptField` to remember the last-seen map index.
    pub ics: Arc<[AtomicU64]>,
}

/// A compiled `patch` expression: a root document program plus a list of
/// individual field-mutation operations applied in order.
///
/// Phase D adds a lazily-built `trie` cache. When the patch contains
/// multiple ops over disjoint or sibling fields, the executor compiles the
/// op list into a `CompiledPatchTrie` once and reuses it on subsequent
/// invocations to amortise the trie-build cost across cache hits.
#[derive(Debug)]
pub struct CompiledPatch {
    /// Program that yields the base document to patch.
    pub root_prog: Arc<Program>,
    /// Ordered list of compiled field operations applied to the document.
    pub ops: Vec<CompiledPatchOp>,
    /// Lazily-built trie used when `ops.len() >= 2` and every op uses
    /// only `Field`/`Index`/`DynIndex` path steps with no `cond` guard.
    /// `None` after build means the op set is not trie-eligible and the
    /// per-op fallback should always be used.
    pub trie: OnceLock<Option<CompiledPatchTrie>>,
}

/// A compiled functional update batch: evaluate `root_prog`, select zero or
/// more target subtrees via `selector`, then apply the ordered relative `ops`
/// to each selected snapshot.
#[derive(Debug)]
pub struct CompiledUpdateBatch {
    /// Program that yields the base document to update.
    pub root_prog: Arc<Program>,
    /// Selector path locating each updated subtree.
    pub selector: Vec<CompiledPathStep>,
    /// Ordered relative update operations applied to every selected subtree.
    pub ops: Vec<CompiledPatchOp>,
    /// Lazily-built trie for the relative operations, reused for every
    /// selected subtree when the op set is trie-eligible.
    pub trie: OnceLock<Option<CompiledPatchTrie>>,
}

impl Clone for CompiledUpdateBatch {
    fn clone(&self) -> Self {
        Self {
            root_prog: Arc::clone(&self.root_prog),
            selector: self.selector.clone(),
            ops: self.ops.clone(),
            trie: OnceLock::new(),
        }
    }
}

impl Clone for CompiledPatch {
    fn clone(&self) -> Self {
        // The lazy trie cache is not propagated across clones; each clone
        // rebuilds on first multi-op execution. This keeps `Clone` cheap
        // and avoids duplicating partially-initialised state.
        Self {
            root_prog: Arc::clone(&self.root_prog),
            ops: self.ops.clone(),
            trie: OnceLock::new(),
        }
    }
}

/// A single field-mutation within a `CompiledPatch`: a path, a replacement/delete
/// value, and an optional runtime guard condition.
#[derive(Debug, Clone)]
pub struct CompiledPatchOp {
    /// Sequence of path steps that locate the target node in the document.
    pub path: Vec<CompiledPathStep>,
    /// The value action to perform at the target: replace or delete.
    pub val: CompiledPatchVal,
    /// When present, the operation is skipped unless this program evaluates truthy.
    pub cond: Option<Arc<Program>>,
}

/// The replacement action for a single `CompiledPatchOp`.
#[derive(Debug, Clone)]
pub enum CompiledPatchVal {
    /// Replace the node with the result of evaluating this program; `@` is the old value.
    Replace(Arc<Program>),
    /// Remove the node from its parent (object field or array element).
    Delete,
}

/// A single step in the path portion of a `CompiledPatchOp`.
#[derive(Debug, Clone)]
pub enum CompiledPathStep {
    /// Navigate into an object field by name.
    Field(Arc<str>),
    /// Navigate into an array element by signed index.
    Index(i64),
    /// Navigate to an array element whose index is computed at runtime.
    DynIndex(Arc<Program>),
    /// Apply the operation to every element of an array (`[*]`).
    Wildcard,
    /// Apply the operation to every array element that satisfies the predicate.
    WildcardFilter(Arc<Program>),
    /// Recursively descend and apply the operation wherever the named field exists.
    Descendant(Arc<str>),
}

/// Phase D: a path-trie that batches multi-op patches into a single tree-walk.
/// Sibling writes share their parent's `Arc::make_mut`; subtrees not on any
/// write path stay `Arc`-shared and are never visited.
#[derive(Debug, Clone)]
pub struct CompiledPatchTrie {
    /// Root of the trie. Always a `Branch` for non-empty patches; a single
    /// op with an empty path produces `Replace`/`Delete` directly at root.
    pub root: TrieNode,
}

/// One node in a `CompiledPatchTrie`.
#[derive(Debug, Clone)]
pub enum TrieNode {
    /// Replace this subtree with the result of executing `prog`. The
    /// program is evaluated with `@` bound to the current value at this
    /// position, mirroring the existing `CompiledPatchVal::Replace` semantics.
    Replace {
        /// Source op index used by update execution to cache invariant RHS
        /// values while preserving source-order conflict semantics.
        op_idx: usize,
        /// Program that produces the replacement value.
        prog: Arc<Program>,
    },
    /// Remove this node from its parent (object field or array element).
    /// Treated as a structural marker; deletion happens in the parent's
    /// `Branch` arm rather than by recursing into this node.
    Delete,
    /// Conditional wrapper: evaluate `cond_prog` against the pre-batch doc
    /// and, only if it's truthy, apply `then` at this position. Phase F
    /// preserves invariant 5 (cond reads pre-batch state) by using the
    /// original `env` and the pre-batch doc as `@` when running `cond_prog`.
    Conditional {
        /// Guard program; evaluated with `@` = pre-batch doc, `$` = env.root.
        cond_prog: Arc<Program>,
        /// Subtree applied when the guard is truthy.
        then: Box<TrieNode>,
    },
    /// Recurse into named (object) and indexed (array) children. Children
    /// not in either map remain `Arc`-shared with no traversal.
    Branch {
        /// Per-field children for object containers, ordered by first-seen op.
        fields: IndexMap<Arc<str>, TrieNode>,
        /// Per-index children for array containers; static indices coalesce
        /// when equal, dynamic indices coalesce by `Arc::ptr_eq` on the program.
        indices: Vec<(IdxKey, TrieNode)>,
    },
}

/// Key into the `indices` slot of a `TrieNode::Branch`.
#[derive(Debug, Clone)]
pub enum IdxKey {
    /// Static index (Python-style negative indexing).
    Static(i64),
    /// Dynamic index — execute the program at apply time to get an `i64`.
    /// Two `Dynamic` keys coalesce only when the program `Arc`s are pointer-equal.
    Dynamic(Arc<Program>),
}

impl CompiledPatchTrie {
    /// Build a trie from `ops` in source order. Returns `None` when any op
    /// uses `Wildcard` / `WildcardFilter` / `Descendant` path steps; such
    /// patches fall back to the per-op walker which handles those cases
    /// natively. Phase F: conditional ops (`op.cond.is_some()`) are now
    /// trie-eligible and produce `TrieNode::Conditional` leaves.
    ///
    /// Source-order semantics: later ops shadow earlier ops at the same
    /// leaf, but ops with deeper paths convert a leaf into a `Branch`. A
    /// later op replacing a prior `Branch` discards the prior children.
    pub fn from_ops(ops: &[CompiledPatchOp]) -> Option<Self> {
        if has_strict_prefix_overlap(ops) {
            return None;
        }
        for op in ops {
            for step in &op.path {
                match step {
                    CompiledPathStep::Field(_)
                    | CompiledPathStep::Index(_)
                    | CompiledPathStep::DynIndex(_) => {}
                    CompiledPathStep::Wildcard
                    | CompiledPathStep::WildcardFilter(_)
                    | CompiledPathStep::Descendant(_) => return None,
                }
            }
        }
        let mut root = TrieNode::Branch {
            fields: IndexMap::new(),
            indices: Vec::new(),
        };
        for (op_idx, op) in ops.iter().enumerate() {
            let leaf = match &op.val {
                CompiledPatchVal::Replace(prog) => TrieNode::Replace {
                    op_idx,
                    prog: Arc::clone(prog),
                },
                CompiledPatchVal::Delete => TrieNode::Delete,
            };
            // Phase F: wrap conditional ops so the trie applier evaluates
            // the guard before descending into `then`. The guard semantics
            // (pre-batch state) are preserved by `apply_trie`.
            let leaf = if let Some(cond_prog) = &op.cond {
                TrieNode::Conditional {
                    cond_prog: Arc::clone(cond_prog),
                    then: Box::new(leaf),
                }
            } else {
                leaf
            };
            insert_leaf(&mut root, &op.path, leaf);
        }
        Some(Self { root })
    }
}

fn has_strict_prefix_overlap(ops: &[CompiledPatchOp]) -> bool {
    for i in 0..ops.len() {
        for j in 0..ops.len() {
            if i != j && path_is_strict_prefix(&ops[i].path, &ops[j].path) {
                return true;
            }
        }
    }
    false
}

fn path_is_strict_prefix(prefix: &[CompiledPathStep], path: &[CompiledPathStep]) -> bool {
    prefix.len() < path.len()
        && prefix
            .iter()
            .zip(path)
            .all(|(left, right)| path_step_eq(left, right))
}

fn path_step_eq(left: &CompiledPathStep, right: &CompiledPathStep) -> bool {
    match (left, right) {
        (CompiledPathStep::Field(left), CompiledPathStep::Field(right)) => left == right,
        (CompiledPathStep::Index(left), CompiledPathStep::Index(right)) => left == right,
        (CompiledPathStep::DynIndex(left), CompiledPathStep::DynIndex(right)) => {
            Arc::ptr_eq(left, right)
        }
        _ => false,
    }
}

/// Insert `leaf` at the position addressed by `path` inside `node`,
/// converting non-`Branch` interior positions into fresh `Branch` nodes
/// as needed. When two ops collide at the same position, the later one
/// fully replaces the earlier (last-write-wins).
fn insert_leaf(node: &mut TrieNode, path: &[CompiledPathStep], leaf: TrieNode) {
    if path.is_empty() {
        *node = leaf;
        return;
    }
    // Force `node` to be a `Branch` so we can descend.
    if !matches!(node, TrieNode::Branch { .. }) {
        *node = TrieNode::Branch {
            fields: IndexMap::new(),
            indices: Vec::new(),
        };
    }
    let TrieNode::Branch { fields, indices } = node else {
        unreachable!()
    };
    match &path[0] {
        CompiledPathStep::Field(name) => {
            if let Some(child) = fields.get_mut(name) {
                insert_leaf(child, &path[1..], leaf);
            } else {
                let mut fresh = TrieNode::Branch {
                    fields: IndexMap::new(),
                    indices: Vec::new(),
                };
                insert_leaf(&mut fresh, &path[1..], leaf);
                fields.insert(Arc::clone(name), fresh);
            }
        }
        CompiledPathStep::Index(i) => {
            // Coalesce by exact i64 match.
            if let Some((_, child)) = indices
                .iter_mut()
                .find(|(k, _)| matches!(k, IdxKey::Static(s) if *s == *i))
            {
                insert_leaf(child, &path[1..], leaf);
            } else {
                let mut fresh = TrieNode::Branch {
                    fields: IndexMap::new(),
                    indices: Vec::new(),
                };
                insert_leaf(&mut fresh, &path[1..], leaf);
                indices.push((IdxKey::Static(*i), fresh));
            }
        }
        CompiledPathStep::DynIndex(prog) => {
            // Coalesce only on pointer equality of the program Arc.
            if let Some((_, child)) = indices.iter_mut().find(|(k, _)| match k {
                IdxKey::Dynamic(p) => Arc::ptr_eq(p, prog),
                _ => false,
            }) {
                insert_leaf(child, &path[1..], leaf);
            } else {
                let mut fresh = TrieNode::Branch {
                    fields: IndexMap::new(),
                    indices: Vec::new(),
                };
                insert_leaf(&mut fresh, &path[1..], leaf);
                indices.push((IdxKey::Dynamic(Arc::clone(prog)), fresh));
            }
        }
        // `from_ops` filters these out before we reach here.
        CompiledPathStep::Wildcard
        | CompiledPathStep::WildcardFilter(_)
        | CompiledPathStep::Descendant(_) => unreachable!(),
    }
}

impl Program {
    /// Construct a new `Program`, computing `is_structural` and allocating fresh inline-cache slots.
    pub fn new(ops: Vec<Opcode>, source: &str) -> Self {
        let id = hash_str(source);
        let is_structural = ops.iter().all(|op| {
            matches!(
                op,
                Opcode::PushRoot
                    | Opcode::PushCurrent
                    | Opcode::GetField(_)
                    | Opcode::GetIndex(_)
                    | Opcode::GetSlice(..)
                    | Opcode::OptField(_)
                    | Opcode::RootChain(_)
                    | Opcode::FieldChain(_)
            )
        });
        let ics = fresh_ics(ops.len());
        Self {
            ops: ops.into(),
            source: source.into(),
            id,
            is_structural,
            ics,
        }
    }
}

/// Cached pointer-path data for a `FieldChain` opcode. Stores the ordered field
/// keys and one inline-cache slot per key for fast map-index lookup.
#[derive(Debug)]
pub struct FieldChainData {
    /// Ordered sequence of field names traversed by this chain.
    pub keys: Arc<[Arc<str>]>,
    /// Per-key inline-cache slots; each stores the last-seen index + 1 (0 = cold).
    pub ics: Box<[AtomicU64]>,
}

impl FieldChainData {
    /// Allocate a new `FieldChainData` with cold (zero) inline-cache slots.
    pub fn new(keys: Arc<[Arc<str>]>) -> Self {
        let n = keys.len();
        let mut ics = Vec::with_capacity(n);
        for _ in 0..n {
            ics.push(AtomicU64::new(0));
        }
        Self {
            keys,
            ics: ics.into_boxed_slice(),
        }
    }
}

/// Deref to the key slice so callers can iterate keys without naming the field.
impl std::ops::Deref for FieldChainData {
    type Target = [Arc<str>];
    #[inline]
    fn deref(&self) -> &[Arc<str>] {
        &self.keys
    }
}

/// Allocate `len` cold inline-cache slots (all zero) and return them as a shared slice.
pub fn fresh_ics(len: usize) -> Arc<[AtomicU64]> {
    let mut v = Vec::with_capacity(len);
    for _ in 0..len {
        v.push(AtomicU64::new(0));
    }
    v.into()
}

/// Return `true` when the `JETRO_DISABLE_OPCODE_FUSION` environment variable is set,
/// suppressing all peephole fusion passes for debugging purposes.
#[inline]
pub(crate) fn disable_opcode_fusion() -> bool {
    std::env::var_os("JETRO_DISABLE_OPCODE_FUSION").is_some()
}

fn hash_str(s: &str) -> u64 {
    let mut h = DefaultHasher::new();
    s.hash(&mut h);
    h.finish()
}