cfg_classify/
cyclical.rs

1//! Cycle detection and elimination.
2
3use std::collections::BTreeMap;
4
5use bit_matrix::BitMatrix;
6use bit_vec::BitVec;
7
8use cfg_grammar::{
9    rule::{cfg_rule::CfgRule, RuleRef},
10    AsRuleRef, RuleContainer,
11};
12use cfg_symbol::Symbol;
13
14use crate::derivation;
15
16/// Provides information about cycles among unit derivations in the grammar. There are two ways of
17/// pruning cycles.
18pub struct Cycles<G> {
19    grammar: G,
20    unit_derivation: BitMatrix,
21    cycle_free: bool,
22}
23
24/// An iterator over the grammar's useless rules.
25pub struct CycleParticipants<'a, G, I> {
26    rules: I,
27    cycles: &'a Cycles<&'a mut G>,
28}
29
30impl<G> Cycles<G>
31where
32    G: RuleContainer,
33{
34    /// Analyzes the grammar's cycles.
35    pub fn new<'a>(grammar: &'a mut G) -> Cycles<&'a mut G> {
36        let unit_derivation = derivation::unit_derivation_matrix(grammar);
37        let cycle_free = (0..grammar.num_syms()).all(|i| !unit_derivation[(i, i)]);
38        Cycles {
39            unit_derivation: unit_derivation,
40            cycle_free: cycle_free,
41            grammar: grammar,
42        }
43    }
44
45    /// Checks whether the grammar is cycle-free.
46    pub fn cycle_free(&self) -> bool {
47        self.cycle_free
48    }
49}
50
51impl<'a, G> Cycles<&'a mut G>
52where
53    G: RuleContainer,
54{
55    /// Iterates over rules that participate in a cycle.
56    pub fn cycle_participants(
57        &'a self,
58    ) -> CycleParticipants<'a, G, impl Iterator<Item = RuleRef<'a>>> {
59        CycleParticipants {
60            rules: self.grammar.rules(),
61            cycles: self,
62        }
63    }
64
65    /// Removes all rules that participate in a cycle. Doesn't preserve the language represented
66    /// by the grammar.
67    pub fn remove_cycles(&mut self) {
68        if !self.cycle_free {
69            let unit_derivation = &self.unit_derivation;
70            self.grammar.retain(|rule| {
71                rule.rhs.len() != 1 || !unit_derivation[(rule.rhs[0].into(), rule.lhs.into())]
72            });
73        }
74    }
75
76    /// Rewrites all rules that participate in a cycle. Preserves the language represented
77    /// by the grammar.
78    pub fn rewrite_cycles(&mut self) {
79        let mut translation = BTreeMap::new();
80        let mut row = BitVec::from_elem(self.grammar.num_syms(), false);
81        if !self.cycle_free {
82            let unit_derivation = &self.unit_derivation;
83            self.grammar.retain(|rule| {
84                // We have `A ::= B`.
85                let lhs = rule.lhs.into();
86                if rule.rhs.len() == 1 && unit_derivation[(rule.rhs[0].into(), lhs)] {
87                    // `B` derives `A`.
88                    if !translation.contains_key(&rule.lhs) {
89                        // Start rewrite. Check which symbols participate in this cycle.
90                        // Get the union of `n`th row and column.
91                        for (i, lhs_derives) in unit_derivation.iter_row(lhs).enumerate() {
92                            row.set(i, lhs_derives && unit_derivation[(i, lhs)])
93                        }
94                        for (i, is_in_cycle) in row.iter().enumerate() {
95                            if is_in_cycle {
96                                translation.insert(Symbol::from(i), Some(rule.lhs));
97                            }
98                        }
99                        translation.insert(rule.lhs, None);
100                    }
101                    false
102                } else {
103                    true
104                }
105            });
106            // Rewrite symbols using the `translation` map, potentially leaving
107            // some symbols unused.
108            let mut rewritten_rules = vec![];
109            self.grammar.retain(|mut rule| {
110                let mut changed = false;
111                if let Some(&Some(new_lhs)) = translation.get(&rule.lhs) {
112                    rule.lhs = new_lhs;
113                    changed = true;
114                }
115                let mut rhs = rule.rhs.to_vec();
116                for sym in &mut rhs {
117                    if let Some(&Some(new_sym)) = translation.get(sym) {
118                        *sym = new_sym;
119                        changed = true;
120                    }
121                }
122                if changed {
123                    rewritten_rules.push(CfgRule {
124                        lhs: rule.lhs,
125                        rhs,
126                        history_id: rule.history_id,
127                    });
128                }
129                !changed
130            });
131            for rule in rewritten_rules {
132                self.grammar.add_rule(rule.as_rule_ref());
133            }
134        }
135    }
136}
137
138impl<'a, G, I> Iterator for CycleParticipants<'a, G, I>
139where
140    G: RuleContainer + 'a,
141    I: Iterator<Item = RuleRef<'a>>,
142{
143    type Item = I::Item;
144
145    fn next(&mut self) -> Option<Self::Item> {
146        if self.cycles.cycle_free {
147            return None;
148        }
149
150        for rule in &mut self.rules {
151            if rule.rhs.len() == 1
152                && self.cycles.unit_derivation[(rule.rhs[0].into(), rule.lhs.into())]
153            {
154                return Some(rule);
155            }
156        }
157
158        None
159    }
160}
cfg_classify/cyclical.rs

cfg_classify/
cyclical.rs
