metrale_grammar/grammar/functor/
constructor.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Grammar constructors — port of `SubGrammarAdderImpl`,
4// `GrammarUnionFunctorImpl` and `GrammarConcatFunctorImpl` from
5// `cpp/grammar_functor.cc`.
6//
7// These build a new grammar out of one or more existing grammars
8// (sub-grammar splicing, union, concatenation).
9
10use crate::grammar::builder::{GrammarBuilder, TagDispatchSpec};
11use crate::grammar::data::GrammarData;
12use crate::grammar::expr::GrammarExprType;
13
14/// Splice every rule of `sub_grammar` into `builder`, returning the new
15/// rule id of `sub_grammar`'s root rule. Rule references, repeats and
16/// tag dispatches are remapped to the freshly-allocated rule ids.
17pub fn add_sub_grammar(builder: &mut GrammarBuilder, sub_grammar: &GrammarData) -> i32 {
18    let num_rules = sub_grammar.num_rules();
19    let mut new_ids: Vec<i32> = Vec::with_capacity(num_rules as usize);
20    for i in 0..num_rules {
21        let hint = builder.get_new_rule_name(&sub_grammar.rule(i).name);
22        new_ids.push(builder.add_empty_rule(hint).expect("unique name"));
23    }
24    for i in 0..num_rules {
25        let rule = sub_grammar.rule(i);
26        let new_body = copy_expr(builder, sub_grammar, rule.body_expr_id, &new_ids);
27        builder
28            .update_rule_body(new_ids[i as usize], new_body)
29            .expect("range");
30        let new_la = if rule.lookahead_assertion_id == -1 {
31            -1
32        } else {
33            copy_expr(builder, sub_grammar, rule.lookahead_assertion_id, &new_ids)
34        };
35        builder
36            .update_lookahead_assertion(new_ids[i as usize], new_la)
37            .expect("range");
38    }
39    new_ids[sub_grammar.root_rule_id() as usize]
40}
41
42/// Recursively copy expr `expr_id` from `src` into `builder`, remapping
43/// rule ids through `id_map`.
44fn copy_expr(builder: &mut GrammarBuilder, src: &GrammarData, expr_id: i32, id_map: &[i32]) -> i32 {
45    let e = src.expr(expr_id);
46    match e.kind {
47        GrammarExprType::RuleRef => builder.add_rule_ref(id_map[e.data[0] as usize]),
48        GrammarExprType::Repeat => {
49            builder.add_repeat(id_map[e.data[0] as usize], e.data[1], e.data[2])
50        }
51        GrammarExprType::TagDispatch => {
52            let td = src.tag_dispatch(expr_id);
53            let spec = TagDispatchSpec {
54                tag_rule_pairs: td
55                    .tag_rule_pairs
56                    .iter()
57                    .map(|(t, r)| (t.clone(), id_map[*r as usize]))
58                    .collect(),
59                stop_eos: td.stop_eos,
60                stop_str: td.stop_str,
61                loop_after_dispatch: td.loop_after_dispatch,
62                excluded_str: td.excluded_str,
63            };
64            builder.add_tag_dispatch(&spec)
65        }
66        GrammarExprType::Sequence => {
67            let ids: Vec<i32> = e
68                .data
69                .iter()
70                .map(|&c| copy_expr(builder, src, c, id_map))
71                .collect();
72            builder.add_sequence(&ids)
73        }
74        GrammarExprType::Choices => {
75            let ids: Vec<i32> = e
76                .data
77                .iter()
78                .map(|&c| copy_expr(builder, src, c, id_map))
79                .collect();
80            builder.add_choices(&ids)
81        }
82        _ => builder.add_grammar_expr(e.kind, e.data),
83    }
84}
85
86/// Build a grammar accepting any string from any of `grammars`.
87pub struct GrammarUnion;
88
89impl GrammarUnion {
90    /// Run the union construction.
91    pub fn apply(grammars: &[GrammarData]) -> GrammarData {
92        let mut builder = GrammarBuilder::new();
93        let root_id = builder.add_empty_rule("root").expect("root");
94        let mut choices: Vec<i32> = Vec::with_capacity(grammars.len());
95        for g in grammars {
96            let sub_root = add_sub_grammar(&mut builder, g);
97            let rr = builder.add_rule_ref(sub_root);
98            let seq = builder.add_sequence(&[rr]);
99            choices.push(seq);
100        }
101        let body = builder.add_choices(&choices);
102        builder.update_rule_body(root_id, body).expect("root range");
103        builder.get_by_id(root_id).expect("root")
104    }
105}
106
107/// Build a grammar accepting the concatenation of `grammars` in order.
108pub struct GrammarConcat;
109
110impl GrammarConcat {
111    /// Run the concatenation construction.
112    pub fn apply(grammars: &[GrammarData]) -> GrammarData {
113        let mut builder = GrammarBuilder::new();
114        let root_id = builder.add_empty_rule("root").expect("root");
115        let mut seq: Vec<i32> = Vec::with_capacity(grammars.len());
116        for g in grammars {
117            let sub_root = add_sub_grammar(&mut builder, g);
118            seq.push(builder.add_rule_ref(sub_root));
119        }
120        let seq_id = builder.add_sequence(&seq);
121        let body = builder.add_choices(&[seq_id]);
122        builder.update_rule_body(root_id, body).expect("root range");
123        builder.get_by_id(root_id).expect("root")
124    }
125}
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130    use crate::grammar::functor::normalizer::GrammarNormalizer;
131    use crate::grammar::parse_ebnf_default;
132
133    fn g(ebnf: &str) -> GrammarData {
134        GrammarNormalizer::apply(parse_ebnf_default(ebnf).expect("parse"))
135    }
136
137    #[test]
138    fn union_of_two_grammars() {
139        let a = g("root ::= \"a\"\n");
140        let b = g("root ::= \"b\"\n");
141        let u = GrammarUnion::apply(&[a, b]);
142        assert_eq!(u.root_rule().name, "root");
143        assert!(u.num_rules() >= 3);
144    }
145
146    #[test]
147    fn concat_of_two_grammars() {
148        let a = g("root ::= \"a\"\n");
149        let b = g("root ::= \"b\"\n");
150        let c = GrammarConcat::apply(&[a, b]);
151        assert_eq!(c.root_rule().name, "root");
152        assert!(c.num_rules() >= 3);
153    }
154
155    #[test]
156    fn sub_grammar_adder_remaps_refs() {
157        let mut builder = GrammarBuilder::new();
158        let sub = g("root ::= inner\ninner ::= \"x\"\n");
159        let root = add_sub_grammar(&mut builder, &sub);
160        let result = builder.get_by_id(root).expect("get");
161        assert_eq!(result.num_rules(), 2);
162    }
163
164    #[test]
165    fn union_single_grammar() {
166        let a = g("root ::= \"only\"\n");
167        let u = GrammarUnion::apply(std::slice::from_ref(&a));
168        assert_eq!(u.root_rule().name, "root");
169    }
170}
metrale_grammar/grammar/functor/constructor.rs

metrale_grammar/grammar/functor/
constructor.rs
