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     verbose_bit_mask_threshold: u64,
  95 }
  96
  97 impl BitMask {
  98     pub fn new(verbose_bit_mask_threshold: u64) -> Self {
  99         Self {
 100             verbose_bit_mask_threshold: verbose_bit_mask_threshold,
 101         }
 102     }
 103 }
 104
 105 impl LintPass for BitMask {
 106     fn get_lints(&self) -> LintArray {
 107         lint_array!(BAD_BIT_MASK, INEFFECTIVE_BIT_MASK, VERBOSE_BIT_MASK)
 108     }
 109 }
 110
 111 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for BitMask {
 112     fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, e: &'tcx Expr) {
 113         if let ExprBinary(ref cmp, ref left, ref right) = e.node {
 114             if cmp.node.is_comparison() {
 115                 if let Some(cmp_opt) = fetch_int_literal(cx, right) {
 116                     check_compare(cx, left, cmp.node, cmp_opt, &e.span)
 117                 } else if let Some(cmp_val) = fetch_int_literal(cx, left) {
 118                     check_compare(cx, right, invert_cmp(cmp.node), cmp_val, &e.span)
 119                 }
 120             }
 121         }
 122         if_chain! {
 123             if let Expr_::ExprBinary(ref op, ref left, ref right) = e.node;
 124             if BinOp_::BiEq == op.node;
 125             if let Expr_::ExprBinary(ref op1, ref left1, ref right1) = left.node;
 126             if BinOp_::BiBitAnd == op1.node;
 127             if let Expr_::ExprLit(ref lit) = right1.node;
 128             if let LitKind::Int(n, _) = lit.node;
 129             if let Expr_::ExprLit(ref lit1) = right.node;
 130             if let LitKind::Int(0, _) = lit1.node;
 131             if n.leading_zeros() == n.count_zeros();
 132             if n > u128::from(self.verbose_bit_mask_threshold);
 133             then {
 134                 span_lint_and_then(cx,
 135                                    VERBOSE_BIT_MASK,
 136                                    e.span,
 137                                    "bit mask could be simplified with a call to `trailing_zeros`",
 138                                    |db| {
 139                     let sugg = Sugg::hir(cx, left1, "...").maybe_par();
 140                     db.span_suggestion(e.span, "try", format!("{}.trailing_zeros() >= {}", sugg, n.count_ones()));
 141                 });
 142             }
 143         }
 144     }
 145 }
 146
 147 fn invert_cmp(cmp: BinOp_) -> BinOp_ {
 148     match cmp {
 149         BiEq => BiEq,
 150         BiNe => BiNe,
 151         BiLt => BiGt,
 152         BiGt => BiLt,
 153         BiLe => BiGe,
 154         BiGe => BiLe,
 155         _ => BiOr, // Dummy
 156     }
 157 }
 158
 159
 160 fn check_compare(cx: &LateContext, bit_op: &Expr, cmp_op: BinOp_, cmp_value: u128, span: &Span) {
 161     if let ExprBinary(ref op, ref left, ref right) = bit_op.node {
 162         if op.node != BiBitAnd && op.node != BiBitOr {
 163             return;
 164         }
 165         fetch_int_literal(cx, right)
 166             .or_else(|| fetch_int_literal(cx, left))
 167             .map_or((), |mask| check_bit_mask(cx, op.node, cmp_op, mask, cmp_value, span))
 168     }
 169 }
 170
 171 fn check_bit_mask(cx: &LateContext, bit_op: BinOp_, cmp_op: BinOp_, mask_value: u128, cmp_value: u128, span: &Span) {
 172     match cmp_op {
 173         BiEq | BiNe => match bit_op {
 174             BiBitAnd => if mask_value & cmp_value != cmp_value {
 175                 if cmp_value != 0 {
 176                     span_lint(
 177                         cx,
 178                         BAD_BIT_MASK,
 179                         *span,
 180                         &format!(
 181                             "incompatible bit mask: `_ & {}` can never be equal to `{}`",
 182                             mask_value,
 183                             cmp_value
 184                         ),
 185                     );
 186                 }
 187             } else if mask_value == 0 {
 188                 span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 189             },
 190             BiBitOr => if mask_value | cmp_value != cmp_value {
 191                 span_lint(
 192                     cx,
 193                     BAD_BIT_MASK,
 194                     *span,
 195                     &format!(
 196                         "incompatible bit mask: `_ | {}` can never be equal to `{}`",
 197                         mask_value,
 198                         cmp_value
 199                     ),
 200                 );
 201             },
 202             _ => (),
 203         },
 204         BiLt | BiGe => match bit_op {
 205             BiBitAnd => if mask_value < cmp_value {
 206                 span_lint(
 207                     cx,
 208                     BAD_BIT_MASK,
 209                     *span,
 210                     &format!(
 211                         "incompatible bit mask: `_ & {}` will always be lower than `{}`",
 212                         mask_value,
 213                         cmp_value
 214                     ),
 215                 );
 216             } else if mask_value == 0 {
 217                 span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 218             },
 219             BiBitOr => if mask_value >= cmp_value {
 220                 span_lint(
 221                     cx,
 222                     BAD_BIT_MASK,
 223                     *span,
 224                     &format!(
 225                         "incompatible bit mask: `_ | {}` will never be lower than `{}`",
 226                         mask_value,
 227                         cmp_value
 228                     ),
 229                 );
 230             } else {
 231                 check_ineffective_lt(cx, *span, mask_value, cmp_value, "|");
 232             },
 233             BiBitXor => check_ineffective_lt(cx, *span, mask_value, cmp_value, "^"),
 234             _ => (),
 235         },
 236         BiLe | BiGt => match bit_op {
 237             BiBitAnd => if mask_value <= cmp_value {
 238                 span_lint(
 239                     cx,
 240                     BAD_BIT_MASK,
 241                     *span,
 242                     &format!(
 243                         "incompatible bit mask: `_ & {}` will never be higher than `{}`",
 244                         mask_value,
 245                         cmp_value
 246                     ),
 247                 );
 248             } else if mask_value == 0 {
 249                 span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 250             },
 251             BiBitOr => if mask_value > cmp_value {
 252                 span_lint(
 253                     cx,
 254                     BAD_BIT_MASK,
 255                     *span,
 256                     &format!(
 257                         "incompatible bit mask: `_ | {}` will always be higher than `{}`",
 258                         mask_value,
 259                         cmp_value
 260                     ),
 261                 );
 262             } else {
 263                 check_ineffective_gt(cx, *span, mask_value, cmp_value, "|");
 264             },
 265             BiBitXor => check_ineffective_gt(cx, *span, mask_value, cmp_value, "^"),
 266             _ => (),
 267         },
 268         _ => (),
 269     }
 270 }
 271
 272 fn check_ineffective_lt(cx: &LateContext, span: Span, m: u128, c: u128, op: &str) {
 273     if c.is_power_of_two() && m < c {
 274         span_lint(
 275             cx,
 276             INEFFECTIVE_BIT_MASK,
 277             span,
 278             &format!(
 279                 "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 280                 op,
 281                 m,
 282                 c
 283             ),
 284         );
 285     }
 286 }
 287
 288 fn check_ineffective_gt(cx: &LateContext, span: Span, m: u128, c: u128, op: &str) {
 289     if (c + 1).is_power_of_two() && m <= c {
 290         span_lint(
 291             cx,
 292             INEFFECTIVE_BIT_MASK,
 293             span,
 294             &format!(
 295                 "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 296                 op,
 297                 m,
 298                 c
 299             ),
 300         );
 301     }
 302 }
 303
 304 fn fetch_int_literal(cx: &LateContext, lit: &Expr) -> Option<u128> {
 305     use rustc::ty::subst::Substs;
 306     match lit.node {
 307         ExprLit(ref lit_ptr) => {
 308             if let LitKind::Int(value, _) = lit_ptr.node {
 309                 Some(value) // TODO: Handle sign
 310             } else {
 311                 None
 312             }
 313         },
 314         ExprPath(ref qpath) => {
 315             let def = cx.tables.qpath_def(qpath, lit.hir_id);
 316             if let Def::Const(def_id) = def {
 317                 lookup_const_by_id(cx.tcx, cx.param_env.and((def_id, Substs::empty()))).and_then(|(l, _ty)| {
 318                     let body = if let Some(id) = cx.tcx.hir.as_local_node_id(l) {
 319                         cx.tcx.mir_const_qualif(def_id);
 320                         cx.tcx.hir.body(cx.tcx.hir.body_owned_by(id))
 321                     } else {
 322                         cx.tcx.extern_const_body(def_id).body
 323                     };
 324                     fetch_int_literal(cx, &body.value)
 325                 })
 326             } else {
 327                 None
 328             }
 329         },
 330         _ => None,
 331     }
 332 }