diff options
Diffstat (limited to 'crates/cfg/src/dnf.rs')
-rw-r--r-- | crates/cfg/src/dnf.rs | 320 |
1 files changed, 320 insertions, 0 deletions
diff --git a/crates/cfg/src/dnf.rs b/crates/cfg/src/dnf.rs new file mode 100644 index 000000000..580c9a9a2 --- /dev/null +++ b/crates/cfg/src/dnf.rs | |||
@@ -0,0 +1,320 @@ | |||
1 | //! Disjunctive Normal Form construction. | ||
2 | //! | ||
3 | //! Algorithm from <https://www.cs.drexel.edu/~jjohnson/2015-16/fall/CS270/Lectures/3/dnf.pdf>, | ||
4 | //! which would have been much easier to read if it used pattern matching. It's also missing the | ||
5 | //! entire "distribute ANDs over ORs" part, which is not trivial. Oh well. | ||
6 | //! | ||
7 | //! This is currently both messy and inefficient. Feel free to improve, there are unit tests. | ||
8 | |||
9 | use std::fmt; | ||
10 | |||
11 | use rustc_hash::FxHashSet; | ||
12 | |||
13 | use crate::{CfgAtom, CfgDiff, CfgExpr, CfgOptions, InactiveReason}; | ||
14 | |||
15 | /// A `#[cfg]` directive in Disjunctive Normal Form (DNF). | ||
16 | pub struct DnfExpr { | ||
17 | conjunctions: Vec<Conjunction>, | ||
18 | } | ||
19 | |||
20 | struct Conjunction { | ||
21 | literals: Vec<Literal>, | ||
22 | } | ||
23 | |||
24 | struct Literal { | ||
25 | negate: bool, | ||
26 | var: Option<CfgAtom>, // None = Invalid | ||
27 | } | ||
28 | |||
29 | impl DnfExpr { | ||
30 | pub fn new(expr: CfgExpr) -> Self { | ||
31 | let builder = Builder { expr: DnfExpr { conjunctions: Vec::new() } }; | ||
32 | |||
33 | builder.lower(expr.clone()) | ||
34 | } | ||
35 | |||
36 | /// Computes a list of present or absent atoms in `opts` that cause this expression to evaluate | ||
37 | /// to `false`. | ||
38 | /// | ||
39 | /// Note that flipping a subset of these atoms might be sufficient to make the whole expression | ||
40 | /// evaluate to `true`. For that, see `compute_enable_hints`. | ||
41 | /// | ||
42 | /// Returns `None` when `self` is already true, or contains errors. | ||
43 | pub fn why_inactive(&self, opts: &CfgOptions) -> Option<InactiveReason> { | ||
44 | let mut res = InactiveReason { enabled: Vec::new(), disabled: Vec::new() }; | ||
45 | |||
46 | for conj in &self.conjunctions { | ||
47 | let mut conj_is_true = true; | ||
48 | for lit in &conj.literals { | ||
49 | let atom = lit.var.as_ref()?; | ||
50 | let enabled = opts.enabled.contains(atom); | ||
51 | if lit.negate == enabled { | ||
52 | // Literal is false, but needs to be true for this conjunction. | ||
53 | conj_is_true = false; | ||
54 | |||
55 | if enabled { | ||
56 | res.enabled.push(atom.clone()); | ||
57 | } else { | ||
58 | res.disabled.push(atom.clone()); | ||
59 | } | ||
60 | } | ||
61 | } | ||
62 | |||
63 | if conj_is_true { | ||
64 | // This expression is not actually inactive. | ||
65 | return None; | ||
66 | } | ||
67 | } | ||
68 | |||
69 | res.enabled.sort_unstable(); | ||
70 | res.enabled.dedup(); | ||
71 | res.disabled.sort_unstable(); | ||
72 | res.disabled.dedup(); | ||
73 | Some(res) | ||
74 | } | ||
75 | |||
76 | /// Returns `CfgDiff` objects that would enable this directive if applied to `opts`. | ||
77 | pub fn compute_enable_hints<'a>( | ||
78 | &'a self, | ||
79 | opts: &'a CfgOptions, | ||
80 | ) -> impl Iterator<Item = CfgDiff> + 'a { | ||
81 | // A cfg is enabled if any of `self.conjunctions` evaluate to `true`. | ||
82 | |||
83 | self.conjunctions.iter().filter_map(move |conj| { | ||
84 | let mut enable = FxHashSet::default(); | ||
85 | let mut disable = FxHashSet::default(); | ||
86 | for lit in &conj.literals { | ||
87 | let atom = lit.var.as_ref()?; | ||
88 | let enabled = opts.enabled.contains(atom); | ||
89 | if lit.negate && enabled { | ||
90 | disable.insert(atom.clone()); | ||
91 | } | ||
92 | if !lit.negate && !enabled { | ||
93 | enable.insert(atom.clone()); | ||
94 | } | ||
95 | } | ||
96 | |||
97 | // Check that this actually makes `conj` true. | ||
98 | for lit in &conj.literals { | ||
99 | let atom = lit.var.as_ref()?; | ||
100 | let enabled = enable.contains(atom) | ||
101 | || (opts.enabled.contains(atom) && !disable.contains(atom)); | ||
102 | if enabled == lit.negate { | ||
103 | return None; | ||
104 | } | ||
105 | } | ||
106 | |||
107 | if enable.is_empty() && disable.is_empty() { | ||
108 | return None; | ||
109 | } | ||
110 | |||
111 | let mut diff = CfgDiff { | ||
112 | enable: enable.into_iter().collect(), | ||
113 | disable: disable.into_iter().collect(), | ||
114 | }; | ||
115 | |||
116 | // Undo the FxHashMap randomization for consistent output. | ||
117 | diff.enable.sort_unstable(); | ||
118 | diff.disable.sort_unstable(); | ||
119 | |||
120 | Some(diff) | ||
121 | }) | ||
122 | } | ||
123 | } | ||
124 | |||
125 | impl fmt::Display for DnfExpr { | ||
126 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | ||
127 | if self.conjunctions.len() != 1 { | ||
128 | write!(f, "any(")?; | ||
129 | } | ||
130 | for (i, conj) in self.conjunctions.iter().enumerate() { | ||
131 | if i != 0 { | ||
132 | f.write_str(", ")?; | ||
133 | } | ||
134 | |||
135 | write!(f, "{}", conj)?; | ||
136 | } | ||
137 | if self.conjunctions.len() != 1 { | ||
138 | write!(f, ")")?; | ||
139 | } | ||
140 | |||
141 | Ok(()) | ||
142 | } | ||
143 | } | ||
144 | |||
145 | impl Conjunction { | ||
146 | fn new(parts: Vec<CfgExpr>) -> Self { | ||
147 | let mut literals = Vec::new(); | ||
148 | for part in parts { | ||
149 | match part { | ||
150 | CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => { | ||
151 | literals.push(Literal::new(part)); | ||
152 | } | ||
153 | CfgExpr::All(conj) => { | ||
154 | // Flatten. | ||
155 | literals.extend(Conjunction::new(conj).literals); | ||
156 | } | ||
157 | CfgExpr::Any(_) => unreachable!("disjunction in conjunction"), | ||
158 | } | ||
159 | } | ||
160 | |||
161 | Self { literals } | ||
162 | } | ||
163 | } | ||
164 | |||
165 | impl fmt::Display for Conjunction { | ||
166 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | ||
167 | if self.literals.len() != 1 { | ||
168 | write!(f, "all(")?; | ||
169 | } | ||
170 | for (i, lit) in self.literals.iter().enumerate() { | ||
171 | if i != 0 { | ||
172 | f.write_str(", ")?; | ||
173 | } | ||
174 | |||
175 | write!(f, "{}", lit)?; | ||
176 | } | ||
177 | if self.literals.len() != 1 { | ||
178 | write!(f, ")")?; | ||
179 | } | ||
180 | |||
181 | Ok(()) | ||
182 | } | ||
183 | } | ||
184 | |||
185 | impl Literal { | ||
186 | fn new(expr: CfgExpr) -> Self { | ||
187 | match expr { | ||
188 | CfgExpr::Invalid => Self { negate: false, var: None }, | ||
189 | CfgExpr::Atom(atom) => Self { negate: false, var: Some(atom) }, | ||
190 | CfgExpr::Not(expr) => match *expr { | ||
191 | CfgExpr::Invalid => Self { negate: true, var: None }, | ||
192 | CfgExpr::Atom(atom) => Self { negate: true, var: Some(atom) }, | ||
193 | _ => unreachable!("non-atom {:?}", expr), | ||
194 | }, | ||
195 | CfgExpr::Any(_) | CfgExpr::All(_) => unreachable!("non-literal {:?}", expr), | ||
196 | } | ||
197 | } | ||
198 | } | ||
199 | |||
200 | impl fmt::Display for Literal { | ||
201 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | ||
202 | if self.negate { | ||
203 | write!(f, "not(")?; | ||
204 | } | ||
205 | |||
206 | match &self.var { | ||
207 | Some(var) => write!(f, "{}", var)?, | ||
208 | None => f.write_str("<invalid>")?, | ||
209 | } | ||
210 | |||
211 | if self.negate { | ||
212 | write!(f, ")")?; | ||
213 | } | ||
214 | |||
215 | Ok(()) | ||
216 | } | ||
217 | } | ||
218 | |||
219 | struct Builder { | ||
220 | expr: DnfExpr, | ||
221 | } | ||
222 | |||
223 | impl Builder { | ||
224 | fn lower(mut self, expr: CfgExpr) -> DnfExpr { | ||
225 | let expr = make_nnf(expr); | ||
226 | let expr = make_dnf(expr); | ||
227 | |||
228 | match expr { | ||
229 | CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => { | ||
230 | self.expr.conjunctions.push(Conjunction::new(vec![expr])); | ||
231 | } | ||
232 | CfgExpr::All(conj) => { | ||
233 | self.expr.conjunctions.push(Conjunction::new(conj)); | ||
234 | } | ||
235 | CfgExpr::Any(mut disj) => { | ||
236 | disj.reverse(); | ||
237 | while let Some(conj) = disj.pop() { | ||
238 | match conj { | ||
239 | CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::All(_) | CfgExpr::Not(_) => { | ||
240 | self.expr.conjunctions.push(Conjunction::new(vec![conj])); | ||
241 | } | ||
242 | CfgExpr::Any(inner_disj) => { | ||
243 | // Flatten. | ||
244 | disj.extend(inner_disj.into_iter().rev()); | ||
245 | } | ||
246 | } | ||
247 | } | ||
248 | } | ||
249 | } | ||
250 | |||
251 | self.expr | ||
252 | } | ||
253 | } | ||
254 | |||
255 | fn make_dnf(expr: CfgExpr) -> CfgExpr { | ||
256 | match expr { | ||
257 | CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => expr, | ||
258 | CfgExpr::Any(e) => CfgExpr::Any(e.into_iter().map(|expr| make_dnf(expr)).collect()), | ||
259 | CfgExpr::All(e) => { | ||
260 | let e = e.into_iter().map(|expr| make_nnf(expr)).collect::<Vec<_>>(); | ||
261 | |||
262 | CfgExpr::Any(distribute_conj(&e)) | ||
263 | } | ||
264 | } | ||
265 | } | ||
266 | |||
267 | /// Turns a conjunction of expressions into a disjunction of expressions. | ||
268 | fn distribute_conj(conj: &[CfgExpr]) -> Vec<CfgExpr> { | ||
269 | fn go(out: &mut Vec<CfgExpr>, with: &mut Vec<CfgExpr>, rest: &[CfgExpr]) { | ||
270 | match rest { | ||
271 | [head, tail @ ..] => match head { | ||
272 | CfgExpr::Any(disj) => { | ||
273 | for part in disj { | ||
274 | with.push(part.clone()); | ||
275 | go(out, with, tail); | ||
276 | with.pop(); | ||
277 | } | ||
278 | } | ||
279 | _ => { | ||
280 | with.push(head.clone()); | ||
281 | go(out, with, tail); | ||
282 | with.pop(); | ||
283 | } | ||
284 | }, | ||
285 | _ => { | ||
286 | // Turn accumulated parts into a new conjunction. | ||
287 | out.push(CfgExpr::All(with.clone())); | ||
288 | } | ||
289 | } | ||
290 | } | ||
291 | |||
292 | let mut out = Vec::new(); | ||
293 | let mut with = Vec::new(); | ||
294 | |||
295 | go(&mut out, &mut with, conj); | ||
296 | |||
297 | out | ||
298 | } | ||
299 | |||
300 | fn make_nnf(expr: CfgExpr) -> CfgExpr { | ||
301 | match expr { | ||
302 | CfgExpr::Invalid | CfgExpr::Atom(_) => expr, | ||
303 | CfgExpr::Any(expr) => CfgExpr::Any(expr.into_iter().map(|expr| make_nnf(expr)).collect()), | ||
304 | CfgExpr::All(expr) => CfgExpr::All(expr.into_iter().map(|expr| make_nnf(expr)).collect()), | ||
305 | CfgExpr::Not(operand) => match *operand { | ||
306 | CfgExpr::Invalid | CfgExpr::Atom(_) => CfgExpr::Not(operand.clone()), // Original negated expr | ||
307 | CfgExpr::Not(expr) => { | ||
308 | // Remove double negation. | ||
309 | make_nnf(*expr) | ||
310 | } | ||
311 | // Convert negated conjunction/disjunction using DeMorgan's Law. | ||
312 | CfgExpr::Any(inner) => CfgExpr::All( | ||
313 | inner.into_iter().map(|expr| make_nnf(CfgExpr::Not(Box::new(expr)))).collect(), | ||
314 | ), | ||
315 | CfgExpr::All(inner) => CfgExpr::Any( | ||
316 | inner.into_iter().map(|expr| make_nnf(CfgExpr::Not(Box::new(expr)))).collect(), | ||
317 | ), | ||
318 | }, | ||
319 | } | ||
320 | } | ||