clippy_lints/src/infinite_iter.rs

   1 use rustc::hir::*;
   2 use rustc::lint::*;
   3 use utils::{get_trait_def_id, implements_trait, higher, match_qpath, paths, span_lint};
   4
   5 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
   6 ///
   7 /// **Why is this bad?** While there may be places where this is acceptable
   8 /// (e.g. in event streams), in most cases this is simply an error.
   9 ///
  10 /// **Known problems:** None.
  11 ///
  12 /// **Example:**
  13 /// ```rust
  14 /// repeat(1_u8).iter().collect::<Vec<_>>()
  15 /// ```
  16 declare_lint! {
  17     pub INFINITE_ITER,
  18     Warn,
  19     "infinite iteration"
  20 }
  21
  22 /// **What it does:** Checks for iteration that may be infinite.
  23 ///
  24 /// **Why is this bad?** While there may be places where this is acceptable
  25 /// (e.g. in event streams), in most cases this is simply an error.
  26 ///
  27 /// **Known problems:** The code may have a condition to stop iteration, but
  28 /// this lint is not clever enough to analyze it.
  29 ///
  30 /// **Example:**
  31 /// ```rust
  32 /// [0..].iter().zip(infinite_iter.take_while(|x| x > 5))
  33 /// ```
  34 declare_lint! {
  35     pub MAYBE_INFINITE_ITER,
  36     Allow,
  37     "possible infinite iteration"
  38 }
  39
  40 #[derive(Copy, Clone)]
  41 pub struct Pass;
  42
  43 impl LintPass for Pass {
  44     fn get_lints(&self) -> LintArray {
  45         lint_array!(INFINITE_ITER, MAYBE_INFINITE_ITER)
  46     }
  47 }
  48
  49 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
  50     fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
  51         let (lint, msg) = match complete_infinite_iter(cx, expr) {
  52             True => (INFINITE_ITER, "infinite iteration detected"),
  53             Unknown => (MAYBE_INFINITE_ITER,
  54                         "possible infinite iteration detected"),
  55             False => { return; }
  56         };
  57         span_lint(cx, lint, expr.span, msg)
  58     }
  59 }
  60
  61 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  62 enum TriState {
  63     True,
  64     Unknown,
  65     False
  66 }
  67
  68 use self::TriState::{True, Unknown, False};
  69
  70 impl TriState {
  71     fn and(self, b: Self) -> Self {
  72         match (self, b) {
  73             (False, _) | (_, False) => False,
  74             (Unknown, _) | (_, Unknown) => Unknown,
  75             _ => True
  76         }
  77     }
  78
  79     fn or(self, b: Self) -> Self {
  80         match (self, b) {
  81             (True, _) | (_, True) => True,
  82             (Unknown, _) | (_, Unknown) => Unknown,
  83             _ => False
  84         }
  85     }
  86 }
  87
  88 impl From<bool> for TriState {
  89     fn from(b: bool) -> Self {
  90         if b { True } else { False }
  91     }
  92 }
  93
  94 #[derive(Copy, Clone)]
  95 enum Heuristic {
  96     Always,
  97     First,
  98     Any,
  99     All
 100 }
 101
 102 use self::Heuristic::{Always, First, Any, All};
 103
 104 // here we use the `TriState` as (Finite, Possible Infinite, Infinite)
 105 static HEURISTICS : &[(&str, usize, Heuristic, TriState)] = &[
 106     ("zip", 2, All, True),
 107     ("chain", 2, Any, True),
 108     ("cycle", 1, Always, True),
 109     ("map", 2, First, True),
 110     ("by_ref", 1, First, True),
 111     ("cloned", 1, First, True),
 112     ("rev", 1, First, True),
 113     ("inspect", 1, First, True),
 114     ("enumerate", 1, First, True),
 115     ("peekable", 2, First, True),
 116     ("fuse", 1, First, True),
 117     ("skip", 2, First, True),
 118     ("skip_while", 1, First, True),
 119     ("filter", 2, First, True),
 120     ("filter_map", 2, First, True),
 121     ("flat_map", 2, First, True),
 122     ("unzip", 1, First, True),
 123     ("take_while", 2, First, Unknown),
 124     ("scan", 3, First, Unknown)
 125 ];
 126
 127 fn is_infinite(cx: &LateContext, expr: &Expr) -> TriState {
 128     match expr.node {
 129         ExprMethodCall(ref method, _, ref args) => {
 130             for &(name, len, heuristic, cap) in HEURISTICS.iter() {
 131                 if method.name == name && args.len() == len {
 132                     return (match heuristic {
 133                         Always => True,
 134                         First => is_infinite(cx, &args[0]),
 135                         Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
 136                         All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
 137                     }).and(cap);
 138                 }
 139             }
 140             if method.name == "flat_map" && args.len() == 2 {
 141                 if let ExprClosure(_, _, body_id, _) = args[1].node {
 142                     let body = cx.tcx.hir.body(body_id);
 143                     return is_infinite(cx, &body.value);
 144                 }
 145             }
 146             False
 147         },
 148         ExprBlock(ref block) =>
 149             block.expr.as_ref().map_or(False, |e| is_infinite(cx, e)),
 150         ExprBox(ref e) | ExprAddrOf(_, ref e) => is_infinite(cx, e),
 151         ExprCall(ref path, _) => {
 152             if let ExprPath(ref qpath) = path.node {
 153                 match_qpath(qpath, &paths::REPEAT).into()
 154             } else { False }
 155         },
 156         ExprStruct(..) => {
 157             higher::range(expr).map_or(false, |r| r.end.is_none()).into()
 158         },
 159         _ => False
 160     }
 161 }
 162
 163 static POSSIBLY_COMPLETING_METHODS : &[(&str, usize)] = &[
 164     ("find", 2),
 165     ("rfind", 2),
 166     ("position", 2),
 167     ("rposition", 2),
 168     ("any", 2),
 169     ("all", 2)
 170 ];
 171
 172 static COMPLETING_METHODS : &[(&str, usize)] = &[
 173     ("count", 1),
 174     ("collect", 1),
 175     ("fold", 3),
 176     ("for_each", 2),
 177     ("partition", 2),
 178     ("max", 1),
 179     ("max_by", 2),
 180     ("max_by_key", 2),
 181     ("min", 1),
 182     ("min_by", 2),
 183     ("min_by_key", 2),
 184     ("sum", 1),
 185     ("product", 1)
 186 ];
 187
 188 fn complete_infinite_iter(cx: &LateContext, expr: &Expr) -> TriState {
 189     match expr.node {
 190         ExprMethodCall(ref method, _, ref args) => {
 191             for &(name, len) in COMPLETING_METHODS.iter() {
 192                 if method.name == name && args.len() == len {
 193                     return is_infinite(cx, &args[0]);
 194                 }
 195             }
 196             for &(name, len) in POSSIBLY_COMPLETING_METHODS.iter() {
 197                 if method.name == name && args.len() == len {
 198                     return Unknown.and(is_infinite(cx, &args[0]));
 199                 }
 200             }
 201             if method.name == "last" && args.len() == 1 &&
 202                     get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR).map_or(false,
 203                         |id| !implements_trait(cx,
 204                                                cx.tables.expr_ty(&args[0]),
 205                                                id,
 206                                                &[])) {
 207                 return is_infinite(cx, &args[0]);
 208             }
 209         },
 210         ExprBinary(op, ref l, ref r) => {
 211             if op.node.is_comparison() {
 212                 return is_infinite(cx, l).and(is_infinite(cx, r)).and(Unknown)
 213             }
 214         }, //TODO: ExprLoop + Match
 215         _ => ()
 216     }
 217     False
 218 }