hf2q 0.1.22

//! GBNF runtime sampler for hf2q constrained decoding.
//!
//! The runtime maintains a set of pushdown stacks over `(rule_id, elem_idx)`
//! positions in the parsed grammar. Character terminals consume decoded
//! Unicode while token terminals consume one tokenizer token by id. A
//! candidate is accepted iff at least one stack remains valid after applying
//! the appropriate terminal domain.
//!
//! Implementation notes:
//!   - `Pos(rule_id, elem_idx)` identifies a position in the flat rules —
//!     O(1) lookup into `rules[rule_id][elem_idx]`, stable across clones.
//!   - `accept_char` returns a fresh `Stacks` set (immutable-style) rather
//!     than mutating in place. The caller assigns it back to the live state.
//!   - `PartialUtf8` stores remaining bytes in an `i8`: zero is clean,
//!     positive is incomplete, and negative is invalid.
//!
//! This file is **pure compute** — no axum / mlx-native dependencies. It
//! runs entirely on CPU and can be exercised without a loaded model, which
//! is why the full JSON-acceptance test suite below has no fixture cost.

use super::parser::{Grammar, GretElement, GretType};
use regex::bytes::Regex;
use std::sync::Arc;

/// Maximum unconstrained output retained while a public lazy grammar waits
/// for a regex trigger. The peer currently leaves this buffer unbounded;
/// hf2q fails closed at the repository's structured-output resource limit.
pub const MAX_LAZY_TRIGGER_BUFFER_BYTES: usize = 64 * 1024;

/// Model-bound lazy-grammar controls after request strings and token ids have
/// been resolved against the authoritative tokenizer.
///
/// `preserved_tokens` is retained as part of the request/runtime contract and
/// cache identity. hf2q's token-byte table already decodes every sampled token
/// without dropping special tokens, so it does not require a second decoder
/// allow-list at runtime.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct LazyGrammarConfig {
    pub token_triggers: Vec<u32>,
    pub trigger_patterns: Vec<String>,
    pub preserved_tokens: Vec<u32>,
}

#[derive(Debug, Clone)]
struct LazyBufferedToken {
    token_id: u32,
    start: usize,
    end: usize,
}

#[derive(Debug, Clone)]
struct PublicLazyRuntime {
    token_triggers: Vec<u32>,
    trigger_patterns: Vec<Regex>,
    buffer: Vec<u8>,
    positions: Vec<LazyBufferedToken>,
}

// ---------------------------------------------------------------------------
// Position + Stack types
// ---------------------------------------------------------------------------

/// Stable position inside the flat `rules[rule_id][elem_idx]` buffer.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Pos {
    pub rule_id: u32,
    pub elem_idx: u32,
}

impl Pos {
    pub fn new(rule_id: u32, elem_idx: u32) -> Self {
        Self { rule_id, elem_idx }
    }
    /// Advance to the next element in the same rule. Caller ensures the
    /// next element exists.
    pub fn advance(self) -> Self {
        Self {
            rule_id: self.rule_id,
            elem_idx: self.elem_idx + 1,
        }
    }
}

/// A grammar pushdown stack — a list of `Pos` entries. The top is `.last()`.
pub type Stack = Vec<Pos>;
pub type Stacks = Vec<Stack>;

/// One decoded vocabulary candidate while applying a grammar mask.
///
/// Code points live in one flat arena owned by the caller.  `cursor` and
/// `end` are offsets into that arena, which avoids one heap allocation per
/// vocabulary token.  The rejection walk advances `cursor` temporarily and
/// restores it while unwinding.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(super) struct GrammarCandidate {
    pub index: usize,
    pub token_id: u32,
    pub cursor: usize,
    pub end: usize,
    pub partial_utf8: PartialUtf8,
}

// ---------------------------------------------------------------------------
// Partial UTF-8 accumulator
// ---------------------------------------------------------------------------

/// Accumulator for multi-byte UTF-8 sequences that straddle token boundaries.
/// After accepting a token whose last bytes form a partial UTF-8 sequence,
/// `partial` carries the decoded bits and the remaining byte count into the
/// next token.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct PartialUtf8 {
    pub value: u32,
    /// Bytes remaining to complete the code point. `0` = no partial state
    /// (clean). Negative values represent invalid state.
    pub n_remain: i8,
}

/// Decode one token's bytes into the shared code-point arena, continuing a
/// partial UTF-8 sequence inherited from the live grammar runtime.
///
/// This deliberately matches [`GrammarRuntime::accept_bytes`]: malformed
/// lead/continuation bytes reject the candidate, while an incomplete trailing
/// code point is retained in `PartialUtf8` for the next sampled token.
pub(super) fn decode_candidate_utf8(
    bytes: &[u8],
    partial_start: PartialUtf8,
    code_points: &mut Vec<u32>,
) -> Option<PartialUtf8> {
    if partial_start.n_remain < 0 {
        return None;
    }

    let mut i = 0usize;
    let mut partial = partial_start;
    if partial.n_remain > 0 {
        while i < bytes.len() && partial.n_remain > 0 {
            let byte = bytes[i];
            if (byte & 0xC0) != 0x80 {
                return None;
            }
            partial.value = (partial.value << 6) | (byte & 0x3F) as u32;
            partial.n_remain -= 1;
            i += 1;
        }
        if partial.n_remain > 0 {
            return Some(partial);
        }
        code_points.push(partial.value);
        partial = PartialUtf8::default();
    }

    while i < bytes.len() {
        let first = bytes[i];
        let (needed, mut value) = if first & 0x80 == 0 {
            (0i8, first as u32)
        } else if first & 0xE0 == 0xC0 {
            (1, (first & 0x1F) as u32)
        } else if first & 0xF0 == 0xE0 {
            (2, (first & 0x0F) as u32)
        } else if first & 0xF8 == 0xF0 {
            (3, (first & 0x07) as u32)
        } else {
            return None;
        };
        i += 1;

        let mut remain = needed;
        while i < bytes.len() && remain > 0 {
            let byte = bytes[i];
            if (byte & 0xC0) != 0x80 {
                return None;
            }
            value = (value << 6) | (byte & 0x3F) as u32;
            i += 1;
            remain -= 1;
        }
        if remain > 0 {
            return Some(PartialUtf8 {
                value,
                n_remain: remain,
            });
        }
        code_points.push(value);
    }

    Some(partial)
}

// ---------------------------------------------------------------------------
// End-of-sequence test
// ---------------------------------------------------------------------------

fn is_end_of_sequence(e: &GretElement) -> bool {
    matches!(e.ty, GretType::End | GretType::Alt)
}

fn is_token_terminal(ty: GretType) -> bool {
    matches!(
        ty,
        GretType::Token | GretType::TokenNot | GretType::TokenAny | GretType::TokenNotSet
    )
}

/// Return whether `token_id` matches the token terminal at `pos`, plus the
/// first element after that terminal. `TokenNotSet` owns the immediately
/// following sorted `TokenSetMember` run. Membership is logarithmic in the
/// bounded exclusion count and never enumerates the vocabulary.
fn match_token(grammar: &Grammar, pos: Pos, token_id: u32) -> (bool, Pos) {
    let Some(element) = at(grammar, pos).copied() else {
        return (false, pos);
    };
    let mut after = pos.advance();
    match element.ty {
        GretType::Token => (element.value == token_id, after),
        GretType::TokenNot => (element.value != token_id, after),
        GretType::TokenAny => (true, after),
        GretType::TokenNotSet => {
            let Some(rule) = grammar.rules.get(pos.rule_id as usize) else {
                return (false, pos);
            };
            let start = pos.elem_idx as usize + 1;
            let Some(end) = start.checked_add(element.value as usize) else {
                return (false, pos);
            };
            let Some(members) = rule.get(start..end) else {
                return (false, pos);
            };
            if members.len() < 2
                || members
                    .iter()
                    .any(|member| member.ty != GretType::TokenSetMember)
            {
                return (false, pos);
            }
            let excluded = members
                .binary_search_by_key(&token_id, |member| member.value)
                .is_ok();
            after.elem_idx = end as u32;
            (!excluded, after)
        }
        _ => (false, pos),
    }
}

/// Look up `pos` in the grammar's flat rule buffer. Returns `None` if the
/// position is out of bounds — that shouldn't happen for a valid grammar but
/// the sampler defends against it so a corrupt state can't panic the process.
fn at<'a>(grammar: &'a Grammar, pos: Pos) -> Option<&'a GretElement> {
    grammar
        .rules
        .get(pos.rule_id as usize)
        .and_then(|r| r.get(pos.elem_idx as usize))
}

// ---------------------------------------------------------------------------
// match_char — does `chr` satisfy the char-range element at `pos`?
// ---------------------------------------------------------------------------

