clippy_lints/src/infinite_iter.rs

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