cfg_symbol_bit_matrix/
remap_symbols.rs

1//! Remaps symbols and removes unused symbols.
2
3use std::cmp::Ordering;
4
5use cfg_symbol::SymbolSource;
6use log::trace;
7
8use cfg_grammar::{Cfg, CfgRule};
9use cfg_symbol::Symbol;
10use cfg_symbol::intern::Mapping;
11
12/// Remaps symbols and removes unused symbols.
13pub struct Remap<'a> {
14    grammar: &'a mut Cfg,
15    mapping: Mapping,
16}
17
18impl<'a> Remap<'a> {
19    /// Creates `Remap` to record information about remapped symbols.
20    pub fn new(grammar: &'a mut Cfg) -> Self {
21        let num_syms = grammar.num_syms();
22        Remap {
23            grammar,
24            mapping: Mapping {
25                to_internal: SymbolSource::generate_fresh()
26                    .take(num_syms)
27                    .map(Some)
28                    .collect(),
29                to_external: SymbolSource::generate_fresh().take(num_syms).collect(),
30            },
31        }
32    }
33
34    /// Removes unused symbols.
35    pub fn remove_unused_symbols(&mut self) {
36        let unused_symbols = self.grammar.unused_symbols();
37        self.reorder_symbols(|sym0, sym1| unused_symbols[sym0].cmp(&unused_symbols[sym1]));
38        let num_syms = self.grammar.num_syms();
39        self.grammar
40            .sym_source_mut()
41            .truncate(num_syms - unused_symbols.iter().count());
42    }
43
44    /// Remaps symbols to satisfy given ordering constraints. The argument
45    /// must be a function that gives total order.
46    pub fn reorder_symbols<F>(&mut self, f: F)
47    where
48        F: Fn(Symbol, Symbol) -> Ordering,
49    {
50        // Create a new map from N to N symbols.
51        let mut new_mapping = Mapping::new(self.grammar.num_syms());
52        new_mapping.to_external = SymbolSource::generate_fresh()
53            .take(self.grammar.num_syms())
54            .collect();
55        // Sort its external symbols (corresponding to internal symbols of self.maps)
56        // according to the given order.
57        new_mapping.to_external.sort_by(|&a, &b| f(a, b));
58        // Update its internal symbol map based on external symbol map.
59        for (before, after) in new_mapping
60            .to_external
61            .iter()
62            .cloned()
63            .zip(SymbolSource::generate_fresh())
64        {
65            new_mapping.to_internal[before.usize()] = Some(after);
66        }
67        self.mapping.translate(&new_mapping);
68        self.remap_symbols(|sym| new_mapping.to_internal[sym.usize()].unwrap());
69    }
70
71    /// Translates symbols in rules to new symbol IDs.
72    ///
73    /// Translates those inside `wrapped_roots` as well.
74    pub fn remap_symbols<F>(&mut self, mut map: F)
75    where
76        F: FnMut(Symbol) -> Symbol,
77    {
78        let mut added_rules = vec![];
79        self.grammar.retain(|rule| {
80            trace!(
81                "REMAP {:?} -> {:?} ::= {:?} -> {:?}",
82                rule.lhs,
83                map(rule.lhs),
84                rule.rhs,
85                rule.rhs.iter().map(|&sym| map(sym)).collect::<Vec<_>>()
86            );
87            if map(rule.lhs) == rule.lhs && rule.rhs.iter().all(|&sym| map(sym) == sym) {
88                true
89            } else {
90                added_rules.push(CfgRule {
91                    lhs: map(rule.lhs),
92                    rhs: rule.rhs.iter().cloned().map(&mut map).collect(),
93                    history: rule.history,
94                });
95                false
96            }
97        });
98        for rule in added_rules {
99            self.grammar.add_rule(rule);
100        }
101
102        // let mut translate = |root: Symbol| {
103        //     if let Some(internal_start) = maps.to_internal[root.usize()] {
104        //         internal_start
105        //     } else {
106        //         // FIXME: weird
107        //         println!("removing {:?}", root);
108        //         // The trivial grammar is a unique edge case -- the start symbol was removed.
109        //         let internal_start = Symbol::from(maps.to_external.len());
110        //         maps.to_internal[root.usize()] = Some(internal_start);
111        //         maps.to_external.push(root);
112        //         internal_start
113        //     }
114        // };
115        let roots: Vec<_> = self.grammar.roots().iter().copied().map(&mut map).collect();
116        self.grammar.set_roots(&roots[..]);
117        let wrapped_roots: Vec<_> = self
118            .grammar
119            .wrapped_roots()
120            .iter()
121            .copied()
122            .map(|mut wrapped_root| {
123                trace!(
124                    "REMAP WRAPPED ROOT {:?}",
125                    (
126                        wrapped_root.inner_root,
127                        wrapped_root.root,
128                        wrapped_root.start_of_input,
129                        wrapped_root.end_of_input
130                    )
131                );
132                wrapped_root.inner_root = map(wrapped_root.inner_root);
133                wrapped_root.root = map(wrapped_root.root);
134                wrapped_root.start_of_input = map(wrapped_root.start_of_input);
135                wrapped_root.end_of_input = map(wrapped_root.end_of_input);
136                wrapped_root
137            })
138            .collect();
139        self.grammar.set_wrapped_roots(&wrapped_roots[..]);
140        self.grammar.sym_source_mut().remap_symbols(map);
141    }
142
143    /// Get the mapping.
144    pub fn get_mapping(self) -> Mapping {
145        self.mapping
146    }
147}
148
149/// Extension trait for running a [`Remap`] on the grammar.
150pub trait CfgRemapSymbolsExt {
151    /// Initiates a [`Remap`] on the grammar.
152    fn remap(&mut self) -> Remap<'_>;
153}
154
155impl CfgRemapSymbolsExt for Cfg {
156    fn remap(&mut self) -> Remap<'_> {
157        Remap::new(self)
158    }
159}
cfg_symbol_bit_matrix/remap_symbols.rs

cfg_symbol_bit_matrix/
remap_symbols.rs
