meta_language/grammar/interchange/lowering/
encoding.rs

1//! The constructs each notation does not carry unchanged and the helper
2//! bodies that encode them in constructs it does.
3
4use super::super::super::emit::case_variants;
5use super::super::super::{CharClassItem, GrammarExpr, RuleKind};
6use super::{GrammarLoweringEncoding, GrammarLoweringError};
7
8/// The highest Unicode code point.
9const MAX_CODE_POINT: u32 = 0x0010_FFFF;
10/// The most characters a character set is expanded to before it is approximated.
11pub const MAX_LOWERED_CHARACTERS: usize = 256;
12
13/// A construct a notation may not carry unchanged.
14#[derive(Clone, Copy, Debug, PartialEq, Eq)]
15pub(super) enum Construct {
16    QuotedLiteral,
17    LiteralInsensitive,
18    CharRange,
19    CharClass,
20    NegatedClass,
21    Any,
22    OrderedChoice,
23    UnorderedChoice,
24    NestedChoice,
25    ChoiceWithEmpty,
26    ParserCharacters,
27    Optional,
28    Repeat0,
29    Repeat1,
30    CountedRepeat,
31    UnboundedRepeat,
32    And,
33    Not,
34    LabeledCapture,
35    UnlabeledCapture,
36    LabelNotIdentifier,
37    Empty,
38}
39
40impl Construct {
41    pub(super) const fn as_str(self) -> &'static str {
42        match self {
43            Self::QuotedLiteral => "quotedLiteral",
44            Self::LiteralInsensitive => "literalInsensitive",
45            Self::CharRange => "charRange",
46            Self::CharClass => "charClass",
47            Self::NegatedClass => "negatedClass",
48            Self::Any => "any",
49            Self::OrderedChoice => "orderedChoice",
50            Self::UnorderedChoice => "unorderedChoice",
51            Self::NestedChoice => "nestedChoice",
52            Self::ChoiceWithEmpty => "choiceWithEmpty",
53            Self::ParserCharacters => "parserCharacters",
54            Self::Optional => "optional",
55            Self::Repeat0 => "repeat0",
56            Self::Repeat1 => "repeat1",
57            Self::CountedRepeat => "countedRepeat",
58            Self::UnboundedRepeat => "unboundedRepeat",
59            Self::And => "and",
60            Self::Not => "not",
61            Self::LabeledCapture => "labeledCapture",
62            Self::UnlabeledCapture => "unlabeledCapture",
63            Self::LabelNotIdentifier => "labelNotIdentifier",
64            Self::Empty => "empty",
65        }
66    }
67}
68
69/// The constructs each notation's emitter and importer do not carry
70/// unchanged, as measured by `experiments/lowering-capability-probe.mjs`.
71pub(super) fn unsupported(format: &str) -> &'static [Construct] {
72    use Construct as C;
73    match format {
74        "abnf" => &[
75            C::NegatedClass,
76            C::Any,
77            C::OrderedChoice,
78            C::And,
79            C::Not,
80            C::LabeledCapture,
81            C::UnlabeledCapture,
82            C::Empty,
83        ],
84        "antlr" => &[
85            C::ParserCharacters,
86            C::LiteralInsensitive,
87            C::OrderedChoice,
88            C::CountedRepeat,
89            C::UnboundedRepeat,
90            C::And,
91            C::Not,
92            C::UnlabeledCapture,
93            C::LabelNotIdentifier,
94        ],
95        "bnf" => &[
96            C::QuotedLiteral,
97            C::LiteralInsensitive,
98            C::CharRange,
99            C::CharClass,
100            C::NegatedClass,
101            C::Any,
102            C::OrderedChoice,
103            C::NestedChoice,
104            C::Optional,
105            C::Repeat0,
106            C::Repeat1,
107            C::CountedRepeat,
108            C::UnboundedRepeat,
109            C::And,
110            C::Not,
111            C::LabeledCapture,
112            C::UnlabeledCapture,
113        ],
114        "ebnf" => &[
115            C::LiteralInsensitive,
116            C::CharRange,
117            C::CharClass,
118            C::NegatedClass,
119            C::Any,
120            C::OrderedChoice,
121            C::CountedRepeat,
122            C::UnboundedRepeat,
123            C::And,
124            C::Not,
125            C::LabeledCapture,
126            C::UnlabeledCapture,
127        ],
128        "gbnf" => &[
129            C::LiteralInsensitive,
130            C::Any,
131            C::OrderedChoice,
132            C::And,
133            C::Not,
134            C::LabeledCapture,
135            C::UnlabeledCapture,
136            C::Empty,
137        ],
138        "lark" => &[
139            C::LiteralInsensitive,
140            C::CharRange,
141            C::Any,
142            C::OrderedChoice,
143            C::UnboundedRepeat,
144            C::And,
145            C::Not,
146            C::LabeledCapture,
147            C::UnlabeledCapture,
148        ],
149        "pest" => &[
150            C::NegatedClass,
151            C::UnorderedChoice,
152            C::LabeledCapture,
153            C::UnlabeledCapture,
154            C::Empty,
155        ],
156        "tree-sitter-json" => &[
157            C::LiteralInsensitive,
158            C::Any,
159            C::OrderedChoice,
160            C::ChoiceWithEmpty,
161            C::CountedRepeat,
162            C::UnboundedRepeat,
163            C::And,
164            C::Not,
165            C::UnlabeledCapture,
166        ],
167        _ => &[],
168    }
169}
170
171/// The rule kinds each notation writes and reads back unchanged, as measured
172/// by `experiments/lowering-kind-probe.mjs`; other rules are lowered to
173/// normal rules with a kind step.
174pub(super) fn kept_kinds(format: &str) -> &'static [RuleKind] {
175    match format {
176        "pest" => &[
177            RuleKind::Normal,
178            RuleKind::Atomic,
179            RuleKind::Silent,
180            RuleKind::Token,
181        ],
182        "tree-sitter-json" => &[RuleKind::Normal, RuleKind::Token],
183        _ => &[RuleKind::Normal],
184    }
185}
186
187fn is_identifier(label: &str) -> bool {
188    let mut bytes = label.bytes();
189    bytes
190        .next()
191        .is_some_and(|first| first.is_ascii_alphabetic() || first == b'_')
192        && bytes.all(|byte| byte.is_ascii_alphanumeric() || byte == b'_')
193}
194
195/// The constructs of `expr` as a whole rule body unless `inner`, outside a
196/// lexer rule unless `lexical`.
197pub(super) fn constructs_of(expr: &GrammarExpr, inner: bool, lexical: bool) -> Vec<Construct> {
198    let character = match expr {
199        GrammarExpr::TerminalInsensitive(value) => !value.is_empty(),
200        GrammarExpr::CharRange(..) | GrammarExpr::CharClass { .. } | GrammarExpr::AnyChar => true,
201        _ => false,
202    };
203    let mut constructs = Vec::new();
204    if !lexical && character {
205        constructs.push(Construct::ParserCharacters);
206    }
207    match expr {
208        GrammarExpr::Terminal(value) if value.contains('"') && value.contains('\'') => {
209            constructs.push(Construct::QuotedLiteral);
210        }
211        GrammarExpr::TerminalInsensitive(value) if !value.is_empty() => {
212            constructs.push(Construct::LiteralInsensitive);
213        }
214        GrammarExpr::CharRange(..) => constructs.push(Construct::CharRange),
215        GrammarExpr::CharClass { negated, .. } => constructs.push(if *negated {
216            Construct::NegatedClass
217        } else {
218            Construct::CharClass
219        }),
220        GrammarExpr::AnyChar => constructs.push(Construct::Any),
221        GrammarExpr::Choice {
222            ordered,
223            alternatives,
224        } => {
225            constructs.push(if *ordered {
226                Construct::OrderedChoice
227            } else {
228                Construct::UnorderedChoice
229            });
230            if alternatives.contains(&GrammarExpr::Empty) {
231                constructs.push(Construct::ChoiceWithEmpty);
232            }
233            if inner {
234                constructs.push(Construct::NestedChoice);
235            }
236        }
237        GrammarExpr::Optional(_) => constructs.push(Construct::Optional),
238        GrammarExpr::ZeroOrMore(_) => constructs.push(Construct::Repeat0),
239        GrammarExpr::OneOrMore(_) => constructs.push(Construct::Repeat1),
240        GrammarExpr::And(_) => constructs.push(Construct::And),
241        GrammarExpr::Not(_) => constructs.push(Construct::Not),
242        GrammarExpr::Empty => constructs.push(Construct::Empty),
243        GrammarExpr::Repeat { max, .. } => constructs.push(if max.is_none() {
244            Construct::UnboundedRepeat
245        } else {
246            Construct::CountedRepeat
247        }),
248        GrammarExpr::Capture { label: None, .. } => constructs.push(Construct::UnlabeledCapture),
249        GrammarExpr::Capture {
250            label: Some(label), ..
251        } => {
252            constructs.push(Construct::LabeledCapture);
253            if !is_identifier(label) {
254                constructs.push(Construct::LabelNotIdentifier);
255            }
256        }
257        _ => {}
258    }
259    constructs
260}
261
262fn literal(value: impl Into<String>) -> GrammarExpr {
263    GrammarExpr::Terminal(value.into())
264}
265
266fn unordered(mut items: Vec<GrammarExpr>) -> GrammarExpr {
267    if items.len() == 1 {
268        items.remove(0)
269    } else {
270        GrammarExpr::Choice {
271            ordered: false,
272            alternatives: items,
273        }
274    }
275}
276
277fn seq(mut items: Vec<GrammarExpr>) -> GrammarExpr {
278    if items.len() == 1 {
279        items.remove(0)
280    } else {
281        GrammarExpr::Sequence(items)
282    }
283}
284
285fn to_char(point: u32) -> char {
286    char::from_u32(point).unwrap_or(char::REPLACEMENT_CHARACTER)
287}
288
289/// The expression a notation reads back as matching the empty text.
290fn empty_encoding(format: &str) -> GrammarExpr {
291    if format == "abnf" {
292        GrammarExpr::TerminalInsensitive(String::new())
293    } else if unsupported(format).contains(&Construct::Empty) {
294        literal("")
295    } else {
296        GrammarExpr::Empty
297    }
298}
299
300/// The code point ranges of a character set's items.
301fn item_ranges(items: &[CharClassItem]) -> Vec<(u32, u32)> {
302    items
303        .iter()
304        .map(|item| match item {
305            CharClassItem::Char(value) => (u32::from(*value), u32::from(*value)),
306            CharClassItem::Range(start, end) => (u32::from(*start), u32::from(*end)),
307        })
308        .collect()
309}
310
311/// Sorted, merged, non-overlapping ranges.
312fn merge_ranges(mut ranges: Vec<(u32, u32)>) -> Vec<(u32, u32)> {
313    ranges.sort_by_key(|range| range.0);
314    let mut merged: Vec<(u32, u32)> = Vec::new();
315    for (start, end) in ranges {
316        match merged.last_mut() {
317            Some(last) if start <= last.1 + 1 => last.1 = last.1.max(end),
318            _ => merged.push((start, end)),
319        }
320    }
321    merged
322}
323
324/// The ranges of every character outside `ranges`, surrogate code points left out.
325fn complement_ranges(mut ranges: Vec<(u32, u32)>) -> Vec<(u32, u32)> {
326    ranges.push((0xD800, 0xDFFF));
327    let mut complement = Vec::new();
328    let mut next = 0;
329    for (start, end) in merge_ranges(ranges) {
330        if start > next {
331            complement.push((next, start - 1));
332        }
333        next = end + 1;
334    }
335    if next <= MAX_CODE_POINT {
336        complement.push((next, MAX_CODE_POINT));
337    }
338    complement
339}
340
341/// A character set as constructs `format` writes: one character class where
342/// the notation has classes and a choice of single characters otherwise. A
343/// set too large to spell character by character is limited to printable
344/// ASCII. Returns the expression and whether it is exact.
345fn character_set_encoding(
346    format: &str,
347    ranges: &[(u32, u32)],
348) -> Result<(GrammarExpr, bool), GrammarLoweringError> {
349    if !unsupported(format).contains(&Construct::CharClass) {
350        let items: Vec<CharClassItem> = ranges
351            .iter()
352            .map(|&(start, end)| {
353                if start == end {
354                    CharClassItem::Char(to_char(start))
355                } else {
356                    CharClassItem::Range(to_char(start), to_char(end))
357                }
358            })
359            .collect();
360        if let [CharClassItem::Char(value)] = items.as_slice() {
361            return Ok((literal(value.to_string()), true));
362        }
363        return Ok((
364            GrammarExpr::CharClass {
365                negated: false,
366                items,
367            },
368            true,
369        ));
370    }
371    let size: u32 = ranges.iter().map(|(start, end)| end - start + 1).sum();
372    let exact = usize::try_from(size).is_ok_and(|size| size <= MAX_LOWERED_CHARACTERS);
373    let characters: Vec<char> = if exact {
374        ranges
375            .iter()
376            .flat_map(|&(start, end)| (start..=end).filter_map(char::from_u32))
377            .collect()
378    } else {
379        (0x20..0x7F)
380            .filter(|point| {
381                ranges
382                    .iter()
383                    .any(|(start, end)| point >= start && point <= end)
384            })
385            .map(to_char)
386            .collect()
387    };
388    if characters.is_empty() {
389        return Err(GrammarLoweringError::Unencodable(format.to_owned()));
390    }
391    Ok((
392        unordered(
393            characters
394                .into_iter()
395                .map(|value| literal(value.to_string()))
396                .collect(),
397        ),
398        exact,
399    ))
400}
401
402/// Whether ordered and unordered readings of a choice accept the same texts.
403fn choice_order_irrelevant(items: &[GrammarExpr]) -> bool {
404    let values: Option<Vec<&str>> = items
405        .iter()
406        .map(|item| match item {
407            GrammarExpr::Terminal(value) if !value.is_empty() => Some(value.as_str()),
408            _ => None,
409        })
410        .collect();
411    values.is_some_and(|values| {
412        values.iter().enumerate().all(|(index, value)| {
413            values
414                .iter()
415                .enumerate()
416                .all(|(at, other)| at == index || !other.starts_with(value))
417        })
418    })
419}
420
421type Encoding = (GrammarExpr, GrammarLoweringEncoding, &'static str);
422
423const fn exact(body: GrammarExpr, note: &'static str) -> Encoding {
424    (body, GrammarLoweringEncoding::Exact, note)
425}
426
427const fn approximate(body: GrammarExpr, note: &'static str) -> Encoding {
428    (body, GrammarLoweringEncoding::Approximate, note)
429}
430
431fn quoted_literal_runs(value: &str) -> GrammarExpr {
432    let mut runs: Vec<String> = Vec::new();
433    for character in value.chars() {
434        if let Some(last) = runs.last_mut() {
435            let candidate = format!("{last}{character}");
436            if !(candidate.contains('"') && candidate.contains('\'')) {
437                *last = candidate;
438                continue;
439            }
440        }
441        runs.push(character.to_string());
442    }
443    seq(runs.into_iter().map(literal).collect())
444}
445
446fn case_insensitive_sequence(value: &str) -> GrammarExpr {
447    let mut items: Vec<GrammarExpr> = Vec::new();
448    for character in value.chars() {
449        if let Some(variants) = case_variants(character) {
450            items.push(GrammarExpr::CharClass {
451                negated: false,
452                items: variants.into_iter().map(CharClassItem::Char).collect(),
453            });
454        } else if let Some(GrammarExpr::Terminal(last)) = items.last_mut() {
455            last.push(character);
456        } else {
457            items.push(literal(character.to_string()));
458        }
459    }
460    seq(items)
461}
462
463fn counted_repeat(item: &GrammarExpr, min: usize, max: Option<usize>) -> GrammarExpr {
464    let mut items = vec![item.clone(); min];
465    let rest = max.map_or_else(
466        || Some(GrammarExpr::ZeroOrMore(Box::new(item.clone()))),
467        |max| {
468            (0..max.saturating_sub(min)).fold(None, |rest, _| {
469                Some(GrammarExpr::Optional(Box::new(rest.map_or_else(
470                    || item.clone(),
471                    |rest| seq(vec![item.clone(), rest]),
472                ))))
473            })
474        },
475    );
476    items.extend(rest);
477    if items.is_empty() {
478        GrammarExpr::Empty
479    } else {
480        seq(items)
481    }
482}
483
484/// The helper body encoding `expr`'s `construct` in `format`, whether it is
485/// exact and a note.
486pub(super) fn encode(
487    format: &str,
488    construct: Construct,
489    expr: &GrammarExpr,
490    helper: &str,
491) -> Result<Encoding, GrammarLoweringError> {
492    let encoding = match (construct, expr) {
493        (Construct::QuotedLiteral, GrammarExpr::Terminal(value)) => exact(
494            quoted_literal_runs(value),
495            "a literal with both quote characters as a sequence of literals",
496        ),
497        (Construct::LiteralInsensitive, GrammarExpr::TerminalInsensitive(value)) => exact(
498            case_insensitive_sequence(value),
499            "a case-insensitive literal as per-letter character sets",
500        ),
501        (Construct::CharRange | Construct::CharClass, _) => {
502            let ranges = match expr {
503                GrammarExpr::CharRange(start, end) => vec![(u32::from(*start), u32::from(*end))],
504                GrammarExpr::CharClass { items, .. } => item_ranges(items),
505                _ => Vec::new(),
506            };
507            match character_set_encoding(format, &merge_ranges(ranges))? {
508                (body, true) => exact(body, "a character set as the characters or ranges it holds"),
509                (body, false) => approximate(body, "a character set limited to printable ASCII"),
510            }
511        }
512        (Construct::NegatedClass, GrammarExpr::CharClass { items, .. }) if format == "pest" => {
513            exact(
514                seq(vec![
515                    GrammarExpr::Not(Box::new(GrammarExpr::CharClass {
516                        negated: false,
517                        items: items.clone(),
518                    })),
519                    GrammarExpr::AnyChar,
520                ]),
521                "a negated character class as a negative lookahead and any character",
522            )
523        }
524        (Construct::NegatedClass, GrammarExpr::CharClass { items, .. }) => {
525            match character_set_encoding(format, &complement_ranges(item_ranges(items)))? {
526                (body, true) => exact(
527                    body,
528                    "a negated character class as the ranges of its complement",
529                ),
530                (body, false) => {
531                    approximate(body, "a negated character class limited to printable ASCII")
532                }
533            }
534        }
535        (Construct::Any, _) => match character_set_encoding(format, &[(0, MAX_CODE_POINT)])? {
536            (body, true) => exact(body, "any character as the range of every code point"),
537            (body, false) => approximate(body, "any character limited to printable ASCII"),
538        },
539        (
540            Construct::OrderedChoice | Construct::UnorderedChoice,
541            GrammarExpr::Choice { alternatives, .. },
542        ) => {
543            let body = GrammarExpr::Choice {
544                ordered: construct == Construct::UnorderedChoice,
545                alternatives: alternatives.clone(),
546            };
547            if choice_order_irrelevant(alternatives) {
548                exact(
549                    body,
550                    "a choice of literals none of which starts another, whose order is irrelevant",
551                )
552            } else if construct == Construct::OrderedChoice {
553                approximate(body, "an ordered choice written as an unordered one")
554            } else {
555                approximate(body, "an unordered choice written as an ordered one")
556            }
557        }
558        (Construct::NestedChoice, _) => exact(expr.clone(), "a nested choice as a rule of its own"),
559        (
560            Construct::ChoiceWithEmpty,
561            GrammarExpr::Choice {
562                ordered,
563                alternatives,
564            },
565        ) => {
566            let mut items: Vec<GrammarExpr> = alternatives
567                .iter()
568                .filter(|item| **item != GrammarExpr::Empty)
569                .cloned()
570                .collect();
571            let item = if items.len() == 1 {
572                items.remove(0)
573            } else {
574                GrammarExpr::Choice {
575                    ordered: *ordered,
576                    alternatives: items,
577                }
578            };
579            exact(
580                GrammarExpr::Optional(Box::new(item)),
581                "a choice with the empty expression as an optional choice",
582            )
583        }
584        (Construct::ParserCharacters, _) => exact(
585            expr.clone(),
586            "a character-level construct as a lexer rule of its own",
587        ),
588        (Construct::Optional, GrammarExpr::Optional(item)) => exact(
589            unordered(vec![(**item).clone(), GrammarExpr::Empty]),
590            "an optional item as a choice with the empty expression",
591        ),
592        (Construct::Repeat0, GrammarExpr::ZeroOrMore(item)) => exact(
593            unordered(vec![
594                seq(vec![
595                    (**item).clone(),
596                    GrammarExpr::NonTerminal(helper.to_owned()),
597                ]),
598                GrammarExpr::Empty,
599            ]),
600            "a repetition as a right-recursive rule",
601        ),
602        (Construct::Repeat1, GrammarExpr::OneOrMore(item)) => exact(
603            unordered(vec![
604                seq(vec![
605                    (**item).clone(),
606                    GrammarExpr::NonTerminal(helper.to_owned()),
607                ]),
608                (**item).clone(),
609            ]),
610            "a repetition as a right-recursive rule",
611        ),
612        (
613            Construct::CountedRepeat | Construct::UnboundedRepeat,
614            GrammarExpr::Repeat {
615                expr: item,
616                min,
617                max,
618            },
619        ) => exact(
620            counted_repeat(item, *min, *max),
621            "a counted repetition as copies and nested optional items",
622        ),
623        (Construct::And, _) => approximate(
624            empty_encoding(format),
625            "a positive lookahead written as the empty expression",
626        ),
627        (Construct::Not, _) => approximate(
628            empty_encoding(format),
629            "a negative lookahead written as the empty expression",
630        ),
631        (
632            Construct::LabeledCapture | Construct::UnlabeledCapture | Construct::LabelNotIdentifier,
633            GrammarExpr::Capture { expr: item, .. },
634        ) => exact((**item).clone(), "a capture as a rule of its own"),
635        (Construct::Empty, _) => exact(
636            empty_encoding(format),
637            "the empty expression as the empty literal",
638        ),
639        _ => unreachable!("constructs_of pairs every construct with its expression"),
640    };
641    Ok(encoding)
642}
meta_language/grammar/interchange/lowering/encoding.rs

meta_language/grammar/interchange/lowering/
encoding.rs
