meta_language/
grammar_concepts.rs

1//! The concepts of the native grammars (requirement
2//! I195-GRAMMAR-SHARED-CONCEPTS): every rule of every native grammar names a
3//! canonical concept record with `(concept ID)`, and the record carries a
4//! `native:<language>` source alias for each rule that names it. A concept
5//! that two or more native grammars name is shared; a concept that one grammar
6//! names is specific to that language. A construct translates from one native
7//! grammar to another through its concept record alone, with no rule for the
8//! pair of languages. This is the port of `js/src/grammar-concepts.js`.
9
10use std::collections::{BTreeMap, BTreeSet};
11
12use crate::decorators::{
13    DecoratorError, DecoratorLevel, DecoratorSet, decorator_record, record_field,
14};
15use crate::language_catalog::{native_grammar, native_grammars};
16use crate::native_grammar_parser::{native_grammar_text, native_parser};
17use crate::{ConceptRecord, FeatureParseOptions, SyntaxTree, concept_records, parse_grammar_links};
18
19const NATIVE_SOURCE_PREFIX: &str = "native:";
20
21/// A rule of a native grammar and the concept it names.
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub struct NativeRuleConcept {
24    /// The rule name.
25    pub rule: String,
26    /// The concept identity the rule names, or `None` when it names none.
27    pub concept: Option<String>,
28}
29
30/// What is wrong with the concept of a native grammar rule.
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum NativeConceptProblemKind {
33    /// The rule names no concept.
34    RuleWithoutConcept,
35    /// No record has the concept the rule names.
36    ConceptWithoutRecord,
37    /// The record of the rule's concept has no source alias for the rule.
38    RuleWithoutAlias,
39    /// A record has a source alias for a rule that does not name it.
40    AliasWithoutRule,
41    /// The rule names a concept in another language's namespace.
42    NamespaceMismatch,
43}
44
45impl NativeConceptProblemKind {
46    /// The kebab-case name the JavaScript runtime uses.
47    #[must_use]
48    pub const fn as_str(self) -> &'static str {
49        match self {
50            Self::RuleWithoutConcept => "rule-without-concept",
51            Self::ConceptWithoutRecord => "concept-without-record",
52            Self::RuleWithoutAlias => "rule-without-alias",
53            Self::AliasWithoutRule => "alias-without-rule",
54            Self::NamespaceMismatch => "namespace-mismatch",
55        }
56    }
57}
58
59/// One problem `check_native_grammar_concepts` finds.
60#[derive(Debug, Clone, PartialEq, Eq)]
61pub struct NativeConceptProblem {
62    /// What is wrong.
63    pub kind: NativeConceptProblemKind,
64    /// The native grammar id, such as `native-json`.
65    pub grammar: String,
66    /// The rule name.
67    pub rule: String,
68    /// The concept identity involved, if any.
69    pub concept: Option<String>,
70}
71
72/// The id of every native grammar of the catalog, sorted.
73#[must_use]
74pub fn native_grammar_ids() -> Vec<&'static str> {
75    let mut ids: Vec<&'static str> = native_grammars()
76        .iter()
77        .map(|grammar| grammar.id.as_str())
78        .collect();
79    ids.sort_unstable();
80    ids
81}
82
83/// The language of the native grammar `id`, its file name: `json` for
84/// `native-json`.
85#[must_use]
86pub fn native_grammar_language(id: &str) -> Option<&'static str> {
87    let file = native_grammar(id)?.file.as_str();
88    let name = file.rsplit('/').next().unwrap_or(file);
89    Some(name.strip_suffix(".lino").unwrap_or(name))
90}
91
92/// The source concept records name the rules of the native grammar `id`
93/// under: `native:json`.
94#[must_use]
95pub fn native_grammar_source(id: &str) -> Option<String> {
96    native_grammar_language(id).map(|language| format!("{NATIVE_SOURCE_PREFIX}{language}"))
97}
98
99/// Every rule of the native grammar `id` with the concept it names, in
100/// grammar order; empty for an id that names no native grammar.
101#[must_use]
102pub fn native_grammar_rule_concepts(id: &str) -> Vec<NativeRuleConcept> {
103    native_grammar_text(id)
104        .and_then(|text| parse_grammar_links(text).ok())
105        .map(|grammar| {
106            grammar
107                .rules()
108                .iter()
109                .map(|rule| NativeRuleConcept {
110                    rule: rule.name.clone(),
111                    concept: rule.concept.clone(),
112                })
113                .collect()
114        })
115        .unwrap_or_default()
116}
117
118// The language a concept identity is specific to by its namespace:
119// `grammar.diff.hunk` belongs to diff.
120fn namespace_language<'a>(concept: &'a str, languages: &BTreeSet<&str>) -> Option<&'a str> {
121    let parts: Vec<&str> = concept.split('.').collect();
122    (parts.len() > 2 && languages.contains(parts[1])).then(|| parts[1])
123}
124
125/// Checks the concepts of every rule of every native grammar.
126///
127/// Every rule names a concept that has a record, the records' native source
128/// aliases are exactly the rules that name them, and a concept in a language
129/// namespace (`grammar.diff.…`) is named by that language alone.
130#[must_use]
131pub fn check_native_grammar_concepts() -> Vec<NativeConceptProblem> {
132    check_native_grammar_concepts_in(
133        concept_records(),
134        &native_grammar_ids(),
135        &native_grammar_rule_concepts,
136    )
137}
138
139/// `check_native_grammar_concepts` over the records `records`, the native
140/// grammars `grammars` and the rule concepts `rule_concepts` gives each.
141#[must_use]
142pub fn check_native_grammar_concepts_in(
143    records: &[ConceptRecord],
144    grammars: &[&str],
145    rule_concepts: &dyn Fn(&str) -> Vec<NativeRuleConcept>,
146) -> Vec<NativeConceptProblem> {
147    let by_id: BTreeMap<&str, &ConceptRecord> = records
148        .iter()
149        .map(|record| (record.id.as_str(), record))
150        .collect();
151    let languages: BTreeSet<&str> = grammars
152        .iter()
153        .filter_map(|id| native_grammar_language(id))
154        .collect();
155    let mut problems = Vec::new();
156    for &grammar in grammars {
157        let (Some(source), Some(language)) = (
158            native_grammar_source(grammar),
159            native_grammar_language(grammar),
160        ) else {
161            continue;
162        };
163        let problem = |kind, rule: &str, concept: Option<&str>| NativeConceptProblem {
164            kind,
165            grammar: grammar.to_owned(),
166            rule: rule.to_owned(),
167            concept: concept.map(str::to_owned),
168        };
169        let mut named = BTreeMap::new();
170        for NativeRuleConcept { rule, concept } in rule_concepts(grammar) {
171            let Some(concept) = concept else {
172                problems.push(problem(
173                    NativeConceptProblemKind::RuleWithoutConcept,
174                    &rule,
175                    None,
176                ));
177                continue;
178            };
179            let Some(record) = by_id.get(concept.as_str()) else {
180                problems.push(problem(
181                    NativeConceptProblemKind::ConceptWithoutRecord,
182                    &rule,
183                    Some(&concept),
184                ));
185                named.insert(rule, concept);
186                continue;
187            };
188            if !record
189                .source_aliases
190                .iter()
191                .any(|alias| alias.source == source && alias.name == rule)
192            {
193                problems.push(problem(
194                    NativeConceptProblemKind::RuleWithoutAlias,
195                    &rule,
196                    Some(&concept),
197                ));
198            }
199            if namespace_language(&concept, &languages).is_some_and(|owner| owner != language) {
200                problems.push(problem(
201                    NativeConceptProblemKind::NamespaceMismatch,
202                    &rule,
203                    Some(&concept),
204                ));
205            }
206            named.insert(rule, concept);
207        }
208        for record in records {
209            for alias in &record.source_aliases {
210                if alias.source == source && named.get(&alias.name) != Some(&record.id) {
211                    problems.push(problem(
212                        NativeConceptProblemKind::AliasWithoutRule,
213                        &alias.name,
214                        Some(&record.id),
215                    ));
216                }
217            }
218        }
219    }
220    problems
221}
222
223/// A rule that names a concept two or more native grammars name.
224#[derive(Debug, Clone, PartialEq, Eq)]
225pub struct SharedRule {
226    /// The rule name.
227    pub rule: String,
228    /// The shared concept identity.
229    pub concept: String,
230    /// The languages whose native grammars name the concept, sorted.
231    pub languages: Vec<String>,
232}
233
234/// A rule that names a concept only its own native grammar names.
235#[derive(Debug, Clone, PartialEq, Eq)]
236pub struct SpecificRule {
237    /// The rule name.
238    pub rule: String,
239    /// The language-specific concept identity.
240    pub concept: String,
241}
242
243/// The reuse of one native grammar: its rules split into shared and
244/// language-specific ones.
245#[derive(Debug, Clone, PartialEq, Eq)]
246pub struct GrammarConceptReuse {
247    /// The native grammar id.
248    pub grammar: String,
249    /// The language of the grammar.
250    pub language: String,
251    /// The number of rules.
252    pub rules: usize,
253    /// The rules that name a shared concept.
254    pub shared: Vec<SharedRule>,
255    /// The rules that name a language-specific concept.
256    pub specific: Vec<SpecificRule>,
257}
258
259/// A concept the native grammars name, with the languages that name it.
260#[derive(Debug, Clone, PartialEq, Eq)]
261pub struct ConceptReuse {
262    /// The concept identity.
263    pub concept: String,
264    /// The languages whose native grammars name the concept, sorted.
265    pub languages: Vec<String>,
266    /// Whether two or more languages name the concept.
267    pub shared: bool,
268}
269
270/// The per-language reuse report of the native grammars.
271#[derive(Debug, Clone, PartialEq, Eq)]
272pub struct NativeConceptReuse {
273    /// The reuse of each native grammar, by grammar id.
274    pub grammars: Vec<GrammarConceptReuse>,
275    /// Every concept the native grammars name, by identity.
276    pub concepts: Vec<ConceptReuse>,
277}
278
279/// The per-language reuse report of the native grammars.
280///
281/// For every native grammar, its rules split into those that name a shared
282/// concept (one two or more native grammars name, listed with those
283/// languages) and those that name a concept specific to that language; and
284/// every concept the native grammars name with the languages that name it.
285#[must_use]
286pub fn native_grammar_concept_reuse() -> NativeConceptReuse {
287    let grammars = native_grammar_ids();
288    let language_of: BTreeMap<String, &str> = grammars
289        .iter()
290        .filter_map(|id| Some((native_grammar_source(id)?, native_grammar_language(id)?)))
291        .collect();
292    let mut languages: BTreeMap<&str, Vec<String>> = BTreeMap::new();
293    for record in concept_records() {
294        let named: BTreeSet<&str> = record
295            .source_aliases
296            .iter()
297            .filter_map(|alias| language_of.get(&alias.source).copied())
298            .collect();
299        if !named.is_empty() {
300            languages.insert(&record.id, named.into_iter().map(str::to_owned).collect());
301        }
302    }
303    let report = grammars
304        .iter()
305        .map(|&grammar| {
306            let mut shared = Vec::new();
307            let mut specific = Vec::new();
308            for NativeRuleConcept { rule, concept } in native_grammar_rule_concepts(grammar) {
309                let concept = concept.unwrap_or_default();
310                match languages.get(concept.as_str()) {
311                    Some(named) if named.len() > 1 => shared.push(SharedRule {
312                        rule,
313                        concept,
314                        languages: named.clone(),
315                    }),
316                    _ => specific.push(SpecificRule { rule, concept }),
317                }
318            }
319            GrammarConceptReuse {
320                grammar: grammar.to_owned(),
321                language: native_grammar_language(grammar)
322                    .unwrap_or_default()
323                    .to_owned(),
324                rules: shared.len() + specific.len(),
325                shared,
326                specific,
327            }
328        })
329        .collect();
330    let concepts = languages
331        .into_iter()
332        .map(|(concept, named)| ConceptReuse {
333            concept: concept.to_owned(),
334            shared: named.len() > 1,
335            languages: named,
336        })
337        .collect();
338    NativeConceptReuse {
339        grammars: report,
340        concepts,
341    }
342}
343
344/// How a construct translates from one native grammar to another.
345#[derive(Debug, Clone, Copy, PartialEq, Eq)]
346pub enum ConstructTranslationRelation {
347    /// The target grammar names one rule with the construct's concept.
348    Translated,
349    /// The target grammar names no rule with the construct's concept.
350    Untranslatable,
351    /// Several records name the rule, or the target names several rules.
352    Ambiguous,
353    /// No record names the rule.
354    Unknown,
355}
356
357impl ConstructTranslationRelation {
358    /// The name the JavaScript runtime uses.
359    #[must_use]
360    pub const fn as_str(self) -> &'static str {
361        match self {
362            Self::Translated => "translated",
363            Self::Untranslatable => "untranslatable",
364            Self::Ambiguous => "ambiguous",
365            Self::Unknown => "unknown",
366        }
367    }
368
369    /// The relation the JavaScript runtime names `name`.
370    #[must_use]
371    pub fn parse(name: &str) -> Option<Self> {
372        [
373            Self::Translated,
374            Self::Untranslatable,
375            Self::Ambiguous,
376            Self::Unknown,
377        ]
378        .into_iter()
379        .find(|relation| relation.as_str() == name)
380    }
381}
382
383/// The translation of one construct between native grammars.
384#[derive(Debug, Clone, PartialEq, Eq)]
385pub struct ConstructTranslation {
386    /// How the construct translates.
387    pub relation: ConstructTranslationRelation,
388    /// The concept the translation went through.
389    pub concept: Option<String>,
390    /// The rules of the target grammar that name the concept.
391    pub rules: Vec<String>,
392}
393
394/// Translates the rule `rule` of the native grammar `from` to `to`.
395///
396/// The translation goes through the concept record whose source alias names
397/// the rule, then that record's alias in the target grammar. No rule for the
398/// pair of languages takes part.
399#[must_use]
400pub fn translate_native_construct(from: &str, rule: &str, to: &str) -> ConstructTranslation {
401    translate_native_construct_in(concept_records(), from, rule, to)
402}
403
404/// `translate_native_construct` over the records `records`.
405#[must_use]
406pub fn translate_native_construct_in(
407    records: &[ConceptRecord],
408    from: &str,
409    rule: &str,
410    to: &str,
411) -> ConstructTranslation {
412    let unknown = ConstructTranslation {
413        relation: ConstructTranslationRelation::Unknown,
414        concept: None,
415        rules: Vec::new(),
416    };
417    let (Some(source), Some(target)) = (native_grammar_source(from), native_grammar_source(to))
418    else {
419        return unknown;
420    };
421    let meanings: Vec<&ConceptRecord> = records
422        .iter()
423        .filter(|record| {
424            record
425                .source_aliases
426                .iter()
427                .any(|alias| alias.source == source && alias.name == rule)
428        })
429        .collect();
430    let record = match meanings.as_slice() {
431        [] => return unknown,
432        [record] => record,
433        _ => {
434            return ConstructTranslation {
435                relation: ConstructTranslationRelation::Ambiguous,
436                ..unknown
437            };
438        }
439    };
440    let rules: Vec<String> = record
441        .source_aliases
442        .iter()
443        .filter(|alias| alias.source == target)
444        .map(|alias| alias.name.clone())
445        .collect();
446    ConstructTranslation {
447        relation: relation_of(&rules),
448        concept: Some(record.id.clone()),
449        rules,
450    }
451}
452
453const fn relation_of(rules: &[String]) -> ConstructTranslationRelation {
454    match rules.len() {
455        1 => ConstructTranslationRelation::Translated,
456        0 => ConstructTranslationRelation::Untranslatable,
457        _ => ConstructTranslationRelation::Ambiguous,
458    }
459}
460
461/// [`translate_native_construct`] after the `concept-mapping` decorators of
462/// `decorators`.
463///
464/// They see the result as `{ from, to, rule, relation,
465/// concept, rules }` (rules joined by spaces): they may change the concept or
466/// the target rules, whose relation then follows from their number unless a
467/// decorator set it, and `drop` makes the construct `unknown`.
468///
469/// # Errors
470///
471/// A [`DecoratorError`] when a decorator sets an unknown relation.
472pub fn translate_native_construct_decorated(
473    from: &str,
474    rule: &str,
475    to: &str,
476    decorators: &DecoratorSet,
477) -> Result<ConstructTranslation, DecoratorError> {
478    let found = translate_native_construct(from, rule, to);
479    if !decorators.has(DecoratorLevel::ConceptMapping) {
480        return Ok(found);
481    }
482    let joined = found.rules.join(" ");
483    let record = decorator_record([
484        ("from", from),
485        ("to", to),
486        ("rule", rule),
487        ("relation", found.relation.as_str()),
488        ("concept", found.concept.as_deref().unwrap_or_default()),
489        ("rules", &joined),
490    ]);
491    let Some(decorated) = decorators.decorate(DecoratorLevel::ConceptMapping, &record) else {
492        return Ok(ConstructTranslation {
493            relation: ConstructTranslationRelation::Unknown,
494            concept: None,
495            rules: Vec::new(),
496        });
497    };
498    let rules: Vec<String> = record_field(&decorated, "rules")
499        .split(' ')
500        .filter(|name| !name.is_empty())
501        .map(str::to_owned)
502        .collect();
503    let relation = record_field(&decorated, "relation");
504    let relation =
505        if relation != found.relation.as_str() || record_field(&decorated, "rules") == joined {
506            ConstructTranslationRelation::parse(relation).ok_or_else(|| {
507                DecoratorError::new(format!("a decorator set the unknown relation {relation:?}"))
508            })?
509        } else {
510            relation_of(&rules)
511        };
512    let concept = record_field(&decorated, "concept");
513    Ok(ConstructTranslation {
514        relation,
515        concept: (!concept.is_empty()).then(|| concept.to_owned()),
516        rules,
517    })
518}
519
520/// A node of a construct tree: a node of a native parse tree whose kind is a
521/// rule of the grammar.
522#[derive(Debug, Clone, PartialEq, Eq)]
523pub struct ConstructTree {
524    /// The rule name.
525    pub kind: String,
526    /// The concept the rule names.
527    pub concept: String,
528    /// The constructs inside it.
529    pub children: Vec<Self>,
530}
531
532/// The construct tree of `source` under the native grammar `id`.
533///
534/// It keeps the nodes of the parse tree whose kind is a rule of the grammar,
535/// without trivia, literals and token kinds that are not rules. `None` when
536/// the grammar does not accept the input.
537#[must_use]
538pub fn native_construct_tree(id: &str, source: &str) -> Option<ConstructTree> {
539    let concepts: BTreeMap<String, String> = native_grammar_rule_concepts(id)
540        .into_iter()
541        .filter_map(|NativeRuleConcept { rule, concept }| Some((rule, concept?)))
542        .collect();
543    let outcome = native_parser(id)?
544        .parse_tree(source.as_bytes(), &FeatureParseOptions::default())
545        .ok()?;
546    let tree = outcome.tree?;
547    if !matches!(tree, SyntaxTree::Node { .. }) {
548        return None;
549    }
550    constructs(&tree, &concepts)?.into_iter().next()
551}
552
553fn constructs(
554    node: &SyntaxTree,
555    concepts: &BTreeMap<String, String>,
556) -> Option<Vec<ConstructTree>> {
557    let (kind, children) = match node {
558        SyntaxTree::Node { kind, children, .. } => {
559            let mut inner = Vec::new();
560            for child in children {
561                inner.extend(constructs(child, concepts)?);
562            }
563            (Some(kind), inner)
564        }
565        SyntaxTree::Token {
566            kind,
567            trivia: false,
568            ..
569        } => (kind.as_ref(), Vec::new()),
570        SyntaxTree::Token { .. } | SyntaxTree::Embed { .. } => (None, Vec::new()),
571        SyntaxTree::Error { .. } | SyntaxTree::Missing { .. } => return None,
572    };
573    match kind.and_then(|kind| Some((kind, concepts.get(kind)?))) {
574        Some((kind, concept)) => Some(vec![ConstructTree {
575            kind: kind.clone(),
576            concept: concept.clone(),
577            children,
578        }]),
579        None => Some(children),
580    }
581}
582
583/// A construct of a tree that does not translate.
584#[derive(Debug, Clone, PartialEq, Eq)]
585pub struct ConstructTranslationProblem {
586    /// The rule name in the source grammar.
587    pub kind: String,
588    /// The concept of the construct, if a record names it.
589    pub concept: Option<String>,
590    /// Why it does not translate.
591    pub relation: ConstructTranslationRelation,
592}
593
594/// The translation of a construct tree between native grammars.
595#[derive(Debug, Clone, PartialEq, Eq)]
596pub struct ConstructTreeTranslation {
597    /// The tree with the target rule names, or `None` when a construct does
598    /// not translate.
599    pub tree: Option<ConstructTree>,
600    /// Every construct that does not translate, children first.
601    pub problems: Vec<ConstructTranslationProblem>,
602}
603
604/// Translates a construct tree of the native grammar `from` to the native
605/// grammar `to`, every node through `translate_native_construct`.
606#[must_use]
607pub fn translate_native_construct_tree(
608    tree: &ConstructTree,
609    from: &str,
610    to: &str,
611) -> ConstructTreeTranslation {
612    fn translate(
613        node: &ConstructTree,
614        from: &str,
615        to: &str,
616        problems: &mut Vec<ConstructTranslationProblem>,
617    ) -> Option<ConstructTree> {
618        let translation = translate_native_construct(from, &node.kind, to);
619        let children: Vec<Option<ConstructTree>> = node
620            .children
621            .iter()
622            .map(|child| translate(child, from, to, problems))
623            .collect();
624        if translation.relation != ConstructTranslationRelation::Translated {
625            problems.push(ConstructTranslationProblem {
626                kind: node.kind.clone(),
627                concept: translation.concept,
628                relation: translation.relation,
629            });
630            return None;
631        }
632        Some(ConstructTree {
633            kind: translation.rules[0].clone(),
634            concept: translation.concept.unwrap_or_default(),
635            children: children.into_iter().collect::<Option<Vec<_>>>()?,
636        })
637    }
638    let mut problems = Vec::new();
639    let translated = translate(tree, from, to, &mut problems);
640    ConstructTreeTranslation {
641        tree: if problems.is_empty() {
642            translated
643        } else {
644            None
645        },
646        problems,
647    }
648}
meta_language/grammar_concepts.rs

meta_language/
grammar_concepts.rs
