meta_language/grammar/
validate.rs

1//! Semantic validation for authored grammar IR values.
2
3use std::collections::{BTreeMap, BTreeSet};
4use std::error::Error;
5use std::fmt;
6use std::ops::Range;
7
8use super::{Grammar, GrammarExpr, GrammarRule};
9
10/// Where a grammar diagnostic applies.
11#[derive(Clone, Debug, PartialEq, Eq)]
12pub struct RuleSpan {
13    /// Rule receiving the diagnostic.
14    pub rule: String,
15    /// Byte range in grammar surface source when available.
16    pub span: Option<Range<usize>>,
17}
18
19/// Diagnostic severity.
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub enum Severity {
22    /// The grammar is semantically invalid or unsafe to execute.
23    Error,
24    /// The grammar is accepted, but the finding is likely an authoring mistake.
25    Warning,
26}
27
28/// Classes of authoring defects detected by [`validate`].
29#[derive(Clone, Debug, PartialEq, Eq)]
30pub enum DiagnosticKind {
31    /// A non-terminal reference whose name no rule defines.
32    UndefinedNonTerminal {
33        /// Referenced rule name that is missing.
34        name: String,
35        /// Rule containing the missing reference.
36        referenced_in: String,
37    },
38    /// A rule can reach itself before consuming input.
39    LeftRecursion {
40        /// Rule chain proving the recursion, ending with the first rule again.
41        cycle: Vec<String>,
42    },
43    /// A rule is not reachable from the grammar start symbol.
44    UnreachableRule {
45        /// Unreachable rule name.
46        name: String,
47    },
48    /// A nullable repetition or suspicious nullable rule body was found.
49    NullableRepetition {
50        /// Rule containing the nullable construct.
51        rule: String,
52        /// Human-readable detail about the nullable construct.
53        detail: String,
54    },
55    /// More than one rule uses the same name.
56    DuplicateRule {
57        /// Duplicated rule name.
58        name: String,
59    },
60    /// A labelled capture has no semantic consumer in the grammar IR.
61    UnusedCapture {
62        /// Rule containing the labelled capture.
63        rule: String,
64        /// Capture label.
65        label: String,
66    },
67}
68
69impl DiagnosticKind {
70    /// Returns the stable textual form of the class, such as `left-recursion`.
71    #[must_use]
72    pub const fn as_str(&self) -> &'static str {
73        match self {
74            Self::UndefinedNonTerminal { .. } => "undefined-non-terminal",
75            Self::LeftRecursion { .. } => "left-recursion",
76            Self::UnreachableRule { .. } => "unreachable-rule",
77            Self::NullableRepetition { .. } => "nullable-repetition",
78            Self::DuplicateRule { .. } => "duplicate-rule",
79            Self::UnusedCapture { .. } => "unused-capture",
80        }
81    }
82}
83
84impl Severity {
85    /// Returns the stable textual form, `error` or `warning`.
86    #[must_use]
87    pub const fn as_str(self) -> &'static str {
88        match self {
89            Self::Error => "error",
90            Self::Warning => "warning",
91        }
92    }
93}
94
95/// One grammar validation finding.
96#[derive(Clone, Debug, PartialEq, Eq)]
97pub struct GrammarDiagnostic {
98    /// Structured class of the finding.
99    pub kind: DiagnosticKind,
100    /// Whether callers should treat the finding as blocking.
101    pub severity: Severity,
102    /// Friendly, fix-suggesting diagnostic text.
103    pub message: String,
104    /// Source rule location for the finding.
105    pub location: RuleSpan,
106}
107
108impl GrammarDiagnostic {
109    /// Returns true when this diagnostic should fail validation.
110    #[must_use]
111    pub fn is_error(&self) -> bool {
112        self.severity == Severity::Error
113    }
114}
115
116impl fmt::Display for GrammarDiagnostic {
117    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
118        formatter.write_str(&self.message)
119    }
120}
121
122impl Error for GrammarDiagnostic {}
123
124impl Grammar {
125    /// Runs semantic grammar validation.
126    #[must_use]
127    pub fn validate(&self) -> Vec<GrammarDiagnostic> {
128        validate(self)
129    }
130}
131
132/// The name of every diagnostic kind, in the order [`validate`] reports
133/// kinds that share a rule, as the JavaScript `GRAMMAR_DIAGNOSTIC_KINDS`.
134pub const GRAMMAR_DIAGNOSTIC_KINDS: [&str; 6] = [
135    "duplicate-rule",
136    "undefined-non-terminal",
137    "left-recursion",
138    "unreachable-rule",
139    "nullable-repetition",
140    "unused-capture",
141];
142
143/// Renders a grammar expression the way diagnostics quote it, as the
144/// JavaScript `displayGrammarExpression` does.
145#[must_use]
146pub fn display_grammar_expression(expr: &GrammarExpr) -> String {
147    expr.to_string()
148}
149
150/// Runs every grammar validation checker and returns deterministic diagnostics.
151#[must_use]
152pub fn validate(grammar: &Grammar) -> Vec<GrammarDiagnostic> {
153    let defined_names = defined_rule_names(grammar);
154    let nullability = compute_nullability(grammar);
155
156    let mut diagnostics = Vec::new();
157    diagnostics.extend(check_duplicate_rules(grammar));
158    diagnostics.extend(check_undefined_nonterminals(grammar, &defined_names));
159    diagnostics.extend(check_left_recursion(grammar, &nullability));
160    diagnostics.extend(check_unreachable_rules(grammar));
161    diagnostics.extend(check_nullable_repetition(grammar, &nullability));
162    diagnostics.extend(check_unused_captures(grammar));
163
164    sort_diagnostics(grammar, &mut diagnostics);
165    diagnostics
166}
167
168fn check_duplicate_rules(grammar: &Grammar) -> Vec<GrammarDiagnostic> {
169    let mut counts = BTreeMap::<String, usize>::new();
170    for rule in grammar.rules() {
171        *counts.entry(rule.name.clone()).or_default() += 1;
172    }
173
174    counts
175        .into_iter()
176        .filter(|(_, count)| *count > 1)
177        .map(|(name, _)| {
178            let message = format!(
179                "rule `{name}` is defined more than once; merge alternatives into one rule or rename the duplicate."
180            );
181            GrammarDiagnostic {
182                kind: DiagnosticKind::DuplicateRule { name: name.clone() },
183                severity: Severity::Error,
184                message,
185                location: rule_location(name),
186            }
187        })
188        .collect()
189}
190
191fn check_undefined_nonterminals(
192    grammar: &Grammar,
193    defined_names: &[String],
194) -> Vec<GrammarDiagnostic> {
195    let defined = defined_names
196        .iter()
197        .map(String::as_str)
198        .collect::<BTreeSet<_>>();
199    let mut diagnostics = Vec::new();
200
201    for rule in grammar.rules() {
202        for name in collect_nonterminals(rule.expr()) {
203            if defined.contains(name.as_str()) {
204                continue;
205            }
206
207            let suggestion = nearest_rule_name(&name, defined_names);
208            let message = suggestion.map_or_else(
209                || {
210                    format!(
211                        "rule `{}` references undefined non-terminal `{name}`; define it or fix the spelling.",
212                        rule.name()
213                    )
214                },
215                |candidate| {
216                    format!(
217                        "rule `{}` references undefined non-terminal `{name}`; did you mean `{candidate}`? Define it or fix the spelling.",
218                        rule.name()
219                    )
220                },
221            );
222            diagnostics.push(GrammarDiagnostic {
223                kind: DiagnosticKind::UndefinedNonTerminal {
224                    name,
225                    referenced_in: rule.name.clone(),
226                },
227                severity: Severity::Error,
228                message,
229                location: rule_location(rule.name()),
230            });
231        }
232    }
233
234    diagnostics
235}
236
237fn check_left_recursion(
238    grammar: &Grammar,
239    nullability: &BTreeMap<String, bool>,
240) -> Vec<GrammarDiagnostic> {
241    let graph = left_reference_graph(grammar, nullability);
242    let mut diagnostics = Vec::new();
243    let mut seen_cycles = BTreeSet::new();
244
245    for rule in grammar.rules() {
246        let mut path = vec![rule.name.clone()];
247        let mut seen_rules = BTreeSet::from([rule.name.clone()]);
248        collect_left_cycles(
249            rule.name(),
250            rule.name(),
251            &graph,
252            &mut seen_rules,
253            &mut path,
254            &mut seen_cycles,
255            &mut diagnostics,
256        );
257    }
258
259    diagnostics
260}
261
262fn collect_left_cycles(
263    target: &str,
264    current: &str,
265    graph: &BTreeMap<String, BTreeSet<String>>,
266    seen_rules: &mut BTreeSet<String>,
267    path: &mut Vec<String>,
268    seen_cycles: &mut BTreeSet<String>,
269    diagnostics: &mut Vec<GrammarDiagnostic>,
270) {
271    let Some(next_rules) = graph.get(current) else {
272        return;
273    };
274
275    for next in next_rules {
276        if next == target {
277            let mut cycle = path.clone();
278            cycle.push(target.to_string());
279            if seen_cycles.insert(canonical_cycle_key(&cycle)) {
280                let cycle_text = cycle.join(" -> ");
281                diagnostics.push(GrammarDiagnostic {
282                    kind: DiagnosticKind::LeftRecursion {
283                        cycle: cycle.clone(),
284                    },
285                    severity: Severity::Error,
286                    message: format!(
287                        "rule `{target}` is left-recursive (`{cycle_text}`); a recursive-descent/PEG parser may not terminate. Rewrite using repetition or factor the common prefix."
288                    ),
289                    location: rule_location(target),
290                });
291            }
292        } else if graph.contains_key(next) && seen_rules.insert(next.clone()) {
293            path.push(next.clone());
294            collect_left_cycles(
295                target,
296                next,
297                graph,
298                seen_rules,
299                path,
300                seen_cycles,
301                diagnostics,
302            );
303            path.pop();
304            seen_rules.remove(next);
305        }
306    }
307}
308
309fn check_unreachable_rules(grammar: &Grammar) -> Vec<GrammarDiagnostic> {
310    let Some(start_rule) = grammar.start_rule() else {
311        return Vec::new();
312    };
313
314    let defined = grammar
315        .rules()
316        .iter()
317        .map(GrammarRule::name)
318        .collect::<BTreeSet<_>>();
319    let mut reachable = BTreeSet::new();
320    let mut stack = vec![start_rule.name.clone()];
321
322    while let Some(name) = stack.pop() {
323        if !reachable.insert(name.clone()) {
324            continue;
325        }
326
327        if let Some(rule) = grammar.rule(&name) {
328            for reference in collect_nonterminals(rule.expr()) {
329                if defined.contains(reference.as_str()) {
330                    stack.push(reference);
331                }
332            }
333        }
334    }
335
336    grammar
337        .rules()
338        .iter()
339        .filter(|rule| !reachable.contains(rule.name()))
340        .map(|rule| GrammarDiagnostic {
341            kind: DiagnosticKind::UnreachableRule {
342                name: rule.name.clone(),
343            },
344            severity: Severity::Warning,
345            message: format!(
346                "rule `{}` is not reachable from start rule `{}`; remove it or reference it from a reachable rule.",
347                rule.name(),
348                start_rule.name()
349            ),
350            location: rule_location(rule.name()),
351        })
352        .collect()
353}
354
355fn check_nullable_repetition(
356    grammar: &Grammar,
357    nullability: &BTreeMap<String, bool>,
358) -> Vec<GrammarDiagnostic> {
359    let suspicious_nullable = compute_suspicious_nullability(grammar, nullability);
360    let mut diagnostics = Vec::new();
361
362    for rule in grammar.rules() {
363        if suspicious_nullable
364            .get(rule.name())
365            .copied()
366            .unwrap_or(false)
367        {
368            diagnostics.push(GrammarDiagnostic {
369                kind: DiagnosticKind::NullableRepetition {
370                    rule: rule.name.clone(),
371                    detail: "rule body is nullable".to_string(),
372                },
373                severity: Severity::Warning,
374                message: format!(
375                    "rule `{}` can match empty; add a required terminal/non-terminal or document the rule as intentional.",
376                    rule.name()
377                ),
378                location: rule_location(rule.name()),
379            });
380        }
381        collect_nullable_repetitions(rule.name(), rule.expr(), nullability, &mut diagnostics);
382    }
383
384    diagnostics
385}
386
387fn collect_nullable_repetitions(
388    rule_name: &str,
389    expr: &GrammarExpr,
390    nullability: &BTreeMap<String, bool>,
391    diagnostics: &mut Vec<GrammarDiagnostic>,
392) {
393    match expr {
394        GrammarExpr::ZeroOrMore(inner) => {
395            push_nullable_repetition(
396                rule_name,
397                "zero-or-more repetition",
398                inner,
399                nullability,
400                diagnostics,
401            );
402            collect_nullable_repetitions(rule_name, inner, nullability, diagnostics);
403        }
404        GrammarExpr::OneOrMore(inner) => {
405            push_nullable_repetition(
406                rule_name,
407                "one-or-more repetition",
408                inner,
409                nullability,
410                diagnostics,
411            );
412            collect_nullable_repetitions(rule_name, inner, nullability, diagnostics);
413        }
414        GrammarExpr::Repeat { expr: inner, .. } => {
415            push_nullable_repetition(
416                rule_name,
417                "counted repetition",
418                inner,
419                nullability,
420                diagnostics,
421            );
422            collect_nullable_repetitions(rule_name, inner, nullability, diagnostics);
423        }
424        GrammarExpr::Choice { alternatives, .. } => {
425            for alternative in alternatives {
426                collect_nullable_repetitions(rule_name, alternative, nullability, diagnostics);
427            }
428        }
429        GrammarExpr::Sequence(items) => {
430            for item in items {
431                collect_nullable_repetitions(rule_name, item, nullability, diagnostics);
432            }
433        }
434        GrammarExpr::Optional(inner)
435        | GrammarExpr::And(inner)
436        | GrammarExpr::Not(inner)
437        | GrammarExpr::Capture { expr: inner, .. } => {
438            collect_nullable_repetitions(rule_name, inner, nullability, diagnostics);
439        }
440        GrammarExpr::Feature(feature) => feature.for_each_expression(&mut |inner| {
441            collect_nullable_repetitions(rule_name, inner, nullability, diagnostics);
442        }),
443        GrammarExpr::Empty
444        | GrammarExpr::Terminal(_)
445        | GrammarExpr::TerminalInsensitive(_)
446        | GrammarExpr::CharRange(_, _)
447        | GrammarExpr::CharClass { .. }
448        | GrammarExpr::AnyChar
449        | GrammarExpr::NonTerminal(_) => {}
450    }
451}
452
453fn push_nullable_repetition(
454    rule_name: &str,
455    repetition: &str,
456    inner: &GrammarExpr,
457    nullability: &BTreeMap<String, bool>,
458    diagnostics: &mut Vec<GrammarDiagnostic>,
459) {
460    if !expr_is_nullable(inner, nullability) {
461        return;
462    }
463
464    let detail = format!("{repetition} has nullable inner expression `{inner}`");
465    diagnostics.push(GrammarDiagnostic {
466        kind: DiagnosticKind::NullableRepetition {
467            rule: rule_name.to_string(),
468            detail: detail.clone(),
469        },
470        severity: Severity::Warning,
471        message: format!(
472            "rule `{rule_name}` uses a {detail}; make the repeated expression consume input or move the optional part outside the repetition."
473        ),
474        location: rule_location(rule_name),
475    });
476}
477
478fn check_unused_captures(grammar: &Grammar) -> Vec<GrammarDiagnostic> {
479    let mut diagnostics = Vec::new();
480    for rule in grammar.rules() {
481        collect_unused_captures(rule.name(), rule.expr(), &mut diagnostics);
482    }
483    diagnostics
484}
485
486fn collect_unused_captures(
487    rule_name: &str,
488    expr: &GrammarExpr,
489    diagnostics: &mut Vec<GrammarDiagnostic>,
490) {
491    match expr {
492        GrammarExpr::Capture {
493            label: Some(label),
494            expr,
495        } => {
496            diagnostics.push(GrammarDiagnostic {
497                kind: DiagnosticKind::UnusedCapture {
498                    rule: rule_name.to_string(),
499                    label: label.clone(),
500                },
501                severity: Severity::Warning,
502                message: format!(
503                    "capture label `{label}` in rule `{rule_name}` is not used by grammar semantics; remove the label or wire it to a consumer."
504                ),
505                location: rule_location(rule_name),
506            });
507            collect_unused_captures(rule_name, expr, diagnostics);
508        }
509        GrammarExpr::Capture { label: None, expr }
510        | GrammarExpr::Optional(expr)
511        | GrammarExpr::ZeroOrMore(expr)
512        | GrammarExpr::OneOrMore(expr)
513        | GrammarExpr::And(expr)
514        | GrammarExpr::Not(expr)
515        | GrammarExpr::Repeat { expr, .. } => collect_unused_captures(rule_name, expr, diagnostics),
516        GrammarExpr::Choice { alternatives, .. } => {
517            for alternative in alternatives {
518                collect_unused_captures(rule_name, alternative, diagnostics);
519            }
520        }
521        GrammarExpr::Sequence(items) => {
522            for item in items {
523                collect_unused_captures(rule_name, item, diagnostics);
524            }
525        }
526        GrammarExpr::Feature(feature) => feature.for_each_expression(&mut |inner| {
527            collect_unused_captures(rule_name, inner, diagnostics);
528        }),
529        GrammarExpr::Empty
530        | GrammarExpr::Terminal(_)
531        | GrammarExpr::TerminalInsensitive(_)
532        | GrammarExpr::CharRange(_, _)
533        | GrammarExpr::CharClass { .. }
534        | GrammarExpr::AnyChar
535        | GrammarExpr::NonTerminal(_) => {}
536    }
537}
538
539fn left_reference_graph(
540    grammar: &Grammar,
541    nullability: &BTreeMap<String, bool>,
542) -> BTreeMap<String, BTreeSet<String>> {
543    let defined = grammar
544        .rules()
545        .iter()
546        .map(GrammarRule::name)
547        .collect::<BTreeSet<_>>();
548    let mut graph = BTreeMap::<String, BTreeSet<String>>::new();
549
550    for rule in grammar.rules() {
551        let mut references = BTreeSet::new();
552        collect_left_references(rule.expr(), nullability, &mut references);
553        graph.entry(rule.name.clone()).or_default().extend(
554            references
555                .into_iter()
556                .filter(|name| defined.contains(name.as_str())),
557        );
558    }
559
560    graph
561}
562
563fn collect_left_references(
564    expr: &GrammarExpr,
565    nullability: &BTreeMap<String, bool>,
566    references: &mut BTreeSet<String>,
567) {
568    match expr {
569        GrammarExpr::NonTerminal(name) => {
570            references.insert(name.clone());
571        }
572        GrammarExpr::Choice { alternatives, .. } => {
573            for alternative in alternatives {
574                collect_left_references(alternative, nullability, references);
575            }
576        }
577        GrammarExpr::Sequence(items) => {
578            for item in items {
579                collect_left_references(item, nullability, references);
580                if !expr_is_nullable(item, nullability) {
581                    break;
582                }
583            }
584        }
585        GrammarExpr::Optional(expr)
586        | GrammarExpr::ZeroOrMore(expr)
587        | GrammarExpr::OneOrMore(expr)
588        | GrammarExpr::And(expr)
589        | GrammarExpr::Not(expr)
590        | GrammarExpr::Capture { expr, .. }
591        | GrammarExpr::Repeat { expr, .. } => {
592            collect_left_references(expr, nullability, references);
593        }
594        GrammarExpr::Empty
595        | GrammarExpr::Terminal(_)
596        | GrammarExpr::TerminalInsensitive(_)
597        | GrammarExpr::CharRange(_, _)
598        | GrammarExpr::CharClass { .. }
599        | GrammarExpr::Feature(_)
600        | GrammarExpr::AnyChar => {}
601    }
602}
603
604fn compute_nullability(grammar: &Grammar) -> BTreeMap<String, bool> {
605    let mut nullability = grammar
606        .rules()
607        .iter()
608        .map(|rule| (rule.name.clone(), false))
609        .collect::<BTreeMap<_, _>>();
610
611    loop {
612        let mut changed = false;
613        for rule in grammar.rules() {
614            if !expr_is_nullable(rule.expr(), &nullability) {
615                continue;
616            }
617
618            let entry = nullability.entry(rule.name.clone()).or_insert(false);
619            if !*entry {
620                *entry = true;
621                changed = true;
622            }
623        }
624
625        if !changed {
626            return nullability;
627        }
628    }
629}
630
631fn expr_is_nullable(expr: &GrammarExpr, nullability: &BTreeMap<String, bool>) -> bool {
632    match expr {
633        GrammarExpr::Terminal(value) | GrammarExpr::TerminalInsensitive(value) => value.is_empty(),
634        GrammarExpr::CharRange(_, _)
635        | GrammarExpr::CharClass { .. }
636        | GrammarExpr::AnyChar
637        | GrammarExpr::Feature(_) => false,
638        GrammarExpr::NonTerminal(name) => nullability.get(name).copied().unwrap_or(false),
639        GrammarExpr::Choice { alternatives, .. } => alternatives
640            .iter()
641            .any(|alternative| expr_is_nullable(alternative, nullability)),
642        GrammarExpr::Sequence(items) => {
643            items.iter().all(|item| expr_is_nullable(item, nullability))
644        }
645        GrammarExpr::Empty
646        | GrammarExpr::Optional(_)
647        | GrammarExpr::ZeroOrMore(_)
648        | GrammarExpr::And(_)
649        | GrammarExpr::Not(_) => true,
650        GrammarExpr::OneOrMore(expr) | GrammarExpr::Capture { expr, .. } => {
651            expr_is_nullable(expr, nullability)
652        }
653        GrammarExpr::Repeat { expr, min, .. } => *min == 0 || expr_is_nullable(expr, nullability),
654    }
655}
656
657fn compute_suspicious_nullability(
658    grammar: &Grammar,
659    nullability: &BTreeMap<String, bool>,
660) -> BTreeMap<String, bool> {
661    let mut suspicious = grammar
662        .rules()
663        .iter()
664        .map(|rule| (rule.name.clone(), false))
665        .collect::<BTreeMap<_, _>>();
666
667    loop {
668        let mut changed = false;
669        for rule in grammar.rules() {
670            if !expr_is_suspicious_nullable(rule.expr(), nullability, &suspicious) {
671                continue;
672            }
673
674            let entry = suspicious.entry(rule.name.clone()).or_insert(false);
675            if !*entry {
676                *entry = true;
677                changed = true;
678            }
679        }
680
681        if !changed {
682            return suspicious;
683        }
684    }
685}
686
687fn expr_is_suspicious_nullable(
688    expr: &GrammarExpr,
689    nullability: &BTreeMap<String, bool>,
690    suspicious: &BTreeMap<String, bool>,
691) -> bool {
692    match expr {
693        GrammarExpr::Terminal(value) | GrammarExpr::TerminalInsensitive(value) => value.is_empty(),
694        GrammarExpr::CharRange(_, _)
695        | GrammarExpr::CharClass { .. }
696        | GrammarExpr::AnyChar
697        | GrammarExpr::Feature(_) => false,
698        GrammarExpr::NonTerminal(name) => suspicious.get(name).copied().unwrap_or(false),
699        GrammarExpr::Choice { alternatives, .. } => alternatives
700            .iter()
701            .any(|alternative| expr_is_suspicious_nullable(alternative, nullability, suspicious)),
702        GrammarExpr::Sequence(items) => {
703            items.is_empty()
704                || (items.iter().all(|item| expr_is_nullable(item, nullability))
705                    && items
706                        .iter()
707                        .any(|item| expr_is_suspicious_nullable(item, nullability, suspicious)))
708        }
709        GrammarExpr::Empty
710        | GrammarExpr::Optional(_)
711        | GrammarExpr::And(_)
712        | GrammarExpr::Not(_) => true,
713        GrammarExpr::ZeroOrMore(expr) | GrammarExpr::OneOrMore(expr) => {
714            expr_is_nullable(expr, nullability)
715        }
716        GrammarExpr::Repeat { expr, .. } => expr_is_nullable(expr, nullability),
717        GrammarExpr::Capture { expr, .. } => {
718            expr_is_suspicious_nullable(expr, nullability, suspicious)
719        }
720    }
721}
722
723fn collect_nonterminals(expr: &GrammarExpr) -> BTreeSet<String> {
724    let mut names = BTreeSet::new();
725    collect_nonterminals_into(expr, &mut names);
726    names
727}
728
729fn collect_nonterminals_into(expr: &GrammarExpr, names: &mut BTreeSet<String>) {
730    match expr {
731        GrammarExpr::NonTerminal(name) => {
732            names.insert(name.clone());
733        }
734        GrammarExpr::Choice { alternatives, .. } => {
735            for alternative in alternatives {
736                collect_nonterminals_into(alternative, names);
737            }
738        }
739        GrammarExpr::Sequence(items) => {
740            for item in items {
741                collect_nonterminals_into(item, names);
742            }
743        }
744        GrammarExpr::Optional(expr)
745        | GrammarExpr::ZeroOrMore(expr)
746        | GrammarExpr::OneOrMore(expr)
747        | GrammarExpr::And(expr)
748        | GrammarExpr::Not(expr)
749        | GrammarExpr::Capture { expr, .. }
750        | GrammarExpr::Repeat { expr, .. } => collect_nonterminals_into(expr, names),
751        GrammarExpr::Feature(feature) => feature.collect_references(names),
752        GrammarExpr::Empty
753        | GrammarExpr::Terminal(_)
754        | GrammarExpr::TerminalInsensitive(_)
755        | GrammarExpr::CharRange(_, _)
756        | GrammarExpr::CharClass { .. }
757        | GrammarExpr::AnyChar => {}
758    }
759}
760
761fn defined_rule_names(grammar: &Grammar) -> Vec<String> {
762    let mut names = Vec::new();
763    let mut seen = BTreeSet::new();
764    for rule in grammar.rules() {
765        if seen.insert(rule.name.clone()) {
766            names.push(rule.name.clone());
767        }
768    }
769    names
770}
771
772fn nearest_rule_name<'a>(name: &str, candidates: &'a [String]) -> Option<&'a str> {
773    let mut best = None;
774
775    for candidate in candidates {
776        let distance = levenshtein(name, candidate);
777        if distance > 2 {
778            continue;
779        }
780
781        let should_replace = best.is_none_or(|(best_name, best_distance)| {
782            distance < best_distance
783                || (distance == best_distance && candidate.as_str() < best_name)
784        });
785        if should_replace {
786            best = Some((candidate.as_str(), distance));
787        }
788    }
789
790    best.map(|(candidate, _)| candidate)
791}
792
793fn levenshtein(left: &str, right: &str) -> usize {
794    let left_chars = left.chars().collect::<Vec<_>>();
795    let right_chars = right.chars().collect::<Vec<_>>();
796    let mut previous = (0..=right_chars.len()).collect::<Vec<_>>();
797    let mut current = vec![0; right_chars.len() + 1];
798
799    for (left_index, left_char) in left_chars.iter().enumerate() {
800        current[0] = left_index + 1;
801        for (right_index, right_char) in right_chars.iter().enumerate() {
802            let substitution_cost = usize::from(left_char != right_char);
803            current[right_index + 1] = (previous[right_index + 1] + 1)
804                .min(current[right_index] + 1)
805                .min(previous[right_index] + substitution_cost);
806        }
807        previous.clone_from(&current);
808    }
809
810    previous[right_chars.len()]
811}
812
813fn canonical_cycle_key(cycle: &[String]) -> String {
814    let nodes = &cycle[..cycle.len().saturating_sub(1)];
815    if nodes.is_empty() {
816        return String::new();
817    }
818
819    let mut best = None;
820    for start in 0..nodes.len() {
821        let rotation = (0..nodes.len())
822            .map(|offset| nodes[(start + offset) % nodes.len()].as_str())
823            .collect::<Vec<_>>()
824            .join("\0");
825        if best.as_ref().is_none_or(|candidate| rotation < *candidate) {
826            best = Some(rotation);
827        }
828    }
829    best.unwrap_or_default()
830}
831
832fn sort_diagnostics(grammar: &Grammar, diagnostics: &mut [GrammarDiagnostic]) {
833    let indices = grammar
834        .rules()
835        .iter()
836        .enumerate()
837        .rev()
838        .map(|(index, rule)| (rule.name.clone(), index))
839        .collect::<BTreeMap<_, _>>();
840
841    diagnostics.sort_by(|left, right| {
842        let left_span = left
843            .location
844            .span
845            .as_ref()
846            .map_or(usize::MAX, |span| span.start);
847        let right_span = right
848            .location
849            .span
850            .as_ref()
851            .map_or(usize::MAX, |span| span.start);
852        let left_index = indices
853            .get(&left.location.rule)
854            .copied()
855            .unwrap_or(usize::MAX);
856        let right_index = indices
857            .get(&right.location.rule)
858            .copied()
859            .unwrap_or(usize::MAX);
860
861        left_span
862            .cmp(&right_span)
863            .then_with(|| left_index.cmp(&right_index))
864            .then_with(|| left.location.rule.cmp(&right.location.rule))
865            .then_with(|| severity_rank(left.severity).cmp(&severity_rank(right.severity)))
866            .then_with(|| kind_rank(&left.kind).cmp(&kind_rank(&right.kind)))
867            .then_with(|| left.message.cmp(&right.message))
868    });
869}
870
871const fn severity_rank(severity: Severity) -> usize {
872    match severity {
873        Severity::Error => 0,
874        Severity::Warning => 1,
875    }
876}
877
878const fn kind_rank(kind: &DiagnosticKind) -> usize {
879    match kind {
880        DiagnosticKind::DuplicateRule { .. } => 0,
881        DiagnosticKind::UndefinedNonTerminal { .. } => 1,
882        DiagnosticKind::LeftRecursion { .. } => 2,
883        DiagnosticKind::UnreachableRule { .. } => 3,
884        DiagnosticKind::NullableRepetition { .. } => 4,
885        DiagnosticKind::UnusedCapture { .. } => 5,
886    }
887}
888
889fn rule_location(rule: impl Into<String>) -> RuleSpan {
890    RuleSpan {
891        rule: rule.into(),
892        span: None,
893    }
894}
meta_language/grammar/validate.rs

meta_language/grammar/
validate.rs
