cfg_classify/
cyclical.rs

1//! Cycle detection and elimination.
2
3use std::borrow::{Borrow, BorrowMut};
4use std::collections::BTreeMap;
5
6use cfg_grammar::{Cfg, CfgRule, SymbolBitSet};
7use cfg_symbol::SymbolSource;
8use cfg_symbol_bit_matrix::{CfgSymbolBitMatrixExt, UnitDerivationMatrix};
9
10/// Provides information about cycles among unit derivations in the grammar. There are two ways of
11/// pruning cycles.
12pub struct Cycles<G: Borrow<Cfg>> {
13    grammar: G,
14    unit_derivation: UnitDerivationMatrix,
15    cycle_free: Option<bool>,
16}
17
18impl<G: Borrow<Cfg>> Cycles<G> {
19    /// Analyzes the grammar's cycles.
20    pub fn new(grammar: G) -> Self {
21        Cycles {
22            unit_derivation: grammar.borrow().unit_derivation_matrix(),
23            cycle_free: None,
24            grammar,
25        }
26    }
27
28    /// Checks whether the grammar is cycle-free.
29    pub fn cycle_free(&mut self) -> bool {
30        *self.cycle_free.get_or_insert_with(|| {
31            SymbolSource::generate_fresh()
32                .take(self.grammar.borrow().num_syms())
33                .all(|i| !self.unit_derivation[(i, i)])
34        })
35    }
36
37    /// Iterates over rules that participate in a cycle.
38    pub fn classify(&self) -> impl Iterator<Item = (&CfgRule, bool)> + '_ {
39        self.grammar.borrow().rules().map(move |rule| {
40            (
41                rule,
42                rule.rhs.len() == 1 && self.unit_derivation[(rule.rhs[0], rule.lhs)],
43            )
44        })
45    }
46
47    /// Iterates over rules that participate in a cycle.
48    pub fn cycle_participants(&self, get_cyclical: bool) -> impl Iterator<Item = &CfgRule> + '_ {
49        self.classify().filter_map(move |(rule, is_cyclical)| {
50            if is_cyclical ^ !get_cyclical {
51                Some(rule)
52            } else {
53                None
54            }
55        })
56    }
57}
58
59impl<G: BorrowMut<Cfg>> Cycles<G> {
60    /// Removes all rules that participate in a cycle. Doesn't preserve the language represented
61    /// by the grammar.
62    pub fn remove_cycles(&mut self) {
63        if !self.cycle_free() {
64            self.grammar.borrow_mut().retain(|rule| {
65                !(rule.rhs.len() == 1 && self.unit_derivation[(rule.rhs[0], rule.lhs)])
66            });
67        }
68    }
69
70    /// Rewrites all rules that participate in a cycle. Preserves the language represented
71    /// by the grammar.
72    pub fn rewrite_cycles(&mut self) {
73        let mut translation = BTreeMap::new();
74        let mut row = SymbolBitSet::from_elem(self.grammar.borrow(), false);
75        if !self.cycle_free() {
76            let unit_derivation = &self.unit_derivation;
77            self.grammar.borrow_mut().retain(|rule| {
78                // We have `A ::= B`.
79                if rule.rhs.len() == 1 && unit_derivation[(rule.rhs[0], rule.lhs)] {
80                    // `B` derives `A`.
81                    if !translation.contains_key(&rule.lhs) {
82                        // Start rewrite. Check which symbols participate in this cycle.
83                        // Get the union of `n`th row and column.
84                        for (lhs_derives, s) in unit_derivation
85                            .iter_row(rule.lhs.usize())
86                            .zip(SymbolSource::generate_fresh())
87                        {
88                            row.set(s, lhs_derives && unit_derivation[(s, rule.lhs)])
89                        }
90                        for sym in row.iter() {
91                            translation.insert(sym, Some(rule.lhs));
92                        }
93                        translation.insert(rule.lhs, None);
94                    }
95                    false
96                } else {
97                    true
98                }
99            });
100            // Rewrite symbols using the `translation` map, potentially leaving
101            // some symbols unused.
102            let mut rewritten_rules = vec![];
103            self.grammar.borrow_mut().retain(|rule| {
104                let mut new_rule = rule.clone();
105                let mut changed = false;
106                if let Some(&Some(new_lhs)) = translation.get(&rule.lhs) {
107                    new_rule.lhs = new_lhs;
108                    changed = true;
109                }
110                let mut rhs = new_rule.rhs.to_vec();
111                for sym in &mut rhs {
112                    if let Some(&Some(new_sym)) = translation.get(sym) {
113                        *sym = new_sym;
114                        changed = true;
115                    }
116                }
117                if changed {
118                    rewritten_rules.push(CfgRule {
119                        lhs: new_rule.lhs,
120                        rhs: rhs.into(),
121                        history: new_rule.history,
122                    });
123                }
124                !changed
125            });
126            for rule in rewritten_rules {
127                self.grammar.borrow_mut().add_rule(rule);
128            }
129        }
130    }
131}
cfg_classify/cyclical.rs

cfg_classify/
cyclical.rs