/// Returns `(matched, after_range_pos)`. `after_range_pos` points to the
/// element immediately following the char-range group (regardless of match).
pub fn match_char(grammar: &Grammar, mut pos: Pos, chr: u32) -> (bool, Pos) {
    let rule = match grammar.rules.get(pos.rule_id as usize) {
        Some(r) => r.as_slice(),
        None => return (false, pos),
    };
    let head = rule[pos.elem_idx as usize];
    let is_positive_char = matches!(head.ty, GretType::Char | GretType::CharAny);
    debug_assert!(is_positive_char || head.ty == GretType::CharNot);

    let mut found = false;
    loop {
        let cur = rule[pos.elem_idx as usize];
        let next = rule.get(pos.elem_idx as usize + 1);
        if next.map(|e| e.ty) == Some(GretType::CharRngUpper) {
            // inclusive range, e.g. [a-z]
            found = found || (cur.value <= chr && chr <= next.unwrap().value);
            pos.elem_idx += 2;
        } else if cur.ty == GretType::CharAny {
            found = true;
            pos.elem_idx += 1;
        } else {
            // exact char match, e.g. [a] or "a"
            found = found || cur.value == chr;
            pos.elem_idx += 1;
        }
        if rule.get(pos.elem_idx as usize).map(|e| e.ty) != Some(GretType::CharAlt) {
            break;
        }
    }
    (found == is_positive_char, pos)
}

/// Returns `true` iff some continuation of the given partial UTF-8 sequence
/// could satisfy the char range at `pos`.
pub fn match_partial_char(grammar: &Grammar, mut pos: Pos, partial: PartialUtf8) -> bool {
    let rule = match grammar.rules.get(pos.rule_id as usize) {
        Some(r) => r.as_slice(),
        None => return false,
    };
    let head = rule[pos.elem_idx as usize];
    let is_positive_char = matches!(head.ty, GretType::Char | GretType::CharAny);

    let n_remain = partial.n_remain;
    if n_remain < 0 {
        return false;
    }
    if n_remain == 1 && partial.value < 2 {
        return false;
    }

    let shift = (n_remain as u32) * 6;
    let mut low = partial.value << shift;
    let mask = if shift == 0 { 0 } else { (1u32 << shift) - 1 };
    let high = low | mask;
    if low == 0 {
        if n_remain == 2 {
            low = 1 << 11;
        } else if n_remain == 3 {
            low = 1 << 16;
        }
    }

    loop {
        let cur = rule[pos.elem_idx as usize];
        let next = rule.get(pos.elem_idx as usize + 1);
        if next.map(|e| e.ty) == Some(GretType::CharRngUpper) {
            let end = next.unwrap().value;
            if cur.value <= high && low <= end {
                return is_positive_char;
            }
            pos.elem_idx += 2;
        } else if cur.ty == GretType::CharAny {
            return true;
        } else {
            if low <= cur.value && cur.value <= high {
                return is_positive_char;
            }
            pos.elem_idx += 1;
        }
        if rule.get(pos.elem_idx as usize).map(|e| e.ty) != Some(GretType::CharAlt) {
            break;
        }
    }
    !is_positive_char
}

// ---------------------------------------------------------------------------
// advance_stack — expand a stack until every entry is a terminal element
// ---------------------------------------------------------------------------

/// Transforms one stack into the set of stacks that all end at a character or
/// token terminal. Handles `RuleRef` expansion (with alternatives) and
/// skips `End`/`Alt` elements at the stack top.
// Stage 9's supported twelve-key any-order object reaches exactly 32,768
// active stacks at its widest byte boundary. This measured baseline is the
// smallest power-of-two cap that preserves the required schema.
const MAX_ACTIVE_STACKS: usize = 32_768;

pub fn advance_stack(grammar: &Grammar, stack: Stack, new_stacks: &mut Stacks) -> bool {
    let mut todo: Vec<Stack> = Vec::new();
    todo.push(stack);
    // `seen` dedups across our BFS frontier.
    let mut seen: std::collections::HashSet<Stack> = std::collections::HashSet::new();

    while let Some(curr_stack) = todo.pop() {
        if seen.contains(&curr_stack) {
            continue;
        }
        seen.insert(curr_stack.clone());

        if curr_stack.is_empty() {
            if !new_stacks.contains(&curr_stack) {
                new_stacks.push(curr_stack);
                if new_stacks.len() > MAX_ACTIVE_STACKS {
                    return false;
                }
            }
            continue;
        }

        let top = *curr_stack.last().unwrap();
        let elem = match at(grammar, top) {
            Some(e) => *e,
            None => continue,
        };

        match elem.ty {
            GretType::RuleRef => {
                let rule_id = elem.value;
                let target_rule = match grammar.rules.get(rule_id as usize) {
                    Some(r) => r,
                    None => continue,
                };

                let mut subpos = Pos::new(rule_id, 0);
                loop {
                    // `next_stack` = curr_stack without its top.
                    let mut next_stack: Stack = curr_stack[..curr_stack.len() - 1].to_vec();
                    // If this ref is followed by another element, push that.
                    let follow = top.advance();
                    if let Some(nxt) = at(grammar, follow) {
                        if !is_end_of_sequence(nxt) {
                            next_stack.push(follow);
                        }
                    }
                    // If the target rule's alternate has content, push its start.
                    if let Some(first) = target_rule.get(subpos.elem_idx as usize) {
                        if !is_end_of_sequence(first) {
                            next_stack.push(subpos);
                        }
                    }
                    todo.push(next_stack);

                    // Scan to end-of-sequence within the target rule.
                    loop {
                        let e = match target_rule.get(subpos.elem_idx as usize) {
                            Some(e) => *e,
                            None => {
                                break;
                            }
                        };
                        if is_end_of_sequence(&e) {
                            break;
                        }
                        subpos.elem_idx += 1;
                    }
                    // If stopped on Alt, continue to next alternative; else done.
                    let stop = target_rule.get(subpos.elem_idx as usize).map(|e| e.ty);
                    if stop == Some(GretType::Alt) {
                        subpos.elem_idx += 1;
                    } else {
                        break;
                    }
                }
            }
            GretType::Char
            | GretType::CharNot
            | GretType::CharAny
            | GretType::Token
            | GretType::TokenNot
            | GretType::TokenAny
            | GretType::TokenNotSet => {
                if !new_stacks.contains(&curr_stack) {
                    new_stacks.push(curr_stack);
                    if new_stacks.len() > MAX_ACTIVE_STACKS {
                        return false;
                    }
                }
            }
            _ => {
                // End / Alt / CharAlt / CharRngUpper — stack should never
                // rest on those. Silently drop in the Rust port (C++ aborts).
                tracing::debug!(
                    "grammar::advance_stack: dropping stack with top element type {:?}",
                    elem.ty
                );
            }
        }
    }
    true
}

// ---------------------------------------------------------------------------
// accept_chr — consume a single character from a stack
// ---------------------------------------------------------------------------

/// Feeds one character to one stack, producing zero or more successor stacks.
fn accept_chr_into(grammar: &Grammar, stack: &Stack, chr: u32, new_stacks: &mut Stacks) -> bool {
    if stack.is_empty() {
        return true;
    }
    let top = *stack.last().unwrap();
    let elem = match at(grammar, top) {
        Some(e) => *e,
        None => return true,
    };
    if matches!(
        elem.ty,
        GretType::End
            | GretType::Alt
            | GretType::Token
            | GretType::TokenNot
            | GretType::TokenAny
            | GretType::TokenNotSet
            | GretType::TokenSetMember
    ) {
        return true;
    }

    let (matched, after) = match_char(grammar, top, chr);
    if matched {
        let mut new_stack: Stack = stack[..stack.len() - 1].to_vec();
        // If the next element isn't End/Alt, push it.
        if let Some(nxt) = at(grammar, after) {
            if !is_end_of_sequence(nxt) {
                new_stack.push(after);
            }
        }
        return advance_stack(grammar, new_stack, new_stacks);
    }
    true
}

/// Accept one character against the current stack set, returning the new set.
pub fn accept_char(grammar: &Grammar, stacks: &Stacks, chr: u32) -> Stacks {
    let mut new_stacks: Stacks = Vec::with_capacity(stacks.len());
    for stack in stacks {
        if !accept_chr_into(grammar, stack, chr, &mut new_stacks) {
            return Vec::new();
        }
    }
    new_stacks
}

// ---------------------------------------------------------------------------
// Candidate-set rejection
// ---------------------------------------------------------------------------

/// Return the candidates rejected by every live grammar stack.
///
/// Candidates rejected by one alternate are passed to the next alternate,
/// so a token is rejected only when no
/// stack can consume it.  Unlike the legacy mask path, this advances each
/// grammar branch once for a whole candidate set instead of cloning a complete
/// `GrammarRuntime` for every vocabulary entry.
pub(super) fn reject_candidates(
    grammar: &Grammar,
    stacks: &Stacks,
    candidates: &[GrammarCandidate],
    code_points: &[u32],
) -> Vec<GrammarCandidate> {
    if candidates.is_empty() {
        return Vec::new();
    }
    if stacks.is_empty() {
        return candidates.to_vec();
    }

    let mut rejects = reject_candidates_for_stack(grammar, &stacks[0], candidates, code_points);
    for stack in &stacks[1..] {
        if rejects.is_empty() {
            break;
        }
        rejects = reject_candidates_for_stack(grammar, stack, &rejects, code_points);
    }
    rejects
}

