clippy_lints/src/bit_mask.rs

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