praxis_runtime/

parser.rs

//! The runtime input-parser interpreter (§7).
//!
//! Evaluates a compiled [`ParserPlan`] against the process-input buffer (or a
//! `Text` value), allocating GC results (`Int`, `Float`, `Byte`, `Char`,
//! source-slice `Text`, `Vec`, `Grid`, `Record`, `Tuple`, enum values) and
//! raising `FaultKind::ParseFailed` on mismatch.
//!
//! The plan type and global arena live in `praxis-input-parser`; this
//! interpreter looks up a plan by its [`PlanId`] and walks its node arena.
//!
//! **The arena is not `#[repr(C)]`.** It is ordinary Rust enums and slices, and
//! nothing here crosses an FFI boundary — only the plan *id* is a JIT immediate.
//! `praxis_input_parser::plan`'s own doc is the authority on its layout.

mod cursor;

use crate::GcRef;
use crate::context::RuntimeContext;
use crate::parse_detail::ParseFail;
use crate::roots::{NativeScope, RuntimeRoots};
use crate::scalars;
use crate::text::TextPayload;
use cursor::{ByteRegion, Cursor, Input, Walked, split_lines, split_sections, trailing_blank_run};
use praxis_input_parser::synthesize::AtomicClass;
use praxis_input_parser::{AtomicKind, ParserPlan, PlanNode, SectionItemNode, TemplateShape};

/// Run the parser plan named by `raw_id` against `input`, returning the parsed
/// result or `None` on failure (a value that names no plan → `None`; parse
/// mismatch → sets `ParseFailed` fault + `None`).
///
/// `raw_id` arrives as the payload of a boxed `Int` — an `i64` the ABI cannot
/// constrain — so it is validated here rather than narrowed with an `as`, which
/// would fold `0x1_0000_0005` onto plan 5 and every negative onto a huge index.
/// Zero is rejected too: [`PlanId`](praxis_input_parser::PlanId) is non-zero
/// precisely so a failure sentinel cannot name a plan.
///
/// # Safety
/// `ctx` must be live and wired; `input` must be a valid `Text` GcRef.
pub unsafe fn run_plan_by_id(ctx: *mut RuntimeContext, raw_id: i64, input: GcRef) -> Option<GcRef> {
    let id = u32::try_from(raw_id)
        .ok()
        .and_then(praxis_input_parser::PlanId::from_raw)?;
    let plan = praxis_input_parser::get_plan(id)?;
    // SAFETY: caller guarantees ctx/input validity.
    Some(unsafe { run_plan(ctx, plan, input) })
}

/// Run a parser plan against an input buffer.
///
/// Clears the runtime's [`ParseDetail`] slot at the start so a stale failure
/// from a prior parse does not leak in; on a mismatch, the deepest failure is
/// recorded there (§7.11) before the `ParseFailed` fault is raised.
///
/// # Safety
/// `ctx` must be live and wired; `input` must be a valid `Text` GcRef.
unsafe fn run_plan(ctx: *mut RuntimeContext, plan: &ParserPlan, input: GcRef) -> GcRef {
    // The buffer **and its owner** both come from the `input` argument. Taking
    // the bytes from here and the owner from `ctx.input_source` would make
    // `parse(text, P)` produce `Text` values that are views of the stdin buffer
    // at the offsets of a different string.
    // SAFETY: the caller guarantees `input` is a valid Text GcRef.
    let Some(i) = (unsafe { Input::new(input) }) else {
        unsafe { clear_parse_detail(ctx) };
        return unsafe { fault_sentinel(ctx) };
    };
    // **The root region is the whole buffer, and no terminator is trimmed off
    // it.** Trailing whitespace is handled where it arises — `walk_exact` lets
    // a child that leaves only whitespace fill its bound, `trailing_blank_run`
    // lets a line-splitting construct leave a trailing blank line to nobody
    // when its parser makes nothing of it, and `split_lines` does not end a
    // region in empty lines — so nothing is left here to special-case. A trim
    // count is the wrong kind of answer (ADR-078).
    //
    // It also matters *whose* buffer this is: `run_plan` is the single body
    // behind both `read <parser>` and the host `parse(text, P)`, so a trim here
    // would delete a byte from a Text the program wrote itself, and
    // `parse(t, rest)` would stop being the identity on `t`.
    let region = i.whole();
    // Root the input for the whole parse. `RuntimeRoots`'s `input` arm reads
    // `ctx.input_source`, which for `parse(text, P)` is a *different* Text —
    // and this one owns every source-slice the parse produces.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(ctx) };
    let _input = scope.root(input);
    // Clear any stale detail from a prior parse, then run.
    unsafe { clear_parse_detail(ctx) };
    let result = unsafe { walk(ctx, &i, plan, plan.root, region) };
    match result {
        // The root does **not** require exhaustion. Every real input ends with
        // a newline (`praxis-cli`'s runner reads the file verbatim), so a root
        // that demanded its region be consumed would fault on every file in the
        // corpus. Exhaustion is a *parent's* decision, made by `walk_exact`.
        Ok(walked) => walked.value,
        Err(fail) => {
            // Record the deepest failure into the runtime's detail slot, then
            // raise the fault. The host reads the detail after `ParseFailed`.
            // The preview is taken against the **whole** buffer: failure
            // offsets are absolute, and `i.whole()` is the region the parse
            // ran against, so the two cannot drift.
            unsafe { record_fail(ctx, fail, i.whole().bytes(&i)) };
            unsafe { fault_sentinel(ctx) }
        }
    }
}

/// Run `plan`'s root against `input` and hand back the value or the failure,
/// with no fault raised and no detail recorded — which is what lets the
/// interpreter's own unit tests assert on a [`ParseFail`] directly.
#[cfg(test)]
unsafe fn run_root(
    ctx: *mut RuntimeContext,
    plan: &ParserPlan,
    input: GcRef,
) -> Result<GcRef, ParseFail> {
    // SAFETY: the caller guarantees `input` is a valid Text GcRef.
    let i = unsafe { Input::new(input) }.expect("the test's input is a Text");
    // The same root region `run_plan` uses, for the same reason.
    let region = i.whole();
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(ctx) };
    let _input = scope.root(input);
    // SAFETY: the caller guarantees ctx is live and wired.
    unsafe { walk(ctx, &i, plan, plan.root, region) }.map(|w| w.value)
}

/// Set a `ParseFailed` fault and return the sentinel.
unsafe fn fault_sentinel(ctx: *mut RuntimeContext) -> GcRef {
    unsafe { set_parse_fault(ctx) };
    unsafe { (*ctx).unit_ref }
}

/// Mark a parse fault on the context.
unsafe fn set_parse_fault(ctx: *mut RuntimeContext) {
    let fault = unsafe { &mut *(*ctx).pending_fault };
    fault.set(crate::context::RaisedFault::PARSE_FAILED);
}

/// Clear the runtime's [`ParseDetail`] slot at the start of a parse.
///
/// `pub(crate)` for `praxis_run_parser`'s §6.3 descriptor guard, which returns
/// before `run_plan` and so has to do its own clearing — otherwise it reports
/// the *previous* parse's offset and expectation for a parse that never ran.
///
/// # Safety
/// `ctx` must be live and wired with a non-null `parse_detail`.
pub(crate) unsafe fn clear_parse_detail(ctx: *mut RuntimeContext) {
    // SAFETY: caller guarantees `ctx` is live.
    if unsafe { (*ctx).parse_detail.is_null() } {
        return;
    }
    // SAFETY: caller guarantees parse_detail points at a live ParseDetail.
    unsafe { (*(*ctx).parse_detail).clear() };
}

/// Record a [`ParseFail`] into the runtime's [`ParseDetail`] slot, keeping the
/// deepest (most specific) failure (§7.11).
///
/// # Safety
/// `ctx` must be live and wired; `input` is the buffer the failure was against
/// (used for the actual-preview).
unsafe fn record_fail(ctx: *mut RuntimeContext, fail: ParseFail, input: &[u8]) {
    // SAFETY: caller guarantees `ctx` is live.
    if unsafe { (*ctx).parse_detail.is_null() } {
        return;
    }
    // SAFETY: caller guarantees parse_detail points at a live ParseDetail.
    unsafe { (*(*ctx).parse_detail).consider(fail, input) };
}

/// The outcome of walking a node: a value + **the absolute position parsing
/// stopped at**, or an error carrying the §7.11 structured detail. The deepest
/// (highest-offset) failure wins at the [`run_plan`] boundary; inner failures
/// propagate up with their already-specific detail, so an outer constructor
/// only overrides when it has *more* specific information (it generally does
/// not).
type WalkResult = Result<Walked, ParseFail>;

/// The runtime, extracted from the context for allocation calls.
struct Rt {
    ctx: *mut RuntimeContext,
}

/// Access the heap from the context (same-crate, so we read the raw pointer).
unsafe fn heap_ref<'a>(ctx: *mut RuntimeContext) -> &'a crate::Heap {
    // SAFETY: caller guarantees ctx is valid and wired.
    unsafe { &*(*ctx).heap }
}

impl Rt {
    /// Give the collector its chance, against the whole root set.
    ///
    /// Every allocation in this file goes through here, which is safe only
    /// because the `NativeScope`s in the helpers below root the interpreter's
    /// `Vec<GcRef>` intermediates. Were they invisible to the root set, a
    /// collection anywhere inside a parse would reclaim the values the parse is
    /// in the middle of assembling (ADR-040, hazard H1).
    fn safepoint(&self) -> (&crate::Heap, crate::heap::Safepoint<'_>) {
        // SAFETY: ctx is valid (caller upholds).
        let heap = unsafe { heap_ref(self.ctx) };
        // SAFETY: as above.
        let roots = unsafe { RuntimeRoots::from_context(self.ctx) };
        let safepoint = heap.pace(&roots);
        (heap, safepoint)
    }

    /// The boxed `Int` for `value` — the interned immortal when it is small
    /// ([`crate::small_int`]), a fresh allocation otherwise.
    ///
    /// The safepoint is taken either way, for [`Rt::safepoint`]'s reason and
    /// not out of symmetry: an `int` atomic repeated over a large input is one
    /// of the few things in a parse that allocates on every step, so it is
    /// exactly where the collector must keep being offered a turn even once most
    /// of the digits it parses answer from the table.
    fn alloc_int(&self, value: i64) -> GcRef {
        let (heap, safepoint) = self.safepoint();
        match crate::small_int::index_of(value) {
            // SAFETY: `ctx` is valid (the `Rt`'s invariant) and `index_of`
            // bounds `i` by the table's length.
            Some(i) => {
                drop(safepoint);
                unsafe { *(*self.ctx).small_ints.add(i) }
            }
            None => heap.alloc(safepoint, scalars::INT_PAYLOAD, value),
        }
    }

    /// The boxed `Char` for `value` — the interned immortal when it is ASCII
    /// ([`crate::small_char`]), a fresh allocation otherwise.
    ///
    /// [`Rt::alloc_int`]'s shape, and the site ADR-107 was written for: the
    /// `char` atomic runs once per **grid cell**, so without interning
    /// `read grid(char)` over a 140×140 AoC map boxes 19,600 objects of which at
    /// most 128 have distinct values.
    ///
    /// The safepoint is taken either way, for [`Rt::alloc_int`]'s reason: a grid
    /// parse is one of the few things that allocates on every step, so it is
    /// exactly where the collector must keep being offered a turn even once every
    /// cell answers from the table. The `Grid`'s own item vector is what still
    /// grows, and it is what a collection here would have to find rooted — which
    /// is `walk_grid`'s `NativeScope`'s job.
    fn alloc_char(&self, value: u32) -> GcRef {
        let (heap, safepoint) = self.safepoint();
        match crate::small_char::index_of(value) {
            // SAFETY: `ctx` is valid (the `Rt`'s invariant) and `index_of`
            // bounds `i` by the table's length.
            Some(i) => {
                drop(safepoint);
                unsafe { *(*self.ctx).small_chars.add(i) }
            }
            None => heap.alloc(safepoint, scalars::CHAR_PAYLOAD, value),
        }
    }

    /// Allocate a boxed `Float` (§7.4's `float` atomic).
    fn alloc_float(&self, value: f64) -> GcRef {
        let (heap, safepoint) = self.safepoint();
        heap.alloc(safepoint, scalars::FLOAT_PAYLOAD, value)
    }

    /// Allocate a boxed `Byte` (§7.4's `byte` atomic).
    fn alloc_byte(&self, value: u8) -> GcRef {
        let (heap, safepoint) = self.safepoint();
        heap.alloc(safepoint, scalars::BYTE_PAYLOAD, value)
    }

    /// Allocate a source-slice `Text` pointing into `owner`, or `None` if the
    /// range is not a `Text`.
    ///
    /// The parser computes its offsets from byte positions in the very buffer
    /// it is slicing, so `None` means the interpreter has a bug — but it must
    /// still surface as a parse fault rather than a panic across the ABI
    /// (§10.4), which is why this is fallible rather than an assert.
    fn alloc_text_slice(&self, owner: GcRef, start: usize, len: usize) -> Option<GcRef> {
        // SAFETY: `owner` is the context's input buffer, a live Text.
        let slice = unsafe { crate::text::SourceSlice::new(owner, start, len) }?;
        let payload = TextPayload::Slice(slice);
        let (heap, safepoint) = self.safepoint();
        // SAFETY: TextPayload is TEXT's payload type.
        Some(unsafe { heap.alloc_payload(safepoint, &crate::text::TEXT, payload) })
    }

    /// Allocate an **owned** `Text` holding a copy of `s`.
    ///
    /// Used only for a ragged grid's `fill` literal, which lives in plan
    /// storage rather than in the input. Giving it a `Text` of its own is what
    /// lets the cell parser slice it: walking the fill's bytes while allocating
    /// slices against the *input* would make a `Text` fill cell name input bytes
    /// chosen by the fill's length.
    fn alloc_text_owned(&self, s: &str) -> GcRef {
        let payload = TextPayload::owned(s);
        let (heap, safepoint) = self.safepoint();
        // SAFETY: TextPayload is TEXT's payload type.
        unsafe { heap.alloc_payload(safepoint, &crate::text::TEXT, payload) }
    }

    /// Allocate a `Vec` from element refs.
    fn alloc_vec(
        &self,
        element_descriptor: &'static crate::TypeDescriptor,
        items: Vec<GcRef>,
    ) -> GcRef {
        let payload = crate::collections::VecPayload {
            element_descriptor,
            items: items.into(),
        };
        let (heap, safepoint) = self.safepoint();
        // SAFETY: VecPayload is VEC's payload type.
        unsafe { heap.alloc_payload(safepoint, &crate::collections::VEC, payload) }
    }

    /// Allocate an enum value: `schema` says which enum type it is, `tag`
    /// selects the variant, and `items` are the payload values. Matches the
    /// `EnumPayload` layout that codegen-produced `match` code expects (§4.6).
    /// Used by `choice`/`optional`.
    fn alloc_enum(
        &self,
        schema: *const crate::enums::EnumSchema,
        tag: u32,
        items: Vec<GcRef>,
    ) -> GcRef {
        let payload = crate::enums::EnumPayload { schema, tag, items };
        let (heap, safepoint) = self.safepoint();
        // SAFETY: EnumPayload is ENUM's payload type.
        unsafe { heap.alloc_payload(safepoint, &crate::enums::ENUM, payload) }
    }
}

/// Walk a plan node against `region`, producing a value and the absolute
/// position where matching stopped.
///
/// The node begins at `region.start()` and may not read past `region.end()`.
/// Whether it must *reach* `region.end()` is the parent's decision, made by
/// [`walk_exact`]: `lines` requires it of each line, `scan` does not require it
/// of a match. That is one rule in one place, which is what makes
/// `scan(choice(…))` and `lines(choice(…))` both correct without `choice`
/// itself having a policy.
///
/// # Safety
/// `ctx` must be live and wired.
unsafe fn walk(
    ctx: *mut RuntimeContext,
    i: &Input<'_>,
    plan: &ParserPlan,
    node: u32,
    region: ByteRegion,
) -> WalkResult {
    let rt = Rt { ctx };
    let node = &plan.nodes[node as usize];
    match node {
        PlanNode::Atomic { kind } => walk_atomic(&rt, i, *kind, region),
        PlanNode::Lines { child } => walk_lines(&rt, i, plan, *child, region),
        PlanNode::Sections { child } => walk_sections(&rt, i, plan, *child, region),
        PlanNode::SectionsNamed {
            fields,
            repeated_tail,
            field_order,
        } => walk_sections_named(&rt, i, plan, fields, *repeated_tail, field_order, region),
        PlanNode::Block { items, field_order } => {
            walk_block(&rt, i, plan, items, field_order, region)
        }
        PlanNode::Choice { cases } => walk_choice(&rt, i, plan, cases, region),
        PlanNode::Optional { child } => walk_optional(&rt, i, plan, *child, region),
        PlanNode::Scan { child } => walk_scan(&rt, i, plan, *child, region),
        PlanNode::OneOf { chars_index } => {
            let chars = plan.literals[*chars_index as usize];
            walk_one_of(&rt, i, chars, region)
        }
        PlanNode::Characters { child, skip } => {
            walk_characters(&rt, i, plan, *child, *skip, region)
        }
        PlanNode::Matrix { child } => walk_matrix(&rt, i, plan, *child, region),
        PlanNode::GridRagged { child, fill_index } => {
            let fill = plan.literals[*fill_index as usize];
            walk_grid_ragged(&rt, i, plan, *child, fill, region)
        }
        PlanNode::Csv { child } => walk_csv(&rt, i, plan, *child, region),
        PlanNode::Ws { child } => walk_ws(&rt, i, plan, *child, region),
        PlanNode::Sep {
            separator_index,
            child,
        } => {
            let sep = plan.literals[*separator_index as usize];
            walk_sep(&rt, i, plan, *child, sep, region)
        }
        PlanNode::Grid { child } => walk_grid(&rt, i, plan, *child, region),
        PlanNode::Template { parts, field_order } => {
            walk_template(&rt, i, plan, parts, field_order, region)
        }
    }
}

