meta_language/grammar/interchange/
links.rs

1//! The native links form of a grammar: Links Notation that both runtimes write
2//! byte for byte the same and read back without the source the grammar came
3//! from.
4//!
5//! A `(grammar (format TAG) (start NAME))` link is followed by one
6//! `(rule NAME KIND EXPRESSION)` link per rule in grammar order, with an
7//! optional trailing `(doc TEXT)`. Expressions are nested links headed by the
8//! native listing's words: `empty`, `any`, `(literal TEXT)`,
9//! `(literalInsensitive TEXT)`, `(range FROM TO)`, `(class plain|negated
10//! ITEM...)` with `(char C)` and `(range FROM TO)` items, `(ref NAME)`,
11//! `(choice ordered|unordered ITEM...)`, `(seq ITEM...)`, `(optional ITEM)`,
12//! `(repeat0 ITEM)`, `(repeat1 ITEM)`, `(repeat MIN MAX|unbounded ITEM)`,
13//! `(and ITEM)`, `(not ITEM)` and `(capture labeled LABEL ITEM)` or
14//! `(capture unlabeled ITEM)`. The grammar feature union adds an optional
15//! `(matching MODE)` and `(settling STEP...)` header fields, declaration links before the first rule,
16//! rule fields before the doc and feature expressions (see the
17//! `feature_links` module). The metadata `(kind NAME (source-names (SOURCE
18//! NAME)...))` links after the declarations keep the source names of the
19//! node kinds no rule defines, such as the kind an alias names. Names, texts and characters are percent-encoded
20//! as [`LinkNetwork`](crate::LinkNetwork) `LiNo` terms are (ASCII letters,
21//! digits and `-_.` kept, every other UTF-8 byte as `%XX`, the empty text as
22//! `%`). It mirrors `js/src/grammar-links.js`.
23
24use std::fmt::Write as _;
25
26use links_notation::{LiNo, ParserConfig, parse_lino_to_links_with_config};
27
28use super::super::{
29    CharClassItem, FeatureExpr, Grammar, GrammarDeclarations, GrammarExpr, GrammarFormat,
30    GrammarImportError, GrammarKind, GrammarRule, GrammarSourceName, MATCHING_MODES, RuleKind,
31    settling_problem,
32};
33use super::feature_links::{
34    read_class, read_declaration, read_feature, read_rule_fields, read_source_names,
35    render_declaration_links, render_links_feature, render_rule_fields,
36};
37
38/// The longest repetition bound the links may spell, in decimal digits.
39const MAX_BOUND_DIGITS: usize = 9;
40
41pub(super) type Node = LiNo<String>;
42
43pub(super) fn links_error(detail: impl AsRef<str>) -> GrammarImportError {
44    GrammarImportError::Parse {
45        format: GrammarFormat::MetaLanguage,
46        message: format!("links: {}", detail.as_ref()),
47    }
48}
49
50const fn is_plain(byte: u8) -> bool {
51    byte.is_ascii_alphanumeric() || matches!(byte, b'-' | b'_' | b'.')
52}
53
54/// Percent-encodes `value` as [`LinkNetwork`](crate::LinkNetwork) `LiNo` terms are.
55#[must_use]
56pub fn percent_encode_links_text(value: &str) -> String {
57    if value.is_empty() {
58        return "%".to_owned();
59    }
60    let mut encoded = String::with_capacity(value.len());
61    for &byte in value.as_bytes() {
62        if is_plain(byte) {
63            encoded.push(char::from(byte));
64        } else {
65            write!(encoded, "%{byte:02X}").expect("writing to a String never fails");
66        }
67    }
68    encoded
69}
70
71/// Reverses [`percent_encode_links_text`].
72///
73/// # Errors
74///
75/// Returns a [`GrammarImportError`] for a malformed escape, an unescaped
76/// character or text that is not UTF-8.
77pub fn percent_decode_links_text(value: &str) -> Result<String, GrammarImportError> {
78    if value == "%" {
79        return Ok(String::new());
80    }
81    let bytes = value.as_bytes();
82    let mut decoded = Vec::with_capacity(bytes.len());
83    let mut index = 0;
84    while index < bytes.len() {
85        let byte = bytes[index];
86        if byte == b'%' {
87            let hex = bytes.get(index + 1..index + 3).filter(|hex| {
88                hex.iter()
89                    .all(|digit| digit.is_ascii_digit() || (b'A'..=b'F').contains(digit))
90            });
91            let Some(hex) = hex else {
92                return Err(links_error(format!("invalid percent escape in {value}")));
93            };
94            let text = std::str::from_utf8(hex).expect("hex digits are ASCII");
95            decoded.push(u8::from_str_radix(text, 16).expect("two hex digits fit a byte"));
96            index += 3;
97        } else if is_plain(byte) {
98            decoded.push(byte);
99            index += 1;
100        } else {
101            return Err(links_error(format!("unescaped character in {value}")));
102        }
103    }
104    String::from_utf8(decoded).map_err(|_| links_error(format!("{value} is not UTF-8")))
105}
106
107/// Renders the native links form of `grammar`, one link per line.
108#[must_use]
109pub fn render_grammar_links(grammar: &Grammar) -> String {
110    let mut header = vec!["grammar".to_owned()];
111    if let Some(format) = grammar.source_format() {
112        header.push(format!("(format {})", format.as_str()));
113    }
114    if let Some(start) = grammar.start_rule() {
115        header.push(format!(
116            "(start {})",
117            percent_encode_links_text(start.name())
118        ));
119    }
120    let declarations = grammar.declarations();
121    if let Some(matching) = &declarations.matching {
122        header.push(format!("(matching {matching})"));
123    }
124    if let Some(settling) = &declarations.settling {
125        header.push(format!("(settling {})", settling.join(" ")));
126    }
127    let mut lines = vec![format!("({})", header.join(" "))];
128    lines.extend(render_declaration_links(declarations));
129    lines.extend(grammar.kinds().iter().map(|kind| {
130        link(&[
131            "kind".to_owned(),
132            percent_encode_links_text(&kind.name),
133            render_source_names(&kind.source_names),
134        ])
135    }));
136    lines.extend(grammar.rules().iter().map(render_rule_link));
137    lines.iter().fold(String::new(), |mut text, line| {
138        text.push_str(line);
139        text.push('\n');
140        text
141    })
142}
143
144/// Renders the `(rule NAME KIND EXPRESSION [FIELDS...] [(concept ID)]
145/// [(source-names (SOURCE NAME)...)] [(doc TEXT)])` link of one rule.
146#[must_use]
147pub fn render_rule_link(rule: &GrammarRule) -> String {
148    let mut parts = vec![
149        "rule".to_owned(),
150        percent_encode_links_text(rule.name()),
151        rule.kind().as_str().to_owned(),
152        render_links_expression(rule.expr()),
153    ];
154    parts.extend(render_rule_fields(&rule.attributes));
155    if let Some(concept) = rule.concept() {
156        parts.push(format!("(concept {})", percent_encode_links_text(concept)));
157    }
158    if !rule.source_names().is_empty() {
159        parts.push(render_source_names(rule.source_names()));
160    }
161    if let Some(doc) = rule.doc() {
162        parts.push(format!("(doc {})", percent_encode_links_text(doc)));
163    }
164    link(&parts)
165}
166
167/// Renders `(source-names (SOURCE NAME)...)`.
168fn render_source_names(source_names: &[GrammarSourceName]) -> String {
169    let mut names = vec!["source-names".to_owned()];
170    names.extend(source_names.iter().map(|source_name| {
171        format!(
172            "({} {})",
173            percent_encode_links_text(&source_name.source),
174            percent_encode_links_text(&source_name.name)
175        )
176    }));
177    link(&names)
178}
179
180pub(super) fn link(parts: &[String]) -> String {
181    format!("({})", parts.join(" "))
182}
183
184pub(super) fn char_text(value: char) -> String {
185    percent_encode_links_text(value.encode_utf8(&mut [0; 4]))
186}
187
188/// Renders one expression of the native links form.
189#[must_use]
190pub fn render_links_expression(expr: &GrammarExpr) -> String {
191    let word = |value: &str| value.to_owned();
192    let headed = |head: &str, items: &[GrammarExpr]| {
193        let mut parts = vec![word(head)];
194        parts.extend(items.iter().map(render_links_expression));
195        link(&parts)
196    };
197    let unary =
198        |head: &str, inner: &GrammarExpr| link(&[word(head), render_links_expression(inner)]);
199    match expr {
200        GrammarExpr::Empty => word("empty"),
201        GrammarExpr::AnyChar => word("any"),
202        GrammarExpr::Terminal(value) => link(&[word("literal"), percent_encode_links_text(value)]),
203        GrammarExpr::TerminalInsensitive(value) => {
204            link(&[word("literalInsensitive"), percent_encode_links_text(value)])
205        }
206        GrammarExpr::CharRange(start, end) => {
207            link(&[word("range"), char_text(*start), char_text(*end)])
208        }
209        GrammarExpr::CharClass { negated, items } => {
210            let mut parts = vec![
211                word("class"),
212                word(if *negated { "negated" } else { "plain" }),
213            ];
214            parts.extend(items.iter().map(|item| match item {
215                CharClassItem::Char(value) => link(&[word("char"), char_text(*value)]),
216                CharClassItem::Range(start, end) => {
217                    link(&[word("range"), char_text(*start), char_text(*end)])
218                }
219            }));
220            link(&parts)
221        }
222        GrammarExpr::NonTerminal(name) => link(&[word("ref"), percent_encode_links_text(name)]),
223        GrammarExpr::Choice {
224            ordered,
225            alternatives,
226        } => {
227            let mut parts = vec![
228                word("choice"),
229                word(if *ordered { "ordered" } else { "unordered" }),
230            ];
231            parts.extend(alternatives.iter().map(render_links_expression));
232            link(&parts)
233        }
234        GrammarExpr::Sequence(items) => headed("seq", items),
235        GrammarExpr::Optional(inner) => unary("optional", inner),
236        GrammarExpr::ZeroOrMore(inner) => unary("repeat0", inner),
237        GrammarExpr::OneOrMore(inner) => unary("repeat1", inner),
238        GrammarExpr::And(inner) => unary("and", inner),
239        GrammarExpr::Not(inner) => unary("not", inner),
240        GrammarExpr::Repeat { expr, min, max } => link(&[
241            word("repeat"),
242            min.to_string(),
243            max.map_or_else(|| word("unbounded"), |max| max.to_string()),
244            render_links_expression(expr),
245        ]),
246        GrammarExpr::Capture { label, expr } => label.as_ref().map_or_else(
247            || {
248                link(&[
249                    word("capture"),
250                    word("unlabeled"),
251                    render_links_expression(expr),
252                ])
253            },
254            |label| {
255                link(&[
256                    word("capture"),
257                    word("labeled"),
258                    percent_encode_links_text(label),
259                    render_links_expression(expr),
260                ])
261            },
262        ),
263        GrammarExpr::Feature(feature) => render_links_feature(feature),
264    }
265}
266
267/// A word: a bare reference, or an identified link without values.
268fn as_word(node: &Node) -> Option<&str> {
269    match node {
270        LiNo::Ref(word) => Some(word),
271        LiNo::Link {
272            id: Some(word),
273            values,
274        } if values.is_empty() => Some(word),
275        LiNo::Link { .. } => None,
276    }
277}
278
279/// A parsed value as a head and its arguments: a word is a head without
280/// arguments.
281pub(super) fn parts(node: &Node) -> Result<(&str, &[Node]), GrammarImportError> {
282    if let Some(word) = as_word(node) {
283        return Ok((word, &[]));
284    }
285    match node {
286        LiNo::Link { id: None, values } => match values.split_first() {
287            None => Err(links_error("empty link")),
288            Some((head, rest)) => as_word(head)
289                .map(|head| (head, rest))
290                .ok_or_else(|| links_error("a link must start with a word")),
291        },
292        LiNo::Link { id: Some(id), .. } => {
293            Err(links_error(format!("unexpected identified link {id}")))
294        }
295        LiNo::Ref(_) => unreachable!("a reference is a word"),
296    }
297}
298
299pub(super) fn word<'a>(node: Option<&'a Node>, what: &str) -> Result<&'a str, GrammarImportError> {
300    node.and_then(as_word)
301        .ok_or_else(|| links_error(format!("expected {what}")))
302}
303
304pub(super) fn decoded_word(node: Option<&Node>, what: &str) -> Result<String, GrammarImportError> {
305    percent_decode_links_text(word(node, what)?)
306}
307
308pub(super) fn character(node: Option<&Node>, what: &str) -> Result<char, GrammarImportError> {
309    let decoded = decoded_word(node, what)?;
310    let mut chars = decoded.chars();
311    match (chars.next(), chars.next()) {
312        (Some(value), None) => Ok(value),
313        _ => Err(links_error(format!("{what} must be one code point"))),
314    }
315}
316
317pub(super) fn arity(head: &str, args: &[Node], count: usize) -> Result<(), GrammarImportError> {
318    if args.len() == count {
319        Ok(())
320    } else {
321        Err(links_error(format!(
322            "{head} takes {count} value(s), not {}",
323            args.len()
324        )))
325    }
326}
327
328fn bound(node: &Node, allow_unbounded: bool) -> Result<Option<usize>, GrammarImportError> {
329    let text = word(Some(node), "a repetition bound")?;
330    if allow_unbounded && text == "unbounded" {
331        return Ok(None);
332    }
333    if text.is_empty() || !text.bytes().all(|byte| byte.is_ascii_digit()) {
334        return Err(links_error(format!("invalid repetition bound {text}")));
335    }
336    if text.len() > MAX_BOUND_DIGITS {
337        return Err(links_error(format!("repetition bound {text} is too large")));
338    }
339    Ok(Some(text.parse().expect("nine decimal digits fit usize")))
340}
341
342fn flag(node: &Node, yes: &str, no: &str) -> Result<bool, GrammarImportError> {
343    let text = word(Some(node), &format!("{yes} or {no}"))?;
344    if text != yes && text != no {
345        return Err(links_error(format!("expected {yes} or {no}, not {text}")));
346    }
347    Ok(text == yes)
348}
349
350fn inner(head: &str, args: &[Node]) -> Result<Box<GrammarExpr>, GrammarImportError> {
351    arity(head, args, 1)?;
352    Ok(Box::new(parse_node(&args[0])?))
353}
354
355pub(super) fn parse_node(node: &Node) -> Result<GrammarExpr, GrammarImportError> {
356    let (head, args) = parts(node)?;
357    Ok(match head {
358        "empty" | "any" => {
359            arity(head, args, 0)?;
360            if head == "empty" {
361                GrammarExpr::Empty
362            } else {
363                GrammarExpr::AnyChar
364            }
365        }
366        "literal" => {
367            arity(head, args, 1)?;
368            GrammarExpr::Terminal(decoded_word(args.first(), "a text")?)
369        }
370        "literalInsensitive" => {
371            arity(head, args, 1)?;
372            GrammarExpr::TerminalInsensitive(decoded_word(args.first(), "a text")?)
373        }
374        "range" => {
375            arity(head, args, 2)?;
376            GrammarExpr::CharRange(
377                character(args.first(), "a range start")?,
378                character(args.get(1), "a range end")?,
379            )
380        }
381        "class" => {
382            let Some((first, items)) = args.split_first() else {
383                return Err(links_error("class needs plain or negated"));
384            };
385            read_class(flag(first, "negated", "plain")?, items)?
386        }
387        "ref" => {
388            let Some((name, arguments)) = args.split_first() else {
389                return Err(links_error("ref takes a rule name"));
390            };
391            let name = decoded_word(Some(name), "a rule name")?;
392            if arguments.is_empty() {
393                GrammarExpr::NonTerminal(name)
394            } else {
395                GrammarExpr::feature(FeatureExpr::Call {
396                    name,
397                    arguments: arguments.iter().map(parse_node).collect::<Result<_, _>>()?,
398                })
399            }
400        }
401        "choice" => {
402            let Some((first, items)) = args.split_first() else {
403                return Err(links_error("choice needs ordered or unordered"));
404            };
405            let ordered = flag(first, "ordered", "unordered")?;
406            GrammarExpr::Choice {
407                ordered,
408                alternatives: items.iter().map(parse_node).collect::<Result<_, _>>()?,
409            }
410        }
411        "seq" => GrammarExpr::Sequence(args.iter().map(parse_node).collect::<Result<_, _>>()?),
412        "repeat" => {
413            arity(head, args, 3)?;
414            let min = bound(&args[0], false)?.expect("a lower bound is never unbounded");
415            let max = bound(&args[1], true)?;
416            if max.is_some_and(|max| max < min) {
417                return Err(links_error(format!(
418                    "repetition bounds {min}, {} are reversed",
419                    max.unwrap_or_default()
420                )));
421            }
422            GrammarExpr::Repeat {
423                expr: Box::new(parse_node(&args[2])?),
424                min,
425                max,
426            }
427        }
428        "capture" => {
429            let Some(first) = args.first() else {
430                return Err(links_error("capture needs labeled or unlabeled"));
431            };
432            if flag(first, "labeled", "unlabeled")? {
433                arity(head, args, 3)?;
434                GrammarExpr::Capture {
435                    label: Some(decoded_word(args.get(1), "a capture label")?),
436                    expr: Box::new(parse_node(&args[2])?),
437                }
438            } else {
439                arity(head, args, 2)?;
440                GrammarExpr::Capture {
441                    label: None,
442                    expr: Box::new(parse_node(&args[1])?),
443                }
444            }
445        }
446        "optional" => GrammarExpr::Optional(inner(head, args)?),
447        "repeat0" => GrammarExpr::ZeroOrMore(inner(head, args)?),
448        "repeat1" => GrammarExpr::OneOrMore(inner(head, args)?),
449        "and" => GrammarExpr::And(inner(head, args)?),
450        "not" => GrammarExpr::Not(inner(head, args)?),
451        other => {
452            return read_feature(other, args)?
453                .ok_or_else(|| links_error(format!("unknown expression {other}")));
454        }
455    })
456}
457
458/// Reads one expression of the native links form.
459///
460/// # Errors
461///
462/// Returns a [`GrammarImportError`] of the meta-language format when the text
463/// is not one well-formed expression link.
464pub fn parse_links_expression(source: &str) -> Result<GrammarExpr, GrammarImportError> {
465    let statements = parse_statements(source)?;
466    match statements.as_slice() {
467        [node] => parse_node(node),
468        _ => Err(links_error("expected one expression")),
469    }
470}
471
472fn parse_statements(source: &str) -> Result<Vec<Node>, GrammarImportError> {
473    parse_lino_to_links_with_config(source, &ParserConfig::without_comments())
474        .map_err(|error| links_error(error.to_string()))
475}
476
477/// Reads the native links form written by [`render_grammar_links`].
478///
479/// # Errors
480///
481/// Returns a [`GrammarImportError`] of the meta-language format when the links
482/// are malformed, define a rule twice or no rule, or name an undefined start
483/// rule.
484pub fn parse_grammar_links(source: &str) -> Result<Grammar, GrammarImportError> {
485    let statements = parse_statements(source)?;
486    let Some((header, statements)) = statements.split_first() else {
487        return Err(links_error("the links define no grammar"));
488    };
489    let (header_head, header_args) = parts(header)?;
490    if header_head != "grammar" {
491        return Err(links_error("the first link must be the grammar link"));
492    }
493    let mut source_format = None;
494    let mut start = None;
495    let mut declarations = GrammarDeclarations::default();
496    for field in header_args {
497        let (key, values) = parts(field)?;
498        if key == "settling" && declarations.settling.is_none() {
499            let steps = values
500                .iter()
501                .map(|value| word(Some(value), "a settling step").map(str::to_owned))
502                .collect::<Result<Vec<_>, _>>()?;
503            if let Some(problem) = settling_problem(&steps) {
504                return Err(links_error(problem));
505            }
506            declarations.settling = Some(steps);
507            continue;
508        }
509        arity(key, values, 1)?;
510        if key == "format" && source_format.is_none() {
511            let tag = word(values.first(), "a format")?;
512            source_format = Some(
513                GrammarFormat::from_tag(tag)
514                    .ok_or_else(|| links_error(format!("unknown source format {tag}")))?,
515            );
516        } else if key == "start" && start.is_none() {
517            start = Some(decoded_word(values.first(), "a start rule")?);
518        } else if key == "matching" && declarations.matching.is_none() {
519            let matching = word(values.first(), "a matching")?;
520            if !MATCHING_MODES.contains(&matching) {
521                return Err(links_error(format!("unknown matching {matching}")));
522            }
523            declarations.matching = Some(matching.to_owned());
524        } else {
525            return Err(links_error(format!("unexpected grammar field {key}")));
526        }
527    }
528    let mut rules: Vec<GrammarRule> = Vec::new();
529    let mut kinds: Vec<GrammarKind> = Vec::new();
530    for statement in statements {
531        let (head, args) = parts(statement)?;
532        if head == "kind" && rules.is_empty() {
533            arity(head, args, 2)?;
534            let name = decoded_word(args.first(), "a kind name")?;
535            if kinds.iter().any(|kind| kind.name == name) {
536                return Err(links_error(format!("kind {name} is given twice")));
537            }
538            let (field, names) = parts(&args[1])?;
539            if field != "source-names" {
540                return Err(links_error(format!(
541                    "expected (source-names ...), not {field}"
542                )));
543            }
544            let source_names = read_source_names(names)?;
545            kinds.push(GrammarKind { name, source_names });
546            continue;
547        }
548        if head != "rule" {
549            if !rules.is_empty() || !read_declaration(head, args, &mut declarations)? {
550                return Err(links_error(format!("unexpected link {head}")));
551            }
552            continue;
553        }
554        if args.len() < 3 {
555            return Err(links_error(
556                "rule takes a name, a kind, an expression and optional fields",
557            ));
558        }
559        let name = decoded_word(args.first(), "a rule name")?;
560        let kind = word(args.get(1), "a rule kind")?;
561        let kind = RuleKind::from_tag(kind)
562            .ok_or_else(|| links_error(format!("unknown rule kind {kind}")))?;
563        if rules.iter().any(|rule| rule.name == name) {
564            return Err(links_error(format!("rule {name} is defined twice")));
565        }
566        let expr = parse_node(&args[2])?;
567        let fields = read_rule_fields(&args[3..])?;
568        let mut rule = GrammarRule::new(name, expr)
569            .with_kind(kind)
570            .with_attributes(fields.attributes)
571            .with_source_names(fields.source_names);
572        if let Some(concept) = fields.concept {
573            rule = rule.with_concept(concept);
574        }
575        if let Some(doc) = fields.doc {
576            rule = rule.with_doc(doc);
577        }
578        rules.push(rule);
579    }
580    let Some(first) = rules.first().map(|rule| rule.name.clone()) else {
581        return Err(links_error("the links define no rules"));
582    };
583    if let Some(start) = &start
584        && !rules.iter().any(|rule| &rule.name == start)
585    {
586        return Err(links_error(format!("start rule {start} is not defined")));
587    }
588    let mut grammar = Grammar::new();
589    for rule in rules {
590        grammar.add_rule(rule);
591    }
592    grammar.set_start(start.unwrap_or(first));
593    if let Some(format) = source_format {
594        grammar.set_source_format(format);
595    }
596    grammar.set_declarations(declarations);
597    grammar.set_kinds(kinds);
598    Ok(grammar)
599}
meta_language/grammar/interchange/links.rs

meta_language/grammar/interchange/
links.rs
