cfg_classify/
recursive.rs

1use cfg_grammar::{Cfg, CfgRule};
2use cfg_predict_distance::MinimalDistance;
3use cfg_symbol_bit_matrix::{CfgSymbolBitMatrixExt, ReachabilityMatrix};
4
5/// Calculation of parts of grammar that participate in recursion,
6/// be it left-recursion, right-recursion or middle-recursion.
7pub struct Recursion<'a> {
8    grammar: &'a Cfg,
9    derivation: ReachabilityMatrix,
10}
11
12#[derive(Eq, PartialEq, Debug, Clone, Copy)]
13pub enum RecursionKind {
14    Left,
15    Right,
16    Middle,
17    All,
18}
19
20#[derive(Eq, PartialEq, Debug, Clone, Copy)]
21pub struct RecursiveRule<'a> {
22    pub rule: &'a CfgRule,
23    pub recursion: RecursionKind,
24    pub distances: Option<(usize, usize)>,
25}
26
27pub struct RecursiveRules<'a, 'b, R: Iterator<Item = &'b CfgRule>> {
28    rules: R,
29    recursion: &'b Recursion<'a>,
30}
31
32pub struct RecursiveRulesWithDistances<'a, 'b, R: Iterator<Item = (usize, &'b CfgRule)>> {
33    rules: R,
34    recursion: &'b Recursion<'a>,
35    minimal_distance: MinimalDistance<'a>,
36}
37
38impl<'a> Recursion<'a> {
39    /// Returns a new `MinimalDistance` for a grammar.
40    pub fn new(grammar: &'a Cfg) -> Self {
41        let reachability = grammar.reachability_matrix();
42
43        Recursion {
44            grammar: grammar,
45            derivation: reachability,
46        }
47    }
48
49    pub fn minimal_distances<'b>(
50        &'b self,
51    ) -> RecursiveRulesWithDistances<'a, 'b, impl Iterator<Item = (usize, &'b CfgRule)>> {
52        let mut minimal_distance = MinimalDistance::new(&self.grammar);
53        let mut dots = vec![];
54        for (idx, rule) in self.grammar.rules().enumerate() {
55            let recursive_dot_pos = rule
56                .rhs
57                .iter()
58                .enumerate()
59                .filter(|&(_dot_pos, &rhs_sym)| self.derivation[(rhs_sym, rule.lhs)]);
60            for (dot_pos, _rhs_sym) in recursive_dot_pos {
61                dots.push((idx, dot_pos));
62            }
63        }
64        minimal_distance.minimal_distances(
65            &dots[..],
66            cfg_predict_distance::DistanceDirection::Symmetric,
67        );
68        RecursiveRulesWithDistances {
69            rules: self.grammar.rules().enumerate(),
70            recursion: self,
71            minimal_distance,
72        }
73    }
74
75    pub fn recursive_rules<'b>(
76        &'b self,
77    ) -> RecursiveRules<'a, 'b, impl Iterator<Item = &'b CfgRule>> {
78        RecursiveRules {
79            rules: self.grammar.rules(),
80            recursion: self,
81        }
82    }
83}
84
85impl<'a, 'b, R: Iterator<Item = &'b CfgRule>> Iterator for RecursiveRules<'a, 'b, R> {
86    type Item = RecursiveRule<'b>;
87
88    fn next(&mut self) -> Option<Self::Item> {
89        while let Some(rule) = self.rules.next() {
90            if let Some(recursion) = rule_recursion(rule, &self.recursion.derivation) {
91                return Some(RecursiveRule {
92                    rule,
93                    recursion,
94                    distances: None,
95                });
96            }
97        }
98        None
99    }
100}
101
102impl<'a, 'b, R: Iterator<Item = (usize, &'b CfgRule)>> Iterator
103    for RecursiveRulesWithDistances<'a, 'b, R>
104{
105    type Item = RecursiveRule<'b>;
106
107    fn next(&mut self) -> Option<Self::Item> {
108        while let Some((idx, rule)) = self.rules.next() {
109            if let Some(recursion) = rule_recursion(rule, &self.recursion.derivation) {
110                // if self.recursion.derivation[(rule.lhs, rule.lhs)] {
111                let rule_distances = &self.minimal_distance.distances()[idx][..];
112                return Some(RecursiveRule {
113                    rule,
114                    recursion,
115                    distances: Some((
116                        rule_distances[0].unwrap_or(u32::MAX) as usize,
117                        rule_distances[rule_distances.len() - 1].unwrap_or(u32::MAX) as usize,
118                    )),
119                });
120            }
121        }
122        None
123    }
124}
125
126fn rule_recursion(rule: &CfgRule, derivation: &ReachabilityMatrix) -> Option<RecursionKind> {
127    if rule.rhs.len() == 0 {
128        return None;
129    }
130    if rule
131        .rhs
132        .iter()
133        .all(|&rhs_sym| derivation[(rhs_sym, rule.lhs)])
134    {
135        // ?
136        // derivation[(rule.lhs, rule.lhs)]
137        return Some(RecursionKind::All);
138    }
139    if rule
140        .rhs
141        .iter()
142        .skip(1)
143        .take(rule.rhs.len().saturating_sub(2))
144        .any(|&rhs_sym| derivation[(rhs_sym, rule.lhs)])
145    {
146        return Some(RecursionKind::Middle);
147    }
148    if rule
149        .rhs
150        .first()
151        .map(|&rhs_sym| derivation[(rhs_sym, rule.lhs)])
152        == Some(true)
153    {
154        return Some(RecursionKind::Left);
155    }
156    if rule
157        .rhs
158        .last()
159        .map(|&rhs_sym| derivation[(rhs_sym, rule.lhs)])
160        == Some(true)
161    {
162        return Some(RecursionKind::Right);
163    }
164    None
165}
cfg_classify/recursive.rs

cfg_classify/
recursive.rs