/// Return candidates rejected by one grammar stack.  Recursive calls consume
/// one code point from every matching candidate together, then advance the
/// grammar stack once.  `cursor` is restored before a rejection is returned so
/// callers can retry that same token against another alternate stack.
fn reject_candidates_for_stack(
    grammar: &Grammar,
    stack: &Stack,
    candidates: &[GrammarCandidate],
    code_points: &[u32],
) -> Vec<GrammarCandidate> {
    if candidates.is_empty() {
        return Vec::new();
    }

    if stack.is_empty() {
        return candidates
            .iter()
            .copied()
            .filter(|candidate| {
                candidate.cursor < candidate.end || candidate.partial_utf8.n_remain != 0
            })
            .collect();
    }

    let top = *stack.last().expect("non-empty stack");
    let Some(elem) = at(grammar, top) else {
        return candidates.to_vec();
    };
    if is_token_terminal(elem.ty) {
        return candidates
            .iter()
            .copied()
            .filter(|candidate| {
                candidate.partial_utf8.n_remain != 0
                    || !match_token(grammar, top, candidate.token_id).0
            })
            .collect();
    }
    if !matches!(
        elem.ty,
        GretType::Char | GretType::CharNot | GretType::CharAny
    ) {
        // `advance_stack` guarantees terminal tops.  A corrupt runtime must
        // fail closed rather than leaving candidates unmasked.
        return candidates.to_vec();
    }

    let mut rejects = Vec::new();
    let mut next_candidates = Vec::new();
    rejects.reserve(candidates.len());
    next_candidates.reserve(candidates.len());

    for candidate in candidates.iter().copied() {
        if candidate.cursor >= candidate.end {
            // Preserve hf2q's existing token-table contract exactly: a
            // syntactically valid but incomplete UTF-8 tail remains alive
            // while the grammar stack is non-empty, and is resolved after the
            // next sampled token. hf2q's current table is built from decoded
            // Rust `String`s and cannot
            // authoritatively classify byte-fallback fragments.  The clone
            // oracle exercises this distinction.
            continue;
        }

        let Some(&chr) = code_points.get(candidate.cursor) else {
            rejects.push(candidate);
            continue;
        };
        if match_char(grammar, top, chr).0 {
            next_candidates.push(GrammarCandidate {
                cursor: candidate.cursor + 1,
                ..candidate
            });
        } else {
            rejects.push(candidate);
        }
    }

    if next_candidates.is_empty() {
        return rejects;
    }

    // The position following a char range is independent of the character
    // value.
    let after = match_char(grammar, top, 0).1;
    let mut stack_after = stack[..stack.len() - 1].to_vec();
    if let Some(next) = at(grammar, after) {
        if !is_end_of_sequence(next) {
            stack_after.push(after);
        }
    }
    let mut next_stacks = Vec::new();
    if !advance_stack(grammar, stack_after, &mut next_stacks) {
        rejects.extend(next_candidates);
        return rejects;
    }

    let mut deeper_rejects =
        reject_candidates(grammar, &next_stacks, &next_candidates, code_points);
    for candidate in &mut deeper_rejects {
        candidate.cursor = candidate.cursor.saturating_sub(1);
    }
    rejects.extend(deeper_rejects);
    rejects
}

// ---------------------------------------------------------------------------
// Grammar runtime state
// ---------------------------------------------------------------------------

/// Runtime grammar state — wraps the parsed grammar with the current stack
/// set and partial-UTF-8 accumulator. Cheap to clone (the inner grammar is
/// shared via `Arc` by callers; stacks copy explicitly).
///
/// # Trigger gate (Wave 2.6 W-α5 Q2)
///
/// The optional `awaiting_trigger` flag implements the **lazy grammar /
/// trigger-activated FSM** pattern:
///
/// * `apply` (mask) — `mask_invalid_tokens` short-circuits to 0 masked
///   when `is_awaiting_trigger()` is true.  All preamble tokens stay
///   live; the model can emit any text up to the open marker.
/// * `accept` (advance) — `accept_bytes` is a no-op returning `true`
///   (alive) while awaiting trigger.  No stacks advance, no UTF-8
///   accumulator state changes.
/// * `is_dead`     — returns `false` while awaiting trigger.  A
///   suspended runtime never dies.
/// * `is_accepted` — returns `false` while awaiting trigger.  A
///   suspended runtime never reaches the accepting state.
///
/// All three short-circuits gate on the SAME boolean — no split-state
/// window where mask says "off" but advance says "on".  This is the
/// architectural property the wave-2.5 audit caught when the gate lived
/// in a separate `Arc<AtomicBool>` outside the runtime
/// (cfa-20260427-adr005-wave2.5/codex-review-last.txt divergence A1,
/// citing `engine.rs:1401, 1489, 1554, 2041, 2145, 2195`).
///
/// The flag is set EXPLICITLY by the caller via
/// [`GrammarRuntime::set_awaiting_trigger`] at construction time, and
/// is flipped to false by [`GrammarRuntime::trigger`] when the engine's
/// `ToolCallSplitter` sees the per-model open marker (e.g. Gemma 4
/// `call:`, Qwen 3.5 `<function=`).  The peer does NOT reset the flag
/// per call — multi-tool support comes from the chat-template-rendered
/// grammar accepting `(call)+` directly.
///
/// Default for new runtimes is `awaiting_trigger == false` so existing
/// callers that don't opt in get the eager-enforcement behavior
/// unchanged (the wave-2.4 baseline).
#[derive(Debug, Clone)]
pub struct GrammarRuntime {
    /// Immutable parsed grammar shared by all speculative candidate probes.
    /// Runtime clones copy only this `Arc` plus their small mutable stack set.
    pub grammar: Arc<Grammar>,
    pub stacks: Stacks,
    pub partial_utf8: PartialUtf8,
    /// Trigger gate.  When `true`, `accept_bytes`/`is_dead`/`is_accepted`
    /// all short-circuit so the runtime is functionally suspended.  Flipped
    /// false either explicitly by [`GrammarRuntime::trigger`] (e.g. when
    /// the engine's tool-call splitter sees the open marker) or implicitly
    /// at construction (the default for `GrammarKind::ResponseFormat`
    /// runtimes).
    awaiting_trigger: bool,
    /// Optional byte marker for a lazy tool grammar.  When configured,
    /// `accept_bytes` watches the unconstrained preamble stream for this
    /// marker and advances the grammar with any body bytes carried by the
    /// SAME token.  That last detail matters for tokenizers which merge an
    /// open marker and the first body prefix into one token.
    lazy_trigger: Option<Vec<u8>>,
    /// At most `lazy_trigger.len() - 1` trailing bytes retained so a marker
    /// split across adjacent tokens can still be recognized.
    lazy_trigger_tail: Vec<u8>,
    /// Public peer-compatible trigger machinery. This is deliberately
    /// separate from `lazy_trigger`: the internal tool marker strips its
    /// marker before applying a body grammar, whereas the peer replays the
    /// matched marker (or first non-empty capture) through the public grammar.
    public_lazy: Option<PublicLazyRuntime>,
}

impl GrammarRuntime {
    /// Initialize runtime from a parsed grammar and a start rule, seeding
    /// `stacks` from the start rule's alternatives.
    pub fn new(grammar: Grammar, start_rule_id: u32) -> Option<Self> {
        let start_rule = grammar.rules.get(start_rule_id as usize)?;
        if start_rule.is_empty() {
            return None;
        }
        let mut stacks: Stacks = Vec::new();
        let mut subpos = Pos::new(start_rule_id, 0);
        loop {
            let mut stack: Stack = Vec::new();
            // If the alternative is non-empty, push its start.
            if let Some(first) = start_rule.get(subpos.elem_idx as usize) {
                if !is_end_of_sequence(first) {
                    stack.push(subpos);
                }
            }
            let mut advanced: Stacks = Vec::new();
            if !advance_stack(&grammar, stack, &mut advanced) {
                return None;
            }
            for s in advanced {
                if !stacks.contains(&s) {
                    stacks.push(s);
                    if stacks.len() > MAX_ACTIVE_STACKS {
                        return None;
                    }
                }
            }
            // Scan to end-of-sequence.
            loop {
                let e = match start_rule.get(subpos.elem_idx as usize) {
                    Some(e) => *e,
                    None => break,
                };
                if is_end_of_sequence(&e) {
                    break;
                }
                subpos.elem_idx += 1;
            }
            let stop = start_rule.get(subpos.elem_idx as usize).map(|e| e.ty);
            if stop == Some(GretType::Alt) {
                subpos.elem_idx += 1;
            } else {
                break;
            }
        }
        Some(Self {
            grammar: Arc::new(grammar),
            stacks,
            partial_utf8: PartialUtf8::default(),
            awaiting_trigger: false,
            lazy_trigger: None,
            lazy_trigger_tail: Vec::new(),
            public_lazy: None,
        })
    }

    // -----------------------------------------------------------------
    // Wave 2.6 W-α5 Q2 — trigger gate (lazy-grammar pattern)
    // -----------------------------------------------------------------

    /// Read the trigger gate.
    ///
    /// When `true`, the runtime is functionally suspended: `accept_bytes`
    /// is a no-op, `is_dead`/`is_accepted` both return `false`, and
    /// `mask::mask_invalid_tokens` short-circuits to 0 masked tokens.
    pub fn is_awaiting_trigger(&self) -> bool {
        self.awaiting_trigger
    }

