Skip to main content

dsl_kit_parse/
peg.rs

1//! PEG grammar AST + recursive-descent interpreter (G-2).
2//!
3//! The [`Peg`] enum is the grammar AST. It derives `DslNode` + `DslSchema`
4//! from the kit — grammars therefore get the L1-L4.6 toolchain for free
5//! (walk traversal, schema JSON, lint, `variant_name`, MCP pretty-print)
6//! per `parser-design §2`. Parse *execution* is a small dedicated
7//! recursive-descent interpreter that walks a [`Grammar`] value against
8//! input text and produces a [`ParseTree`] (crate root).
9//!
10//! # Quality bar (parser-design §3.5, non-negotiable)
11//!
12//! - **PEG semantics, exactly.** Ordered [`Peg::Choice`] commits on the
13//!   first alternative that matches (no reparse of committed input);
14//!   [`Peg::Repeat`] is greedy and never backtracks into completed
15//!   iterations; a failed alternative restores the input position fully
16//!   (no partial-consume leaks).
17//! - **Farthest-failure tracking from day one.** The interpreter records
18//!   the rightmost failure position + the expected set at that point *as
19//!   it runs*. `dsl_kit_load` sees a diagnostic with position + expected
20//!   set on failure.
21//! - **Termination guarantees at runtime.** Left recursion (a rule
22//!   re-entered at the same input position) and nullable-body
23//!   [`Peg::Repeat`] (body succeeds without consuming) both trip
24//!   guards that either error out (left recursion) or break the loop
25//!   (nullable repeat) rather than hanging. G-3's `GrammarCheck` will
26//!   catch these statically.
27//!
28//! # Capture model
29//!
30//! Three capture primitives:
31//!
32//! - [`Peg::Node`] `{ variant, body }` — opens a `ParseTree` scope with
33//!   the given variant name. Inside `body`, every [`Peg::Field`] binding
34//!   becomes a field or child slot on the tree. On success the tree is
35//!   *contributed* upwards (to an enclosing Field, or to the top-level
36//!   result at the root).
37//! - [`Peg::Field`] `{ name, body }` — captures body's *productions*
38//!   (raw text spans from [`Peg::Token`] + trees from [`Peg::Node`]) and
39//!   binds them under `name` on the enclosing Node scope. Productions
40//!   that are all text → one [`RawValue::Text`] field (joined). All
41//!   trees → child slot with one or more subtrees. Mixed → tree
42//!   productions win (raw text is dropped as syntactic noise from
43//!   sub-Nodes' brackets etc.); empty → the Field silently no-ops.
44//!   G-3's `GrammarCheck` will surface Mixed as a grammar bug.
45//! - [`Peg::KeyedEntry`] `{ slot, key, value }` — one entry of a keyed
46//!   child slot (`Multiplicity::Map`). `key` produces the entry's key
47//!   text, `value` the entry's subtree, and the pair lands in
48//!   [`ParseTree::keyed_children`] under `slot`. A separate primitive
49//!   rather than a `Field` convention because a `Field` binds *one*
50//!   name to its productions, which cannot express a name the input
51//!   supplies; pairing adjacent text and tree productions inside a
52//!   `Field` instead would make the capture depend on production
53//!   order, which every backtracking path is free to disturb.
54//!   [`Peg::Node`] sorts each keyed slot by key before emitting, so
55//!   grammars need not care what order the source was written in —
56//!   the canonical order [`ParseTree`] requires falls out.
57//!
58//! # Whitespace policy (parser-design §3.5, decided in G-2)
59//!
60//! **Implicit skip of `[ \t\r\n]*` before every [`Peg::Token`]** (except
61//! the `%ws` class itself, which matches one-or-more whitespace
62//! literally). No per-rule opt-out yet — deferred until a concrete
63//! consumer demands it. Leading and trailing whitespace at the input
64//! boundary are also skipped by [`Grammar::parse`].
65//!
66//! # Token pattern language
67//!
68//! [`Peg::Token`]'s `pat` string is either a literal or a class:
69//!
70//! - `%ident` — `[A-Za-z_][A-Za-z_0-9]*`
71//! - `%int`   — `-?[0-9]+`
72//! - `%str`   — a double-quoted string literal with `\"` `\\` `\n`
73//!   `\t` `\r` escapes. Unlike every other token, the production it
74//!   contributes is the **decoded inner content** (quotes stripped,
75//!   escapes resolved), so a `Field` wrapping `%str` binds the string
76//!   value directly.
77//! - `%str_raw` — same matching rules as `%str`, but the production
78//!   is the **raw source slice** (quotes and escape sequences kept
79//!   verbatim). Field authors use this when downstream consumers need
80//!   the JSON-compatible literal — typically the built-in
81//!   `Vec<String>` mapping in `schema_gen`, which relies on
82//!   `serde_json::from_str` in `build_field_vec` to reparse the
83//!   captured `["a", "b"]` text.
84//! - `%ws`    — `[ \t\r\n]+` (skip is disabled for this class)
85//! - `%kw:<word>` — literal `<word>` with a word-boundary guard: the
86//!   byte immediately after the match must not be a word char. This is
87//!   how you write reserved words like `let` / `in` without swallowing
88//!   the prefix of identifiers such as `letme`.
89//! - anything else — plain literal match with no boundary guard. Use
90//!   this for punctuation like `+`, `*`, `(`, `)`, `=`.
91
92#![allow(clippy::result_unit_err)]
93
94use crate::{BuildError, Diagnostic, ParseTree, RawValue, Span};
95use dsl_kit_core::{NodeId, Suggester};
96use dsl_kit_macros::{DslNode as DslNodeDerive, DslSchema as DslSchemaDerive};
97use std::collections::{BTreeSet, HashMap};
98
99// ---------------------------------------------------------------------------
100// Peg AST
101// ---------------------------------------------------------------------------
102
103/// PEG grammar AST.
104///
105/// One value per primitive; the [`Grammar`] wrapper carries the flat
106/// list of rules and the start-rule name.
107#[derive(Debug, Clone, DslNodeDerive, DslSchemaDerive)]
108pub enum Peg {
109    /// Named rule definition. Top-level entries in
110    /// [`Grammar::rules`] must be `Rule`s; nested `Rule` variants are
111    /// legal but unusual and are treated as anonymous scopes by the
112    /// interpreter (they run `body` and forward its productions).
113    Rule {
114        /// Stable node id.
115        id: NodeId,
116        /// Rule name (referenced by [`Peg::RuleRef`]).
117        name: String,
118        /// Rule body.
119        body: Box<Peg>,
120    },
121    /// Sequence — every item must succeed in order.
122    Seq {
123        /// Stable node id.
124        id: NodeId,
125        /// Ordered sequence items.
126        items: Vec<Peg>,
127    },
128    /// Ordered choice — first alternative that succeeds commits.
129    Choice {
130        /// Stable node id.
131        id: NodeId,
132        /// Alternatives, tried left to right.
133        alts: Vec<Peg>,
134    },
135    /// Greedy repetition — runs `body` between `min` and `max` times.
136    Repeat {
137        /// Stable node id.
138        id: NodeId,
139        /// Repeated body.
140        body: Box<Peg>,
141        /// Minimum successful iterations (inclusive).
142        min: u32,
143        /// Maximum successful iterations (inclusive); `None` = unbounded.
144        max: Option<u32>,
145    },
146    /// Reference to another rule by name.
147    RuleRef {
148        /// Stable node id.
149        id: NodeId,
150        /// Referenced rule name.
151        name: String,
152    },
153    /// Terminal — matches a literal string or a small character class
154    /// (see the module docs' token pattern language).
155    Token {
156        /// Stable node id.
157        id: NodeId,
158        /// Token pattern (literal or `%ident` / `%int` / `%str` /
159        /// `%ws` / `%kw:<word>`).
160        pat: String,
161    },
162    /// Opens a `ParseTree` capture scope with the given `variant` name.
163    Node {
164        /// Stable node id.
165        id: NodeId,
166        /// Variant name on the produced `ParseTree`.
167        variant: String,
168        /// Scope body.
169        body: Box<Peg>,
170    },
171    /// Captures body's productions and binds them under `name` on the
172    /// enclosing [`Peg::Node`] scope.
173    Field {
174        /// Stable node id.
175        id: NodeId,
176        /// Field or child-slot name on the enclosing Node.
177        name: String,
178        /// Capture body.
179        body: Box<Peg>,
180    },
181    /// Captures one `key → subtree` entry of a keyed child slot
182    /// ([`dsl_kit_schema::Multiplicity::Map`]) on the enclosing
183    /// [`Peg::Node`] scope.
184    ///
185    /// `key` must produce text (typically `%str` or `%ident`) and
186    /// `value` must produce exactly one tree (typically a `RuleRef`
187    /// reaching a [`Peg::Node`]). Anything else is a grammar bug: the
188    /// entry is dropped and the parse fails rather than contributing a
189    /// half-formed pair, because a keyed entry missing its key has
190    /// nowhere to go.
191    KeyedEntry {
192        /// Stable node id.
193        id: NodeId,
194        /// Keyed child-slot name on the enclosing Node.
195        slot: String,
196        /// Production for the entry's key.
197        key: Box<Peg>,
198        /// Production for the entry's subtree.
199        value: Box<Peg>,
200    },
201}
202
203// ---------------------------------------------------------------------------
204// Grammar wrapper
205// ---------------------------------------------------------------------------
206
207/// A PEG grammar: a flat list of top-level [`Peg::Rule`]s plus the name
208/// of the start rule.
209///
210/// Kept as a plain wrapper struct deriving nothing so the `Peg` enum
211/// stays clean (parser-design §3.4).
212#[derive(Debug, Clone)]
213pub struct Grammar {
214    /// Top-level rules. Every element should be a [`Peg::Rule`]
215    /// variant — the interpreter looks up rules by name against this
216    /// list.
217    pub rules: Vec<Peg>,
218    /// Name of the start rule.
219    pub start: String,
220}
221
222impl Grammar {
223    /// Constructs a new [`Grammar`].
224    pub fn new(rules: Vec<Peg>, start: impl Into<String>) -> Self {
225        Self {
226            rules,
227            start: start.into(),
228        }
229    }
230
231    /// Parses `input` against this grammar.
232    ///
233    /// On success returns a single top-level [`ParseTree`] (produced by
234    /// exactly one [`Peg::Node`] reached from the start rule).
235    ///
236    /// On failure returns a [`BuildError`] whose diagnostics carry the
237    /// farthest-failure position + expected set, formatted in the shared
238    /// dialect (`{ severity, code, message, location }`).
239    pub fn parse(&self, input: &str) -> Result<ParseTree, BuildError> {
240        let mut rules_by_name: HashMap<&str, &Peg> = HashMap::new();
241        for r in &self.rules {
242            if let Peg::Rule { name, .. } = r {
243                rules_by_name.insert(name.as_str(), r);
244            }
245        }
246        let start_rule = rules_by_name
247            .get(self.start.as_str())
248            .copied()
249            .ok_or_else(|| {
250                let names: Vec<&str> = rules_by_name.keys().copied().collect();
251                let base = format!("start rule `{}` is not defined in the grammar", self.start);
252                let msg = match crate::BuiltinLevenshteinSuggester
253                    .enrich_unknown(self.start.as_str(), &names)
254                {
255                    Some(hint) => format!("{base} ({hint})"),
256                    None => base,
257                };
258                BuildError::single(Diagnostic::error(codes::UNKNOWN_RULE, msg))
259            })?;
260
261        let mut interp = Interpreter::new(input, rules_by_name);
262        // Skip leading whitespace at the input boundary.
263        interp.skip_ws();
264        // Push the top-level sink.
265        interp.sink_stack.push(ActiveSink::Top(TopSink::default()));
266
267        match interp.run_peg(start_rule) {
268            Ok(()) => {}
269            Err(()) => {
270                if let Some(fatal) = interp.fatal_error.take() {
271                    return Err(BuildError::single(fatal));
272                }
273                return Err(BuildError::single(interp.expected_diagnostic()));
274            }
275        }
276
277        // Trailing whitespace + EOF check.
278        interp.skip_ws();
279        if interp.pos != input.len() {
280            // Try to attribute to the farthest expected set if we have
281            // one at/after this position; otherwise raw "trailing input".
282            let diag = if interp.farthest_pos >= interp.pos && !interp.farthest_expected.is_empty()
283            {
284                interp.expected_diagnostic()
285            } else {
286                Diagnostic::error(
287                    codes::UNEXPECTED,
288                    format!("unexpected trailing input at byte {}", interp.pos),
289                )
290                .with_span(Some(Span::new(interp.pos, input.len())))
291            };
292            return Err(BuildError::single(diag));
293        }
294
295        let top = match interp.sink_stack.pop() {
296            Some(ActiveSink::Top(t)) => t,
297            _ => unreachable!("top sink must be present"),
298        };
299        top.tree.ok_or_else(|| {
300            BuildError::single(Diagnostic::error(
301                codes::NO_TOP_TREE,
302                format!(
303                    "parse succeeded but produced no top-level `Node`; \
304                     start rule `{}` must reach exactly one `Peg::Node`",
305                    self.start
306                ),
307            ))
308        })
309    }
310}
311
312// ---------------------------------------------------------------------------
313// Diagnostic codes
314// ---------------------------------------------------------------------------
315
316/// Diagnostic codes emitted by the PEG interpreter.
317pub mod codes {
318    /// Input did not match at the farthest failure position; message
319    /// carries the expected set.
320    pub const UNEXPECTED: &str = "dsl_kit::parse::peg::unexpected";
321    /// [`super::Peg::RuleRef`] pointed to a rule name not present in
322    /// [`super::Grammar::rules`], or [`super::Grammar::start`] itself is
323    /// unresolved.
324    pub const UNKNOWN_RULE: &str = "dsl_kit::parse::peg::unknown_rule";
325    /// A rule was re-entered at the same input position without any
326    /// progress — indicates left recursion. G-3's `GrammarCheck` will
327    /// catch this statically; the runtime guard is a backstop that
328    /// errors out rather than hanging.
329    pub const LEFT_RECURSION: &str = "dsl_kit::parse::peg::left_recursion";
330    /// A [`super::Peg::Repeat`] iteration succeeded without consuming
331    /// input. The interpreter breaks the loop (per §3.5 termination
332    /// guarantee); this diagnostic is attached when the `min` bound is
333    /// also not yet met, turning the situation into a hard failure.
334    pub const NULLABLE_REPEAT: &str = "dsl_kit::parse::peg::nullable_repeat";
335    /// Parse succeeded but the start rule never reached a
336    /// [`super::Peg::Node`], so there is no top-level `ParseTree`.
337    pub const NO_TOP_TREE: &str = "dsl_kit::parse::peg::no_top_tree";
338}
339
340// ---------------------------------------------------------------------------
341// Interpreter
342// ---------------------------------------------------------------------------
343
344/// A raw production captured inside a [`FieldSink`]. Text comes from
345/// [`Peg::Token`] matches, trees from [`Peg::Node`] captures. The span
346/// on `Text` is retained for future span-carrying `RawValue::Text`
347/// support (post-G-2).
348#[derive(Debug, Clone)]
349enum Production {
350    #[allow(dead_code)] // span kept for post-G-2 span-carrying Text values
351    Text(String, Span),
352    Tree(ParseTree),
353}
354
355#[derive(Debug, Default, Clone)]
356struct FieldSink {
357    productions: Vec<Production>,
358}
359
360#[derive(Debug, Default, Clone)]
361struct NodeSink {
362    fields: Vec<(String, RawValue)>,
363    children: Vec<(String, Vec<ParseTree>)>,
364    keyed_children: Vec<(String, Vec<(String, ParseTree)>)>,
365}
366
367#[derive(Debug, Default, Clone)]
368struct TopSink {
369    tree: Option<ParseTree>,
370}
371
372/// The active-sink stack entry. Only the top sink is ever mutated by
373/// productions.
374#[derive(Debug, Clone)]
375enum ActiveSink {
376    Top(TopSink),
377    Node(NodeSink),
378    Field(FieldSink),
379}
380
381struct Interpreter<'g, 'i> {
382    input: &'i str,
383    pos: usize,
384    rules_by_name: HashMap<&'g str, &'g Peg>,
385    sink_stack: Vec<ActiveSink>,
386    // Farthest-failure tracking (parser-design §3.5).
387    farthest_pos: usize,
388    farthest_expected: BTreeSet<String>,
389    // Left-recursion guard: (rule name, position at entry).
390    call_stack: Vec<(&'g str, usize)>,
391    // Fatal errors (unknown rule / left recursion) — trip Err(()) and
392    // short-circuit past normal recovery.
393    fatal_error: Option<Diagnostic>,
394}
395
396impl<'g, 'i> Interpreter<'g, 'i> {
397    fn new(input: &'i str, rules_by_name: HashMap<&'g str, &'g Peg>) -> Self {
398        Self {
399            input,
400            pos: 0,
401            rules_by_name,
402            sink_stack: Vec::new(),
403            farthest_pos: 0,
404            farthest_expected: BTreeSet::new(),
405            call_stack: Vec::new(),
406            fatal_error: None,
407        }
408    }
409
410    // -----------------------------------------------------------------------
411    // Sink helpers
412    // -----------------------------------------------------------------------
413
414    fn top_sink_snapshot(&self) -> ActiveSink {
415        self.sink_stack
416            .last()
417            .cloned()
418            .expect("sink stack has at least the top-level entry during parse")
419    }
420
421    fn restore_top_sink(&mut self, snap: ActiveSink) {
422        let last = self
423            .sink_stack
424            .last_mut()
425            .expect("sink stack has at least the top-level entry during parse");
426        *last = snap;
427    }
428
429    fn contribute_text(&mut self, text: String, span: Span) {
430        match self.sink_stack.last_mut() {
431            Some(ActiveSink::Field(s)) => s.productions.push(Production::Text(text, span)),
432            _ => {
433                // Discard — Token outside a Field is syntactic (like "+" or "let").
434            }
435        }
436    }
437
438    fn contribute_tree(&mut self, tree: ParseTree) {
439        match self.sink_stack.last_mut() {
440            Some(ActiveSink::Field(s)) => s.productions.push(Production::Tree(tree)),
441            Some(ActiveSink::Node(_)) => {
442                // Nested Node not wrapped in Field — silently discarded
443                // at runtime. G-3's GrammarCheck should flag such
444                // grammars as author bugs.
445            }
446            Some(ActiveSink::Top(t)) => {
447                // Top-level result: latest wins (there should be exactly
448                // one; a subsequent one is unusual but harmless).
449                t.tree = Some(tree);
450            }
451            None => unreachable!("sink stack must not be empty during parse"),
452        }
453    }
454
455    fn contribute_field(&mut self, name: &str, productions: Vec<Production>) {
456        if productions.is_empty() {
457            return;
458        }
459        let all_text = productions
460            .iter()
461            .all(|p| matches!(p, Production::Text(..)));
462        let all_tree = productions
463            .iter()
464            .all(|p| matches!(p, Production::Tree(..)));
465
466        let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
467            // Field outside a Node — silently ignored at runtime.
468            return;
469        };
470
471        if all_text {
472            let joined: String = productions
473                .iter()
474                .filter_map(|p| match p {
475                    Production::Text(t, _) => Some(t.as_str()),
476                    _ => None,
477                })
478                .collect();
479            node_sink
480                .fields
481                .push((name.to_string(), RawValue::Text(joined)));
482            return;
483        }
484        if all_tree {
485            let trees: Vec<ParseTree> = productions
486                .into_iter()
487                .filter_map(|p| match p {
488                    Production::Tree(t) => Some(t),
489                    _ => None,
490                })
491                .collect();
492            if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
493                slot.1.extend(trees);
494            } else {
495                node_sink.children.push((name.to_string(), trees));
496            }
497            return;
498        }
499        // Mixed: keep tree productions, drop texts (grammar bug — G-3
500        // GrammarCheck will flag).
501        let trees: Vec<ParseTree> = productions
502            .into_iter()
503            .filter_map(|p| match p {
504                Production::Tree(t) => Some(t),
505                _ => None,
506            })
507            .collect();
508        if trees.is_empty() {
509            return;
510        }
511        if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
512            slot.1.extend(trees);
513        } else {
514            node_sink.children.push((name.to_string(), trees));
515        }
516    }
517
518    // -----------------------------------------------------------------------
519    // Farthest-failure helpers
520    // -----------------------------------------------------------------------
521
522    fn expected(&mut self, what: impl Into<String>) {
523        if self.pos > self.farthest_pos {
524            self.farthest_pos = self.pos;
525            self.farthest_expected.clear();
526            self.farthest_expected.insert(what.into());
527        } else if self.pos == self.farthest_pos {
528            self.farthest_expected.insert(what.into());
529        }
530    }
531
532    fn expected_diagnostic(&self) -> Diagnostic {
533        let expected: Vec<String> = self.farthest_expected.iter().cloned().collect();
534        let expected_msg = if expected.is_empty() {
535            "<unknown>".to_string()
536        } else {
537            expected
538                .iter()
539                .map(|e| format!("`{e}`"))
540                .collect::<Vec<_>>()
541                .join(" | ")
542        };
543        let end = self.input.len().min(self.farthest_pos + 1);
544        let got_msg = if self.farthest_pos >= self.input.len() {
545            "end of input".to_string()
546        } else {
547            let bytes = self.input.as_bytes();
548            // Grab a small snippet — up to 8 bytes — to help the reader.
549            let snip_end = self.input.len().min(self.farthest_pos + 8);
550            let snip =
551                std::str::from_utf8(&bytes[self.farthest_pos..snip_end]).unwrap_or("<non-utf8>");
552            format!("`{}`", snip)
553        };
554        Diagnostic::error(
555            codes::UNEXPECTED,
556            format!(
557                "expected {expected_msg} at byte {}, got {got_msg}",
558                self.farthest_pos
559            ),
560        )
561        .with_span(Some(Span::new(self.farthest_pos, end)))
562    }
563
564    // -----------------------------------------------------------------------
565    // PEG dispatch
566    // -----------------------------------------------------------------------
567
568    fn run_peg(&mut self, peg: &'g Peg) -> Result<(), ()> {
569        match peg {
570            Peg::Rule { body, .. } => self.run_peg(body),
571            Peg::Seq { items, .. } => {
572                for item in items {
573                    self.run_peg(item)?;
574                }
575                Ok(())
576            }
577            Peg::Choice { alts, .. } => self.run_choice(alts),
578            Peg::Repeat { body, min, max, .. } => self.run_repeat(body, *min, *max),
579            Peg::RuleRef { name, .. } => self.run_rule_ref(name),
580            Peg::Token { pat, .. } => self.match_token(pat),
581            Peg::Node { variant, body, .. } => self.run_node(variant, body),
582            Peg::Field { name, body, .. } => self.run_field(name, body),
583            Peg::KeyedEntry {
584                slot, key, value, ..
585            } => self.run_keyed_entry(slot, key, value),
586        }
587    }
588
589    fn run_choice(&mut self, alts: &'g [Peg]) -> Result<(), ()> {
590        let start_pos = self.pos;
591        let saved = self.top_sink_snapshot();
592        for alt in alts {
593            self.pos = start_pos;
594            self.restore_top_sink(saved.clone());
595            if self.fatal_error.is_some() {
596                return Err(());
597            }
598            if self.run_peg(alt).is_ok() {
599                return Ok(());
600            }
601            if self.fatal_error.is_some() {
602                return Err(());
603            }
604        }
605        self.pos = start_pos;
606        self.restore_top_sink(saved);
607        Err(())
608    }
609
610    fn run_repeat(&mut self, body: &'g Peg, min: u32, max: Option<u32>) -> Result<(), ()> {
611        let mut count: u32 = 0;
612        loop {
613            if let Some(mx) = max
614                && count >= mx
615            {
616                break;
617            }
618            let saved_pos = self.pos;
619            let saved_sink = self.top_sink_snapshot();
620            match self.run_peg(body) {
621                Ok(()) => {
622                    if self.pos == saved_pos {
623                        // Nullable-body iteration — break rather than
624                        // hang. GrammarCheck should reject grammars that
625                        // permit this, so the interpreter's job is
626                        // termination, not diagnosis.
627                        if count < min {
628                            self.fatal_error = Some(
629                                Diagnostic::error(
630                                    codes::NULLABLE_REPEAT,
631                                    "repeat body succeeded without consuming input".to_string(),
632                                )
633                                .with_span(Some(Span::new(saved_pos, saved_pos))),
634                            );
635                            return Err(());
636                        }
637                        break;
638                    }
639                    count += 1;
640                }
641                Err(()) => {
642                    if self.fatal_error.is_some() {
643                        return Err(());
644                    }
645                    self.pos = saved_pos;
646                    self.restore_top_sink(saved_sink);
647                    break;
648                }
649            }
650        }
651        if count < min { Err(()) } else { Ok(()) }
652    }
653
654    fn run_rule_ref(&mut self, name: &str) -> Result<(), ()> {
655        let Some(&rule) = self.rules_by_name.get(name) else {
656            let candidates: Vec<&str> = self.rules_by_name.keys().copied().collect();
657            let base = format!("reference to undefined rule `{name}`");
658            let msg = match crate::BuiltinLevenshteinSuggester.enrich_unknown(name, &candidates) {
659                Some(hint) => format!("{base} ({hint})"),
660                None => base,
661            };
662            self.fatal_error = Some(
663                Diagnostic::error(codes::UNKNOWN_RULE, msg)
664                    .with_span(Some(Span::new(self.pos, self.pos))),
665            );
666            return Err(());
667        };
668        // Look up by pointer so we keep the &'g lifetime attached.
669        let rule_name: &'g str = self
670            .rules_by_name
671            .keys()
672            .copied()
673            .find(|k| *k == name)
674            .expect("just found");
675        // Left-recursion guard: rule re-entered at the same position
676        // without any progress.
677        if self
678            .call_stack
679            .iter()
680            .any(|(n, p)| *n == rule_name && *p == self.pos)
681        {
682            self.fatal_error = Some(
683                Diagnostic::error(
684                    codes::LEFT_RECURSION,
685                    format!(
686                        "left recursion detected: rule `{name}` re-entered at byte {}",
687                        self.pos
688                    ),
689                )
690                .with_span(Some(Span::new(self.pos, self.pos))),
691            );
692            return Err(());
693        }
694        self.call_stack.push((rule_name, self.pos));
695        let r = self.run_peg(rule);
696        self.call_stack.pop();
697        r
698    }
699
700    fn run_node(&mut self, variant: &str, body: &'g Peg) -> Result<(), ()> {
701        let start_pos = self.pos;
702        self.sink_stack.push(ActiveSink::Node(NodeSink::default()));
703        let body_result = self.run_peg(body);
704        let node_sink = match self.sink_stack.pop() {
705            Some(ActiveSink::Node(s)) => s,
706            _ => unreachable!("balanced push/pop of NodeSink"),
707        };
708        body_result?;
709        let end_pos = self.pos;
710        // Keyed entries arrive in source order; `ParseTree` requires
711        // ascending key order, and `check_conformance` enforces it.
712        // Sorting here — rather than asking every grammar author to
713        // write their maps pre-sorted — is what makes source order a
714        // surface detail, exactly as it is for the JSON bridge.
715        let mut keyed_children = node_sink.keyed_children;
716        for (_, entries) in &mut keyed_children {
717            entries.sort_by(|(a, _), (b, _)| a.cmp(b));
718        }
719
720        let tree = ParseTree {
721            variant: variant.to_string(),
722            fields: node_sink.fields,
723            children: node_sink.children,
724            keyed_children,
725            span: Some(Span::new(start_pos, end_pos)),
726        };
727        self.contribute_tree(tree);
728        Ok(())
729    }
730
731    fn run_field(&mut self, name: &str, body: &'g Peg) -> Result<(), ()> {
732        self.sink_stack
733            .push(ActiveSink::Field(FieldSink::default()));
734        let body_result = self.run_peg(body);
735        let field_sink = match self.sink_stack.pop() {
736            Some(ActiveSink::Field(s)) => s,
737            _ => unreachable!("balanced push/pop of FieldSink"),
738        };
739        body_result?;
740        self.contribute_field(name, field_sink.productions);
741        Ok(())
742    }
743
744    /// Runs one keyed entry: `key` into its own sink, then `value` into
745    /// another, then pairs them onto the enclosing Node's keyed half.
746    ///
747    /// The two halves are captured separately rather than in one sink
748    /// because a single `FieldSink` would leave "which production was
749    /// the key" to positional luck. Failure of either half fails the
750    /// entry: a pair missing its key cannot be stored, and storing the
751    /// value under a fabricated key would invent data.
752    fn run_keyed_entry(&mut self, slot: &str, key: &'g Peg, value: &'g Peg) -> Result<(), ()> {
753        let key_text = {
754            self.sink_stack
755                .push(ActiveSink::Field(FieldSink::default()));
756            let result = self.run_peg(key);
757            let sink = match self.sink_stack.pop() {
758                Some(ActiveSink::Field(s)) => s,
759                _ => unreachable!("balanced push/pop of FieldSink"),
760            };
761            result?;
762            // A key half that matched without producing anything is a
763            // grammar bug (typically a nullable key production). Every
764            // such entry would key on the empty string and collide
765            // with its siblings, so fail instead — this is the check
766            // the `is_empty()` guard exists for. A production that is
767            // *present* but empty (`""` via `%str`) is a different
768            // thing: it is a key the AST and the JSON front-end can
769            // both hold, so the text syntax accepts it too.
770            if sink.productions.is_empty() {
771                self.expected("a text production for the keyed-entry key");
772                return Err(());
773            }
774            let mut text = String::new();
775            for production in &sink.productions {
776                match production {
777                    Production::Text(t, _) => text.push_str(t),
778                    // A tree where the key belongs is a grammar bug of
779                    // the same family — there is no text to key on.
780                    Production::Tree(_) => {
781                        self.expected("a text production for the keyed-entry key");
782                        return Err(());
783                    }
784                }
785            }
786            text
787        };
788
789        self.sink_stack
790            .push(ActiveSink::Field(FieldSink::default()));
791        let value_result = self.run_peg(value);
792        let value_sink = match self.sink_stack.pop() {
793            Some(ActiveSink::Field(s)) => s,
794            _ => unreachable!("balanced push/pop of FieldSink"),
795        };
796        value_result?;
797
798        let mut trees = value_sink.productions.into_iter().filter_map(|p| match p {
799            Production::Tree(t) => Some(t),
800            // Syntactic noise from the value's own brackets, dropped
801            // the same way `contribute_field`'s mixed arm drops it.
802            Production::Text(..) => None,
803        });
804        let Some(tree) = trees.next() else {
805            self.expected("a subtree production for the keyed-entry value");
806            return Err(());
807        };
808        if trees.next().is_some() {
809            self.expected("exactly one subtree for the keyed-entry value");
810            return Err(());
811        }
812
813        let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
814            // KeyedEntry outside a Node — silently ignored at runtime,
815            // matching `contribute_field`'s handling of the same
816            // grammar bug.
817            return Ok(());
818        };
819        if let Some(existing) = node_sink.keyed_children.iter_mut().find(|(n, _)| n == slot) {
820            existing.1.push((key_text, tree));
821        } else {
822            node_sink
823                .keyed_children
824                .push((slot.to_string(), vec![(key_text, tree)]));
825        }
826        Ok(())
827    }
828
829    // -----------------------------------------------------------------------
830    // Token matching
831    // -----------------------------------------------------------------------
832
833    fn match_token(&mut self, pat: &str) -> Result<(), ()> {
834        if pat != "%ws" {
835            self.skip_ws();
836        }
837        let start = self.pos;
838        if pat == "%str" {
839            // Special-cased because the contributed production is the
840            // decoded inner content, not the matched source slice.
841            return match self.match_str() {
842                Some(decoded) => {
843                    let end = self.pos;
844                    self.contribute_text(decoded, Span::new(start, end));
845                    Ok(())
846                }
847                None => {
848                    self.expected(pat);
849                    self.pos = start;
850                    Err(())
851                }
852            };
853        }
854        if pat == "%str_raw" {
855            // Same match as %str, but the contributed production is the
856            // raw source slice (quotes + escape sequences preserved).
857            // Used by the built-in `Vec<String>` production so the
858            // captured field text is JSON-parseable directly.
859            return match self.match_str() {
860                Some(_) => {
861                    let end = self.pos;
862                    let text = self.input[start..end].to_string();
863                    self.contribute_text(text, Span::new(start, end));
864                    Ok(())
865                }
866                None => {
867                    self.expected(pat);
868                    self.pos = start;
869                    Err(())
870                }
871            };
872        }
873        let ok = if pat == "%ident" {
874            self.match_ident()
875        } else if pat == "%int" {
876            self.match_int()
877        } else if pat == "%ws" {
878            self.match_ws_required()
879        } else if let Some(word) = pat.strip_prefix("%kw:") {
880            self.match_keyword(word)
881        } else {
882            self.match_literal(pat)
883        };
884        if ok {
885            let end = self.pos;
886            let text = self.input[start..end].to_string();
887            self.contribute_text(text, Span::new(start, end));
888            Ok(())
889        } else {
890            // Restore pos (in case skip_ws advanced but match failed —
891            // farthest-failure position is the *post-skip* position,
892            // which is the semantic failure spot).
893            self.expected(pat);
894            self.pos = start;
895            Err(())
896        }
897    }
898
899    fn skip_ws(&mut self) {
900        let bytes = self.input.as_bytes();
901        while let Some(&c) = bytes.get(self.pos) {
902            if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
903                self.pos += 1;
904            } else {
905                break;
906            }
907        }
908    }
909
910    fn match_ident(&mut self) -> bool {
911        let bytes = self.input.as_bytes();
912        match bytes.get(self.pos) {
913            Some(&c) if is_ident_start(c) => self.pos += 1,
914            _ => return false,
915        }
916        while let Some(&c) = bytes.get(self.pos) {
917            if is_ident_cont(c) {
918                self.pos += 1;
919            } else {
920                break;
921            }
922        }
923        true
924    }
925
926    fn match_int(&mut self) -> bool {
927        let bytes = self.input.as_bytes();
928        let mut p = self.pos;
929        if bytes.get(p) == Some(&b'-') {
930            p += 1;
931        }
932        let digit_start = p;
933        while let Some(&c) = bytes.get(p) {
934            if c.is_ascii_digit() {
935                p += 1;
936            } else {
937                break;
938            }
939        }
940        if p > digit_start {
941            self.pos = p;
942            true
943        } else {
944            false
945        }
946    }
947
948    /// Matches a double-quoted string literal and returns the decoded
949    /// inner content. `None` on no opening quote, an unterminated
950    /// literal, or an unknown escape.
951    fn match_str(&mut self) -> Option<String> {
952        let rest = &self.input[self.pos..];
953        let mut chars = rest.char_indices();
954        match chars.next() {
955            Some((_, '"')) => {}
956            _ => return None,
957        }
958        let mut out = String::new();
959        while let Some((i, c)) = chars.next() {
960            match c {
961                '"' => {
962                    self.pos += i + 1;
963                    return Some(out);
964                }
965                '\\' => match chars.next() {
966                    Some((_, '"')) => out.push('"'),
967                    Some((_, '\\')) => out.push('\\'),
968                    Some((_, 'n')) => out.push('\n'),
969                    Some((_, 't')) => out.push('\t'),
970                    Some((_, 'r')) => out.push('\r'),
971                    _ => return None,
972                },
973                other => out.push(other),
974            }
975        }
976        None
977    }
978
979    fn match_ws_required(&mut self) -> bool {
980        let start = self.pos;
981        let bytes = self.input.as_bytes();
982        while let Some(&c) = bytes.get(self.pos) {
983            if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
984                self.pos += 1;
985            } else {
986                break;
987            }
988        }
989        self.pos > start
990    }
991
992    fn match_literal(&mut self, s: &str) -> bool {
993        let bytes = self.input.as_bytes();
994        let end = self.pos + s.len();
995        if end > bytes.len() {
996            return false;
997        }
998        if &bytes[self.pos..end] != s.as_bytes() {
999            return false;
1000        }
1001        self.pos = end;
1002        true
1003    }
1004
1005    fn match_keyword(&mut self, word: &str) -> bool {
1006        let saved = self.pos;
1007        if !self.match_literal(word) {
1008            return false;
1009        }
1010        // Word-boundary guard: the byte after must not be a word char.
1011        if let Some(&next) = self.input.as_bytes().get(self.pos)
1012            && is_ident_cont(next)
1013        {
1014            self.pos = saved;
1015            return false;
1016        }
1017        true
1018    }
1019}
1020
1021fn is_ident_start(c: u8) -> bool {
1022    c.is_ascii_alphabetic() || c == b'_'
1023}
1024
1025fn is_ident_cont(c: u8) -> bool {
1026    c.is_ascii_alphanumeric() || c == b'_'
1027}
1028
1029// ---------------------------------------------------------------------------
1030// Convenience constructors (grammar authors build Peg values by hand
1031// until G-4's meta-grammar; these helpers cut boilerplate).
1032// ---------------------------------------------------------------------------
1033
1034use dsl_kit_core::IdGen;
1035
1036/// Builds a [`Peg::Rule`] node with a fresh id.
1037pub fn rule(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
1038    Peg::Rule {
1039        id: ids.node(),
1040        name: name.into(),
1041        body: Box::new(body),
1042    }
1043}
1044
1045/// Builds a [`Peg::Seq`] node with a fresh id.
1046pub fn seq(ids: &IdGen, items: Vec<Peg>) -> Peg {
1047    Peg::Seq {
1048        id: ids.node(),
1049        items,
1050    }
1051}
1052
1053/// Builds a [`Peg::Choice`] node with a fresh id.
1054pub fn choice(ids: &IdGen, alts: Vec<Peg>) -> Peg {
1055    Peg::Choice {
1056        id: ids.node(),
1057        alts,
1058    }
1059}
1060
1061/// Builds a [`Peg::Repeat`] node with a fresh id.
1062pub fn repeat(ids: &IdGen, body: Peg, min: u32, max: Option<u32>) -> Peg {
1063    Peg::Repeat {
1064        id: ids.node(),
1065        body: Box::new(body),
1066        min,
1067        max,
1068    }
1069}
1070
1071/// Builds a [`Peg::RuleRef`] node with a fresh id.
1072pub fn rule_ref(ids: &IdGen, name: impl Into<String>) -> Peg {
1073    Peg::RuleRef {
1074        id: ids.node(),
1075        name: name.into(),
1076    }
1077}
1078
1079/// Builds a [`Peg::Token`] node with a fresh id.
1080pub fn token(ids: &IdGen, pat: impl Into<String>) -> Peg {
1081    Peg::Token {
1082        id: ids.node(),
1083        pat: pat.into(),
1084    }
1085}
1086
1087/// Builds a [`Peg::Node`] capture node with a fresh id.
1088pub fn node(ids: &IdGen, variant: impl Into<String>, body: Peg) -> Peg {
1089    Peg::Node {
1090        id: ids.node(),
1091        variant: variant.into(),
1092        body: Box::new(body),
1093    }
1094}
1095
1096/// Builds a [`Peg::Field`] capture node with a fresh id.
1097pub fn field(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
1098    Peg::Field {
1099        id: ids.node(),
1100        name: name.into(),
1101        body: Box::new(body),
1102    }
1103}
1104
1105/// Builds a [`Peg::KeyedEntry`] capture node with a fresh id.
1106///
1107/// `key` should produce text (e.g. `token(ids, "%str")`) and `value`
1108/// exactly one subtree (e.g. `rule_ref(ids, "node")`).
1109pub fn keyed_entry(ids: &IdGen, slot: impl Into<String>, key: Peg, value: Peg) -> Peg {
1110    Peg::KeyedEntry {
1111        id: ids.node(),
1112        slot: slot.into(),
1113        key: Box::new(key),
1114        value: Box::new(value),
1115    }
1116}
1117
1118// ---------------------------------------------------------------------------
1119// Tests
1120// ---------------------------------------------------------------------------
1121
1122#[cfg(test)]
1123mod tests {
1124    use super::*;
1125    use dsl_kit_core::IdGen;
1126    use dsl_kit_schema::DslSchema;
1127
1128    // -- schema shape --
1129
1130    #[test]
1131    fn peg_schema_lists_all_variants() {
1132        let s = Peg::schema();
1133        assert_eq!(s.name, "Peg");
1134        let names: Vec<&str> = s.variants.iter().map(|v| v.name.as_str()).collect();
1135        assert_eq!(
1136            names,
1137            vec![
1138                "Rule",
1139                "Seq",
1140                "Choice",
1141                "Repeat",
1142                "RuleRef",
1143                "Token",
1144                "Node",
1145                "Field",
1146                "KeyedEntry"
1147            ]
1148        );
1149        // `KeyedEntry`'s two `Box<Peg>` halves are both child slots;
1150        // `slot` is the only payload field. Pins the derive's view of
1151        // the newest variant alongside the older `Repeat` check below.
1152        let keyed = s.variant("KeyedEntry").unwrap();
1153        let keyed_children: Vec<&str> = keyed.children.iter().map(|c| c.name.as_str()).collect();
1154        assert_eq!(keyed_children, vec!["key", "value"]);
1155        let keyed_fields: Vec<&str> = keyed.fields.iter().map(|f| f.name.as_str()).collect();
1156        assert_eq!(keyed_fields, vec!["slot"]);
1157
1158        let repeat = s.variant("Repeat").unwrap();
1159        // body -> one child; min / max -> fields.
1160        assert_eq!(repeat.children.len(), 1);
1161        assert_eq!(repeat.children[0].name, "body");
1162        let field_names: Vec<&str> = repeat.fields.iter().map(|f| f.name.as_str()).collect();
1163        assert!(field_names.contains(&"min"));
1164        assert!(field_names.contains(&"max"));
1165    }
1166
1167    // -- Token matching --
1168
1169    fn parse_one(g: &Grammar, input: &str) -> Result<ParseTree, BuildError> {
1170        g.parse(input)
1171    }
1172
1173    fn one_rule_grammar(ids: &IdGen, start: &str, body: Peg) -> Grammar {
1174        Grammar::new(vec![rule(ids, start, body)], start)
1175    }
1176
1177    // -- KeyedEntry primitive (hand-built grammars) --
1178    //
1179    // The generated grammars in `schema_gen` only ever build keyed
1180    // entries in one shape, so the primitive's own contract — what it
1181    // does with a malformed key half, a value half that yields the
1182    // wrong number of trees, or an entry outside a Node — is only
1183    // reachable from grammars written by hand, as below.
1184
1185    /// `{ key: <leaf> ... }`-style grammar over a single keyed slot,
1186    /// with the key production supplied by the caller so the failure
1187    /// branches can be driven individually.
1188    fn keyed_grammar(ids: &IdGen, key: Peg, value: Peg) -> Grammar {
1189        let entry = keyed_entry(ids, "entries", key, value);
1190        one_rule_grammar(
1191            ids,
1192            "start",
1193            node(
1194                ids,
1195                "Env",
1196                seq(
1197                    ids,
1198                    vec![
1199                        token(ids, "{"),
1200                        repeat(
1201                            ids,
1202                            seq(ids, vec![entry, repeat(ids, token(ids, ","), 0, Some(1))]),
1203                            0,
1204                            None,
1205                        ),
1206                        token(ids, "}"),
1207                    ],
1208                ),
1209            ),
1210        )
1211    }
1212
1213    /// A leaf value production: `: Lit(<int>)` wrapped in its own Node.
1214    fn keyed_leaf_value(ids: &IdGen) -> Peg {
1215        seq(
1216            ids,
1217            vec![
1218                token(ids, ":"),
1219                node(ids, "Lit", field(ids, "value", token(ids, "%int"))),
1220            ],
1221        )
1222    }
1223
1224    #[test]
1225    fn keyed_entry_pairs_key_with_subtree_and_sorts() {
1226        let ids = IdGen::new();
1227        let g = keyed_grammar(&ids, token(&ids, "%ident"), keyed_leaf_value(&ids));
1228        let tree = parse_one(&g, "{ b: 2, a: 1 }").unwrap();
1229        let entries = tree.keyed_child_slot("entries").expect("slot bound");
1230        let keys: Vec<&str> = entries.iter().map(|(k, _)| k.as_str()).collect();
1231        assert_eq!(keys, ["a", "b"], "Node emission sorts by key");
1232        // Values travelled with their own keys, not just in order.
1233        let values: Vec<&RawValue> = entries
1234            .iter()
1235            .map(|(_, t)| t.field("value").expect("leaf payload"))
1236            .collect();
1237        assert_eq!(values[0], &RawValue::Text("1".into()));
1238        assert_eq!(values[1], &RawValue::Text("2".into()));
1239    }
1240
1241    #[test]
1242    fn keyed_entry_accepts_an_empty_string_key() {
1243        let ids = IdGen::new();
1244        // `""` is a key the AST and the JSON bridge can both hold, so
1245        // the text side accepts it rather than leaving a `BTreeMap`
1246        // value with no spelling.
1247        let g = keyed_grammar(&ids, token(&ids, "%str"), keyed_leaf_value(&ids));
1248        let tree = parse_one(&g, r#"{ "": 1 }"#).unwrap();
1249        let entries = tree.keyed_child_slot("entries").expect("slot bound");
1250        assert_eq!(entries.len(), 1);
1251        assert_eq!(entries[0].0, "");
1252    }
1253
1254    #[test]
1255    fn keyed_entry_rejects_a_key_half_that_produces_nothing() {
1256        let ids = IdGen::new();
1257        // A nullable key half — here an optional identifier that is
1258        // absent — succeeds while contributing no production, so there
1259        // is no text to key on. Every such entry would land on `""`
1260        // and collide with its siblings, which is what separates this
1261        // case from a genuinely empty `""` key (accepted above).
1262        let g = keyed_grammar(
1263            &ids,
1264            repeat(&ids, token(&ids, "%ident"), 0, Some(1)),
1265            keyed_leaf_value(&ids),
1266        );
1267        let err = parse_one(&g, "{ : 1 }").unwrap_err();
1268        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1269    }
1270
1271    #[test]
1272    fn keyed_entry_rejects_a_tree_where_the_key_belongs() {
1273        let ids = IdGen::new();
1274        let g = keyed_grammar(
1275            &ids,
1276            node(&ids, "Lit", field(&ids, "value", token(&ids, "%int"))),
1277            keyed_leaf_value(&ids),
1278        );
1279        let err = parse_one(&g, "{ 1: 2 }").unwrap_err();
1280        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1281    }
1282
1283    #[test]
1284    fn keyed_entry_rejects_a_value_half_without_exactly_one_tree() {
1285        let ids = IdGen::new();
1286
1287        // Zero trees: the value is a bare token, so nothing to store.
1288        let none = keyed_grammar(
1289            &ids,
1290            token(&ids, "%ident"),
1291            seq(&ids, vec![token(&ids, ":"), token(&ids, "%int")]),
1292        );
1293        assert!(parse_one(&none, "{ a: 1 }").is_err());
1294
1295        // Two trees: ambiguous — which one is the entry's value?
1296        let leaf = |ids: &IdGen| node(ids, "Lit", field(ids, "value", token(ids, "%int")));
1297        let two = keyed_grammar(
1298            &ids,
1299            token(&ids, "%ident"),
1300            seq(&ids, vec![token(&ids, ":"), leaf(&ids), leaf(&ids)]),
1301        );
1302        assert!(parse_one(&two, "{ a: 1 2 }").is_err());
1303    }
1304
1305    #[test]
1306    fn keyed_entry_survives_backtracking_without_leaking_entries() {
1307        let ids = IdGen::new();
1308        // The first alternative parses one entry and then demands a
1309        // `;` the input does not have, so it fails *after* writing to
1310        // the enclosing Node's keyed half. If the sink snapshot did
1311        // not cover `keyed_children`, the abandoned entry would still
1312        // be there when the second alternative succeeds.
1313        let entry_then_semi = seq(
1314            &ids,
1315            vec![
1316                keyed_entry(
1317                    &ids,
1318                    "entries",
1319                    token(&ids, "%ident"),
1320                    keyed_leaf_value(&ids),
1321                ),
1322                token(&ids, ";"),
1323            ],
1324        );
1325        let entry_then_end = seq(
1326            &ids,
1327            vec![
1328                keyed_entry(
1329                    &ids,
1330                    "entries",
1331                    token(&ids, "%ident"),
1332                    keyed_leaf_value(&ids),
1333                ),
1334                token(&ids, "}"),
1335            ],
1336        );
1337        let g = one_rule_grammar(
1338            &ids,
1339            "start",
1340            node(
1341                &ids,
1342                "Env",
1343                seq(
1344                    &ids,
1345                    vec![
1346                        token(&ids, "{"),
1347                        choice(&ids, vec![entry_then_semi, entry_then_end]),
1348                    ],
1349                ),
1350            ),
1351        );
1352
1353        let tree = parse_one(&g, "{ a: 1 }").unwrap();
1354        let entries = tree.keyed_child_slot("entries").expect("slot bound");
1355        assert_eq!(
1356            entries.len(),
1357            1,
1358            "the failed alternative's entry must be rolled back, not kept: {entries:?}"
1359        );
1360        assert_eq!(entries[0].0, "a");
1361    }
1362
1363    #[test]
1364    fn keyed_entry_outside_a_node_drops_the_entry() {
1365        let ids = IdGen::new();
1366        // No enclosing Node scope, so there is nowhere to bind the
1367        // pair. Documented as a silent drop, matching how a stray
1368        // `Field` behaves; pinned here so the behaviour is a decision
1369        // rather than an accident.
1370        let g = one_rule_grammar(
1371            &ids,
1372            "start",
1373            seq(
1374                &ids,
1375                vec![
1376                    keyed_entry(
1377                        &ids,
1378                        "entries",
1379                        token(&ids, "%ident"),
1380                        keyed_leaf_value(&ids),
1381                    ),
1382                    node(&ids, "Env", token(&ids, "!")),
1383                ],
1384            ),
1385        );
1386        let tree = parse_one(&g, "a: 1 !").unwrap();
1387        assert_eq!(tree.variant, "Env");
1388        assert!(
1389            tree.keyed_children.is_empty(),
1390            "a keyed entry with no enclosing Node has nowhere to land: {:?}",
1391            tree.keyed_children
1392        );
1393    }
1394
1395    #[test]
1396    fn literal_token_and_wrap_node() {
1397        let ids = IdGen::new();
1398        // start = Node "K" { Field "kw" "let" }
1399        let g = one_rule_grammar(
1400            &ids,
1401            "start",
1402            node(&ids, "K", field(&ids, "kw", token(&ids, "let"))),
1403        );
1404        let tree = parse_one(&g, "let").unwrap();
1405        assert_eq!(tree.variant, "K");
1406        assert_eq!(tree.fields.len(), 1);
1407        assert_eq!(tree.fields[0].0, "kw");
1408        match &tree.fields[0].1 {
1409            RawValue::Text(t) => assert_eq!(t, "let"),
1410            _ => panic!("expected text"),
1411        }
1412    }
1413
1414    #[test]
1415    fn keyword_guard_blocks_prefix_match() {
1416        let ids = IdGen::new();
1417        // Plain literal `"let"` would greedily eat the prefix of
1418        // "letme"; `%kw:let` applies the word-boundary guard.
1419        let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1420        let err = parse_one(&g, "letme").unwrap_err();
1421        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1422
1423        // And the same pattern DOES match when the boundary is honoured.
1424        let g2 = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1425        assert!(parse_one(&g2, "let ").is_ok());
1426    }
1427
1428    #[test]
1429    fn plain_literal_has_no_word_boundary_guard() {
1430        let ids = IdGen::new();
1431        // Plain "a" matches even when followed by another word char —
1432        // it's the grammar author's job to sequence more tokens after.
1433        let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "a")));
1434        let err = parse_one(&g, "ab").unwrap_err();
1435        // The literal matched; trailing "b" tripped the EOF check.
1436        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1437        assert!(
1438            err.diagnostics[0].message.contains("trailing"),
1439            "{}",
1440            err.diagnostics[0].message
1441        );
1442    }
1443
1444    #[test]
1445    fn ident_and_int_classes() {
1446        let ids = IdGen::new();
1447        let g = one_rule_grammar(
1448            &ids,
1449            "s",
1450            node(&ids, "Var", field(&ids, "name", token(&ids, "%ident"))),
1451        );
1452        let t = parse_one(&g, "foo_bar1").unwrap();
1453        assert_eq!(t.variant, "Var");
1454        match &t.fields[0].1 {
1455            RawValue::Text(v) => assert_eq!(v, "foo_bar1"),
1456            _ => panic!(),
1457        }
1458
1459        let g2 = one_rule_grammar(
1460            &ids,
1461            "s",
1462            node(&ids, "N", field(&ids, "v", token(&ids, "%int"))),
1463        );
1464        let t2 = parse_one(&g2, "-42").unwrap();
1465        match &t2.fields[0].1 {
1466            RawValue::Text(v) => assert_eq!(v, "-42"),
1467            _ => panic!(),
1468        }
1469    }
1470
1471    // -- Whitespace --
1472
1473    #[test]
1474    fn implicit_ws_skip_before_tokens_and_at_boundaries() {
1475        let ids = IdGen::new();
1476        // Node "P" { Field "a" %int Field "b" %int }
1477        let body = seq(
1478            &ids,
1479            vec![
1480                field(&ids, "a", token(&ids, "%int")),
1481                field(&ids, "b", token(&ids, "%int")),
1482            ],
1483        );
1484        let g = one_rule_grammar(&ids, "s", node(&ids, "P", body));
1485        let t = parse_one(&g, "  3   7 ").unwrap();
1486        assert_eq!(t.fields.len(), 2);
1487        assert_eq!(t.fields[0].0, "a");
1488        assert_eq!(t.fields[1].0, "b");
1489    }
1490
1491    // -- PEG semantics (parser-design §3.5) --
1492
1493    #[test]
1494    fn choice_commits_on_first_match() {
1495        let ids = IdGen::new();
1496        // Choice("a" -> A | "ab" -> B). Input "ab" — PEG commits to
1497        // first alt, "a" matches (leaves "b" behind), then EOF check
1498        // fails on the trailing "b".
1499        let alt_a = node(&ids, "A", token(&ids, "a"));
1500        let alt_ab = node(&ids, "B", token(&ids, "ab"));
1501        let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_a, alt_ab]));
1502        let err = parse_one(&g, "ab").unwrap_err();
1503        // Should complain about trailing "b", not attempt the second
1504        // alt.
1505        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1506        assert!(
1507            err.diagnostics[0].message.contains("byte 1"),
1508            "{}",
1509            err.diagnostics[0].message
1510        );
1511    }
1512
1513    #[test]
1514    fn failed_alt_restores_position() {
1515        let ids = IdGen::new();
1516        // Choice("abc" | "a") on "ab": first fails (partial), position
1517        // must restore, second succeeds on "a"; trailing "b" then fails
1518        // EOF. Confirms no partial-consume leak.
1519        let alt_abc = node(&ids, "L", token(&ids, "abc"));
1520        let alt_a = node(&ids, "S", token(&ids, "a"));
1521        let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_abc, alt_a]));
1522        let err = parse_one(&g, "ab").unwrap_err();
1523        // Trailing "b" at byte 1.
1524        assert!(
1525            err.diagnostics[0].message.contains("byte 1"),
1526            "{}",
1527            err.diagnostics[0].message
1528        );
1529    }
1530
1531    #[test]
1532    fn repeat_is_greedy_and_no_backtrack_into_completed() {
1533        let ids = IdGen::new();
1534        // Seq( Repeat("a", 0..*), "a" ). Repeat eats all a's greedily;
1535        // trailing "a" required by the Seq item then fails. If Repeat
1536        // gave back one iteration, we'd succeed — the test proves it
1537        // does not.
1538        let g = one_rule_grammar(
1539            &ids,
1540            "s",
1541            node(
1542                &ids,
1543                "N",
1544                seq(
1545                    &ids,
1546                    vec![repeat(&ids, token(&ids, "a"), 0, None), token(&ids, "a")],
1547                ),
1548            ),
1549        );
1550        let err = parse_one(&g, "aaa").unwrap_err();
1551        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1552    }
1553
1554    #[test]
1555    fn repeat_min_enforced() {
1556        let ids = IdGen::new();
1557        let g = one_rule_grammar(
1558            &ids,
1559            "s",
1560            node(&ids, "N", repeat(&ids, token(&ids, "a"), 2, None)),
1561        );
1562        // Only one "a" — Repeat min=2 fails.
1563        assert!(parse_one(&g, "a").is_err());
1564        // Two "a"s — succeeds.
1565        assert!(parse_one(&g, "aa").is_ok());
1566    }
1567
1568    // -- Farthest failure --
1569
1570    #[test]
1571    fn farthest_failure_carries_position_and_expected_set() {
1572        let ids = IdGen::new();
1573        // Seq("let", "x", "="). On input "let x !": we match "let"
1574        // (0..3), skip ws to 4, match "x" (4..5), skip ws to 6, expect
1575        // "=" at 6 but get "!". Farthest-failure position = 6, expected
1576        // = ["="].
1577        let g = one_rule_grammar(
1578            &ids,
1579            "s",
1580            node(
1581                &ids,
1582                "N",
1583                seq(
1584                    &ids,
1585                    vec![token(&ids, "let"), token(&ids, "x"), token(&ids, "=")],
1586                ),
1587            ),
1588        );
1589        let err = parse_one(&g, "let x !").unwrap_err();
1590        let msg = &err.diagnostics[0].message;
1591        assert!(msg.contains("byte 6"), "{msg}");
1592        assert!(msg.contains("`=`"), "{msg}");
1593    }
1594
1595    // -- Termination guards --
1596
1597    #[test]
1598    fn left_recursion_is_detected_at_runtime() {
1599        let ids = IdGen::new();
1600        // r <- r "a" — direct left recursion. Should trip the guard
1601        // rather than hang.
1602        let r = rule(
1603            &ids,
1604            "r",
1605            seq(&ids, vec![rule_ref(&ids, "r"), token(&ids, "a")]),
1606        );
1607        let g = Grammar::new(vec![r], "r");
1608        let err = g.parse("aaa").unwrap_err();
1609        assert_eq!(err.diagnostics[0].code, codes::LEFT_RECURSION);
1610    }
1611
1612    #[test]
1613    fn unknown_rule_ref_is_diagnosed() {
1614        let ids = IdGen::new();
1615        let r = rule(&ids, "start", rule_ref(&ids, "missing"));
1616        let g = Grammar::new(vec![r], "start");
1617        let err = g.parse("").unwrap_err();
1618        assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1619    }
1620
1621    #[test]
1622    fn unknown_rule_ref_suggests_declared_rule() {
1623        // A typo of a declared rule name should surface the correct
1624        // name via the built-in Levenshtein suggester.
1625        let ids = IdGen::new();
1626        let start = rule(&ids, "start", rule_ref(&ids, "helo"));
1627        let target = rule(&ids, "hello", token(&ids, "hi"));
1628        let g = Grammar::new(vec![start, target], "start");
1629        let err = g.parse("hi").unwrap_err();
1630        assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1631        assert!(
1632            err.diagnostics[0].message.contains("did you mean")
1633                && err.diagnostics[0].message.contains("hello"),
1634            "expected hint, got: {}",
1635            err.diagnostics[0].message
1636        );
1637    }
1638
1639    #[test]
1640    fn unknown_start_rule_is_diagnosed() {
1641        let ids = IdGen::new();
1642        let r = rule(&ids, "other", token(&ids, "x"));
1643        let g = Grammar::new(vec![r], "start");
1644        let err = g.parse("x").unwrap_err();
1645        assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1646    }
1647
1648    #[test]
1649    fn unknown_start_rule_suggests_declared_rule() {
1650        let ids = IdGen::new();
1651        let r = rule(&ids, "start", token(&ids, "x"));
1652        let g = Grammar::new(vec![r], "strat");
1653        let err = g.parse("x").unwrap_err();
1654        assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1655        assert!(
1656            err.diagnostics[0].message.contains("did you mean")
1657                && err.diagnostics[0].message.contains("start"),
1658            "expected hint, got: {}",
1659            err.diagnostics[0].message
1660        );
1661    }
1662
1663    #[test]
1664    fn nullable_repeat_body_below_min_is_rejected() {
1665        let ids = IdGen::new();
1666        // Repeat body is a Field with no productive body — matches
1667        // empty. min=1 forces a failure rather than a hang.
1668        let empty_body = seq(&ids, vec![]);
1669        let g = one_rule_grammar(
1670            &ids,
1671            "s",
1672            node(&ids, "N", repeat(&ids, empty_body, 1, None)),
1673        );
1674        let err = g.parse("").unwrap_err();
1675        assert_eq!(err.diagnostics[0].code, codes::NULLABLE_REPEAT);
1676    }
1677}