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::expr::empty";
20const EXPR_TERMINAL: &str = "grammar::runtime::expr::terminal";
21const EXPR_TERMINAL_INSENSITIVE: &str = "grammar::runtime::expr::terminal-insensitive";
22const EXPR_CHAR_RANGE: &str = "grammar::runtime::expr::char-range";
23const EXPR_CHAR_CLASS: &str = "grammar::runtime::expr::char-class";
24const EXPR_ANY_CHAR: &str = "grammar::runtime::expr::any-char";
25const EXPR_CHOICE: &str = "grammar::runtime::expr::choice";
26const EXPR_SEQUENCE: &str = "grammar::runtime::expr::sequence";
27const EXPR_OPTIONAL: &str = "grammar::runtime::expr::optional";
28const EXPR_ZERO_OR_MORE: &str = "grammar::runtime::expr::zero-or-more";
29const EXPR_ONE_OR_MORE: &str = "grammar::runtime::expr::one-or-more";
30const EXPR_REPEAT: &str = "grammar::runtime::expr::repeat";
31const EXPR_AND: &str = "grammar::runtime::expr::and";
32const EXPR_NOT: &str = "grammar::runtime::expr::not";
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        if grammar.rule(start).is_none() {
159            diagnostics.push(format!("start rule `{start}` is not defined"));
160        }
161    }
162    diagnostics.extend(
163        grammar
164            .undefined_nonterminals()
165            .into_iter()
166            .map(|rule| format!("undefined non-terminal `{rule}`")),
167    );
168    diagnostics
169}
170
171#[derive(Clone, Debug, PartialEq, Eq)]
172struct RuntimeMatcher<'grammar, 'text> {
173    grammar: &'grammar Grammar,
174    text: &'text str,
175    memo: HashMap<(String, usize), Option<ParseNode>>,
176    active: HashSet<(String, usize)>,
177}
178
179impl<'grammar, 'text> RuntimeMatcher<'grammar, 'text> {
180    fn new(grammar: &'grammar Grammar, text: &'text str) -> Self {
181        Self {
182            grammar,
183            text,
184            memo: HashMap::new(),
185            active: HashSet::new(),
186        }
187    }
188
189    fn parse_full(&mut self) -> Result<Option<ParseNode>, MatchError> {
190        let Some(start) = self.grammar.start_rule() else {
191            return Ok(None);
192        };
193        Ok(self
194            .match_rule(start.name(), 0)?
195            .filter(|node| node.end == self.text.len()))
196    }
197
198    fn match_rule(&mut self, name: &str, position: usize) -> Result<Option<ParseNode>, MatchError> {
199        if !self.valid_position(position) {
200            return Ok(None);
201        }
202
203        let key = (name.to_string(), position);
204        if let Some(cached) = self.memo.get(&key) {
205            return Ok(cached.clone());
206        }
207        if self.active.contains(&key) {
208            return Err(MatchError::LeftRecursive);
209        }
210
211        let Some(rule) = self.grammar.rule(name) else {
212            return Ok(None);
213        };
214
215        self.active.insert(key.clone());
216        let result = self.match_expr(rule.expr(), position);
217        self.active.remove(&key);
218
219        let child = result?;
220        let node = child
221            .map(|child| ParseNode::structural(rule_term(name), position, child.end, vec![child]));
222        self.memo.insert(key, node.clone());
223        Ok(node)
224    }
225
226    fn match_expr(
227        &mut self,
228        expr: &GrammarExpr,
229        position: usize,
230    ) -> Result<Option<ParseNode>, MatchError> {
231        if !self.valid_position(position) {
232            return Ok(None);
233        }
234
235        match expr {
236            GrammarExpr::Empty => Ok(Some(ParseNode::structural(
237                EXPR_EMPTY,
238                position,
239                position,
240                Vec::new(),
241            ))),
242            GrammarExpr::Terminal(value) => {
243                Ok(self.match_terminal(EXPR_TERMINAL, value, position, false))
244            }
245            GrammarExpr::TerminalInsensitive(value) => {
246                Ok(self.match_terminal(EXPR_TERMINAL_INSENSITIVE, value, position, true))
247            }
248            GrammarExpr::CharRange(start, end) => Ok(self
249                .char_at(position)
250                .filter(|(value, _next)| start <= value && value <= end)
251                .map(|(_value, next)| ParseNode::token(EXPR_CHAR_RANGE, position, next))),
252            GrammarExpr::CharClass { negated, items } => Ok(self
253                .char_at(position)
254                .filter(|(value, _next)| class_accepts(*value, *negated, items))
255                .map(|(_value, next)| ParseNode::token(EXPR_CHAR_CLASS, position, next))),
256            GrammarExpr::AnyChar => Ok(self
257                .char_at(position)
258                .map(|(_value, next)| ParseNode::token(EXPR_ANY_CHAR, position, next))),
259            GrammarExpr::NonTerminal(name) => {
260                let child = self.match_rule(name, position)?;
261                Ok(child.map(|child| {
262                    ParseNode::structural(non_terminal_term(name), position, child.end, vec![child])
263                }))
264            }
265            GrammarExpr::Choice {
266                ordered,
267                alternatives,
268            } => self.match_choice(*ordered, alternatives, position),
269            GrammarExpr::Sequence(items) => self.match_sequence(items, position),
270            GrammarExpr::Optional(inner) => {
271                if let Some(child) = self.match_expr(inner, position)? {
272                    Ok(Some(ParseNode::structural(
273                        EXPR_OPTIONAL,
274                        position,
275                        child.end,
276                        vec![child],
277                    )))
278                } else {
279                    Ok(Some(ParseNode::structural(
280                        EXPR_OPTIONAL,
281                        position,
282                        position,
283                        Vec::new(),
284                    )))
285                }
286            }
287            GrammarExpr::ZeroOrMore(inner) => {
288                self.match_repetition(EXPR_ZERO_OR_MORE, inner, position, 0, None)
289            }
290            GrammarExpr::OneOrMore(inner) => {
291                self.match_repetition(EXPR_ONE_OR_MORE, inner, position, 1, None)
292            }
293            GrammarExpr::Repeat { expr, min, max } => {
294                self.match_repetition(EXPR_REPEAT, expr, position, *min, *max)
295            }
296            GrammarExpr::And(inner) => {
297                if self.match_expr(inner, position)?.is_some() {
298                    Ok(Some(ParseNode::structural(
299                        EXPR_AND,
300                        position,
301                        position,
302                        Vec::new(),
303                    )))
304                } else {
305                    Ok(None)
306                }
307            }
308            GrammarExpr::Not(inner) => {
309                if self.match_expr(inner, position)?.is_none() {
310                    Ok(Some(ParseNode::structural(
311                        EXPR_NOT,
312                        position,
313                        position,
314                        Vec::new(),
315                    )))
316                } else {
317                    Ok(None)
318                }
319            }
320            GrammarExpr::Capture { label, expr } => {
321                let child = self.match_expr(expr, position)?;
322                Ok(child.map(|child| {
323                    ParseNode::structural(
324                        capture_term(label.as_deref()),
325                        position,
326                        child.end,
327                        vec![child],
328                    )
329                }))
330            }
331        }
332    }
333
334    fn match_choice(
335        &mut self,
336        ordered: bool,
337        alternatives: &[GrammarExpr],
338        position: usize,
339    ) -> Result<Option<ParseNode>, MatchError> {
340        if ordered {
341            for alternative in alternatives {
342                if let Some(child) = self.match_expr(alternative, position)? {
343                    return Ok(Some(ParseNode::structural(
344                        EXPR_CHOICE,
345                        position,
346                        child.end,
347                        vec![child],
348                    )));
349                }
350            }
351            return Ok(None);
352        }
353
354        let mut best: Option<ParseNode> = None;
355        for alternative in alternatives {
356            let candidate = self.match_expr(alternative, position)?;
357            let replace_best = candidate
358                .as_ref()
359                .is_some_and(|node| best.as_ref().map_or(true, |best| node.end > best.end));
360            if replace_best {
361                best = candidate;
362            }
363        }
364
365        Ok(best.map(|child| ParseNode::structural(EXPR_CHOICE, position, child.end, vec![child])))
366    }
367
368    fn match_sequence(
369        &mut self,
370        items: &[GrammarExpr],
371        position: usize,
372    ) -> Result<Option<ParseNode>, MatchError> {
373        let mut current = position;
374        let mut children = Vec::with_capacity(items.len());
375        for item in items {
376            let Some(child) = self.match_expr(item, current)? else {
377                return Ok(None);
378            };
379            current = child.end;
380            children.push(child);
381        }
382
383        Ok(Some(ParseNode::structural(
384            EXPR_SEQUENCE,
385            position,
386            current,
387            children,
388        )))
389    }
390
391    fn match_repetition(
392        &mut self,
393        term: &'static str,
394        inner: &GrammarExpr,
395        position: usize,
396        min: usize,
397        max: Option<usize>,
398    ) -> Result<Option<ParseNode>, MatchError> {
399        if max.is_some_and(|max| max < min) {
400            return Ok(None);
401        }
402
403        let mut current = position;
404        let mut count = 0;
405        let mut children = Vec::new();
406        loop {
407            if max.is_some_and(|max| count >= max) {
408                break;
409            }
410
411            let Some(child) = self.match_expr(inner, current)? else {
412                break;
413            };
414
415            if child.end == current {
416                if count < min {
417                    count = min;
418                    children.push(child);
419                }
420                break;
421            }
422
423            current = child.end;
424            count += 1;
425            children.push(child);
426        }
427
428        if count >= min {
429            Ok(Some(ParseNode::structural(
430                term, position, current, children,
431            )))
432        } else {
433            Ok(None)
434        }
435    }
436
437    fn match_terminal(
438        &self,
439        term: &'static str,
440        value: &str,
441        position: usize,
442        insensitive: bool,
443    ) -> Option<ParseNode> {
444        let matches = if insensitive {
445            starts_with_ascii_insensitive(&self.text[position..], value)
446        } else {
447            self.text[position..].starts_with(value)
448        };
449        matches.then(|| ParseNode::token(term, position, position + value.len()))
450    }
451
452    fn char_at(&self, position: usize) -> Option<(char, usize)> {
453        self.text[position..]
454            .chars()
455            .next()
456            .map(|value| (value, position + value.len_utf8()))
457    }
458
459    fn valid_position(&self, position: usize) -> bool {
460        position <= self.text.len() && self.text.is_char_boundary(position)
461    }
462}
463
464#[derive(Clone, Debug, PartialEq, Eq)]
465enum MatchError {
466    LeftRecursive,
467}
468
469#[derive(Clone, Debug, PartialEq, Eq)]
470struct ParseNode {
471    term: String,
472    start: usize,
473    end: usize,
474    children: Vec<Self>,
475    token: bool,
476}
477
478impl ParseNode {
479    fn structural(term: impl Into<String>, start: usize, end: usize, children: Vec<Self>) -> Self {
480        Self {
481            term: term.into(),
482            start,
483            end,
484            children,
485            token: false,
486        }
487    }
488
489    fn token(term: impl Into<String>, start: usize, end: usize) -> Self {
490        Self {
491            term: term.into(),
492            start,
493            end,
494            children: Vec::new(),
495            token: true,
496        }
497    }
498}
499
500#[derive(Clone, Copy, Debug)]
501struct EmitContext<'source> {
502    text: &'source str,
503    lines: &'source LineIndex,
504    language: &'source str,
505    configuration: ParseConfiguration,
506}
507
508fn emit_parse_node(
509    network: &mut LinkNetwork,
510    owner: LinkId,
511    node: &ParseNode,
512    context: EmitContext<'_>,
513) -> LinkId {
514    let span = span_for_range(context.lines, node.start, node.end);
515    let node_id = network.insert_link(
516        [owner],
517        LinkMetadata::new()
518            .with_link_type(LinkType::Grammar)
519            .with_named(true)
520            .with_term(&node.term)
521            .with_language(context.language)
522            .with_span(span)
523            .with_flags(LinkFlags::clean()),
524    );
525
526    for child in &node.children {
527        emit_parse_node(network, node_id, child, context);
528    }
529
530    if node.token && node.start < node.end {
531        emit_token(network, node_id, node.start, node.end, context);
532    }
533
534    node_id
535}
536
537fn emit_token(
538    network: &mut LinkNetwork,
539    owner: LinkId,
540    start: usize,
541    end: usize,
542    context: EmitContext<'_>,
543) -> LinkId {
544    let text = &context.text[start..end];
545    let span = span_for_range(context.lines, start, end);
546    let flags = if text.chars().all(char::is_whitespace) {
547        LinkFlags::extra()
548    } else {
549        LinkFlags::clean()
550    };
551    let token = network.insert_link(
552        [owner],
553        LinkMetadata::new()
554            .with_link_type(LinkType::Token)
555            .with_named(!text.chars().all(char::is_whitespace))
556            .with_term(text)
557            .with_language(context.language)
558            .with_span(span)
559            .with_flags(flags),
560    );
561
562    if flags.is_extra() {
563        network.attach_trivia(
564            owner,
565            token,
566            span,
567            context.configuration.trivia_attachment_policy(),
568        );
569    }
570
571    token
572}
573
574fn span_for_range(lines: &LineIndex, start: usize, end: usize) -> SourceSpan {
575    SourceSpan::new(
576        ByteRange::new(start, end),
577        lines.byte_point(start),
578        lines.byte_point(end),
579    )
580}
581
582fn starts_with_ascii_insensitive(text: &str, value: &str) -> bool {
583    text.get(..value.len())
584        .is_some_and(|prefix| prefix.eq_ignore_ascii_case(value))
585}
586
587fn class_accepts(value: char, negated: bool, items: &[CharClassItem]) -> bool {
588    let contains = items.iter().any(|item| match item {
589        CharClassItem::Char(item) => *item == value,
590        CharClassItem::Range(start, end) => *start <= value && value <= *end,
591    });
592    contains != negated
593}
594
595fn rule_term(name: &str) -> String {
596    format!("grammar::runtime::rule::{name}")
597}
598
599fn non_terminal_term(name: &str) -> String {
600    format!("grammar::runtime::expr::non-terminal::{name}")
601}
602
603fn capture_term(label: Option<&str>) -> String {
604    label.map_or_else(
605        || "grammar::runtime::capture".to_string(),
606        |label| format!("grammar::runtime::capture::{label}"),
607    )
608}
meta_language/grammar/runtime/mod.rs

meta_language/grammar/runtime/
mod.rs
