meta_language/grammar/import/
abnf.rs

1use std::char;
2
3use ::abnf::types::{
4    Kind as AbnfKind, Node as AbnfNode, Repeat as AbnfRepeat, Rule as AbnfRule,
5    StringLiteral as AbnfStringLiteral, TerminalValues as AbnfTerminalValues,
6};
7
8use super::{parse_error, unsupported_error, GrammarImportError};
9use crate::grammar::{CharClassItem, Grammar, GrammarExpr, GrammarFormat, GrammarRule};
10
11/// Parses Augmented Backus-Naur Form text into the grammar IR.
12///
13/// # Errors
14///
15/// Returns [`GrammarImportError`] when the ABNF text cannot be parsed, when a
16/// parsed construct cannot be represented, or when a non-terminal reference
17/// does not resolve to an imported or RFC 5234 core rule.
18pub fn import_abnf(text: &str) -> Result<Grammar, GrammarImportError> {
19    let normalized = normalize_input(text);
20    let parsed = ::abnf::rulelist(&normalized)
21        .map_err(|error| parse_error(GrammarFormat::Abnf, error.to_string()))?;
22    let mut grammar = lower_grammar(&parsed)?;
23    inject_core_rules(&mut grammar);
24    validate_references(&grammar)?;
25    Ok(grammar)
26}
27
28fn normalize_input(text: &str) -> String {
29    let mut normalized = text.trim().to_string();
30    if !normalized.ends_with('\n') {
31        normalized.push('\n');
32    }
33    normalized
34}
35
36fn lower_grammar(parsed: &[AbnfRule]) -> Result<Grammar, GrammarImportError> {
37    let mut rules = Vec::new();
38    for rule in parsed {
39        let expr = lower_node(rule.node())?;
40        merge_rule(&mut rules, rule.name(), rule.kind(), expr)?;
41    }
42    canonicalize_rule_references(&mut rules);
43
44    let mut grammar = Grammar::new().with_source_format(GrammarFormat::Abnf);
45    for rule in rules {
46        grammar.add_rule(rule);
47    }
48    Ok(grammar)
49}
50
51fn merge_rule(
52    rules: &mut Vec<GrammarRule>,
53    name: &str,
54    kind: AbnfKind,
55    expr: GrammarExpr,
56) -> Result<(), GrammarImportError> {
57    match kind {
58        AbnfKind::Basic => {
59            if find_rule_index(rules, name).is_some() {
60                return Err(parse_error(
61                    GrammarFormat::Abnf,
62                    format!("duplicate rule {name}"),
63                ));
64            }
65            rules.push(GrammarRule::new(name, expr));
66            Ok(())
67        }
68        AbnfKind::Incremental => {
69            let Some(index) = find_rule_index(rules, name) else {
70                return Err(parse_error(
71                    GrammarFormat::Abnf,
72                    format!("incremental alternative for undefined rule {name}"),
73                ));
74            };
75            append_choice_alternative(&mut rules[index].expr, expr);
76            Ok(())
77        }
78    }
79}
80
81fn find_rule_index(rules: &[GrammarRule], name: &str) -> Option<usize> {
82    rules
83        .iter()
84        .position(|rule| rule.name().eq_ignore_ascii_case(name))
85}
86
87fn append_choice_alternative(expr: &mut GrammarExpr, alternative: GrammarExpr) {
88    if let GrammarExpr::Choice {
89        ordered: false,
90        alternatives,
91    } = expr
92    {
93        push_choice_alternative(alternatives, alternative);
94    } else {
95        let previous = std::mem::replace(expr, GrammarExpr::Empty);
96        let mut alternatives = Vec::new();
97        push_choice_alternative(&mut alternatives, previous);
98        push_choice_alternative(&mut alternatives, alternative);
99        *expr = GrammarExpr::Choice {
100            ordered: false,
101            alternatives,
102        };
103    }
104}
105
106fn canonicalize_rule_references(rules: &mut [GrammarRule]) {
107    let names = rules
108        .iter()
109        .map(|rule| rule.name().to_string())
110        .collect::<Vec<_>>();
111    for rule in rules {
112        canonicalize_expr_references(&mut rule.expr, &names);
113    }
114}
115
116fn canonicalize_expr_references(expr: &mut GrammarExpr, names: &[String]) {
117    match expr {
118        GrammarExpr::NonTerminal(name) => {
119            if let Some(canonical) = canonical_rule_name(names, name) {
120                *name = canonical.to_string();
121            }
122        }
123        GrammarExpr::Choice { alternatives, .. } | GrammarExpr::Sequence(alternatives) => {
124            for alternative in alternatives {
125                canonicalize_expr_references(alternative, names);
126            }
127        }
128        GrammarExpr::Optional(expr)
129        | GrammarExpr::ZeroOrMore(expr)
130        | GrammarExpr::OneOrMore(expr)
131        | GrammarExpr::And(expr)
132        | GrammarExpr::Not(expr) => canonicalize_expr_references(expr, names),
133        GrammarExpr::Repeat { expr, .. } | GrammarExpr::Capture { expr, .. } => {
134            canonicalize_expr_references(expr, names);
135        }
136        GrammarExpr::Empty
137        | GrammarExpr::Terminal(_)
138        | GrammarExpr::TerminalInsensitive(_)
139        | GrammarExpr::CharRange(_, _)
140        | GrammarExpr::CharClass { .. }
141        | GrammarExpr::AnyChar => {}
142    }
143}
144
145fn canonical_rule_name<'name>(names: &'name [String], name: &str) -> Option<&'name str> {
146    names
147        .iter()
148        .find(|candidate| candidate.eq_ignore_ascii_case(name))
149        .map(String::as_str)
150}
151
152fn lower_node(node: &AbnfNode) -> Result<GrammarExpr, GrammarImportError> {
153    match node {
154        AbnfNode::Alternatives(nodes) => lower_choice(nodes.iter().map(lower_node)),
155        AbnfNode::Concatenation(nodes) => lower_sequence(nodes.iter().map(lower_node)),
156        AbnfNode::Repetition { repeat, node } => lower_repetition(repeat, node),
157        AbnfNode::Rulename(name) => Ok(GrammarExpr::NonTerminal(name.clone())),
158        AbnfNode::Group(node) => lower_node(node),
159        AbnfNode::Optional(node) => lower_node(node).map(GrammarExpr::optional),
160        AbnfNode::String(literal) => Ok(lower_string(literal)),
161        AbnfNode::TerminalValues(values) => lower_terminal_values(values),
162        AbnfNode::Prose(_) => Err(unsupported_error(GrammarFormat::Abnf, "prose-val")),
163    }
164}
165
166fn lower_string(literal: &AbnfStringLiteral) -> GrammarExpr {
167    let value = literal.as_str().to_string();
168    if literal.is_case_sensitive() {
169        GrammarExpr::Terminal(value)
170    } else {
171        GrammarExpr::TerminalInsensitive(value)
172    }
173}
174
175fn lower_terminal_values(
176    terminal_values: &AbnfTerminalValues,
177) -> Result<GrammarExpr, GrammarImportError> {
178    match terminal_values {
179        AbnfTerminalValues::Range(start, end) if start == end => {
180            decode_terminal(*start).map(GrammarExpr::Terminal)
181        }
182        AbnfTerminalValues::Range(start, end) => {
183            let start = decode_char(*start)?;
184            let end = decode_char(*end)?;
185            Ok(GrammarExpr::CharRange(start, end))
186        }
187        AbnfTerminalValues::Concatenation(values) => {
188            let mut terminal = String::new();
189            for value in values {
190                terminal.push(decode_char(*value)?);
191            }
192            if terminal.is_empty() {
193                Ok(GrammarExpr::Empty)
194            } else {
195                Ok(GrammarExpr::Terminal(terminal))
196            }
197        }
198    }
199}
200
201fn decode_terminal(value: u32) -> Result<String, GrammarImportError> {
202    decode_char(value).map(|character| character.to_string())
203}
204
205fn decode_char(value: u32) -> Result<char, GrammarImportError> {
206    char::from_u32(value).ok_or_else(|| {
207        unsupported_error(
208            GrammarFormat::Abnf,
209            format!("numeric terminal value U+{value:04X}"),
210        )
211    })
212}
213
214fn lower_repetition(
215    repeat: &AbnfRepeat,
216    node: &AbnfNode,
217) -> Result<GrammarExpr, GrammarImportError> {
218    let expr = lower_node(node)?;
219    let (min, max) = match repeat {
220        AbnfRepeat::Specific(count) => (*count, Some(*count)),
221        AbnfRepeat::Variable { min, max } => (min.unwrap_or(0), *max),
222    };
223    Ok(canonical_repeat(expr, min, max))
224}
225
226fn canonical_repeat(expr: GrammarExpr, min: usize, max: Option<usize>) -> GrammarExpr {
227    match (min, max) {
228        (0, None) => GrammarExpr::zero_or_more(expr),
229        (1, None) => GrammarExpr::one_or_more(expr),
230        (0, Some(1)) => GrammarExpr::optional(expr),
231        _ => GrammarExpr::repeat(expr, min, max),
232    }
233}
234
235fn lower_sequence<I>(items: I) -> Result<GrammarExpr, GrammarImportError>
236where
237    I: IntoIterator<Item = Result<GrammarExpr, GrammarImportError>>,
238{
239    let mut lowered = Vec::new();
240    for item in items {
241        push_sequence_item(&mut lowered, item?);
242    }
243
244    Ok(match lowered.len() {
245        0 => GrammarExpr::Empty,
246        1 => lowered.remove(0),
247        _ => GrammarExpr::Sequence(lowered),
248    })
249}
250
251fn push_sequence_item(items: &mut Vec<GrammarExpr>, item: GrammarExpr) {
252    match item {
253        GrammarExpr::Empty => {}
254        GrammarExpr::Sequence(nested) => {
255            for item in nested {
256                push_sequence_item(items, item);
257            }
258        }
259        item => items.push(item),
260    }
261}
262
263fn lower_choice<I>(alternatives: I) -> Result<GrammarExpr, GrammarImportError>
264where
265    I: IntoIterator<Item = Result<GrammarExpr, GrammarImportError>>,
266{
267    let mut lowered = Vec::new();
268    for alternative in alternatives {
269        push_choice_alternative(&mut lowered, alternative?);
270    }
271
272    if lowered.iter().all(|expr| expr == &GrammarExpr::Empty) {
273        return Ok(GrammarExpr::Empty);
274    }
275
276    Ok(match lowered.len() {
277        0 => GrammarExpr::Empty,
278        1 => lowered.remove(0),
279        _ => GrammarExpr::Choice {
280            ordered: false,
281            alternatives: lowered,
282        },
283    })
284}
285
286fn push_choice_alternative(alternatives: &mut Vec<GrammarExpr>, alternative: GrammarExpr) {
287    match alternative {
288        GrammarExpr::Choice {
289            ordered: false,
290            alternatives: nested,
291        } => alternatives.extend(nested),
292        alternative => alternatives.push(alternative),
293    }
294}
295
296fn inject_core_rules(grammar: &mut Grammar) {
297    loop {
298        let unresolved = grammar.undefined_nonterminals();
299        let mut added = false;
300        for name in unresolved {
301            if let Some(rule) = core_rule(&name) {
302                grammar.add_rule(rule);
303                added = true;
304            }
305        }
306        if !added {
307            break;
308        }
309    }
310}
311
312fn core_rule(name: &str) -> Option<GrammarRule> {
313    let canonical_name = name.to_ascii_uppercase();
314    let expr = match canonical_name.as_str() {
315        "ALPHA" => GrammarExpr::char_class(
316            false,
317            [
318                CharClassItem::Range('A', 'Z'),
319                CharClassItem::Range('a', 'z'),
320            ],
321        ),
322        "DIGIT" => GrammarExpr::CharRange('0', '9'),
323        "HEXDIG" => GrammarExpr::char_class(
324            false,
325            [
326                CharClassItem::Range('0', '9'),
327                CharClassItem::Range('A', 'F'),
328                CharClassItem::Range('a', 'f'),
329            ],
330        ),
331        "BIT" => GrammarExpr::CharRange('0', '1'),
332        "CR" => GrammarExpr::Terminal("\r".into()),
333        "LF" => GrammarExpr::Terminal("\n".into()),
334        "CRLF" => crlf_expr(),
335        "SP" => GrammarExpr::Terminal(" ".into()),
336        "HTAB" => GrammarExpr::Terminal("\t".into()),
337        "WSP" => wsp_expr(),
338        "DQUOTE" => GrammarExpr::Terminal("\"".into()),
339        "CHAR" => GrammarExpr::CharRange('\u{01}', '\u{7f}'),
340        "CTL" => GrammarExpr::Choice {
341            ordered: false,
342            alternatives: vec![
343                GrammarExpr::CharRange('\u{00}', '\u{1f}'),
344                GrammarExpr::CharRange('\u{7f}', '\u{7f}'),
345            ],
346        },
347        "OCTET" => GrammarExpr::CharRange('\u{00}', '\u{ff}'),
348        "VCHAR" => GrammarExpr::CharRange('\u{21}', '\u{7e}'),
349        "LWSP" => GrammarExpr::zero_or_more(GrammarExpr::Choice {
350            ordered: false,
351            alternatives: vec![
352                wsp_expr(),
353                GrammarExpr::Sequence(vec![crlf_expr(), wsp_expr()]),
354            ],
355        }),
356        _ => return None,
357    };
358    Some(GrammarRule::new(name, expr))
359}
360
361fn crlf_expr() -> GrammarExpr {
362    GrammarExpr::Sequence(vec![
363        GrammarExpr::Terminal("\r".into()),
364        GrammarExpr::Terminal("\n".into()),
365    ])
366}
367
368fn wsp_expr() -> GrammarExpr {
369    GrammarExpr::char_class(false, [CharClassItem::Char(' '), CharClassItem::Char('\t')])
370}
371
372fn validate_references(grammar: &Grammar) -> Result<(), GrammarImportError> {
373    if let Some(name) = grammar.undefined_nonterminals().into_iter().next() {
374        return Err(parse_error(
375            GrammarFormat::Abnf,
376            format!("undefined non-terminal {name}"),
377        ));
378    }
379    Ok(())
380}
meta_language/grammar/import/abnf.rs

meta_language/grammar/import/
abnf.rs
