cfg/
dnf.rs

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
9use std::fmt::{self, Write};
10
11use rustc_hash::FxHashSet;
12
13use crate::{CfgAtom, CfgDiff, CfgExpr, CfgOptions, InactiveReason};
14
15/// A `#[cfg]` directive in Disjunctive Normal Form (DNF).
16pub struct DnfExpr {
17    conjunctions: Vec<Conjunction>,
18}
19
20struct Conjunction {
21    literals: Vec<Literal>,
22}
23
24struct Literal {
25    negate: bool,
26    var: Option<CfgAtom>, // None = Invalid
27}
28
29impl DnfExpr {
30    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.
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
125impl fmt::Display for DnfExpr {
126    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
145impl Conjunction {
146    fn new(parts: Box<[CfgExpr]>) -> Self {
147        let mut literals = Vec::new();
148        for part in parts.into_vec() {
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
165impl fmt::Display for Conjunction {
166    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
185impl 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
200impl 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) => 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
219struct Builder {
220    expr: DnfExpr,
221}
222
223impl 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(Box::new([expr])));
231            }
232            CfgExpr::All(conj) => {
233                self.expr.conjunctions.push(Conjunction::new(conj));
234            }
235            CfgExpr::Any(disj) => {
236                let mut disj = disj.into_vec();
237                disj.reverse();
238                while let Some(conj) = disj.pop() {
239                    match conj {
240                        CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::All(_) | CfgExpr::Not(_) => {
241                            self.expr.conjunctions.push(Conjunction::new(Box::new([conj])));
242                        }
243                        CfgExpr::Any(inner_disj) => {
244                            // Flatten.
245                            disj.extend(inner_disj.into_vec().into_iter().rev());
246                        }
247                    }
248                }
249            }
250        }
251
252        self.expr
253    }
254}
255
256fn make_dnf(expr: CfgExpr) -> CfgExpr {
257    match expr {
258        CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => expr,
259        CfgExpr::Any(e) => flatten(CfgExpr::Any(e.into_vec().into_iter().map(make_dnf).collect())),
260        CfgExpr::All(e) => {
261            let e = e.into_vec().into_iter().map(make_dnf).collect::<Vec<_>>();
262
263            flatten(CfgExpr::Any(distribute_conj(&e).into_boxed_slice()))
264        }
265    }
266}
267
268/// Turns a conjunction of expressions into a disjunction of expressions.
269fn distribute_conj(conj: &[CfgExpr]) -> Vec<CfgExpr> {
270    fn go(out: &mut Vec<CfgExpr>, with: &mut Vec<CfgExpr>, rest: &[CfgExpr]) {
271        match rest {
272            [head, tail @ ..] => match head {
273                CfgExpr::Any(disj) => {
274                    for part in disj.iter() {
275                        with.push(part.clone());
276                        go(out, with, tail);
277                        with.pop();
278                    }
279                }
280                _ => {
281                    with.push(head.clone());
282                    go(out, with, tail);
283                    with.pop();
284                }
285            },
286            _ => {
287                // Turn accumulated parts into a new conjunction.
288                out.push(CfgExpr::All(with.clone().into_boxed_slice()));
289            }
290        }
291    }
292
293    let mut out = Vec::new(); // contains only `all()`
294    let mut with = Vec::new();
295
296    go(&mut out, &mut with, conj);
297
298    out
299}
300
301fn make_nnf(expr: &CfgExpr) -> CfgExpr {
302    match expr {
303        CfgExpr::Invalid | CfgExpr::Atom(_) => expr.clone(),
304        CfgExpr::Any(expr) => CfgExpr::Any(expr.iter().map(make_nnf).collect()),
305        CfgExpr::All(expr) => CfgExpr::All(expr.iter().map(make_nnf).collect()),
306        CfgExpr::Not(operand) => make_nnf_neg(operand),
307    }
308}
309
310fn make_nnf_neg(operand: &CfgExpr) -> CfgExpr {
311    match operand {
312        // Original negated expr
313        CfgExpr::Invalid => CfgExpr::Not(Box::new(CfgExpr::Invalid)), // Original negated expr
314        // Original negated expr
315        CfgExpr::Atom(atom) => CfgExpr::Not(Box::new(CfgExpr::Atom(atom.clone()))),
316        // Remove double negation.
317        CfgExpr::Not(expr) => make_nnf(expr),
318        // Convert negated conjunction/disjunction using DeMorgan's Law.
319        CfgExpr::Any(inner) => CfgExpr::All(inner.iter().map(make_nnf_neg).collect()),
320        // Convert negated conjunction/disjunction using DeMorgan's Law.
321        CfgExpr::All(inner) => CfgExpr::Any(inner.iter().map(make_nnf_neg).collect()),
322    }
323}
324
325/// Collapses nested `any()` and `all()` predicates.
326fn flatten(expr: CfgExpr) -> CfgExpr {
327    match expr {
328        CfgExpr::All(inner) => CfgExpr::All(
329            inner
330                .iter()
331                .flat_map(|e| match e {
332                    CfgExpr::All(inner) => inner.as_ref(),
333                    _ => std::slice::from_ref(e),
334                })
335                .cloned()
336                .collect(),
337        ),
338        CfgExpr::Any(inner) => CfgExpr::Any(
339            inner
340                .iter()
341                .flat_map(|e| match e {
342                    CfgExpr::Any(inner) => inner.as_ref(),
343                    _ => std::slice::from_ref(e),
344                })
345                .cloned()
346                .collect(),
347        ),
348        _ => expr,
349    }
350}
cfg/dnf.rs

cfg/
dnf.rs
