clippy_lints/src/bit_mask.rs

   1 use rustc::hir::*;
   2 use rustc::hir::def::{Def, PathResolution};
   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;
   8
   9 /// **What it does:** This lint checks for incompatible bit masks in comparisons.
  10 ///
  11 /// The formula for detecting if an expression of the type  `_ <bit_op> m <cmp_op> c` (where `<bit_op>`
  12 /// is one of {`&`, `|`} and `<cmp_op>` is one of {`!=`, `>=`, `>`, `!=`, `>=`, `>`}) can be determined from the following table:
  13 ///
  14 /// |Comparison  |Bit Op|Example     |is always|Formula               |
  15 /// |------------|------|------------|---------|----------------------|
  16 /// |`==` or `!=`| `&`  |`x & 2 == 3`|`false`  |`c & m != c`          |
  17 /// |`<`  or `>=`| `&`  |`x & 2 < 3` |`true`   |`m < c`               |
  18 /// |`>`  or `<=`| `&`  |`x & 1 > 1` |`false`  |`m <= c`              |
  19 /// |`==` or `!=`| `|`  |`x | 1 == 0`|`false`  |`c | m != c`          |
  20 /// |`<`  or `>=`| `|`  |`x | 1 < 1` |`false`  |`m >= c`              |
  21 /// |`<=` or `>` | `|`  |`x | 1 > 0` |`true`   |`m > c`               |
  22 ///
  23 /// **Why is this bad?** If the bits that the comparison cares about are always set to zero or one by the bit mask, the comparison is constant `true` or `false` (depending on mask, compared value, and operators).
  24 ///
  25 /// So the code is actively misleading, and the only reason someone would write this intentionally is to win an underhanded Rust contest or create a test-case for this lint.
  26 ///
  27 /// **Known problems:** None
  28 ///
  29 /// **Example:**
  30 /// ```rust
  31 /// if (x & 1 == 2) { … }
  32 /// ```
  33 declare_lint! {
  34     pub BAD_BIT_MASK,
  35     Warn,
  36     "expressions of the form `_ & mask == select` that will only ever return `true` or `false` \
  37      (because in the example `select` containing bits that `mask` doesn't have)"
  38 }
  39
  40 /// **What it does:** This lint checks for bit masks in comparisons which can be removed without changing the outcome. The basic structure can be seen in the following table:
  41 ///
  42 /// |Comparison| Bit Op  |Example    |equals |
  43 /// |----------|---------|-----------|-------|
  44 /// |`>` / `<=`|`|` / `^`|`x | 2 > 3`|`x > 3`|
  45 /// |`<` / `>=`|`|` / `^`|`x ^ 1 < 4`|`x < 4`|
  46 ///
  47 /// **Why is this bad?** Not equally evil as [`bad_bit_mask`](#bad_bit_mask), but still a bit misleading, because the bit mask is ineffective.
  48 ///
  49 /// **Known problems:** False negatives: This lint will only match instances where we have figured out the math (which is for a power-of-two compared value). This means things like `x | 1 >= 7` (which would be better written as `x >= 6`) will not be reported (but bit masks like this are fairly uncommon).
  50 ///
  51 /// **Example:**
  52 /// ```rust
  53 /// if (x | 1 > 3) { … }
  54 /// ```
  55 declare_lint! {
  56     pub INEFFECTIVE_BIT_MASK,
  57     Warn,
  58     "expressions where a bit mask will be rendered useless by a comparison, e.g. `(x | 1) > 2`"
  59 }
  60
  61 /// Checks for incompatible bit masks in comparisons, e.g. `x & 1 == 2`.
  62 /// This cannot work because the bit that makes up the value two was
  63 /// zeroed out by the bit-and with 1. So the formula for detecting if an
  64 /// expression of the type  `_ <bit_op> m <cmp_op> c` (where `<bit_op>`
  65 /// is one of {`&`, '|'} and `<cmp_op>` is one of {`!=`, `>=`, `>` ,
  66 /// `!=`, `>=`, `>`}) can be determined from the following table:
  67 ///
  68 /// |Comparison  |Bit Op|Example     |is always|Formula               |
  69 /// |------------|------|------------|---------|----------------------|
  70 /// |`==` or `!=`| `&`  |`x & 2 == 3`|`false`  |`c & m != c`          |
  71 /// |`<`  or `>=`| `&`  |`x & 2 < 3` |`true`   |`m < c`               |
  72 /// |`>`  or `<=`| `&`  |`x & 1 > 1` |`false`  |`m <= c`              |
  73 /// |`==` or `!=`| `|`  |`x | 1 == 0`|`false`  |`c | m != c`          |
  74 /// |`<`  or `>=`| `|`  |`x | 1 < 1` |`false`  |`m >= c`              |
  75 /// |`<=` or `>` | `|`  |`x | 1 > 0` |`true`   |`m > c`               |
  76 ///
  77 /// This lint is **deny** by default
  78 ///
  79 /// There is also a lint that warns on ineffective masks that is *warn*
  80 /// by default.
  81 ///
  82 /// |Comparison|Bit Op   |Example    |equals |Formula|
  83 /// |`>` / `<=`|`|` / `^`|`x | 2 > 3`|`x > 3`|`¹ && m <= c`|
  84 /// |`<` / `>=`|`|` / `^`|`x ^ 1 < 4`|`x < 4`|`¹ && m < c` |
  85 ///
  86 /// `¹ power_of_two(c + 1)`
  87 #[derive(Copy,Clone)]
  88 pub struct BitMask;
  89
  90 impl LintPass for BitMask {
  91     fn get_lints(&self) -> LintArray {
  92         lint_array!(BAD_BIT_MASK, INEFFECTIVE_BIT_MASK)
  93     }
  94 }
  95
  96 impl LateLintPass for BitMask {
  97     fn check_expr(&mut self, cx: &LateContext, e: &Expr) {
  98         if let ExprBinary(ref cmp, ref left, ref right) = e.node {
  99             if cmp.node.is_comparison() {
 100                 if let Some(cmp_opt) = fetch_int_literal(cx, right) {
 101                     check_compare(cx, left, cmp.node, cmp_opt, &e.span)
 102                 } else if let Some(cmp_val) = fetch_int_literal(cx, left) {
 103                     check_compare(cx, right, invert_cmp(cmp.node), cmp_val, &e.span)
 104                 }
 105             }
 106         }
 107     }
 108 }
 109
 110 fn invert_cmp(cmp: BinOp_) -> BinOp_ {
 111     match cmp {
 112         BiEq => BiEq,
 113         BiNe => BiNe,
 114         BiLt => BiGt,
 115         BiGt => BiLt,
 116         BiLe => BiGe,
 117         BiGe => BiLe,
 118         _ => BiOr, // Dummy
 119     }
 120 }
 121
 122
 123 fn check_compare(cx: &LateContext, bit_op: &Expr, cmp_op: BinOp_, cmp_value: u64, span: &Span) {
 124     if let ExprBinary(ref op, ref left, ref right) = bit_op.node {
 125         if op.node != BiBitAnd && op.node != BiBitOr {
 126             return;
 127         }
 128         fetch_int_literal(cx, right)
 129             .or_else(|| fetch_int_literal(cx, left))
 130             .map_or((), |mask| check_bit_mask(cx, op.node, cmp_op, mask, cmp_value, span))
 131     }
 132 }
 133
 134 fn check_bit_mask(cx: &LateContext, bit_op: BinOp_, cmp_op: BinOp_, mask_value: u64, cmp_value: u64, span: &Span) {
 135     match cmp_op {
 136         BiEq | BiNe => {
 137             match bit_op {
 138                 BiBitAnd => {
 139                     if mask_value & cmp_value != cmp_value {
 140                         if cmp_value != 0 {
 141                             span_lint(cx,
 142                                       BAD_BIT_MASK,
 143                                       *span,
 144                                       &format!("incompatible bit mask: `_ & {}` can never be equal to `{}`",
 145                                                mask_value,
 146                                                cmp_value));
 147                         }
 148                     } else if mask_value == 0 {
 149                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 150                     }
 151                 }
 152                 BiBitOr => {
 153                     if mask_value | cmp_value != cmp_value {
 154                         span_lint(cx,
 155                                   BAD_BIT_MASK,
 156                                   *span,
 157                                   &format!("incompatible bit mask: `_ | {}` can never be equal to `{}`",
 158                                            mask_value,
 159                                            cmp_value));
 160                     }
 161                 }
 162                 _ => (),
 163             }
 164         }
 165         BiLt | BiGe => {
 166             match bit_op {
 167                 BiBitAnd => {
 168                     if mask_value < cmp_value {
 169                         span_lint(cx,
 170                                   BAD_BIT_MASK,
 171                                   *span,
 172                                   &format!("incompatible bit mask: `_ & {}` will always be lower than `{}`",
 173                                            mask_value,
 174                                            cmp_value));
 175                     } else if mask_value == 0 {
 176                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 177                     }
 178                 }
 179                 BiBitOr => {
 180                     if mask_value >= cmp_value {
 181                         span_lint(cx,
 182                                   BAD_BIT_MASK,
 183                                   *span,
 184                                   &format!("incompatible bit mask: `_ | {}` will never be lower than `{}`",
 185                                            mask_value,
 186                                            cmp_value));
 187                     } else {
 188                         check_ineffective_lt(cx, *span, mask_value, cmp_value, "|");
 189                     }
 190                 }
 191                 BiBitXor => check_ineffective_lt(cx, *span, mask_value, cmp_value, "^"),
 192                 _ => (),
 193             }
 194         }
 195         BiLe | BiGt => {
 196             match bit_op {
 197                 BiBitAnd => {
 198                     if mask_value <= cmp_value {
 199                         span_lint(cx,
 200                                   BAD_BIT_MASK,
 201                                   *span,
 202                                   &format!("incompatible bit mask: `_ & {}` will never be higher than `{}`",
 203                                            mask_value,
 204                                            cmp_value));
 205                     } else if mask_value == 0 {
 206                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 207                     }
 208                 }
 209                 BiBitOr => {
 210                     if mask_value > cmp_value {
 211                         span_lint(cx,
 212                                   BAD_BIT_MASK,
 213                                   *span,
 214                                   &format!("incompatible bit mask: `_ | {}` will always be higher than `{}`",
 215                                            mask_value,
 216                                            cmp_value));
 217                     } else {
 218                         check_ineffective_gt(cx, *span, mask_value, cmp_value, "|");
 219                     }
 220                 }
 221                 BiBitXor => check_ineffective_gt(cx, *span, mask_value, cmp_value, "^"),
 222                 _ => (),
 223             }
 224         }
 225         _ => (),
 226     }
 227 }
 228
 229 fn check_ineffective_lt(cx: &LateContext, span: Span, m: u64, c: u64, op: &str) {
 230     if c.is_power_of_two() && m < c {
 231         span_lint(cx,
 232                   INEFFECTIVE_BIT_MASK,
 233                   span,
 234                   &format!("ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 235                            op,
 236                            m,
 237                            c));
 238     }
 239 }
 240
 241 fn check_ineffective_gt(cx: &LateContext, span: Span, m: u64, c: u64, op: &str) {
 242     if (c + 1).is_power_of_two() && m <= c {
 243         span_lint(cx,
 244                   INEFFECTIVE_BIT_MASK,
 245                   span,
 246                   &format!("ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 247                            op,
 248                            m,
 249                            c));
 250     }
 251 }
 252
 253 fn fetch_int_literal(cx: &LateContext, lit: &Expr) -> Option<u64> {
 254     match lit.node {
 255         ExprLit(ref lit_ptr) => {
 256             if let LitKind::Int(value, _) = lit_ptr.node {
 257                 Some(value) //TODO: Handle sign
 258             } else {
 259                 None
 260             }
 261         }
 262         ExprPath(_, _) => {
 263             {
 264                 // Important to let the borrow expire before the const lookup to avoid double
 265                 // borrowing.
 266                 let def_map = cx.tcx.def_map.borrow();
 267                 match def_map.get(&lit.id) {
 268                     Some(&PathResolution { base_def: Def::Const(def_id), .. }) => Some(def_id),
 269                     _ => None,
 270                 }
 271             }
 272             .and_then(|def_id| lookup_const_by_id(cx.tcx, def_id, None))
 273             .and_then(|(l, _ty)| fetch_int_literal(cx, l))
 274         }
 275         _ => None,
 276     }
 277 }