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