    /// Explicitly set the trigger gate.  Engine callers wire this to
    /// `true` for `GrammarKind::ToolCallBodyAuto` runtimes at construction;
    /// `GrammarKind::ResponseFormat` and `GrammarKind::ToolCallBodyRequired`
    /// runtimes leave the default (`false`) so enforcement is eager.
    pub fn set_awaiting_trigger(&mut self, value: bool) {
        self.awaiting_trigger = value;
        if !value {
            self.lazy_trigger_tail.clear();
        }
    }

    /// Suspend the grammar until `marker` appears in accepted token bytes.
    ///
    /// Unlike the legacy splitter-only trigger, this keeps grammar state
    /// synchronized when one token decodes to `marker + body-prefix`, and
    /// when the marker spans token boundaries.  The output splitter remains
    /// responsible for routing SSE fields; this method owns only grammar
    /// state.
    pub fn set_lazy_trigger(&mut self, marker: &[u8]) {
        self.awaiting_trigger = true;
        self.lazy_trigger = (!marker.is_empty()).then(|| marker.to_vec());
        self.lazy_trigger_tail.clear();
        self.public_lazy = None;
    }

    /// Suspend this runtime until one of the peer's public token or regex
    /// triggers fires. Regexes are compiled once at runtime construction; an
    /// unsupported expression is an error rather than an ignored trigger.
    pub fn configure_public_lazy(
        &mut self,
        config: &LazyGrammarConfig,
    ) -> Result<(), regex::Error> {
        let trigger_patterns = config
            .trigger_patterns
            .iter()
            .map(|pattern| Regex::new(pattern))
            .collect::<Result<Vec<_>, _>>()?;
        self.awaiting_trigger = true;
        self.lazy_trigger = None;
        self.lazy_trigger_tail.clear();
        self.public_lazy = Some(PublicLazyRuntime {
            token_triggers: config.token_triggers.clone(),
            trigger_patterns,
            buffer: Vec::new(),
            positions: Vec::new(),
        });
        Ok(())
    }

    /// Flip the trigger gate to `false`.  Called by the engine when the
    /// `ToolCallSplitter` reports a `ToolCallOpen` event.  After this,
    /// every subsequent `accept_bytes` / mask call enforces the grammar
    /// normally.
    ///
    /// The peer does NOT reset this flag back to `true` on the close
    /// marker — the bounded grammar SHAPE reaches an accepted state after the
    /// close (`body close space` for hf2q's
    /// `OneOrMoreCallsBodyOnly { parallel: false }` emission). Multi-tool
    /// support
    /// comes from the grammar shape accepting `(call)+` directly when
    /// the operator opts in via `parallel_tool_calls=true`.
    ///
    /// **iter-218 default-flip note.** Pre-iter-218 the
    /// `parallel_tool_calls.unwrap_or(true)` default at handlers.rs
    /// caused single-tool requests to compile to a `body close
    /// gemma4-call* space` shape (unbounded recursion). With the
    /// `awaiting_trigger=false` post-open / no-reset-on-close lifecycle,
    /// the model could emit another `<|tool_call>` open and re-enter the
    /// recursion indefinitely, masking the training-signal `<turn|>`
    /// terminator (id 106) until max_tokens
    /// (`openwebui_tools_streaming_scenario_2` regression). iter-218
    /// flips the default to `false` (matches the peer's "disabled by
    /// default") so the typical request gets the bounded `body close
    /// space` shape that accepts naturally after the first close. DeepSeek's
    /// single-call paths stop at that accepted boundary without evaluating an
    /// unused next-token forward; engines that continue rely on the existing
    /// grammar-driven exhaustion check.
    pub fn trigger(&mut self) {
        self.awaiting_trigger = false;
        self.lazy_trigger_tail.clear();
        if let Some(lazy) = self.public_lazy.as_mut() {
            lazy.buffer.clear();
            lazy.positions.clear();
        }
    }

    fn reject_lazy_buffer_overflow(&mut self) -> bool {
        self.awaiting_trigger = false;
        self.stacks.clear();
        self.partial_utf8 = PartialUtf8::default();
        if let Some(lazy) = self.public_lazy.as_mut() {
            lazy.buffer.clear();
            lazy.positions.clear();
        }
        false
    }

    /// Return `Some(result)` while the public lazy gate owns this token, or
    /// `None` when normal/legacy processing should continue.
    fn accept_public_lazy_token(&mut self, token_id: u32, bytes: &[u8]) -> Option<bool> {
        if !self.awaiting_trigger || self.public_lazy.is_none() {
            return None;
        }

        if self
            .public_lazy
            .as_ref()
            .is_some_and(|lazy| lazy.token_triggers.contains(&token_id))
        {
            self.trigger();
            return Some(self.accept_token(token_id, bytes));
        }

        let new_len = self
            .public_lazy
            .as_ref()
            .expect("checked above")
            .buffer
            .len()
            .checked_add(bytes.len());
        if new_len.is_none_or(|len| len > MAX_LAZY_TRIGGER_BUFFER_BYTES) {
            return Some(self.reject_lazy_buffer_overflow());
        }

        let replay = {
            let lazy = self.public_lazy.as_mut().expect("checked above");
            let start = lazy.buffer.len();
            lazy.buffer.extend_from_slice(bytes);
            lazy.positions.push(LazyBufferedToken {
                token_id,
                start,
                end: lazy.buffer.len(),
            });

            let trigger_start = lazy.trigger_patterns.iter().find_map(|pattern| {
                let captures = pattern.captures(&lazy.buffer)?;
                (1..captures.len())
                    .find_map(|index| {
                        captures
                            .get(index)
                            .filter(|capture| !capture.is_empty())
                            .map(|capture| capture.start())
                    })
                    .or_else(|| captures.get(0).map(|capture| capture.start()))
            });
            trigger_start.map(|trigger_start| {
                lazy.positions
                    .iter()
                    .filter(|position| position.end > trigger_start)
                    .map(|position| {
                        let piece_start = position.start.max(trigger_start);
                        (
                            position.token_id,
                            lazy.buffer[piece_start..position.end].to_vec(),
                        )
                    })
                    .collect::<Vec<_>>()
            })
        };

        let Some(replay) = replay else {
            return Some(true);
        };
        self.trigger();
        for (replay_token, replay_bytes) in replay {
            if !self.accept_token(replay_token, &replay_bytes) {
                return Some(false);
            }
        }
        Some(true)
    }

    /// Byte-only counterpart used by direct runtime callers. Production
    /// sampling always uses `accept_token`, retaining token identity for token
    /// terminals. A regex match replays the constrained byte suffix exactly
    /// once, which is sufficient for character-terminal grammars.
    fn accept_public_lazy_bytes(&mut self, bytes: &[u8]) -> Option<bool> {
        if !self.awaiting_trigger || self.public_lazy.is_none() {
            return None;
        }
        let new_len = self
            .public_lazy
            .as_ref()
            .expect("checked above")
            .buffer
            .len()
            .checked_add(bytes.len());
        if new_len.is_none_or(|len| len > MAX_LAZY_TRIGGER_BUFFER_BYTES) {
            return Some(self.reject_lazy_buffer_overflow());
        }
        let suffix = {
            let lazy = self.public_lazy.as_mut().expect("checked above");
            lazy.buffer.extend_from_slice(bytes);
            lazy.trigger_patterns.iter().find_map(|pattern| {
                let captures = pattern.captures(&lazy.buffer)?;
                let start = (1..captures.len())
                    .find_map(|index| {
                        captures
                            .get(index)
                            .filter(|capture| !capture.is_empty())
                            .map(|capture| capture.start())
                    })
                    .or_else(|| captures.get(0).map(|capture| capture.start()))?;
                Some(lazy.buffer[start..].to_vec())
            })
        };
        let Some(suffix) = suffix else {
            return Some(true);
        };
        self.trigger();
        Some(self.accept_bytes(&suffix))
    }

    /// Feed one Unicode code point. Returns `true` if any stacks remain
    /// after the feed (i.e. the grammar still has a valid continuation).
    pub fn accept_char(&mut self, chr: u32) -> bool {
        self.stacks = accept_char(&self.grammar, &self.stacks, chr);
        !self.stacks.is_empty()
    }

