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};
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..;
44 /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
46 #[clippy::version = "pre 1.29.0"]
47 pub MAYBE_INFINITE_ITER,
49 "possible infinite iteration"
52 declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);
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"),
63 span_lint(cx, lint, expr.span, msg);
67 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
74 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
78 fn and(self, b: Self) -> Self {
80 (Finite, _) | (_, Finite) => Finite,
81 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
87 fn or(self, b: Self) -> Self {
89 (Infinite, _) | (_, Infinite) => Infinite,
90 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
96 impl From<bool> for Finiteness {
98 fn from(b: bool) -> Self {
99 if b { Infinite } else { Finite }
103 /// This tells us what to look for to know if the iterator returned by
104 /// this method is infinite
105 #[derive(Copy, Clone)]
107 /// infinite no matter what
109 /// infinite if the first argument is
111 /// infinite if any of the supplied arguments is
113 /// infinite if all of the supplied arguments are
117 use self::Heuristic::{All, Always, Any, First};
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),
146 fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
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 {
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])),
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);
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()
177 ExprKind::Struct(..) => higher::Range::hir(expr).map_or(false, |r| r.end.is_none()).into(),
182 /// the names and argument lengths of methods that *may* exhaust their
184 const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
193 /// the names and argument lengths of methods that *always* exhaust
195 const COMPLETING_METHODS: [(&str, usize); 12] = [
210 /// the paths of types that are known to be infinitely allocating
211 const INFINITE_COLLECTORS: &[Symbol] = &[
222 fn complete_infinite_iter(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
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]);
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]));
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, &[])
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