meta_language/grammar/feature_runtime/
mod.rs

1//! The native executor of the grammar feature union, the Rust port of
2//! `js/src/grammar-runtime.js`.
3//!
4//! Compile a grammar once, then parse sources into lossless concrete syntax
5//! trees. Loading (`load.rs`, `compile.rs`)
6//! resolves imports, macros and parameterized rules and checks every
7//! scanner, action and predicate; the executor (`executor.rs`, `rules.rs`)
8//! runs it within explicit resource limits; `tree.rs` copies and renders the
9//! result. docs/grammar/feature-union.md is the specification both
10//! runtimes follow.
11
12mod compile;
13mod executor;
14mod forking;
15mod joins;
16mod keyword_lexing;
17mod lexing;
18mod load;
19mod operations;
20mod ordering;
21mod parting;
22mod precedence;
23mod program;
24mod reducing;
25mod repetition;
26mod results;
27mod roots;
28mod rules;
29mod separators;
30mod text;
31mod token_conflicts;
32mod token_ranks;
33mod tree;
34mod walk;
35
36use std::cell::{Cell, RefCell};
37use std::collections::HashSet;
38use std::fmt;
39use std::rc::Rc;
40
41pub use load::GrammarRuntimeError;
42pub use operations::OperationValue;
43pub use tree::{Ambiguity, LeafText, SyntaxAttributes, SyntaxTree};
44
45use super::Grammar;
46use super::decorators::{decorate_grammar, decorate_syntax_tree};
47use crate::decorators::{DecoratorError, DecoratorLevel, DecoratorSet};
48use executor::Executor;
49use operations::Abort;
50use program::{Compiled, SettlingStep};
51use results::{Expectations, KeywordLexing, Outcome, Shared, TokenOrder};
52
53/// The default bound on nested rule calls.
54const DEFAULT_MAX_DEPTH: usize = 1000;
55/// The default bound on memoized rule calls.
56const DEFAULT_MEMO_LIMIT: usize = 1_000_000;
57/// The default memory budget of a parse, in memo cells.
58const DEFAULT_MEMORY_LIMIT: usize = 2_000_000;
59/// The stack of the thread a parse runs on; the executor's frame bound keeps
60/// a parse well inside it.
61const PARSE_STACK: usize = 256 * 1024 * 1024;
62
63/// The limits and policies of a parse. Every field left `None` keeps the
64/// value the parser was compiled with, and then the default.
65#[derive(Clone, Debug, Default, PartialEq, Eq)]
66pub struct FeatureParseOptions {
67    /// The rule to parse from instead of the grammar's start rule.
68    pub start_rule: Option<String>,
69    /// The bound on nested rule calls (default 1000).
70    pub max_depth: Option<usize>,
71    /// The bound on evaluation steps (default `100000 + 1000 * input length`,
72    /// twice that with error recovery).
73    pub step_limit: Option<usize>,
74    /// The bound on memoized rule calls (default 1000000).
75    pub memo_limit: Option<usize>,
76    /// The memory budget of the whole parse, its runs, repair rounds and
77    /// embedded languages included, in memo cells: one per rule call recorded
78    /// and one per result such a call keeps, counted and never released
79    /// (default 2000000). A parse that needs more is rejected with
80    /// `memoryBudget` instead of growing.
81    pub memory_limit: Option<usize>,
82    /// Whether a reported ambiguity rejects the input (default false).
83    pub reject_ambiguity: Option<bool>,
84    /// Whether a tree with ERROR or MISSING nodes is accepted (default false).
85    pub accept_recovery: Option<bool>,
86    /// Whether a failed parse is repaired into a tree with ERROR or MISSING
87    /// nodes instead of rejected without a tree (default false).
88    pub error_recovery: Option<bool>,
89    /// The bound on repair points of automatic recovery (default 32).
90    pub max_repairs: Option<usize>,
91    /// Decorators of the `grammar-rule` level, applied to the grammar a
92    /// parser is compiled from, and of the `executor` and `recovery` levels,
93    /// applied to every tree (see [`decorate_syntax_tree`]). An empty set
94    /// keeps the decorators the parser was compiled with.
95    pub decorators: DecoratorSet,
96}
97
98impl FeatureParseOptions {
99    fn over(&self, base: &Self) -> Self {
100        Self {
101            start_rule: self.start_rule.clone().or_else(|| base.start_rule.clone()),
102            max_depth: self.max_depth.or(base.max_depth),
103            step_limit: self.step_limit.or(base.step_limit),
104            memo_limit: self.memo_limit.or(base.memo_limit),
105            memory_limit: self.memory_limit.or(base.memory_limit),
106            reject_ambiguity: self.reject_ambiguity.or(base.reject_ambiguity),
107            accept_recovery: self.accept_recovery.or(base.accept_recovery),
108            error_recovery: self.error_recovery.or(base.error_recovery),
109            max_repairs: self.max_repairs.or(base.max_repairs),
110            decorators: if self.decorators.is_empty() {
111                base.decorators.clone()
112            } else {
113                self.decorators.clone()
114            },
115        }
116    }
117}
118
119/// Why a parse rejects its input, and where.
120#[derive(Clone, Debug, PartialEq, Eq)]
121pub struct ParseRejection {
122    /// `syntax`, `nestingDepth`, `stepLimit`, `memoryBudget`, `recovered` or
123    /// `ambiguity`.
124    pub reason: &'static str,
125    /// The byte offset, for a positioned rejection.
126    pub offset: Option<usize>,
127    /// The 1-based line of the offset.
128    pub line: Option<usize>,
129    /// The 1-based column of the offset, in code points.
130    pub column: Option<usize>,
131    /// What a syntax error expected at the offset, sorted.
132    pub expected: Option<Vec<String>>,
133    /// The limit a resource rejection reached.
134    pub limit: Option<usize>,
135}
136
137impl ParseRejection {
138    const fn limited(reason: &'static str, limit: usize) -> Self {
139        Self {
140            reason,
141            offset: None,
142            line: None,
143            column: None,
144            expected: None,
145            limit: Some(limit),
146        }
147    }
148
149    fn positioned(reason: &'static str, bytes: &[u8], offset: usize) -> Self {
150        let (line, column) = text::line_and_column(bytes, offset);
151        Self {
152            reason,
153            offset: Some(offset),
154            line: Some(line),
155            column: Some(column),
156            expected: None,
157            limit: None,
158        }
159    }
160}
161
162impl fmt::Display for ParseRejection {
163    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
164        let place = match (self.line, self.column) {
165            (Some(line), Some(column)) => format!(" at line {line} column {column}"),
166            _ => String::new(),
167        };
168        let limit = self.limit.unwrap_or_default();
169        match self.reason {
170            "syntax" => {
171                let expected = self.expected.as_deref().unwrap_or_default();
172                let expected = if expected.is_empty() {
173                    "nothing more".to_owned()
174                } else {
175                    expected.join(", ")
176                };
177                write!(formatter, "syntax error{place}: expected {expected}")
178            }
179            "nestingDepth" => write!(formatter, "the input nests deeper than {limit} rules"),
180            "stepLimit" => write!(formatter, "the parse needed more than {limit} steps"),
181            "memoryBudget" => write!(formatter, "the parse needed more than {limit} memo cells"),
182            "recovered" => write!(formatter, "the input needed error recovery{place}"),
183            "ambiguity" => write!(formatter, "the input is ambiguous{place}"),
184            reason => write!(formatter, "the input is rejected ({reason})"),
185        }
186    }
187}
188
189/// The outcome of one parse: `ok` only without a rejection; the tree is kept
190/// whenever one was built.
191#[derive(Clone, Debug, PartialEq, Eq)]
192pub struct ParseOutcome {
193    /// Whether the input is accepted.
194    pub ok: bool,
195    /// The concrete syntax tree, when one was built.
196    pub tree: Option<SyntaxTree>,
197    /// The ambiguous nodes outside the declared conflicts.
198    pub ambiguities: Vec<Ambiguity>,
199    /// Why the input is rejected.
200    pub rejection: Option<ParseRejection>,
201}
202
203/// A source the grammar rejects.
204#[derive(Clone, Debug, PartialEq, Eq)]
205pub struct GrammarParseError {
206    /// The reason and position.
207    pub rejection: ParseRejection,
208}
209
210impl fmt::Display for GrammarParseError {
211    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
212        self.rejection.fmt(formatter)
213    }
214}
215
216impl std::error::Error for GrammarParseError {}
217
218/// Returns the grammar an import or an embedded language names.
219pub type GrammarResolver<'a> = &'a dyn Fn(&str) -> Option<Grammar>;
220
221/// A grammar compiled for the native executor.
222#[derive(Debug)]
223pub struct FeatureGrammarParser {
224    compiled: Compiled,
225    options: FeatureParseOptions,
226}
227
228/// Compiles `grammar` for the native executor. `resolve_grammar(name)`
229/// returns the grammar an import or an embedded language names; `options`
230/// are the defaults of every parse.
231///
232/// # Errors
233///
234/// A [`GrammarRuntimeError`] when an import, a macro, a parameterized rule,
235/// an operation, a mode, a Unicode property or an embedded language does not
236/// load; its `reason` names which.
237pub fn compile_feature_grammar(
238    grammar: &Grammar,
239    resolve_grammar: Option<GrammarResolver<'_>>,
240    options: FeatureParseOptions,
241) -> Result<FeatureGrammarParser, GrammarRuntimeError> {
242    let decorated = decorate_grammar(grammar, &options.decorators, DecoratorLevel::GrammarRule)
243        .map_err(decorator_error)?;
244    Ok(FeatureGrammarParser {
245        compiled: load::load(&decorated, resolve_grammar)?,
246        options,
247    })
248}
249
250impl FeatureGrammarParser {
251    /// Parses `source` into an outcome that keeps the tree, the ambiguities
252    /// and the rejection.
253    ///
254    /// # Errors
255    ///
256    /// A [`GrammarRuntimeError`] with reason `reference` when the start rule
257    /// is not a rule of the grammar.
258    pub fn parse_tree(
259        &self,
260        source: &[u8],
261        options: &FeatureParseOptions,
262    ) -> Result<ParseOutcome, GrammarRuntimeError> {
263        let options = options.over(&self.options);
264        let program = &self.compiled.programs[self.compiled.main];
265        let start_name = options
266            .start_rule
267            .clone()
268            .or_else(|| program.start.clone())
269            .unwrap_or_default();
270        let Some(&start_rule) = program.rule_index.get(&start_name) else {
271            return Err(GrammarRuntimeError {
272                reason: "reference",
273                message: format!("undefined start rule {start_name}"),
274            });
275        };
276        let compiled = &self.compiled;
277        let mut outcome = std::thread::scope(|scope| {
278            std::thread::Builder::new()
279                .stack_size(PARSE_STACK)
280                .spawn_scoped(scope, || {
281                    parse_program(compiled, start_rule, source, &options)
282                })
283                .map_or_else(
284                    |_| parse_program(compiled, start_rule, source, &options),
285                    |handle| {
286                        handle
287                            .join()
288                            .unwrap_or_else(|panic| std::panic::resume_unwind(panic))
289                    },
290                )
291        });
292        if let Some(tree) = &outcome.tree {
293            outcome.tree = Some(
294                decorate_syntax_tree(tree, &options.decorators, source).map_err(decorator_error)?,
295            );
296        }
297        Ok(outcome)
298    }
299
300    /// Parses `source` into its concrete syntax tree.
301    ///
302    /// # Errors
303    ///
304    /// A [`GrammarParseError`] when the input is rejected; a rejected start
305    /// rule is reported as a syntax rejection at offset 0.
306    pub fn parse(
307        &self,
308        source: &[u8],
309        options: &FeatureParseOptions,
310    ) -> Result<SyntaxTree, GrammarParseError> {
311        let outcome = self
312            .parse_tree(source, options)
313            .map_err(|_| GrammarParseError {
314                rejection: ParseRejection::positioned("syntax", source, 0),
315            })?;
316        match (outcome.rejection, outcome.tree) {
317            (None, Some(tree)) => Ok(tree),
318            (rejection, _) => Err(GrammarParseError {
319                rejection: rejection
320                    .unwrap_or_else(|| ParseRejection::positioned("syntax", source, 0)),
321            }),
322        }
323    }
324}
325
326/// Why [`parse_with_grammar`] produced no tree: the grammar did not compile,
327/// or the source did not parse.
328#[derive(Clone, Debug, PartialEq, Eq)]
329pub enum ParseWithGrammarError {
330    /// The grammar did not load for the native executor.
331    Runtime(GrammarRuntimeError),
332    /// The source was rejected.
333    Parse(GrammarParseError),
334}
335
336impl fmt::Display for ParseWithGrammarError {
337    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
338        match self {
339            Self::Runtime(error) => error.fmt(formatter),
340            Self::Parse(error) => error.fmt(formatter),
341        }
342    }
343}
344
345impl std::error::Error for ParseWithGrammarError {}
346
347/// Compiles `grammar` with `options` and parses `source` with the same
348/// options, as the JavaScript `parseWithGrammar` does.
349///
350/// # Errors
351///
352/// [`ParseWithGrammarError::Runtime`] when the grammar does not compile and
353/// [`ParseWithGrammarError::Parse`] when the source is rejected.
354pub fn parse_with_grammar(
355    grammar: &Grammar,
356    source: &[u8],
357    options: &FeatureParseOptions,
358) -> Result<SyntaxTree, ParseWithGrammarError> {
359    compile_feature_grammar(grammar, None, options.clone())
360        .map_err(ParseWithGrammarError::Runtime)?
361        .parse(source, options)
362        .map_err(ParseWithGrammarError::Parse)
363}
364
365fn decorator_error(error: DecoratorError) -> GrammarRuntimeError {
366    GrammarRuntimeError {
367        reason: "decorator",
368        message: error.message,
369    }
370}
371
372/// The default bound on repair points of automatic recovery.
373const DEFAULT_MAX_REPAIRS: usize = 32;
374
375/// Automatic error recovery after a failed parse: each round reparses with
376/// one more repair point, the farthest offset where an element failed without
377/// a repair, until a parse completes. After `max_repairs` rounds, or when no
378/// new point appears, the last round's partial tree stands, the rest of the
379/// input an ERROR leaf. Each round has its own step budget; a round that
380/// runs out of steps ends the rounds as well.
381fn repair_parse(
382    failed: Outcome,
383    max_repairs: usize,
384    attempt: impl Fn(Option<&HashSet<usize>>) -> Result<Outcome, Abort>,
385) -> Result<Outcome, Abort> {
386    let mut points = HashSet::new();
387    let mut outcome = failed;
388    while points.len() < max_repairs {
389        let Outcome::Failed {
390            farthest,
391            element_farthest,
392            ..
393        } = &outcome
394        else {
395            break;
396        };
397        if !points.insert(element_farthest.unwrap_or(*farthest)) {
398            break;
399        }
400        outcome = match attempt(Some(&points)) {
401            Err(Abort::StepLimit) => break,
402            attempted => attempted?,
403        };
404        if matches!(outcome, Outcome::Parsed(_)) {
405            return Ok(outcome);
406        }
407    }
408    Ok(match outcome {
409        Outcome::Failed {
410            partial: Some(partial),
411            ..
412        } => Outcome::Parsed(partial),
413        outcome => outcome,
414    })
415}
416
417fn parse_program(
418    compiled: &Compiled,
419    start_rule: usize,
420    bytes: &[u8],
421    options: &FeatureParseOptions,
422) -> ParseOutcome {
423    let max_depth = options.max_depth.unwrap_or(DEFAULT_MAX_DEPTH);
424    // Error recovery parses each repaired alternative too: twice the budget.
425    let limit = options.step_limit.unwrap_or_else(|| {
426        (100_000 + 1000 * bytes.len())
427            * if options.error_recovery == Some(true) {
428                2
429            } else {
430                1
431            }
432    });
433    let refused = |rejection, tree| ParseOutcome {
434        ok: false,
435        tree,
436        ambiguities: Vec::new(),
437        rejection: Some(rejection),
438    };
439    // Under `(matching longest)` the input is parsed again while the tree
440    // takes a token rule's leaf where a keyword a lexer prefers matched.
441    let tokens = compiled.programs[compiled.main]
442        .token_ranks
443        .as_ref()
444        .filter(|_| {
445            compiled.programs[compiled.main]
446                .settling
447                .has(SettlingStep::Tokens)
448        })
449        .map(|ranks| TokenOrder {
450            ranks,
451            bytes,
452            orders: &compiled.programs[compiled.main].precedence_orders,
453            grammar: &compiled.programs[compiled.main].grammar,
454            trivia: &compiled.programs[compiled.main].trivia,
455        });
456    let keywords = tokens.map(|_| RefCell::new(KeywordLexing::default()));
457    let expectations = RefCell::new(Expectations::default());
458    // Every run and repair round takes its memo cells of the one budget.
459    let memory_limit = options.memory_limit.unwrap_or(DEFAULT_MEMORY_LIMIT);
460    let cells = Rc::new(Cell::new(0));
461    // Parses the whole input with a fresh executor. While a scanner's
462    // `expected` was answered before the parse made the request it asks
463    // about, the parse runs again with the requests so far (see
464    // `Expectations`). Each run has its own step budget.
465    let attempt = |points: Option<&HashSet<usize>>| loop {
466        let mut record = expectations.take();
467        record.restart();
468        let shared = Shared {
469            steps: Cell::new(0),
470            limit,
471            frames: Cell::new(0),
472            memo_limit: options.memo_limit.unwrap_or(DEFAULT_MEMO_LIMIT),
473            cells: Rc::clone(&cells),
474            memory_limit,
475            expectations: RefCell::new(record),
476        };
477        let outcome = {
478            let mut executor = Executor::new(
479                compiled,
480                compiled.main,
481                bytes,
482                0,
483                bytes.len(),
484                &shared,
485                max_depth,
486            );
487            executor.repair_points = points.cloned();
488            executor.keywords = keywords.as_ref();
489            executor.run(start_rule)
490        };
491        let record = shared.expectations.into_inner();
492        let stale = record.stale;
493        expectations.replace(record);
494        if outcome.is_err() || !stale {
495            break outcome;
496        }
497    };
498    let recovery = options.error_recovery == Some(true);
499    let outcome = loop {
500        // With no repair point yet, recovery only notes where elements fail.
501        let outcome =
502            attempt(recovery.then(HashSet::new).as_ref()).and_then(|outcome| match outcome {
503                Outcome::Failed { .. } if recovery => repair_parse(
504                    outcome,
505                    options.max_repairs.unwrap_or(DEFAULT_MAX_REPAIRS),
506                    attempt,
507                ),
508                outcome => Ok(outcome),
509            });
510        if let (Ok(Outcome::Parsed(root)), Some(keywords), Some(tokens)) =
511            (&outcome, &keywords, tokens)
512            && keywords.borrow_mut().conflicts(
513                root,
514                tokens,
515                &compiled.programs[compiled.main].rules,
516            )
517        {
518            continue;
519        }
520        break outcome;
521    };
522    let root = match outcome {
523        Err(Abort::StepLimit) => {
524            return refused(ParseRejection::limited("stepLimit", limit), None);
525        }
526        Err(Abort::MemoryBudget) => {
527            return refused(ParseRejection::limited("memoryBudget", memory_limit), None);
528        }
529        Err(Abort::NestingTooDeep) => {
530            let tree = tree::error_tree(bytes, 0, bytes.len(), Some("nestingDepth"));
531            return refused(
532                ParseRejection::limited("nestingDepth", max_depth),
533                Some(tree),
534            );
535        }
536        Ok(Outcome::Failed {
537            farthest, expected, ..
538        }) => {
539            let mut rejection = ParseRejection::positioned("syntax", bytes, farthest);
540            rejection.expected = Some(expected);
541            return refused(rejection, None);
542        }
543        Ok(Outcome::Parsed(root)) => root,
544    };
545    let tree = tree::public_tree(&root, bytes);
546    let mut ambiguities = Vec::new();
547    tree::collect_ambiguities(&root, compiled, compiled.main, &mut ambiguities);
548    let recovered = tree
549        .first_recovery()
550        .filter(|_| options.accept_recovery != Some(true))
551        .map(|recovery| ParseRejection::positioned("recovered", bytes, recovery.start()));
552    let rejection = recovered.or_else(|| {
553        ambiguities
554            .first()
555            .filter(|_| options.reject_ambiguity == Some(true))
556            .map(|first| ParseRejection::positioned("ambiguity", bytes, first.start))
557    });
558    ParseOutcome {
559        ok: rejection.is_none(),
560        tree: Some(tree),
561        ambiguities,
562        rejection,
563    }
564}
meta_language/grammar/feature_runtime/mod.rs

meta_language/grammar/feature_runtime/
mod.rs
