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                 fetch_int_literal(cx, right).map_or_else(|| {
  95                                                              fetch_int_literal(cx, left).map_or((), |cmp_val| {
  96                                                                  check_compare(cx,
  97                                                                                right,
  98                                                                                invert_cmp(cmp.node),
  99                                                                                cmp_val,
 100                                                                                &e.span)
 101                                                              })
 102                                                          },
 103                                                          |cmp_opt| check_compare(cx, left, cmp.node, cmp_opt, &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)
 128             .or_else(|| fetch_int_literal(cx, left))
 129             .map_or((), |mask| check_bit_mask(cx, op.node, cmp_op, mask, cmp_value, span))
 130     }
 131 }
 132
 133 fn check_bit_mask(cx: &LateContext, bit_op: BinOp_, cmp_op: BinOp_, mask_value: u64, cmp_value: u64, span: &Span) {
 134     match cmp_op {
 135         BiEq | BiNe => {
 136             match bit_op {
 137                 BiBitAnd => {
 138                     if mask_value & cmp_value != cmp_value {
 139                         if cmp_value != 0 {
 140                             span_lint(cx,
 141                                       BAD_BIT_MASK,
 142                                       *span,
 143                                       &format!("incompatible bit mask: `_ & {}` can never be equal to `{}`",
 144                                                mask_value,
 145                                                cmp_value));
 146                         }
 147                     } else if mask_value == 0 {
 148                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 149                     }
 150                 }
 151                 BiBitOr => {
 152                     if mask_value | cmp_value != cmp_value {
 153                         span_lint(cx,
 154                                   BAD_BIT_MASK,
 155                                   *span,
 156                                   &format!("incompatible bit mask: `_ | {}` can never be equal to `{}`",
 157                                            mask_value,
 158                                            cmp_value));
 159                     }
 160                 }
 161                 _ => (),
 162             }
 163         }
 164         BiLt | BiGe => {
 165             match bit_op {
 166                 BiBitAnd => {
 167                     if mask_value < cmp_value {
 168                         span_lint(cx,
 169                                   BAD_BIT_MASK,
 170                                   *span,
 171                                   &format!("incompatible bit mask: `_ & {}` will always be lower than `{}`",
 172                                            mask_value,
 173                                            cmp_value));
 174                     } else if mask_value == 0 {
 175                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 176                     }
 177                 }
 178                 BiBitOr => {
 179                     if mask_value >= cmp_value {
 180                         span_lint(cx,
 181                                   BAD_BIT_MASK,
 182                                   *span,
 183                                   &format!("incompatible bit mask: `_ | {}` will never be lower than `{}`",
 184                                            mask_value,
 185                                            cmp_value));
 186                     } else {
 187                         check_ineffective_lt(cx, *span, mask_value, cmp_value, "|");
 188                     }
 189                 }
 190                 BiBitXor => check_ineffective_lt(cx, *span, mask_value, cmp_value, "^"),
 191                 _ => (),
 192             }
 193         }
 194         BiLe | BiGt => {
 195             match bit_op {
 196                 BiBitAnd => {
 197                     if mask_value <= cmp_value {
 198                         span_lint(cx,
 199                                   BAD_BIT_MASK,
 200                                   *span,
 201                                   &format!("incompatible bit mask: `_ & {}` will never be higher than `{}`",
 202                                            mask_value,
 203                                            cmp_value));
 204                     } else if mask_value == 0 {
 205                         span_lint(cx, BAD_BIT_MASK, *span, "&-masking with zero");
 206                     }
 207                 }
 208                 BiBitOr => {
 209                     if mask_value > cmp_value {
 210                         span_lint(cx,
 211                                   BAD_BIT_MASK,
 212                                   *span,
 213                                   &format!("incompatible bit mask: `_ | {}` will always be higher than `{}`",
 214                                            mask_value,
 215                                            cmp_value));
 216                     } else {
 217                         check_ineffective_gt(cx, *span, mask_value, cmp_value, "|");
 218                     }
 219                 }
 220                 BiBitXor => check_ineffective_gt(cx, *span, mask_value, cmp_value, "^"),
 221                 _ => (),
 222             }
 223         }
 224         _ => (),
 225     }
 226 }
 227
 228 fn check_ineffective_lt(cx: &LateContext, span: Span, m: u64, c: u64, op: &str) {
 229     if c.is_power_of_two() && m < c {
 230         span_lint(cx,
 231                   INEFFECTIVE_BIT_MASK,
 232                   span,
 233                   &format!("ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 234                            op,
 235                            m,
 236                            c));
 237     }
 238 }
 239
 240 fn check_ineffective_gt(cx: &LateContext, span: Span, m: u64, c: u64, op: &str) {
 241     if (c + 1).is_power_of_two() && m <= c {
 242         span_lint(cx,
 243                   INEFFECTIVE_BIT_MASK,
 244                   span,
 245                   &format!("ineffective bit mask: `x {} {}` compared to `{}`, is the same as x compared directly",
 246                            op,
 247                            m,
 248                            c));
 249     }
 250 }
 251
 252 fn fetch_int_literal(cx: &LateContext, lit: &Expr) -> Option<u64> {
 253     match lit.node {
 254         ExprLit(ref lit_ptr) => {
 255             if let LitKind::Int(value, _) = lit_ptr.node {
 256                 Some(value) //TODO: Handle sign
 257             } else {
 258                 None
 259             }
 260         }
 261         ExprPath(_, _) => {
 262             {
 263                 // Important to let the borrow expire before the const lookup to avoid double
 264                 // borrowing.
 265                 let def_map = cx.tcx.def_map.borrow();
 266                 match def_map.get(&lit.id) {
 267                     Some(&PathResolution { base_def: Def::Const(def_id), .. }) => Some(def_id),
 268                     _ => None,
 269                 }
 270             }
 271             .and_then(|def_id| lookup_const_by_id(cx.tcx, def_id, None))
 272             .and_then(|(l, _ty)| fetch_int_literal(cx, l))
 273         }
 274         _ => None,
 275     }
 276 }