metrale_grammar/grammar/functor/
normalizer.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Grammar normalization passes (part 1) — port of the normalizer
4// section of `cpp/grammar_functor.cc`:
5//   SingleElementExprEliminator, RootRuleRenamer, GrammarNormalizer.
6//
7// `StructureNormalizer` lives in `structure_normalizer.rs` to keep
8// each file under the 250-line cap.
9
10use std::collections::HashSet;
11
12use super::mutator::{GrammarMutator, MutatorState, OwnedExpr};
13use super::structure_normalizer::StructureNormalizer;
14use crate::grammar::data::GrammarData;
15use crate::grammar::printer::codepoint_to_bytes;
16
17/// Eliminates single-element sequences/choices and single-codepoint
18/// character classes. `choices("a") -> "a"`, `[a-a] -> "a"`.
19#[derive(Default)]
20pub struct SingleElementExprEliminator {
21    state: Option<MutatorState>,
22}
23
24impl SingleElementExprEliminator {
25    /// Run the pass on `grammar`.
26    pub fn apply(grammar: GrammarData) -> GrammarData {
27        let mut p = Self::default();
28        GrammarMutator::apply(&mut p, grammar)
29    }
30}
31
32impl GrammarMutator for SingleElementExprEliminator {
33    fn state(&mut self) -> &mut MutatorState {
34        self.state
35            .get_or_insert_with(|| MutatorState::new(GrammarData::new()))
36    }
37
38    fn visit_sequence(&mut self, e: &OwnedExpr) -> i32 {
39        let ids: Vec<i32> = e.data.iter().map(|&c| self.visit_expr_id(c)).collect();
40        if ids.len() == 1 {
41            return ids[0];
42        }
43        self.state().builder.add_sequence(&ids)
44    }
45
46    fn visit_choices(&mut self, e: &OwnedExpr) -> i32 {
47        let ids: Vec<i32> = e.data.iter().map(|&c| self.visit_expr_id(c)).collect();
48        if ids.len() == 1 {
49            return ids[0];
50        }
51        self.state().builder.add_choices(&ids)
52    }
53
54    fn visit_character_class(&mut self, e: &OwnedExpr) -> i32 {
55        if e.data.len() == 3 && e.data[0] == 0 && e.data[1] == e.data[2] {
56            let bytes = codepoint_to_bytes(e.data[1]);
57            return self.state().builder.add_byte_string_bytes(&bytes);
58        }
59        self.state().builder.add_grammar_expr(e.kind, &e.data)
60    }
61}
62
63/// Rename the root rule to `"root"`; if another rule is already named
64/// `"root"`, give it a fresh `root_N` name.
65pub struct RootRuleRenamer;
66
67impl RootRuleRenamer {
68    /// Run the pass.
69    pub fn apply(grammar: GrammarData) -> GrammarData {
70        if grammar.root_rule().name == "root" {
71            return grammar;
72        }
73        let mut names: HashSet<String> = HashSet::new();
74        let mut root_name_rule_id = -1;
75        for i in 0..grammar.num_rules() {
76            let n = &grammar.rule(i).name;
77            if n == "root" {
78                root_name_rule_id = i;
79            }
80            names.insert(n.clone());
81        }
82        let mut g = grammar;
83        let root_id = g.root_rule_id();
84        g.set_rule_name(root_id, "root");
85        if root_name_rule_id != -1 {
86            for i in 0..=g.num_rules() {
87                let candidate = format!("root_{i}");
88                if !names.contains(&candidate) {
89                    g.set_rule_name(root_name_rule_id, candidate);
90                    break;
91                }
92            }
93        }
94        g
95    }
96}
97
98/// Normalize a grammar: rename the root rule, then structure-normalize.
99/// Port of `GrammarNormalizer`.
100pub struct GrammarNormalizer;
101
102impl GrammarNormalizer {
103    /// Run the full normalization pipeline.
104    pub fn apply(grammar: GrammarData) -> GrammarData {
105        let renamed = RootRuleRenamer::apply(grammar);
106        StructureNormalizer::apply(renamed)
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113    use crate::grammar::parse_ebnf_default;
114    use crate::grammar::printer::print_grammar;
115
116    fn norm(ebnf: &str) -> GrammarData {
117        GrammarNormalizer::apply(parse_ebnf_default(ebnf).expect("parse"))
118    }
119
120    #[test]
121    fn normalize_simple_string() {
122        let g = norm("root ::= \"abc\"\n");
123        let out = print_grammar(&g);
124        assert!(out.contains("root ::="));
125        assert!(out.contains("\"abc\""));
126    }
127
128    #[test]
129    fn normalize_choices() {
130        let g = norm("root ::= \"a\" | \"b\"\n");
131        let out = print_grammar(&g);
132        assert!(out.contains(" | "));
133    }
134
135    #[test]
136    fn root_renamer_keeps_root() {
137        let g = parse_ebnf_default("root ::= \"x\"\n").unwrap();
138        let renamed = RootRuleRenamer::apply(g);
139        assert_eq!(renamed.root_rule().name, "root");
140    }
141
142    #[test]
143    fn single_element_eliminator_collapses_seq() {
144        let g = parse_ebnf_default("root ::= (\"a\")\n").unwrap();
145        let out = print_grammar(&SingleElementExprEliminator::apply(g));
146        assert!(out.contains("\"a\""));
147    }
148
149    #[test]
150    fn normalize_nested_rule() {
151        let g = norm("root ::= \"a\" | (\"b\" (\"c\" | \"d\"))\n");
152        let out = print_grammar(&g);
153        assert!(g.num_rules() >= 2, "{out}");
154    }
155
156    #[test]
157    fn empty_string_rule() {
158        let g = norm("root ::= \"\"\n");
159        let out = print_grammar(&g);
160        assert!(out.contains("\"\""));
161    }
162
163    #[test]
164    fn normalize_idempotent_shape() {
165        let g1 = norm("root ::= \"a\" \"b\"\n");
166        let g2 = GrammarNormalizer::apply(g1.clone());
167        assert_eq!(print_grammar(&g1), print_grammar(&g2));
168    }
169}
metrale_grammar/grammar/functor/normalizer.rs

metrale_grammar/grammar/functor/
normalizer.rs
