metrale_grammar/grammar/functor/
optimizer.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Grammar optimization passes — port of `cpp/grammar_functor.cc`:
4//   ByteStringFuser, RuleInliner, DeadCodeEliminator.
5//
6// `RepetitionNormalizer` + `GrammarOptimizer` live in
7// `optimizer_pipeline.rs` (250-line cap).
8
9use std::collections::HashMap;
10
11use super::analyzer::UsedRulesAnalyzer;
12use super::mutator::{GrammarMutator, MutatorState, OwnedExpr, rebuild_tag_dispatch};
13use crate::grammar::data::GrammarData;
14use crate::grammar::expr::GrammarExprType;
15
16/// Fuse adjacent byte-string elements inside sequences.
17/// `("ab" "cd") -> ("abcd")`.
18#[derive(Default)]
19pub struct ByteStringFuser {
20    state: Option<MutatorState>,
21}
22
23impl ByteStringFuser {
24    /// Run the pass.
25    pub fn apply(grammar: GrammarData) -> GrammarData {
26        let mut p = Self::default();
27        GrammarMutator::apply(&mut p, grammar)
28    }
29}
30
31impl GrammarMutator for ByteStringFuser {
32    fn state(&mut self) -> &mut MutatorState {
33        self.state
34            .get_or_insert_with(|| MutatorState::new(GrammarData::new()))
35    }
36
37    fn visit_sequence(&mut self, e: &OwnedExpr) -> i32 {
38        let mut new_seq: Vec<i32> = Vec::new();
39        let mut cur_bytes: Vec<i32> = Vec::new();
40        for &i in &e.data {
41            let elem = self.state().base.owned_expr(i);
42            if elem.kind == GrammarExprType::ByteString {
43                cur_bytes.extend_from_slice(&elem.data);
44            } else {
45                if !cur_bytes.is_empty() {
46                    let bs = self.state().builder.add_byte_string_bytes(&cur_bytes);
47                    new_seq.push(bs);
48                    cur_bytes.clear();
49                }
50                let s = self.state().builder.add_grammar_expr(elem.kind, &elem.data);
51                new_seq.push(s);
52            }
53        }
54        if !cur_bytes.is_empty() {
55            let bs = self.state().builder.add_byte_string_bytes(&cur_bytes);
56            new_seq.push(bs);
57        }
58        self.state().builder.add_sequence(&new_seq)
59    }
60}
61
62/// Inline rule references that start a sequence, when the referenced
63/// rule is a non-empty choices-of-sequences with no rule references.
64#[derive(Default)]
65pub struct RuleInliner {
66    state: Option<MutatorState>,
67    can_inline: HashMap<i32, bool>,
68}
69
70impl RuleInliner {
71    /// Run the pass.
72    pub fn apply(grammar: GrammarData) -> GrammarData {
73        let mut p = Self::default();
74        GrammarMutator::apply(&mut p, grammar)
75    }
76
77    fn check_can_inline(&self, rule_id: i32) -> bool {
78        let base = &self.state_ref().base;
79        let rule = base.rule(rule_id);
80        let body = base.expr(rule.body_expr_id);
81        if body.kind != GrammarExprType::Choices || body.is_empty() {
82            return false;
83        }
84        for &cid in body.data {
85            let choice = base.expr(cid);
86            if choice.kind == GrammarExprType::EmptyStr {
87                return false;
88            }
89            assert_eq!(choice.kind, GrammarExprType::Sequence);
90            for &eid in choice.data {
91                if base.expr(eid).kind == GrammarExprType::RuleRef {
92                    return false;
93                }
94            }
95        }
96        true
97    }
98
99    fn state_ref(&self) -> &MutatorState {
100        self.state.as_ref().expect("state initialized")
101    }
102}
103
104impl GrammarMutator for RuleInliner {
105    fn state(&mut self) -> &mut MutatorState {
106        self.state
107            .get_or_insert_with(|| MutatorState::new(GrammarData::new()))
108    }
109
110    fn visit_choices(&mut self, e: &OwnedExpr) -> i32 {
111        let mut new_choice_ids: Vec<i32> = Vec::new();
112        for &cid in &e.data {
113            let choice = self.state().base.owned_expr(cid);
114            if choice.kind == GrammarExprType::EmptyStr {
115                new_choice_ids.push(self.visit_expr_id(cid));
116                continue;
117            }
118            assert_eq!(choice.kind, GrammarExprType::Sequence);
119            let first = self.state().base.owned_expr(choice.data[0]);
120            if first.kind != GrammarExprType::RuleRef {
121                new_choice_ids.push(self.visit_expr(&choice));
122                continue;
123            }
124            let rule_ref_id = first.data[0];
125            if !self.can_inline.contains_key(&rule_ref_id) {
126                let v = self.check_can_inline(rule_ref_id);
127                self.can_inline.insert(rule_ref_id, v);
128            }
129            if !self.can_inline[&rule_ref_id] {
130                new_choice_ids.push(self.visit_expr(&choice));
131                continue;
132            }
133
134            // Inline: visit the trailing elements of this choice...
135            let other: Vec<i32> = choice.data[1..]
136                .iter()
137                .map(|&x| self.visit_expr_id(x))
138                .collect();
139            // ...and splice each choice of the referenced rule before them.
140            let ref_body_id = self.state().base.rule(rule_ref_id).body_expr_id;
141            let ref_choices: Vec<i32> = self.state().base.expr(ref_body_id).data.to_vec();
142            for ref_cid in ref_choices {
143                let ref_choice = self.state().base.owned_expr(ref_cid);
144                assert_eq!(ref_choice.kind, GrammarExprType::Sequence);
145                let mut to_add: Vec<i32> = ref_choice
146                    .data
147                    .iter()
148                    .map(|&x| self.visit_expr_id(x))
149                    .collect();
150                to_add.extend_from_slice(&other);
151                let s = self.state().builder.add_sequence(&to_add);
152                new_choice_ids.push(s);
153            }
154        }
155        self.state().builder.add_choices(&new_choice_ids)
156    }
157}
158
159/// Eliminate rules not reachable from the root.
160#[derive(Default)]
161pub struct DeadCodeEliminator {
162    state: Option<MutatorState>,
163    rule_id_map: HashMap<i32, i32>,
164}
165
166impl DeadCodeEliminator {
167    /// Run the pass.
168    pub fn apply(grammar: GrammarData) -> GrammarData {
169        let mut p = Self::default();
170        *p.st() = MutatorState::new(grammar);
171        let used = UsedRulesAnalyzer::apply(&p.st().base);
172        for &rule_id in &used {
173            let name = p.st().base.rule(rule_id).name.clone();
174            let new_id = p.st().builder.add_empty_rule(name).expect("dup");
175            p.rule_id_map.insert(rule_id, new_id);
176        }
177        for &rule_id in &used {
178            let rule = p.st().base.rule(rule_id).clone();
179            let new_id = p.rule_id_map[&rule_id];
180            let new_body = p.visit_expr_id(rule.body_expr_id);
181            p.st()
182                .builder
183                .update_rule_body(new_id, new_body)
184                .expect("range");
185            let new_la = p.visit_lookahead(rule.lookahead_assertion_id);
186            p.st()
187                .builder
188                .update_lookahead_assertion(new_id, new_la)
189                .expect("range");
190        }
191        let root_old = p.st().base.root_rule_id();
192        let root_new = p.rule_id_map[&root_old];
193        let builder = std::mem::take(&mut p.st().builder);
194        builder.get_by_id(root_new).expect("root mapped")
195    }
196
197    fn st(&mut self) -> &mut MutatorState {
198        self.state
199            .get_or_insert_with(|| MutatorState::new(GrammarData::new()))
200    }
201}
202
203impl GrammarMutator for DeadCodeEliminator {
204    fn state(&mut self) -> &mut MutatorState {
205        self.st()
206    }
207
208    fn visit_tag_dispatch(&mut self, e: &OwnedExpr) -> i32 {
209        let mut td = e.tag_dispatch.clone().expect("td");
210        for pair in &mut td.tag_rule_pairs {
211            pair.1 = self.rule_id_map[&pair.1];
212        }
213        rebuild_tag_dispatch(&mut self.state().builder, &td)
214    }
215
216    fn visit_rule_ref(&mut self, e: &OwnedExpr) -> i32 {
217        let new_id = self.rule_id_map[&e.data[0]];
218        self.state().builder.add_rule_ref(new_id)
219    }
220
221    fn visit_repeat(&mut self, e: &OwnedExpr) -> i32 {
222        let new_id = self.rule_id_map[&e.data[0]];
223        self.state()
224            .builder
225            .add_repeat(new_id, e.data[1], e.data[2])
226    }
227}
228#[path = "optimizer_pipeline.rs"]
229mod optimizer_pipeline;
230pub use optimizer_pipeline::{GrammarOptimizer, RepetitionNormalizer};
231
232#[cfg(test)]
233#[path = "optimizer_tests.rs"]
234mod tests;
metrale_grammar/grammar/functor/optimizer.rs

metrale_grammar/grammar/functor/
optimizer.rs
