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//! Two 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//!
46//! # Whitespace policy (parser-design §3.5, decided in G-2)
47//!
48//! **Implicit skip of `[ \t\r\n]*` before every [`Peg::Token`]** (except
49//! the `%ws` class itself, which matches one-or-more whitespace
50//! literally). No per-rule opt-out yet — deferred until a concrete
51//! consumer demands it. Leading and trailing whitespace at the input
52//! boundary are also skipped by [`Grammar::parse`].
53//!
54//! # Token pattern language
55//!
56//! [`Peg::Token`]'s `pat` string is either a literal or a class:
57//!
58//! - `%ident` — `[A-Za-z_][A-Za-z_0-9]*`
59//! - `%int`   — `-?[0-9]+`
60//! - `%str`   — a double-quoted string literal with `\"` `\\` `\n`
61//!   `\t` `\r` escapes. Unlike every other token, the production it
62//!   contributes is the **decoded inner content** (quotes stripped,
63//!   escapes resolved), so a `Field` wrapping `%str` binds the string
64//!   value directly.
65//! - `%ws`    — `[ \t\r\n]+` (skip is disabled for this class)
66//! - `%kw:<word>` — literal `<word>` with a word-boundary guard: the
67//!   byte immediately after the match must not be a word char. This is
68//!   how you write reserved words like `let` / `in` without swallowing
69//!   the prefix of identifiers such as `letme`.
70//! - anything else — plain literal match with no boundary guard. Use
71//!   this for punctuation like `+`, `*`, `(`, `)`, `=`.
72
73#![allow(clippy::result_unit_err)]
74
75use crate::{BuildError, Diagnostic, ParseTree, RawValue, Span};
76use dsl_kit_core::NodeId;
77use dsl_kit_macros::{DslNode as DslNodeDerive, DslSchema as DslSchemaDerive};
78use std::collections::{BTreeSet, HashMap};
79
80// ---------------------------------------------------------------------------
81// Peg AST
82// ---------------------------------------------------------------------------
83
84/// PEG grammar AST.
85///
86/// One value per primitive; the [`Grammar`] wrapper carries the flat
87/// list of rules and the start-rule name.
88#[derive(Debug, Clone, DslNodeDerive, DslSchemaDerive)]
89pub enum Peg {
90    /// Named rule definition. Top-level entries in
91    /// [`Grammar::rules`] must be `Rule`s; nested `Rule` variants are
92    /// legal but unusual and are treated as anonymous scopes by the
93    /// interpreter (they run `body` and forward its productions).
94    Rule {
95        /// Stable node id.
96        id: NodeId,
97        /// Rule name (referenced by [`Peg::RuleRef`]).
98        name: String,
99        /// Rule body.
100        body: Box<Peg>,
101    },
102    /// Sequence — every item must succeed in order.
103    Seq {
104        /// Stable node id.
105        id: NodeId,
106        /// Ordered sequence items.
107        items: Vec<Peg>,
108    },
109    /// Ordered choice — first alternative that succeeds commits.
110    Choice {
111        /// Stable node id.
112        id: NodeId,
113        /// Alternatives, tried left to right.
114        alts: Vec<Peg>,
115    },
116    /// Greedy repetition — runs `body` between `min` and `max` times.
117    Repeat {
118        /// Stable node id.
119        id: NodeId,
120        /// Repeated body.
121        body: Box<Peg>,
122        /// Minimum successful iterations (inclusive).
123        min: u32,
124        /// Maximum successful iterations (inclusive); `None` = unbounded.
125        max: Option<u32>,
126    },
127    /// Reference to another rule by name.
128    RuleRef {
129        /// Stable node id.
130        id: NodeId,
131        /// Referenced rule name.
132        name: String,
133    },
134    /// Terminal — matches a literal string or a small character class
135    /// (see the module docs' token pattern language).
136    Token {
137        /// Stable node id.
138        id: NodeId,
139        /// Token pattern (literal or `%ident` / `%int` / `%str` /
140        /// `%ws` / `%kw:<word>`).
141        pat: String,
142    },
143    /// Opens a `ParseTree` capture scope with the given `variant` name.
144    Node {
145        /// Stable node id.
146        id: NodeId,
147        /// Variant name on the produced `ParseTree`.
148        variant: String,
149        /// Scope body.
150        body: Box<Peg>,
151    },
152    /// Captures body's productions and binds them under `name` on the
153    /// enclosing [`Peg::Node`] scope.
154    Field {
155        /// Stable node id.
156        id: NodeId,
157        /// Field or child-slot name on the enclosing Node.
158        name: String,
159        /// Capture body.
160        body: Box<Peg>,
161    },
162}
163
164// ---------------------------------------------------------------------------
165// Grammar wrapper
166// ---------------------------------------------------------------------------
167
168/// A PEG grammar: a flat list of top-level [`Peg::Rule`]s plus the name
169/// of the start rule.
170///
171/// Kept as a plain wrapper struct deriving nothing so the `Peg` enum
172/// stays clean (parser-design §3.4).
173#[derive(Debug, Clone)]
174pub struct Grammar {
175    /// Top-level rules. Every element should be a [`Peg::Rule`]
176    /// variant — the interpreter looks up rules by name against this
177    /// list.
178    pub rules: Vec<Peg>,
179    /// Name of the start rule.
180    pub start: String,
181}
182
183impl Grammar {
184    /// Constructs a new [`Grammar`].
185    pub fn new(rules: Vec<Peg>, start: impl Into<String>) -> Self {
186        Self {
187            rules,
188            start: start.into(),
189        }
190    }
191
192    /// Parses `input` against this grammar.
193    ///
194    /// On success returns a single top-level [`ParseTree`] (produced by
195    /// exactly one [`Peg::Node`] reached from the start rule).
196    ///
197    /// On failure returns a [`BuildError`] whose diagnostics carry the
198    /// farthest-failure position + expected set, formatted in the shared
199    /// dialect (`{ severity, code, message, location }`).
200    pub fn parse(&self, input: &str) -> Result<ParseTree, BuildError> {
201        let mut rules_by_name: HashMap<&str, &Peg> = HashMap::new();
202        for r in &self.rules {
203            if let Peg::Rule { name, .. } = r {
204                rules_by_name.insert(name.as_str(), r);
205            }
206        }
207        let start_rule = rules_by_name
208            .get(self.start.as_str())
209            .copied()
210            .ok_or_else(|| {
211                BuildError::single(Diagnostic::error(
212                    codes::UNKNOWN_RULE,
213                    format!("start rule `{}` is not defined in the grammar", self.start),
214                ))
215            })?;
216
217        let mut interp = Interpreter::new(input, rules_by_name);
218        // Skip leading whitespace at the input boundary.
219        interp.skip_ws();
220        // Push the top-level sink.
221        interp.sink_stack.push(ActiveSink::Top(TopSink::default()));
222
223        match interp.run_peg(start_rule) {
224            Ok(()) => {}
225            Err(()) => {
226                if let Some(fatal) = interp.fatal_error.take() {
227                    return Err(BuildError::single(fatal));
228                }
229                return Err(BuildError::single(interp.expected_diagnostic()));
230            }
231        }
232
233        // Trailing whitespace + EOF check.
234        interp.skip_ws();
235        if interp.pos != input.len() {
236            // Try to attribute to the farthest expected set if we have
237            // one at/after this position; otherwise raw "trailing input".
238            let diag = if interp.farthest_pos >= interp.pos && !interp.farthest_expected.is_empty()
239            {
240                interp.expected_diagnostic()
241            } else {
242                Diagnostic::error(
243                    codes::UNEXPECTED,
244                    format!("unexpected trailing input at byte {}", interp.pos),
245                )
246                .with_span(Some(Span::new(interp.pos, input.len())))
247            };
248            return Err(BuildError::single(diag));
249        }
250
251        let top = match interp.sink_stack.pop() {
252            Some(ActiveSink::Top(t)) => t,
253            _ => unreachable!("top sink must be present"),
254        };
255        top.tree.ok_or_else(|| {
256            BuildError::single(Diagnostic::error(
257                codes::NO_TOP_TREE,
258                format!(
259                    "parse succeeded but produced no top-level `Node`; \
260                     start rule `{}` must reach exactly one `Peg::Node`",
261                    self.start
262                ),
263            ))
264        })
265    }
266}
267
268// ---------------------------------------------------------------------------
269// Diagnostic codes
270// ---------------------------------------------------------------------------
271
272/// Diagnostic codes emitted by the PEG interpreter.
273pub mod codes {
274    /// Input did not match at the farthest failure position; message
275    /// carries the expected set.
276    pub const UNEXPECTED: &str = "dsl_kit::parse::peg::unexpected";
277    /// [`super::Peg::RuleRef`] pointed to a rule name not present in
278    /// [`super::Grammar::rules`], or [`super::Grammar::start`] itself is
279    /// unresolved.
280    pub const UNKNOWN_RULE: &str = "dsl_kit::parse::peg::unknown_rule";
281    /// A rule was re-entered at the same input position without any
282    /// progress — indicates left recursion. G-3's `GrammarCheck` will
283    /// catch this statically; the runtime guard is a backstop that
284    /// errors out rather than hanging.
285    pub const LEFT_RECURSION: &str = "dsl_kit::parse::peg::left_recursion";
286    /// A [`super::Peg::Repeat`] iteration succeeded without consuming
287    /// input. The interpreter breaks the loop (per §3.5 termination
288    /// guarantee); this diagnostic is attached when the `min` bound is
289    /// also not yet met, turning the situation into a hard failure.
290    pub const NULLABLE_REPEAT: &str = "dsl_kit::parse::peg::nullable_repeat";
291    /// Parse succeeded but the start rule never reached a
292    /// [`super::Peg::Node`], so there is no top-level `ParseTree`.
293    pub const NO_TOP_TREE: &str = "dsl_kit::parse::peg::no_top_tree";
294}
295
296// ---------------------------------------------------------------------------
297// Interpreter
298// ---------------------------------------------------------------------------
299
300/// A raw production captured inside a [`FieldSink`]. Text comes from
301/// [`Peg::Token`] matches, trees from [`Peg::Node`] captures. The span
302/// on `Text` is retained for future span-carrying `RawValue::Text`
303/// support (post-G-2).
304#[derive(Debug, Clone)]
305enum Production {
306    #[allow(dead_code)] // span kept for post-G-2 span-carrying Text values
307    Text(String, Span),
308    Tree(ParseTree),
309}
310
311#[derive(Debug, Default, Clone)]
312struct FieldSink {
313    productions: Vec<Production>,
314}
315
316#[derive(Debug, Default, Clone)]
317struct NodeSink {
318    fields: Vec<(String, RawValue)>,
319    children: Vec<(String, Vec<ParseTree>)>,
320}
321
322#[derive(Debug, Default, Clone)]
323struct TopSink {
324    tree: Option<ParseTree>,
325}
326
327/// The active-sink stack entry. Only the top sink is ever mutated by
328/// productions.
329#[derive(Debug, Clone)]
330enum ActiveSink {
331    Top(TopSink),
332    Node(NodeSink),
333    Field(FieldSink),
334}
335
336struct Interpreter<'g, 'i> {
337    input: &'i str,
338    pos: usize,
339    rules_by_name: HashMap<&'g str, &'g Peg>,
340    sink_stack: Vec<ActiveSink>,
341    // Farthest-failure tracking (parser-design §3.5).
342    farthest_pos: usize,
343    farthest_expected: BTreeSet<String>,
344    // Left-recursion guard: (rule name, position at entry).
345    call_stack: Vec<(&'g str, usize)>,
346    // Fatal errors (unknown rule / left recursion) — trip Err(()) and
347    // short-circuit past normal recovery.
348    fatal_error: Option<Diagnostic>,
349}
350
351impl<'g, 'i> Interpreter<'g, 'i> {
352    fn new(input: &'i str, rules_by_name: HashMap<&'g str, &'g Peg>) -> Self {
353        Self {
354            input,
355            pos: 0,
356            rules_by_name,
357            sink_stack: Vec::new(),
358            farthest_pos: 0,
359            farthest_expected: BTreeSet::new(),
360            call_stack: Vec::new(),
361            fatal_error: None,
362        }
363    }
364
365    // -----------------------------------------------------------------------
366    // Sink helpers
367    // -----------------------------------------------------------------------
368
369    fn top_sink_snapshot(&self) -> ActiveSink {
370        self.sink_stack
371            .last()
372            .cloned()
373            .expect("sink stack has at least the top-level entry during parse")
374    }
375
376    fn restore_top_sink(&mut self, snap: ActiveSink) {
377        let last = self
378            .sink_stack
379            .last_mut()
380            .expect("sink stack has at least the top-level entry during parse");
381        *last = snap;
382    }
383
384    fn contribute_text(&mut self, text: String, span: Span) {
385        match self.sink_stack.last_mut() {
386            Some(ActiveSink::Field(s)) => s.productions.push(Production::Text(text, span)),
387            _ => {
388                // Discard — Token outside a Field is syntactic (like "+" or "let").
389            }
390        }
391    }
392
393    fn contribute_tree(&mut self, tree: ParseTree) {
394        match self.sink_stack.last_mut() {
395            Some(ActiveSink::Field(s)) => s.productions.push(Production::Tree(tree)),
396            Some(ActiveSink::Node(_)) => {
397                // Nested Node not wrapped in Field — silently discarded
398                // at runtime. G-3's GrammarCheck should flag such
399                // grammars as author bugs.
400            }
401            Some(ActiveSink::Top(t)) => {
402                // Top-level result: latest wins (there should be exactly
403                // one; a subsequent one is unusual but harmless).
404                t.tree = Some(tree);
405            }
406            None => unreachable!("sink stack must not be empty during parse"),
407        }
408    }
409
410    fn contribute_field(&mut self, name: &str, productions: Vec<Production>) {
411        if productions.is_empty() {
412            return;
413        }
414        let all_text = productions
415            .iter()
416            .all(|p| matches!(p, Production::Text(..)));
417        let all_tree = productions
418            .iter()
419            .all(|p| matches!(p, Production::Tree(..)));
420
421        let Some(ActiveSink::Node(node_sink)) = self.sink_stack.last_mut() else {
422            // Field outside a Node — silently ignored at runtime.
423            return;
424        };
425
426        if all_text {
427            let joined: String = productions
428                .iter()
429                .filter_map(|p| match p {
430                    Production::Text(t, _) => Some(t.as_str()),
431                    _ => None,
432                })
433                .collect();
434            node_sink
435                .fields
436                .push((name.to_string(), RawValue::Text(joined)));
437            return;
438        }
439        if all_tree {
440            let trees: Vec<ParseTree> = productions
441                .into_iter()
442                .filter_map(|p| match p {
443                    Production::Tree(t) => Some(t),
444                    _ => None,
445                })
446                .collect();
447            if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
448                slot.1.extend(trees);
449            } else {
450                node_sink.children.push((name.to_string(), trees));
451            }
452            return;
453        }
454        // Mixed: keep tree productions, drop texts (grammar bug — G-3
455        // GrammarCheck will flag).
456        let trees: Vec<ParseTree> = productions
457            .into_iter()
458            .filter_map(|p| match p {
459                Production::Tree(t) => Some(t),
460                _ => None,
461            })
462            .collect();
463        if trees.is_empty() {
464            return;
465        }
466        if let Some(slot) = node_sink.children.iter_mut().find(|(n, _)| n == name) {
467            slot.1.extend(trees);
468        } else {
469            node_sink.children.push((name.to_string(), trees));
470        }
471    }
472
473    // -----------------------------------------------------------------------
474    // Farthest-failure helpers
475    // -----------------------------------------------------------------------
476
477    fn expected(&mut self, what: impl Into<String>) {
478        if self.pos > self.farthest_pos {
479            self.farthest_pos = self.pos;
480            self.farthest_expected.clear();
481            self.farthest_expected.insert(what.into());
482        } else if self.pos == self.farthest_pos {
483            self.farthest_expected.insert(what.into());
484        }
485    }
486
487    fn expected_diagnostic(&self) -> Diagnostic {
488        let expected: Vec<String> = self.farthest_expected.iter().cloned().collect();
489        let expected_msg = if expected.is_empty() {
490            "<unknown>".to_string()
491        } else {
492            expected
493                .iter()
494                .map(|e| format!("`{e}`"))
495                .collect::<Vec<_>>()
496                .join(" | ")
497        };
498        let end = self.input.len().min(self.farthest_pos + 1);
499        let got_msg = if self.farthest_pos >= self.input.len() {
500            "end of input".to_string()
501        } else {
502            let bytes = self.input.as_bytes();
503            // Grab a small snippet — up to 8 bytes — to help the reader.
504            let snip_end = self.input.len().min(self.farthest_pos + 8);
505            let snip =
506                std::str::from_utf8(&bytes[self.farthest_pos..snip_end]).unwrap_or("<non-utf8>");
507            format!("`{}`", snip)
508        };
509        Diagnostic::error(
510            codes::UNEXPECTED,
511            format!(
512                "expected {expected_msg} at byte {}, got {got_msg}",
513                self.farthest_pos
514            ),
515        )
516        .with_span(Some(Span::new(self.farthest_pos, end)))
517    }
518
519    // -----------------------------------------------------------------------
520    // PEG dispatch
521    // -----------------------------------------------------------------------
522
523    fn run_peg(&mut self, peg: &'g Peg) -> Result<(), ()> {
524        match peg {
525            Peg::Rule { body, .. } => self.run_peg(body),
526            Peg::Seq { items, .. } => {
527                for item in items {
528                    self.run_peg(item)?;
529                }
530                Ok(())
531            }
532            Peg::Choice { alts, .. } => self.run_choice(alts),
533            Peg::Repeat { body, min, max, .. } => self.run_repeat(body, *min, *max),
534            Peg::RuleRef { name, .. } => self.run_rule_ref(name),
535            Peg::Token { pat, .. } => self.match_token(pat),
536            Peg::Node { variant, body, .. } => self.run_node(variant, body),
537            Peg::Field { name, body, .. } => self.run_field(name, body),
538        }
539    }
540
541    fn run_choice(&mut self, alts: &'g [Peg]) -> Result<(), ()> {
542        let start_pos = self.pos;
543        let saved = self.top_sink_snapshot();
544        for alt in alts {
545            self.pos = start_pos;
546            self.restore_top_sink(saved.clone());
547            if self.fatal_error.is_some() {
548                return Err(());
549            }
550            if self.run_peg(alt).is_ok() {
551                return Ok(());
552            }
553            if self.fatal_error.is_some() {
554                return Err(());
555            }
556        }
557        self.pos = start_pos;
558        self.restore_top_sink(saved);
559        Err(())
560    }
561
562    fn run_repeat(&mut self, body: &'g Peg, min: u32, max: Option<u32>) -> Result<(), ()> {
563        let mut count: u32 = 0;
564        loop {
565            if let Some(mx) = max
566                && count >= mx
567            {
568                break;
569            }
570            let saved_pos = self.pos;
571            let saved_sink = self.top_sink_snapshot();
572            match self.run_peg(body) {
573                Ok(()) => {
574                    if self.pos == saved_pos {
575                        // Nullable-body iteration — break rather than
576                        // hang. GrammarCheck should reject grammars that
577                        // permit this, so the interpreter's job is
578                        // termination, not diagnosis.
579                        if count < min {
580                            self.fatal_error = Some(
581                                Diagnostic::error(
582                                    codes::NULLABLE_REPEAT,
583                                    "repeat body succeeded without consuming input".to_string(),
584                                )
585                                .with_span(Some(Span::new(saved_pos, saved_pos))),
586                            );
587                            return Err(());
588                        }
589                        break;
590                    }
591                    count += 1;
592                }
593                Err(()) => {
594                    if self.fatal_error.is_some() {
595                        return Err(());
596                    }
597                    self.pos = saved_pos;
598                    self.restore_top_sink(saved_sink);
599                    break;
600                }
601            }
602        }
603        if count < min { Err(()) } else { Ok(()) }
604    }
605
606    fn run_rule_ref(&mut self, name: &str) -> Result<(), ()> {
607        let Some(&rule) = self.rules_by_name.get(name) else {
608            self.fatal_error = Some(
609                Diagnostic::error(
610                    codes::UNKNOWN_RULE,
611                    format!("reference to undefined rule `{name}`"),
612                )
613                .with_span(Some(Span::new(self.pos, self.pos))),
614            );
615            return Err(());
616        };
617        // Look up by pointer so we keep the &'g lifetime attached.
618        let rule_name: &'g str = self
619            .rules_by_name
620            .keys()
621            .copied()
622            .find(|k| *k == name)
623            .expect("just found");
624        // Left-recursion guard: rule re-entered at the same position
625        // without any progress.
626        if self
627            .call_stack
628            .iter()
629            .any(|(n, p)| *n == rule_name && *p == self.pos)
630        {
631            self.fatal_error = Some(
632                Diagnostic::error(
633                    codes::LEFT_RECURSION,
634                    format!(
635                        "left recursion detected: rule `{name}` re-entered at byte {}",
636                        self.pos
637                    ),
638                )
639                .with_span(Some(Span::new(self.pos, self.pos))),
640            );
641            return Err(());
642        }
643        self.call_stack.push((rule_name, self.pos));
644        let r = self.run_peg(rule);
645        self.call_stack.pop();
646        r
647    }
648
649    fn run_node(&mut self, variant: &str, body: &'g Peg) -> Result<(), ()> {
650        let start_pos = self.pos;
651        self.sink_stack.push(ActiveSink::Node(NodeSink::default()));
652        let body_result = self.run_peg(body);
653        let node_sink = match self.sink_stack.pop() {
654            Some(ActiveSink::Node(s)) => s,
655            _ => unreachable!("balanced push/pop of NodeSink"),
656        };
657        body_result?;
658        let end_pos = self.pos;
659        let tree = ParseTree {
660            variant: variant.to_string(),
661            fields: node_sink.fields,
662            children: node_sink.children,
663            span: Some(Span::new(start_pos, end_pos)),
664        };
665        self.contribute_tree(tree);
666        Ok(())
667    }
668
669    fn run_field(&mut self, name: &str, body: &'g Peg) -> Result<(), ()> {
670        self.sink_stack
671            .push(ActiveSink::Field(FieldSink::default()));
672        let body_result = self.run_peg(body);
673        let field_sink = match self.sink_stack.pop() {
674            Some(ActiveSink::Field(s)) => s,
675            _ => unreachable!("balanced push/pop of FieldSink"),
676        };
677        body_result?;
678        self.contribute_field(name, field_sink.productions);
679        Ok(())
680    }
681
682    // -----------------------------------------------------------------------
683    // Token matching
684    // -----------------------------------------------------------------------
685
686    fn match_token(&mut self, pat: &str) -> Result<(), ()> {
687        if pat != "%ws" {
688            self.skip_ws();
689        }
690        let start = self.pos;
691        if pat == "%str" {
692            // Special-cased because the contributed production is the
693            // decoded inner content, not the matched source slice.
694            return match self.match_str() {
695                Some(decoded) => {
696                    let end = self.pos;
697                    self.contribute_text(decoded, Span::new(start, end));
698                    Ok(())
699                }
700                None => {
701                    self.expected(pat);
702                    self.pos = start;
703                    Err(())
704                }
705            };
706        }
707        let ok = if pat == "%ident" {
708            self.match_ident()
709        } else if pat == "%int" {
710            self.match_int()
711        } else if pat == "%ws" {
712            self.match_ws_required()
713        } else if let Some(word) = pat.strip_prefix("%kw:") {
714            self.match_keyword(word)
715        } else {
716            self.match_literal(pat)
717        };
718        if ok {
719            let end = self.pos;
720            let text = self.input[start..end].to_string();
721            self.contribute_text(text, Span::new(start, end));
722            Ok(())
723        } else {
724            // Restore pos (in case skip_ws advanced but match failed —
725            // farthest-failure position is the *post-skip* position,
726            // which is the semantic failure spot).
727            self.expected(pat);
728            self.pos = start;
729            Err(())
730        }
731    }
732
733    fn skip_ws(&mut self) {
734        let bytes = self.input.as_bytes();
735        while let Some(&c) = bytes.get(self.pos) {
736            if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
737                self.pos += 1;
738            } else {
739                break;
740            }
741        }
742    }
743
744    fn match_ident(&mut self) -> bool {
745        let bytes = self.input.as_bytes();
746        match bytes.get(self.pos) {
747            Some(&c) if is_ident_start(c) => self.pos += 1,
748            _ => return false,
749        }
750        while let Some(&c) = bytes.get(self.pos) {
751            if is_ident_cont(c) {
752                self.pos += 1;
753            } else {
754                break;
755            }
756        }
757        true
758    }
759
760    fn match_int(&mut self) -> bool {
761        let bytes = self.input.as_bytes();
762        let mut p = self.pos;
763        if bytes.get(p) == Some(&b'-') {
764            p += 1;
765        }
766        let digit_start = p;
767        while let Some(&c) = bytes.get(p) {
768            if c.is_ascii_digit() {
769                p += 1;
770            } else {
771                break;
772            }
773        }
774        if p > digit_start {
775            self.pos = p;
776            true
777        } else {
778            false
779        }
780    }
781
782    /// Matches a double-quoted string literal and returns the decoded
783    /// inner content. `None` on no opening quote, an unterminated
784    /// literal, or an unknown escape.
785    fn match_str(&mut self) -> Option<String> {
786        let rest = &self.input[self.pos..];
787        let mut chars = rest.char_indices();
788        match chars.next() {
789            Some((_, '"')) => {}
790            _ => return None,
791        }
792        let mut out = String::new();
793        while let Some((i, c)) = chars.next() {
794            match c {
795                '"' => {
796                    self.pos += i + 1;
797                    return Some(out);
798                }
799                '\\' => match chars.next() {
800                    Some((_, '"')) => out.push('"'),
801                    Some((_, '\\')) => out.push('\\'),
802                    Some((_, 'n')) => out.push('\n'),
803                    Some((_, 't')) => out.push('\t'),
804                    Some((_, 'r')) => out.push('\r'),
805                    _ => return None,
806                },
807                other => out.push(other),
808            }
809        }
810        None
811    }
812
813    fn match_ws_required(&mut self) -> bool {
814        let start = self.pos;
815        let bytes = self.input.as_bytes();
816        while let Some(&c) = bytes.get(self.pos) {
817            if matches!(c, b' ' | b'\t' | b'\n' | b'\r') {
818                self.pos += 1;
819            } else {
820                break;
821            }
822        }
823        self.pos > start
824    }
825
826    fn match_literal(&mut self, s: &str) -> bool {
827        let bytes = self.input.as_bytes();
828        let end = self.pos + s.len();
829        if end > bytes.len() {
830            return false;
831        }
832        if &bytes[self.pos..end] != s.as_bytes() {
833            return false;
834        }
835        self.pos = end;
836        true
837    }
838
839    fn match_keyword(&mut self, word: &str) -> bool {
840        let saved = self.pos;
841        if !self.match_literal(word) {
842            return false;
843        }
844        // Word-boundary guard: the byte after must not be a word char.
845        if let Some(&next) = self.input.as_bytes().get(self.pos)
846            && is_ident_cont(next)
847        {
848            self.pos = saved;
849            return false;
850        }
851        true
852    }
853}
854
855fn is_ident_start(c: u8) -> bool {
856    c.is_ascii_alphabetic() || c == b'_'
857}
858
859fn is_ident_cont(c: u8) -> bool {
860    c.is_ascii_alphanumeric() || c == b'_'
861}
862
863// ---------------------------------------------------------------------------
864// Convenience constructors (grammar authors build Peg values by hand
865// until G-4's meta-grammar; these helpers cut boilerplate).
866// ---------------------------------------------------------------------------
867
868use dsl_kit_core::IdGen;
869
870/// Builds a [`Peg::Rule`] node with a fresh id.
871pub fn rule(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
872    Peg::Rule {
873        id: ids.node(),
874        name: name.into(),
875        body: Box::new(body),
876    }
877}
878
879/// Builds a [`Peg::Seq`] node with a fresh id.
880pub fn seq(ids: &IdGen, items: Vec<Peg>) -> Peg {
881    Peg::Seq {
882        id: ids.node(),
883        items,
884    }
885}
886
887/// Builds a [`Peg::Choice`] node with a fresh id.
888pub fn choice(ids: &IdGen, alts: Vec<Peg>) -> Peg {
889    Peg::Choice {
890        id: ids.node(),
891        alts,
892    }
893}
894
895/// Builds a [`Peg::Repeat`] node with a fresh id.
896pub fn repeat(ids: &IdGen, body: Peg, min: u32, max: Option<u32>) -> Peg {
897    Peg::Repeat {
898        id: ids.node(),
899        body: Box::new(body),
900        min,
901        max,
902    }
903}
904
905/// Builds a [`Peg::RuleRef`] node with a fresh id.
906pub fn rule_ref(ids: &IdGen, name: impl Into<String>) -> Peg {
907    Peg::RuleRef {
908        id: ids.node(),
909        name: name.into(),
910    }
911}
912
913/// Builds a [`Peg::Token`] node with a fresh id.
914pub fn token(ids: &IdGen, pat: impl Into<String>) -> Peg {
915    Peg::Token {
916        id: ids.node(),
917        pat: pat.into(),
918    }
919}
920
921/// Builds a [`Peg::Node`] capture node with a fresh id.
922pub fn node(ids: &IdGen, variant: impl Into<String>, body: Peg) -> Peg {
923    Peg::Node {
924        id: ids.node(),
925        variant: variant.into(),
926        body: Box::new(body),
927    }
928}
929
930/// Builds a [`Peg::Field`] capture node with a fresh id.
931pub fn field(ids: &IdGen, name: impl Into<String>, body: Peg) -> Peg {
932    Peg::Field {
933        id: ids.node(),
934        name: name.into(),
935        body: Box::new(body),
936    }
937}
938
939// ---------------------------------------------------------------------------
940// Tests
941// ---------------------------------------------------------------------------
942
943#[cfg(test)]
944mod tests {
945    use super::*;
946    use dsl_kit_core::IdGen;
947    use dsl_kit_schema::DslSchema;
948
949    // -- schema shape --
950
951    #[test]
952    fn peg_schema_lists_all_variants() {
953        let s = Peg::schema();
954        assert_eq!(s.name, "Peg");
955        let names: Vec<&str> = s.variants.iter().map(|v| v.name.as_str()).collect();
956        assert_eq!(
957            names,
958            vec![
959                "Rule", "Seq", "Choice", "Repeat", "RuleRef", "Token", "Node", "Field"
960            ]
961        );
962        let repeat = s.variant("Repeat").unwrap();
963        // body -> one child; min / max -> fields.
964        assert_eq!(repeat.children.len(), 1);
965        assert_eq!(repeat.children[0].name, "body");
966        let field_names: Vec<&str> = repeat.fields.iter().map(|f| f.name.as_str()).collect();
967        assert!(field_names.contains(&"min"));
968        assert!(field_names.contains(&"max"));
969    }
970
971    // -- Token matching --
972
973    fn parse_one(g: &Grammar, input: &str) -> Result<ParseTree, BuildError> {
974        g.parse(input)
975    }
976
977    fn one_rule_grammar(ids: &IdGen, start: &str, body: Peg) -> Grammar {
978        Grammar::new(vec![rule(ids, start, body)], start)
979    }
980
981    #[test]
982    fn literal_token_and_wrap_node() {
983        let ids = IdGen::new();
984        // start = Node "K" { Field "kw" "let" }
985        let g = one_rule_grammar(
986            &ids,
987            "start",
988            node(&ids, "K", field(&ids, "kw", token(&ids, "let"))),
989        );
990        let tree = parse_one(&g, "let").unwrap();
991        assert_eq!(tree.variant, "K");
992        assert_eq!(tree.fields.len(), 1);
993        assert_eq!(tree.fields[0].0, "kw");
994        match &tree.fields[0].1 {
995            RawValue::Text(t) => assert_eq!(t, "let"),
996            _ => panic!("expected text"),
997        }
998    }
999
1000    #[test]
1001    fn keyword_guard_blocks_prefix_match() {
1002        let ids = IdGen::new();
1003        // Plain literal `"let"` would greedily eat the prefix of
1004        // "letme"; `%kw:let` applies the word-boundary guard.
1005        let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1006        let err = parse_one(&g, "letme").unwrap_err();
1007        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1008
1009        // And the same pattern DOES match when the boundary is honoured.
1010        let g2 = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "%kw:let")));
1011        assert!(parse_one(&g2, "let ").is_ok());
1012    }
1013
1014    #[test]
1015    fn plain_literal_has_no_word_boundary_guard() {
1016        let ids = IdGen::new();
1017        // Plain "a" matches even when followed by another word char —
1018        // it's the grammar author's job to sequence more tokens after.
1019        let g = one_rule_grammar(&ids, "s", node(&ids, "K", token(&ids, "a")));
1020        let err = parse_one(&g, "ab").unwrap_err();
1021        // The literal matched; trailing "b" tripped the EOF check.
1022        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1023        assert!(
1024            err.diagnostics[0].message.contains("trailing"),
1025            "{}",
1026            err.diagnostics[0].message
1027        );
1028    }
1029
1030    #[test]
1031    fn ident_and_int_classes() {
1032        let ids = IdGen::new();
1033        let g = one_rule_grammar(
1034            &ids,
1035            "s",
1036            node(&ids, "Var", field(&ids, "name", token(&ids, "%ident"))),
1037        );
1038        let t = parse_one(&g, "foo_bar1").unwrap();
1039        assert_eq!(t.variant, "Var");
1040        match &t.fields[0].1 {
1041            RawValue::Text(v) => assert_eq!(v, "foo_bar1"),
1042            _ => panic!(),
1043        }
1044
1045        let g2 = one_rule_grammar(
1046            &ids,
1047            "s",
1048            node(&ids, "N", field(&ids, "v", token(&ids, "%int"))),
1049        );
1050        let t2 = parse_one(&g2, "-42").unwrap();
1051        match &t2.fields[0].1 {
1052            RawValue::Text(v) => assert_eq!(v, "-42"),
1053            _ => panic!(),
1054        }
1055    }
1056
1057    // -- Whitespace --
1058
1059    #[test]
1060    fn implicit_ws_skip_before_tokens_and_at_boundaries() {
1061        let ids = IdGen::new();
1062        // Node "P" { Field "a" %int Field "b" %int }
1063        let body = seq(
1064            &ids,
1065            vec![
1066                field(&ids, "a", token(&ids, "%int")),
1067                field(&ids, "b", token(&ids, "%int")),
1068            ],
1069        );
1070        let g = one_rule_grammar(&ids, "s", node(&ids, "P", body));
1071        let t = parse_one(&g, "  3   7 ").unwrap();
1072        assert_eq!(t.fields.len(), 2);
1073        assert_eq!(t.fields[0].0, "a");
1074        assert_eq!(t.fields[1].0, "b");
1075    }
1076
1077    // -- PEG semantics (parser-design §3.5) --
1078
1079    #[test]
1080    fn choice_commits_on_first_match() {
1081        let ids = IdGen::new();
1082        // Choice("a" -> A | "ab" -> B). Input "ab" — PEG commits to
1083        // first alt, "a" matches (leaves "b" behind), then EOF check
1084        // fails on the trailing "b".
1085        let alt_a = node(&ids, "A", token(&ids, "a"));
1086        let alt_ab = node(&ids, "B", token(&ids, "ab"));
1087        let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_a, alt_ab]));
1088        let err = parse_one(&g, "ab").unwrap_err();
1089        // Should complain about trailing "b", not attempt the second
1090        // alt.
1091        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1092        assert!(
1093            err.diagnostics[0].message.contains("byte 1"),
1094            "{}",
1095            err.diagnostics[0].message
1096        );
1097    }
1098
1099    #[test]
1100    fn failed_alt_restores_position() {
1101        let ids = IdGen::new();
1102        // Choice("abc" | "a") on "ab": first fails (partial), position
1103        // must restore, second succeeds on "a"; trailing "b" then fails
1104        // EOF. Confirms no partial-consume leak.
1105        let alt_abc = node(&ids, "L", token(&ids, "abc"));
1106        let alt_a = node(&ids, "S", token(&ids, "a"));
1107        let g = one_rule_grammar(&ids, "s", choice(&ids, vec![alt_abc, alt_a]));
1108        let err = parse_one(&g, "ab").unwrap_err();
1109        // Trailing "b" at byte 1.
1110        assert!(
1111            err.diagnostics[0].message.contains("byte 1"),
1112            "{}",
1113            err.diagnostics[0].message
1114        );
1115    }
1116
1117    #[test]
1118    fn repeat_is_greedy_and_no_backtrack_into_completed() {
1119        let ids = IdGen::new();
1120        // Seq( Repeat("a", 0..*), "a" ). Repeat eats all a's greedily;
1121        // trailing "a" required by the Seq item then fails. If Repeat
1122        // gave back one iteration, we'd succeed — the test proves it
1123        // does not.
1124        let g = one_rule_grammar(
1125            &ids,
1126            "s",
1127            node(
1128                &ids,
1129                "N",
1130                seq(
1131                    &ids,
1132                    vec![repeat(&ids, token(&ids, "a"), 0, None), token(&ids, "a")],
1133                ),
1134            ),
1135        );
1136        let err = parse_one(&g, "aaa").unwrap_err();
1137        assert_eq!(err.diagnostics[0].code, codes::UNEXPECTED);
1138    }
1139
1140    #[test]
1141    fn repeat_min_enforced() {
1142        let ids = IdGen::new();
1143        let g = one_rule_grammar(
1144            &ids,
1145            "s",
1146            node(&ids, "N", repeat(&ids, token(&ids, "a"), 2, None)),
1147        );
1148        // Only one "a" — Repeat min=2 fails.
1149        assert!(parse_one(&g, "a").is_err());
1150        // Two "a"s — succeeds.
1151        assert!(parse_one(&g, "aa").is_ok());
1152    }
1153
1154    // -- Farthest failure --
1155
1156    #[test]
1157    fn farthest_failure_carries_position_and_expected_set() {
1158        let ids = IdGen::new();
1159        // Seq("let", "x", "="). On input "let x !": we match "let"
1160        // (0..3), skip ws to 4, match "x" (4..5), skip ws to 6, expect
1161        // "=" at 6 but get "!". Farthest-failure position = 6, expected
1162        // = ["="].
1163        let g = one_rule_grammar(
1164            &ids,
1165            "s",
1166            node(
1167                &ids,
1168                "N",
1169                seq(
1170                    &ids,
1171                    vec![token(&ids, "let"), token(&ids, "x"), token(&ids, "=")],
1172                ),
1173            ),
1174        );
1175        let err = parse_one(&g, "let x !").unwrap_err();
1176        let msg = &err.diagnostics[0].message;
1177        assert!(msg.contains("byte 6"), "{msg}");
1178        assert!(msg.contains("`=`"), "{msg}");
1179    }
1180
1181    // -- Termination guards --
1182
1183    #[test]
1184    fn left_recursion_is_detected_at_runtime() {
1185        let ids = IdGen::new();
1186        // r <- r "a" — direct left recursion. Should trip the guard
1187        // rather than hang.
1188        let r = rule(
1189            &ids,
1190            "r",
1191            seq(&ids, vec![rule_ref(&ids, "r"), token(&ids, "a")]),
1192        );
1193        let g = Grammar::new(vec![r], "r");
1194        let err = g.parse("aaa").unwrap_err();
1195        assert_eq!(err.diagnostics[0].code, codes::LEFT_RECURSION);
1196    }
1197
1198    #[test]
1199    fn unknown_rule_ref_is_diagnosed() {
1200        let ids = IdGen::new();
1201        let r = rule(&ids, "start", rule_ref(&ids, "missing"));
1202        let g = Grammar::new(vec![r], "start");
1203        let err = g.parse("").unwrap_err();
1204        assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1205    }
1206
1207    #[test]
1208    fn unknown_start_rule_is_diagnosed() {
1209        let ids = IdGen::new();
1210        let r = rule(&ids, "other", token(&ids, "x"));
1211        let g = Grammar::new(vec![r], "start");
1212        let err = g.parse("x").unwrap_err();
1213        assert_eq!(err.diagnostics[0].code, codes::UNKNOWN_RULE);
1214    }
1215
1216    #[test]
1217    fn nullable_repeat_body_below_min_is_rejected() {
1218        let ids = IdGen::new();
1219        // Repeat body is a Field with no productive body — matches
1220        // empty. min=1 forces a failure rather than a hang.
1221        let empty_body = seq(&ids, vec![]);
1222        let g = one_rule_grammar(
1223            &ids,
1224            "s",
1225            node(&ids, "N", repeat(&ids, empty_body, 1, None)),
1226        );
1227        let err = g.parse("").unwrap_err();
1228        assert_eq!(err.diagnostics[0].code, codes::NULLABLE_REPEAT);
1229    }
1230}