cfg_symbol_bit_matrix/
symbol_bit_matrix.rs

1use std::ops::{self, Deref, DerefMut};
2
3use bit_matrix::BitMatrix;
4
5use cfg_grammar::Cfg;
6use cfg_symbol::{Symbol, SymbolSource};
7
8#[derive(Debug)]
9pub struct SymbolBitMatrix {
10    bit_matrix: BitMatrix,
11}
12
13pub struct DirectDerivationMatrix(SymbolBitMatrix);
14pub struct ReachabilityMatrix(SymbolBitMatrix);
15pub struct UnitDerivationMatrix(SymbolBitMatrix);
16
17impl SymbolBitMatrix {
18    fn new(num_syms: usize) -> Self {
19        SymbolBitMatrix {
20            bit_matrix: BitMatrix::new(num_syms, num_syms),
21        }
22    }
23
24    fn set(&mut self, row: Symbol, col: Symbol, included: bool) {
25        self.bit_matrix.set(row.usize(), col.usize(), included);
26    }
27
28    pub fn iter_row_syms(&self, row: Symbol) -> impl Iterator<Item = Symbol> + '_ {
29        self.bit_matrix
30            .iter_row(row.usize())
31            .zip(SymbolSource::generate_fresh())
32            .filter_map(|(present, sym)| if present { Some(sym) } else { None })
33    }
34}
35
36impl Deref for SymbolBitMatrix {
37    type Target = BitMatrix;
38    fn deref(&self) -> &Self::Target {
39        &self.bit_matrix
40    }
41}
42
43impl DerefMut for SymbolBitMatrix {
44    fn deref_mut(&mut self) -> &mut Self::Target {
45        &mut self.bit_matrix
46    }
47}
48
49impl Deref for DirectDerivationMatrix {
50    type Target = SymbolBitMatrix;
51    fn deref(&self) -> &Self::Target {
52        &self.0
53    }
54}
55
56impl DerefMut for DirectDerivationMatrix {
57    fn deref_mut(&mut self) -> &mut Self::Target {
58        &mut self.0
59    }
60}
61
62impl Deref for ReachabilityMatrix {
63    type Target = SymbolBitMatrix;
64    fn deref(&self) -> &Self::Target {
65        &self.0
66    }
67}
68
69impl DerefMut for ReachabilityMatrix {
70    fn deref_mut(&mut self) -> &mut Self::Target {
71        &mut self.0
72    }
73}
74
75impl Deref for UnitDerivationMatrix {
76    type Target = SymbolBitMatrix;
77    fn deref(&self) -> &Self::Target {
78        &self.0
79    }
80}
81
82impl DerefMut for UnitDerivationMatrix {
83    fn deref_mut(&mut self) -> &mut Self::Target {
84        &mut self.0
85    }
86}
87
88impl From<DirectDerivationMatrix> for SymbolBitMatrix {
89    fn from(value: DirectDerivationMatrix) -> Self {
90        value.0
91    }
92}
93
94impl From<ReachabilityMatrix> for SymbolBitMatrix {
95    fn from(value: ReachabilityMatrix) -> Self {
96        value.0
97    }
98}
99
100impl From<UnitDerivationMatrix> for SymbolBitMatrix {
101    fn from(value: UnitDerivationMatrix) -> Self {
102        value.0
103    }
104}
105
106static TRUE: bool = true;
107static FALSE: bool = false;
108
109impl ops::Index<(Symbol, Symbol)> for SymbolBitMatrix {
110    type Output = bool;
111    fn index(&self, index: (Symbol, Symbol)) -> &Self::Output {
112        if self.bit_matrix[(index.0.usize(), index.1.usize())] {
113            &TRUE
114        } else {
115            &FALSE
116        }
117    }
118}
119
120impl TryFrom<BitMatrix> for SymbolBitMatrix {
121    type Error = ();
122
123    fn try_from(bit_matrix: BitMatrix) -> Result<Self, Self::Error> {
124        let (rows, cols) = bit_matrix.size();
125        if rows == cols {
126            Ok(SymbolBitMatrix { bit_matrix })
127        } else {
128            Err(())
129        }
130    }
131}
132
133impl From<SymbolBitMatrix> for BitMatrix {
134    fn from(value: SymbolBitMatrix) -> Self {
135        value.bit_matrix
136    }
137}
138
139impl ReachabilityMatrix {
140    pub fn reflexive(mut self) -> Self {
141        self.reflexive_closure();
142        self
143    }
144}
145
146impl DirectDerivationMatrix {
147    /// Returns the derivation matrix.
148    pub fn reachability(mut self) -> ReachabilityMatrix {
149        self.transitive_closure();
150        ReachabilityMatrix(self.into())
151    }
152}
153
154pub trait CfgSymbolBitMatrixExt {
155    fn empty_matrix(&self) -> SymbolBitMatrix;
156    fn direct_derivation_matrix(&self) -> DirectDerivationMatrix;
157    fn reachability_matrix(&self) -> ReachabilityMatrix;
158    fn unit_derivation_matrix(&self) -> UnitDerivationMatrix;
159}
160
161impl CfgSymbolBitMatrixExt for Cfg {
162    fn empty_matrix(&self) -> SymbolBitMatrix {
163        SymbolBitMatrix::new(self.num_syms())
164    }
165
166    fn direct_derivation_matrix(&self) -> DirectDerivationMatrix {
167        let mut derivation = self.empty_matrix();
168
169        for rule in self.rules() {
170            for &sym in rule.rhs.iter() {
171                derivation.set(rule.lhs, sym, true);
172            }
173        }
174
175        DirectDerivationMatrix(derivation)
176    }
177
178    fn reachability_matrix(&self) -> ReachabilityMatrix {
179        self.direct_derivation_matrix().reachability()
180    }
181
182    fn unit_derivation_matrix(&self) -> UnitDerivationMatrix {
183        let mut unit_derivation = self.empty_matrix();
184
185        for rule in self.rules() {
186            // A rule of form `A ::= A` is not a cycle. We can represent unit rules in the form of
187            // a directed graph. The rule `A ::= A` is then presented as a self-loop. Self-loops
188            // aren't cycles.
189            if rule.rhs.len() == 1 && rule.lhs != rule.rhs[0] {
190                unit_derivation.set(rule.lhs, rule.rhs[0], true);
191            }
192        }
193
194        unit_derivation.transitive_closure();
195        UnitDerivationMatrix(unit_derivation)
196    }
197}
cfg_symbol_bit_matrix/symbol_bit_matrix.rs

cfg_symbol_bit_matrix/
symbol_bit_matrix.rs
