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<_>>();
28 declare_clippy_lint! {
30 /// Checks for iteration that may be infinite.
32 /// ### Why is this bad?
33 /// While there may be places where this is acceptable
34 /// (e.g., in event streams), in most cases this is simply an error.
36 /// ### Known problems
37 /// The code may have a condition to stop iteration, but
38 /// this lint is not clever enough to analyze it.
42 /// let infinite_iter = 0..;
43 /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
45 pub MAYBE_INFINITE_ITER,
47 "possible infinite iteration"
50 declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);
52 impl<'tcx> LateLintPass<'tcx> for InfiniteIter {
53 fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
54 let (lint, msg) = match complete_infinite_iter(cx, expr) {
55 Infinite => (INFINITE_ITER, "infinite iteration detected"),
56 MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
61 span_lint(cx, lint, expr.span, msg);
65 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
72 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
76 fn and(self, b: Self) -> Self {
78 (Finite, _) | (_, Finite) => Finite,
79 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
85 fn or(self, b: Self) -> Self {
87 (Infinite, _) | (_, Infinite) => Infinite,
88 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
94 impl From<bool> for Finiteness {
96 fn from(b: bool) -> Self {
97 if b { Infinite } else { Finite }
101 /// This tells us what to look for to know if the iterator returned by
102 /// this method is infinite
103 #[derive(Copy, Clone)]
105 /// infinite no matter what
107 /// infinite if the first argument is
109 /// infinite if any of the supplied arguments is
111 /// infinite if all of the supplied arguments are
115 use self::Heuristic::{All, Always, Any, First};
117 /// a slice of (method name, number of args, heuristic, bounds) tuples
118 /// that will be used to determine whether the method in question
119 /// returns an infinite or possibly infinite iterator. The finiteness
120 /// is an upper bound, e.g., some methods can return a possibly
121 /// infinite iterator at worst, e.g., `take_while`.
122 const HEURISTICS: [(&str, usize, Heuristic, Finiteness); 19] = [
123 ("zip", 2, All, Infinite),
124 ("chain", 2, Any, Infinite),
125 ("cycle", 1, Always, Infinite),
126 ("map", 2, First, Infinite),
127 ("by_ref", 1, First, Infinite),
128 ("cloned", 1, First, Infinite),
129 ("rev", 1, First, Infinite),
130 ("inspect", 1, First, Infinite),
131 ("enumerate", 1, First, Infinite),
132 ("peekable", 2, First, Infinite),
133 ("fuse", 1, First, Infinite),
134 ("skip", 2, First, Infinite),
135 ("skip_while", 1, First, Infinite),
136 ("filter", 2, First, Infinite),
137 ("filter_map", 2, First, Infinite),
138 ("flat_map", 2, First, Infinite),
139 ("unzip", 1, First, Infinite),
140 ("take_while", 2, First, MaybeInfinite),
141 ("scan", 3, First, MaybeInfinite),
144 fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
146 ExprKind::MethodCall(method, _, args, _) => {
147 for &(name, len, heuristic, cap) in &HEURISTICS {
148 if method.ident.name.as_str() == name && args.len() == len {
149 return (match heuristic {
151 First => is_infinite(cx, &args[0]),
152 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
153 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
158 if method.ident.name == sym!(flat_map) && args.len() == 2 {
159 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].kind {
160 let body = cx.tcx.hir().body(body_id);
161 return is_infinite(cx, &body.value);
166 ExprKind::Block(block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
167 ExprKind::Box(e) | ExprKind::AddrOf(BorrowKind::Ref, _, e) => is_infinite(cx, e),
168 ExprKind::Call(path, _) => {
169 if let ExprKind::Path(ref qpath) = path.kind {
170 is_qpath_def_path(cx, qpath, path.hir_id, &paths::ITER_REPEAT).into()
175 ExprKind::Struct(..) => higher::range(expr).map_or(false, |r| r.end.is_none()).into(),
180 /// the names and argument lengths of methods that *may* exhaust their
182 const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
191 /// the names and argument lengths of methods that *always* exhaust
193 const COMPLETING_METHODS: [(&str, usize); 12] = [
208 /// the paths of types that are known to be infinitely allocating
209 const INFINITE_COLLECTORS: &[Symbol] = &[
220 fn complete_infinite_iter(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
222 ExprKind::MethodCall(method, _, args, _) => {
223 for &(name, len) in &COMPLETING_METHODS {
224 if method.ident.name.as_str() == name && args.len() == len {
225 return is_infinite(cx, &args[0]);
228 for &(name, len) in &POSSIBLY_COMPLETING_METHODS {
229 if method.ident.name.as_str() == name && args.len() == len {
230 return MaybeInfinite.and(is_infinite(cx, &args[0]));
233 if method.ident.name == sym!(last) && args.len() == 1 {
234 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR).map_or(false, |id| {
235 !implements_trait(cx, cx.typeck_results().expr_ty(&args[0]), id, &[])
237 if not_double_ended {
238 return is_infinite(cx, &args[0]);
240 } else if method.ident.name == sym!(collect) {
241 let ty = cx.typeck_results().expr_ty(expr);
242 if INFINITE_COLLECTORS
244 .any(|diag_item| is_type_diagnostic_item(cx, ty, *diag_item))
246 return is_infinite(cx, &args[0]);
250 ExprKind::Binary(op, l, r) => {
251 if op.node.is_comparison() {
252 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite);
254 }, // TODO: ExprKind::Loop + Match