meta_language/grammar/runtime/
mod.rs

1//! Runtime parser for first-class grammar values.
2//!
3//! [`GrammarParser`] interprets the grammar IR directly. It uses PEG-style
4//! ordered choice, longest-local-match determinisation for unordered choice,
5//! greedy repetition, and a same-rule/same-position guard so left-recursive
6//! grammars fail closed instead of looping.
7
8use std::collections::{HashMap, HashSet};
9use std::sync::Arc;
10
11use crate::grammar::inference::eval::MembershipOracle;
12use crate::grammar::{CharClassItem, Grammar, GrammarExpr};
13use crate::line_index::LineIndex;
14use crate::{
15    ByteRange, LanguageParser, LinkFlags, LinkId, LinkMetadata, LinkNetwork, LinkType,
16    ParseConfiguration, ParserRegistry, SourceSpan,
17};
18
19const EXPR_EMPTY: &str = "grammar::runtime::expression::empty-expression";
20const EXPR_TERMINAL: &str = "grammar::runtime::expression::terminal";
21const EXPR_TERMINAL_INSENSITIVE: &str = "grammar::runtime::expression::case-insensitive-terminal";
22const EXPR_CHAR_RANGE: &str = "grammar::runtime::expression::character-range";
23const EXPR_CHAR_CLASS: &str = "grammar::runtime::expression::character-class";
24const EXPR_ANY_CHAR: &str = "grammar::runtime::expression::any-character";
25const EXPR_CHOICE: &str = "grammar::runtime::expression::choice";
26const EXPR_SEQUENCE: &str = "grammar::runtime::expression::sequence";
27const EXPR_OPTIONAL: &str = "grammar::runtime::expression::optional-expression";
28const EXPR_ZERO_OR_MORE: &str = "grammar::runtime::expression::zero-or-more-repetition";
29const EXPR_ONE_OR_MORE: &str = "grammar::runtime::expression::one-or-more-repetition";
30const EXPR_REPEAT: &str = "grammar::runtime::expression::counted-repetition";
31const EXPR_AND: &str = "grammar::runtime::expression::positive-predicate";
32const EXPR_NOT: &str = "grammar::runtime::expression::negative-predicate";
33
34/// A [`LanguageParser`] that interprets a [`Grammar`] at runtime.
35///
36/// The parser is intentionally in-process: it does not generate source code.
37/// It accepts input only when the start rule consumes the complete string.
38/// Failed or partial parses return `false` from [`accepts`](Self::accepts) and
39/// fall back to [`LinkNetwork::parse_lossless_text`] through the
40/// [`LanguageParser`] implementation.
41#[derive(Clone, Debug)]
42pub struct GrammarParser {
43    grammar: Grammar,
44    diagnostics: Vec<String>,
45}
46
47impl GrammarParser {
48    /// Builds a runtime parser for `grammar`.
49    ///
50    /// Construction records basic grammar diagnostics, including missing start
51    /// rules and undefined non-terminal references. Diagnostic grammars fail
52    /// closed at parse time instead of panicking.
53    #[must_use]
54    pub fn new(grammar: Grammar) -> Self {
55        let diagnostics = validate_grammar(&grammar);
56        Self {
57            grammar,
58            diagnostics,
59        }
60    }
61
62    /// Wrapped grammar.
63    #[must_use]
64    pub const fn grammar(&self) -> &Grammar {
65        &self.grammar
66    }
67
68    /// Construction-time diagnostics for malformed grammar references.
69    #[must_use]
70    pub fn diagnostics(&self) -> &[String] {
71        &self.diagnostics
72    }
73
74    /// Membership query: does the grammar accept all of `text`?
75    ///
76    /// This is the oracle surface consumed by grammar-inference evaluation and
77    /// active-learning callers.
78    #[must_use]
79    pub fn accepts(&self, text: &str) -> bool {
80        self.parse_full(text).is_some()
81    }
82
83    fn parse_full(&self, text: &str) -> Option<ParseNode> {
84        if !self.diagnostics.is_empty() {
85            return None;
86        }
87
88        RuntimeMatcher::new(&self.grammar, text)
89            .parse_full()
90            .ok()
91            .flatten()
92    }
93
94    fn try_parse_network(
95        &self,
96        text: &str,
97        language: &str,
98        configuration: ParseConfiguration,
99    ) -> Option<LinkNetwork> {
100        let tree = self.parse_full(text)?;
101        let (mut network, document) = LinkNetwork::new_parse_document(text, language);
102        let lines = LineIndex::new(text);
103        let context = EmitContext {
104            text,
105            lines: &lines,
106            language,
107            configuration,
108        };
109        emit_parse_node(&mut network, document, &tree, context);
110        network.attach_embedded_regions(document, text, language, configuration);
111        Some(network)
112    }
113}
114
115impl LanguageParser for GrammarParser {
116    fn parse_source(
117        &self,
118        text: &str,
119        language: &str,
120        configuration: ParseConfiguration,
121    ) -> LinkNetwork {
122        self.try_parse_network(text, language, configuration)
123            .unwrap_or_else(|| LinkNetwork::parse_lossless_text(text, language, configuration))
124    }
125}
126
127impl MembershipOracle for GrammarParser {
128    fn accepts(&self, text: &str) -> bool {
129        Self::accepts(self, text)
130    }
131}
132
133/// Register `grammar` under `key`, shadowing the built-in dispatch for that key.
134pub fn register_grammar(
135    registry: &mut ParserRegistry,
136    key: impl Into<String>,
137    grammar: Grammar,
138) -> &mut ParserRegistry {
139    registry.register(key, Arc::new(GrammarParser::new(grammar)))
140}
141
142/// Builder-style variant mirroring [`ParserRegistry::with_parser`].
143#[must_use]
144pub fn with_grammar(
145    registry: ParserRegistry,
146    key: impl Into<String>,
147    grammar: Grammar,
148) -> ParserRegistry {
149    registry.with_parser(key, Arc::new(GrammarParser::new(grammar)))
150}
151
152fn validate_grammar(grammar: &Grammar) -> Vec<String> {
153    let mut diagnostics = Vec::new();
154    if grammar.rules().is_empty() {
155        diagnostics.push("grammar has no start rule".to_string());
156    }
157    if let Some(start) = grammar.start()
158        && grammar.rule(start).is_none()
159    {
160        diagnostics.push(format!("start rule `{start}` is not defined"));
161    }
162    diagnostics.extend(
163        grammar
164            .undefined_nonterminals()
165            .into_iter()
166            .map(|rule| format!("undefined non-terminal `{rule}`")),
167    );
168    // The feature union forms run in `feature_runtime::compile_grammar`.
169    for rule in grammar.rules() {
170        if let Some(feature) = rule.expr().first_feature() {
171            diagnostics.push(format!(
172                "rule `{}` uses the feature union form `{}`; the grammar executor runs it",
173                rule.name(),
174                feature.head()
175            ));
176        }
177    }
178    diagnostics
179}
180
181#[derive(Clone, Debug, PartialEq, Eq)]
182struct RuntimeMatcher<'grammar, 'text> {
183    grammar: &'grammar Grammar,
184    text: &'text str,
185    memo: HashMap<(String, usize), Option<ParseNode>>,
186    active: HashSet<(String, usize)>,
187}
188
189impl<'grammar, 'text> RuntimeMatcher<'grammar, 'text> {
190    fn new(grammar: &'grammar Grammar, text: &'text str) -> Self {
191        Self {
192            grammar,
193            text,
194            memo: HashMap::new(),
195            active: HashSet::new(),
196        }
197    }
198
199    fn parse_full(&mut self) -> Result<Option<ParseNode>, MatchError> {
200        let Some(start) = self.grammar.start_rule() else {
201            return Ok(None);
202        };
203        Ok(self
204            .match_rule(start.name(), 0)?
205            .filter(|node| node.end == self.text.len()))
206    }
207
208    fn match_rule(&mut self, name: &str, position: usize) -> Result<Option<ParseNode>, MatchError> {
209        if !self.valid_position(position) {
210            return Ok(None);
211        }
212
213        let key = (name.to_string(), position);
214        if let Some(cached) = self.memo.get(&key) {
215            return Ok(cached.clone());
216        }
217        if self.active.contains(&key) {
218            return Err(MatchError::LeftRecursive);
219        }
220
221        let Some(rule) = self.grammar.rule(name) else {
222            return Ok(None);
223        };
224
225        self.active.insert(key.clone());
226        let result = self.match_expr(rule.expr(), position);
227        self.active.remove(&key);
228
229        let child = result?;
230        let node = child
231            .map(|child| ParseNode::structural(rule_term(name), position, child.end, vec![child]));
232        self.memo.insert(key, node.clone());
233        Ok(node)
234    }
235
236    fn match_expr(
237        &mut self,
238        expr: &GrammarExpr,
239        position: usize,
240    ) -> Result<Option<ParseNode>, MatchError> {
241        if !self.valid_position(position) {
242            return Ok(None);
243        }
244
245        match expr {
246            GrammarExpr::Feature(_) => Ok(None),
247            GrammarExpr::Empty => Ok(Some(ParseNode::structural(
248                EXPR_EMPTY,
249                position,
250                position,
251                Vec::new(),
252            ))),
253            GrammarExpr::Terminal(value) => {
254                Ok(self.match_terminal(EXPR_TERMINAL, value, position, false))
255            }
256            GrammarExpr::TerminalInsensitive(value) => {
257                Ok(self.match_terminal(EXPR_TERMINAL_INSENSITIVE, value, position, true))
258            }
259            GrammarExpr::CharRange(start, end) => Ok(self
260                .char_at(position)
261                .filter(|(value, _next)| start <= value && value <= end)
262                .map(|(_value, next)| ParseNode::token(EXPR_CHAR_RANGE, position, next))),
263            GrammarExpr::CharClass { negated, items } => Ok(self
264                .char_at(position)
265                .filter(|(value, _next)| class_accepts(*value, *negated, items))
266                .map(|(_value, next)| ParseNode::token(EXPR_CHAR_CLASS, position, next))),
267            GrammarExpr::AnyChar => Ok(self
268                .char_at(position)
269                .map(|(_value, next)| ParseNode::token(EXPR_ANY_CHAR, position, next))),
270            GrammarExpr::NonTerminal(name) => {
271                let child = self.match_rule(name, position)?;
272                Ok(child.map(|child| {
273                    ParseNode::structural(non_terminal_term(name), position, child.end, vec![child])
274                }))
275            }
276            GrammarExpr::Choice {
277                ordered,
278                alternatives,
279            } => self.match_choice(*ordered, alternatives, position),
280            GrammarExpr::Sequence(items) => self.match_sequence(items, position),
281            GrammarExpr::Optional(inner) => {
282                if let Some(child) = self.match_expr(inner, position)? {
283                    Ok(Some(ParseNode::structural(
284                        EXPR_OPTIONAL,
285                        position,
286                        child.end,
287                        vec![child],
288                    )))
289                } else {
290                    Ok(Some(ParseNode::structural(
291                        EXPR_OPTIONAL,
292                        position,
293                        position,
294                        Vec::new(),
295                    )))
296                }
297            }
298            GrammarExpr::ZeroOrMore(inner) => {
299                self.match_repetition(EXPR_ZERO_OR_MORE, inner, position, 0, None)
300            }
301            GrammarExpr::OneOrMore(inner) => {
302                self.match_repetition(EXPR_ONE_OR_MORE, inner, position, 1, None)
303            }
304            GrammarExpr::Repeat { expr, min, max } => {
305                self.match_repetition(EXPR_REPEAT, expr, position, *min, *max)
306            }
307            GrammarExpr::And(inner) => {
308                if self.match_expr(inner, position)?.is_some() {
309                    Ok(Some(ParseNode::structural(
310                        EXPR_AND,
311                        position,
312                        position,
313                        Vec::new(),
314                    )))
315                } else {
316                    Ok(None)
317                }
318            }
319            GrammarExpr::Not(inner) => {
320                if self.match_expr(inner, position)?.is_none() {
321                    Ok(Some(ParseNode::structural(
322                        EXPR_NOT,
323                        position,
324                        position,
325                        Vec::new(),
326                    )))
327                } else {
328                    Ok(None)
329                }
330            }
331            GrammarExpr::Capture { label, expr } => {
332                let child = self.match_expr(expr, position)?;
333                Ok(child.map(|child| {
334                    ParseNode::structural(
335                        capture_term(label.as_deref()),
336                        position,
337                        child.end,
338                        vec![child],
339                    )
340                }))
341            }
342        }
343    }
344
345    fn match_choice(
346        &mut self,
347        ordered: bool,
348        alternatives: &[GrammarExpr],
349        position: usize,
350    ) -> Result<Option<ParseNode>, MatchError> {
351        if ordered {
352            for alternative in alternatives {
353                if let Some(child) = self.match_expr(alternative, position)? {
354                    return Ok(Some(ParseNode::structural(
355                        EXPR_CHOICE,
356                        position,
357                        child.end,
358                        vec![child],
359                    )));
360                }
361            }
362            return Ok(None);
363        }
364
365        let mut best: Option<ParseNode> = None;
366        for alternative in alternatives {
367            let candidate = self.match_expr(alternative, position)?;
368            let replace_best = candidate
369                .as_ref()
370                .is_some_and(|node| best.as_ref().is_none_or(|best| node.end > best.end));
371            if replace_best {
372                best = candidate;
373            }
374        }
375
376        Ok(best.map(|child| ParseNode::structural(EXPR_CHOICE, position, child.end, vec![child])))
377    }
378
379    fn match_sequence(
380        &mut self,
381        items: &[GrammarExpr],
382        position: usize,
383    ) -> Result<Option<ParseNode>, MatchError> {
384        let mut current = position;
385        let mut children = Vec::with_capacity(items.len());
386        for item in items {
387            let Some(child) = self.match_expr(item, current)? else {
388                return Ok(None);
389            };
390            current = child.end;
391            children.push(child);
392        }
393
394        Ok(Some(ParseNode::structural(
395            EXPR_SEQUENCE,
396            position,
397            current,
398            children,
399        )))
400    }
401
402    fn match_repetition(
403        &mut self,
404        term: &'static str,
405        inner: &GrammarExpr,
406        position: usize,
407        min: usize,
408        max: Option<usize>,
409    ) -> Result<Option<ParseNode>, MatchError> {
410        if max.is_some_and(|max| max < min) {
411            return Ok(None);
412        }
413
414        let mut current = position;
415        let mut count = 0;
416        let mut children = Vec::new();
417        loop {
418            if max.is_some_and(|max| count >= max) {
419                break;
420            }
421
422            let Some(child) = self.match_expr(inner, current)? else {
423                break;
424            };
425
426            if child.end == current {
427                if count < min {
428                    count = min;
429                    children.push(child);
430                }
431                break;
432            }
433
434            current = child.end;
435            count += 1;
436            children.push(child);
437        }
438
439        if count >= min {
440            Ok(Some(ParseNode::structural(
441                term, position, current, children,
442            )))
443        } else {
444            Ok(None)
445        }
446    }
447
448    fn match_terminal(
449        &self,
450        term: &'static str,
451        value: &str,
452        position: usize,
453        insensitive: bool,
454    ) -> Option<ParseNode> {
455        let matches = if insensitive {
456            starts_with_ascii_insensitive(&self.text[position..], value)
457        } else {
458            self.text[position..].starts_with(value)
459        };
460        matches.then(|| ParseNode::token(term, position, position + value.len()))
461    }
462
463    fn char_at(&self, position: usize) -> Option<(char, usize)> {
464        self.text[position..]
465            .chars()
466            .next()
467            .map(|value| (value, position + value.len_utf8()))
468    }
469
470    const fn valid_position(&self, position: usize) -> bool {
471        position <= self.text.len() && self.text.is_char_boundary(position)
472    }
473}
474
475#[derive(Clone, Debug, PartialEq, Eq)]
476enum MatchError {
477    LeftRecursive,
478}
479
480#[derive(Clone, Debug, PartialEq, Eq)]
481struct ParseNode {
482    term: String,
483    start: usize,
484    end: usize,
485    children: Vec<Self>,
486    token: bool,
487}
488
489impl ParseNode {
490    fn structural(term: impl Into<String>, start: usize, end: usize, children: Vec<Self>) -> Self {
491        Self {
492            term: term.into(),
493            start,
494            end,
495            children,
496            token: false,
497        }
498    }
499
500    fn token(term: impl Into<String>, start: usize, end: usize) -> Self {
501        Self {
502            term: term.into(),
503            start,
504            end,
505            children: Vec::new(),
506            token: true,
507        }
508    }
509}
510
511#[derive(Clone, Copy, Debug)]
512struct EmitContext<'source> {
513    text: &'source str,
514    lines: &'source LineIndex,
515    language: &'source str,
516    configuration: ParseConfiguration,
517}
518
519fn emit_parse_node(
520    network: &mut LinkNetwork,
521    owner: LinkId,
522    node: &ParseNode,
523    context: EmitContext<'_>,
524) -> LinkId {
525    let span = span_for_range(context.lines, node.start, node.end);
526    let node_id = network.insert_link(
527        [owner],
528        LinkMetadata::new()
529            .with_link_type(LinkType::Grammar)
530            .with_named(true)
531            .with_term(&node.term)
532            .with_language(context.language)
533            .with_span(span)
534            .with_flags(LinkFlags::clean()),
535    );
536
537    for child in &node.children {
538        emit_parse_node(network, node_id, child, context);
539    }
540
541    if node.token && node.start < node.end {
542        emit_token(network, node_id, node.start, node.end, context);
543    }
544
545    node_id
546}
547
548fn emit_token(
549    network: &mut LinkNetwork,
550    owner: LinkId,
551    start: usize,
552    end: usize,
553    context: EmitContext<'_>,
554) -> LinkId {
555    let text = &context.text[start..end];
556    let span = span_for_range(context.lines, start, end);
557    let flags = if text.chars().all(char::is_whitespace) {
558        LinkFlags::extra()
559    } else {
560        LinkFlags::clean()
561    };
562    let token = network.insert_link(
563        [owner],
564        LinkMetadata::new()
565            .with_link_type(LinkType::Token)
566            .with_named(!text.chars().all(char::is_whitespace))
567            .with_term(text)
568            .with_language(context.language)
569            .with_span(span)
570            .with_flags(flags),
571    );
572
573    if flags.is_extra() {
574        network.attach_trivia(
575            owner,
576            token,
577            span,
578            context.configuration.trivia_attachment_policy(),
579        );
580    }
581
582    token
583}
584
585fn span_for_range(lines: &LineIndex, start: usize, end: usize) -> SourceSpan {
586    SourceSpan::new(
587        ByteRange::new(start, end),
588        lines.byte_point(start),
589        lines.byte_point(end),
590    )
591}
592
593fn starts_with_ascii_insensitive(text: &str, value: &str) -> bool {
594    text.get(..value.len())
595        .is_some_and(|prefix| prefix.eq_ignore_ascii_case(value))
596}
597
598fn class_accepts(value: char, negated: bool, items: &[CharClassItem]) -> bool {
599    let contains = items.iter().any(|item| match item {
600        CharClassItem::Char(item) => *item == value,
601        CharClassItem::Range(start, end) => *start <= value && value <= *end,
602    });
603    contains != negated
604}
605
606fn rule_term(name: &str) -> String {
607    format!("grammar::runtime::rule::{name}")
608}
609
610fn non_terminal_term(name: &str) -> String {
611    format!("grammar::runtime::expression::nonterminal::{name}")
612}
613
614fn capture_term(label: Option<&str>) -> String {
615    label.map_or_else(
616        || "grammar::runtime::capture".to_string(),
617        |label| format!("grammar::runtime::capture::{label}"),
618    )
619}
meta_language/grammar/runtime/mod.rs

meta_language/grammar/runtime/
mod.rs
