clippy_lints/src/booleans.rs

   1 use crate::utils::{
   2     eq_expr_value, get_trait_def_id, implements_trait, in_macro, is_type_diagnostic_item, paths, snippet_opt,
   3     span_lint_and_sugg, span_lint_and_then,
   4 };
   5 use if_chain::if_chain;
   6 use rustc_ast::ast::LitKind;
   7 use rustc_errors::Applicability;
   8 use rustc_hir::intravisit::{walk_expr, FnKind, NestedVisitorMap, Visitor};
   9 use rustc_hir::{BinOpKind, Body, Expr, ExprKind, FnDecl, HirId, UnOp};
  10 use rustc_lint::{LateContext, LateLintPass};
  11 use rustc_middle::hir::map::Map;
  12 use rustc_session::{declare_lint_pass, declare_tool_lint};
  13 use rustc_span::source_map::Span;
  14 use rustc_span::sym;
  15
  16 declare_clippy_lint! {
  17     /// **What it does:** Checks for boolean expressions that can be written more
  18     /// concisely.
  19     ///
  20     /// **Why is this bad?** Readability of boolean expressions suffers from
  21     /// unnecessary duplication.
  22     ///
  23     /// **Known problems:** Ignores short circuiting behavior of `||` and
  24     /// `&&`. Ignores `|`, `&` and `^`.
  25     ///
  26     /// **Example:**
  27     /// ```ignore
  28     /// if a && true  // should be: if a
  29     /// if !(a == b)  // should be: if a != b
  30     /// ```
  31     pub NONMINIMAL_BOOL,
  32     complexity,
  33     "boolean expressions that can be written more concisely"
  34 }
  35
  36 declare_clippy_lint! {
  37     /// **What it does:** Checks for boolean expressions that contain terminals that
  38     /// can be eliminated.
  39     ///
  40     /// **Why is this bad?** This is most likely a logic bug.
  41     ///
  42     /// **Known problems:** Ignores short circuiting behavior.
  43     ///
  44     /// **Example:**
  45     /// ```ignore
  46     /// if a && b || a { ... }
  47     /// ```
  48     /// The `b` is unnecessary, the expression is equivalent to `if a`.
  49     pub LOGIC_BUG,
  50     correctness,
  51     "boolean expressions that contain terminals which can be eliminated"
  52 }
  53
  54 // For each pairs, both orders are considered.
  55 const METHODS_WITH_NEGATION: [(&str, &str); 2] = [("is_some", "is_none"), ("is_err", "is_ok")];
  56
  57 declare_lint_pass!(NonminimalBool => [NONMINIMAL_BOOL, LOGIC_BUG]);
  58
  59 impl<'tcx> LateLintPass<'tcx> for NonminimalBool {
  60     fn check_fn(
  61         &mut self,
  62         cx: &LateContext<'tcx>,
  63         _: FnKind<'tcx>,
  64         _: &'tcx FnDecl<'_>,
  65         body: &'tcx Body<'_>,
  66         _: Span,
  67         _: HirId,
  68     ) {
  69         NonminimalBoolVisitor { cx }.visit_body(body)
  70     }
  71 }
  72
  73 struct NonminimalBoolVisitor<'a, 'tcx> {
  74     cx: &'a LateContext<'tcx>,
  75 }
  76
  77 use quine_mc_cluskey::Bool;
  78 struct Hir2Qmm<'a, 'tcx, 'v> {
  79     terminals: Vec<&'v Expr<'v>>,
  80     cx: &'a LateContext<'tcx>,
  81 }
  82
  83 impl<'a, 'tcx, 'v> Hir2Qmm<'a, 'tcx, 'v> {
  84     fn extract(&mut self, op: BinOpKind, a: &[&'v Expr<'_>], mut v: Vec<Bool>) -> Result<Vec<Bool>, String> {
  85         for a in a {
  86             if let ExprKind::Binary(binop, lhs, rhs) = &a.kind {
  87                 if binop.node == op {
  88                     v = self.extract(op, &[lhs, rhs], v)?;
  89                     continue;
  90                 }
  91             }
  92             v.push(self.run(a)?);
  93         }
  94         Ok(v)
  95     }
  96
  97     fn run(&mut self, e: &'v Expr<'_>) -> Result<Bool, String> {
  98         fn negate(bin_op_kind: BinOpKind) -> Option<BinOpKind> {
  99             match bin_op_kind {
 100                 BinOpKind::Eq => Some(BinOpKind::Ne),
 101                 BinOpKind::Ne => Some(BinOpKind::Eq),
 102                 BinOpKind::Gt => Some(BinOpKind::Le),
 103                 BinOpKind::Ge => Some(BinOpKind::Lt),
 104                 BinOpKind::Lt => Some(BinOpKind::Ge),
 105                 BinOpKind::Le => Some(BinOpKind::Gt),
 106                 _ => None,
 107             }
 108         }
 109
 110         // prevent folding of `cfg!` macros and the like
 111         if !e.span.from_expansion() {
 112             match &e.kind {
 113                 ExprKind::Unary(UnOp::Not, inner) => return Ok(Bool::Not(box self.run(inner)?)),
 114                 ExprKind::Binary(binop, lhs, rhs) => match &binop.node {
 115                     BinOpKind::Or => {
 116                         return Ok(Bool::Or(self.extract(BinOpKind::Or, &[lhs, rhs], Vec::new())?));
 117                     },
 118                     BinOpKind::And => {
 119                         return Ok(Bool::And(self.extract(BinOpKind::And, &[lhs, rhs], Vec::new())?));
 120                     },
 121                     _ => (),
 122                 },
 123                 ExprKind::Lit(lit) => match lit.node {
 124                     LitKind::Bool(true) => return Ok(Bool::True),
 125                     LitKind::Bool(false) => return Ok(Bool::False),
 126                     _ => (),
 127                 },
 128                 _ => (),
 129             }
 130         }
 131         for (n, expr) in self.terminals.iter().enumerate() {
 132             if eq_expr_value(self.cx, e, expr) {
 133                 #[allow(clippy::cast_possible_truncation)]
 134                 return Ok(Bool::Term(n as u8));
 135             }
 136
 137             if_chain! {
 138                 if let ExprKind::Binary(e_binop, e_lhs, e_rhs) = &e.kind;
 139                 if implements_ord(self.cx, e_lhs);
 140                 if let ExprKind::Binary(expr_binop, expr_lhs, expr_rhs) = &expr.kind;
 141                 if negate(e_binop.node) == Some(expr_binop.node);
 142                 if eq_expr_value(self.cx, e_lhs, expr_lhs);
 143                 if eq_expr_value(self.cx, e_rhs, expr_rhs);
 144                 then {
 145                     #[allow(clippy::cast_possible_truncation)]
 146                     return Ok(Bool::Not(Box::new(Bool::Term(n as u8))));
 147                 }
 148             }
 149         }
 150         let n = self.terminals.len();
 151         self.terminals.push(e);
 152         if n < 32 {
 153             #[allow(clippy::cast_possible_truncation)]
 154             Ok(Bool::Term(n as u8))
 155         } else {
 156             Err("too many literals".to_owned())
 157         }
 158     }
 159 }
 160
 161 struct SuggestContext<'a, 'tcx, 'v> {
 162     terminals: &'v [&'v Expr<'v>],
 163     cx: &'a LateContext<'tcx>,
 164     output: String,
 165 }
 166
 167 impl<'a, 'tcx, 'v> SuggestContext<'a, 'tcx, 'v> {
 168     fn recurse(&mut self, suggestion: &Bool) -> Option<()> {
 169         use quine_mc_cluskey::Bool::{And, False, Not, Or, Term, True};
 170         match suggestion {
 171             True => {
 172                 self.output.push_str("true");
 173             },
 174             False => {
 175                 self.output.push_str("false");
 176             },
 177             Not(inner) => match **inner {
 178                 And(_) | Or(_) => {
 179                     self.output.push('!');
 180                     self.output.push('(');
 181                     self.recurse(inner);
 182                     self.output.push(')');
 183                 },
 184                 Term(n) => {
 185                     let terminal = self.terminals[n as usize];
 186                     if let Some(str) = simplify_not(self.cx, terminal) {
 187                         self.output.push_str(&str)
 188                     } else {
 189                         self.output.push('!');
 190                         let snip = snippet_opt(self.cx, terminal.span)?;
 191                         self.output.push_str(&snip);
 192                     }
 193                 },
 194                 True | False | Not(_) => {
 195                     self.output.push('!');
 196                     self.recurse(inner)?;
 197                 },
 198             },
 199             And(v) => {
 200                 for (index, inner) in v.iter().enumerate() {
 201                     if index > 0 {
 202                         self.output.push_str(" && ");
 203                     }
 204                     if let Or(_) = *inner {
 205                         self.output.push('(');
 206                         self.recurse(inner);
 207                         self.output.push(')');
 208                     } else {
 209                         self.recurse(inner);
 210                     }
 211                 }
 212             },
 213             Or(v) => {
 214                 for (index, inner) in v.iter().rev().enumerate() {
 215                     if index > 0 {
 216                         self.output.push_str(" || ");
 217                     }
 218                     self.recurse(inner);
 219                 }
 220             },
 221             &Term(n) => {
 222                 let snip = snippet_opt(self.cx, self.terminals[n as usize].span)?;
 223                 self.output.push_str(&snip);
 224             },
 225         }
 226         Some(())
 227     }
 228 }
 229
 230 fn simplify_not(cx: &LateContext<'_>, expr: &Expr<'_>) -> Option<String> {
 231     match &expr.kind {
 232         ExprKind::Binary(binop, lhs, rhs) => {
 233             if !implements_ord(cx, lhs) {
 234                 return None;
 235             }
 236
 237             match binop.node {
 238                 BinOpKind::Eq => Some(" != "),
 239                 BinOpKind::Ne => Some(" == "),
 240                 BinOpKind::Lt => Some(" >= "),
 241                 BinOpKind::Gt => Some(" <= "),
 242                 BinOpKind::Le => Some(" > "),
 243                 BinOpKind::Ge => Some(" < "),
 244                 _ => None,
 245             }
 246             .and_then(|op| {
 247                 Some(format!(
 248                     "{}{}{}",
 249                     snippet_opt(cx, lhs.span)?,
 250                     op,
 251                     snippet_opt(cx, rhs.span)?
 252                 ))
 253             })
 254         },
 255         ExprKind::MethodCall(path, _, args, _) if args.len() == 1 => {
 256             let type_of_receiver = cx.typeck_results().expr_ty(&args[0]);
 257             if !is_type_diagnostic_item(cx, type_of_receiver, sym::option_type)
 258                 && !is_type_diagnostic_item(cx, type_of_receiver, sym::result_type)
 259             {
 260                 return None;
 261             }
 262             METHODS_WITH_NEGATION
 263                 .iter()
 264                 .cloned()
 265                 .flat_map(|(a, b)| vec![(a, b), (b, a)])
 266                 .find(|&(a, _)| {
 267                     let path: &str = &path.ident.name.as_str();
 268                     a == path
 269                 })
 270                 .and_then(|(_, neg_method)| Some(format!("{}.{}()", snippet_opt(cx, args[0].span)?, neg_method)))
 271         },
 272         _ => None,
 273     }
 274 }
 275
 276 fn suggest(cx: &LateContext<'_>, suggestion: &Bool, terminals: &[&Expr<'_>]) -> String {
 277     let mut suggest_context = SuggestContext {
 278         terminals,
 279         cx,
 280         output: String::new(),
 281     };
 282     suggest_context.recurse(suggestion);
 283     suggest_context.output
 284 }
 285
 286 fn simple_negate(b: Bool) -> Bool {
 287     use quine_mc_cluskey::Bool::{And, False, Not, Or, Term, True};
 288     match b {
 289         True => False,
 290         False => True,
 291         t @ Term(_) => Not(Box::new(t)),
 292         And(mut v) => {
 293             for el in &mut v {
 294                 *el = simple_negate(::std::mem::replace(el, True));
 295             }
 296             Or(v)
 297         },
 298         Or(mut v) => {
 299             for el in &mut v {
 300                 *el = simple_negate(::std::mem::replace(el, True));
 301             }
 302             And(v)
 303         },
 304         Not(inner) => *inner,
 305     }
 306 }
 307
 308 #[derive(Default)]
 309 struct Stats {
 310     terminals: [usize; 32],
 311     negations: usize,
 312     ops: usize,
 313 }
 314
 315 fn terminal_stats(b: &Bool) -> Stats {
 316     fn recurse(b: &Bool, stats: &mut Stats) {
 317         match b {
 318             True | False => stats.ops += 1,
 319             Not(inner) => {
 320                 match **inner {
 321                     And(_) | Or(_) => stats.ops += 1, // brackets are also operations
 322                     _ => stats.negations += 1,
 323                 }
 324                 recurse(inner, stats);
 325             },
 326             And(v) | Or(v) => {
 327                 stats.ops += v.len() - 1;
 328                 for inner in v {
 329                     recurse(inner, stats);
 330                 }
 331             },
 332             &Term(n) => stats.terminals[n as usize] += 1,
 333         }
 334     }
 335     use quine_mc_cluskey::Bool::{And, False, Not, Or, Term, True};
 336     let mut stats = Stats::default();
 337     recurse(b, &mut stats);
 338     stats
 339 }
 340
 341 impl<'a, 'tcx> NonminimalBoolVisitor<'a, 'tcx> {
 342     fn bool_expr(&self, e: &'tcx Expr<'_>) {
 343         let mut h2q = Hir2Qmm {
 344             terminals: Vec::new(),
 345             cx: self.cx,
 346         };
 347         if let Ok(expr) = h2q.run(e) {
 348             if h2q.terminals.len() > 8 {
 349                 // QMC has exponentially slow behavior as the number of terminals increases
 350                 // 8 is reasonable, it takes approximately 0.2 seconds.
 351                 // See #825
 352                 return;
 353             }
 354
 355             let stats = terminal_stats(&expr);
 356             let mut simplified = expr.simplify();
 357             for simple in Bool::Not(Box::new(expr)).simplify() {
 358                 match simple {
 359                     Bool::Not(_) | Bool::True | Bool::False => {},
 360                     _ => simplified.push(Bool::Not(Box::new(simple.clone()))),
 361                 }
 362                 let simple_negated = simple_negate(simple);
 363                 if simplified.iter().any(|s| *s == simple_negated) {
 364                     continue;
 365                 }
 366                 simplified.push(simple_negated);
 367             }
 368             let mut improvements = Vec::with_capacity(simplified.len());
 369             'simplified: for suggestion in &simplified {
 370                 let simplified_stats = terminal_stats(suggestion);
 371                 let mut improvement = false;
 372                 for i in 0..32 {
 373                     // ignore any "simplifications" that end up requiring a terminal more often
 374                     // than in the original expression
 375                     if stats.terminals[i] < simplified_stats.terminals[i] {
 376                         continue 'simplified;
 377                     }
 378                     if stats.terminals[i] != 0 && simplified_stats.terminals[i] == 0 {
 379                         span_lint_and_then(
 380                             self.cx,
 381                             LOGIC_BUG,
 382                             e.span,
 383                             "this boolean expression contains a logic bug",
 384                             |diag| {
 385                                 diag.span_help(
 386                                     h2q.terminals[i].span,
 387                                     "this expression can be optimized out by applying boolean operations to the \
 388                                      outer expression",
 389                                 );
 390                                 diag.span_suggestion(
 391                                     e.span,
 392                                     "it would look like the following",
 393                                     suggest(self.cx, suggestion, &h2q.terminals),
 394                                     // nonminimal_bool can produce minimal but
 395                                     // not human readable expressions (#3141)
 396                                     Applicability::Unspecified,
 397                                 );
 398                             },
 399                         );
 400                         // don't also lint `NONMINIMAL_BOOL`
 401                         return;
 402                     }
 403                     // if the number of occurrences of a terminal decreases or any of the stats
 404                     // decreases while none increases
 405                     improvement |= (stats.terminals[i] > simplified_stats.terminals[i])
 406                         || (stats.negations > simplified_stats.negations && stats.ops == simplified_stats.ops)
 407                         || (stats.ops > simplified_stats.ops && stats.negations == simplified_stats.negations);
 408                 }
 409                 if improvement {
 410                     improvements.push(suggestion);
 411                 }
 412             }
 413             let nonminimal_bool_lint = |suggestions: Vec<_>| {
 414                 span_lint_and_then(
 415                     self.cx,
 416                     NONMINIMAL_BOOL,
 417                     e.span,
 418                     "this boolean expression can be simplified",
 419                     |diag| {
 420                         diag.span_suggestions(
 421                             e.span,
 422                             "try",
 423                             suggestions.into_iter(),
 424                             // nonminimal_bool can produce minimal but
 425                             // not human readable expressions (#3141)
 426                             Applicability::Unspecified,
 427                         );
 428                     },
 429                 );
 430             };
 431             if improvements.is_empty() {
 432                 let mut visitor = NotSimplificationVisitor { cx: self.cx };
 433                 visitor.visit_expr(e);
 434             } else {
 435                 nonminimal_bool_lint(
 436                     improvements
 437                         .into_iter()
 438                         .map(|suggestion| suggest(self.cx, suggestion, &h2q.terminals))
 439                         .collect(),
 440                 );
 441             }
 442         }
 443     }
 444 }
 445
 446 impl<'a, 'tcx> Visitor<'tcx> for NonminimalBoolVisitor<'a, 'tcx> {
 447     type Map = Map<'tcx>;
 448
 449     fn visit_expr(&mut self, e: &'tcx Expr<'_>) {
 450         if in_macro(e.span) {
 451             return;
 452         }
 453         match &e.kind {
 454             ExprKind::Binary(binop, _, _) if binop.node == BinOpKind::Or || binop.node == BinOpKind::And => {
 455                 self.bool_expr(e)
 456             },
 457             ExprKind::Unary(UnOp::Not, inner) => {
 458                 if self.cx.typeck_results().node_types()[inner.hir_id].is_bool() {
 459                     self.bool_expr(e);
 460                 } else {
 461                     walk_expr(self, e);
 462                 }
 463             },
 464             _ => walk_expr(self, e),
 465         }
 466     }
 467     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 468         NestedVisitorMap::None
 469     }
 470 }
 471
 472 fn implements_ord<'tcx>(cx: &LateContext<'tcx>, expr: &Expr<'_>) -> bool {
 473     let ty = cx.typeck_results().expr_ty(expr);
 474     get_trait_def_id(cx, &paths::ORD).map_or(false, |id| implements_trait(cx, ty, id, &[]))
 475 }
 476
 477 struct NotSimplificationVisitor<'a, 'tcx> {
 478     cx: &'a LateContext<'tcx>,
 479 }
 480
 481 impl<'a, 'tcx> Visitor<'tcx> for NotSimplificationVisitor<'a, 'tcx> {
 482     type Map = Map<'tcx>;
 483
 484     fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
 485         if let ExprKind::Unary(UnOp::Not, inner) = &expr.kind {
 486             if let Some(suggestion) = simplify_not(self.cx, inner) {
 487                 span_lint_and_sugg(
 488                     self.cx,
 489                     NONMINIMAL_BOOL,
 490                     expr.span,
 491                     "this boolean expression can be simplified",
 492                     "try",
 493                     suggestion,
 494                     Applicability::MachineApplicable,
 495                 );
 496             }
 497         }
 498
 499         walk_expr(self, expr);
 500     }
 501     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 502         NestedVisitorMap::None
 503     }
 504 }