crates/cfg/src/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
   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)
  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) => 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.
 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
 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(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.
 323 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 }