clippy_lints/src/infinite_iter.rs

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