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