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             Infinite => (INFINITE_ITER, "infinite iteration detected"),
  53             MaybeInfinite => (MAYBE_INFINITE_ITER,
  54                         "possible infinite iteration detected"),
  55             Finite => { return; }
  56         };
  57         span_lint(cx, lint, expr.span, msg)
  58     }
  59 }
  60
  61 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  62 enum Finiteness {
  63     Infinite,
  64     MaybeInfinite,
  65     Finite
  66 }
  67
  68 use self::Finiteness::{Infinite, MaybeInfinite, Finite};
  69
  70 impl Finiteness {
  71     fn and(self, b: Self) -> Self {
  72         match (self, b) {
  73             (Finite, _) | (_, Finite) => Finite,
  74             (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
  75             _ => Infinite
  76         }
  77     }
  78
  79     fn or(self, b: Self) -> Self {
  80         match (self, b) {
  81             (Infinite, _) | (_, Infinite) => Infinite,
  82             (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
  83             _ => Finite
  84         }
  85     }
  86 }
  87
  88 impl From<bool> for Finiteness {
  89     fn from(b: bool) -> Self {
  90         if b { Infinite } else { Finite }
  91     }
  92 }
  93
  94 /// This tells us what to look for to know if the iterator returned by
  95 /// this method is infinite
  96 #[derive(Copy, Clone)]
  97 enum Heuristic {
  98     /// infinite no matter what
  99     Always,
 100     /// infinite if the first argument is
 101     First,
 102     /// infinite if any of the supplied arguments is
 103     Any,
 104     /// infinite if all of the supplied arguments are
 105     All
 106 }
 107
 108 use self::Heuristic::{Always, First, Any, All};
 109
 110 /// a slice of (method name, number of args, heuristic, bounds) tuples
 111 /// that will be used to determine whether the method in question
 112 /// returns an infinite or possibly infinite iterator. The finiteness
 113 /// is an upper bound, e.g. some methods can return a possibly
 114 /// infinite iterator at worst, e.g. `take_while`.
 115 static HEURISTICS : &[(&str, usize, Heuristic, Finiteness)] = &[
 116     ("zip", 2, All, Infinite),
 117     ("chain", 2, Any, Infinite),
 118     ("cycle", 1, Always, Infinite),
 119     ("map", 2, First, Infinite),
 120     ("by_ref", 1, First, Infinite),
 121     ("cloned", 1, First, Infinite),
 122     ("rev", 1, First, Infinite),
 123     ("inspect", 1, First, Infinite),
 124     ("enumerate", 1, First, Infinite),
 125     ("peekable", 2, First, Infinite),
 126     ("fuse", 1, First, Infinite),
 127     ("skip", 2, First, Infinite),
 128     ("skip_while", 1, First, Infinite),
 129     ("filter", 2, First, Infinite),
 130     ("filter_map", 2, First, Infinite),
 131     ("flat_map", 2, First, Infinite),
 132     ("unzip", 1, First, Infinite),
 133     ("take_while", 2, First, MaybeInfinite),
 134     ("scan", 3, First, MaybeInfinite)
 135 ];
 136
 137 fn is_infinite(cx: &LateContext, expr: &Expr) -> Finiteness {
 138     match expr.node {
 139         ExprMethodCall(ref method, _, ref args) => {
 140             for &(name, len, heuristic, cap) in HEURISTICS.iter() {
 141                 if method.name == name && args.len() == len {
 142                     return (match heuristic {
 143                         Always => Infinite,
 144                         First => is_infinite(cx, &args[0]),
 145                         Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
 146                         All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
 147                     }).and(cap);
 148                 }
 149             }
 150             if method.name == "flat_map" && args.len() == 2 {
 151                 if let ExprClosure(_, _, body_id, _) = args[1].node {
 152                     let body = cx.tcx.hir.body(body_id);
 153                     return is_infinite(cx, &body.value);
 154                 }
 155             }
 156             Finite
 157         },
 158         ExprBlock(ref block) =>
 159             block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
 160         ExprBox(ref e) | ExprAddrOf(_, ref e) => is_infinite(cx, e),
 161         ExprCall(ref path, _) => {
 162             if let ExprPath(ref qpath) = path.node {
 163                 match_qpath(qpath, &paths::REPEAT).into()
 164             } else { Finite }
 165         },
 166         ExprStruct(..) => {
 167             higher::range(expr).map_or(false, |r| r.end.is_none()).into()
 168         },
 169         _ => Finite
 170     }
 171 }
 172
 173 /// the names and argument lengths of methods that *may* exhaust their
 174 /// iterators
 175 static POSSIBLY_COMPLETING_METHODS : &[(&str, usize)] = &[
 176     ("find", 2),
 177     ("rfind", 2),
 178     ("position", 2),
 179     ("rposition", 2),
 180     ("any", 2),
 181     ("all", 2)
 182 ];
 183
 184 /// the names and argument lengths of methods that *always* exhaust
 185 /// their iterators
 186 static COMPLETING_METHODS : &[(&str, usize)] = &[
 187     ("count", 1),
 188     ("collect", 1),
 189     ("fold", 3),
 190     ("for_each", 2),
 191     ("partition", 2),
 192     ("max", 1),
 193     ("max_by", 2),
 194     ("max_by_key", 2),
 195     ("min", 1),
 196     ("min_by", 2),
 197     ("min_by_key", 2),
 198     ("sum", 1),
 199     ("product", 1)
 200 ];
 201
 202 fn complete_infinite_iter(cx: &LateContext, expr: &Expr) -> Finiteness {
 203     match expr.node {
 204         ExprMethodCall(ref method, _, ref args) => {
 205             for &(name, len) in COMPLETING_METHODS.iter() {
 206                 if method.name == name && args.len() == len {
 207                     return is_infinite(cx, &args[0]);
 208                 }
 209             }
 210             for &(name, len) in POSSIBLY_COMPLETING_METHODS.iter() {
 211                 if method.name == name && args.len() == len {
 212                     return MaybeInfinite.and(is_infinite(cx, &args[0]));
 213                 }
 214             }
 215             if method.name == "last" && args.len() == 1 &&
 216                     get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR).map_or(false,
 217                         |id| !implements_trait(cx,
 218                                                cx.tables.expr_ty(&args[0]),
 219                                                id,
 220                                                &[])) {
 221                 return is_infinite(cx, &args[0]);
 222             }
 223         },
 224         ExprBinary(op, ref l, ref r) => {
 225             if op.node.is_comparison() {
 226                 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite)
 227             }
 228         }, //TODO: ExprLoop + Match
 229         _ => ()
 230     }
 231     Finite
 232 }