meta_language/grammar/interchange/lowering/
mod.rs

1//! Faithful lowering of a grammar into a less expressive grammar notation.
2//!
3//! Every construct the target notation cannot write so that its own importer
4//! reads it back unchanged is moved into a fresh helper rule whose body is an
5//! encoding in constructs the target does write: an optional item becomes a
6//! choice with the empty expression, a repetition a recursive helper, a
7//! character set a choice of its characters, a case-insensitive literal a
8//! sequence of per-letter character sets, a capture its item. Each rewrite is
9//! a step of the reconstruction metadata, which names the helper, the rule it
10//! was lowered from, the construct, whether the encoding is exact (accepts the
11//! same texts) or approximate (an ordered choice written as an unordered one, a
12//! lookahead written as the empty expression, an arbitrary character limited
13//! to printable ASCII), a note and the original expression as native links.
14//! Rule names, kinds and documentation the target does not keep are metadata
15//! steps as well, and so are the declarations of the grammar feature union
16//! (matching, imports, modes, extras, conflicts, macros and scanners) and the
17//! rule parameters, channels, modes and actions: no target notation writes
18//! them, so the executable does not honor them and a lowering that carries
19//! them is approximate. The executable grammar (the emitted text) is therefore
20//! distinct from the lossless interchange package (executable plus metadata),
21//! and [`check_grammar_lowering`] reconstructs the original from the package
22//! and reports every feature the package does not carry. It mirrors
23//! `js/src/grammar-lowering.js`.
24
25use std::collections::{HashMap, HashSet};
26use std::error::Error;
27use std::fmt;
28
29use super::super::emit::{EmitReport, GrammarEmitError};
30use super::super::import::GrammarImportError;
31use super::super::round_trip::{GrammarEmitFn, GrammarImportFn, GrammarRoundTripError};
32use super::super::{Grammar, GrammarExpr, GrammarFormat, GrammarRule, RuleAttributes, RuleKind};
33use super::links::render_links_expression;
34use super::{grammar_emitter, grammar_importer, render_rule_fields};
35
36mod encoding;
37mod metadata;
38
39use encoding::{Construct, constructs_of, encode, kept_kinds, unsupported};
40use metadata::render_declarations_text;
41
42pub use encoding::MAX_LOWERED_CHARACTERS;
43
44pub use metadata::{
45    GrammarLoweringFailure, GrammarLoweringFailureKind, GrammarLoweringReport,
46    check_grammar_lowering, dropped_grammar_features, parse_lowering_metadata, reconstruct_grammar,
47    render_lowering_metadata,
48};
49
50/// The notations the lowering writes.
51pub const GRAMMAR_LOWERING_FORMATS: &[&str] = &[
52    "abnf",
53    "antlr",
54    "bnf",
55    "ebnf",
56    "gbnf",
57    "lark",
58    "pest",
59    "tree-sitter-json",
60];
61
62const HELPER_PREFIX: &str = "lowered";
63
64/// Whether a lowering kept every encoding exact.
65#[derive(Clone, Copy, Debug, PartialEq, Eq)]
66pub enum GrammarLoweringStatus {
67    /// Every encoding accepts the same texts as the original.
68    Exact,
69    /// At least one encoding accepts different texts.
70    Approximate,
71    /// A check of the lowering failed.
72    Broken,
73}
74
75impl GrammarLoweringStatus {
76    /// Stable tag shared with the JavaScript runtime.
77    #[must_use]
78    pub const fn as_str(self) -> &'static str {
79        match self {
80            Self::Exact => "exact",
81            Self::Approximate => "approximate",
82            Self::Broken => "broken",
83        }
84    }
85}
86
87/// Whether one helper accepts the same texts as the expression it replaces.
88#[derive(Clone, Copy, Debug, PartialEq, Eq)]
89pub enum GrammarLoweringEncoding {
90    /// The helper accepts the same texts.
91    Exact,
92    /// The helper accepts different texts.
93    Approximate,
94}
95
96impl GrammarLoweringEncoding {
97    /// Stable tag shared with the JavaScript runtime.
98    #[must_use]
99    pub const fn as_str(self) -> &'static str {
100        match self {
101            Self::Exact => "exact",
102            Self::Approximate => "approximate",
103        }
104    }
105}
106
107/// One step of the reconstruction metadata.
108#[derive(Clone, Debug, PartialEq, Eq)]
109pub enum GrammarLoweringStep {
110    /// The target writes `rule` under the name `value`.
111    Rename {
112        /// The original rule name.
113        rule: String,
114        /// The name in the executable grammar.
115        value: String,
116    },
117    /// An expression of `owner` moved into the helper rule `helper`.
118    Helper {
119        /// The helper rule name.
120        helper: String,
121        /// The rule the expression was lowered from.
122        owner: String,
123        /// The construct the target does not write.
124        construct: String,
125        /// Whether the helper accepts the same texts.
126        encoding: GrammarLoweringEncoding,
127        /// How the helper encodes the construct.
128        note: String,
129        /// The expression the helper replaces.
130        original: GrammarExpr,
131    },
132    /// The target does not keep the kind of `rule`.
133    Kind {
134        /// The original rule name.
135        rule: String,
136        /// The original rule kind.
137        kind: RuleKind,
138    },
139    /// The target does not keep the documentation of `rule` verbatim.
140    Doc {
141        /// The original rule name.
142        rule: String,
143        /// The original documentation.
144        doc: String,
145    },
146    /// The feature union declarations of the grammar, which no target writes
147    /// and the executable does not honor.
148    Declarations {
149        /// The declarations as native links: a grammar link with the
150        /// matching, then one link per declaration, each on its own line.
151        declarations: String,
152    },
153    /// The parameters, channel, modes and action of `rule`, which no target
154    /// writes and the executable does not honor.
155    Attributes {
156        /// The original rule name.
157        rule: String,
158        /// The rule fields as native links, separated by spaces.
159        attributes: String,
160    },
161}
162
163/// The reconstruction metadata of a lowering.
164#[derive(Clone, Debug, PartialEq, Eq)]
165pub struct GrammarLoweringMetadata {
166    /// The target notation, one of [`GRAMMAR_LOWERING_FORMATS`].
167    pub format: String,
168    /// Whether every encoding is exact.
169    pub status: GrammarLoweringStatus,
170    /// The source format of the original grammar.
171    pub source: Option<GrammarFormat>,
172    /// The original start rule.
173    pub start: String,
174    /// The original rule names in grammar order.
175    pub order: Vec<String>,
176    /// The steps in the order they were taken.
177    pub steps: Vec<GrammarLoweringStep>,
178}
179
180/// A grammar lowered into one notation.
181#[derive(Clone, Debug, PartialEq, Eq)]
182pub struct GrammarLowering {
183    /// The target notation.
184    pub format: String,
185    /// Whether every encoding is exact.
186    pub status: GrammarLoweringStatus,
187    /// The lowered grammar under the names the target gives its rules.
188    pub grammar: Grammar,
189    /// The executable text the target emitter writes for it.
190    pub executable: String,
191    /// The emitter's fidelity report for the executable.
192    pub report: EmitReport,
193    /// The grammar the target importer reads from the executable.
194    pub imported: Grammar,
195    /// The reconstruction steps.
196    pub steps: Vec<GrammarLoweringStep>,
197    /// The reconstruction metadata as links.
198    pub metadata: String,
199}
200
201/// The emitter, importer, samples and metadata edit a lowering runs with.
202#[derive(Clone, Copy, Default)]
203pub struct GrammarLoweringOptions<'a> {
204    /// Replaces the target's own emitter.
205    pub emit: Option<GrammarEmitFn<'a>>,
206    /// Replaces the target's own importer.
207    pub import: Option<GrammarImportFn<'a>>,
208    /// Texts an exact lowering must accept.
209    pub accepts: &'a [String],
210    /// Texts an exact lowering must reject.
211    pub rejects: &'a [String],
212    /// Rewrites the metadata before the reconstruction, for negative controls.
213    pub edit_metadata: Option<&'a dyn Fn(&str) -> String>,
214}
215
216/// A lowering or reconstruction that cannot be carried out.
217#[derive(Clone, Debug, PartialEq, Eq)]
218pub enum GrammarLoweringError {
219    /// The format is not one of [`GRAMMAR_LOWERING_FORMATS`].
220    UnsupportedFormat(String),
221    /// The grammar has no start rule.
222    NoStartRule,
223    /// A character set holds no character the format can spell.
224    Unencodable(String),
225    /// The executable grammar has no rule of this name.
226    MissingRule(String),
227    /// The importer rejected the executable or the metadata is malformed.
228    Import(GrammarImportError),
229    /// The emitter rejected the lowered grammar.
230    Emit(GrammarEmitError),
231    /// A rule definition could not be normalized for comparison.
232    Definition(GrammarRoundTripError),
233}
234
235impl fmt::Display for GrammarLoweringError {
236    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
237        match self {
238            Self::UnsupportedFormat(format) => write!(
239                formatter,
240                "the lowering does not support the format {format}"
241            ),
242            Self::NoStartRule => formatter.write_str("the grammar has no start rule"),
243            Self::Unencodable(format) => write!(
244                formatter,
245                "a character set without printable ASCII characters cannot be written in {format}"
246            ),
247            Self::MissingRule(name) => {
248                write!(formatter, "the executable grammar has no rule {name}")
249            }
250            Self::Import(error) => write!(formatter, "{error}"),
251            Self::Emit(error) => write!(formatter, "{error}"),
252            Self::Definition(error) => write!(formatter, "{error}"),
253        }
254    }
255}
256
257impl Error for GrammarLoweringError {}
258
259impl From<GrammarImportError> for GrammarLoweringError {
260    fn from(error: GrammarImportError) -> Self {
261        Self::Import(error)
262    }
263}
264
265impl From<GrammarEmitError> for GrammarLoweringError {
266    fn from(error: GrammarEmitError) -> Self {
267        Self::Emit(error)
268    }
269}
270
271impl From<GrammarRoundTripError> for GrammarLoweringError {
272    fn from(error: GrammarRoundTripError) -> Self {
273        Self::Definition(error)
274    }
275}
276
277fn check_format(format: &str) -> Result<(), GrammarLoweringError> {
278    if GRAMMAR_LOWERING_FORMATS.contains(&format) {
279        Ok(())
280    } else {
281        Err(GrammarLoweringError::UnsupportedFormat(format.to_owned()))
282    }
283}
284
285/// Rebuilds `expr` with `map` applied to its direct sub-expressions.
286pub(super) fn map_children<E>(
287    expr: &GrammarExpr,
288    map: &mut impl FnMut(&GrammarExpr) -> Result<GrammarExpr, E>,
289) -> Result<GrammarExpr, E> {
290    let mut boxed = |item: &GrammarExpr| map(item).map(Box::new);
291    Ok(match expr {
292        GrammarExpr::Choice {
293            ordered,
294            alternatives,
295        } => GrammarExpr::Choice {
296            ordered: *ordered,
297            alternatives: alternatives
298                .iter()
299                .map(&mut *map)
300                .collect::<Result<_, _>>()?,
301        },
302        GrammarExpr::Sequence(items) => {
303            GrammarExpr::Sequence(items.iter().map(&mut *map).collect::<Result<_, _>>()?)
304        }
305        GrammarExpr::Optional(item) => GrammarExpr::Optional(boxed(item)?),
306        GrammarExpr::ZeroOrMore(item) => GrammarExpr::ZeroOrMore(boxed(item)?),
307        GrammarExpr::OneOrMore(item) => GrammarExpr::OneOrMore(boxed(item)?),
308        GrammarExpr::And(item) => GrammarExpr::And(boxed(item)?),
309        GrammarExpr::Not(item) => GrammarExpr::Not(boxed(item)?),
310        GrammarExpr::Repeat { expr, min, max } => GrammarExpr::Repeat {
311            expr: boxed(expr)?,
312            min: *min,
313            max: *max,
314        },
315        GrammarExpr::Capture { label, expr } => GrammarExpr::Capture {
316            label: label.clone(),
317            expr: boxed(expr)?,
318        },
319        _ => expr.clone(),
320    })
321}
322
323/// Builds a grammar from its parts.
324pub(super) fn assemble(
325    start: &str,
326    rules: Vec<GrammarRule>,
327    source: Option<GrammarFormat>,
328) -> Grammar {
329    let mut grammar = Grammar::new().with_start(start);
330    for rule in rules {
331        grammar.add_rule(rule);
332    }
333    if let Some(source) = source {
334        grammar.set_source_format(source);
335    }
336    grammar
337}
338
339fn rule(name: &str, kind: RuleKind, expr: GrammarExpr, doc: Option<String>) -> GrammarRule {
340    GrammarRule {
341        name: name.to_owned(),
342        expr,
343        kind,
344        concept: None,
345        source_names: Vec::new(),
346        doc,
347        attributes: RuleAttributes::default(),
348    }
349}
350
351/// The helper rules and steps of one lowering.
352struct Lowerer<'a> {
353    format: &'a str,
354    unsupported: &'static [Construct],
355    taken: HashSet<String>,
356    counter: usize,
357    helpers: Vec<GrammarRule>,
358    memo: HashMap<String, String>,
359    steps: Vec<GrammarLoweringStep>,
360}
361
362impl Lowerer<'_> {
363    /// A fresh helper name; a lexer helper gets an upper-case name, which
364    /// ANTLR and Lark read as a token rule.
365    fn helper_name(&mut self, lexical: bool) -> String {
366        let name = loop {
367            self.counter += 1;
368            let name = format!("{HELPER_PREFIX}{}", self.counter);
369            if !self.taken.contains(&name) {
370                break name;
371            }
372        };
373        self.taken.insert(name.clone());
374        if lexical { name.to_uppercase() } else { name }
375    }
376
377    /// Lowers `expr` of `owner`; `lexical` marks a lexer rule body, where
378    /// character-level constructs are matched, and ANTLR's parser rules get
379    /// them through a lexer helper.
380    fn lower(
381        &mut self,
382        expr: &GrammarExpr,
383        owner: &str,
384        inner: bool,
385        lexical: bool,
386    ) -> Result<GrammarExpr, GrammarLoweringError> {
387        let Some(construct) = constructs_of(expr, inner, lexical)
388            .into_iter()
389            .find(|construct| self.unsupported.contains(construct))
390        else {
391            return map_children(expr, &mut |item| self.lower(item, owner, true, lexical));
392        };
393        let helper_lexical = lexical || construct == Construct::ParserCharacters;
394        let key = format!(
395            "{} {helper_lexical} {}",
396            construct.as_str(),
397            render_links_expression(expr)
398        );
399        if let Some(helper) = self.memo.get(&key) {
400            return Ok(GrammarExpr::NonTerminal(helper.clone()));
401        }
402        let helper = self.helper_name(helper_lexical);
403        self.memo.insert(key, helper.clone());
404        let (body, encoding, note) = encode(self.format, construct, expr, &helper)?;
405        self.steps.push(GrammarLoweringStep::Helper {
406            helper: helper.clone(),
407            owner: owner.to_owned(),
408            construct: construct.as_str().to_owned(),
409            encoding,
410            note: note.to_owned(),
411            original: expr.clone(),
412        });
413        let index = self.helpers.len();
414        let kind = if helper_lexical {
415            RuleKind::Token
416        } else {
417            RuleKind::Normal
418        };
419        self.helpers
420            .push(rule(&helper, kind, GrammarExpr::Empty, None));
421        self.helpers[index].expr = self.lower(&body, &helper, false, helper_lexical)?;
422        Ok(GrammarExpr::NonTerminal(helper))
423    }
424}
425
426/// Lowers `grammar` into `format`.
427///
428/// The result holds the lowered grammar, the executable text the target
429/// emitter writes for it, the steps and the metadata links that reconstruct
430/// the original from the executable, and whether every encoding is exact. The options' `emit` and `import` replace the format's own pair.
431///
432/// # Errors
433///
434/// Returns a [`GrammarLoweringError`] for an unsupported format, a grammar
435/// without a start rule, a character set the format cannot spell, or an
436/// emitter or importer error.
437pub fn lower_grammar(
438    grammar: &Grammar,
439    format: &str,
440    options: &GrammarLoweringOptions<'_>,
441) -> Result<GrammarLowering, GrammarLoweringError> {
442    check_format(format)?;
443    let start = grammar
444        .start_rule()
445        .ok_or(GrammarLoweringError::NoStartRule)?;
446    let own_emit = grammar_emitter(format)
447        .ok_or_else(|| GrammarLoweringError::UnsupportedFormat(format.to_owned()))?;
448    let own_import = grammar_importer(format)
449        .ok_or_else(|| GrammarLoweringError::UnsupportedFormat(format.to_owned()))?;
450    let emit: GrammarEmitFn<'_> = options.emit.unwrap_or(&own_emit);
451    let import: GrammarImportFn<'_> = options.import.unwrap_or(&own_import);
452
453    let mut state = Lowerer {
454        format,
455        unsupported: unsupported(format),
456        taken: grammar
457            .rule_names()
458            .iter()
459            .map(|name| name.to_lowercase())
460            .collect(),
461        counter: 0,
462        helpers: Vec::new(),
463        memo: HashMap::new(),
464        steps: Vec::new(),
465    };
466    let kept = kept_kinds(format);
467    let mut rules = Vec::new();
468    for original in grammar.rules() {
469        let expr = state.lower(&original.expr, &original.name, false, false)?;
470        // A tree-sitter token cannot refer to other rules, so a token rule
471        // that needs a helper becomes a normal rule with a kind step.
472        let refers_to_helper = format == "tree-sitter-json"
473            && render_links_expression(&expr) != render_links_expression(&original.expr);
474        let kind = if kept.contains(&original.kind) && !refers_to_helper {
475            original.kind
476        } else {
477            RuleKind::Normal
478        };
479        rules.push(rule(&original.name, kind, expr, original.doc.clone()));
480    }
481    rules.append(&mut state.helpers);
482    // The lowered grammar keeps the original source format, so the emitter
483    // reports every construct it cannot write for a grammar of that format.
484    let lowered = assemble(&start.name, rules, grammar.source_format());
485
486    // A first emission shows the names the target gives the rules (GBNF
487    // starts at root, ANTLR and Lark adjust case), matched by position, which
488    // every emitter keeps. The lowered grammar takes those names, so the
489    // target writes it without renaming, and the renames become steps.
490    let first = import(&emit(&lowered)?.0)?;
491    let first = first.rule_names();
492    let renames: Vec<(String, String)> = lowered
493        .rule_names()
494        .iter()
495        .zip(&first)
496        .filter(|(name, executable)| name != executable)
497        .map(|(name, executable)| ((*name).to_owned(), (*executable).to_owned()))
498        .collect();
499    let named = |name: &str| {
500        renames
501            .iter()
502            .find(|(rule, _)| rule == name)
503            .map_or_else(|| name.to_owned(), |(_, value)| value.clone())
504    };
505    let mut executable_rules: Vec<GrammarRule> = lowered
506        .rules()
507        .iter()
508        .map(|lowered_rule| {
509            let expr = rename_references(&lowered_rule.expr, &named);
510            rule(
511                &named(&lowered_rule.name),
512                lowered_rule.kind,
513                expr,
514                lowered_rule.doc.clone(),
515            )
516        })
517        .collect();
518    let executable_start = named(&start.name);
519    let mut executable = assemble(
520        &executable_start,
521        executable_rules.clone(),
522        grammar.source_format(),
523    );
524    let (mut text, mut report) = emit(&executable)?;
525    let mut imported = import(&text)?;
526    // Documentation the target does not read back verbatim (ANTLR keeps the
527    // comment markers, BNF has no comments) leaves the executable and is
528    // carried by a doc step instead.
529    let mut unkept = false;
530    for executable_rule in &mut executable_rules {
531        let kept_doc = imported
532            .rule(&executable_rule.name)
533            .is_some_and(|back| back.doc == executable_rule.doc);
534        if executable_rule.doc.is_some() && !kept_doc {
535            executable_rule.doc = None;
536            unkept = true;
537        }
538    }
539    if unkept {
540        executable = assemble(&executable_start, executable_rules, grammar.source_format());
541        (text, report) = emit(&executable)?;
542        imported = import(&text)?;
543    }
544
545    let mut steps: Vec<GrammarLoweringStep> = renames
546        .iter()
547        .map(|(rule, value)| GrammarLoweringStep::Rename {
548            rule: rule.clone(),
549            value: value.clone(),
550        })
551        .collect();
552    steps.append(&mut state.steps);
553    for original in grammar.rules() {
554        let Some(back) = imported.rule(&named(&original.name)) else {
555            continue;
556        };
557        if back.kind != original.kind {
558            steps.push(GrammarLoweringStep::Kind {
559                rule: original.name.clone(),
560                kind: original.kind,
561            });
562        }
563        if let Some(doc) = &original.doc
564            && back.doc.as_ref() != Some(doc)
565        {
566            steps.push(GrammarLoweringStep::Doc {
567                rule: original.name.clone(),
568                doc: doc.clone(),
569            });
570        }
571    }
572
573    // The feature union declarations and rule fields have no form in any
574    // target notation: they become steps, and the executable does not honor
575    // them.
576    if let Some(declarations) = render_declarations_text(grammar.declarations()) {
577        steps.push(GrammarLoweringStep::Declarations { declarations });
578    }
579    for original in grammar.rules() {
580        let fields = render_rule_fields(&original.attributes);
581        if !fields.is_empty() {
582            steps.push(GrammarLoweringStep::Attributes {
583                rule: original.name.clone(),
584                attributes: fields.join(" "),
585            });
586        }
587    }
588
589    let approximate = steps.iter().any(|step| {
590        matches!(
591            step,
592            GrammarLoweringStep::Helper {
593                encoding: GrammarLoweringEncoding::Approximate,
594                ..
595            } | GrammarLoweringStep::Declarations { .. }
596                | GrammarLoweringStep::Attributes { .. }
597        )
598    });
599    let status = if approximate {
600        GrammarLoweringStatus::Approximate
601    } else {
602        GrammarLoweringStatus::Exact
603    };
604    let metadata = GrammarLoweringMetadata {
605        format: format.to_owned(),
606        status,
607        source: grammar.source_format(),
608        start: start.name.clone(),
609        order: grammar
610            .rule_names()
611            .into_iter()
612            .map(str::to_owned)
613            .collect(),
614        steps,
615    };
616    Ok(GrammarLowering {
617        format: format.to_owned(),
618        status,
619        grammar: executable,
620        executable: text,
621        report,
622        imported,
623        metadata: render_lowering_metadata(&metadata),
624        steps: metadata.steps,
625    })
626}
627
628/// `expr` with every reference renamed by `named`.
629fn rename_references(expr: &GrammarExpr, named: &impl Fn(&str) -> String) -> GrammarExpr {
630    match expr {
631        GrammarExpr::NonTerminal(name) => GrammarExpr::NonTerminal(named(name)),
632        _ => map_children::<std::convert::Infallible>(expr, &mut |item| {
633            Ok(rename_references(item, named))
634        })
635        .unwrap_or_else(|never| match never {}),
636    }
637}
meta_language/grammar/interchange/lowering/mod.rs

meta_language/grammar/interchange/lowering/
mod.rs
