metrale_grammar/grammar/functor/
structure_normalizer.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// StructureNormalizer — port of `StructureNormalizerImpl` from
4// `cpp/grammar_functor.cc`.
5//
6// Normalizes the structure of a grammar so every rule body is a
7// choices-of-sequences-of-elements (or a TagDispatch). New rules are
8// created where nesting must be flattened.
9
10use super::mutator::{MutatorState, OwnedExpr, rebuild_tag_dispatch};
11use super::normalizer::SingleElementExprEliminator;
12use crate::grammar::data::GrammarData;
13use crate::grammar::expr::GrammarExprType;
14
15/// Structure-normalization pass.
16#[derive(Default)]
17pub struct StructureNormalizer {
18    state: Option<MutatorState>,
19}
20
21impl StructureNormalizer {
22    /// Run the pass: first `SingleElementExprEliminator`, then normalize.
23    pub fn apply(grammar: GrammarData) -> GrammarData {
24        let grammar = SingleElementExprEliminator::apply(grammar);
25        let mut p = Self::default();
26        *p.st() = MutatorState::new(grammar);
27        let num_rules = p.st().base.num_rules();
28        for i in 0..num_rules {
29            let name = p.st().base.rule(i).name.clone();
30            p.st().builder.add_empty_rule(name).expect("dup rule");
31        }
32        for i in 0..num_rules {
33            let rule = p.st().base.rule(i).clone();
34            p.st().cur_rule_name = rule.name.clone();
35            let body = p.st().base.owned_expr(rule.body_expr_id);
36            let new_body = p.visit_rule_body(&body);
37            p.st().builder.update_rule_body(i, new_body).expect("range");
38            let la = p.visit_lookahead(rule.lookahead_assertion_id);
39            p.st()
40                .builder
41                .update_lookahead_assertion(i, la)
42                .expect("range");
43        }
44        let root_name = p.st().base.root_rule().name.clone();
45        let builder = std::mem::take(&mut p.st().builder);
46        builder.get(&root_name).expect("root")
47    }
48
49    fn st(&mut self) -> &mut MutatorState {
50        self.state
51            .get_or_insert_with(|| MutatorState::new(GrammarData::new()))
52    }
53
54    fn visit_lookahead(&mut self, id: i32) -> i32 {
55        if id == -1 {
56            return -1;
57        }
58        let e = self.st().base.owned_expr(id);
59        match e.kind {
60            GrammarExprType::Sequence => {
61                let ids = self.visit_sequence_(&e);
62                self.st().builder.add_sequence(&ids)
63            }
64            GrammarExprType::Choices => panic!("Choices in lookahead assertion not supported"),
65            GrammarExprType::EmptyStr => panic!("Empty string in lookahead assertion"),
66            GrammarExprType::TagDispatch => panic!("TagDispatch in lookahead assertion"),
67            _ => {
68                let elem = self.st().builder.add_grammar_expr(e.kind, &e.data);
69                self.st().builder.add_sequence(&[elem])
70            }
71        }
72    }
73
74    fn visit_rule_body(&mut self, e: &OwnedExpr) -> i32 {
75        match e.kind {
76            GrammarExprType::Sequence => {
77                let seq = self.visit_sequence_(e);
78                let s = self.st().builder.add_sequence(&seq);
79                self.st().builder.add_choices(&[s])
80            }
81            GrammarExprType::Choices => {
82                let ids = self.visit_choices_(e);
83                self.st().builder.add_choices(&ids)
84            }
85            GrammarExprType::EmptyStr => {
86                let empty = self.st().builder.add_empty_str();
87                self.st().builder.add_choices(&[empty])
88            }
89            GrammarExprType::TagDispatch => {
90                let td = e.tag_dispatch.clone().expect("td");
91                rebuild_tag_dispatch(&mut self.st().builder, &td)
92            }
93            _ => {
94                let elem = self.st().builder.add_grammar_expr(e.kind, &e.data);
95                let seq = self.st().builder.add_sequence(&[elem]);
96                self.st().builder.add_choices(&[seq])
97            }
98        }
99    }
100
101    /// Returns a list of new choice expr ids.
102    fn visit_choices_(&mut self, e: &OwnedExpr) -> Vec<i32> {
103        let mut new_choice_ids: Vec<i32> = Vec::new();
104        let mut found_empty = false;
105        for &i in &e.data {
106            let choice = self.st().base.owned_expr(i);
107            match choice.kind {
108                GrammarExprType::Sequence => {
109                    let sub = self.visit_sequence_(&choice);
110                    if sub.is_empty() {
111                        found_empty = true;
112                    } else {
113                        let s = self.st().builder.add_sequence(&sub);
114                        new_choice_ids.push(s);
115                    }
116                }
117                GrammarExprType::Choices => {
118                    let sub = self.visit_choices_(&choice);
119                    let contains_empty = self.st().builder.get_grammar_expr(sub[0]).kind
120                        == GrammarExprType::EmptyStr;
121                    if contains_empty {
122                        found_empty = true;
123                        new_choice_ids.extend_from_slice(&sub[1..]);
124                    } else {
125                        new_choice_ids.extend_from_slice(&sub);
126                    }
127                }
128                GrammarExprType::EmptyStr => found_empty = true,
129                GrammarExprType::TagDispatch => {
130                    let td = choice.tag_dispatch.clone().expect("td");
131                    let td_id = rebuild_tag_dispatch(&mut self.st().builder, &td);
132                    let hint = self.st().cur_rule_name.clone();
133                    let new_rule = self
134                        .st()
135                        .builder
136                        .add_rule_with_hint(&hint, td_id)
137                        .expect("hint");
138                    let rr = self.st().builder.add_rule_ref(new_rule);
139                    let s = self.st().builder.add_sequence(&[rr]);
140                    new_choice_ids.push(s);
141                }
142                _ => {
143                    let sub = self
144                        .st()
145                        .builder
146                        .add_grammar_expr(choice.kind, &choice.data);
147                    let s = self.st().builder.add_sequence(&[sub]);
148                    new_choice_ids.push(s);
149                }
150            }
151        }
152        if found_empty {
153            let empty = self.st().builder.add_empty_str();
154            new_choice_ids.insert(0, empty);
155        }
156        assert!(!new_choice_ids.is_empty());
157        new_choice_ids
158    }
159
160    /// Returns a list of new sequence element expr ids (flattened).
161    fn visit_sequence_(&mut self, e: &OwnedExpr) -> Vec<i32> {
162        let mut new_seq: Vec<i32> = Vec::new();
163        for &i in &e.data {
164            let elem = self.st().base.owned_expr(i);
165            match elem.kind {
166                GrammarExprType::Sequence => {
167                    let sub = self.visit_sequence_(&elem);
168                    new_seq.extend_from_slice(&sub);
169                }
170                GrammarExprType::Choices => {
171                    let sub = self.visit_choices_(&elem);
172                    if sub.len() == 1 {
173                        let ce = self.st().builder.get_grammar_expr(sub[0]);
174                        if ce.kind != GrammarExprType::EmptyStr {
175                            let data: Vec<i32> = ce.data.to_vec();
176                            new_seq.extend_from_slice(&data);
177                        }
178                    } else {
179                        let c = self.st().builder.add_choices(&sub);
180                        let hint = self.st().cur_rule_name.clone();
181                        let nr = self
182                            .st()
183                            .builder
184                            .add_rule_with_hint(&hint, c)
185                            .expect("hint");
186                        new_seq.push(self.st().builder.add_rule_ref(nr));
187                    }
188                }
189                GrammarExprType::EmptyStr => {}
190                GrammarExprType::TagDispatch => {
191                    let td = elem.tag_dispatch.clone().expect("td");
192                    let td_id = rebuild_tag_dispatch(&mut self.st().builder, &td);
193                    let hint = self.st().cur_rule_name.clone();
194                    let nr = self
195                        .st()
196                        .builder
197                        .add_rule_with_hint(&hint, td_id)
198                        .expect("hint");
199                    new_seq.push(self.st().builder.add_rule_ref(nr));
200                }
201                _ => {
202                    let s = self.st().builder.add_grammar_expr(elem.kind, &elem.data);
203                    new_seq.push(s);
204                }
205            }
206        }
207        new_seq
208    }
209}
210
211#[cfg(test)]
212mod tests {
213    use super::*;
214    use crate::grammar::parse_ebnf_default;
215    use crate::grammar::printer::print_grammar;
216
217    #[test]
218    fn body_becomes_choices_of_sequences() {
219        let g = parse_ebnf_default("root ::= \"a\" \"b\"\n").unwrap();
220        let n = StructureNormalizer::apply(g);
221        let out = print_grammar(&n);
222        // sequence wrapped in choices: "((\"ab\")...)" or "((\"a\" \"b\")...)"
223        assert!(out.starts_with("root ::= ("), "{out}");
224    }
225
226    #[test]
227    fn nested_choices_flattened() {
228        let g = parse_ebnf_default("root ::= \"a\" | (\"b\" | \"c\")\n").unwrap();
229        let n = StructureNormalizer::apply(g);
230        let out = print_grammar(&n);
231        assert!(out.contains(" | "), "{out}");
232    }
233
234    #[test]
235    fn inner_alternation_makes_new_rule() {
236        let g = parse_ebnf_default("root ::= \"a\" (\"b\" | \"c\")\n").unwrap();
237        let n = StructureNormalizer::apply(g);
238        assert!(n.num_rules() >= 2);
239    }
240
241    #[test]
242    fn empty_str_body() {
243        let g = parse_ebnf_default("root ::= \"\"\n").unwrap();
244        let n = StructureNormalizer::apply(g);
245        assert!(print_grammar(&n).contains("\"\""));
246    }
247}
metrale_grammar/grammar/functor/structure_normalizer.rs

metrale_grammar/grammar/functor/
structure_normalizer.rs
