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