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 => {
 162             match bit_op {
 163                 BiBitAnd => {
 164                     if mask_value & cmp_value != cmp_value {
 165                         if cmp_value != 0 {
 166                             span_lint(
 167                                 cx,
 168                                 BAD_BIT_MASK,
 169                                 *span,
 170                                 &format!(
 171                                     "incompatible bit mask: `_ & {}` can never be equal to `{}`",
 172                                     mask_value,
 173                                     cmp_value
 174                                 ),
 175                             );
 176                         }
 177                     } else if mask_value == 0 {
 178                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 179                     }
 180                 },
 181                 BiBitOr => {
 182                     if mask_value | cmp_value != cmp_value {
 183                         span_lint(
 184                             cx,
 185                             BAD_BIT_MASK,
 186                             *span,
 187                             &format!(
 188                                 "incompatible bit mask: `_ | {}` can never be equal to `{}`",
 189                                 mask_value,
 190                                 cmp_value
 191                             ),
 192                         );
 193                     }
 194                 },
 195                 _ => (),
 196             }
 197         },
 198         BiLt | BiGe => {
 199             match bit_op {
 200                 BiBitAnd => {
 201                     if mask_value < cmp_value {
 202                         span_lint(
 203                             cx,
 204                             BAD_BIT_MASK,
 205                             *span,
 206                             &format!(
 207                                 "incompatible bit mask: `_ & {}` will always be lower than `{}`",
 208                                 mask_value,
 209                                 cmp_value
 210                             ),
 211                         );
 212                     } else if mask_value == 0 {
 213                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 214                     }
 215                 },
 216                 BiBitOr => {
 217                     if mask_value >= cmp_value {
 218                         span_lint(
 219                             cx,
 220                             BAD_BIT_MASK,
 221                             *span,
 222                             &format!(
 223                                 "incompatible bit mask: `_ | {}` will never be lower than `{}`",
 224                                 mask_value,
 225                                 cmp_value
 226                             ),
 227                         );
 228                     } else {
 229                         check_ineffective_lt(cx, *span, mask_value, cmp_value, "|");
 230                     }
 231                 },
 232                 BiBitXor => check_ineffective_lt(cx, *span, mask_value, cmp_value, "^"),
 233                 _ => (),
 234             }
 235         },
 236         BiLe | BiGt => {
 237             match bit_op {
 238                 BiBitAnd => {
 239                     if mask_value <= cmp_value {
 240                         span_lint(
 241                             cx,
 242                             BAD_BIT_MASK,
 243                             *span,
 244                             &format!(
 245                                 "incompatible bit mask: `_ & {}` will never be higher than `{}`",
 246                                 mask_value,
 247                                 cmp_value
 248                             ),
 249                         );
 250                     } else if mask_value == 0 {
 251                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 252                     }
 253                 },
 254                 BiBitOr => {
 255                     if mask_value > cmp_value {
 256                         span_lint(
 257                             cx,
 258                             BAD_BIT_MASK,
 259                             *span,
 260                             &format!(
 261                                 "incompatible bit mask: `_ | {}` will always be higher than `{}`",
 262                                 mask_value,
 263                                 cmp_value
 264                             ),
 265                         );
 266                     } else {
 267                         check_ineffective_gt(cx, *span, mask_value, cmp_value, "|");
 268                     }
 269                 },
 270                 BiBitXor => check_ineffective_gt(cx, *span, mask_value, cmp_value, "^"),
 271                 _ => (),
 272             }
 273         },
 274         _ => (),
 275     }
 276 }
 277
 278 fn check_ineffective_lt(cx: &LateContext, span: Span, m: u128, c: u128, op: &str) {
 279     if c.is_power_of_two() && m < c {
 280         span_lint(
 281             cx,
 282             INEFFECTIVE_BIT_MASK,
 283             span,
 284             &format!(
 285                 "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 286                 op,
 287                 m,
 288                 c
 289             ),
 290         );
 291     }
 292 }
 293
 294 fn check_ineffective_gt(cx: &LateContext, span: Span, m: u128, c: u128, op: &str) {
 295     if (c + 1).is_power_of_two() && m <= c {
 296         span_lint(
 297             cx,
 298             INEFFECTIVE_BIT_MASK,
 299             span,
 300             &format!(
 301                 "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 302                 op,
 303                 m,
 304                 c
 305             ),
 306         );
 307     }
 308 }
 309
 310 fn fetch_int_literal(cx: &LateContext, lit: &Expr) -> Option<u128> {
 311     use rustc::ty::subst::Substs;
 312     match lit.node {
 313         ExprLit(ref lit_ptr) => {
 314             if let LitKind::Int(value, _) = lit_ptr.node {
 315                 Some(value) // TODO: Handle sign
 316             } else {
 317                 None
 318             }
 319         },
 320         ExprPath(ref qpath) => {
 321             let def = cx.tables.qpath_def(qpath, lit.hir_id);
 322             if let Def::Const(def_id) = def {
 323                 lookup_const_by_id(cx.tcx, cx.param_env.and((def_id, Substs::empty()))).and_then(|(l, _ty)| {
 324                     let body = if let Some(id) = cx.tcx.hir.as_local_node_id(l) {
 325                         cx.tcx.mir_const_qualif(def_id);
 326                         cx.tcx.hir.body(cx.tcx.hir.body_owned_by(id))
 327                     } else {
 328                         cx.tcx.sess.cstore.item_body(cx.tcx, def_id)
 329                     };
 330                     fetch_int_literal(cx, &body.value)
 331                 })
 332             } else {
 333                 None
 334             }
 335         },
 336         _ => None,
 337     }
 338 }