// ---- atomics (§7.4) -------------------------------------------------------

fn walk_atomic(rt: &Rt, i: &Input<'_>, kind: AtomicKind, region: ByteRegion) -> WalkResult {
    let rest = region.bytes(i);
    // Every atomic starts by skipping horizontal whitespace; `at` is where the
    // value itself begins, in the input's own coordinates.
    let s = trim_leading_ws(rest);
    let at = region.start().advance(rest.len() - s.len());
    // The name a failure reports is the atomic's own keyword, taken from the one
    // place that owns those ten strings ([`AtomicKind::keyword`]) rather than
    // spelled per-arm — arms are shared between kinds, so a per-arm literal
    // would report a parser the program did not write.
    let what = kind.keyword();
    match kind {
        AtomicKind::Int => {
            // Parse a signed decimal integer.
            let (digits, len) = take_int_run(s);
            if digits.is_empty() {
                return Err(ParseFail::at(at.offset(), 0, what));
            }
            let value: i64 = digits
                .parse()
                .map_err(|_| ParseFail::at(at.offset(), len, what))?;
            Ok(Walked {
                value: rt.alloc_int(value),
                next: at.advance(len),
            })
        }
        AtomicKind::Digit => {
            let Some(&b) = s.first() else {
                return Err(ParseFail::at(at.offset(), 0, what));
            };
            if !b.is_ascii_digit() {
                return Err(ParseFail::at(at.offset(), 1, what));
            }
            let value = (b - b'0') as i64;
            Ok(Walked {
                value: rt.alloc_int(value),
                next: at.advance(1),
            })
        }
        AtomicKind::Char => {
            // One Unicode scalar value, stepped by the region.
            //
            // **A space is a character**, so `char` reads the scalar at the
            // cursor and does not trim first. §7.4's "surrounding horizontal
            // space handled by caller" is a rule for the *numeric* atomics; a
            // character parser that skipped spaces cannot represent one. That
            // is not a nicety: a `grid` column is positional, so a trim here
            // would make `grid(char)` over `"ab\na b\n"` count two cells in
            // both rows and report a genuinely ragged input as a clean 2x2
            // grid with `b` shifted into the space's slot.
            let at = region.start();
            let Some(next) = region.next_scalar(i, at) else {
                return Err(ParseFail::at(at.offset(), 0, what));
            };
            let text = region
                .subregion(at, next)
                .str(i)
                .ok_or_else(|| ParseFail::at(at.offset(), 0, what))?;
            let ch = text
                .chars()
                .next()
                .ok_or_else(|| ParseFail::at(at.offset(), 0, what))?;
            Ok(Walked {
                value: rt.alloc_char(ch as u32),
                next,
            })
        }
        AtomicKind::Word => {
            let (word, len) = take_word_run(s);
            if word.is_empty() {
                return Err(ParseFail::at(at.offset(), 0, what));
            }
            let slice = rt
                .alloc_text_slice(i.owner(), i.owner_offset(at.offset()), len)
                .ok_or_else(|| ParseFail::at(at.offset(), len, what))?;
            Ok(Walked {
                value: slice,
                next: at.advance(len),
            })
        }
        AtomicKind::UInt => {
            // §7.4's `uint`. Its **type** is `Int` (`ScalarType::UInt` is
            // reserved and has no runtime object); the non-negativity is this
            // rule: a leading `-` is not a `uint`, it is a parse failure.
            if s.first() == Some(&b'-') {
                return Err(ParseFail::at(at.offset(), 1, what));
            }
            let (digits, len) = take_int_run(s);
            if digits.is_empty() {
                return Err(ParseFail::at(at.offset(), 0, what));
            }
            let value: i64 = digits
                .parse()
                .map_err(|_| ParseFail::at(at.offset(), len, what))?;
            Ok(Walked {
                value: rt.alloc_int(value),
                next: at.advance(len),
            })
        }
        AtomicKind::Float => {
            let (text, len) = take_float_run(s);
            if text.is_empty() {
                return Err(ParseFail::at(at.offset(), 0, what));
            }
            let value: f64 = text
                .parse()
                .map_err(|_| ParseFail::at(at.offset(), len, what))?;
            Ok(Walked {
                value: rt.alloc_float(value),
                next: at.advance(len),
            })
        }
        AtomicKind::Byte => {
            // A decimal integer in `0..=255`, not a raw input byte: a raw byte
            // cannot be re-sliced as `Text` without breaking the UTF-8
            // invariant every source-slice `Text` relies on.
            let (digits, len) = take_int_run(s);
            if digits.is_empty() {
                return Err(ParseFail::at(at.offset(), 0, what));
            }
            let value: u8 = digits
                .parse()
                .map_err(|_| ParseFail::at(at.offset(), len, what))?;
            Ok(Walked {
                value: rt.alloc_byte(value),
                next: at.advance(len),
            })
        }
        AtomicKind::Identifier => {
            // §4.1's identifier class, not a local ASCII rule. §7.4 says
            // "ASCII-like … by default"; accepting fewer names than the
            // language itself declares would be the narrower mistake.
            let len = take_ident_run(s);
            if len == 0 {
                return Err(ParseFail::at(at.offset(), 0, what));
            }
            let slice = rt
                .alloc_text_slice(i.owner(), i.owner_offset(at.offset()), len)
                .ok_or_else(|| ParseFail::at(at.offset(), len, what))?;
            Ok(Walked {
                value: slice,
                next: at.advance(len),
            })
        }
        AtomicKind::Text | AtomicKind::Rest => {
            // `text`/`rest` consume the rest of **the region**, not the rest of
            // the buffer: running to `bytes.len()` would let a `text` capture
            // swallow the literal that follows it, making every
            // `pre{body:text}post` template unmatchable. Leading whitespace is
            // part of the text.
            //
            // The two kinds share a rule but not a name: `what` is the keyword
            // the program actually wrote.
            let start = region.start();
            let len = region.end().delta_from(start);
            let slice = rt
                .alloc_text_slice(i.owner(), i.owner_offset(start.offset()), len)
                .ok_or_else(|| ParseFail::at(start.offset(), len, what))?;
            Ok(Walked {
                value: slice,
                next: region.end(),
            })
        }
    }
}

// ---- constructors (§7.5) --------------------------------------------------

/// The kind of bound a [`walk_exact`] caller computed, for the mismatch it
/// names.
///
/// A closed set rather than a free-form `&'static str`, so each description is
/// spelled once for the dozen call sites that name one. The strings are user
/// visible: the book's fault reference (`docs/book/src/input/faults.md`)
/// tabulates them verbatim against the constructor that raises each.
#[derive(Clone, Copy)]
enum ExactBound {
    Line,
    Section,
    Token,
    Field,
    Capture,
    Fill,
}

impl ExactBound {
    /// The description [`ParseFail`] reports after `expected `.
    const fn describe(self) -> &'static str {
        match self {
            ExactBound::Line => "the rest of the line",
            ExactBound::Section => "the rest of the section",
            ExactBound::Token => "the rest of the token",
            ExactBound::Field => "the rest of the field",
            ExactBound::Capture => "the rest of the capture",
            ExactBound::Fill => "the rest of the fill",
        }
    }
}

/// Walk `node` against `region` and require it to consume the region **exactly**.
///
/// §7.5's rule for a bounded construct is that "each application must consume
/// the entire line" (and the same for a section, a CSV field, a
/// whitespace-delimited token, a matrix cell).
///
/// Returning a bare `GcRef` is the point: there is no cursor left for a caller
/// to forget to check, so "I bounded the child but did not require it to fill
/// the bound" stops being expressible.
///
/// **What the child leaves is whitespace, or it is a mismatch** — the *bound*
/// half of the rule stated in [`cursor`]. §7.4 puts "surrounding horizontal
/// space" on the caller, and this is the caller for every bounded construct
/// there is: a line, a section, a CSV field, a `ws`/`sep` token, a matrix cell,
/// a template capture. The rule lives in this one place, so no two constructs
/// can disagree about a leftover space.
///
/// It is deliberately the child's answer and not the region's. `int` cannot
/// read `"1 "`'s trailing space, so the space is padding; `char` reads it as a
/// cell, so `grid(char)` over `"ab\ncd \n"` is a **ragged grid** — a complaint
/// about the data, not about a file convention. The same answer covers the
/// shape next door: `grid(char)` over `"ab\ncd\n  \n"` is three rows, because a
/// trailing line of spaces is offered too (`cursor::trailing_blank_run`) and
/// `char` reads it.
///
/// And it is only what the child *leaves*: `lines(int)` over `"12junk"` faults,
/// because `"junk"` is not whitespace, which is what this check exists for.
///
/// # Safety
/// `ctx` must be live and wired.
unsafe fn walk_exact(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    node: u32,
    region: ByteRegion,
    what: ExactBound,
) -> Result<GcRef, ParseFail> {
    // SAFETY: forwarded from this function's contract.
    let walked = unsafe { walk(rt.ctx, i, plan, node, region)? };
    if walked.next != region.end() && !region.from(walked.next).is_all_whitespace(i) {
        return Err(ParseFail::at(
            walked.next.offset(),
            region.end().delta_from(walked.next),
            what.describe(),
        ));
    }
    Ok(walked.value)
}

/// The text a region spans, or a parse failure naming `what`.
///
/// A region of a validated [`Input`] can only fail this by splitting a scalar,
/// which is an interpreter bug; it is reported as a parse failure rather than
/// asserted, because this runs inside `extern "C"`. Substituting an empty `str`
/// for an unconvertible region would answer a mismatch with a zero-row,
/// zero-width `Grid`.
fn region_str<'a>(
    i: &Input<'a>,
    region: ByteRegion,
    what: &'static str,
) -> Result<&'a str, ParseFail> {
    region
        .str(i)
        .ok_or_else(|| ParseFail::at(region.start().offset(), region.len(), what))
}

/// The whitespace-delimited tokens of `region`, whose text is `s`, as absolute
/// subregions.
///
/// Bounds are computed while splitting rather than recovered afterwards by
/// searching the region for the token's text, which would map every duplicate
/// token to the first occurrence.
fn whitespace_tokens(region: ByteRegion, s: &str) -> Vec<ByteRegion> {
    let base = region.start();
    let mut out = Vec::new();
    let mut start: Option<usize> = None;
    for (idx, ch) in s.char_indices() {
        if ch.is_whitespace() {
            if let Some(st) = start.take() {
                out.push(region.subregion(base.advance(st), base.advance(idx)));
            }
        } else if start.is_none() {
            start = Some(idx);
        }
    }
    if let Some(st) = start {
        out.push(region.subregion(base.advance(st), region.end()));
    }
    out
}

/// The comma-separated fields of `region`, whose text is `s`, as absolute
/// subregions. A field runs from one comma to the next, **untrimmed**.
///
/// §7.5's csv entry says "ignore horizontal whitespace around each comma".
/// Implementing that with `str::trim()` on every field would decide about
/// whitespace *without asking the field's parser*, the one thing §7.5's rule
/// forbids — and `trim()` eats vertical whitespace too, which is more than the
/// entry authorises.
///
/// The entry's promise is kept by the rule instead: `walk_csv` hands each field
/// to [`walk_exact`], `int` (like every atomic §7.4 puts surrounding space on
/// the caller for) skips leading horizontal whitespace itself, and the bound
/// half forgives a leftover run that is all whitespace. So `csv(int)` over
/// `" 1, 2, 3"` reads three ints, and `csv(char)` over `"a, ,c"` reads three
/// characters — one of them a space, because `char` reads spaces everywhere
/// else too.
///
/// An empty field yields an **empty region**.
fn csv_tokens(region: ByteRegion, s: &str) -> Vec<ByteRegion> {
    let base = region.start();
    let mut out = Vec::new();
    let mut field_start = 0usize;
    for (idx, ch) in s.char_indices() {
        if ch == ',' {
            out.push(region.subregion(base.advance(field_start), base.advance(idx)));
            field_start = idx + ch.len_utf8();
        }
    }
    out.push(region.subregion(base.advance(field_start), region.end()));
    out
}

/// Parse one grid row: apply the cell parser from the row's start until the row
/// is consumed, appending each cell to `items`. Returns the row's cell count.
///
/// **A cell is whatever the cell parser reads.** §7.5's `grid` examples are
/// `grid(char)` and `grid(digit)`, and `digit` exists *for* the
/// one-digit-per-cell case — if `grid(int)` meant that too, `digit` would name
/// nothing. So a cell parser inside `grid` parses a cell exactly as it would
/// parse anywhere else: `char` is one scalar, `digit` is one digit, `int` is an
/// integer token.
///
/// The row is exactly consumed by construction: the cell is bounded to the row,
/// so it cannot overshoot, and the loop only ends at the row's end or on the
/// cell parser's own failure.
///
/// # Safety
/// `ctx` must be live and wired.
unsafe fn walk_grid_row(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    line: ByteRegion,
    items: &mut Vec<GcRef>,
    scope: &NativeScope<'_>,
) -> Result<usize, ParseFail> {
    let mut cells = 0usize;
    let mut cursor = line.start();
    while cursor < line.end() {
        // SAFETY: forwarded from this function's contract.
        let walked = match unsafe { walk(rt.ctx, i, plan, child, line.from(cursor)) } {
            Ok(walked) => walked,
            Err(fail) => {
                // **A trailing run the cell parser cannot read is padding, not
                // a cell** — `walk_exact`'s bound rule, in the second loop that
                // is not `walk_exact`-shaped, through the same predicate.
                // Trailing spaces are ordinary in real input, and `matrix(int)`
                // already drops them (`whitespace_tokens` never emits an empty
                // token); without this rule `grid(int)` would fault on the very
                // same file. §7.5 asks only that every row have the same cell
                // count.
                //
                // A cell parser that *can* read the run never gets here:
                // `grid(char)` reads a space as a space, which is what keeps a
                // char grid positional — and is why `grid(char)` over
                // `"ab\ncd \n"` is a ragged grid rather than a 2x2 one.
                if line.from(cursor).is_all_whitespace(i) {
                    break;
                }
                return Err(fail);
            }
        };
        if walked.next <= cursor {
            // A cell parser that reads nothing would loop forever. `text`/`rest`
            // over an empty tail is the shape that gets here.
            return Err(ParseFail::at(cursor.offset(), 0, "a cell that reads input"));
        }
        scope.root(walked.value);
        items.push(walked.value);
        cursor = walked.next;
        cells += 1;
    }
    Ok(cells)
}

/// **The uniform-row rule (§7.5), stated where it is enforced.** Every row holds
/// the same count as the first, and the fault names **the row that broke it** —
/// the line's own region, never the region the constructor was handed. Returns
/// the width to carry forward.
///
/// Two constructors enforce this, so the rule is stated once here. What the
/// count *counts* is the caller's — cells for `grid`, whitespace tokens for
/// `matrix` — and so is `expected`; where the fault points is not. ADR-078
/// consequence 2 and §7.11 say a fault names the position parsing broke at.
///
/// It answers the width rather than taking `&mut Option<usize>` so that a caller
/// cannot check the rule and forget to record the first row's width: the check
/// **is** how the width is obtained.
fn uniform_row_width(
    first: Option<usize>,
    count: usize,
    line: ByteRegion,
    expected: &'static str,
) -> Result<usize, ParseFail> {
    match first {
        None => Ok(count),
        Some(w) if w != count => Err(ParseFail::at(line.start().offset(), line.len(), expected)),
        Some(w) => Ok(w),
    }
}

fn walk_lines(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut items = Vec::new();
    let lines = split_lines(i, region);
    // The trailing run of blank lines is *offered* like any other line; what
    // happens to it is the child's answer (`cursor`'s rule, bound half).
    let blank_run = trailing_blank_run(i, &lines);
    for (n, line) in lines.iter().enumerate() {
        // One line, consumed exactly.
        // SAFETY: ctx is valid (upheld by `walk`'s caller).
        match unsafe { walk_exact(rt, i, plan, child, *line, ExactBound::Line) } {
            Ok(value) => {
                scope.root(value);
                items.push(value);
            }
            // A trailing line of nothing but whitespace the child makes nothing
            // of belongs to nobody: `lines(int)` over `"1\n2\n  \n"` is two
            // elements. The child is asked rather than the line being deleted
            // before anyone sees it — deleting it would also delete it for the
            // children that *can* read it, and `lines(rest)` losing a line is
            // `rest`'s identity property failing one level up. So
            // `lines(rest)` and `lines(char)` keep it.
            Err(fail) => {
                if n < blank_run {
                    return Err(fail);
                }
            }
        }
    }
    let elem_desc = child_descriptor(plan, child);
    Ok(Walked {
        value: rt.alloc_vec(elem_desc, items),
        next: region.end(),
    })
}

fn walk_sections(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut items = Vec::new();
    for section in split_sections(i, region) {
        // A **narrowing of the same buffer**, not a re-slice walked at offset
        // zero: the child's offsets are the input's own, so a `word` in section
        // 2 slices the bytes it actually matched.
        // SAFETY: ctx is valid.
        let value = unsafe { walk_exact(rt, i, plan, child, section, ExactBound::Section)? };
        scope.root(value);
        items.push(value);
    }
    let elem_desc = child_descriptor(plan, child);
    Ok(Walked {
        value: rt.alloc_vec(elem_desc, items),
        next: region.end(),
    })
}

