src/booleans.rs

   1 use rustc::lint::{LintArray, LateLintPass, LateContext, LintPass};
   2 use rustc_front::hir::*;
   3 use rustc_front::intravisit::*;
   4 use syntax::ast::{LitKind, DUMMY_NODE_ID};
   5 use syntax::codemap::{DUMMY_SP, dummy_spanned};
   6 use utils::{span_lint_and_then, in_macro, snippet_opt, SpanlessEq};
   7
   8 /// **What it does:** This lint checks for boolean expressions that can be written more concisely
   9 ///
  10 /// **Why is this bad?** Readability of boolean expressions suffers from unnecesessary duplication
  11 ///
  12 /// **Known problems:** Ignores short circuting behavior, bitwise and/or and xor. Ends up suggesting things like !(a == b)
  13 ///
  14 /// **Example:** `if a && true` should be `if a`
  15 declare_lint! {
  16     pub NONMINIMAL_BOOL, Warn,
  17     "checks for boolean expressions that can be written more concisely"
  18 }
  19
  20 /// **What it does:** This lint checks for boolean expressions that contain terminals that can be eliminated
  21 ///
  22 /// **Why is this bad?** This is most likely a logic bug
  23 ///
  24 /// **Known problems:** Ignores short circuiting behavior
  25 ///
  26 /// **Example:** The `b` in `if a && b || a` is unnecessary because the expression is equivalent to `if a`
  27 declare_lint! {
  28     pub LOGIC_BUG, Warn,
  29     "checks for boolean expressions that contain terminals which can be eliminated"
  30 }
  31
  32 #[derive(Copy,Clone)]
  33 pub struct NonminimalBool;
  34
  35 impl LintPass for NonminimalBool {
  36     fn get_lints(&self) -> LintArray {
  37         lint_array!(NONMINIMAL_BOOL, LOGIC_BUG)
  38     }
  39 }
  40
  41 impl LateLintPass for NonminimalBool {
  42     fn check_item(&mut self, cx: &LateContext, item: &Item) {
  43         NonminimalBoolVisitor(cx).visit_item(item)
  44     }
  45 }
  46
  47 struct NonminimalBoolVisitor<'a, 'tcx: 'a>(&'a LateContext<'a, 'tcx>);
  48
  49 use quine_mc_cluskey::Bool;
  50 struct Hir2Qmm<'a, 'tcx: 'a, 'v> {
  51     terminals: Vec<&'v Expr>,
  52     cx: &'a LateContext<'a, 'tcx>
  53 }
  54
  55 impl<'a, 'tcx, 'v> Hir2Qmm<'a, 'tcx, 'v> {
  56     fn extract(&mut self, op: BinOp_, a: &[&'v Expr], mut v: Vec<Bool>) -> Result<Vec<Bool>, String> {
  57         for a in a {
  58             if let ExprBinary(binop, ref lhs, ref rhs) = a.node {
  59                 if binop.node == op {
  60                     v = self.extract(op, &[lhs, rhs], v)?;
  61                     continue;
  62                 }
  63             }
  64             v.push(self.run(a)?);
  65         }
  66         Ok(v)
  67     }
  68
  69     fn run(&mut self, e: &'v Expr) -> Result<Bool, String> {
  70         // prevent folding of `cfg!` macros and the like
  71         if !in_macro(self.cx, e.span) {
  72             match e.node {
  73                 ExprUnary(UnNot, ref inner) => return Ok(Bool::Not(box self.run(inner)?)),
  74                 ExprBinary(binop, ref lhs, ref rhs) => {
  75                     match binop.node {
  76                         BiOr => return Ok(Bool::Or(self.extract(BiOr, &[lhs, rhs], Vec::new())?)),
  77                         BiAnd => return Ok(Bool::And(self.extract(BiAnd, &[lhs, rhs], Vec::new())?)),
  78                         _ => {},
  79                     }
  80                 },
  81                 ExprLit(ref lit) => {
  82                     match lit.node {
  83                         LitKind::Bool(true) => return Ok(Bool::True),
  84                         LitKind::Bool(false) => return Ok(Bool::False),
  85                         _ => {},
  86                     }
  87                 },
  88                 _ => {},
  89             }
  90         }
  91         for (n, expr) in self.terminals.iter().enumerate() {
  92             if SpanlessEq::new(self.cx).ignore_fn().eq_expr(e, expr) {
  93                 #[allow(cast_possible_truncation)]
  94                 return Ok(Bool::Term(n as u8));
  95             }
  96             let negated = match e.node {
  97                 ExprBinary(binop, ref lhs, ref rhs) => {
  98                     let mk_expr = |op| Expr {
  99                         id: DUMMY_NODE_ID,
 100                         span: DUMMY_SP,
 101                         attrs: None,
 102                         node: ExprBinary(dummy_spanned(op), lhs.clone(), rhs.clone()),
 103                     };
 104                     match binop.node {
 105                         BiEq => mk_expr(BiNe),
 106                         BiNe => mk_expr(BiEq),
 107                         BiGt => mk_expr(BiLe),
 108                         BiGe => mk_expr(BiLt),
 109                         BiLt => mk_expr(BiGe),
 110                         BiLe => mk_expr(BiGt),
 111                         _ => continue,
 112                     }
 113                 },
 114                 _ => continue,
 115             };
 116             if SpanlessEq::new(self.cx).ignore_fn().eq_expr(&negated, expr) {
 117                 #[allow(cast_possible_truncation)]
 118                 return Ok(Bool::Not(Box::new(Bool::Term(n as u8))));
 119             }
 120         }
 121         let n = self.terminals.len();
 122         self.terminals.push(e);
 123         if n < 32 {
 124             #[allow(cast_possible_truncation)]
 125             Ok(Bool::Term(n as u8))
 126         } else {
 127             Err("too many literals".to_owned())
 128         }
 129     }
 130 }
 131
 132 macro_rules! brackets {
 133     ($val:expr => $($name:ident),*) => {
 134         match $val {
 135             $($name(_) => true,)*
 136             _ => false,
 137         }
 138     }
 139 }
 140
 141 fn suggest(cx: &LateContext, suggestion: &Bool, terminals: &[&Expr]) -> String {
 142     fn recurse(brackets: bool, cx: &LateContext, suggestion: &Bool, terminals: &[&Expr], mut s: String) -> String {
 143         use quine_mc_cluskey::Bool::*;
 144         match *suggestion {
 145             True => {
 146                 s.push_str("true");
 147                 s
 148             },
 149             False => {
 150                 s.push_str("false");
 151                 s
 152             },
 153             Not(ref inner) => {
 154                 s.push('!');
 155                 recurse(brackets!(**inner => And, Or, Term), cx, inner, terminals, s)
 156             },
 157             And(ref v) => {
 158                 if brackets {
 159                     s.push('(');
 160                 }
 161                 s = recurse(brackets!(v[0] => Or), cx, &v[0], terminals, s);
 162                 for inner in &v[1..] {
 163                     s.push_str(" && ");
 164                     s = recurse(brackets!(*inner => Or), cx, inner, terminals, s);
 165                 }
 166                 if brackets {
 167                     s.push(')');
 168                 }
 169                 s
 170             },
 171             Or(ref v) => {
 172                 if brackets {
 173                     s.push('(');
 174                 }
 175                 s = recurse(false, cx, &v[0], terminals, s);
 176                 for inner in &v[1..] {
 177                     s.push_str(" || ");
 178                     s = recurse(false, cx, inner, terminals, s);
 179                 }
 180                 if brackets {
 181                     s.push(')');
 182                 }
 183                 s
 184             },
 185             Term(n) => {
 186                 if brackets {
 187                     if let ExprBinary(..) = terminals[n as usize].node {
 188                         s.push('(');
 189                     }
 190                 }
 191                 s.push_str(&snippet_opt(cx, terminals[n as usize].span).expect("don't try to improve booleans created by macros"));
 192                 if brackets {
 193                     if let ExprBinary(..) = terminals[n as usize].node {
 194                         s.push(')');
 195                     }
 196                 }
 197                 s
 198             }
 199         }
 200     }
 201     recurse(false, cx, suggestion, terminals, String::new())
 202 }
 203
 204 fn simple_negate(b: Bool) -> Bool {
 205     use quine_mc_cluskey::Bool::*;
 206     match b {
 207         True => False,
 208         False => True,
 209         t @ Term(_) => Not(Box::new(t)),
 210         And(mut v) => {
 211             for el in &mut v {
 212                 *el = simple_negate(::std::mem::replace(el, True));
 213             }
 214             Or(v)
 215         },
 216         Or(mut v) => {
 217             for el in &mut v {
 218                 *el = simple_negate(::std::mem::replace(el, True));
 219             }
 220             And(v)
 221         },
 222         Not(inner) => *inner,
 223     }
 224 }
 225
 226 #[derive(Default)]
 227 struct Stats {
 228     terminals: [usize; 32],
 229     negations: usize,
 230     ops: usize,
 231 }
 232
 233 fn terminal_stats(b: &Bool) -> Stats {
 234     fn recurse(b: &Bool, stats: &mut Stats) {
 235         match *b {
 236             True | False => stats.ops += 1,
 237             Not(ref inner) => {
 238                 match **inner {
 239                     And(_) | Or(_) => stats.ops += 1, // brackets are also operations
 240                     _ => stats.negations += 1,
 241                 }
 242                 recurse(inner, stats);
 243             },
 244             And(ref v) | Or(ref v) => {
 245                 stats.ops += v.len() - 1;
 246                 for inner in v {
 247                     recurse(inner, stats);
 248                 }
 249             },
 250             Term(n) => stats.terminals[n as usize] += 1,
 251         }
 252     }
 253     use quine_mc_cluskey::Bool::*;
 254     let mut stats = Stats::default();
 255     recurse(b, &mut stats);
 256     stats
 257 }
 258
 259 impl<'a, 'tcx> NonminimalBoolVisitor<'a, 'tcx> {
 260     fn bool_expr(&self, e: &Expr) {
 261         let mut h2q = Hir2Qmm {
 262             terminals: Vec::new(),
 263             cx: self.0,
 264         };
 265         if let Ok(expr) = h2q.run(e) {
 266             let stats = terminal_stats(&expr);
 267             let mut simplified = expr.simplify();
 268             for simple in Bool::Not(Box::new(expr.clone())).simplify() {
 269                 match simple {
 270                     Bool::Not(_) | Bool::True | Bool::False => {},
 271                     _ => simplified.push(Bool::Not(Box::new(simple.clone()))),
 272                 }
 273                 let simple_negated = simple_negate(simple);
 274                 if simplified.iter().any(|s| *s == simple_negated) {
 275                     continue;
 276                 }
 277                 simplified.push(simple_negated);
 278             }
 279             let mut improvements = Vec::new();
 280             'simplified: for suggestion in &simplified {
 281                 let simplified_stats = terminal_stats(&suggestion);
 282                 let mut improvement = false;
 283                 for i in 0..32 {
 284                     // ignore any "simplifications" that end up requiring a terminal more often than in the original expression
 285                     if stats.terminals[i] < simplified_stats.terminals[i] {
 286                         continue 'simplified;
 287                     }
 288                     if stats.terminals[i] != 0 && simplified_stats.terminals[i] == 0 {
 289                         span_lint_and_then(self.0, LOGIC_BUG, e.span, "this boolean expression contains a logic bug", |db| {
 290                             db.span_help(h2q.terminals[i].span, "this expression can be optimized out by applying boolean operations to the outer expression");
 291                             db.span_suggestion(e.span, "it would look like the following", suggest(self.0, suggestion, &h2q.terminals));
 292                         });
 293                         // don't also lint `NONMINIMAL_BOOL`
 294                         return;
 295                     }
 296                     // if the number of occurrences of a terminal decreases or any of the stats decreases while none increases
 297                     improvement |= (stats.terminals[i] > simplified_stats.terminals[i]) ||
 298                         (stats.negations > simplified_stats.negations && stats.ops == simplified_stats.ops) ||
 299                         (stats.ops > simplified_stats.ops && stats.negations == simplified_stats.negations);
 300                 }
 301                 if improvement {
 302                     improvements.push(suggestion);
 303                 }
 304             }
 305             if !improvements.is_empty() {
 306                 span_lint_and_then(self.0, NONMINIMAL_BOOL, e.span, "this boolean expression can be simplified", |db| {
 307                     for suggestion in &improvements {
 308                         db.span_suggestion(e.span, "try", suggest(self.0, suggestion, &h2q.terminals));
 309                     }
 310                 });
 311             }
 312         }
 313     }
 314 }
 315
 316 impl<'a, 'v, 'tcx> Visitor<'v> for NonminimalBoolVisitor<'a, 'tcx> {
 317     fn visit_expr(&mut self, e: &'v Expr) {
 318         if in_macro(self.0, e.span) { return }
 319         match e.node {
 320             ExprBinary(binop, _, _) if binop.node == BiOr || binop.node == BiAnd => self.bool_expr(e),
 321             ExprUnary(UnNot, ref inner) => {
 322                 if self.0.tcx.node_types()[&inner.id].is_bool() {
 323                     self.bool_expr(e);
 324                 } else {
 325                     walk_expr(self, e);
 326                 }
 327             },
 328             _ => walk_expr(self, e),
 329         }
 330     }
 331 }