src/tools/clippy/clippy_lints/src/infinite_iter.rs

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