/// Walk named heterogeneous `sections(name: P, ..., tail: repeated(P))` (§7.5).
/// The region is split on blank lines into sections, and the named arguments
/// consume them **through one cursor, in source order**: a
/// `SectionItemNode::One` takes the section at the cursor, a
/// `SectionItemNode::Counted` takes its count's worth and collects them into a
/// `Vec`, and the unbounded `repeated(P)` tail — if there is one — takes
/// whatever the cursor has not reached. The result is an anonymous record
/// assembled via [`alloc_record`].
///
/// The cursor is what makes a counted group followable: a rule of "the fields
/// take `sections[0..fields.len()]` and the tail takes the rest" cannot express
/// a field that wants six sections, let alone one that wants six and is
/// followed by another field.
fn walk_sections_named(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    fields: &'static [SectionItemNode],
    repeated_tail: Option<(&'static str, u32)>,
    field_order: &'static [&'static str],
    region: ByteRegion,
) -> WalkResult {
    let sections = split_sections(i, region);
    // Too few sections is a parse fault, for a counted group exactly as for a
    // fixed field: a group of six that finds four is input that did not match
    // the parser, not a `Vec` of four. Truncating it silently would be the one
    // outcome no program can notice, since the whole point of writing the count
    // is that the program knows how many there are.
    let required: usize = fields.iter().map(SectionItemNode::sections_wanted).sum();
    if sections.len() < required {
        return Err(ParseFail::at(
            region.start().offset(),
            region.len(),
            sections_shortfall(fields, sections.len()),
        ));
    }
    // Each section is a narrowing of the input, so the child's offsets are the
    // input's own offsets and a source-slice `Text` is right by construction.
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut captures: Vec<(Option<&'static str>, u32, GcRef)> = Vec::new();
    let mut at = 0usize;
    for item in fields {
        match item {
            SectionItemNode::One { name, child } => {
                // SAFETY: ctx is valid.
                let value =
                    unsafe { walk_exact(rt, i, plan, *child, sections[at], ExactBound::Section)? };
                scope.root(value);
                captures.push((Some(*name), *child, value));
            }
            SectionItemNode::Counted { name, child, count } => {
                let mut group = Vec::with_capacity(*count as usize);
                for section in &sections[at..at + *count as usize] {
                    // SAFETY: ctx is valid.
                    let value =
                        unsafe { walk_exact(rt, i, plan, *child, *section, ExactBound::Section)? };
                    scope.root(value);
                    group.push(value);
                }
                let elem_desc = child_descriptor(plan, *child);
                let group_vec = rt.alloc_vec(elem_desc, group);
                // Rooted before the next allocation: a collection between two
                // sections would otherwise drop the Vec this field *is*.
                scope.root(group_vec);
                captures.push((Some(*name), *child, group_vec));
            }
        }
        at += item.sections_wanted();
    }
    if let Some((tail_name, tail_child)) = repeated_tail {
        // The tail consumes every section the cursor has not reached, parsed
        // per-section by its child into a Vec.
        let mut tail_items = Vec::new();
        for section in &sections[at..] {
            // SAFETY: ctx is valid.
            let value =
                unsafe { walk_exact(rt, i, plan, tail_child, *section, ExactBound::Section)? };
            scope.root(value);
            tail_items.push(value);
        }
        let elem_desc = child_descriptor(plan, tail_child);
        let tail_vec = rt.alloc_vec(elem_desc, tail_items);
        scope.root(tail_vec);
        // The tail field's "child" node for descriptor purposes is the tail
        // child; its value is the assembled Vec.
        captures.push((Some(tail_name), tail_child, tail_vec));
    }
    let record = alloc_record(rt, &captures, field_order);
    Ok(Walked {
        value: record,
        next: region.end(),
    })
}

/// What a `sections(...)` with too few sections was expecting, in the words
/// [`ParseFail`] renders after "expected".
///
/// A call of fixed fields says `section header`, the message the book
/// documents: every field wants one section, so "another section" is the whole
/// of what is missing. A counted group is different — the number is written in
/// the program, and the reader's question is *which* group came up short — so
/// the first item the section list cannot satisfy names itself and its count.
fn sections_shortfall(fields: &'static [SectionItemNode], available: usize) -> String {
    let mut at = 0usize;
    for item in fields {
        let wanted = item.sections_wanted();
        if at + wanted > available {
            if let SectionItemNode::Counted { name, count, .. } = item {
                return format!("{count} sections for `{name}`");
            }
            break;
        }
        at += wanted;
    }
    "section header".to_string()
}

/// Walk `block(item, ...)` (§7.5): apply sequential parsers within one region,
/// advancing the cursor after each. A positional named-capture template
/// *flattens* its fields into the block record; a named item contributes one
/// field. The result is a flattened anonymous record assembled via
/// [`alloc_record`].
///
/// Cursor model: each item is walked against a window computed from the current
/// cursor, and the item's returned position becomes the next cursor. Every
/// position in play is absolute. Line-anchoring is two questions with two
/// answers, and both live elsewhere: where an item *starts* is
/// [`skip_line_boundary`]'s, and how far it may *reach* is
/// [`block_item_window`]'s.
fn walk_block(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    items: &'static [praxis_input_parser::BlockItemNode],
    field_order: &'static [&'static str],
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut cursor = region.start();
    // Captures collected as (name, child_node_for_descriptor, value). For a
    // flattened positional record, we expand its fields into separate entries.
    let mut captures: Vec<(Option<&'static str>, u32, GcRef)> = Vec::new();
    for (n, item) in items.iter().enumerate() {
        // Before every item after the first, skip the line boundary. The first
        // item starts at the region head.
        if n > 0 {
            cursor = skip_line_boundary(i, region, cursor);
        }
        match item {
            praxis_input_parser::BlockItemNode::Positional { child } => {
                // SAFETY: ctx is valid.
                let walked = unsafe {
                    walk(
                        rt.ctx,
                        i,
                        plan,
                        *child,
                        block_item_window(i, plan, *child, region, cursor),
                    )?
                };
                scope.root(walked.value);
                cursor = walked.next;
                // If the positional produced a record (named-capture template),
                // flatten its fields into the block record. We detect a record
                // by pointer-equality of its descriptor against RECORD.
                if std::ptr::eq(walked.value.descriptor(), &crate::records::RECORD) {
                    flatten_record_into(rt, walked.value, &mut captures);
                }
                // A non-record positional (scalar) was rejected by validation
                // (I026); if we reach one here it contributes no field.
            }
            praxis_input_parser::BlockItemNode::Named { name, child } => {
                // The same window as the positional arm, deliberately: the
                // window is read off the item's plan node, so whether the item
                // carries a name has no part in it.
                // SAFETY: ctx is valid.
                let walked = unsafe {
                    walk(
                        rt.ctx,
                        i,
                        plan,
                        *child,
                        block_item_window(i, plan, *child, region, cursor),
                    )?
                };
                scope.root(walked.value);
                cursor = walked.next;
                captures.push((Some(name), *child, walked.value));
            }
        }
    }
    let record = alloc_record(rt, &captures, field_order);
    Ok(Walked {
        value: record,
        next: cursor,
    })
}

/// **The window a `block` item is offered** (ADR-090, §7.5). A *template* item
/// gets the line it starts on, plus one more line for each `\n` the template
/// writes; every other item gets the rest of the region.
///
/// This is the one statement of the rule. Every other sequencing construct
/// narrows for its children — `lines` to a line, `sections` to a section, `csv`
/// to a field, `ws`/`sep`/`matrix` to a token — and ADR-078's thesis is that
/// the window is the *parent's* job. With no parent bound, a capture that is
/// its template's last part meets `walk_template`'s unbounded-last-part rule
/// and is handed the rest of the section: §7.7's own example, whose
/// `` `  Starting items: {items:csv(int)}` `` would feed the remaining five
/// lines of the monkey to `csv`, where the identical template under `lines`
/// reads two ints because `lines` bounded it.
///
/// **Why the split is templates and not a list of greedy constructors.** §7.2
/// defines a template as a description of characters *within a line*, and gives
/// `\n` as the template's own way of saying it spans another one — so a
/// template states its extent and this function reads it off. `lines`,
/// `sections`, `grid` and `matrix` are defined on several lines by their §7.5
/// entries and compute their own extent, so bounding them here would be a
/// second, disagreeing opinion. Any other split — "is this parser greedy?" —
/// would need a per-constructor table, which is the rule-in-N-places trap
/// ADR-078's corollary warns against.
///
/// It is a **narrowing and not a bound**: the item may stop short of the window
/// and `block` carries its cursor to the next item, which is how two items on
/// one line still work. Requiring exhaustion here ([`walk_exact`]) breaks
/// ``block(`a: {a:int}`, `b: {b:int}`)`` over `"a: 1 b: 2"` and every named
/// `lines(...)` item, which is §7.5's own `block` example.
///
/// The gap it leaves, named rather than papered over: a **non-template** greedy
/// item followed by another item (``block(`h:`, a: csv(int), b: word)``) still
/// swallows. It is a loud fault rather than a wrong answer, and closing it is
/// the per-constructor table above.
fn block_item_window(
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
    cursor: Cursor,
) -> ByteRegion {
    let PlanNode::Template { parts, .. } = &plan.nodes[child as usize] else {
        return region.from(cursor);
    };
    let extra = parts
        .iter()
        .filter(|p| {
            matches!(
                p,
                praxis_input_parser::TemplatePartNode::Literal {
                    ws: praxis_input_parser::WsPolicy::Newline,
                    ..
                }
            )
        })
        .count();
    region.subregion(cursor, cursor::line_window_end(i, region, cursor, extra))
}

/// Skip the line boundary between sequential `block` items (§7.5): any run of
/// horizontal whitespace, then an optional single line ending (`\n` or `\r\n`).
/// Returns the new cursor. If no line ending is present (e.g. the items are on
/// one line separated by spaces), only the horizontal whitespace is consumed.
///
/// Where the *next* item starts, and only that. How far it may then reach is
/// [`block_item_window`]'s — the other half of "block items are line-anchored".
///
/// Byte-wise on purpose: space, tab, CR and LF are single-byte scalars and
/// cannot occur inside a multi-byte one, so scanning bytes here can never land
/// mid-scalar. (The cell and scan loops step by scalar because *they* can.)
fn skip_line_boundary(i: &Input<'_>, region: ByteRegion, cursor: Cursor) -> Cursor {
    let tail = region.from(cursor);
    let bytes = tail.bytes(i);
    let mut n = horizontal_ws_run(bytes);
    if bytes.get(n) == Some(&b'\r') {
        n += 1;
    }
    if bytes.get(n) == Some(&b'\n') {
        n += 1;
    }
    cursor.advance(n)
}

/// Flatten a positional record's fields into the block captures (§7.5
/// flattening). Reads the value's `RecordPayload` schema + items and pushes one
/// `(name, child_for_descriptor, value)` entry per field. The per-field
/// descriptor is read from the value's own header at record-format/eq/hash time,
/// so the `child` placeholder here is only a fallback tag.
fn flatten_record_into(
    _rt: &Rt,
    record_ref: GcRef,
    captures: &mut Vec<(Option<&'static str>, u32, GcRef)>,
) {
    let payload = record_ref.payload::<u8>() as *const crate::records::RecordPayload;
    // SAFETY: record_ref is a valid RECORD GcRef (descriptor checked by caller).
    let (schema, items) = unsafe {
        let p = &*payload;
        (p.schema, &p.items)
    };
    // SAFETY: schema is a valid RecordSchema pointer, owned by the schema cache
    // and live until `retire_schemas`.
    let schema = unsafe { &*schema };
    for (n, field) in schema.fields.iter().enumerate() {
        if let Some(value) = items.get(n) {
            captures.push((Some(field.name), u32::MAX, *value));
        }
    }
}

/// Walk `choice(Name: P, ...)` (§7.5): try each case in source order from
/// the region's start. The first case whose parser succeeds wins; its value
/// becomes the variant's payload and the cursor advances to where that parser
/// stopped. If a case fails, the next case is tried from the same start
/// (backtracking). If no case matches, this is a parse fault.
///
/// `choice` does **not** require its region to be exhausted. Whether a match
/// must fill its region is the bounded parent's question — `lines(choice(…))`
/// requires it through `walk_exact`, `scan(choice(…))` matches fragments by
/// design — and answering it in one place is what makes both correct.
///
/// Backtracking note: a failed case may have allocated GC objects (since `walk`
/// allocates eagerly); those are unreferenced and collected later. Only the
/// cursor is restored — there is no allocator rollback, which is fine because
/// failed allocations are simply garbage.
fn walk_choice(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    cases: &'static [(&'static str, u32)],
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut deepest: Option<ParseFail> = None;
    for (tag, (_name, child)) in cases.iter().enumerate() {
        // SAFETY: ctx is valid.
        match unsafe { walk(rt.ctx, i, plan, *child, region) } {
            Ok(walked) => {
                // First match wins. Tag with this case's index; the value is
                // the single payload slot, rooted across `alloc_enum`.
                scope.root(walked.value);
                let schema = enum_schema_for(cases);
                let enum_ref = rt.alloc_enum(schema, tag as u32, vec![walked.value]);
                return Ok(Walked {
                    value: enum_ref,
                    next: walked.next,
                });
            }
            Err(inner) => {
                // Backtrack, **keeping the deepest case failure**. The deepest
                // failure is the most specific one — it is the same rule
                // `ParseDetail::consider` applies across a whole parse — and a
                // case that got further is the case the input was trying to be.
                // Discarding them for a generic message at the choice's own
                // offset would make §7.11's detail name the outermost construct
                // and point where nothing had gone wrong yet.
                let deeper = match &deepest {
                    None => true,
                    Some(best) => inner.input_span.0 > best.input_span.0,
                };
                if deeper {
                    deepest = Some(inner);
                }
            }
        }
    }
    // A choice with no cases has no case failure to report; that is the only
    // shape the generic message describes honestly.
    Err(deepest.unwrap_or_else(|| ParseFail::at(region.start().offset(), 0, "any choice case")))
}

/// Walk `optional(P)` (§7.5): parse `P`; on success return `Some(value)`
/// (Option tag 0) advancing the cursor, on failure return `None` (tag 1) and
/// consume NO input (the cursor stays at the region's start). No fault is
/// raised on a miss — this is parser-level optionality, not exception recovery.
fn walk_optional(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    // SAFETY: ctx is valid.
    match unsafe { walk(rt.ctx, i, plan, child, region) } {
        Ok(walked) => {
            // Rooted across `alloc_enum`, which paces.
            scope.root(walked.value);
            let some_ref = rt.alloc_enum(crate::enums::option_schema(), 0, vec![walked.value]);
            Ok(Walked {
                value: some_ref,
                next: walked.next,
            })
        }
        Err(_) => {
            // Consume nothing; return None (tag 1, no payload). The inner
            // failure is intentionally swallowed — `optional` is parser-level
            // optionality, not exception recovery.
            let none_ref = rt.alloc_enum(crate::enums::option_schema(), 1, Vec::new());
            Ok(Walked {
                value: none_ref,
                next: region.start(),
            })
        }
    }
}

/// Walk `scan(P)` (§7.5): slide a cursor across the region; at each position
/// try `P`. On success, push the value and advance past the match
/// (so overlapping matches aren't found); on failure, advance one position.
/// All unmatched text is ignored. Returns `Vec[result(P)]` in source order.
fn walk_scan(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut items = Vec::new();
    let mut cursor = region.start();
    while cursor < region.end() {
        // SAFETY: ctx is valid.
        match unsafe { walk(rt.ctx, i, plan, child, region.from(cursor)) } {
            Ok(walked) => {
                // A match must advance the cursor (otherwise we'd loop forever
                // on a zero-width match). If it didn't, step one position.
                scope.root(walked.value);
                items.push(walked.value);
                cursor = if walked.next > cursor {
                    walked.next
                } else {
                    match region.next_scalar(i, cursor) {
                        Some(next) => next,
                        None => break,
                    }
                };
            }
            Err(_) => {
                cursor = match region.next_scalar(i, cursor) {
                    Some(next) => next,
                    None => break,
                };
            }
        }
    }
    let elem_desc = child_descriptor(plan, child);
    Ok(Walked {
        value: rt.alloc_vec(elem_desc, items),
        next: region.end(),
    })
}

/// Walk `one_of("LR")` (§7.5): match one character from a literal set.
///
/// Like [`AtomicKind::Char`], it reads the scalar **at** the cursor: it is a
/// character class, and a class that skipped spaces before matching could not
/// contain one — nor could `chars(one_of(…), skip: none)` mean what it says.
/// A caller that wants leading space skipped has `skip:` or `walk_exact`'s token
/// bounds. **Not** a template's pre-capture skip: that skip *bounds* a capture
/// and does not feed it, so it deletes nothing before the child is offered the
/// bytes. Offering it as a third way would make ``lines(`{a:char}`)`` and
/// `lines(char)` disagree about the same file (ADR-079).
fn walk_one_of(rt: &Rt, i: &Input<'_>, chars: &str, region: ByteRegion) -> WalkResult {
    let at = region.start();
    let Some(next) = region.next_scalar(i, at) else {
        return Err(ParseFail::at(at.offset(), 0, "char"));
    };
    let ch = region
        .subregion(at, next)
        .str(i)
        .and_then(|t| t.chars().next())
        .ok_or_else(|| ParseFail::at(at.offset(), 0, "char"))?;
    if !chars.contains(ch) {
        return Err(ParseFail::at(
            at.offset(),
            ch.len_utf8(),
            format!("one of \"{chars}\""),
        ));
    }
    Ok(Walked {
        value: rt.alloc_char(ch as u32),
        next,
    })
}

