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