    /// Feed one sampled tokenizer token. Token terminals compare `token_id`
    /// and consume the whole token atomically; character terminals consume
    /// the decoded `bytes`. This preserves both domains when alternatives
    /// mix token and character rules.
    pub fn accept_token(&mut self, token_id: u32, bytes: &[u8]) -> bool {
        if let Some(result) = self.accept_public_lazy_token(token_id, bytes) {
            return result;
        }
        if self.awaiting_trigger {
            let Some(marker) = self.lazy_trigger.as_deref() else {
                return true;
            };

            let mut scan = std::mem::take(&mut self.lazy_trigger_tail);
            scan.extend_from_slice(bytes);
            if let Some(marker_start) = scan.windows(marker.len()).position(|w| w == marker) {
                let body_start = marker_start + marker.len();
                let body_suffix = scan[body_start..].to_vec();
                self.trigger();
                return self.accept_token(token_id, &body_suffix);
            }

            let keep = marker.len().saturating_sub(1).min(scan.len());
            self.lazy_trigger_tail
                .extend_from_slice(&scan[scan.len().saturating_sub(keep)..]);
            return true;
        }

        let mut code_points = Vec::new();
        let Some(partial_utf8) = decode_candidate_utf8(bytes, self.partial_utf8, &mut code_points)
        else {
            self.partial_utf8 = PartialUtf8 {
                value: 0,
                n_remain: -1,
            };
            self.stacks.clear();
            return false;
        };

        let mut stacks_new = Vec::with_capacity(self.stacks.len());
        for stack in &self.stacks {
            let Some(top) = stack.last().copied() else {
                continue;
            };
            let Some(element) = at(&self.grammar, top).copied() else {
                continue;
            };
            if is_token_terminal(element.ty) {
                let (matched, after) = match_token(&self.grammar, top, token_id);
                if matched {
                    let mut stack_after = stack[..stack.len() - 1].to_vec();
                    if at(&self.grammar, after).is_some_and(|next| !is_end_of_sequence(next)) {
                        stack_after.push(after);
                    }
                    if !advance_stack(&self.grammar, stack_after, &mut stacks_new) {
                        self.stacks.clear();
                        return false;
                    }
                }
                continue;
            }

            let mut current_stacks = vec![stack.clone()];
            for &chr in &code_points {
                current_stacks = accept_char(&self.grammar, &current_stacks, chr);
                if current_stacks.is_empty() {
                    break;
                }
            }
            for surviving in current_stacks {
                if !stacks_new.contains(&surviving) {
                    stacks_new.push(surviving);
                    if stacks_new.len() > MAX_ACTIVE_STACKS {
                        self.stacks.clear();
                        return false;
                    }
                }
            }
        }
        self.stacks = stacks_new;
        self.partial_utf8 = partial_utf8;
        !self.stacks.is_empty()
    }

    /// Accept an end-of-generation token only after the grammar is already
    /// complete. EOG never consumes a grammar token terminal. An unexpected
    /// EOG kills the runtime so callers that violate masking fail closed.
    pub fn accept_eog(&mut self) -> bool {
        if self.awaiting_trigger {
            return true;
        }
        if self.is_terminally_accepted() {
            return true;
        }
        self.stacks.clear();
        false
    }

    /// Feed a byte string (e.g. a decoded token text). Partial UTF-8 bytes
    /// at the tail are carried in `self.partial_utf8`. Returns `true` if the
    /// grammar still has a valid continuation after consuming all the bytes.
    ///
    /// Wave 2.6 W-α5 Q2: when [`is_awaiting_trigger`] is `true`, this is
    /// a no-op returning `true` (alive).  No stacks advance, no UTF-8
    /// accumulator state changes.  The runtime is suspended until the
    /// engine calls [`trigger`] (typically in the `ToolCallOpen`
    /// handler).
    pub fn accept_bytes(&mut self, bytes: &[u8]) -> bool {
        if let Some(result) = self.accept_public_lazy_bytes(bytes) {
            return result;
        }
        if self.awaiting_trigger {
            let Some(marker) = self.lazy_trigger.as_deref() else {
                // Legacy explicit-trigger mode: no advance while suspended.
                return true;
            };

            let mut scan = std::mem::take(&mut self.lazy_trigger_tail);
            scan.extend_from_slice(bytes);
            if let Some(marker_start) = scan.windows(marker.len()).position(|w| w == marker) {
                let body_start = marker_start + marker.len();
                let body_suffix = scan[body_start..].to_vec();
                self.trigger();
                return self.accept_bytes(&body_suffix);
            }

            let keep = marker.len().saturating_sub(1).min(scan.len());
            self.lazy_trigger_tail
                .extend_from_slice(&scan[scan.len().saturating_sub(keep)..]);
            return true;
        }
        let mut i = 0;

        // If there's an unfinished UTF-8 code point from the previous call,
        // try to complete it first. Only runs when `partial.n_remain > 0`.
        if self.partial_utf8.n_remain > 0 {
            let mut partial = self.partial_utf8;
            while i < bytes.len() && partial.n_remain > 0 {
                let b = bytes[i];
                if (b & 0xC0) != 0x80 {
                    self.partial_utf8 = PartialUtf8 {
                        value: 0,
                        n_remain: -1,
                    };
                    self.stacks.clear();
                    return false;
                }
                partial.value = (partial.value << 6) | (b & 0x3F) as u32;
                partial.n_remain -= 1;
                i += 1;
            }
            if partial.n_remain > 0 {
                // Still incomplete at end-of-buffer — stash for next call.
                self.partial_utf8 = partial;
                return !self.stacks.is_empty();
            }
            // Completed code point.
            self.partial_utf8 = PartialUtf8::default();
            if !self.accept_char(partial.value) {
                return false;
            }
        }

        // Now consume full code points from `bytes[i..]`.
        while i < bytes.len() {
            let first = bytes[i];
            let (needed, mut val) = if first & 0x80 == 0 {
                (0usize, first as u32)
            } else if first & 0xE0 == 0xC0 {
                (1, (first & 0x1F) as u32)
            } else if first & 0xF0 == 0xE0 {
                (2, (first & 0x0F) as u32)
            } else if first & 0xF8 == 0xF0 {
                (3, (first & 0x07) as u32)
            } else {
                self.stacks.clear();
                return false;
            };
            i += 1;
            let mut remain = needed as i8;
            while remain > 0 && i < bytes.len() {
                let b = bytes[i];
                if (b & 0xC0) != 0x80 {
                    self.stacks.clear();
                    return false;
                }
                val = (val << 6) | (b & 0x3F) as u32;
                i += 1;
                remain -= 1;
            }
            if remain > 0 {
                self.partial_utf8 = PartialUtf8 {
                    value: val,
                    n_remain: remain,
                };
                return !self.stacks.is_empty();
            }
            if !self.accept_char(val) {
                return false;
            }
        }
        self.partial_utf8 = PartialUtf8::default();
        !self.stacks.is_empty()
    }

    /// Returns `true` if the grammar is in an accepting state — i.e. any
    /// stack is empty (meaning the root rule has been fully matched).
    ///
    /// Wave 2.6 W-α5 Q2: a suspended runtime
    /// (`is_awaiting_trigger() == true`) is NEVER in an accepting state.
    /// Returning `false` here lets the engine call this method
    /// unconditionally on every step (no separate gate around the call
    /// site needed) — the trigger gate IS the gate.
    pub fn is_accepted(&self) -> bool {
        if self.awaiting_trigger {
            return false;
        }
        self.stacks.iter().any(|s| s.is_empty())
    }

    /// Return whether generation may terminate successfully at this exact
    /// byte boundary. Structural acceptance alone is insufficient while a
    /// decoded token has left an incomplete UTF-8 sequence pending.
    pub fn is_terminally_accepted(&self) -> bool {
        self.is_accepted() && self.partial_utf8.n_remain == 0
    }

