clippy_lints/src/infinite_iter.rs

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