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::{self, Write};
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 {
new(expr: CfgExpr) -> Self30 pub fn new(expr: CfgExpr) -> Self {
31 let builder = Builder { expr: DnfExpr { conjunctions: Vec::new() } };
32
33 builder.lower(expr)
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.
why_inactive(&self, opts: &CfgOptions) -> Option<InactiveReason>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`.
compute_enable_hints<'a>( &'a self, opts: &'a CfgOptions, ) -> impl Iterator<Item = CfgDiff> + 'a77 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 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result126 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127 if self.conjunctions.len() != 1 {
128 f.write_str("any(")?;
129 }
130 for (i, conj) in self.conjunctions.iter().enumerate() {
131 if i != 0 {
132 f.write_str(", ")?;
133 }
134
135 conj.fmt(f)?;
136 }
137 if self.conjunctions.len() != 1 {
138 f.write_char(')')?;
139 }
140
141 Ok(())
142 }
143 }
144
145 impl Conjunction {
new(parts: Vec<CfgExpr>) -> Self146 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 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result166 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
167 if self.literals.len() != 1 {
168 f.write_str("all(")?;
169 }
170 for (i, lit) in self.literals.iter().enumerate() {
171 if i != 0 {
172 f.write_str(", ")?;
173 }
174
175 lit.fmt(f)?;
176 }
177 if self.literals.len() != 1 {
178 f.write_str(")")?;
179 }
180
181 Ok(())
182 }
183 }
184
185 impl Literal {
new(expr: CfgExpr) -> Self186 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 {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result201 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) => var.fmt(f)?,
208 None => f.write_str("<invalid>")?,
209 }
210
211 if self.negate {
212 f.write_char(')')?;
213 }
214
215 Ok(())
216 }
217 }
218
219 struct Builder {
220 expr: DnfExpr,
221 }
222
223 impl Builder {
lower(mut self, expr: CfgExpr) -> DnfExpr224 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
make_dnf(expr: CfgExpr) -> CfgExpr255 fn make_dnf(expr: CfgExpr) -> CfgExpr {
256 match expr {
257 CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => expr,
258 CfgExpr::Any(e) => flatten(CfgExpr::Any(e.into_iter().map(make_dnf).collect())),
259 CfgExpr::All(e) => {
260 let e = e.into_iter().map(make_dnf).collect::<Vec<_>>();
261
262 flatten(CfgExpr::Any(distribute_conj(&e)))
263 }
264 }
265 }
266
267 /// Turns a conjunction of expressions into a disjunction of expressions.
distribute_conj(conj: &[CfgExpr]) -> Vec<CfgExpr>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(); // contains only `all()`
293 let mut with = Vec::new();
294
295 go(&mut out, &mut with, conj);
296
297 out
298 }
299
make_nnf(expr: CfgExpr) -> CfgExpr300 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(make_nnf).collect()),
304 CfgExpr::All(expr) => CfgExpr::All(expr.into_iter().map(make_nnf).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 }
321
322 /// Collapses nested `any()` and `all()` predicates.
flatten(expr: CfgExpr) -> CfgExpr323 fn flatten(expr: CfgExpr) -> CfgExpr {
324 match expr {
325 CfgExpr::All(inner) => CfgExpr::All(
326 inner
327 .into_iter()
328 .flat_map(|e| match e {
329 CfgExpr::All(inner) => inner,
330 _ => vec![e],
331 })
332 .collect(),
333 ),
334 CfgExpr::Any(inner) => CfgExpr::Any(
335 inner
336 .into_iter()
337 .flat_map(|e| match e {
338 CfgExpr::Any(inner) => inner,
339 _ => vec![e],
340 })
341 .collect(),
342 ),
343 _ => expr,
344 }
345 }
346