/// Walk `chars(P, skip:)` (§7.5): apply a char-parser repeatedly, trimming
/// between matches per the skip policy.
fn walk_characters(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    skip: praxis_input_parser::SkipPolicy,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut items = Vec::new();
    let mut cursor = region.start();
    loop {
        cursor = skip_chars(i, region, cursor, skip);
        if cursor >= region.end() {
            break;
        }
        // **What is left is whitespace, or the child's failure is the parse's
        // failure.** Breaking on the failure half instead would return `Ok` at
        // the first mismatch and silently drop the rest of the region —
        // `chars(digit)` over `"12x34"` answering `[1, 2]` and reporting
        // nothing.
        //
        // The whitespace half is `walk_exact`'s bound rule, in the one loop
        // that is not `walk_exact`-shaped: `chars` has no bound to fill, it
        // consumes until the region runs out. Without it, whether §7.5's own
        // `chars(one_of("^v<>"), skip: whitespace)` could read an ordinary file
        // came down to whether its skip policy happened to include line endings
        // — and `whitespace` is horizontal whitespace, so it did not. It is
        // only what is *left*: `chars(digit, skip: none)` over `"1\n2"` still
        // faults, because `"\n2"` is not whitespace. And it is asked *after*
        // the child, so a character parser that can read whitespace still reads
        // it — `chars(one_of(" "))` counts spaces rather than skipping them.
        // SAFETY: ctx is valid.
        let walked = match unsafe { walk(rt.ctx, i, plan, child, region.from(cursor)) } {
            Ok(walked) => walked,
            Err(fail) => {
                if region.from(cursor).is_all_whitespace(i) {
                    break;
                }
                return Err(fail);
            }
        };
        cursor = if walked.next > cursor {
            walked.next
        } else {
            match region.next_scalar(i, cursor) {
                Some(next) => next,
                None => break,
            }
        };
        scope.root(walked.value);
        items.push(walked.value);
    }
    // The element descriptor is the child's, not a hardcoded `CHAR`: a Vec
    // tagged `Char` whatever it held would make `chars(int, …)` a `Vec[Char]`
    // full of `Int` objects, with `vec_format`/`vec_equals`/`vec_hash`
    // dispatching through the wrong callback.
    let elem_desc = child_descriptor(plan, child);
    Ok(Walked {
        value: rt.alloc_vec(elem_desc, items),
        next: region.end(),
    })
}

/// Skip bytes at `cursor` per the `chars` skip policy (§7.5).
///
/// **`Newlines` is the broader policy, not the narrower one.** `Whitespace`
/// skips spaces and tabs; `Newlines` skips those *and* line endings. The names
/// do not say so and the arms below look backwards to a reader who assumes
/// "whitespace" is the superset. In particular `skip: whitespace` cannot absorb
/// an input file's trailing newline, and does not have to: the terminator is
/// **inside** the region — the root region is the whole buffer — and it is
/// forgiven because it is whitespace no child read. [`walk_characters`] asks the
/// child first and accepts a whitespace-only leftover through
/// `ByteRegion::is_all_whitespace`, the bound half of `parser::cursor`'s rule.
/// `SkipPolicy`'s own documentation in `praxis-input-parser` carries the full
/// note, and `the_skip_policies_are_ordered_by_what_they_skip` pins the
/// inclusion so the sets cannot be quietly swapped.
///
/// Byte-wise like [`skip_line_boundary`], and sound for the same reason: every
/// byte it tests is ASCII whitespace, which cannot appear inside a multi-byte
/// scalar.
fn skip_chars(
    i: &Input<'_>,
    region: ByteRegion,
    cursor: Cursor,
    skip: praxis_input_parser::SkipPolicy,
) -> Cursor {
    use praxis_input_parser::SkipPolicy;
    let bytes = region.from(cursor).bytes(i);
    let n = match skip {
        SkipPolicy::None => 0,
        SkipPolicy::Whitespace => horizontal_ws_run(bytes),
        SkipPolicy::Newlines => ascii_ws_run(bytes),
    };
    cursor.advance(n)
}

/// Walk `matrix(P)` (§7.5, ADR-030): parse lines of whitespace-separated tokens
/// into a rectangular `Grid[result(P)]`. Each row must have the same token
/// count.
fn walk_matrix(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let lines = split_lines(i, region);
    let blank_run = trailing_blank_run(i, &lines);
    // **One loop, because the offending line has to still be in scope at the
    // width check**: tokenizing every line first and checking afterwards leaves
    // the width check with only `region` to name, so a ragged `matrix` would
    // report the whole input where the identical `grid` rule reports the line.
    // The single loop is order-preserving: the first observable failure is the
    // earliest row's, and `region_str` can only fail on a non-scalar-boundary
    // region, which `split_lines` over a validated `Input` cannot produce.
    let mut items = Vec::with_capacity(lines.len());
    let mut width: Option<usize> = None;
    for (n, line) in lines.iter().enumerate() {
        let text = region_str(i, *line, "matrix row")?;
        let tokens = whitespace_tokens(*line, text);
        // A **trailing** blank line yields no tokens, so `matrix` makes nothing
        // of it and it belongs to nobody — the same rule `grid` and `lines`
        // answer from, not a `matrix` special case. Skipping *any* line that
        // trims to nothing, interior ones included, would be the
        // per-constructor whitespace exception ADR-078's corollary warns
        // against: `matrix(int)` would silently drop the middle of
        // `"1 2\n  \n3 4\n"` where `lines(int)` and `grid(digit)` fault on the
        // identical shape. An interior blank line is structure, so it is a
        // zero-token row and the width check below rejects it.
        if tokens.is_empty() && n >= blank_run {
            continue;
        }
        // Uniform in **whitespace tokens**, which is matrix's own unit — grid
        // counts cells. `uniform_row_width` owns the half that is not: which
        // span the fault names.
        width = Some(uniform_row_width(
            width,
            tokens.len(),
            *line,
            "rectangular matrix row",
        )?);
        for token in &tokens {
            // The token's own region, not its bytes copied into a fresh buffer
            // walked at offset zero, and consumed exactly.
            // SAFETY: ctx is valid.
            let value = unsafe { walk_exact(rt, i, plan, child, *token, ExactBound::Token)? };
            scope.root(value);
            items.push(value);
        }
    }
    let width = width.unwrap_or(0);
    let elem_desc = child_descriptor(plan, child);
    alloc_grid(rt, elem_desc, items, width, region.end())
}

/// Walk ragged `grid(P, ragged, fill:)` (§7.5): permit uneven rows and pad
/// to the maximum width with the `fill` value (parsed by the cell parser).
fn walk_grid_ragged(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    fill: &str,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let lines = split_lines(i, region);
    // **The fill is not a region of the input.** It is a plan literal, so it
    // gets its own owned `Text` and its own `Input` — which is what makes a
    // sliced fill cell name the fill rather than unrelated input bytes.
    let fill_owner = rt.alloc_text_owned(fill);
    // The fill's `Text` and the value parsed out of it are both live across
    // every row: the value is a slice of the owner, and the padding cells all
    // share it.
    scope.root(fill_owner);
    // SAFETY: `alloc_text_owned` just produced a live Text.
    let fill_input = unsafe { Input::new(fill_owner) }
        .ok_or_else(|| ParseFail::at(region.start().offset(), 0, "grid fill"))?;
    let fill_region = fill_input.whole();
    // SAFETY: ctx is valid.
    let fill_value =
        unsafe { walk_exact(rt, &fill_input, plan, child, fill_region, ExactBound::Fill)? };
    scope.root(fill_value);
    // Rows are parsed first and padded second: a ragged grid's width is the
    // widest row's **cell count**, which is not known until the cell parser has
    // read them.
    let mut items = Vec::new();
    let mut rows = Vec::with_capacity(lines.len());
    let blank_run = trailing_blank_run(i, &lines);
    for (n, line) in lines.iter().enumerate() {
        // SAFETY: ctx is valid.
        let cells = unsafe { walk_grid_row(rt, i, plan, child, *line, &mut items, &scope)? };
        // The same rule uniform `grid` answers from: a trailing blank line the
        // cell parser reads no cell in is nobody's, and would otherwise be a
        // zero-cell row padded out to the full width with `fill`.
        if cells == 0 && n >= blank_run {
            continue;
        }
        rows.push(cells);
    }
    let width = rows.iter().copied().max().unwrap_or(0);
    // Pad each short row out to the width, from the back forwards so the
    // earlier rows' offsets stay valid while we insert.
    let mut at = items.len();
    for (n, cells) in rows.iter().enumerate().rev() {
        at -= cells;
        for _ in *cells..width {
            items.insert(at + cells, fill_value);
        }
        let _ = n;
    }
    let elem_desc = child_descriptor(plan, child);
    alloc_grid(rt, elem_desc, items, width, region.end())
}

/// Allocate a `Grid` from element refs + width (shared by grid/matrix/ragged).
/// `next` is the position the constructor stopped at.
fn alloc_grid(
    rt: &Rt,
    elem_desc: &'static crate::TypeDescriptor,
    items: Vec<GcRef>,
    width: usize,
    next: Cursor,
) -> WalkResult {
    let payload = crate::collections::GridPayload {
        element_descriptor: elem_desc,
        items,
        width,
    };
    let (heap, safepoint) = rt.safepoint();
    // SAFETY: GridPayload is GRID's payload type.
    let grid_ref = unsafe { heap.alloc_payload(safepoint, &crate::collections::GRID, payload) };
    Ok(Walked {
        value: grid_ref,
        next,
    })
}

fn walk_csv(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let text = region_str(i, region, "csv")?;
    let mut items = Vec::new();
    for token in csv_tokens(region, text) {
        // The field's own region, consumed exactly.
        // SAFETY: ctx is valid.
        let value = unsafe { walk_exact(rt, i, plan, child, token, ExactBound::Field)? };
        scope.root(value);
        items.push(value);
    }
    let elem_desc = child_descriptor(plan, child);
    Ok(Walked {
        value: rt.alloc_vec(elem_desc, items),
        next: region.end(),
    })
}

/// Walk `ws(P)` (§7.5): split on whitespace and apply `P` to each token.
///
/// **A whitespace-delimited token contains no whitespace.** §7.5 says `ws`
/// splits "on one or more spaces or tabs", which names the *separator*; it does
/// not say a `\n` may sit inside a token, and nothing could want it to.
/// Splitting on spaces and tabs alone would run a token through a line ending,
/// making `read ws(int)` over `"1 2\n3 4\n"` three tokens — `1`, `2\n3`, `4\n`
/// — the middle of which faults. A line terminator is not `ws`'s separator but
/// it is still a token terminator, which is the rule [`whitespace_tokens`]
/// applies for `matrix`; sharing that splitter is what stops the two
/// whitespace-token constructors disagreeing about one file.
fn walk_ws(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let text = region_str(i, region, "whitespace-separated tokens")?;
    let mut items = Vec::new();
    for token in whitespace_tokens(region, text) {
        // SAFETY: ctx is valid.
        let value = unsafe { walk_exact(rt, i, plan, child, token, ExactBound::Token)? };
        scope.root(value);
        items.push(value);
    }
    let elem_desc = child_descriptor(plan, child);
    Ok(Walked {
        value: rt.alloc_vec(elem_desc, items),
        next: region.end(),
    })
}

fn walk_sep(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    sep: &str,
    region: ByteRegion,
) -> WalkResult {
    let bytes = region.bytes(i);
    let base = region.start();
    let sep_bytes = sep.as_bytes();
    // The loop below advances by `sep_bytes.len()` on a match, and
    // `starts_with(&[])` is unconditionally true — so an empty separator is an
    // infinite loop that allocates a value per iteration. The compiler makes
    // that unrepresentable (`praxis_input_parser::Separator`); this records
    // what the loop is relying on.
    debug_assert!(
        !sep_bytes.is_empty(),
        "Separator::new refuses an empty separator (IP-10): the loop below cannot advance past one"
    );
    if sep_bytes.is_empty() {
        return Err(ParseFail::at(base.offset(), 0, "a non-empty separator"));
    }
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let mut items = Vec::new();
    let mut token_start = 0usize;
    let mut pos = 0usize;
    while pos < bytes.len() {
        if bytes[pos..].starts_with(sep_bytes) {
            let token = region.subregion(base.advance(token_start), base.advance(pos));
            // SAFETY: ctx is valid.
            let value = unsafe { walk_exact(rt, i, plan, child, token, ExactBound::Token)? };
            scope.root(value);
            items.push(value);
            pos += sep_bytes.len();
            token_start = pos;
        } else {
            pos += 1;
        }
    }
    // Parse the final token.
    if token_start < bytes.len() {
        let token = region.subregion(base.advance(token_start), region.end());
        // SAFETY: ctx is valid.
        let value = unsafe { walk_exact(rt, i, plan, child, token, ExactBound::Token)? };
        scope.root(value);
        items.push(value);
    }
    let elem_desc = child_descriptor(plan, child);
    Ok(Walked {
        value: rt.alloc_vec(elem_desc, items),
        next: region.end(),
    })
}

fn walk_grid(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    child: u32,
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let lines = split_lines(i, region);
    let blank_run = trailing_blank_run(i, &lines);
    let mut items = Vec::new();
    let mut width: Option<usize> = None;
    for (n, line) in lines.iter().enumerate() {
        // SAFETY: ctx is valid.
        let cells = unsafe { walk_grid_row(rt, i, plan, child, *line, &mut items, &scope)? };
        // **A trailing blank line is a row if the cell parser reads cells in
        // it.** `char` does, so `grid(char)` over `"ab\ncd\n  \n"` is 2x3 —
        // which is the same answer that makes `"ab\ncd \n"` ragged, rather than
        // an exception to it. `digit`/`int` read no cell there, so the line
        // belongs to nobody and the grid is 2x2.
        if cells == 0 && n >= blank_run {
            continue;
        }
        // Grid rows must be uniform (§7.5); uneven rows are `walk_grid_ragged`'s
        // job. Uniform in **cells**, which is the only measure that means the
        // same thing for every cell parser: `grid(char)` counts characters and
        // `grid(int)` counts integer tokens. That choice of unit is grid's own;
        // where the fault points is the shared rule, and `uniform_row_width`
        // owns it.
        width = Some(uniform_row_width(
            width,
            cells,
            *line,
            "a grid row of the same cell count as the first",
        )?);
    }
    let width = width.unwrap_or(0);
    let elem_desc = child_descriptor(plan, child);
    alloc_grid(rt, elem_desc, items, width, region.end())
}

// ---- templates (§7.2, §7.3) -----------------------------------------------

/// The run of template parts a capture must stop before: every part from
/// `index + 1` up to (not including) the next capture.
///
/// **The whole run, not its first constraining member.** §7.4 says `text`
/// "minimally consumes text until the following template literal can match";
/// what has to be able to match is everything before the next capture. That is
/// the only reading under which two spellings of one policy agree: §7.9 lowers
/// `\\s+` to its own empty-text part, so bounding by the first part alone would
/// stop `` lines(`{a:text}\\s+bar`) `` at the first space, where `bar` is not,
/// while `` lines(`{a:text} bar`) `` reads the same bytes as `a = "x y"`.
///
/// **A literal's trailing run is one of those parts.** The scanner emits the
/// run at a literal's *trailing* end as an empty literal carrying `SpaceRun` —
/// a literal has one policy slot and it sits in front of the text — so
/// `` `Card {id:int}: {body:rest}` `` bounds `id` by the two-part run
/// `[":" with no policy, "" with `SpaceRun`]`, and `body` starts after the
/// space rather than on it. Taking the *whole* run is what makes that work:
/// bounding by the `":"` alone would stop `id` in the right place and then hand
/// `body` the space the template wrote.
///
/// `None` means the run constrains nothing — it is empty (the next part is a
/// capture), or every member matches the empty string (`\\s*` and a literal
/// with no run in front of it: `WsPolicy::ZeroOrMore`, `WsPolicy::None`, with
/// no text). A capture with nothing to stop before takes the rest of its
/// region, which is the documented answer for a template that asks for
/// zero-or-more.
fn following_bound(
    parts: &[praxis_input_parser::TemplatePartNode],
    index: usize,
) -> Option<&[praxis_input_parser::TemplatePartNode]> {
    use praxis_input_parser::{TemplatePartNode, WsPolicy};
    let rest = &parts[index + 1..];
    let len = rest
        .iter()
        .take_while(|p| matches!(p, TemplatePartNode::Literal { .. }))
        .count();
    let run = &rest[..len];
    let constrains = run.iter().any(|p| match p {
        TemplatePartNode::Literal { text, ws } => {
            !text.is_empty() || !matches!(ws, WsPolicy::None | WsPolicy::ZeroOrMore)
        }
        _ => false,
    });
    constrains.then_some(run)
}

