cfg_grammar/
symbol_bit_set.rs

1//! Informs whether symbols are terminal or nonterminal.
2
3use std::{iter, ops};
4
5use bit_vec;
6use bit_vec::BitVec;
7
8use crate::local_prelude::*;
9
10/// A set of symbols in the form of a bit vector.
11#[derive(miniserde::Serialize, miniserde::Deserialize, Clone, Debug)]
12pub struct SymbolBitSet {
13    bit_vec: BitVec,
14}
15
16impl Default for SymbolBitSet {
17    fn default() -> Self {
18        Self::new()
19    }
20}
21
22impl SymbolBitSet {
23    /// Constructs an empty `SymbolBitSet`.
24    pub fn new() -> Self {
25        SymbolBitSet {
26            bit_vec: BitVec::new(),
27        }
28    }
29
30    /// Constructs a `SymbolBitSet`.
31    pub fn from_elem(grammar: &Cfg, elem: bool) -> Self {
32        SymbolBitSet {
33            bit_vec: BitVec::from_elem(grammar.num_syms(), elem),
34        }
35    }
36
37    pub fn reset(&mut self, symbol_source: &SymbolSource) {
38        self.bit_vec = BitVec::new();
39        self.bit_vec
40            .extend(iter::repeat(false).take(symbol_source.num_syms()));
41    }
42
43    pub fn set_all(&mut self, symbol_source: &SymbolSource) {
44        self.bit_vec = BitVec::new();
45        self.bit_vec
46            .extend(iter::repeat(true).take(symbol_source.num_syms()));
47    }
48
49    pub fn used(&mut self, grammar: &Cfg) {
50        self.reset(grammar.sym_source());
51        for rule in grammar.rules() {
52            self.set(rule.lhs, true);
53            for &sym in &rule.rhs[..] {
54                self.set(sym, true);
55            }
56        }
57    }
58
59    pub fn unused(&mut self, grammar: &Cfg) {
60        self.set_all(grammar.sym_source());
61        for rule in grammar.rules() {
62            self.set(rule.lhs, false);
63            for &sym in &rule.rhs[..] {
64                self.set(sym, false);
65            }
66        }
67    }
68
69    pub fn negate(&mut self) {
70        self.bit_vec.negate();
71    }
72
73    /// Gathers information about whether symbols are terminal or nonterminal.
74    /// Constructs a set of terminal symbols.
75    ///
76    /// Constructs a data structure in O(n) time.
77    pub fn terminal(&mut self, grammar: &Cfg) {
78        self.set_all(grammar.sym_source());
79        for rule in grammar.rules() {
80            self.set(rule.lhs, false);
81        }
82    }
83
84    /// Gathers information about whether symbols are terminal or nonterminal.
85    /// Constructs a set of terminal symbols.
86    ///
87    /// Constructs a data structure in O(n) time.
88    pub fn nulling(&mut self, grammar: &Cfg) {
89        if self.is_empty() {
90            self.reset(grammar.sym_source());
91        }
92        for rule in grammar.rules() {
93            if rule.rhs.is_empty() {
94                self.set(rule.lhs, true);
95            }
96        }
97    }
98
99    /// Gathers information about whether symbols are terminal or nonterminal.
100    /// Constructs a set of terminal symbols.
101    ///
102    /// Constructs a data structure in O(n) time.
103    pub fn productive(&mut self, grammar: &Cfg) {
104        if self.is_empty() {
105            self.reset(grammar.sym_source());
106        }
107        for rule in grammar.rules() {
108            self.set(rule.lhs, true);
109        }
110    }
111
112    pub fn subtract_productive(&mut self, grammar: &Cfg) {
113        if self.is_empty() {
114            self.set_all(grammar.sym_source());
115        }
116        for rule in grammar.rules() {
117            self.set(rule.lhs, false);
118        }
119    }
120
121    pub fn set(&mut self, index: Symbol, elem: bool) {
122        self.bit_vec.set(index.usize(), elem);
123    }
124
125    pub fn bit_vec(&self) -> &BitVec {
126        &self.bit_vec
127    }
128
129    /// Converts into a bit vector.
130    pub fn into_bit_vec(self) -> BitVec {
131        self.bit_vec
132    }
133
134    /// Iterates over symbols in the set.
135    pub fn iter(&self) -> impl Iterator<Item = Symbol> + use<'_> {
136        self.bit_vec
137            .iter()
138            .zip(SymbolSource::generate_fresh())
139            .filter_map(|(is_present, sym)| if is_present { Some(sym) } else { None })
140    }
141
142    pub fn union(&mut self, other: &SymbolBitSet) {
143        self.bit_vec.or(&other.bit_vec);
144    }
145
146    pub fn len(&self) -> usize {
147        self.bit_vec.len()
148    }
149
150    pub fn is_empty(&self) -> bool {
151        self.bit_vec.is_empty()
152    }
153
154    pub fn all(&self) -> bool {
155        self.bit_vec.iter().all(|b| b)
156    }
157
158    pub fn reserve(&mut self, len: usize) {
159        self.bit_vec
160            .extend(iter::repeat(false).take(len.saturating_sub(self.bit_vec.len())));
161    }
162}
163
164static TRUE: bool = true;
165static FALSE: bool = false;
166
167impl ops::Index<Symbol> for SymbolBitSet {
168    type Output = bool;
169
170    fn index(&self, index: Symbol) -> &Self::Output {
171        if self.bit_vec[index.usize()] {
172            &TRUE
173        } else {
174            &FALSE
175        }
176    }
177}
178
179impl Cfg {
180    pub fn terminal_symbols(&self) -> SymbolBitSet {
181        let mut set = SymbolBitSet::new();
182        set.terminal(self);
183        set
184    }
185
186    pub fn nulling_symbols(&self) -> SymbolBitSet {
187        let mut set = SymbolBitSet::new();
188        set.reset(self.sym_source());
189        set.nulling(self);
190        set
191    }
192
193    pub fn unused_symbols(&self) -> SymbolBitSet {
194        let mut set = SymbolBitSet::new();
195        set.reset(self.sym_source());
196        set.unused(self);
197        set
198    }
199}
cfg_grammar/symbol_bit_set.rs

cfg_grammar/
symbol_bit_set.rs
