clippy_lints/src/infinite_iter.rs

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