/// Match the literal run `run` at `at`, returning where it ends, or `None`.
///
/// Exactly what `walk_template`'s own `Literal` arm does, in the form the bound
/// scan needs: a lookahead that answers "could the rest of this template's
/// fixed text start here?" without committing.
fn match_literal_run(
    i: &Input<'_>,
    region: ByteRegion,
    base: Cursor,
    bytes: &[u8],
    at: Cursor,
    run: &[praxis_input_parser::TemplatePartNode],
) -> Option<Cursor> {
    let mut cursor = at;
    for part in run {
        let praxis_input_parser::TemplatePartNode::Literal { text, ws } = part else {
            // `following_bound` only ever hands us literals.
            return None;
        };
        cursor = base.advance(consume_ws(bytes, cursor.delta_from(base), *ws)?);
        if !region.from(cursor).bytes(i).starts_with(text.as_bytes()) {
            return None;
        }
        cursor = cursor.advance(text.len());
    }
    Some(cursor)
}

/// The earliest position at or after `cursor` where `run` can match — i.e.
/// where the capture before it must stop.
///
/// "Earliest" is what makes `text` non-greedy, and taking the position *before*
/// the run's leading whitespace policy runs is what keeps that whitespace out of
/// the capture: `` `{name:text} {v:int}` `` on `"foo 3"` stops `name` at the
/// space rather than inside it, because the run is a literal with empty text
/// and `WsPolicy::SpaceRun` whose earliest match is byte 3.
///
/// It does **not** follow that the child fills its region. For
/// `{a:int},{b:int}` on `"12 ,34"` the comma carries `WsPolicy::None` — a
/// template that writes nothing in front of a literal gets no run in front of
/// it — so the bound is the comma at byte 3, `a` is handed `"12 "`, and the
/// space is forgiven by `walk_exact` because it is whitespace `int` did not
/// read (ADR-078). Removing `walk_exact`'s forgiveness would make that program
/// fault at `2..3`.
///
/// `None` means the run does not occur in the rest of the region at all, which
/// is a mismatch the parts themselves will report.
fn capture_bound(
    i: &Input<'_>,
    region: ByteRegion,
    base: Cursor,
    cursor: Cursor,
    run: &[praxis_input_parser::TemplatePartNode],
) -> Option<Cursor> {
    let bytes = region.bytes(i);
    let mut at = cursor;
    loop {
        if match_literal_run(i, region, base, bytes, at, run).is_some() {
            return Some(at);
        }
        // Step by scalar, so a bound never lands inside a multi-byte character.
        at = region.next_scalar(i, at)?;
    }
}

