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