1 use clippy_utils::diagnostics::span_lint;
2 use clippy_utils::ty::{implements_trait, is_type_diagnostic_item};
3 use clippy_utils::{higher, match_def_path, path_def_id, 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};
11 /// Checks for iteration that is guaranteed to be infinite.
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.
21 /// iter::repeat(1_u8).collect::<Vec<_>>();
23 #[clippy::version = "pre 1.29.0"]
29 declare_clippy_lint! {
31 /// Checks for iteration that may be infinite.
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.
37 /// ### Known problems
38 /// The code may have a condition to stop iteration, but
39 /// this lint is not clever enough to analyze it.
43 /// let infinite_iter = 0..;
45 /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
47 #[clippy::version = "pre 1.29.0"]
48 pub MAYBE_INFINITE_ITER,
50 "possible infinite iteration"
53 declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);
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"),
64 span_lint(cx, lint, expr.span, msg);
68 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
75 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
79 fn and(self, b: Self) -> Self {
81 (Finite, _) | (_, Finite) => Finite,
82 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
88 fn or(self, b: Self) -> Self {
90 (Infinite, _) | (_, Infinite) => Infinite,
91 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
97 impl From<bool> for Finiteness {
99 fn from(b: bool) -> Self {
100 if b { Infinite } else { Finite }
104 /// This tells us what to look for to know if the iterator returned by
105 /// this method is infinite
106 #[derive(Copy, Clone)]
108 /// infinite no matter what
110 /// infinite if the first argument is
112 /// infinite if any of the supplied arguments is
114 /// infinite if all of the supplied arguments are
118 use self::Heuristic::{All, Always, Any, First};
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", 2, All, Infinite),
127 ("chain", 2, Any, Infinite),
128 ("cycle", 1, Always, Infinite),
129 ("map", 2, First, Infinite),
130 ("by_ref", 1, First, Infinite),
131 ("cloned", 1, First, Infinite),
132 ("rev", 1, First, Infinite),
133 ("inspect", 1, First, Infinite),
134 ("enumerate", 1, First, Infinite),
135 ("peekable", 2, First, Infinite),
136 ("fuse", 1, First, Infinite),
137 ("skip", 2, First, Infinite),
138 ("skip_while", 1, First, Infinite),
139 ("filter", 2, First, Infinite),
140 ("filter_map", 2, First, Infinite),
141 ("flat_map", 2, First, Infinite),
142 ("unzip", 1, First, Infinite),
143 ("take_while", 2, First, MaybeInfinite),
144 ("scan", 3, First, MaybeInfinite),
147 fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
149 ExprKind::MethodCall(method, args, _) => {
150 for &(name, len, heuristic, cap) in &HEURISTICS {
151 if method.ident.name.as_str() == name && args.len() == len {
152 return (match heuristic {
154 First => is_infinite(cx, &args[0]),
155 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
156 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
161 if method.ident.name == sym!(flat_map) && args.len() == 2 {
162 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].kind {
163 let body = cx.tcx.hir().body(body_id);
164 return is_infinite(cx, &body.value);
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, _) => path_def_id(cx, path)
172 .map_or(false, |id| match_def_path(cx, id, &paths::ITER_REPEAT))
174 ExprKind::Struct(..) => higher::Range::hir(expr).map_or(false, |r| r.end.is_none()).into(),
179 /// the names and argument lengths of methods that *may* exhaust their
181 const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
190 /// the names and argument lengths of methods that *always* exhaust
192 const COMPLETING_METHODS: [(&str, usize); 12] = [
207 /// the paths of types that are known to be infinitely allocating
208 const INFINITE_COLLECTORS: &[Symbol] = &[
219 fn complete_infinite_iter(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
221 ExprKind::MethodCall(method, args, _) => {
222 for &(name, len) in &COMPLETING_METHODS {
223 if method.ident.name.as_str() == name && args.len() == len {
224 return is_infinite(cx, &args[0]);
227 for &(name, len) in &POSSIBLY_COMPLETING_METHODS {
228 if method.ident.name.as_str() == name && args.len() == len {
229 return MaybeInfinite.and(is_infinite(cx, &args[0]));
232 if method.ident.name == sym!(last) && args.len() == 1 {
233 let not_double_ended = cx
235 .get_diagnostic_item(sym::DoubleEndedIterator)
236 .map_or(false, |id| {
237 !implements_trait(cx, cx.typeck_results().expr_ty(&args[0]), id, &[])
239 if not_double_ended {
240 return is_infinite(cx, &args[0]);
242 } else if method.ident.name == sym!(collect) {
243 let ty = cx.typeck_results().expr_ty(expr);
244 if INFINITE_COLLECTORS
246 .any(|diag_item| is_type_diagnostic_item(cx, ty, *diag_item))
248 return is_infinite(cx, &args[0]);
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);
256 }, // TODO: ExprKind::Loop + Match