/// Interpret a backtick template against `region` (§7.2, §7.3).
///
/// Walks the `parts` in order: a `Literal` part matches its bytes (honoring the
/// whitespace policy), a `Capture` part recursively walks its child parser to
/// extract one value. Which of §7.3's four results those captures assemble into
/// is [`TemplateShape::of`]'s answer, read from the same `parts` — this
/// function does not classify them itself, and neither does
/// [`template_result_descriptor`], which tags the same value inside a
/// collection. Classifying in two places lets the two disagree (ADR-092).
fn walk_template(
    rt: &Rt,
    i: &Input<'_>,
    plan: &ParserPlan,
    parts: &[praxis_input_parser::TemplatePartNode],
    field_order: &'static [&'static str],
    region: ByteRegion,
) -> WalkResult {
    // Every `GcRef` this helper holds is rooted here. A `NativeScope` claims the
    // tail of `ctx.native_roots`, and `RuntimeRoots` scans the whole store, so a
    // scope opened deeper covers everything its callers hold too.
    // SAFETY: ctx is live and outlives this scope.
    let scope = unsafe { NativeScope::new(rt.ctx) };
    let base = region.start();
    let bytes = region.bytes(i);
    let mut cursor = base;
    // Capture values in field-index order. Each entry is (name, child_node,
    // value): the child node is kept so a multi-anon-capture tuple can build its
    // TupleSchema from the child result descriptors.
    let mut captures: Vec<(Option<&'static str>, u32, GcRef)> = Vec::new();

    for (index, part) in parts.iter().enumerate() {
        match part {
            praxis_input_parser::TemplatePartNode::Literal { text, ws } => {
                // Honor the whitespace policy before matching the literal.
                let Some(after) = consume_ws(bytes, cursor.delta_from(base), *ws) else {
                    return Err(ParseFail::at(cursor.offset(), 0, "whitespace"));
                };
                cursor = base.advance(after);
                // Match the literal bytes verbatim, within the region.
                let lit = text.as_bytes();
                if !region.from(cursor).bytes(i).starts_with(lit) {
                    return Err(ParseFail::at(
                        cursor.offset(),
                        lit.len(),
                        format!("literal {:?}", text),
                    ));
                }
                cursor = cursor.advance(lit.len());
            }
            praxis_input_parser::TemplatePartNode::Capture {
                child,
                field_index: _,
                name,
            } => {
                // **The child is offered the bytes at the cursor, whitespace
                // and all** — a capture answers from the one rule like every
                // other construct (ADR-078's amended §, §7.5). The cursor is
                // *not* advanced past leading horizontal whitespace here:
                // trimming would decide about whitespace without asking the
                // child, so the same child on the same bytes would answer one
                // way as `lines(char)` and another as ``lines(`{a:char}`)``,
                // and a `{a:text}`/`{a:rest}` capture would lose bytes its
                // child reads. `walk_atomic` already puts §7.4's "surrounding
                // horizontal space handled by caller" where it belongs — it
                // trims for the numeric atomics and deliberately does not for
                // `char`, `text` and `rest` — so a trim here would re-impose it
                // one level up for exactly the children that forbid it.
                //
                // The skip applies as a *lookahead offset for the bound scan
                // only* (`search`, below). That is a bound question, not a
                // whitespace-reading one: a capture may not be bounded by its
                // own leading whitespace, or `` `{a:text} {v:int}` `` over
                // `"  foo 3"` would stop `a` at byte 0 — the following literal
                // run is `SpaceRun` + empty text, which matches the indent
                // itself — and hand `int` the word.
                let search = base.advance(skip_capture_ws(bytes, cursor.delta_from(base)));
                // **Bound the capture by the literal that follows it.** §7.4
                // says `text` "minimally consumes text until the following
                // template literal can match"; unbounded, `pre{body:text}post`
                // would eat its own suffix and no template with a trailing
                // literal could match. Done here rather than in `walk_atomic`
                // because it is uniform: every capture is bounded, not only the
                // `text` ones, which is also what stops a `word` at a `-`
                // without adding `-` to `word`'s delimiter set.
                match following_bound(parts, index) {
                    Some(bound) => {
                        match capture_bound(i, region, base, search, bound) {
                            Some(bound) => {
                                // SAFETY: ctx is valid.
                                let value = unsafe {
                                    walk_exact(
                                        rt,
                                        i,
                                        plan,
                                        *child,
                                        region.subregion(cursor, bound),
                                        ExactBound::Capture,
                                    )?
                                };
                                scope.root(value);
                                cursor = bound;
                                captures.push((*name, *child, value));
                            }
                            None => {
                                // The following part does not occur at all. Let
                                // the capture parse naturally so *that part*
                                // reports the mismatch, at the position where it
                                // was actually looked for.
                                // SAFETY: ctx is valid.
                                let walked =
                                    unsafe { walk(rt.ctx, i, plan, *child, region.from(cursor))? };
                                scope.root(walked.value);
                                cursor = walked.next;
                                captures.push((*name, *child, walked.value));
                            }
                        }
                    }
                    None => {
                        // Nothing follows, so there is nothing to stop before:
                        // the capture takes the rest of the region and keeps
                        // its own cursor. Requiring exhaustion here would fault
                        // every root-level template on its input's trailing
                        // newline; whether the region must be filled is the
                        // *parent's* question.
                        // SAFETY: ctx is valid.
                        let walked = unsafe { walk(rt.ctx, i, plan, *child, region.from(cursor))? };
                        scope.root(walked.value);
                        cursor = walked.next;
                        captures.push((*name, *child, walked.value));
                    }
                }
            }
        }
    }

    // Assemble the result per §7.3, returning the position where matching
    // stopped so a `block(...)` parent can advance item by item (§7.5).
    let value = match (TemplateShape::of(parts), captures.as_slice()) {
        // Named captures → Record. Build the schema at runtime.
        (TemplateShape::Record, _) => alloc_record(rt, &captures, field_order),
        // One anonymous capture → the captured value itself.
        (TemplateShape::Scalar { .. }, [(_, _, only)]) => *only,
        // Two or more anonymous captures → Tuple. The schema comes from the
        // child result descriptors, the payload from the captured values.
        (TemplateShape::Tuple, _) => {
            let children: Vec<u32> = captures.iter().map(|(_, c, _)| *c).collect();
            let values: Vec<GcRef> = captures.iter().map(|(_, _, v)| *v).collect();
            alloc_tuple(rt, &children, plan, values)
        }
        // No captures → Unit, and so is `Scalar` paired with anything other
        // than exactly one captured value — a combination the classifier
        // cannot produce, since it counts the same captures this loop pushed.
        // Bound by slice pattern rather than bridged with `expect`: this runs
        // beneath an `extern "C"` entry point, where a panic is undefined
        // behaviour.
        _ => alloc_unit(rt),
    };
    Ok(Walked {
        value,
        next: cursor,
    })
}

/// Where a capture's **bound scan** starts: past zero or more spaces or tabs.
/// Returns that position as an offset into `bytes`.
///
/// This is **not** a [`WsPolicy`](praxis_input_parser::WsPolicy): `SpaceRun` is
/// the one-or-more policy, and a capture may not demand leading whitespace.
///
/// It offsets the bound scan and nothing else — never the **cursor**, which is
/// what the child is offered. Moving the cursor would decide about whitespace
/// without asking the child, and `walk_atomic` already answers that question
/// per atomic, trimming for the numeric ones and deliberately not for `char`,
/// `text` and `rest`. The earliest place the following literal run may match is
/// *after* the capture's own leading whitespace, or a run that can match a
/// space run would bound every indented capture at its first byte.
fn skip_capture_ws(bytes: &[u8], cursor: usize) -> usize {
    let Some(rest) = bytes.get(cursor..) else {
        return cursor;
    };
    cursor + horizontal_ws_run(rest)
}

/// Consume bytes at `cursor` per `ws`, returning the new cursor or `None` if the
/// policy is not satisfied (§7.2).
fn consume_ws(bytes: &[u8], cursor: usize, ws: praxis_input_parser::WsPolicy) -> Option<usize> {
    use praxis_input_parser::WsPolicy;
    let rest = bytes.get(cursor..)?;
    let mut i = 0;
    match ws {
        WsPolicy::None => {
            // The template wrote no run in front of this literal, so no run is
            // consumed. Without this variant every literal would claim
            // `SpaceRun`, and `SpaceRun` would have to accept an empty run to
            // compensate.
        }
        WsPolicy::SpaceRun => {
            // **One or more** spaces or tabs — the flexible §7.2 default, as
            // `WsPolicy`'s own definition states it. A literal the template
            // wrote no run in front of carries `None`, not this policy, so
            // requiring a run here cannot make a template that starts with a
            // literal unmatchable.
            i = horizontal_ws_run(rest);
            if i == 0 {
                return None;
            }
        }
        WsPolicy::ZeroOrMore => {
            i = ascii_ws_run(rest);
        }
        WsPolicy::OneOrMore => {
            // Literally `ZeroOrMore` plus a non-empty check, sharing the same
            // run so the two cannot drift apart.
            i = ascii_ws_run(rest);
            if i == 0 {
                return None;
            }
        }
        WsPolicy::ExactSpace => {
            if rest.first() == Some(&b' ') {
                i = 1;
            } else {
                return None;
            }
        }
        WsPolicy::Newline => {
            // Match `\n`, optionally preceded by `\r`.
            if rest.first() == Some(&b'\r') {
                i = 1;
            }
            if rest.get(i) == Some(&b'\n') {
                i += 1;
            } else {
                return None;
            }
        }
        WsPolicy::Tab => {
            if rest.first() == Some(&b'\t') {
                i = 1;
            } else {
                return None;
            }
        }
    }
    Some(cursor + i)
}

/// Allocate a `Unit` sentinel.
fn alloc_unit(rt: &Rt) -> GcRef {
    // SAFETY: ctx is valid.
    unsafe { (*rt.ctx).unit_ref }
}

/// Allocate a record from named captures (§7.3). Builds (and caches) the
/// `RecordSchema` from the capture names + the child result descriptors, and
/// fills the payload with the captured values. The schema is owned by the cache
/// below, not leaked.
fn alloc_record(
    rt: &Rt,
    captures: &[(Option<&'static str>, u32, GcRef)],
    field_order: &'static [&'static str],
) -> GcRef {
    // **The record is laid out in `field_order`, not in capture order** (§5.6,
    // ADR-152). An anonymous record's identity is its field-name set, so a
    // second parser naming the same fields in another order builds the *same
    // type* — and a field read compiles to a slot index against that one type's
    // definition. Assembling in capture order would put `w` in `h`'s slot for
    // whichever spelling the compiler did not make canonical, and the read
    // would answer the wrong field with no error anywhere.
    //
    // Build the schema fields. Named captures only (the record case requires
    // every capture to have a name in well-formed input; anonymous ones in a
    // named template are a parser-validation concern, treated as `_` here).
    //
    // Each field's descriptor is taken from the CAPTURED VALUE's own header
    // (`value.descriptor()`). record_equals/format/hash dispatch through the
    // schema's per-field descriptor (records.rs), so it must match the value's
    // real type — hardcoding INT here miscompares/misformats/segsfaults on any
    // non-Int field (Text, Char, nested record, …) because the INT callback
    // reinterprets the foreign payload as an i64.
    let ordered = canonical_captures(captures, field_order);
    let fields: Vec<crate::records::RecordField> = ordered
        .iter()
        .map(|(name, _child, value)| crate::records::RecordField {
            name: name.unwrap_or("_"),
            descriptor: value.descriptor(),
        })
        .collect();
    let schema = record_schema_for(fields);
    let items: Vec<GcRef> = ordered.iter().map(|(_, _, v)| *v).collect();
    let payload = crate::records::RecordPayload { schema, items };
    let (heap, safepoint) = rt.safepoint();
    // SAFETY: RecordPayload is RECORD's payload type.
    unsafe { heap.alloc_payload(safepoint, &crate::records::RECORD, payload) }
}

/// `captures` permuted into `field_order`, borrowed unchanged when they already
/// agree.
///
/// They almost always do: a program with one spelling of a shape gets its own
/// order back, which is the whole of `SourceOrder`'s case and nearly all of a
/// compile's. So the common path is one name comparison per field and no
/// allocation, and the copy is paid only by the spelling that lost.
///
/// An empty `field_order` means the plan node builds no record — a tuple or
/// scalar template — and the captures stand as they are.
fn canonical_captures<'a>(
    captures: &'a [(Option<&'static str>, u32, GcRef)],
    field_order: &'static [&'static str],
) -> std::borrow::Cow<'a, [(Option<&'static str>, u32, GcRef)]> {
    let agrees = field_order.len() == captures.len()
        && captures
            .iter()
            .zip(field_order)
            .all(|((name, _, _), want)| *name == Some(*want));
    if agrees || field_order.is_empty() {
        return std::borrow::Cow::Borrowed(captures);
    }
    // A name in `field_order` that no capture carries cannot happen — the order
    // was computed from these same names — but the walk is written to be total
    // rather than to assert: this runs beneath an `extern "C"` entry point,
    // where a panic is undefined behaviour. A capture left over keeps its place
    // at the end, so no field is ever dropped.
    let mut ordered: Vec<(Option<&'static str>, u32, GcRef)> = Vec::with_capacity(captures.len());
    for want in field_order {
        if let Some(c) = captures
            .iter()
            .find(|(name, _, _)| *name == Some(*want) && !ordered.iter().any(|o| o.0 == *name))
        {
            ordered.push(*c);
        }
    }
    for c in captures {
        if !ordered.iter().any(|o| o.0 == c.0) {
            ordered.push(*c);
        }
    }
    std::borrow::Cow::Owned(ordered)
}

/// Allocate a tuple from positional capture values (§7.3). Builds (and caches)
/// the `TupleSchema` from the element descriptors and fills the payload. The
/// schema is owned by the cache below, not leaked.
fn alloc_tuple(rt: &Rt, elements: &[u32], plan: &ParserPlan, values: Vec<GcRef>) -> GcRef {
    let descriptors: Vec<*const crate::TypeDescriptor> = elements
        .iter()
        .map(|&e| child_descriptor(plan, e) as *const _)
        .collect();
    let schema = tuple_schema_for(descriptors);
    let payload = crate::tuples::TuplePayload {
        schema,
        items: values,
    };
    let (heap, safepoint) = rt.safepoint();
    // SAFETY: TuplePayload is TUPLE's payload type.
    unsafe { heap.alloc_payload(safepoint, &crate::tuples::TUPLE, payload) }
}

// ---- parser-built schemas --------------------------------------------------
//
// A named-capture template produces an anonymous record, and an anonymous
// multi-capture template produces a tuple. Both need a schema, and the
// interpreter is the only thing that knows the field descriptors — it learns
// them from the values the child plans produced. So the schemas are built here,
// at runtime, and cached by shape so repeated parses of one template share one.
//
// **These entries own their storage.** `Box::leak`ing them would not be merely
// a leak: a `RecordField::name` is a `&'static str` *borrowed from plan
// storage*, so a cache that outlives the plans holds dangling names. Owning
// them lets `retire_schemas` drop the schemas in the same breath as the plans,
// which is what makes reclaiming either one sound.

/// One cached record schema and everything it points at.
struct RecordSchemaEntry {
    /// `(field name, descriptor address)` — the shape this schema serves.
    key: Vec<(&'static str, usize)>,
    /// The fields the schema borrows. Boxed so the address is stable across the
    /// registry `Vec`'s reallocations. Never read directly.
    #[allow(dead_code)]
    fields: Box<[crate::records::RecordField]>,
    schema: Box<crate::records::RecordSchema>,
}

/// One cached tuple schema and everything it points at.
struct TupleSchemaEntry {
    /// The descriptor-address sequence this schema serves.
    key: Vec<usize>,
    /// The descriptors the schema borrows. See [`RecordSchemaEntry::fields`].
    #[allow(dead_code)]
    descriptors: Box<[*const crate::TypeDescriptor]>,
    schema: Box<crate::tuples::TupleSchema>,
}

/// One cached enum schema and everything it points at.
struct EnumSchemaEntry {
    /// The case-name sequence this schema serves.
    key: Vec<&'static str>,
    /// The variant shapes the schema borrows. See [`RecordSchemaEntry::fields`].
    #[allow(dead_code)]
    variants: Box<[crate::enums::EnumVariantShape]>,
    /// The one-slot payload arrays each variant shape borrows.
    #[allow(dead_code)]
    payloads: Box<[*const crate::TypeDescriptor]>,
    schema: Box<crate::enums::EnumSchema>,
}

/// The parser interpreter's schema cache.
#[derive(Default)]
struct ParserSchemas {
    records: Vec<RecordSchemaEntry>,
    tuples: Vec<TupleSchemaEntry>,
    enums: Vec<EnumSchemaEntry>,
}

// SAFETY: the entries hold raw `*const TypeDescriptor`s into process-static
// descriptor data and `&'static str`s into plan storage. Nothing is mutated
// after construction, and every access goes through the mutex below.
unsafe impl Send for ParserSchemas {}

static SCHEMAS: std::sync::Mutex<Option<ParserSchemas>> = std::sync::Mutex::new(None);

/// Drop every schema the parser interpreter has built.
///
/// # Safety
/// Every schema pointer handed out must be dead — no live `RecordPayload` or
/// `TuplePayload` may still name one. `retire_parser_plans` is the only
/// intended caller and holds the [`HeapDrained`](crate::HeapDrained) proof of
/// exactly that.
pub(crate) unsafe fn retire_schemas() {
    *SCHEMAS
        .lock()
        .unwrap_or_else(std::sync::PoisonError::into_inner) = None;
}

/// Run `f` against the schema cache, created on first use.
///
/// The three `*_schema_for` builders below all start here, and it is the only
/// thing that locks: "every access goes through the mutex" is the sentence
/// [`ParserSchemas`]' `unsafe impl Send` rests on.
fn with_schemas<R>(f: impl FnOnce(&mut ParserSchemas) -> R) -> R {
    let mut guard = SCHEMAS
        .lock()
        .unwrap_or_else(std::sync::PoisonError::into_inner);
    f(guard.get_or_insert_with(ParserSchemas::default))
}

/// Re-borrow cache-owned data as `'static`, which is what the schema structs
/// below declare their borrows to be.
///
/// # Safety
/// The slice must live in a box the cache entry being built owns, so that it
/// outlives every schema pointer handed out from that entry. [`retire_schemas`]
/// is what discharges the obligation.
unsafe fn erase_lifetime<T: 'static>(slice: &[T]) -> &'static [T] {
    // SAFETY: per the contract above, the owning entry outlives the borrow.
    unsafe { &*(slice as *const [T]) }
}

/// The `RecordSchema` for a template shape, built once and shared afterwards.
///
/// Cached by the `(field-name, descriptor)` sequence. The descriptor half is
/// load-bearing: two templates with the same field *names* but different
/// capture types (e.g. `{x:int}` vs `{x:word}`) must NOT share a schema —
/// `alloc_record` records each field's real descriptor, and
/// `record_equals`/`record_format`/`record_hash` dispatch through the schema's
/// per-field descriptor, so a name-only cache would hand the second template
/// the first template's descriptor and recompare/reformat via the wrong
/// callback.
fn record_schema_for(
    fields: Vec<crate::records::RecordField>,
) -> *const crate::records::RecordSchema {
    with_schemas(|cache| {
        let key: Vec<(&'static str, usize)> = fields
            .iter()
            .map(|f| (f.name, f.descriptor as usize))
            .collect();
        if let Some(entry) = cache.records.iter().find(|e| e.key == key) {
            return &*entry.schema as *const _;
        }
        let fields: Box<[crate::records::RecordField]> = fields.into_boxed_slice();
        // SAFETY: `RecordSchema::fields` declares `&'static`, and the slice
        // lives in the boxed `fields` this entry owns.
        let borrowed = unsafe { erase_lifetime(&fields) };
        // A named-capture template produces an *anonymous* structural record
        // (§5.6): its identity is its shape, so two templates with the same
        // fields yield records that compare equal.
        let schema = Box::new(crate::records::RecordSchema {
            identity: crate::records::SchemaIdentity::Anonymous,
            fields: borrowed,
        });
        let raw: *const crate::records::RecordSchema = &*schema;
        cache.records.push(RecordSchemaEntry {
            key,
            fields,
            schema,
        });
        raw
    })
}

/// The `EnumSchema` for a `choice`'s case list, built once and shared
/// afterwards, so two parses of one template produce values that compare equal.
///
/// `choice(Name: P, …)` synthesizes an **anonymous** enum (§7.5,
/// `synthesize::ParserAst::Choice`), so its identity is its case-name shape and
/// the key is that sequence.
///
/// Every payload slot is **null** — unknown. The interpreter learns a case's
/// value type from the value the child plan produced, never from a static type,
/// and a null slot says exactly that: the value's own descriptor answers, and
/// it is read off the object's header, so it is never wrong. The arity is still
/// exact (one payload per case), which is what sizes the payload.
fn enum_schema_for(cases: &'static [(&'static str, u32)]) -> *const crate::enums::EnumSchema {
    with_schemas(|cache| {
        let key: Vec<&'static str> = cases.iter().map(|(name, _)| *name).collect();
        if let Some(entry) = cache.enums.iter().find(|e| e.key == key) {
            return &*entry.schema as *const _;
        }
        // One unknown slot per case, in one owned array the variant shapes
        // borrow disjoint single-element windows of.
        let payloads: Box<[*const crate::TypeDescriptor]> =
            vec![std::ptr::null(); cases.len()].into_boxed_slice();
        let variants: Box<[crate::enums::EnumVariantShape]> = key
            .iter()
            .enumerate()
            .map(|(i, name)| {
                // SAFETY: the window lives in the boxed `payloads` this
                // entry owns.
                let slot = unsafe { erase_lifetime(&payloads[i..=i]) };
                crate::enums::EnumVariantShape {
                    name,
                    payload: slot,
                }
            })
            .collect::<Vec<_>>()
            .into_boxed_slice();
        // SAFETY: as the slot above, for the boxed `variants`.
        let borrowed = unsafe { erase_lifetime(&variants) };
        let schema = Box::new(crate::enums::EnumSchema {
            identity: crate::records::SchemaIdentity::Anonymous,
            variants: borrowed,
        });
        let raw: *const crate::enums::EnumSchema = &*schema;
        cache.enums.push(EnumSchemaEntry {
            key,
            variants,
            payloads,
            schema,
        });
        raw
    })
}

/// The `TupleSchema` for a descriptor sequence, built once and shared
/// afterwards, so same-shaped tuples compare structurally equal.
fn tuple_schema_for(
    descriptors: Vec<*const crate::TypeDescriptor>,
) -> *const crate::tuples::TupleSchema {
    with_schemas(|cache| {
        let key: Vec<usize> = descriptors.iter().map(|p| *p as usize).collect();
        if let Some(entry) = cache.tuples.iter().find(|e| e.key == key) {
            return &*entry.schema as *const _;
        }
        let descriptors: Box<[*const crate::TypeDescriptor]> = descriptors.into_boxed_slice();
        // SAFETY: the slice lives in the boxed `descriptors` this entry owns.
        let borrowed = unsafe { erase_lifetime(&descriptors) };
        let schema = Box::new(crate::tuples::TupleSchema {
            descriptors: borrowed,
        });
        let raw: *const crate::tuples::TupleSchema = &*schema;
        cache.tuples.push(TupleSchemaEntry {
            key,
            descriptors,
            schema,
        });
        raw
    })
}

// ---- byte-splitting helpers -----------------------------------------------
//
// `split_lines` and `split_sections` live in `cursor.rs`, because they produce
// positions and positions are that module's business.

/// Skip leading horizontal whitespace (spaces and tabs).
fn trim_leading_ws(bytes: &[u8]) -> &[u8] {
    &bytes[horizontal_ws_run(bytes)..]
}

/// Take a run of integer characters (optional `-` + digits), returning the text
/// and the byte length consumed.
///
/// `pub(crate)` for `Text.int()` (ADR-136), which is the second caller and the
/// reason this is a shared function rather than a local one: `parse(t, int)` and
/// `t.int()` are two spellings of "read a number out of text", and a program
/// that gets different answers from them has found a defect in one of us. The
/// method requires the run to cover the *whole* trimmed text; the atomic stops
/// where the run stops and hands the rest to the template.
pub(crate) fn take_int_run(bytes: &[u8]) -> (&str, usize) {
    let mut end = 0;
    if end < bytes.len() && bytes[end] == b'-' {
        end += 1;
    }
    while end < bytes.len() && bytes[end].is_ascii_digit() {
        end += 1;
    }
    // SAFETY: ASCII digits are valid UTF-8.
    let s = std::str::from_utf8(&bytes[..end]).unwrap_or("");
    (s, end)
}

/// Take a run of decimal floating-point characters (optional `-`, digits, an
/// optional `.` and fraction, an optional `e±NN` exponent), returning the text
/// and the byte length consumed (§7.4 `float`).
///
/// `pub(crate)` for `Text.float()`, for the reason [`take_int_run`] gives.
///
/// Note that this accepts a leading `+` and [`take_int_run`] does not. That
/// asymmetry is §7.4's as implemented, and it is carried into the two methods
/// rather than papered over there: changing an atomic's accepted set is a
/// change to the input language, and it wants its own decision.
pub(crate) fn take_float_run(bytes: &[u8]) -> (&str, usize) {
    let mut end = 0;
    if end < bytes.len() && (bytes[end] == b'-' || bytes[end] == b'+') {
        end += 1;
    }
    let int_start = end;
    while end < bytes.len() && bytes[end].is_ascii_digit() {
        end += 1;
    }
    let mut saw_digit = end > int_start;
    if end < bytes.len() && bytes[end] == b'.' {
        let after_dot = end + 1;
        let mut frac = after_dot;
        while frac < bytes.len() && bytes[frac].is_ascii_digit() {
            frac += 1;
        }
        // A trailing `.` with no fraction is not part of the number: `1.` in
        // `1.` is a `1` followed by a literal `.` the template may need.
        if frac > after_dot {
            saw_digit = true;
            end = frac;
        }
    }
    if !saw_digit {
        return ("", 0);
    }
    // An exponent only counts if it is complete; `1e` is `1` followed by `e`.
    if end < bytes.len() && (bytes[end] == b'e' || bytes[end] == b'E') {
        let mut exp = end + 1;
        if exp < bytes.len() && (bytes[exp] == b'-' || bytes[exp] == b'+') {
            exp += 1;
        }
        let digits_start = exp;
        while exp < bytes.len() && bytes[exp].is_ascii_digit() {
            exp += 1;
        }
        if exp > digits_start {
            end = exp;
        }
    }
    // SAFETY: every byte accepted above is ASCII.
    let s = std::str::from_utf8(&bytes[..end]).unwrap_or("");
    (s, end)
}

/// Take an identifier run under §4.1's **one** character class, returning the
/// byte length consumed (§7.4 `identifier`).
///
/// Zero if the run does not start one. Invalid UTF-8 simply ends the run —
/// `identifier` produces a source-slice `Text`, whose invariant is that its
/// bytes are valid UTF-8.
fn take_ident_run(bytes: &[u8]) -> usize {
    // Scan as far as the input decodes; a bad byte simply ends the run.
    let s = match std::str::from_utf8(bytes) {
        Ok(s) => s,
        Err(e) => std::str::from_utf8(&bytes[..e.valid_up_to()]).unwrap_or_default(),
    };
    praxis_syntax::ident::ident_run_len(s)
}

/// Take a run of word characters (non-whitespace, non-delimiter).
fn take_word_run(bytes: &[u8]) -> (&str, usize) {
    let mut end = 0;
    while end < bytes.len()
        && !is_ws(bytes[end])
        && bytes[end] != b','
        && bytes[end] != b'\n'
        && bytes[end] != b'\r'
    {
        end += 1;
    }
    let s = std::str::from_utf8(&bytes[..end]).unwrap_or("");
    (s, end)
}

/// Horizontal whitespace: space and tab, and nothing else.
fn is_ws(b: u8) -> bool {
    b == b' ' || b == b'\t'
}

/// Length of the leading run of horizontal whitespace in `bytes`.
///
/// The one spelling of that run for the whole module — `skip_line_boundary`,
/// `skip_chars`'s `Whitespace` arm, `skip_capture_ws`, `consume_ws`'s
/// `SpaceRun` arm and `trim_leading_ws` all ask here. They are one lexical
/// class, not five policies, and the policies differ only in what they *do*
/// with the count (advance a cursor, require it non-empty, slice at it).
///
/// Byte-wise on purpose: space and tab are single-byte scalars and cannot occur
/// inside a multi-byte one, so scanning bytes can never land mid-scalar. Every
/// caller depends on that. (The cell and scan loops step by scalar because
/// *they* can.)
fn horizontal_ws_run(bytes: &[u8]) -> usize {
    bytes.iter().take_while(|&&b| is_ws(b)).count()
}

/// Length of the leading run of ASCII whitespace in `bytes` — [`is_ws`]'s class
/// *plus* line endings, and so always at least [`horizontal_ws_run`].
///
/// That inclusion is the point: `SkipPolicy::Newlines` is the broader policy and
/// `WsPolicy::{ZeroOrMore, OneOrMore}` the broader runs, which is easy to get
/// backwards from the names alone. See [`skip_chars`] for the full note and the
/// test that pins the ordering.
fn ascii_ws_run(bytes: &[u8]) -> usize {
    bytes.iter().take_while(|b| b.is_ascii_whitespace()).count()
}

/// Determine the element descriptor for a child plan node's *result* type. A
/// constructor `lines(P)` produces `Vec[result(P)]`, so its element descriptor is
/// the descriptor of `result(P)`.
///
/// Because the collection descriptors (`VEC`, `GRID`) are **uniform** — the
/// per-instance element type lives in the payload, not the descriptor — a nested
/// constructor's result descriptor is just `VEC`/`GRID` regardless of how deep
/// the nesting goes. The payload chain carries the inner element types, so
/// `vec_format`/`vec_equals`/`vec_hash` recurse correctly through it. Collapsing
/// the subtree to its leaf atomic instead would mis-tag every intermediate
/// Vec/Grid — a silent mis-dispatch in any nested-collection format/eq/hash.
///
/// `RECORD`, `ENUM` and `TUPLE` are uniform in exactly the same way: one
/// descriptor for every shape, with the `RecordSchema`/`EnumSchema`/
/// `TupleSchema` in the payload. So every arm below answers a fixed descriptor
/// or recurses; none of them ever needs to *construct* one.
fn child_descriptor(plan: &ParserPlan, child: u32) -> &'static crate::TypeDescriptor {
    match &plan.nodes[child as usize] {
        // Atomics produce their scalar.
        PlanNode::Atomic { kind } => atomic_descriptor(*kind),
        // Collection constructors produce a Vec (lines/sections/csv/ws/sep) or a
        // Grid. Uniform descriptors — the element type is in the payload.
        PlanNode::Lines { .. }
        | PlanNode::Sections { .. }
        | PlanNode::Csv { .. }
        | PlanNode::Ws { .. }
        | PlanNode::Sep { .. }
        | PlanNode::Scan { .. } => &crate::collections::VEC,
        PlanNode::Grid { .. } => &crate::collections::GRID,
        // Named sections produce an anonymous record (uniform descriptor; the
        // schema is in the payload, built at runtime by `walk_sections_named`).
        PlanNode::SectionsNamed { .. } => &crate::records::RECORD,
        // A block produces a flattened anonymous record (uniform descriptor).
        PlanNode::Block { .. } => &crate::records::RECORD,
        // choice/optional produce an enum (uniform descriptor; tag + payload).
        PlanNode::Choice { .. } | PlanNode::Optional { .. } => &crate::enums::ENUM,
        // one_of produces a Char; chars produces a Vec[Char].
        PlanNode::OneOf { .. } => &scalars::CHAR,
        PlanNode::Characters { .. } => &crate::collections::VEC,
        // matrix / ragged grid produce a Grid.
        PlanNode::Matrix { .. } | PlanNode::GridRagged { .. } => &crate::collections::GRID,
        // A template's result is one of §7.3's four shapes, decided by the same
        // classifier that assembles the value.
        PlanNode::Template { parts, .. } => template_result_descriptor(plan, parts),
    }
}

/// The scalar descriptor for an atomic kind.
///
/// Which kinds share a descriptor is [`AtomicClass::of`]'s decision, not this
/// function's, and it is the same decision `synthesize::atomic_type` reads for
/// the *static* type — `uint` is an `Int` on both sides because
/// `ScalarType::UInt` has no runtime object to describe (§7.4). Two copies of
/// that grouping are precisely how a descriptor comes to disagree with the type
/// behind it.
fn atomic_descriptor(kind: AtomicKind) -> &'static crate::TypeDescriptor {
    match AtomicClass::of(kind) {
        AtomicClass::Int => &scalars::INT,
        AtomicClass::Float => &scalars::FLOAT,
        AtomicClass::Byte => &scalars::BYTE,
        AtomicClass::Char => &scalars::CHAR,
        AtomicClass::Text => &crate::text::TEXT,
    }
}