    /// Is the grammar dead? (no stacks remain; no continuation can satisfy it).
    ///
    /// Wave 2.6 W-α5 Q2: a suspended runtime
    /// (`is_awaiting_trigger() == true`) is NEVER dead.  Returning
    /// `false` here lets the engine call this method unconditionally on
    /// every step — the wave-2.5 audit divergence at engine.rs:1554 +
    /// :2195 ("dead-check global") is no longer a divergence because
    /// the runtime self-gates instead of relying on a sibling
    /// `Arc<AtomicBool>`.
    pub fn is_dead(&self) -> bool {
        if self.awaiting_trigger {
            return false;
        }
        self.stacks.is_empty()
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

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

    fn runtime_from(src: &str, start: &str) -> GrammarRuntime {
        let g = parse(src).expect("parse");
        let rid = g.rule_id(start).expect("start rule exists");
        GrammarRuntime::new(g, rid).expect("start rule nonempty")
    }

    #[test]
    fn accept_exact_literal_sequence() {
        let mut rt = runtime_from("root ::= \"abc\"\n", "root");
        assert!(!rt.is_dead());
        assert!(rt.accept_char('a' as u32));
        assert!(rt.accept_char('b' as u32));
        assert!(rt.accept_char('c' as u32));
        assert!(rt.is_accepted(), "grammar should be in accepting state");
    }

    #[test]
    fn reject_wrong_literal() {
        let mut rt = runtime_from("root ::= \"abc\"\n", "root");
        assert!(!rt.accept_char('X' as u32));
        assert!(rt.is_dead());
    }

    #[test]
    fn char_class_range_accepts_in_range() {
        let mut rt = runtime_from("root ::= [a-z]\n", "root");
        assert!(rt.accept_char('m' as u32));
        assert!(rt.is_accepted());
    }

    #[test]
    fn char_class_range_rejects_out_of_range() {
        let mut rt = runtime_from("root ::= [a-z]\n", "root");
        assert!(!rt.accept_char('A' as u32));
        assert!(rt.is_dead());
    }

    #[test]
    fn negated_char_class() {
        let mut rt = runtime_from("root ::= [^abc]\n", "root");
        assert!(rt.accept_char('z' as u32));
        assert!(rt.is_accepted());

        let mut rt2 = runtime_from("root ::= [^abc]\n", "root");
        assert!(!rt2.accept_char('a' as u32));
    }

    #[test]
    fn token_terminal_consumes_id_and_ignores_piece_text() {
        let mut runtime = runtime_from("root ::= <[10]> <[11]>\n", "root");
        assert!(runtime.accept_token(10, b"unrelated decoded text"));
        assert!(!runtime.is_accepted());
        assert!(runtime.accept_token(11, b"more unrelated text"));
        assert!(runtime.is_accepted());
    }

    #[test]
    fn token_not_terminal_rejects_only_the_named_id() {
        let mut allowed = runtime_from("root ::= !<[11]>\n", "root");
        assert!(allowed.accept_token(12, b"same-piece"));
        assert!(allowed.is_accepted());

        let mut denied = runtime_from("root ::= !<[11]>\n", "root");
        assert!(!denied.accept_token(11, b"same-piece"));
        assert!(denied.is_dead());
    }

    #[test]
    fn peer_simple_token_grammar_sequence_matches() {
        let grammar = "root ::= <[10]> content <[11]>\ncontent ::= (!<[11]>)*\n";
        let mut runtime = runtime_from(grammar, "root");

        assert!(runtime.accept_token(10, b"<[10]>"));
        assert!(runtime.accept_token(12, b"hello world"));
        assert!(runtime.accept_token(13, b" mixed in"));
        assert!(runtime.accept_token(11, b"<[11]>"));
        assert!(runtime.is_accepted());

        let mut missing_end = runtime_from(grammar, "root");
        assert!(missing_end.accept_token(10, b"<[10]>"));
        assert!(missing_end.accept_token(12, b"missing end token"));
        assert!(!missing_end.is_accepted());
    }

    #[test]
    fn mixed_token_and_character_alternatives_use_the_correct_domain() {
        let grammar = "root ::= <[7]> | \"x\"\n";

        let mut token_branch = runtime_from(grammar, "root");
        assert!(token_branch.accept_token(7, b"not-x"));
        assert!(token_branch.is_accepted());

        let mut character_branch = runtime_from(grammar, "root");
        assert!(character_branch.accept_token(99, b"x"));
        assert!(character_branch.is_accepted());

        let mut bytes_only = runtime_from(grammar, "root");
        assert!(!bytes_only.accept_bytes(b"not-x"));
    }

    #[test]
    fn token_any_and_exclusion_sets_support_quantifiers_without_vocab_expansion() {
        let grammar = "root ::= <[*]>{2} !<[1,2,3]>+\n";
        let mut runtime = runtime_from(grammar, "root");
        assert!(runtime.accept_token(1, b"first"));
        assert!(runtime.accept_token(2, b"second"));
        assert!(runtime.accept_token(4, b"fourth"));
        assert!(runtime.accept_token(5, b"fifth"));
        assert!(runtime.is_terminally_accepted());

        for excluded in [1, 2, 3] {
            let mut rejected = runtime_from(grammar, "root");
            assert!(rejected.accept_token(8, b"first"));
            assert!(rejected.accept_token(9, b"second"));
            assert!(!rejected.accept_token(excluded, b"excluded"));
            assert!(rejected.is_dead());
        }
    }

    #[test]
    fn token_exclusion_set_and_character_alternative_use_separate_domains() {
        let grammar = "root ::= !<[1,2]> | \"x\"\n";

        let mut token_branch = runtime_from(grammar, "root");
        assert!(token_branch.accept_token(3, b"not-x"));
        assert!(token_branch.is_terminally_accepted());

        let mut character_branch = runtime_from(grammar, "root");
        assert!(character_branch.accept_token(1, b"x"));
        assert!(character_branch.is_terminally_accepted());

        let mut rejected = runtime_from(grammar, "root");
        assert!(!rejected.accept_token(2, b"not-x"));
    }

    #[test]
    fn terminal_acceptance_requires_a_complete_utf8_tail() {
        let mut runtime = runtime_from("root ::= \"\" | .\n", "root");
        assert!(runtime.is_terminally_accepted());

        assert!(runtime.accept_bytes(&[0xCE]));
        assert!(
            runtime.is_accepted(),
            "empty alternate remains structurally accepted"
        );
        assert!(
            !runtime.is_terminally_accepted(),
            "partial UTF-8 is not terminal"
        );
        let mut premature_eog = runtime.clone();
        assert!(!premature_eog.accept_eog());
        assert!(premature_eog.is_dead());

        assert!(runtime.accept_bytes(&[0xB1]));
        assert!(runtime.is_terminally_accepted());
    }

    #[test]
    fn eog_cannot_force_a_token_terminal() {
        let mut runtime = runtime_from("root ::= <[2]>\n", "root");
        assert!(!runtime.accept_eog());
        assert!(runtime.is_dead());

        let mut accepted = runtime_from("root ::= \"x\"\n", "root");
        assert!(accepted.accept_token(5, b"x"));
        assert!(accepted.accept_eog());
        assert!(accepted.is_accepted());
    }

    #[test]
    fn any_char_dot_accepts_anything() {
        let mut rt = runtime_from("root ::= .\n", "root");
        assert!(rt.accept_char('Q' as u32));
        assert!(rt.is_accepted());
    }

    #[test]
    fn alternation_either_path_accepted() {
        let mut rt = runtime_from("root ::= \"yes\" | \"no\"\n", "root");
        assert!(rt.accept_char('n' as u32));
        assert!(rt.accept_char('o' as u32));
        assert!(rt.is_accepted());
    }

    #[test]
    fn alternation_wrong_prefix_rejected() {
        let mut rt = runtime_from("root ::= \"yes\" | \"no\"\n", "root");
        assert!(!rt.accept_char('q' as u32));
    }

    #[test]
    fn rule_reference_chain() {
        let mut rt = runtime_from("root ::= ws \"hi\"\nws ::= \" \"\n", "root");
        assert!(rt.accept_char(' ' as u32));
        assert!(rt.accept_char('h' as u32));
        assert!(rt.accept_char('i' as u32));
        assert!(rt.is_accepted());
    }

    #[test]
    fn kleene_star_zero_occurrences() {
        let rt = runtime_from("root ::= \"a\"*\n", "root");
        // zero occurrences — already accepted.
        assert!(rt.is_accepted());
    }

    #[test]
    fn kleene_star_many_occurrences() {
        let mut rt = runtime_from("root ::= \"a\"*\n", "root");
        for _ in 0..10 {
            assert!(rt.accept_char('a' as u32));
        }
        assert!(rt.is_accepted());
    }

    #[test]
    fn plus_requires_at_least_one() {
        let rt_zero = runtime_from("root ::= \"a\"+\n", "root");
        // Before accepting any char, should not yet be accepted.
        assert!(!rt_zero.is_accepted());

        let mut rt = runtime_from("root ::= \"a\"+\n", "root");
        assert!(rt.accept_char('a' as u32));
        assert!(rt.is_accepted());
        assert!(rt.accept_char('a' as u32));
        assert!(rt.is_accepted());
    }

    #[test]
    fn optional_question_mark_both_paths() {
        let rt_empty = runtime_from("root ::= \"x\"?\n", "root");
        assert!(rt_empty.is_accepted());

        let mut rt_one = runtime_from("root ::= \"x\"?\n", "root");
        assert!(rt_one.accept_char('x' as u32));
        assert!(rt_one.is_accepted());

        let mut rt_two = runtime_from("root ::= \"x\"?\n", "root");
        rt_two.accept_char('x' as u32);
        assert!(!rt_two.accept_char('x' as u32));
    }

    #[test]
    fn brace_exact_count_rejects_over() {
        let mut rt = runtime_from("root ::= \"a\"{3}\n", "root");
        assert!(rt.accept_char('a' as u32));
        assert!(!rt.is_accepted());
        assert!(rt.accept_char('a' as u32));
        assert!(!rt.is_accepted());
        assert!(rt.accept_char('a' as u32));
        assert!(rt.is_accepted());
        assert!(!rt.accept_char('a' as u32));
    }

    #[test]
    fn brace_range_accepts_within() {
        for count in 0..=3 {
            let mut rt = runtime_from("root ::= \"a\"{0,3}\n", "root");
            for _ in 0..count {
                assert!(rt.accept_char('a' as u32), "count={}", count);
            }
            assert!(rt.is_accepted(), "count={}", count);
        }
        // 4 'a's — extra char should be rejected.
        let mut rt = runtime_from("root ::= \"a\"{0,3}\n", "root");
        for _ in 0..3 {
            rt.accept_char('a' as u32);
        }
        assert!(!rt.accept_char('a' as u32));
    }

    #[test]
    fn accept_bytes_utf8() {
        let mut rt = runtime_from("root ::= \"α\"\n", "root");
        // Greek alpha UTF-8 is CE B1.
        assert!(rt.accept_bytes("α".as_bytes()));
        assert!(rt.is_accepted());
    }

    #[test]
    fn accept_bytes_incremental_utf8() {
        let mut rt = runtime_from("root ::= \"α\"\n", "root");
        // Feed the first byte — should accumulate as partial.
        assert!(rt.accept_bytes(&[0xCE]));
        assert!(!rt.is_accepted(), "not yet accepted after 1 byte");
        // Feed the rest.
        assert!(rt.accept_bytes(&[0xB1]));
        assert!(rt.is_accepted());
    }

    #[test]
    fn json_grammar_value_rule_accepts_scalars_and_arrays() {
        // The peer's `json.gbnf` has `root ::= object` (root accepts ONLY
        // a top-level object), but `value ::= object | array | string |
        // number | ("true" | "false" | "null") ws` accepts everything.
        // Verify each alternative against the `value` rule.
        let src = super::super::test_fixtures::peer_grammar("json.gbnf");
        for input in [
            "null",
            "true",
            "false",
            "123",
            "-4.2",
            "\"hello\"",
            "[]",
            "[1,2,3]",
            "{}",
            "{\"k\":\"v\"}",
            "{\"a\":1,\"b\":[true,false]}",
        ] {
            let g = parse(src).expect("parse");
            let rid = g.rule_id("value").unwrap();
            let mut rt = GrammarRuntime::new(g, rid).unwrap();
            assert!(
                rt.accept_bytes(input.as_bytes()),
                "json grammar (value rule) should accept {:?}",
                input
            );
            assert!(
                rt.is_accepted(),
                "json grammar (value rule) should ACCEPT {:?}",
                input
            );
        }
    }

    #[test]
    fn json_grammar_root_rule_requires_object() {
        // `root ::= object` — bare scalars rejected, objects accepted.
        let src = super::super::test_fixtures::peer_grammar("json.gbnf");
        for good_object in ["{}", "{\"k\":\"v\"}", "{\"a\":1,\"b\":[true,false]}"] {
            let g = parse(src).expect("parse");
            let rid = g.rule_id("root").unwrap();
            let mut rt = GrammarRuntime::new(g, rid).unwrap();
            assert!(rt.accept_bytes(good_object.as_bytes()));
            assert!(rt.is_accepted(), "root must accept {:?}", good_object);
        }
        for bad_scalar in ["null", "42", "\"hello\""] {
            let g = parse(src).expect("parse");
            let rid = g.rule_id("root").unwrap();
            let mut rt = GrammarRuntime::new(g, rid).unwrap();
            let ok = rt.accept_bytes(bad_scalar.as_bytes());
            assert!(
                !(ok && rt.is_accepted()),
                "root MUST reject bare scalar {:?}",
                bad_scalar
            );
        }
    }

    #[test]
    fn json_grammar_rejects_malformed() {
        let src = super::super::test_fixtures::peer_grammar("json.gbnf");
        for input in [
            "nul",      // truncated
            "tru e",    // space in literal
            "[1,",      // truncated array
            "{\"k\":}", // missing value
            "\"unterminated",
        ] {
            let g = parse(src).expect("parse");
            let rid = g.rule_id("root").unwrap();
            let mut rt = GrammarRuntime::new(g, rid).unwrap();
            let ok = rt.accept_bytes(input.as_bytes());
            // Either bytes were rejected mid-stream OR the grammar isn't in
            // an accepting state at end-of-input.
            let final_accepted = ok && rt.is_accepted();
            assert!(
                !final_accepted,
                "json grammar MUST reject {:?}, but it accepted",
                input
            );
        }
    }

    #[test]
    fn json_grammar_rejects_trailing_garbage_after_object() {
        // `root ::= object` — after a valid object, only trailing ws is
        // allowed. Alphabetic garbage is rejected.
        let src = super::super::test_fixtures::peer_grammar("json.gbnf");
        let g = parse(src).expect("parse");
        let rid = g.rule_id("root").unwrap();
        let mut rt = GrammarRuntime::new(g, rid).unwrap();
        assert!(rt.accept_bytes(b"{}"));
        let still_alive = rt.accept_bytes(b"x");
        assert!(
            !still_alive,
            "json root rule must reject 'x' after a complete '{{}}'"
        );
    }

    #[test]
    fn dead_grammar_stays_dead() {
        let mut rt = runtime_from("root ::= \"a\"\n", "root");
        assert!(!rt.accept_char('x' as u32));
        assert!(rt.is_dead());
        assert!(!rt.accept_char('a' as u32));
        assert!(rt.is_dead());
    }

    #[test]
    fn all_vendored_peer_grammars_accept_representative_output() {
        let cases = [
            ("arithmetic.gbnf", "x=1\n"),
            ("c.gbnf", "int main(){return 0;}"),
            ("chess.gbnf", "1. e4 e5\n2. Nf3 Nc6\n"),
            ("english.gbnf", "Hello world"),
            ("japanese.gbnf", "日本語"),
            ("json.gbnf", "{\"ok\":true}"),
            ("json_arr.gbnf", "[\n]"),
            ("list.gbnf", "- first\n- second\n"),
        ];
        for (name, output) in cases {
            let source = super::super::test_fixtures::peer_grammar(name);
            let grammar = parse(source).unwrap_or_else(|error| panic!("{name}: {error}"));
            let root = grammar.rule_id("root").expect("fixture has root");
            let mut runtime =
                GrammarRuntime::new(grammar, root).unwrap_or_else(|| panic!("{name}: runtime"));
            assert!(
                runtime.accept_bytes(output.as_bytes()),
                "{name} rejected representative output {output:?}"
            );
            assert!(
                runtime.is_accepted(),
                "{name} did not finish in an accepting state for {output:?}"
            );
        }
    }

    #[test]
    fn partial_utf8_initial_state_is_clean() {
        let rt = runtime_from("root ::= \"a\"\n", "root");
        assert_eq!(rt.partial_utf8, PartialUtf8::default());
    }

    // -----------------------------------------------------------------
    // Wave 2.6 W-α5 Q2 — trigger-gate (lazy grammar) contract tests
    // -----------------------------------------------------------------
    //
    // These exercise the runtime self-gate that replaces the wave-2.5
    // `Arc<AtomicBool>` sibling in engine.rs.  Each test is a direct
    // expression of an audit divergence (cf. cfa-20260427-adr005-wave2.5
    // /codex-review-last.txt) — together they prove the new contract
    // makes the divergence structurally impossible.

    /// Audit fix: `accept_bytes` is a no-op while
    /// `is_awaiting_trigger()` is true.  This is the wave-2.5 audit
    /// divergence "advance the grammar runtime unconditionally outside
    /// the gated region" (engine.rs:1401, 1489, 2041, 2145) — moving
    /// the gate INSIDE the runtime makes the unconditional advance
    /// safe.
    #[test]
    fn runtime_accept_noops_when_awaiting_trigger() {
        // Grammar that requires literal "abc"; if accept_bytes were
        // NOT a no-op while suspended, feeding "xyz" would die.
        let mut rt = runtime_from("root ::= \"abc\"\n", "root");
        rt.set_awaiting_trigger(true);
        // Snapshot pre-state for byte-exact equality check.
        let pre_stacks = rt.stacks.clone();
        let pre_partial = rt.partial_utf8;

        // Feed garbage bytes.  Must NOT advance, must NOT clear stacks.
        let alive = rt.accept_bytes(b"xyz");
        assert!(
            alive,
            "suspended runtime must report alive=true (return value semantics)"
        );
        assert_eq!(
            rt.stacks, pre_stacks,
            "suspended runtime stacks MUST NOT change on accept_bytes"
        );
        assert_eq!(
            rt.partial_utf8, pre_partial,
            "suspended runtime partial_utf8 MUST NOT change on accept_bytes"
        );
        assert!(rt.is_awaiting_trigger(), "trigger gate stays armed");

        // Now flip the gate; the original grammar should still be intact.
        rt.trigger();
        assert!(!rt.is_awaiting_trigger());
        assert!(
            rt.accept_bytes(b"abc"),
            "post-trigger grammar accepts literal"
        );
        assert!(rt.is_accepted(), "literal fully matched");
    }

    /// Audit fix: `is_dead()` returns false while suspended.  This
    /// kills the wave-2.5 audit divergence "src/serve/api/engine.rs:1554
    /// and 2195 also terminate on dead grammar regardless of gate" —
    /// the engine can call `is_dead()` unconditionally because the
    /// runtime self-gates.
    #[test]
    fn runtime_is_dead_returns_false_while_awaiting_trigger() {
        let mut rt = runtime_from("root ::= \"abc\"\n", "root");
        rt.set_awaiting_trigger(true);

        // Even if the underlying stacks were artificially cleared, the
        // gate masks death.  Most natural pre-trigger state is the
        // construction default (stacks non-empty), which would also
        // report not-dead.  Force the worst case explicitly:
        rt.stacks.clear();
        assert!(
            !rt.is_dead(),
            "suspended runtime MUST NOT report dead even when stacks empty"
        );
        assert!(
            !rt.is_accepted(),
            "suspended runtime MUST NOT report accepted even when stacks empty"
        );

        // Triggering reveals the underlying state honestly.
        rt.trigger();
        assert!(
            rt.is_dead(),
            "post-trigger runtime with empty stacks IS dead"
        );
    }

    /// Audit fix: `is_accepted()` returns false while suspended.
    /// Symmetric to the dead-check fix; ensures the early-termination
    /// branch in the streaming decode loop (engine.rs:2199-2208) is
    /// safe to call unconditionally.
    #[test]
    fn runtime_is_accepted_returns_false_while_awaiting_trigger() {
        // `"a"*` is in an accepting state immediately (zero
        // occurrences satisfies the kleene star).
        let mut rt = runtime_from("root ::= \"a\"*\n", "root");
        assert!(
            rt.is_accepted(),
            "kleene star is accepted at zero occurrences"
        );

        rt.set_awaiting_trigger(true);
        assert!(
            !rt.is_accepted(),
            "suspended runtime MUST NOT report accepted even when underlying \
             grammar IS in an accepting state"
        );

        rt.trigger();
        assert!(rt.is_accepted(), "post-trigger reveals the actual state");
    }

    /// Default for new runtimes is awaiting_trigger=false (eager
    /// enforcement).  This is the contract that makes
    /// `GrammarKind::ResponseFormat` safe — its runtime never waits.
    /// Without this default, every existing caller of
    /// `GrammarRuntime::new` would silently enter the lazy-grammar
    /// state and break response_format=json_schema enforcement.
    #[test]
    fn runtime_default_is_eager_not_awaiting_trigger() {
        let rt = runtime_from("root ::= \"abc\"\n", "root");
        assert!(
            !rt.is_awaiting_trigger(),
            "default runtime MUST NOT await trigger (eager enforcement is the safe \
             default; ResponseFormat-kind grammars rely on this)"
        );
    }

    /// `set_awaiting_trigger(true)` then `trigger()` is the explicit
    /// path used by the engine for `GrammarKind::ToolCallBodyAuto`
    /// runtimes.  Verifies the round-trip restores normal enforcement.
    #[test]
    fn runtime_set_then_trigger_restores_eager_enforcement() {
        let mut rt = runtime_from("root ::= \"abc\"\n", "root");
        rt.set_awaiting_trigger(true);
        assert!(rt.is_awaiting_trigger());

        // Pre-trigger garbage MUST be ignored.
        let _ = rt.accept_bytes(b"PREAMBLE-junk-blah");
        assert!(rt.is_awaiting_trigger());

        // Trigger.
        rt.trigger();
        assert!(!rt.is_awaiting_trigger());

        // Post-trigger: the grammar is intact; the literal matches.
        assert!(rt.accept_bytes(b"abc"));
        assert!(rt.is_accepted());
    }

    #[test]
    fn lazy_marker_accepts_body_suffix_carried_by_trigger_token() {
        let mut rt = runtime_from("root ::= \"call:read_file\"\n", "root");
        rt.set_lazy_trigger(b"<|tool_call>");

        assert!(rt.accept_bytes(b"preamble<|tool_call>call:read"));
        assert!(!rt.is_awaiting_trigger());
        assert!(rt.accept_bytes(b"_file"));
        assert!(rt.is_accepted());
    }

    #[test]
    fn lazy_marker_matches_across_token_boundaries_without_replaying_prefix() {
        let mut rt = runtime_from("root ::= \"call:f{}\"\n", "root");
        rt.set_lazy_trigger(b"<|tool_call>");

        assert!(rt.accept_bytes(b"plain text <|tool"));
        assert!(rt.is_awaiting_trigger());
        assert!(rt.accept_bytes(b"_call>call:f"));
        assert!(!rt.is_awaiting_trigger());
        assert!(rt.accept_bytes(b"{}"));
        assert!(rt.is_accepted());
    }

    #[test]
    fn lazy_marker_retains_only_a_bounded_partial_match_tail() {
        let mut rt = runtime_from("root ::= \"x\"\n", "root");
        rt.set_lazy_trigger(b"<tool_call>");

        assert!(rt.accept_bytes(&vec![b'a'; 64 * 1024]));
        assert!(rt.is_awaiting_trigger());
        assert!(rt.lazy_trigger_tail.len() < b"<tool_call>".len());
    }

    #[test]
    fn public_lazy_token_trigger_is_inactive_then_replays_whole_token() {
        let mut rt = runtime_from("root ::= <[7]> \"x\"\n", "root");
        rt.configure_public_lazy(&LazyGrammarConfig {
            token_triggers: vec![7],
            ..Default::default()
        })
        .unwrap();

        assert!(rt.accept_token(1, b"unconstrained preamble"));
        assert!(rt.is_awaiting_trigger());
        assert!(rt.accept_eog(), "EOG is unconstrained before activation");
        assert!(rt.accept_token(7, b"<special>"));
        assert!(!rt.is_awaiting_trigger());
        assert!(!rt.is_terminally_accepted());
        assert!(!rt.accept_eog(), "EOG must fail closed after activation");
    }

    #[test]
    fn public_lazy_pattern_replays_split_capture_with_original_token_ids() {
        let mut rt = runtime_from("root ::= \"BODY\"\n", "root");
        rt.configure_public_lazy(&LazyGrammarConfig {
            trigger_patterns: vec!["tool:(BODY)".into()],
            ..Default::default()
        })
        .unwrap();

        assert!(rt.accept_token(11, b"noise tool:BO"));
        assert!(rt.is_awaiting_trigger());
        assert!(rt.accept_token(12, b"DY"));
        assert!(!rt.is_awaiting_trigger());
        assert!(rt.is_terminally_accepted());
    }

    #[test]
    fn public_lazy_pattern_replays_marker_and_body_exactly_once() {
        let mut rt = runtime_from("root ::= \"<tag>BODY\"\n", "root");
        rt.configure_public_lazy(&LazyGrammarConfig {
            trigger_patterns: vec![regex::escape("<tag>")],
            ..Default::default()
        })
        .unwrap();

        assert!(rt.accept_token(5, b"preamble<tag>BODY"));
        assert!(!rt.is_awaiting_trigger());
        assert!(rt.is_terminally_accepted());
    }

    #[test]
    fn public_lazy_full_pattern_requires_the_whole_buffer() {
        let config = LazyGrammarConfig {
            trigger_patterns: vec!["^tool:(BODY)$".into()],
            ..Default::default()
        };
        let mut prefixed = runtime_from("root ::= \"BODY\"\n", "root");
        prefixed.configure_public_lazy(&config).unwrap();
        assert!(prefixed.accept_token(1, b"prefix tool:BODY"));
        assert!(prefixed.is_awaiting_trigger());

        let mut exact = runtime_from("root ::= \"BODY\"\n", "root");
        exact.configure_public_lazy(&config).unwrap();
        assert!(exact.accept_token(2, b"tool:BODY"));
        assert!(exact.is_terminally_accepted());
    }

    #[test]
    fn public_lazy_buffer_limit_fails_closed() {
        let mut rt = runtime_from("root ::= \"x\"\n", "root");
        rt.configure_public_lazy(&LazyGrammarConfig {
            trigger_patterns: vec!["never".into()],
            ..Default::default()
        })
        .unwrap();

        assert!(!rt.accept_token(1, &vec![b'a'; MAX_LAZY_TRIGGER_BUFFER_BYTES + 1]));
        assert!(!rt.is_awaiting_trigger());
        assert!(rt.is_dead());
    }

    /// Multi-tool-call regression guard.  The peer does NOT reset
    /// awaiting_trigger on the close marker — multi-call support comes
    /// from the chat-template-rendered grammar accepting `(call)+`
    /// directly.  This test verifies a `(call)+`-shaped grammar
    /// continues to accept after a complete first call without any
    /// runtime reset.
    ///
    /// See research-report.md Q2 anti-finding: "No production engine
    /// implements parallel-tool-call as a multi-runtime architecture."
    #[test]
    fn multi_tool_call_grammar_continues_across_close_marker() {
        // Two complete calls back-to-back, single grammar.  Models
        // `<call>X</call><call>Y</call>` collapsed to two literals.
        let src = "root ::= call+\ncall ::= \"<call>\" [a-z]+ \"</call>\"\n";
        let mut rt = runtime_from(src, "root");
        // Engine-equivalent: trigger fires once when the splitter sees
        // the first `<call>`; that flip is permanent.
        rt.set_awaiting_trigger(true);
        rt.trigger();

        // First complete call.
        assert!(rt.accept_bytes(b"<call>foo</call>"));
        assert!(
            rt.is_accepted(),
            "after first complete call, kleene + is in an accepting state"
        );

        // Second complete call WITHOUT any reset — proving the runtime
        // carries state through naturally.  This is the canonical
        // Hermes 2 Pro template pattern.
        assert!(
            rt.accept_bytes(b"<call>bar</call>"),
            "(call)+ grammar MUST accept a second complete call without runtime reset"
        );
        assert!(rt.is_accepted(), "still accepting after the second call");
    }

    #[test]
    fn runtime_rejects_more_than_the_active_stack_budget() {
        let mut source = String::from("root ::= ");
        for index in 0..=MAX_ACTIVE_STACKS {
            if index > 0 {
                source.push_str(" | ");
            }
            source.push_str(&format!("\"a{index:05}\""));
        }
        source.push('\n');
        let grammar = crate::serve::api::grammar::parse(&source).expect("bounded grammar parse");
        let root = grammar.rule_id("root").expect("root rule");
        assert!(
            GrammarRuntime::new(grammar, root).is_none(),
            "runtime MUST fail closed when initial alternatives exceed 32,768 active stacks"
        );
    }
}