meta_language/grammar/merge/
mod.rs

1//! Deterministic, meaning-aware merging of grammars from several sources, and
2//! binding-aware renaming of grammar rules.
3//!
4//! This mirrors `js/src/grammar-merge.js`: both runtimes normalize rule
5//! definitions the same way, prove equivalence by the same recursive structural
6//! bisimulation and print the same canonical definitions, so their decisions
7//! agree.
8
9mod declarations;
10mod group;
11mod names;
12mod normalize;
13mod reconcile;
14mod rename;
15
16use group::{
17    Prepared, edition_alternatives, group_fingerprint, group_key, merge_group, name_label,
18    normalize_samples, prepare_sources, required_failures, source_of,
19};
20use normalize::normalize;
21pub use rename::{rename_grammar_rule, restore_source_names};
22
23use std::collections::{BTreeMap, BTreeSet};
24use std::error::Error;
25use std::fmt;
26
27use serde::Serialize;
28
29use super::{Grammar, GrammarRule};
30use crate::decorators::{DecoratorLevel, DecoratorSet, decorator_record, record_field};
31
32/// How an accepted equivalence is justified.
33pub const GRAMMAR_MERGE_METHOD: &str = "recursive-structural-bisimulation";
34
35/// One grammar taking part in a merge.
36#[derive(Clone, Debug, PartialEq, Eq)]
37pub struct GrammarMergeSource {
38    /// Source identifier, unique within one merge and free of `:`.
39    pub id: String,
40    /// Language the grammar describes.
41    pub language: String,
42    /// Language edition; different editions are never merged with each other.
43    pub edition: String,
44    /// Lower precedence wins name collisions.
45    pub precedence: u32,
46    /// The source grammar.
47    pub grammar: Grammar,
48}
49
50impl GrammarMergeSource {
51    /// Builds a source with an empty edition and precedence zero.
52    #[must_use]
53    pub fn new(id: impl Into<String>, language: impl Into<String>, grammar: Grammar) -> Self {
54        Self {
55            id: id.into(),
56            language: language.into(),
57            edition: String::new(),
58            precedence: 0,
59            grammar,
60        }
61    }
62
63    /// Sets the language edition.
64    #[must_use]
65    pub fn with_edition(mut self, edition: impl Into<String>) -> Self {
66        self.edition = edition.into();
67        self
68    }
69
70    /// Sets the precedence.
71    #[must_use]
72    pub const fn with_precedence(mut self, precedence: u32) -> Self {
73        self.precedence = precedence;
74        self
75    }
76}
77
78/// Optional inputs of [`merge_grammars`].
79#[derive(Clone, Debug, Default)]
80pub struct GrammarMergeOptions<'a> {
81    /// Sample inputs keyed by `sourceId:ruleName`; identical samples only
82    /// nominate candidates, they never decide a merge.
83    pub samples: BTreeMap<String, Vec<String>>,
84    /// Pairs of `sourceId:ruleName` aliases that must end up merged.
85    pub required_equivalences: Vec<(String, String)>,
86    /// An earlier result: unchanged groups are reused and established
87    /// canonical names are kept.
88    pub previous: Option<&'a GrammarMergeResult>,
89    /// `merge-decision` decorators, which see each decision as `{ kind,
90    /// name, members, basis, definition }` (members joined by spaces): they
91    /// may change the kind or the basis, and `drop` removes the decision.
92    /// They change the reported decisions only, never the merged grammar.
93    pub decorators: DecoratorSet,
94    /// Also unite corresponding rules of different sources that are
95    /// equivalent up to their lexical roles, or that share a name when no
96    /// correspondence matched them (see `reconcile.rs`). Each such class is a
97    /// [`GrammarMergeDecisionKind::Reconciled`] decision, kept by the
98    /// definition of its first source and the concept of its first rule that
99    /// has one.
100    pub reconcile: bool,
101}
102
103/// What the merge decided about one class of rules.
104#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
105#[serde(rename_all = "kebab-case")]
106pub enum GrammarMergeDecisionKind {
107    /// Several rules were proven equivalent and merged.
108    Merged,
109    /// Corresponding rules of different sources were reconciled and merged.
110    Reconciled,
111    /// The rule has no equivalent in the group.
112    KeptUnique,
113    /// The rule was renamed because a higher-precedence rule holds its name.
114    RenamedForCollision,
115    /// Rules sharing a name have different meanings and stay distinct.
116    HomonymKeptDistinct,
117    /// A nominated match could not be proven and was not merged.
118    Uncertain,
119    /// Sources declare a different matching, macro or scanner of one name;
120    /// the declaration of the first source in precedence order is kept.
121    DeclarationConflict,
122}
123
124impl GrammarMergeDecisionKind {
125    /// Returns the stable textual form.
126    #[must_use]
127    pub const fn as_str(self) -> &'static str {
128        match self {
129            Self::Merged => "merged",
130            Self::Reconciled => "reconciled",
131            Self::KeptUnique => "kept-unique",
132            Self::RenamedForCollision => "renamed-for-collision",
133            Self::HomonymKeptDistinct => "homonym-kept-distinct",
134            Self::Uncertain => "uncertain",
135            Self::DeclarationConflict => "declaration-conflict",
136        }
137    }
138
139    /// The kind whose textual form is `text`.
140    #[must_use]
141    pub fn parse(text: &str) -> Option<Self> {
142        [
143            Self::Merged,
144            Self::Reconciled,
145            Self::KeptUnique,
146            Self::RenamedForCollision,
147            Self::HomonymKeptDistinct,
148            Self::Uncertain,
149            Self::DeclarationConflict,
150        ]
151        .into_iter()
152        .find(|kind| kind.as_str() == text)
153    }
154}
155
156/// One merge decision with its justification.
157#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
158pub struct GrammarMergeDecision {
159    /// Decision kind.
160    pub kind: GrammarMergeDecisionKind,
161    /// Canonical name (the raw source name for homonyms).
162    pub name: String,
163    /// Source aliases, or canonical names for homonyms.
164    pub members: Vec<String>,
165    /// Justification of the decision.
166    pub basis: String,
167    /// Canonical normalized definition of a merged or unique rule.
168    pub definition: Option<String>,
169    /// The concept record a reconciling merge gave the merged rule.
170    #[serde(skip_serializing_if = "Option::is_none")]
171    pub concept: Option<String>,
172}
173
174/// Why two rules were nominated as a possible match.
175#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
176#[serde(rename_all = "kebab-case")]
177pub enum GrammarMergeNominationBasis {
178    /// The names differ only in case, `-` or `_`.
179    NameSimilarity,
180    /// Both rules have the same caller-supplied samples.
181    IdenticalSamples,
182}
183
184impl GrammarMergeNominationBasis {
185    /// Returns the stable textual form.
186    #[must_use]
187    pub const fn as_str(self) -> &'static str {
188        match self {
189            Self::NameSimilarity => "name-similarity",
190            Self::IdenticalSamples => "identical-samples",
191        }
192    }
193}
194
195/// Whether a nomination was confirmed by the structural proof.
196#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
197#[serde(rename_all = "kebab-case")]
198pub enum GrammarMergeNominationOutcome {
199    /// The nominated rules were proven equivalent.
200    Proven,
201    /// The nominated rules were reconciled as corresponding rules.
202    Reconciled,
203    /// The nominated rules were not proven equivalent and stay separate.
204    Unproven,
205}
206
207/// A candidate match nominated by a heuristic.
208#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
209pub struct GrammarMergeNomination {
210    /// Heuristic that nominated the pair.
211    pub basis: GrammarMergeNominationBasis,
212    /// The two source aliases.
213    pub members: [String; 2],
214    /// Result of the structural proof.
215    pub outcome: GrammarMergeNominationOutcome,
216}
217
218/// Why the merge kept several options instead of choosing silently.
219#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
220#[serde(rename_all = "kebab-case")]
221pub enum GrammarMergeAlternativeReason {
222    /// Sources start from different rules.
223    StartRule,
224    /// Rules sharing a name have different meanings.
225    DistinctMeaning,
226    /// A nominated match was not proven.
227    UncertainMatch,
228    /// A language has several editions.
229    Edition,
230    /// Sources declare a different matching, macro or scanner of one name.
231    DeclarationConflict,
232}
233
234impl GrammarMergeAlternativeReason {
235    /// Returns the stable textual form.
236    #[must_use]
237    pub const fn as_str(self) -> &'static str {
238        match self {
239            Self::StartRule => "start-rule",
240            Self::DistinctMeaning => "distinct-meaning",
241            Self::UncertainMatch => "uncertain-match",
242            Self::Edition => "edition",
243            Self::DeclarationConflict => "declaration-conflict",
244        }
245    }
246}
247
248/// An explicit alternative kept by the merge.
249#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
250pub struct GrammarMergeAlternative {
251    /// Why the alternative exists.
252    pub reason: GrammarMergeAlternativeReason,
253    /// The chosen option, the shared name, the nomination basis or the language.
254    pub name: String,
255    /// The options kept.
256    pub options: Vec<String>,
257}
258
259/// Kind of a merge failure.
260#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
261#[serde(rename_all = "kebab-case")]
262pub enum GrammarMergeFailureKind {
263    /// A required equivalence was not established.
264    UnresolvedRequiredEquivalence,
265}
266
267/// Why a required equivalence was not established.
268#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize)]
269#[serde(rename_all = "kebab-case")]
270pub enum GrammarMergeFailureReason {
271    /// An alias names no rule of the merged sources.
272    UnknownRule,
273    /// The rules belong to different languages or editions.
274    DifferentLanguageOrEdition,
275    /// The rules were not proven equivalent.
276    NotProven,
277}
278
279impl GrammarMergeFailureReason {
280    /// Returns the stable textual form.
281    #[must_use]
282    pub const fn as_str(self) -> &'static str {
283        match self {
284            Self::UnknownRule => "unknown-rule",
285            Self::DifferentLanguageOrEdition => "different-language-or-edition",
286            Self::NotProven => "not-proven",
287        }
288    }
289}
290
291/// A required equivalence the merge could not establish.
292#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
293pub struct GrammarMergeFailure {
294    /// Failure kind.
295    pub kind: GrammarMergeFailureKind,
296    /// The two aliases, sorted.
297    pub members: [String; 2],
298    /// Why the equivalence is unresolved.
299    pub reason: GrammarMergeFailureReason,
300}
301
302/// The merged grammar of one language edition.
303#[derive(Clone, Debug, PartialEq, Eq)]
304pub struct MergedGrammarGroup {
305    /// `language@edition`.
306    pub key: String,
307    /// Language.
308    pub language: String,
309    /// Edition.
310    pub edition: String,
311    /// SHA-256 of the group's normalized inputs.
312    pub fingerprint: String,
313    /// Source ids in precedence order.
314    pub sources: Vec<String>,
315    /// The merged grammar.
316    pub grammar: Grammar,
317    /// Canonical rule name of every `sourceId:ruleName` alias.
318    pub identities: BTreeMap<String, String>,
319    /// Decisions with their justification.
320    pub decisions: Vec<GrammarMergeDecision>,
321    /// Candidate matches nominated by heuristics.
322    pub nominations: Vec<GrammarMergeNomination>,
323    /// Alternatives kept explicit.
324    pub alternatives: Vec<GrammarMergeAlternative>,
325}
326
327/// The result of [`merge_grammars`].
328#[derive(Clone, Debug, PartialEq, Eq)]
329pub struct GrammarMergeResult {
330    /// One merged grammar per language edition, sorted by language and edition.
331    pub groups: Vec<MergedGrammarGroup>,
332    /// Languages with several editions.
333    pub alternatives: Vec<GrammarMergeAlternative>,
334    /// Unresolved required equivalences.
335    pub failures: Vec<GrammarMergeFailure>,
336    /// Keys of groups reused from the previous result.
337    pub reused: Vec<String>,
338    /// Keys of groups merged again.
339    pub recomputed: Vec<String>,
340}
341
342impl GrammarMergeResult {
343    /// `"complete"` when every required equivalence holds, else `"incomplete"`.
344    #[must_use]
345    pub const fn status(&self) -> &'static str {
346        if self.failures.is_empty() {
347            "complete"
348        } else {
349            "incomplete"
350        }
351    }
352
353    /// Returns the group with `key`, when present.
354    #[must_use]
355    pub fn group(&self, key: &str) -> Option<&MergedGrammarGroup> {
356        self.groups.iter().find(|group| group.key == key)
357    }
358}
359
360/// Malformed merge input, or an incomplete merge in [`assert_merge_complete`].
361#[derive(Clone, Debug, PartialEq, Eq)]
362pub struct GrammarMergeError {
363    message: String,
364    failures: Vec<GrammarMergeFailure>,
365    concatenated: Vec<String>,
366}
367
368impl GrammarMergeError {
369    fn new(message: impl Into<String>) -> Self {
370        Self {
371            message: message.into(),
372            failures: Vec::new(),
373            concatenated: Vec::new(),
374        }
375    }
376
377    /// The unresolved required equivalences, if any.
378    #[must_use]
379    pub fn failures(&self) -> &[GrammarMergeFailure] {
380        &self.failures
381    }
382
383    /// The keys of the groups [`assert_merge_shares`] rejected, if any.
384    #[must_use]
385    pub fn concatenated(&self) -> &[String] {
386        &self.concatenated
387    }
388}
389
390impl fmt::Display for GrammarMergeError {
391    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
392        formatter.write_str(&self.message)
393    }
394}
395
396impl Error for GrammarMergeError {}
397
398/// Why a rename was refused.
399#[derive(Clone, Copy, Debug, PartialEq, Eq)]
400pub enum GrammarRenameErrorKind {
401    /// The new name is empty or contains whitespace.
402    InvalidName,
403    /// The grammar has no rule with the old name.
404    UnknownRule,
405    /// The new name would capture an existing binding.
406    Collision,
407}
408
409impl GrammarRenameErrorKind {
410    /// Returns the stable textual form.
411    #[must_use]
412    pub const fn as_str(self) -> &'static str {
413        match self {
414            Self::InvalidName => "invalid-name",
415            Self::UnknownRule => "unknown-rule",
416            Self::Collision => "collision",
417        }
418    }
419}
420
421/// A refused rename.
422#[derive(Clone, Debug, PartialEq, Eq)]
423pub struct GrammarRenameError {
424    kind: GrammarRenameErrorKind,
425    message: String,
426}
427
428impl GrammarRenameError {
429    fn new(kind: GrammarRenameErrorKind, message: impl Into<String>) -> Self {
430        Self {
431            kind,
432            message: message.into(),
433        }
434    }
435
436    /// Why the rename was refused.
437    #[must_use]
438    pub const fn kind(&self) -> GrammarRenameErrorKind {
439        self.kind
440    }
441}
442
443impl fmt::Display for GrammarRenameError {
444    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
445        formatter.write_str(&self.message)
446    }
447}
448
449impl Error for GrammarRenameError {}
450
451/// Maps a canonical rule name back to its original source name.
452#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
453pub struct RuleAlias {
454    /// Current name in the grammar.
455    pub canonical: String,
456    /// Name in the source grammar.
457    pub original: String,
458}
459
460/// A renamed grammar and its source aliases.
461#[derive(Clone, Debug, PartialEq, Eq)]
462pub struct RenamedGrammar {
463    /// The grammar after the rename.
464    pub grammar: Grammar,
465    /// Aliases from canonical names to original source names.
466    pub aliases: Vec<RuleAlias>,
467}
468
469/// Merges grammars of several sources without user interaction.
470///
471/// Sources of different languages or editions are never merged with each
472/// other. Within one language edition, rules are merged only when their
473/// normalized definitions are equivalent under a recursive structural
474/// bisimulation; similar names and identical samples only nominate candidates.
475pub fn merge_grammars(
476    sources: &[GrammarMergeSource],
477    options: &GrammarMergeOptions<'_>,
478) -> Result<GrammarMergeResult, GrammarMergeError> {
479    let prepared = prepare_sources(sources)?;
480    let samples = normalize_samples(&options.samples);
481    let required: BTreeSet<(String, String)> = options
482        .required_equivalences
483        .iter()
484        .map(|(first, second)| {
485            if first <= second {
486                (first.clone(), second.clone())
487            } else {
488                (second.clone(), first.clone())
489            }
490        })
491        .collect();
492    let previous_groups: BTreeMap<&str, &MergedGrammarGroup> = options
493        .previous
494        .map(|previous| {
495            previous
496                .groups
497                .iter()
498                .map(|group| (group.key.as_str(), group))
499                .collect()
500        })
501        .unwrap_or_default();
502
503    let mut grouped: BTreeMap<(&str, &str), Vec<&Prepared<'_>>> = BTreeMap::new();
504    for source in &prepared {
505        grouped
506            .entry((source.language, source.edition))
507            .or_default()
508            .push(source);
509    }
510
511    let mut groups = Vec::new();
512    let mut reused = Vec::new();
513    let mut recomputed = Vec::new();
514    for ((language, edition), entry) in grouped {
515        let key = group_key(language, edition);
516        let ids: BTreeSet<&str> = entry.iter().map(|source| source.id).collect();
517        let group_required: Vec<&(String, String)> = required
518            .iter()
519            .filter(|(first, second)| {
520                ids.contains(source_of(first)) || ids.contains(source_of(second))
521            })
522            .collect();
523        let fingerprint = group_fingerprint(
524            language,
525            edition,
526            &entry,
527            &group_required,
528            &samples,
529            &options.decorators,
530            options.reconcile,
531        )?;
532        let previous = previous_groups.get(key.as_str()).copied();
533        if let Some(previous) = previous.filter(|previous| previous.fingerprint == fingerprint) {
534            groups.push(previous.clone());
535            reused.push(key);
536            continue;
537        }
538        let empty = BTreeMap::new();
539        let previous_identities = previous.map_or(&empty, |previous| &previous.identities);
540        let mut group = merge_group(
541            language,
542            edition,
543            &entry,
544            fingerprint,
545            &samples,
546            previous_identities,
547            options.reconcile,
548        )?;
549        group.decisions = decorate_decisions(group.decisions, &options.decorators)?;
550        groups.push(group);
551        recomputed.push(key);
552    }
553
554    let alternatives = edition_alternatives(&groups);
555    let failures = required_failures(&required, &groups);
556    Ok(GrammarMergeResult {
557        groups,
558        alternatives,
559        failures,
560        reused,
561        recomputed,
562    })
563}
564
565fn decorate_decisions(
566    decisions: Vec<GrammarMergeDecision>,
567    decorators: &DecoratorSet,
568) -> Result<Vec<GrammarMergeDecision>, GrammarMergeError> {
569    if !decorators.has(DecoratorLevel::MergeDecision) {
570        return Ok(decisions);
571    }
572    let mut kept = Vec::with_capacity(decisions.len());
573    for mut decision in decisions {
574        let record = decorator_record([
575            ("kind", decision.kind.as_str()),
576            ("name", &decision.name),
577            ("members", &decision.members.join(" ")),
578            ("basis", &decision.basis),
579            (
580                "definition",
581                decision.definition.as_deref().unwrap_or_default(),
582            ),
583        ]);
584        let Some(decorated) = decorators.decorate(DecoratorLevel::MergeDecision, &record) else {
585            continue;
586        };
587        let kind = record_field(&decorated, "kind");
588        decision.kind = GrammarMergeDecisionKind::parse(kind).ok_or_else(|| {
589            GrammarMergeError::new(format!(
590                "a decorator set the unknown decision kind {kind:?}"
591            ))
592        })?;
593        record_field(&decorated, "basis").clone_into(&mut decision.basis);
594        kept.push(decision);
595    }
596    Ok(kept)
597}
598
599/// Fails when a merge left a required equivalence unresolved.
600pub fn assert_merge_complete(
601    result: &GrammarMergeResult,
602) -> Result<&GrammarMergeResult, GrammarMergeError> {
603    if result.failures.is_empty() {
604        return Ok(result);
605    }
606    let detail = result
607        .failures
608        .iter()
609        .map(|failure| {
610            format!(
611                "{} = {} ({})",
612                failure.members[0],
613                failure.members[1],
614                failure.reason.as_str()
615            )
616        })
617        .collect::<Vec<_>>()
618        .join("; ");
619    Err(GrammarMergeError {
620        message: format!("unresolved required equivalence: {detail}"),
621        failures: result.failures.clone(),
622        concatenated: Vec::new(),
623    })
624}
625
626/// The decisions of a merge group that share a rule between its sources: the
627/// merged and reconciled classes with members of more than one source.
628#[must_use]
629pub fn shared_rule_decisions(group: &MergedGrammarGroup) -> Vec<&GrammarMergeDecision> {
630    group
631        .decisions
632        .iter()
633        .filter(|decision| {
634            matches!(
635                decision.kind,
636                GrammarMergeDecisionKind::Merged | GrammarMergeDecisionKind::Reconciled
637            ) && decision
638                .members
639                .iter()
640                .map(|member| source_of(member))
641                .collect::<BTreeSet<_>>()
642                .len()
643                > 1
644        })
645        .collect()
646}
647
648/// Fails when a group of two or more sources shares no rule between them:
649/// such a merge only concatenates its sources side by side.
650pub fn assert_merge_shares(
651    result: &GrammarMergeResult,
652) -> Result<&GrammarMergeResult, GrammarMergeError> {
653    let concatenated: Vec<&MergedGrammarGroup> = result
654        .groups
655        .iter()
656        .filter(|group| group.sources.len() > 1 && shared_rule_decisions(group).is_empty())
657        .collect();
658    if concatenated.is_empty() {
659        return Ok(result);
660    }
661    let detail = concatenated
662        .iter()
663        .map(|group| {
664            format!(
665                "{} ({}: {} rules)",
666                group.key,
667                group.sources.join(", "),
668                group.grammar.rules().len()
669            )
670        })
671        .collect::<Vec<_>>()
672        .join("; ");
673    Err(GrammarMergeError {
674        message: format!("the merge only concatenates its sources, sharing no rule: {detail}"),
675        failures: Vec::new(),
676        concatenated: concatenated.iter().map(|group| group.key.clone()).collect(),
677    })
678}
679
680/// The canonical text of a rule definition after meaning-aware normalization.
681pub fn normalized_rule_definition(rule: &GrammarRule) -> Result<String, GrammarMergeError> {
682    Ok(format!(
683        "{}:{}",
684        rule.kind.as_str(),
685        normalize(&rule.expr, &name_label)?.text
686    ))
687}
meta_language/grammar/merge/mod.rs

meta_language/grammar/merge/
mod.rs
