clippy_lints/src/infinite_iter.rs

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