src/bit_mask.rs

   1 use rustc::lint::*;
   2 use rustc::middle::const_eval::lookup_const_by_id;
   3 use rustc::middle::def::*;
   4 use rustc_front::hir::*;
   5 use rustc_front::util::is_comparison_binop;
   6 use syntax::codemap::Span;
   7 use syntax::ast::Lit_::*;
   8
   9 use utils::span_lint;
  10
  11 /// **What it does:** This lint checks for incompatible bit masks in comparisons. It is `Warn` by default.
  12 ///
  13 /// The formula for detecting if an expression of the type  `_ <bit_op> m <cmp_op> c` (where `<bit_op>`
  14 /// is one of {`&`, '|'} and `<cmp_op>` is one of {`!=`, `>=`, `>`, `!=`, `>=`, `>`}) can be determined from the following 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 set to zero or one by the bit mask, the comparison is constant `true` or `false` (depending on mask, compared value, and operators).
  26 ///
  27 /// 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.
  28 ///
  29 /// **Known problems:** None
  30 ///
  31 /// **Example:** `x & 1 == 2` (also see table above)
  32 declare_lint! {
  33     pub BAD_BIT_MASK,
  34     Warn,
  35     "expressions of the form `_ & mask == select` that will only ever return `true` or `false` \
  36      (because in the example `select` containing bits that `mask` doesn't have)"
  37 }
  38
  39 /// **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:
  40 ///
  41 /// |Comparison|Bit-Op   |Example    |equals |
  42 /// |----------|---------|-----------|-------|
  43 /// |`>` / `<=`|`|` / `^`|`x | 2 > 3`|`x > 3`|
  44 /// |`<` / `>=`|`|` / `^`|`x ^ 1 < 4`|`x < 4`|
  45 ///
  46 /// This lint is `Warn` by default.
  47 ///
  48 /// **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.
  49 ///
  50 /// **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).
  51 ///
  52 /// **Example:** `x | 1 > 3` (also see table above)
  53 declare_lint! {
  54     pub INEFFECTIVE_BIT_MASK,
  55     Warn,
  56     "expressions where a bit mask will be rendered useless by a comparison, e.g. `(x | 1) > 2`"
  57 }
  58
  59 /// Checks for incompatible bit masks in comparisons, e.g. `x & 1 == 2`.
  60 /// This cannot work because the bit that makes up the value two was
  61 /// zeroed out by the bit-and with 1. So the formula for detecting if an
  62 /// expression of the type  `_ <bit_op> m <cmp_op> c` (where `<bit_op>`
  63 /// is one of {`&`, '|'} and `<cmp_op>` is one of {`!=`, `>=`, `>` ,
  64 /// `!=`, `>=`, `>`}) can be determined from the following table:
  65 ///
  66 /// |Comparison  |Bit-Op|Example     |is always|Formula               |
  67 /// |------------|------|------------|---------|----------------------|
  68 /// |`==` or `!=`| `&`  |`x & 2 == 3`|`false`  |`c & m != c`          |
  69 /// |`<`  or `>=`| `&`  |`x & 2 < 3` |`true`   |`m < c`               |
  70 /// |`>`  or `<=`| `&`  |`x & 1 > 1` |`false`  |`m <= c`              |
  71 /// |`==` or `!=`| `|`  |`x | 1 == 0`|`false`  |`c | m != c`          |
  72 /// |`<`  or `>=`| `|`  |`x | 1 < 1` |`false`  |`m >= c`              |
  73 /// |`<=` or `>` | `|`  |`x | 1 > 0` |`true`   |`m > c`               |
  74 ///
  75 /// This lint is **deny** by default
  76 ///
  77 /// There is also a lint that warns on ineffective masks that is *warn*
  78 /// by default.
  79 ///
  80 /// |Comparison|Bit-Op   |Example    |equals |Formula|
  81 /// |`>` / `<=`|`|` / `^`|`x | 2 > 3`|`x > 3`|`¹ && m <= c`|
  82 /// |`<` / `>=`|`|` / `^`|`x ^ 1 < 4`|`x < 4`|`¹ && m < c` |
  83 ///
  84 /// `¹ power_of_two(c + 1)`
  85 #[derive(Copy,Clone)]
  86 pub struct BitMask;
  87
  88 impl LintPass for BitMask {
  89     fn get_lints(&self) -> LintArray {
  90         lint_array!(BAD_BIT_MASK, INEFFECTIVE_BIT_MASK)
  91     }
  92 }
  93
  94 impl LateLintPass for BitMask {
  95     fn check_expr(&mut self, cx: &LateContext, e: &Expr) {
  96         if let ExprBinary(ref cmp, ref left, ref right) = e.node {
  97             if is_comparison_binop(cmp.node) {
  98                 fetch_int_literal(cx, right).map_or_else(||
  99                     fetch_int_literal(cx, left).map_or((), |cmp_val|
 100                         check_compare(cx, right, invert_cmp(cmp.node),
 101                                       cmp_val, &e.span)),
 102                     |cmp_opt| check_compare(cx, left, cmp.node, cmp_opt,
 103                                             &e.span))
 104             }
 105         }
 106     }
 107 }
 108
 109 fn invert_cmp(cmp : BinOp_) -> BinOp_ {
 110     match cmp {
 111         BiEq => BiEq,
 112         BiNe => BiNe,
 113         BiLt => BiGt,
 114         BiGt => BiLt,
 115         BiLe => BiGe,
 116         BiGe => BiLe,
 117         _ => BiOr // Dummy
 118     }
 119 }
 120
 121
 122 fn check_compare(cx: &LateContext, bit_op: &Expr, cmp_op: BinOp_, cmp_value: u64, span: &Span) {
 123     if let ExprBinary(ref op, ref left, ref right) = bit_op.node {
 124         if op.node != BiBitAnd && op.node != BiBitOr {
 125             return;
 126         }
 127         fetch_int_literal(cx, right).or_else(|| fetch_int_literal(
 128             cx, left)).map_or((), |mask| check_bit_mask(cx, op.node,
 129                                                         cmp_op, mask, cmp_value, span))
 130     }
 131 }
 132
 133 fn check_bit_mask(cx: &LateContext, bit_op: BinOp_, cmp_op: BinOp_,
 134                   mask_value: u64, cmp_value: u64, span: &Span) {
 135     match cmp_op {
 136         BiEq | BiNe => match bit_op {
 137             BiBitAnd => if mask_value & cmp_value != cmp_value {
 138                 if cmp_value != 0 {
 139                     span_lint(cx, BAD_BIT_MASK, *span, &format!(
 140                         "incompatible bit mask: `_ & {}` can never be equal to `{}`",
 141                         mask_value, cmp_value));
 142                 }
 143             } else {
 144                 if mask_value == 0 {
 145                     span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 146                 }
 147             },
 148             BiBitOr => if mask_value | cmp_value != cmp_value {
 149                 span_lint(cx, BAD_BIT_MASK, *span, &format!(
 150                     "incompatible bit mask: `_ | {}` can never be equal to `{}`",
 151                     mask_value, cmp_value));
 152             },
 153             _ => ()
 154         },
 155         BiLt | BiGe => match bit_op {
 156             BiBitAnd => if mask_value < cmp_value {
 157                 span_lint(cx, BAD_BIT_MASK, *span, &format!(
 158                     "incompatible bit mask: `_ & {}` will always be lower than `{}`",
 159                     mask_value, cmp_value));
 160             } else {
 161                 if mask_value == 0 {
 162                     span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 163                 }
 164             },
 165             BiBitOr => if mask_value >= cmp_value {
 166                 span_lint(cx, BAD_BIT_MASK, *span, &format!(
 167                     "incompatible bit mask: `_ | {}` will never be lower than `{}`",
 168                     mask_value, cmp_value));
 169             } else {
 170                 check_ineffective_lt(cx, *span, mask_value, cmp_value, "|");
 171             },
 172             BiBitXor =>
 173                 check_ineffective_lt(cx, *span, mask_value, cmp_value, "^"),
 174             _ => ()
 175         },
 176         BiLe | BiGt => match bit_op {
 177             BiBitAnd => if mask_value <= cmp_value {
 178                 span_lint(cx, BAD_BIT_MASK, *span, &format!(
 179                     "incompatible bit mask: `_ & {}` will never be higher than `{}`",
 180                     mask_value, cmp_value));
 181             } else {
 182                 if mask_value == 0 {
 183                     span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 184                 }
 185             },
 186             BiBitOr => if mask_value > cmp_value {
 187                 span_lint(cx, BAD_BIT_MASK, *span, &format!(
 188                     "incompatible bit mask: `_ | {}` will always be higher than `{}`",
 189                     mask_value, cmp_value));
 190             } else {
 191                 check_ineffective_gt(cx, *span, mask_value, cmp_value, "|");
 192             },
 193             BiBitXor =>
 194                 check_ineffective_gt(cx, *span, mask_value, cmp_value, "^"),
 195             _ => ()
 196         },
 197         _ => ()
 198     }
 199 }
 200
 201 fn check_ineffective_lt(cx: &LateContext, span: Span, m: u64, c: u64, op: &str) {
 202     if c.is_power_of_two() && m < c {
 203         span_lint(cx, INEFFECTIVE_BIT_MASK, span, &format!(
 204             "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 205             op, m, c));
 206     }
 207 }
 208
 209 fn check_ineffective_gt(cx: &LateContext, span: Span, m: u64, c: u64, op: &str) {
 210     if (c + 1).is_power_of_two() && m <= c {
 211         span_lint(cx, INEFFECTIVE_BIT_MASK, span, &format!(
 212             "ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 213             op, m, c));
 214     }
 215 }
 216
 217 fn fetch_int_literal(cx: &LateContext, lit : &Expr) -> Option<u64> {
 218     match lit.node {
 219         ExprLit(ref lit_ptr) => {
 220             if let LitInt(value, _) = lit_ptr.node {
 221                 Some(value) //TODO: Handle sign
 222             } else { None }
 223         }
 224         ExprPath(_, _) => {
 225             // Important to let the borrow expire before the const lookup to avoid double
 226             // borrowing.
 227             let def_map = cx.tcx.def_map.borrow();
 228             match def_map.get(&lit.id) {
 229                 Some(&PathResolution { base_def: DefConst(def_id), ..}) => Some(def_id),
 230                 _ => None
 231             }
 232         }
 233         .and_then(|def_id| lookup_const_by_id(cx.tcx, def_id, None))
 234         .and_then(|l| fetch_int_literal(cx, l)),
 235         _ => None
 236     }
 237 }