cfg_classify/
useful.rs

1//! Analysis of rule usefulness.
2
3use cfg_grammar::CfgRule;
4use cfg_symbol_bit_matrix::CfgSymbolBitMatrixExt;
5use cfg_symbol_bit_matrix::ReachabilityMatrix;
6
7use cfg_grammar::Cfg;
8use cfg_grammar::SymbolBitSet;
9use cfg_symbol::Symbol;
10
11/// Contains the information about usefulness of the grammar's rules.
12/// Useful rules are both reachable and productive.
13pub struct Usefulness {
14    reachability: ReachabilityMatrix,
15    reachable_syms: SymbolBitSet,
16    productivity: SymbolBitSet,
17}
18
19/// A reference to a useless rule, together with the reason for its uselessness.
20#[derive(Copy, Clone, Debug)]
21pub struct UsefulnessForRule<'a> {
22    rule: &'a CfgRule,
23    usefulness: RuleUsefulness,
24}
25
26/// Useful rules are both reachable and productive.
27#[derive(Copy, Clone, Debug)]
28pub struct RuleUsefulness {
29    /// Indicates whether the rule is unreachable.
30    pub reachable: bool,
31    /// Indicates whether the rule is unproductive.
32    pub productive: bool,
33}
34
35impl<'a> UsefulnessForRule<'a> {
36    /// Get reference to the rule.
37    pub fn rule(&self) -> &CfgRule {
38        self.rule
39    }
40
41    /// Get information about this rule's usefulness.
42    pub fn usefulness(&self) -> RuleUsefulness {
43        self.usefulness
44    }
45}
46
47impl RuleUsefulness {
48    fn is_useless(&self) -> bool {
49        !self.reachable || !self.productive
50    }
51}
52
53/// Returns the set of productive symbols.
54///
55/// An productive symbol is one where there exists a rule
56/// with that symbol on the LHS as well as all symbols
57/// being productive, terminal or nulling.
58fn productive_syms(grammar: &Cfg) -> SymbolBitSet {
59    let mut productive_syms = SymbolBitSet::new();
60    productive_syms.terminal(grammar);
61    productive_syms.nulling(grammar);
62    grammar.rhs_closure_for_all(&mut productive_syms);
63    productive_syms
64}
65
66impl Usefulness {
67    /// Analyzes usefulness of the grammar's rules. In particular, it checks for reachable
68    /// and productive symbols.
69    pub fn new(grammar: &Cfg) -> Self {
70        let mut productivity = productive_syms(grammar);
71        let reachability: ReachabilityMatrix = grammar.reachability_matrix().reflexive();
72        let mut unused_syms = SymbolBitSet::new();
73        unused_syms.unused(grammar);
74        let mut reachable_syms = SymbolBitSet::from_elem(grammar, false);
75
76        productivity.union(&unused_syms);
77        reachable_syms.union(&unused_syms);
78
79        debug_assert_eq!(
80            reachability.size(),
81            (productivity.space(), productivity.space())
82        );
83
84        Usefulness {
85            productivity,
86            reachability,
87            reachable_syms,
88        }
89    }
90
91    /// Checks whether a symbol is productive. Can be used to determine the precise reason
92    /// of a rule's unproductiveness.
93    pub fn productivity(&self, sym: Symbol) -> bool {
94        self.productivity[sym]
95    }
96
97    /// Sets symbol reachability. Takes an array of reachable symbols.
98    pub fn reachable(&mut self, syms: impl AsRef<[Symbol]>) {
99        for &sym in syms.as_ref() {
100            for derived in self.reachability.iter_row_syms(sym) {
101                self.reachable_syms.set(derived, true);
102            }
103        }
104    }
105
106    /// Checks whether all rules in the grammar are useful.
107    pub fn all_useful(&self) -> bool {
108        self.productivity.all() && self.reachable_syms.all()
109    }
110
111    /// Checks whether all rules in the grammar are productive.
112    pub fn all_productive(&self) -> bool {
113        self.productivity.all()
114    }
115
116    /// Checks whether all rules in the grammar are reachable.
117    pub fn all_reachable(&self) -> bool {
118        self.reachable_syms.all()
119    }
120
121    /// Get the usefulness of the given rule.
122    pub fn usefulness<'r>(&self, rule: &'r CfgRule) -> UsefulnessForRule<'r> {
123        let productive = rule.rhs.iter().all(|&sym| self.productivity[sym]);
124        let reachable = self.reachable_syms[rule.lhs];
125        UsefulnessForRule {
126            rule,
127            usefulness: RuleUsefulness {
128                productive,
129                reachable,
130            },
131        }
132    }
133
134    fn uselessness_if_useless<'r>(&self, rule: &'r CfgRule) -> Option<UsefulnessForRule<'r>> {
135        let usefulness = self.usefulness(rule);
136        if usefulness.usefulness.is_useless() {
137            Some(usefulness)
138        } else {
139            None
140        }
141    }
142
143    /// Returns an iterator over the grammar's useless rules.
144    pub fn useless_rules<'a, 'g>(
145        &'a self,
146        grammar: &'g Cfg,
147    ) -> impl Iterator<Item = UsefulnessForRule<'g>> + 'a
148    where
149        'g: 'a,
150    {
151        grammar
152            .rules()
153            .filter_map(|rule| self.uselessness_if_useless(rule))
154    }
155
156    /// Removes useless rules. The language represented by the grammar doesn't change.
157    pub fn remove_useless_rules(&self, grammar: &mut Cfg) {
158        if !self.all_useful() {
159            let productivity = &self.productivity;
160            let reachable_syms = &self.reachable_syms;
161            let rule_is_useful = |rule: &CfgRule| {
162                let productive = rule.rhs.iter().all(|&sym| productivity[sym]);
163                let reachable = reachable_syms[rule.lhs];
164                productive && reachable
165            };
166            grammar.retain(rule_is_useful);
167        }
168    }
169}
cfg_classify/useful.rs

cfg_classify/
useful.rs
