meta_language/grammar/
round_trip.rs

1//! Mutation-guarded grammar interchange round trips.
2//!
3//! A plain round trip (import, emit, re-import, compare) cannot tell a correct
4//! importer/emitter pair from two that are wrong in mutually cancelling ways,
5//! and it cannot tell an emitter that re-emits a cached source from one that
6//! prints the grammar it was given. The guard therefore changes the grammar
7//! before export, requires the change in the exported text and in the
8//! re-imported grammar, and checks both the imported and the re-imported
9//! grammar against independent accept and reject samples that do not come
10//! from the pair under test. It mirrors `js/src/grammar-round-trip.js`.
11
12use std::error::Error;
13use std::fmt;
14
15use super::emit::{EmitReport, GrammarEmitError};
16use super::import::GrammarImportError;
17use super::merge::{GrammarMergeError, normalized_rule_definition};
18use super::runtime::GrammarParser;
19use super::{CharClassItem, Grammar, GrammarExpr, GrammarFormat, GrammarRule};
20
21/// The literal alternative the guard adds to the start rule by default.
22pub const GRAMMAR_ROUND_TRIP_MARKER: &str = "round-trip-mutation";
23
24/// Imports grammar source text of one notation.
25pub type GrammarImportFn<'a> = &'a dyn Fn(&str) -> Result<Grammar, GrammarImportError>;
26
27/// Emits a grammar in one notation, with its fidelity report.
28pub type GrammarEmitFn<'a> = &'a dyn Fn(&Grammar) -> Result<(String, EmitReport), GrammarEmitError>;
29
30/// The importer/emitter pair under test and the independent samples.
31#[derive(Clone, Copy)]
32pub struct GrammarRoundTrip<'a> {
33    /// Importer of the notation.
34    pub import: GrammarImportFn<'a>,
35    /// Emitter of the same notation.
36    pub emit: GrammarEmitFn<'a>,
37    /// Literal alternative added to the start rule before export.
38    pub marker: &'a str,
39    /// Texts the grammar must accept.
40    pub accepts: &'a [String],
41    /// Texts the grammar must reject.
42    pub rejects: &'a [String],
43}
44
45impl<'a> GrammarRoundTrip<'a> {
46    /// Builds a round trip through `import` and `emit` with the default
47    /// marker and no samples.
48    #[must_use]
49    pub const fn new(import: GrammarImportFn<'a>, emit: GrammarEmitFn<'a>) -> Self {
50        Self {
51            import,
52            emit,
53            marker: GRAMMAR_ROUND_TRIP_MARKER,
54            accepts: &[],
55            rejects: &[],
56        }
57    }
58
59    /// Returns this round trip with independent accept and reject samples.
60    #[must_use]
61    pub const fn with_samples(mut self, accepts: &'a [String], rejects: &'a [String]) -> Self {
62        self.accepts = accepts;
63        self.rejects = rejects;
64        self
65    }
66}
67
68/// Whether the pair carried the grammar and the mutation.
69#[derive(Clone, Copy, Debug, PartialEq, Eq)]
70pub enum GrammarRoundTripStatus {
71    /// Every check held.
72    Preserved,
73    /// At least one check failed.
74    Broken,
75}
76
77impl GrammarRoundTripStatus {
78    /// Stable tag shared with the JavaScript runtime.
79    #[must_use]
80    pub const fn as_str(self) -> &'static str {
81        match self {
82            Self::Preserved => "preserved",
83            Self::Broken => "broken",
84        }
85    }
86}
87
88/// What a failed check found.
89#[derive(Clone, Copy, Debug, PartialEq, Eq)]
90pub enum GrammarRoundTripFailureKind {
91    /// A text the grammar must accept was rejected.
92    SampleRejected,
93    /// A text the grammar must reject was accepted.
94    SampleAccepted,
95    /// The imported grammar already accepts the marker.
96    MarkerAlreadyAccepted,
97    /// The emitter reported a lossy conversion of the mutated grammar.
98    LossyExport,
99    /// The exported text does not carry the mutation.
100    MutationNotExported,
101    /// The re-imported rules differ from the mutated ones.
102    RulesChanged,
103    /// The re-imported grammar does not accept the marker.
104    MutationNotVisible,
105    /// A second export does not settle on the same rules and text.
106    ExportNotStable,
107}
108
109impl GrammarRoundTripFailureKind {
110    /// Stable tag shared with the JavaScript runtime.
111    #[must_use]
112    pub const fn as_str(self) -> &'static str {
113        match self {
114            Self::SampleRejected => "sample-rejected",
115            Self::SampleAccepted => "sample-accepted",
116            Self::MarkerAlreadyAccepted => "marker-already-accepted",
117            Self::LossyExport => "lossy-export",
118            Self::MutationNotExported => "mutation-not-exported",
119            Self::RulesChanged => "rules-changed",
120            Self::MutationNotVisible => "mutation-not-visible",
121            Self::ExportNotStable => "export-not-stable",
122        }
123    }
124}
125
126/// The grammar a failed check looked at.
127#[derive(Clone, Copy, Debug, PartialEq, Eq)]
128pub enum GrammarRoundTripStage {
129    /// The grammar imported from the source.
130    Imported,
131    /// The exported text of the mutated grammar.
132    Exported,
133    /// The grammar re-imported from the exported text.
134    Reimported,
135}
136
137impl GrammarRoundTripStage {
138    /// Stable tag shared with the JavaScript runtime.
139    #[must_use]
140    pub const fn as_str(self) -> &'static str {
141        match self {
142            Self::Imported => "imported",
143            Self::Exported => "exported",
144            Self::Reimported => "reimported",
145        }
146    }
147}
148
149/// One failed check.
150#[derive(Clone, Debug, PartialEq, Eq)]
151pub struct GrammarRoundTripFailure {
152    /// What the check found.
153    pub kind: GrammarRoundTripFailureKind,
154    /// The grammar it looked at.
155    pub stage: GrammarRoundTripStage,
156    /// The sample, marker, note or rule involved.
157    pub detail: String,
158}
159
160/// The outcome of [`check_grammar_round_trip`].
161#[derive(Clone, Debug, PartialEq, Eq)]
162pub struct GrammarRoundTripReport {
163    /// Whether every check held.
164    pub status: GrammarRoundTripStatus,
165    /// Every failed check, in the order the guard ran them.
166    pub failures: Vec<GrammarRoundTripFailure>,
167    /// The imported grammar with the marker alternative.
168    pub mutated: Grammar,
169    /// The exported text of the mutated grammar.
170    pub exported: String,
171    /// The grammar re-imported from the exported text.
172    pub reimported: Grammar,
173}
174
175/// Why the guard could not run.
176#[derive(Clone, Debug, PartialEq, Eq)]
177pub enum GrammarRoundTripError {
178    /// The importer rejected a source, such as a malformed grammar.
179    Import(GrammarImportError),
180    /// The emitter rejected a grammar.
181    Emit(GrammarEmitError),
182    /// A rule definition could not be normalized for comparison.
183    Normalize(GrammarMergeError),
184    /// The grammar has no start rule to mutate.
185    MissingStartRule,
186}
187
188impl fmt::Display for GrammarRoundTripError {
189    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
190        match self {
191            Self::Import(error) => write!(formatter, "{error}"),
192            Self::Emit(error) => write!(formatter, "{error}"),
193            Self::Normalize(error) => write!(formatter, "{error}"),
194            Self::MissingStartRule => {
195                formatter.write_str("the grammar has no start rule to mutate")
196            }
197        }
198    }
199}
200
201impl Error for GrammarRoundTripError {}
202
203impl From<GrammarImportError> for GrammarRoundTripError {
204    fn from(error: GrammarImportError) -> Self {
205        Self::Import(error)
206    }
207}
208
209impl From<GrammarEmitError> for GrammarRoundTripError {
210    fn from(error: GrammarEmitError) -> Self {
211        Self::Emit(error)
212    }
213}
214
215impl From<GrammarMergeError> for GrammarRoundTripError {
216    fn from(error: GrammarMergeError) -> Self {
217        Self::Normalize(error)
218    }
219}
220
221/// Adds `marker` as a literal alternative of the start rule.
222///
223/// PEG grammars get an ordered choice, every other notation an unordered one,
224/// so the mutation is expressible without a lossy fallback.
225pub fn mutate_grammar_start_rule(
226    grammar: &Grammar,
227    marker: &str,
228) -> Result<Grammar, GrammarRoundTripError> {
229    let start = grammar
230        .start_rule()
231        .ok_or(GrammarRoundTripError::MissingStartRule)?
232        .name
233        .clone();
234    let ordered = grammar.source_format() == Some(GrammarFormat::Peg);
235    let mut mutated = Grammar::new();
236    for rule in grammar.rules() {
237        let mut rule = rule.clone();
238        if rule.name == start {
239            rule.expr = GrammarExpr::Choice {
240                ordered,
241                alternatives: vec![rule.expr, GrammarExpr::Terminal(marker.to_owned())],
242            };
243        }
244        mutated.add_rule(rule);
245    }
246    if let Some(name) = grammar.start() {
247        mutated.set_start(name);
248    }
249    if let Some(format) = grammar.source_format() {
250        mutated.set_source_format(format);
251    }
252    Ok(mutated)
253}
254
255/// Round trips `source` through a mutated export and reports every failure.
256///
257/// The grammar is imported, mutated, exported and re-imported, and every way
258/// the pair failed to carry the grammar and the mutation is reported.
259/// Malformed sources are rejected by the importer, whose error is returned.
260pub fn check_grammar_round_trip(
261    source: &str,
262    round_trip: &GrammarRoundTrip<'_>,
263) -> Result<GrammarRoundTripReport, GrammarRoundTripError> {
264    let mut failures = Vec::new();
265    let imported = (round_trip.import)(source)?;
266    check_samples(
267        &mut failures,
268        GrammarRoundTripStage::Imported,
269        &imported,
270        round_trip,
271    );
272    if accepts(&imported, round_trip.marker) {
273        failures.push(failure(
274            GrammarRoundTripFailureKind::MarkerAlreadyAccepted,
275            GrammarRoundTripStage::Imported,
276            round_trip.marker,
277        ));
278    }
279
280    let mutated = mutate_grammar_start_rule(&imported, round_trip.marker)?;
281    let (unmutated, _) = (round_trip.emit)(&imported)?;
282    let (exported, report) = (round_trip.emit)(&mutated)?;
283    for note in &report.lossy {
284        failures.push(failure(
285            GrammarRoundTripFailureKind::LossyExport,
286            GrammarRoundTripStage::Exported,
287            note,
288        ));
289    }
290    if exported == unmutated || !exported.contains(round_trip.marker) {
291        failures.push(failure(
292            GrammarRoundTripFailureKind::MutationNotExported,
293            GrammarRoundTripStage::Exported,
294            round_trip.marker,
295        ));
296    }
297
298    let reimported = (round_trip.import)(&exported)?;
299    compare_rules(&mut failures, &mutated, &reimported)?;
300    if !accepts(&reimported, round_trip.marker) {
301        failures.push(failure(
302            GrammarRoundTripFailureKind::MutationNotVisible,
303            GrammarRoundTripStage::Reimported,
304            round_trip.marker,
305        ));
306    }
307    check_samples(
308        &mut failures,
309        GrammarRoundTripStage::Reimported,
310        &reimported,
311        round_trip,
312    );
313    // A notation may print an equivalent construct differently once (ABNF has
314    // no character classes), so the second export must carry the same rules
315    // and be a fixpoint rather than repeat the first text.
316    let (again, _) = (round_trip.emit)(&reimported)?;
317    let settled = (round_trip.import)(&again)?;
318    if definitions(&mutated)? != definitions(&settled)? || (round_trip.emit)(&settled)?.0 != again {
319        failures.push(failure(
320            GrammarRoundTripFailureKind::ExportNotStable,
321            GrammarRoundTripStage::Reimported,
322            "a second export does not settle",
323        ));
324    }
325
326    Ok(GrammarRoundTripReport {
327        status: if failures.is_empty() {
328            GrammarRoundTripStatus::Preserved
329        } else {
330            GrammarRoundTripStatus::Broken
331        },
332        failures,
333        mutated,
334        exported,
335        reimported,
336    })
337}
338
339fn failure(
340    kind: GrammarRoundTripFailureKind,
341    stage: GrammarRoundTripStage,
342    detail: &str,
343) -> GrammarRoundTripFailure {
344    GrammarRoundTripFailure {
345        kind,
346        stage,
347        detail: detail.to_owned(),
348    }
349}
350
351fn compare_rules(
352    failures: &mut Vec<GrammarRoundTripFailure>,
353    expected: &Grammar,
354    actual: &Grammar,
355) -> Result<(), GrammarRoundTripError> {
356    let expected_names = expected.rule_names();
357    let actual_names = actual.rule_names();
358    if expected_names != actual_names {
359        failures.push(failure(
360            GrammarRoundTripFailureKind::RulesChanged,
361            GrammarRoundTripStage::Reimported,
362            &format!(
363                "rule names [{}] became [{}]",
364                expected_names.join(", "),
365                actual_names.join(", ")
366            ),
367        ));
368    }
369    let start = |grammar: &Grammar| grammar.start_rule().map(|rule| rule.name.clone());
370    if start(expected) != start(actual) {
371        failures.push(failure(
372            GrammarRoundTripFailureKind::RulesChanged,
373            GrammarRoundTripStage::Reimported,
374            "the start rule changed",
375        ));
376    }
377    for rule in expected.rules() {
378        if let Some(other) = actual.rule(&rule.name)
379            && canonical_rule_definition(other)? != canonical_rule_definition(rule)?
380        {
381            failures.push(failure(
382                GrammarRoundTripFailureKind::RulesChanged,
383                GrammarRoundTripStage::Reimported,
384                &format!("rule {} changed its definition", rule.name),
385            ));
386        }
387    }
388    Ok(())
389}
390
391fn definitions(grammar: &Grammar) -> Result<Vec<String>, GrammarRoundTripError> {
392    grammar
393        .rules()
394        .iter()
395        .map(|rule| {
396            Ok(format!(
397                "{}={}",
398                rule.name,
399                canonical_rule_definition(rule)?
400            ))
401        })
402        .collect()
403}
404
405/// The meaning-aware definition of a rule.
406///
407/// Every set of single characters is spelled as one unordered choice first: a
408/// character class, a choice of its ranges and an ordered choice of them all
409/// consume the same one character. Mirrors the JavaScript
410/// `canonicalRuleDefinition`.
411///
412/// # Errors
413///
414/// A [`GrammarRoundTripError`] when the rule does not normalize.
415pub fn canonical_rule_definition(rule: &GrammarRule) -> Result<String, GrammarRoundTripError> {
416    let canonical = GrammarRule {
417        expr: canonical_characters(&rule.expr),
418        ..rule.clone()
419    };
420    Ok(normalized_rule_definition(&canonical)?)
421}
422
423fn canonical_characters(expr: &GrammarExpr) -> GrammarExpr {
424    if let Some(mut set) = character_set(expr) {
425        return if set.len() == 1 {
426            set.remove(0)
427        } else {
428            GrammarExpr::Choice {
429                ordered: false,
430                alternatives: set,
431            }
432        };
433    }
434    let boxed = |inner: &GrammarExpr| Box::new(canonical_characters(inner));
435    match expr {
436        GrammarExpr::Choice {
437            ordered,
438            alternatives,
439        } => GrammarExpr::Choice {
440            ordered: *ordered,
441            alternatives: alternatives.iter().map(canonical_characters).collect(),
442        },
443        GrammarExpr::Sequence(items) => {
444            GrammarExpr::Sequence(items.iter().map(canonical_characters).collect())
445        }
446        GrammarExpr::Optional(inner) => GrammarExpr::Optional(boxed(inner)),
447        GrammarExpr::ZeroOrMore(inner) => GrammarExpr::ZeroOrMore(boxed(inner)),
448        GrammarExpr::OneOrMore(inner) => GrammarExpr::OneOrMore(boxed(inner)),
449        GrammarExpr::Repeat { expr, min, max } => GrammarExpr::Repeat {
450            expr: boxed(expr),
451            min: *min,
452            max: *max,
453        },
454        GrammarExpr::And(inner) => GrammarExpr::And(boxed(inner)),
455        GrammarExpr::Not(inner) => GrammarExpr::Not(boxed(inner)),
456        GrammarExpr::Capture { label, expr } => GrammarExpr::Capture {
457            label: label.clone(),
458            expr: boxed(expr),
459        },
460        other => other.clone(),
461    }
462}
463
464fn character_set(expr: &GrammarExpr) -> Option<Vec<GrammarExpr>> {
465    match expr {
466        GrammarExpr::Terminal(value) if value.chars().count() == 1 => Some(vec![expr.clone()]),
467        GrammarExpr::CharRange(..) => Some(vec![expr.clone()]),
468        GrammarExpr::CharClass {
469            negated: false,
470            items,
471        } => Some(
472            items
473                .iter()
474                .map(|item| match item {
475                    CharClassItem::Char(value) => GrammarExpr::Terminal(value.to_string()),
476                    CharClassItem::Range(start, end) => GrammarExpr::CharRange(*start, *end),
477                })
478                .collect(),
479        ),
480        GrammarExpr::Choice { alternatives, .. } => alternatives
481            .iter()
482            .map(character_set)
483            .collect::<Option<Vec<_>>>()
484            .map(|sets| sets.into_iter().flatten().collect()),
485        _ => None,
486    }
487}
488
489fn check_samples(
490    failures: &mut Vec<GrammarRoundTripFailure>,
491    stage: GrammarRoundTripStage,
492    grammar: &Grammar,
493    round_trip: &GrammarRoundTrip<'_>,
494) {
495    let parser = GrammarParser::new(grammar.clone());
496    for text in round_trip.accepts {
497        if !parser.accepts(text) {
498            failures.push(failure(
499                GrammarRoundTripFailureKind::SampleRejected,
500                stage,
501                text,
502            ));
503        }
504    }
505    for text in round_trip.rejects {
506        if parser.accepts(text) {
507            failures.push(failure(
508                GrammarRoundTripFailureKind::SampleAccepted,
509                stage,
510                text,
511            ));
512        }
513    }
514}
515
516/// Whether `text` parses with `grammar` on the native executor, as the
517/// JavaScript `acceptsText` does.
518#[must_use]
519pub fn accepts_text(grammar: &Grammar, text: &str) -> bool {
520    super::feature_runtime::parse_with_grammar(
521        grammar,
522        text.as_bytes(),
523        &super::feature_runtime::FeatureParseOptions::default(),
524    )
525    .is_ok()
526}
527
528fn accepts(grammar: &Grammar, text: &str) -> bool {
529    GrammarParser::new(grammar.clone()).accepts(text)
530}
meta_language/grammar/round_trip.rs

meta_language/grammar/
round_trip.rs
