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    pub fn remap_symbols<F>(&mut self, mut map: F)
73    where
74        F: FnMut(Symbol) -> Symbol,
75    {
76        let mut added_rules = vec![];
77        self.grammar.retain(|rule| {
78            trace!(
79                "REMAP {:?} -> {:?} ::= {:?} -> {:?}",
80                rule.lhs,
81                map(rule.lhs),
82                rule.rhs,
83                rule.rhs.iter().map(|&sym| map(sym)).collect::<Vec<_>>()
84            );
85            if map(rule.lhs) == rule.lhs && rule.rhs.iter().all(|&sym| map(sym) == sym) {
86                true
87            } else {
88                added_rules.push(CfgRule {
89                    lhs: map(rule.lhs),
90                    rhs: rule.rhs.iter().cloned().map(&mut map).collect(),
91                    history: rule.history,
92                });
93                false
94            }
95        });
96        for rule in added_rules {
97            self.grammar.add_rule(rule);
98        }
99
100        // let mut translate = |root: Symbol| {
101        //     if let Some(internal_start) = maps.to_internal[root.usize()] {
102        //         internal_start
103        //     } else {
104        //         // FIXME: weird
105        //         println!("removing {:?}", root);
106        //         // The trivial grammar is a unique edge case -- the start symbol was removed.
107        //         let internal_start = Symbol::from(maps.to_external.len());
108        //         maps.to_internal[root.usize()] = Some(internal_start);
109        //         maps.to_external.push(root);
110        //         internal_start
111        //     }
112        // };
113        let roots: Vec<_> = self.grammar.roots().iter().copied().map(&mut map).collect();
114        self.grammar.set_roots(&roots[..]);
115        let wrapped_roots: Vec<_> = self
116            .grammar
117            .wrapped_roots()
118            .iter()
119            .copied()
120            .map(|mut wrapped_root| {
121                trace!(
122                    "REMAP WRAPPED ROOT {:?}",
123                    (
124                        wrapped_root.inner_root,
125                        wrapped_root.root,
126                        wrapped_root.start_of_input,
127                        wrapped_root.end_of_input
128                    )
129                );
130                wrapped_root.inner_root = map(wrapped_root.inner_root);
131                wrapped_root.root = map(wrapped_root.root);
132                wrapped_root.start_of_input = map(wrapped_root.start_of_input);
133                wrapped_root.end_of_input = map(wrapped_root.end_of_input);
134                wrapped_root
135            })
136            .collect();
137        self.grammar.set_wrapped_roots(&wrapped_roots[..]);
138        self.grammar.sym_source_mut().remap_symbols(map);
139    }
140
141    /// Get the mapping.
142    pub fn get_mapping(self) -> Mapping {
143        self.mapping
144    }
145}
146
147pub trait CfgRemapSymbolsExt {
148    fn remap(&mut self) -> Remap<'_>;
149}
150
151impl CfgRemapSymbolsExt for Cfg {
152    fn remap(&mut self) -> Remap<'_> {
153        Remap::new(self)
154    }
155}
cfg_symbol_bit_matrix/remap_symbols.rs

cfg_symbol_bit_matrix/
remap_symbols.rs
