clippy_lints/src/bit_mask.rs

   1 use rustc::hir::*;
   2 use rustc::hir::def::Def;
   3 use rustc::lint::*;
   4 use rustc_const_eval::lookup_const_by_id;
   5 use syntax::ast::LitKind;
   6 use syntax::codemap::Span;
   7 use utils::{span_lint, span_lint_and_then};
   8 use utils::sugg::Sugg;
   9
  10 /// **What it does:** Checks for incompatible bit masks in comparisons.
  11 ///
  12 /// The formula for detecting if an expression of the type `_ <bit_op> m
  13 /// <cmp_op> c` (where `<bit_op>` is one of {`&`, `|`} and `<cmp_op>` is one of
  14 /// {`!=`, `>=`, `>`, `!=`, `>=`, `>`}) can be determined from the following
  15 /// table:
  16 ///
  17 /// |Comparison  |Bit Op|Example     |is always|Formula               |
  18 /// |------------|------|------------|---------|----------------------|
  19 /// |`==` or `!=`| `&`  |`x & 2 == 3`|`false`  |`c & m != c`          |
  20 /// |`<`  or `>=`| `&`  |`x & 2 < 3` |`true`   |`m < c`               |
  21 /// |`>`  or `<=`| `&`  |`x & 1 > 1` |`false`  |`m <= c`              |
  22 /// |`==` or `!=`| `|`  |`x | 1 == 0`|`false`  |`c | m != c`          |
  23 /// |`<`  or `>=`| `|`  |`x | 1 < 1` |`false`  |`m >= c`              |
  24 /// |`<=` or `>` | `|`  |`x | 1 > 0` |`true`   |`m > c`               |
  25 ///
  26 /// **Why is this bad?** If the bits that the comparison cares about are always
  27 /// set to zero or one by the bit mask, the comparison is constant `true` or
  28 /// `false` (depending on mask, compared value, and operators).
  29 ///
  30 /// So the code is actively misleading, and the only reason someone would write
  31 /// this intentionally is to win an underhanded Rust contest or create a
  32 /// test-case for this lint.
  33 ///
  34 /// **Known problems:** None.
  35 ///
  36 /// **Example:**
  37 /// ```rust
  38 /// if (x & 1 == 2) { … }
  39 /// ```
  40 declare_lint! {
  41     pub BAD_BIT_MASK,
  42     Warn,
  43     "expressions of the form `_ & mask == select` that will only ever return `true` or `false`"
  44 }
  45
  46 /// **What it does:** Checks for bit masks in comparisons which can be removed
  47 /// without changing the outcome. The basic structure can be seen in the
  48 /// following table:
  49 ///
  50 /// |Comparison| Bit Op  |Example    |equals |
  51 /// |----------|---------|-----------|-------|
  52 /// |`>` / `<=`|`|` / `^`|`x | 2 > 3`|`x > 3`|
  53 /// |`<` / `>=`|`|` / `^`|`x ^ 1 < 4`|`x < 4`|
  54 ///
  55 /// **Why is this bad?** Not equally evil as [`bad_bit_mask`](#bad_bit_mask),
  56 /// but still a bit misleading, because the bit mask is ineffective.
  57 ///
  58 /// **Known problems:** False negatives: This lint will only match instances
  59 /// where we have figured out the math (which is for a power-of-two compared
  60 /// value). This means things like `x | 1 >= 7` (which would be better written
  61 /// as `x >= 6`) will not be reported (but bit masks like this are fairly
  62 /// uncommon).
  63 ///
  64 /// **Example:**
  65 /// ```rust
  66 /// if (x | 1 > 3) { … }
  67 /// ```
  68 declare_lint! {
  69     pub INEFFECTIVE_BIT_MASK,
  70     Warn,
  71     "expressions where a bit mask will be rendered useless by a comparison, e.g. `(x | 1) > 2`"
  72 }
  73
  74 /// **What it does:** Checks for bit masks that can be replaced by a call
  75 /// to `trailing_zeros`
  76 ///
  77 /// **Why is this bad?** `x.trailing_zeros() > 4` is much clearer than `x & 15
  78 /// == 0`
  79 ///
  80 /// **Known problems:** llvm generates better code for `x & 15 == 0` on x86
  81 ///
  82 /// **Example:**
  83 /// ```rust
  84 /// x & 0x1111 == 0
  85 /// ```
  86 declare_lint! {
  87     pub VERBOSE_BIT_MASK,
  88     Warn,
  89     "expressions where a bit mask is less readable than the corresponding method call"
  90 }
  91
  92 #[derive(Copy, Clone)]
  93 pub struct BitMask;
  94
  95 impl LintPass for BitMask {
  96     fn get_lints(&self) -> LintArray {
  97         lint_array!(BAD_BIT_MASK, INEFFECTIVE_BIT_MASK, VERBOSE_BIT_MASK)
  98     }
  99 }
 100
 101 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for BitMask {
 102     fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, e: &'tcx Expr) {
 103         if let ExprBinary(ref cmp, ref left, ref right) = e.node {
 104             if cmp.node.is_comparison() {
 105                 if let Some(cmp_opt) = fetch_int_literal(cx, right) {
 106                     check_compare(cx, left, cmp.node, cmp_opt, &e.span)
 107                 } else if let Some(cmp_val) = fetch_int_literal(cx, left) {
 108                     check_compare(cx, right, invert_cmp(cmp.node), cmp_val, &e.span)
 109                 }
 110             }
 111         }
 112         if_let_chain!{[
 113             let Expr_::ExprBinary(ref op, ref left, ref right) = e.node,
 114             BinOp_::BiEq == op.node,
 115             let Expr_::ExprBinary(ref op1, ref left1, ref right1) = left.node,
 116             BinOp_::BiBitAnd == op1.node,
 117             let Expr_::ExprLit(ref lit) = right1.node,
 118             let LitKind::Int(n, _) = lit.node,
 119             let Expr_::ExprLit(ref lit1) = right.node,
 120             let LitKind::Int(0, _) = lit1.node,
 121             n.leading_zeros() == n.count_zeros(),
 122         ], {
 123             span_lint_and_then(cx,
 124                                VERBOSE_BIT_MASK,
 125                                e.span,
 126                                "bit mask could be simplified with a call to `trailing_zeros`",
 127                                |db| {
 128                 let sugg = Sugg::hir(cx, left1, "...").maybe_par();
 129                 db.span_suggestion(e.span, "try", format!("{}.trailing_zeros() >= {}", sugg, n.count_ones()));
 130             });
 131         }}
 132     }
 133 }
 134
 135 fn invert_cmp(cmp: BinOp_) -> BinOp_ {
 136     match cmp {
 137         BiEq => BiEq,
 138         BiNe => BiNe,
 139         BiLt => BiGt,
 140         BiGt => BiLt,
 141         BiLe => BiGe,
 142         BiGe => BiLe,
 143         _ => BiOr, // Dummy
 144     }
 145 }
 146
 147
 148 fn check_compare(cx: &LateContext, bit_op: &Expr, cmp_op: BinOp_, cmp_value: u128, span: &Span) {
 149     if let ExprBinary(ref op, ref left, ref right) = bit_op.node {
 150         if op.node != BiBitAnd && op.node != BiBitOr {
 151             return;
 152         }
 153         fetch_int_literal(cx, right)
 154             .or_else(|| fetch_int_literal(cx, left))
 155             .map_or((), |mask| check_bit_mask(cx, op.node, cmp_op, mask, cmp_value, span))
 156     }
 157 }
 158
 159 fn check_bit_mask(cx: &LateContext, bit_op: BinOp_, cmp_op: BinOp_, mask_value: u128, cmp_value: u128, span: &Span) {
 160     match cmp_op {
 161         BiEq | BiNe => match bit_op {
 162             BiBitAnd => if mask_value & cmp_value != cmp_value {
 163                 if cmp_value != 0 {
 164                     span_lint(
 165                         cx,
 166                         BAD_BIT_MASK,
 167                         *span,
 168                         &format!(
 169                             "incompatible bit mask: `_ & {}` can never be equal to `{}`",
 170                             mask_value,
 171                             cmp_value
 172                         ),
 173                     );
 174                 }
 175             } else if mask_value == 0 {
 176                 span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 177             },
 178             BiBitOr => if mask_value | cmp_value != cmp_value {
 179                 span_lint(
 180                     cx,
 181                     BAD_BIT_MASK,
 182                     *span,
 183                     &format!(
 184                         "incompatible bit mask: `_ | {}` can never be equal to `{}`",
 185                         mask_value,
 186                         cmp_value
 187                     ),
 188                 );
 189             },
 190             _ => (),
 191         },
 192         BiLt | BiGe => match bit_op {
 193             BiBitAnd => if mask_value < cmp_value {
 194                 span_lint(
 195                     cx,
 196                     BAD_BIT_MASK,
 197                     *span,
 198                     &format!(
 199                         "incompatible bit mask: `_ & {}` will always be lower than `{}`",
 200                         mask_value,
 201                         cmp_value
 202                     ),
 203                 );
 204             } else if mask_value == 0 {
 205                 span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 206             },
 207             BiBitOr => if mask_value >= cmp_value {
 208                 span_lint(
 209                     cx,
 210                     BAD_BIT_MASK,
 211                     *span,
 212                     &format!(
 213                         "incompatible bit mask: `_ | {}` will never be lower than `{}`",
 214                         mask_value,
 215                         cmp_value
 216                     ),
 217                 );
 218             } else {
 219                 check_ineffective_lt(cx, *span, mask_value, cmp_value, "|");
 220             },
 221             BiBitXor => check_ineffective_lt(cx, *span, mask_value, cmp_value, "^"),
 222             _ => (),
 223         },
 224         BiLe | BiGt => match bit_op {
 225             BiBitAnd => if mask_value <= cmp_value {
 226                 span_lint(
 227                     cx,
 228                     BAD_BIT_MASK,
 229                     *span,
 230                     &format!(
 231                         "incompatible bit mask: `_ & {}` will never be higher than `{}`",
 232                         mask_value,
 233                         cmp_value
 234                     ),
 235                 );
 236             } else if mask_value == 0 {
 237                 span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 238             },
 239             BiBitOr => if mask_value > cmp_value {
 240                 span_lint(
 241                     cx,
 242                     BAD_BIT_MASK,
 243                     *span,
 244                     &format!(
 245                         "incompatible bit mask: `_ | {}` will always be higher than `{}`",
 246                         mask_value,
 247                         cmp_value
 248                     ),
 249                 );
 250             } else {
 251                 check_ineffective_gt(cx, *span, mask_value, cmp_value, "|");
 252             },
 253             BiBitXor => check_ineffective_gt(cx, *span, mask_value, cmp_value, "^"),
 254             _ => (),
 255         },
 256         _ => (),
 257     }
 258 }
 259
 260 fn check_ineffective_lt(cx: &LateContext, span: Span, m: u128, c: u128, op: &str) {
 261     if c.is_power_of_two() && m < c {
 262         span_lint(
 263             cx,
 264             INEFFECTIVE_BIT_MASK,
 265             span,
 266             &format!(
 267                 "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 268                 op,
 269                 m,
 270                 c
 271             ),
 272         );
 273     }
 274 }
 275
 276 fn check_ineffective_gt(cx: &LateContext, span: Span, m: u128, c: u128, op: &str) {
 277     if (c + 1).is_power_of_two() && m <= c {
 278         span_lint(
 279             cx,
 280             INEFFECTIVE_BIT_MASK,
 281             span,
 282             &format!(
 283                 "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 284                 op,
 285                 m,
 286                 c
 287             ),
 288         );
 289     }
 290 }
 291
 292 fn fetch_int_literal(cx: &LateContext, lit: &Expr) -> Option<u128> {
 293     use rustc::ty::subst::Substs;
 294     match lit.node {
 295         ExprLit(ref lit_ptr) => {
 296             if let LitKind::Int(value, _) = lit_ptr.node {
 297                 Some(value) // TODO: Handle sign
 298             } else {
 299                 None
 300             }
 301         },
 302         ExprPath(ref qpath) => {
 303             let def = cx.tables.qpath_def(qpath, lit.hir_id);
 304             if let Def::Const(def_id) = def {
 305                 lookup_const_by_id(cx.tcx, cx.param_env.and((def_id, Substs::empty()))).and_then(|(l, _ty)| {
 306                     let body = if let Some(id) = cx.tcx.hir.as_local_node_id(l) {
 307                         cx.tcx.mir_const_qualif(def_id);
 308                         cx.tcx.hir.body(cx.tcx.hir.body_owned_by(id))
 309                     } else {
 310                         cx.tcx.sess.cstore.item_body(cx.tcx, def_id)
 311                     };
 312                     fetch_int_literal(cx, &body.value)
 313                 })
 314             } else {
 315                 None
 316             }
 317         },
 318         _ => None,
 319     }
 320 }