1 use clippy_utils::diagnostics::span_lint;
2 use clippy_utils::ty::{implements_trait, match_type};
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};
9 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
11 /// **Why is this bad?** While there may be places where this is acceptable
12 /// (e.g., in event streams), in most cases this is simply an error.
14 /// **Known problems:** None.
20 /// iter::repeat(1_u8).collect::<Vec<_>>();
27 declare_clippy_lint! {
28 /// **What it does:** Checks for iteration that may be infinite.
30 /// **Why is this bad?** While there may be places where this is acceptable
31 /// (e.g., in event streams), in most cases this is simply an error.
33 /// **Known problems:** The code may have a condition to stop iteration, but
34 /// this lint is not clever enough to analyze it.
38 /// let infinite_iter = 0..;
39 /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
41 pub MAYBE_INFINITE_ITER,
43 "possible infinite iteration"
46 declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);
48 impl<'tcx> LateLintPass<'tcx> for InfiniteIter {
49 fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
50 let (lint, msg) = match complete_infinite_iter(cx, expr) {
51 Infinite => (INFINITE_ITER, "infinite iteration detected"),
52 MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
57 span_lint(cx, lint, expr.span, msg);
61 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
68 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
72 fn and(self, b: Self) -> Self {
74 (Finite, _) | (_, Finite) => Finite,
75 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
81 fn or(self, b: Self) -> Self {
83 (Infinite, _) | (_, Infinite) => Infinite,
84 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
90 impl From<bool> for Finiteness {
92 fn from(b: bool) -> Self {
93 if b { Infinite } else { Finite }
97 /// This tells us what to look for to know if the iterator returned by
98 /// this method is infinite
99 #[derive(Copy, Clone)]
101 /// infinite no matter what
103 /// infinite if the first argument is
105 /// infinite if any of the supplied arguments is
107 /// infinite if all of the supplied arguments are
111 use self::Heuristic::{All, Always, Any, First};
113 /// a slice of (method name, number of args, heuristic, bounds) tuples
114 /// that will be used to determine whether the method in question
115 /// returns an infinite or possibly infinite iterator. The finiteness
116 /// is an upper bound, e.g., some methods can return a possibly
117 /// infinite iterator at worst, e.g., `take_while`.
118 const HEURISTICS: [(&str, usize, Heuristic, Finiteness); 19] = [
119 ("zip", 2, All, Infinite),
120 ("chain", 2, Any, Infinite),
121 ("cycle", 1, Always, Infinite),
122 ("map", 2, First, Infinite),
123 ("by_ref", 1, First, Infinite),
124 ("cloned", 1, First, Infinite),
125 ("rev", 1, First, Infinite),
126 ("inspect", 1, First, Infinite),
127 ("enumerate", 1, First, Infinite),
128 ("peekable", 2, First, Infinite),
129 ("fuse", 1, First, Infinite),
130 ("skip", 2, First, Infinite),
131 ("skip_while", 1, First, Infinite),
132 ("filter", 2, First, Infinite),
133 ("filter_map", 2, First, Infinite),
134 ("flat_map", 2, First, Infinite),
135 ("unzip", 1, First, Infinite),
136 ("take_while", 2, First, MaybeInfinite),
137 ("scan", 3, First, MaybeInfinite),
140 fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
142 ExprKind::MethodCall(method, _, args, _) => {
143 for &(name, len, heuristic, cap) in &HEURISTICS {
144 if method.ident.name.as_str() == name && args.len() == len {
145 return (match heuristic {
147 First => is_infinite(cx, &args[0]),
148 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
149 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
154 if method.ident.name == sym!(flat_map) && args.len() == 2 {
155 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].kind {
156 let body = cx.tcx.hir().body(body_id);
157 return is_infinite(cx, &body.value);
162 ExprKind::Block(block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
163 ExprKind::Box(e) | ExprKind::AddrOf(BorrowKind::Ref, _, e) => is_infinite(cx, e),
164 ExprKind::Call(path, _) => {
165 if let ExprKind::Path(ref qpath) = path.kind {
166 is_qpath_def_path(cx, qpath, path.hir_id, &paths::ITER_REPEAT).into()
171 ExprKind::Struct(..) => higher::range(expr).map_or(false, |r| r.end.is_none()).into(),
176 /// the names and argument lengths of methods that *may* exhaust their
178 const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
187 /// the names and argument lengths of methods that *always* exhaust
189 const COMPLETING_METHODS: [(&str, usize); 12] = [
204 /// the paths of types that are known to be infinitely allocating
205 const INFINITE_COLLECTORS: [&[&str]; 8] = [
216 fn complete_infinite_iter(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
218 ExprKind::MethodCall(method, _, args, _) => {
219 for &(name, len) in &COMPLETING_METHODS {
220 if method.ident.name.as_str() == name && args.len() == len {
221 return is_infinite(cx, &args[0]);
224 for &(name, len) in &POSSIBLY_COMPLETING_METHODS {
225 if method.ident.name.as_str() == name && args.len() == len {
226 return MaybeInfinite.and(is_infinite(cx, &args[0]));
229 if method.ident.name == sym!(last) && args.len() == 1 {
230 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR).map_or(false, |id| {
231 !implements_trait(cx, cx.typeck_results().expr_ty(&args[0]), id, &[])
233 if not_double_ended {
234 return is_infinite(cx, &args[0]);
236 } else if method.ident.name == sym!(collect) {
237 let ty = cx.typeck_results().expr_ty(expr);
238 if INFINITE_COLLECTORS.iter().any(|path| match_type(cx, ty, path)) {
239 return is_infinite(cx, &args[0]);
243 ExprKind::Binary(op, l, r) => {
244 if op.node.is_comparison() {
245 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite);
247 }, // TODO: ExprKind::Loop + Match