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

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