/// The descriptor of a template's *result*, which is the tag a collection built
/// from that template carries for its elements. One arm per §7.3 shape, from
/// the same [`TemplateShape::of`] that decides the value in [`walk_template`].
///
/// **The tuple arm is a fixed descriptor, not a constructed one** (ADR-092).
/// There is nothing to construct: `TUPLE` is uniform like `VEC` and `RECORD`,
/// and the per-shape `TupleSchema` lives in the payload (`tuples.rs`), where
/// `alloc_tuple` interns it. Tagging ``read lines(`{int},{int}`)``'s elements
/// anything else would hold real tuples in a mistagged `Vec`, print them
/// through the wrong format callback, and compare them unequal to the same Vec
/// built with `push`, because `vec_equals` bails on unequal element tags before
/// comparing an element.
fn template_result_descriptor(
    plan: &ParserPlan,
    parts: &[praxis_input_parser::TemplatePartNode],
) -> &'static crate::TypeDescriptor {
    match TemplateShape::of(parts) {
        TemplateShape::Unit => &scalars::UNIT,
        // One anonymous capture → the child's own result descriptor.
        //
        // Not a guessed default: this is the tag a *collection* carries for its
        // elements, and `vec_format`, `vec_equals` and `vec_hash` dispatch
        // through exactly that tag (ADR-078 Decision 5). A fixed `&scalars::INT`
        // here would give `lines(`{word}`)` a `Vec` of `Text` objects whose
        // element descriptor says `Int`, rendering a `Text` payload through the
        // `Int` callback.
        //
        // Deriving it is correct because a capture names its own parser body.
        TemplateShape::Scalar { child } => child_descriptor(plan, child),
        TemplateShape::Record => &crate::records::RECORD,
        TemplateShape::Tuple => &crate::tuples::TUPLE,
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn test_plan(nodes: Vec<PlanNode>, root: u32) -> ParserPlan {
        ParserPlan {
            nodes: Box::leak(nodes.into_boxed_slice()),
            template_parts: &[],
            literals: &[],
            root,
        }
    }

    // `split_lines`/`split_sections` are covered by `cursor.rs`'s own tests:
    // they produce `ByteRegion`s over an `Input`, so their gates live beside
    // the types whose invariants they establish.

    /// **ADR-136.** `t.int()`/`t.float()` and `parse(t, int)`/`parse(t, float)`
    /// read the same set, because they run the same scanner.
    ///
    /// This is the gate on that claim, and it is written as the *difference from
    /// the obvious implementation*: every row below is a text where
    /// `i64::from_str`/`f64::from_str` disagrees with §7.4's atomic, so a
    /// rewrite in terms of `from_str` turns each of them red.
    ///
    /// `abi::whole_trimmed` is the method side; it requires the run to cover the
    /// whole trimmed text, which is the only difference between a method and an
    /// atomic (an atomic hands the rest of the line to its template).
    #[test]
    fn a_method_and_an_atomic_read_the_same_number() {
        fn whole(s: &str, run: fn(&[u8]) -> (&str, usize)) -> bool {
            let t = s.trim();
            let (text, len) = run(t.as_bytes());
            !text.is_empty() && len == t.len()
        }

        // `from_str` takes these; §7.4 does not, so neither does the method.
        for s in ["+5", "1_000"] {
            assert!(s.parse::<i64>().is_ok() || s == "1_000");
            assert!(!whole(s, take_int_run), "`{s}` is not an `int`");
        }
        for s in ["1.", "inf", "infinity", "nan", "NaN", "-inf"] {
            assert!(s.parse::<f64>().is_ok(), "`{s}` is a Rust float");
            assert!(!whole(s, take_float_run), "`{s}` is not a §7.4 `float`");
        }

        // …and the ordinary spellings are read by both, trimmed.
        for s in ["12", " -7 ", "0"] {
            assert!(whole(s, take_int_run), "`{s}` is an `int`");
        }
        for s in ["1.5", " -2 ", "+5.0", "1e10", "3"] {
            assert!(whole(s, take_float_run), "`{s}` is a `float`");
        }

        // A run that stops short is a rejection for the method and a *partial*
        // read for the atomic — the one place the two differ, stated directly.
        assert_eq!(take_int_run(b"12abc"), ("12", 2));
        assert!(!whole("12abc", take_int_run));
    }

    #[test]
    fn take_int_run_parses_negative() {
        let (s, len) = take_int_run(b"-42abc");
        assert_eq!(s, "-42");
        assert_eq!(len, 3);
    }

    /// §7.4's ten atomic parsers all exist at runtime: every kind parses
    /// something and has a descriptor, and `uint`, `float`, `byte` and
    /// `identifier` mean what §7.4 says they mean.
    ///
    /// The type half is in `praxis-input-parser`'s `synthesize`; the closed-set
    /// half is `atomic_round_trips_keywords` in its `ast.rs`.
    #[test]
    fn every_atomic_the_design_requires_has_a_parser_and_a_type() {
        /// Parse `input` with one atomic and return the consumed length, or
        /// `None` on a parse failure.
        fn parse_one(kind: AtomicKind, input: &str) -> Option<(crate::Runtime, GcRef, usize)> {
            let mut rt = crate::Runtime::new();
            let text = rt.alloc_text(input);
            let mut ctx = rt.context();
            ctx.input_source = text;
            let plan = test_plan(vec![PlanNode::Atomic { kind }], 0);
            let i = unsafe { Input::new(text) }.expect("a Text is UTF-8");
            let out = unsafe { walk(&mut ctx, &i, &plan, plan.root, i.whole()) };
            out.ok().map(|w| (rt, w.value, w.next.offset()))
        }

        // Every kind has a descriptor. Exhaustive by `ALL`, so a new atomic
        // cannot be added without one.
        for kind in AtomicKind::ALL {
            let _ = atomic_descriptor(*kind);
        }

        // `uint` is an Int and refuses a leading `-` — the non-negativity is
        // the parse rule, because `ScalarType::UInt` has no runtime object.
        let (_rt, v, consumed) = parse_one(AtomicKind::UInt, "42rest").expect("uint reads 42");
        assert_eq!(v.as_int(), 42);
        assert_eq!(consumed, 2);
        assert!(
            parse_one(AtomicKind::UInt, "-1").is_none(),
            "`uint` refuses a negative"
        );
        // …and `int` still accepts it, so the two are different rules.
        let (_rt, v, _) = parse_one(AtomicKind::Int, "-1").expect("int reads -1");
        assert_eq!(v.as_int(), -1);

        // `float`.
        for (input, expected, consumed) in [
            ("3.5", 3.5_f64, 3),
            ("-0.25x", -0.25, 5),
            ("2", 2.0, 1),
            ("1e3", 1000.0, 3),
            ("1.5e-2", 0.015, 6),
            // A trailing `.` is not part of the number: the template may need it.
            ("7.", 7.0, 1),
        ] {
            let (_rt, v, got) = parse_one(AtomicKind::Float, input)
                .unwrap_or_else(|| panic!("float reads {input}"));
            assert_eq!(v.as_float(), expected, "for {input}");
            assert_eq!(got, consumed, "for {input}");
        }
        assert!(parse_one(AtomicKind::Float, "x").is_none());

        // `byte` is a decimal integer in 0..=255 — not a raw input byte, which
        // could not be re-sliced as Text without breaking the UTF-8 invariant.
        let (_rt, v, _) = parse_one(AtomicKind::Byte, "255").expect("byte reads 255");
        assert_eq!(v.as_byte(), 255);
        assert!(
            parse_one(AtomicKind::Byte, "256").is_none(),
            "256 is not a byte"
        );
        assert!(
            parse_one(AtomicKind::Byte, "-1").is_none(),
            "-1 is not a byte"
        );

        // `identifier` uses §4.1's one class, so a Unicode name is a name, and
        // the run stops where an identifier stops.
        for (input, expected) in [
            ("name rest", "name"),
            ("λx-1", "λx"),
            ("_x9=2", "_x9"),
            ("日本語:", "日本語"),
        ] {
            let (_rt, v, _) = parse_one(AtomicKind::Identifier, input)
                .unwrap_or_else(|| panic!("identifier reads {input}"));
            assert_eq!(v.as_text(), expected, "for {input}");
        }
        assert!(
            parse_one(AtomicKind::Identifier, "9x").is_none(),
            "a digit does not start an identifier"
        );
    }

    #[test]
    fn text_slices_in_later_sections_point_at_their_actual_source_bytes() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("first\n\nsecond");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Word,
                },
                PlanNode::Sections { child: 0 },
            ],
            1,
        );

        let result =
            unsafe { run_root(&mut ctx, &plan, input) }.expect("sections(word) should parse");
        let values: Vec<&str> = result.as_vec().iter().map(GcRef::as_text).collect();

        assert_eq!(values, vec!["first", "second"]);
    }

    /// **The owner of a slice is the buffer that was *parsed*,** not whatever
    /// the context happens to call its input: `parse(text, P)` hands the
    /// interpreter a `Text` that is not `ctx.input_source`.
    #[test]
    fn a_parse_of_a_non_input_text_owns_its_slices() {
        let mut rt = crate::Runtime::new();
        // The context's input is one buffer…
        let stdin_buffer = rt.alloc_text("XXXXXXXXXXXXXXXX");
        // …and the thing being parsed is a different one.
        let subject = rt.alloc_text("alpha beta");
        let mut ctx = rt.context();
        ctx.input_source = stdin_buffer;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Word,
                },
                PlanNode::Ws { child: 0 },
            ],
            1,
        );

        let result = unsafe { run_root(&mut ctx, &plan, subject) }.expect("ws(word) should parse");
        let values: Vec<&str> = result.as_vec().iter().map(GcRef::as_text).collect();

        assert_eq!(
            values,
            vec!["alpha", "beta"],
            "a parse's slices must be views of the text it parsed, not of ctx.input_source"
        );
    }

    /// **A parse of a slice does not extend the owner chain.**
    ///
    /// `parse(t, P)` takes its owner from the argument, and that argument may
    /// itself be a slice. Naming it directly makes every produced `Text` one
    /// link longer than the last, and `text_bytes` walks the chain on every
    /// read — so `t = parse(t, rest)` in a loop would go quadratic and
    /// eventually overflow the stack. `Input::new` resolves to the root owned
    /// `Text` and carries the base offset, so a slice of a slice is not
    /// constructible from here however deep the argument was.
    #[test]
    fn a_parse_of_a_slice_does_not_extend_the_owner_chain() {
        let mut rt = crate::Runtime::new();
        let owned = rt.alloc_text("XXalpha betaXX");
        // The subject is a *slice* of the owned text: bytes [2, 12).
        // SAFETY: `owned` is the live Text allocated above.
        let subject = unsafe { rt.alloc_text_slice(owned, 2, 10) }.expect("[2, 12) is in range");
        assert_eq!(subject.as_text(), "alpha beta");
        let mut ctx = rt.context();
        ctx.input_source = owned;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Word,
                },
                PlanNode::Ws { child: 0 },
            ],
            1,
        );

        let result = unsafe { run_root(&mut ctx, &plan, subject) }.expect("ws(word) should parse");
        let items: Vec<GcRef> = result.as_vec().to_vec();
        let values: Vec<&str> = items.iter().map(GcRef::as_text).collect();
        assert_eq!(
            values,
            vec!["alpha", "beta"],
            "the base offset must be applied, or the slices name the wrong bytes"
        );

        for item in items {
            // SAFETY: each item is a live Text produced by the parse.
            let payload = unsafe {
                &*(item.payload::<crate::text::TextPayload>() as *const crate::text::TextPayload)
            };
            let crate::text::TextPayload::Slice(slice) = payload else {
                panic!("a `word` is a source slice");
            };
            // SAFETY: a slice's owner is a live Text.
            let owner = unsafe {
                &*(slice.owner().payload::<crate::text::TextPayload>()
                    as *const crate::text::TextPayload)
            };
            assert!(
                owner.is_owned(),
                "a parse of a slice must still name the ROOT owned text, not another slice"
            );
        }
    }

    #[test]
    fn unicode_grid_cells_are_parsed_once_per_scalar() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("é");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Char,
                },
                PlanNode::Grid { child: 0 },
            ],
            1,
        );

        let grid = unsafe { run_root(&mut ctx, &plan, input) }
            .expect("one Unicode scalar is one valid grid cell");
        let payload = unsafe { &*grid.payload::<crate::collections::GridPayload>() };

        assert_eq!(payload.width, 1);
        assert_eq!(payload.items.len(), 1);
    }

    /// **ADR-107, the parser half.** `read grid(char)` is the shape the interning
    /// was written for: the `char` atomic runs once per cell, so uninterned a
    /// 140×140 AoC map boxes 19,600 `Char`s with at most 128 distinct values.
    ///
    /// The assertion is a *count*, not a spot check, because the property is
    /// "the parse allocates nothing per cell" and only a count can say that. One
    /// object is allocated by the whole parse — the `Grid` itself, whose cells
    /// live in a Rust `Vec<GcRef>` rather than in the heap — and that number is
    /// independent of how many cells there are, which the second grid below is
    /// what proves. A per-cell allocation makes the first delta 10 and the
    /// second 26.
    #[test]
    fn a_grid_of_chars_interns_its_ascii_cells() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("#.#\n.#.\n#.#");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Char,
                },
                PlanNode::Grid { child: 0 },
            ],
            1,
        );

        let before = rt.heap().stats().live_count;
        let grid = unsafe { run_root(&mut ctx, &plan, input) }.expect("a 3×3 ASCII grid parses");
        let after = rt.heap().stats().live_count;
        assert_eq!(
            after - before,
            1,
            "nine cells, one allocation: the Grid object and no Chars at all"
        );

        let payload = unsafe { &*grid.payload::<crate::collections::GridPayload>() };
        assert_eq!(payload.items.len(), 9);
        let hash = rt.immortals().small_char('#' as u32).expect("ASCII");
        let dot = rt.immortals().small_char('.' as u32).expect("ASCII");
        for (n, cell) in payload.items.iter().enumerate() {
            // Every cell is one of exactly two objects, and they are the
            // runtime's own table entries rather than a cache of the parser's.
            let expected = if n % 2 == 0 { hash } else { dot };
            assert_eq!(cell.as_ptr(), expected.as_ptr(), "cell {n}");
        }

        // The same shape at a different size costs the same: the delta is the
        // Grid, not the cells.
        let bigger = rt.alloc_text("#.#.#\n.#.#.\n#.#.#\n.#.#.\n#.#.#");
        let mut ctx = rt.context();
        ctx.input_source = bigger;
        let before = rt.heap().stats().live_count;
        let _ = unsafe { run_root(&mut ctx, &plan, bigger) }.expect("a 5×5 ASCII grid parses");
        assert_eq!(
            rt.heap().stats().live_count - before,
            1,
            "twenty-five cells cost exactly what nine did"
        );
    }

    /// The branch a regression would delete. A cell outside the interned range
    /// is still a fresh object per cell, and still holds its own scalar.
    #[test]
    fn a_non_ascii_grid_cell_is_still_a_fresh_object() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("éé");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Char,
                },
                PlanNode::Grid { child: 0 },
            ],
            1,
        );

        let before = rt.heap().stats().live_count;
        let grid = unsafe { run_root(&mut ctx, &plan, input) }.expect("two scalars, one row");
        assert_eq!(
            rt.heap().stats().live_count - before,
            3,
            "the Grid and one Char per cell — `é` is outside the interned range"
        );

        let payload = unsafe { &*grid.payload::<crate::collections::GridPayload>() };
        assert_eq!(payload.items.len(), 2);
        assert_ne!(payload.items[0].as_ptr(), payload.items[1].as_ptr());
        assert_eq!(payload.items[0].as_char(), 'é');
        assert_eq!(payload.items[1].as_char(), 'é');
    }

    /// `one_of` is the parser's *other* door to `Rt::alloc_char`, and the grid
    /// test does not reach it — `walk_one_of` builds its `Char` itself rather
    /// than through the `char` atomic.
    #[test]
    fn one_of_answers_the_interned_char() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("<");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let literals: &'static [&'static str] = Box::leak(vec!["<>^v"].into_boxed_slice());
        let nodes: &'static [PlanNode] =
            Box::leak(vec![PlanNode::OneOf { chars_index: 0 }].into_boxed_slice());
        let plan = ParserPlan {
            nodes,
            template_parts: &[],
            literals,
            root: 0,
        };

        let before = rt.heap().stats().live_count;
        let value = unsafe { run_root(&mut ctx, &plan, input) }.expect("`<` is one of \"<>^v\"");
        assert_eq!(
            rt.heap().stats().live_count,
            before,
            "an interned Char never enters the live registry"
        );
        assert_eq!(
            value.as_ptr(),
            rt.immortals()
                .small_char('<' as u32)
                .expect("ASCII")
                .as_ptr()
        );
        assert_eq!(value.as_char(), '<');
    }

    #[test]
    fn csv_rest_parser_is_bounded_to_each_token() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("a,b");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Rest,
                },
                PlanNode::Csv { child: 0 },
            ],
            1,
        );

        let result = unsafe { run_root(&mut ctx, &plan, input) }.expect("csv(rest) should parse");
        let values: Vec<&str> = result.as_vec().iter().map(GcRef::as_text).collect();

        assert_eq!(values, vec!["a", "b"]);
    }

    /// **An empty csv field is an empty `Text`, not a panic.** This runs inside
    /// `extern "C"`, where a panic is undefined behaviour, and `"10,20,"` is
    /// all it takes to produce a field that trims to nothing.
    #[test]
    fn an_empty_csv_field_does_not_panic() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("10,20,");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Rest,
                },
                PlanNode::Csv { child: 0 },
            ],
            1,
        );

        let result = unsafe { run_root(&mut ctx, &plan, input) }
            .expect("an empty csv field is an empty Text, not an abort");
        let values: Vec<&str> = result.as_vec().iter().map(GcRef::as_text).collect();
        assert_eq!(
            values,
            vec!["10", "20", ""],
            "the field after the last comma is empty, and being empty is not a panic"
        );
    }

    // --- whitespace matcher (§7.2) -------------------------------------------

    /// A failed `choice` reports the deepest case failure, not a generic
    /// `"any choice case"` at its own offset.
    ///
    /// The case that got furthest is the case the input was trying to be, and
    /// its own message is the one worth showing; a generic message would name
    /// the outermost construct and point at a byte where nothing went wrong.
    #[test]
    fn a_failed_choice_reports_the_deepest_case_failure() {
        fn lit(text: &'static str) -> praxis_input_parser::TemplatePartNode {
            praxis_input_parser::TemplatePartNode::Literal {
                text,
                ws: praxis_input_parser::WsPolicy::None,
            }
        }
        fn capture(child: u32) -> praxis_input_parser::TemplatePartNode {
            praxis_input_parser::TemplatePartNode::Capture {
                child,
                field_index: None,
                name: None,
            }
        }

        let mut rt = crate::Runtime::new();
        // `a{int}` fails at byte 1; `ab{int}` gets one byte further and fails
        // at byte 2. The second is the one to report.
        let input = rt.alloc_text("abz");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let short: &'static [praxis_input_parser::TemplatePartNode] =
            Box::leak(vec![lit("a"), capture(0)].into_boxed_slice());
        let long: &'static [praxis_input_parser::TemplatePartNode] =
            Box::leak(vec![lit("ab"), capture(0)].into_boxed_slice());
        let cases: &'static [(&'static str, u32)] =
            Box::leak(vec![("Short", 1u32), ("Long", 2u32)].into_boxed_slice());
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Int,
                },
                PlanNode::Template {
                    parts: short,
                    field_order: &[],
                },
                PlanNode::Template {
                    parts: long,
                    field_order: &[],
                },
                PlanNode::Choice { cases },
            ],
            3,
        );

        let fail = unsafe { run_root(&mut ctx, &plan, input) }
            .expect_err("neither case can read `z` as an int");
        assert_eq!(
            fail.expected, "int",
            "the deepest case's own expectation, not \"any choice case\""
        );
        assert_eq!(
            fail.input_span.0, 2,
            "byte 2 is where the case that got furthest actually broke"
        );
    }

    /// A ragged row's fault names *the row that broke it*, in both constructors
    /// that have the rule.
    ///
    /// **Both halves are asserted in one test on purpose.** The gate is on the
    /// *pair* stating one rule, so neither constructor can drift into naming
    /// the whole region it was handed and stay green.
    #[test]
    fn a_ragged_row_fault_names_the_row_in_grid_and_in_matrix() {
        let mut rt = crate::Runtime::new();

        // `"1 2\n  \n3 4\n"`: the interior blank line is a zero-token row, and
        // its own bytes are 4..6.
        let input = rt.alloc_text("1 2\n  \n3 4\n");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Int,
                },
                PlanNode::Matrix { child: 0 },
            ],
            1,
        );
        let fail = unsafe { run_root(&mut ctx, &plan, input) }
            .expect_err("a zero-token row is not two tokens wide");
        assert_eq!(fail.expected, "rectangular matrix row");
        assert_eq!(
            fail.input_span,
            (4, 6),
            "the blank line's own bytes, not the region matrix was handed"
        );

        // The analogous grid, which must answer the same way.
        // `"12\n  \n34\n"`: the blank line is 3..5.
        let input = rt.alloc_text("12\n  \n34\n");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let plan = test_plan(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Digit,
                },
                PlanNode::Grid { child: 0 },
            ],
            1,
        );
        let fail = unsafe { run_root(&mut ctx, &plan, input) }
            .expect_err("a zero-cell row is not two cells wide");
        assert_eq!(
            fail.expected,
            "a grid row of the same cell count as the first"
        );
        assert_eq!(fail.input_span, (3, 5), "the blank line's own bytes");
    }

    /// **The `chars` skip policies, ordered by what they skip.**
    ///
    /// `Whitespace` is spaces and tabs; `Newlines` is those **and** line
    /// endings. The names imply the opposite containment — "whitespace" reads
    /// like the superset — which invites the conclusion that `skip: whitespace`
    /// can absorb an input file's trailing newline. It cannot. The sets are
    /// deliberately kept as they are (they are the ones §7.5's
    /// `chars(one_of("^v<>"), skip: whitespace)` example needs, and swapping
    /// them would change what every existing `skip: newlines` program accepts),
    /// so what has to exist instead is this: a test that states the inclusion,
    /// and fails if anyone quietly swaps the arms to make the names read
    /// straight.
    #[test]
    fn the_skip_policies_are_ordered_by_what_they_skip() {
        use praxis_input_parser::SkipPolicy;
        let rt = crate::Runtime::new();
        let owner = rt.alloc_text(" \t\n\r x");
        // SAFETY: `owner` is a Text allocated just above and `rt` outlives `i`.
        let i = unsafe { Input::new(owner) }.expect("a Text is UTF-8");
        let region = i.whole();
        let skipped = |p| skip_chars(&i, region, region.start(), p).offset();

        assert_eq!(skipped(SkipPolicy::None), 0, "`none` skips nothing");
        assert_eq!(
            skipped(SkipPolicy::Whitespace),
            2,
            "`whitespace` is HORIZONTAL whitespace: it stops at the newline"
        );
        assert_eq!(
            skipped(SkipPolicy::Newlines),
            5,
            "`newlines` is horizontal whitespace AND line endings — the broader policy"
        );
        assert!(
            skipped(SkipPolicy::Newlines) > skipped(SkipPolicy::Whitespace),
            "`newlines` must skip a superset of `whitespace`, however the two are named"
        );
        // The one description both the diagnostic and the runtime comment
        // quote, so the names are never the only thing a reader is given.
        assert_eq!(SkipPolicy::Whitespace.skips(), "spaces and tabs");
        assert_eq!(
            SkipPolicy::Newlines.skips(),
            "spaces, tabs and line endings"
        );
        // Sweep the closed list, so a fourth policy cannot arrive without a
        // description and a position in the ordering.
        let mut previous = 0usize;
        for policy in SkipPolicy::ALL.iter().copied() {
            assert!(
                !policy.skips().is_empty(),
                "every skip policy states what it skips"
            );
            let n = skipped(policy);
            assert!(
                n >= previous,
                "SkipPolicy::ALL is ordered from narrowest to broadest; {policy:?} skips {n}"
            );
            previous = n;
        }
    }

    /// **`chars` that cannot read its whole region faults**, rather than
    /// returning `Ok` at the first child failure and silently dropping the
    /// rest: `chars(digit, skip: none)` over `"12x34"` is a parse failure, not
    /// `[1, 2]`.
    ///
    /// The rule §7.5 wants falls out of running the skip policy once more after
    /// the last match: whatever the skip does not absorb, the child must read.
    #[test]
    fn chars_that_cannot_read_the_whole_region_is_a_parse_failure() {
        fn parse(input: &str, skip: praxis_input_parser::SkipPolicy) -> Option<Vec<i64>> {
            let mut rt = crate::Runtime::new();
            let text = rt.alloc_text(input);
            let mut ctx = rt.context();
            ctx.input_source = text;
            let plan = test_plan(
                vec![
                    PlanNode::Atomic {
                        kind: AtomicKind::Digit,
                    },
                    PlanNode::Characters { child: 0, skip },
                ],
                1,
            );
            unsafe { run_root(&mut ctx, &plan, text) }
                .ok()
                .map(|v| v.as_vec().iter().map(GcRef::as_int).collect())
        }

        use praxis_input_parser::SkipPolicy;
        assert_eq!(parse("1234", SkipPolicy::None), Some(vec![1, 2, 3, 4]));
        assert_eq!(
            parse("12x34", SkipPolicy::None),
            None,
            "a child failure inside the region is the parse's failure, not a short answer"
        );
        // The skip policy is what a trailing run is for, and it is applied
        // after the last match as well as between matches.
        assert_eq!(
            parse("1 2 3 \t", SkipPolicy::Whitespace),
            Some(vec![1, 2, 3])
        );
        assert_eq!(parse("1 2\n", SkipPolicy::Newlines), Some(vec![1, 2]));
        assert_eq!(
            parse("1\n2", SkipPolicy::None),
            None,
            "`skip: none` absorbs nothing, so an interior newline is a mismatch"
        );
        // **The byte at the end of an input file is the file's terminator, not
        // a byte the program asked any parser to read.** It IS inside the
        // region — the root region is the whole buffer — and `walk_characters`
        // forgives it because it is whitespace the child declined
        // (`ByteRegion::is_all_whitespace`, the bound half of `cursor`'s rule).
        // No skip policy has to absorb it and no root trim has to hide it;
        // requiring `chars` to consume it would fault every newline-terminated
        // file, §7.5's own `chars(one_of("^v<>"), skip: whitespace)` example
        // included. `parse("1\n2", None)` above states the other half: a
        // newline *inside* the data is still a mismatch under `skip: none`.
        assert_eq!(
            parse("12\n", SkipPolicy::None),
            Some(vec![1, 2]),
            "the file's own terminator is whitespace the child declined"
        );
    }

    /// **A `grid` cell is whatever the cell parser reads**, so `grid(int)` reads
    /// one integer **token** per cell and `grid(digit)` reads one digit. §7.5's
    /// two examples are `grid(char)` and `grid(digit)`, and `digit` exists *for*
    /// the one-digit case — if `grid(int)` meant that too, `digit` would name
    /// nothing.
    ///
    /// Measuring width in bytes and walking the child once per byte answers
    /// neither semantics: over `"12\n34\n"` it yields **four** cells
    /// `[12, 2, 34, 4]`, the token and then the token's tail.
    #[test]
    fn a_grid_cell_is_whatever_its_cell_parser_reads() {
        fn cells(kind: AtomicKind, input: &str) -> Option<(usize, Vec<i64>)> {
            let mut rt = crate::Runtime::new();
            let text = rt.alloc_text(input);
            let mut ctx = rt.context();
            ctx.input_source = text;
            let plan = test_plan(
                vec![PlanNode::Atomic { kind }, PlanNode::Grid { child: 0 }],
                1,
            );
            let grid = unsafe { run_root(&mut ctx, &plan, text) }.ok()?;
            let payload = unsafe { &*grid.payload::<crate::collections::GridPayload>() };
            Some((
                payload.width,
                payload.items.iter().map(|r| r.as_int()).collect(),
            ))
        }

        // `int` is an integer token, so each row of `"12\n34\n"` is one cell.
        assert_eq!(
            cells(AtomicKind::Int, "12\n34\n"),
            Some((1, vec![12, 34])),
            "one token per cell — not [12, 2, 34, 4], and not [1, 2, 3, 4] either"
        );
        // …and a row of several tokens is several cells.
        assert_eq!(
            cells(AtomicKind::Int, "1 2\n3 4\n"),
            Some((2, vec![1, 2, 3, 4]))
        );
        // `digit` is the per-digit parser, which is what it is for.
        assert_eq!(
            cells(AtomicKind::Digit, "12\n34\n"),
            Some((2, vec![1, 2, 3, 4])),
            "`digit` names the one-digit-per-cell case, so `int` must not"
        );
        // Rows must agree in **cells**, which is the only measure that means
        // the same thing for every cell parser.
        assert_eq!(
            cells(AtomicKind::Int, "1 2\n3\n"),
            None,
            "two cells then one is not a rectangle"
        );
    }

    /// **`scan` advances one scalar at a time, not one byte**, so it never
    /// attempts a match at a continuation byte — a position that is not a
    /// character at all.
    ///
    /// Over `"ééé"` there are exactly three scalar starts and three
    /// continuation bytes. A byte-stepping `scan` visits six positions; a
    /// scalar-stepping one visits three, and `one_of("é")` matches at each.
    #[test]
    fn scan_advances_by_scalar_across_a_multibyte_run() {
        let mut rt = crate::Runtime::new();
        let input = rt.alloc_text("ééé");
        let mut ctx = rt.context();
        ctx.input_source = input;
        let literals: &'static [&'static str] = Box::leak(vec!["é"].into_boxed_slice());
        let nodes: &'static [PlanNode] = Box::leak(
            vec![
                PlanNode::OneOf { chars_index: 0 },
                PlanNode::Scan { child: 0 },
            ]
            .into_boxed_slice(),
        );
        let plan = ParserPlan {
            nodes,
            template_parts: &[],
            literals,
            root: 1,
        };

        let result = unsafe { run_root(&mut ctx, &plan, input) }.expect("scan never fails");
        let chars: Vec<char> = result
            .as_vec()
            .iter()
            .map(|r| char::from_u32(unsafe { *r.payload::<u32>() }).expect("a Char"))
            .collect();
        assert_eq!(
            chars,
            vec!['é', 'é', 'é'],
            "three scalars, and no attempt at the three continuation bytes between them"
        );
    }

    #[test]
    fn consume_ws_space_run_requires_one_or_more_spaces_or_tabs() {
        use praxis_input_parser::WsPolicy;
        assert_eq!(consume_ws(b"  ,x", 0, WsPolicy::SpaceRun), Some(2));
        assert_eq!(consume_ws(b"\t\t,x", 0, WsPolicy::SpaceRun), Some(2));
        assert_eq!(
            consume_ws(b"x", 0, WsPolicy::SpaceRun),
            None,
            "SpaceRun is the one-or-more policy; absence of whitespace must not match"
        );
    }

    #[test]
    fn consume_ws_one_or_more_requires_at_least_one() {
        use praxis_input_parser::WsPolicy;
        assert_eq!(consume_ws(b"  x", 0, WsPolicy::OneOrMore), Some(2));
        assert_eq!(consume_ws(b"x", 0, WsPolicy::OneOrMore), None);
    }

    #[test]
    fn consume_ws_exact_space_matches_one() {
        use praxis_input_parser::WsPolicy;
        assert_eq!(consume_ws(b" x", 0, WsPolicy::ExactSpace), Some(1));
        assert_eq!(consume_ws(b"\tx", 0, WsPolicy::ExactSpace), None);
    }

    #[test]
    fn consume_ws_newline_matches_crlf_and_lf() {
        use praxis_input_parser::WsPolicy;
        assert_eq!(consume_ws(b"\r\nx", 0, WsPolicy::Newline), Some(2));
        assert_eq!(consume_ws(b"\nx", 0, WsPolicy::Newline), Some(1));
        assert_eq!(consume_ws(b"x", 0, WsPolicy::Newline), None);
    }

    #[test]
    fn single_anonymous_template_capture_uses_its_child_descriptor() {
        let parts: &'static [praxis_input_parser::TemplatePartNode] = Box::leak(
            vec![praxis_input_parser::TemplatePartNode::Capture {
                child: 0,
                field_index: None,
                name: None,
            }]
            .into_boxed_slice(),
        );
        let nodes: &'static [PlanNode] = Box::leak(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Word,
                },
                PlanNode::Template {
                    parts,
                    field_order: &[],
                },
            ]
            .into_boxed_slice(),
        );
        let plan = ParserPlan {
            nodes,
            template_parts: &[],
            literals: &[],
            root: 1,
        };

        assert_eq!(
            child_descriptor(&plan, plan.root).id(),
            crate::text::TEXT.id(),
            "lines(`{{word}}`) must carry Text as its Vec element descriptor"
        );
    }

    /// The sibling of the test above: that one gates the *one*-capture tag,
    /// this one gates the *many*-capture tag (ADR-092).
    ///
    /// `Int` and `Word`, not `Int` and `Int`, on purpose: an implementation
    /// that reached for the first child's descriptor — the shape the
    /// one-capture arm has — would answer `INT` and stay red here.
    #[test]
    fn multi_anonymous_template_captures_are_a_tuple() {
        let parts: &'static [praxis_input_parser::TemplatePartNode] = Box::leak(
            vec![
                praxis_input_parser::TemplatePartNode::Capture {
                    child: 0,
                    field_index: Some(0),
                    name: None,
                },
                praxis_input_parser::TemplatePartNode::Literal {
                    text: ",",
                    ws: praxis_input_parser::WsPolicy::None,
                },
                praxis_input_parser::TemplatePartNode::Capture {
                    child: 1,
                    field_index: Some(1),
                    name: None,
                },
            ]
            .into_boxed_slice(),
        );
        let nodes: &'static [PlanNode] = Box::leak(
            vec![
                PlanNode::Atomic {
                    kind: AtomicKind::Int,
                },
                PlanNode::Atomic {
                    kind: AtomicKind::Word,
                },
                PlanNode::Template {
                    parts,
                    field_order: &[],
                },
            ]
            .into_boxed_slice(),
        );
        let plan = ParserPlan {
            nodes,
            template_parts: &[],
            literals: &[],
            root: 2,
        };

        assert_eq!(
            child_descriptor(&plan, plan.root).id(),
            crate::tuples::TUPLE.id(),
            "lines(`{{int}},{{word}}`) must carry Tuple as its Vec element descriptor"
        );
    }
}