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};
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 /// # #[allow(unused)]
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", 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),
147 fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
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 {
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])),
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);
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)
175 .map_or(false, |id| cx.tcx.is_diagnostic_item(sym::iter_repeat, id))
181 ExprKind::Struct(..) => higher::Range::hir(expr).map_or(false, |r| r.end.is_none()).into(),
186 /// the names and argument lengths of methods that *may* exhaust their
188 const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
197 /// the names and argument lengths of methods that *always* exhaust
199 const COMPLETING_METHODS: [(&str, usize); 12] = [
214 /// the paths of types that are known to be infinitely allocating
215 const INFINITE_COLLECTORS: &[Symbol] = &[
226 fn complete_infinite_iter(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
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);
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));
239 if method.ident.name == sym!(last) && args.is_empty() {
240 let not_double_ended = cx
242 .get_diagnostic_item(sym::DoubleEndedIterator)
243 .map_or(false, |id| {
244 !implements_trait(cx, cx.typeck_results().expr_ty(receiver), id, &[])
246 if not_double_ended {
247 return is_infinite(cx, receiver);
249 } else if method.ident.name == sym!(collect) {
250 let ty = cx.typeck_results().expr_ty(expr);
251 if INFINITE_COLLECTORS
253 .any(|diag_item| is_type_diagnostic_item(cx, ty, *diag_item))
255 return is_infinite(cx, receiver);
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);
263 }, // TODO: ExprKind::Loop + Match