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

meta_language/grammar/runtime/
mod.rs
