1 use rustc_hir::{BorrowKind, Expr, ExprKind};
2 use rustc_lint::{LateContext, LateLintPass};
3 use rustc_session::{declare_lint_pass, declare_tool_lint};
5 use crate::utils::{get_trait_def_id, higher, implements_trait, match_qpath, match_type, paths, span_lint};
8 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
10 /// **Why is this bad?** While there may be places where this is acceptable
11 /// (e.g., in event streams), in most cases this is simply an error.
13 /// **Known problems:** None.
19 /// iter::repeat(1_u8).collect::<Vec<_>>();
26 declare_clippy_lint! {
27 /// **What it does:** Checks for iteration that may be infinite.
29 /// **Why is this bad?** While there may be places where this is acceptable
30 /// (e.g., in event streams), in most cases this is simply an error.
32 /// **Known problems:** The code may have a condition to stop iteration, but
33 /// this lint is not clever enough to analyze it.
37 /// let infinite_iter = 0..;
38 /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
40 pub MAYBE_INFINITE_ITER,
42 "possible infinite iteration"
45 declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);
47 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for InfiniteIter {
48 fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr<'_>) {
49 let (lint, msg) = match complete_infinite_iter(cx, expr) {
50 Infinite => (INFINITE_ITER, "infinite iteration detected"),
51 MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
56 span_lint(cx, lint, expr.span, msg)
60 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
67 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
71 fn and(self, b: Self) -> Self {
73 (Finite, _) | (_, Finite) => Finite,
74 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
80 fn or(self, b: Self) -> Self {
82 (Infinite, _) | (_, Infinite) => Infinite,
83 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
89 impl From<bool> for Finiteness {
91 fn from(b: bool) -> Self {
100 /// This tells us what to look for to know if the iterator returned by
101 /// this method is infinite
102 #[derive(Copy, Clone)]
104 /// infinite no matter what
106 /// infinite if the first argument is
108 /// infinite if any of the supplied arguments is
110 /// infinite if all of the supplied arguments are
114 use self::Heuristic::{All, Always, Any, First};
116 /// a slice of (method name, number of args, heuristic, bounds) tuples
117 /// that will be used to determine whether the method in question
118 /// returns an infinite or possibly infinite iterator. The finiteness
119 /// is an upper bound, e.g., some methods can return a possibly
120 /// infinite iterator at worst, e.g., `take_while`.
121 const HEURISTICS: [(&str, usize, Heuristic, Finiteness); 19] = [
122 ("zip", 2, All, Infinite),
123 ("chain", 2, Any, Infinite),
124 ("cycle", 1, Always, Infinite),
125 ("map", 2, First, Infinite),
126 ("by_ref", 1, First, Infinite),
127 ("cloned", 1, First, Infinite),
128 ("rev", 1, First, Infinite),
129 ("inspect", 1, First, Infinite),
130 ("enumerate", 1, First, Infinite),
131 ("peekable", 2, First, Infinite),
132 ("fuse", 1, First, Infinite),
133 ("skip", 2, First, Infinite),
134 ("skip_while", 1, First, Infinite),
135 ("filter", 2, First, Infinite),
136 ("filter_map", 2, First, Infinite),
137 ("flat_map", 2, First, Infinite),
138 ("unzip", 1, First, Infinite),
139 ("take_while", 2, First, MaybeInfinite),
140 ("scan", 3, First, MaybeInfinite),
143 fn is_infinite(cx: &LateContext<'_, '_>, expr: &Expr<'_>) -> Finiteness {
145 ExprKind::MethodCall(ref method, _, ref args) => {
146 for &(name, len, heuristic, cap) in &HEURISTICS {
147 if method.ident.name.as_str() == name && args.len() == len {
148 return (match heuristic {
150 First => is_infinite(cx, &args[0]),
151 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
152 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
157 if method.ident.name == sym!(flat_map) && args.len() == 2 {
158 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].kind {
159 let body = cx.tcx.hir().body(body_id);
160 return is_infinite(cx, &body.value);
165 ExprKind::Block(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
166 ExprKind::Box(ref e) | ExprKind::AddrOf(BorrowKind::Ref, _, ref e) => is_infinite(cx, e),
167 ExprKind::Call(ref path, _) => {
168 if let ExprKind::Path(ref qpath) = path.kind {
169 match_qpath(qpath, &paths::REPEAT).into()
174 ExprKind::Struct(..) => higher::range(cx, 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: [&[&str]; 8] = [
219 fn complete_infinite_iter(cx: &LateContext<'_, '_>, expr: &Expr<'_>) -> Finiteness {
221 ExprKind::MethodCall(ref method, _, ref 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 = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR)
234 .map_or(false, |id| !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[]));
235 if not_double_ended {
236 return is_infinite(cx, &args[0]);
238 } else if method.ident.name == sym!(collect) {
239 let ty = cx.tables.expr_ty(expr);
240 if INFINITE_COLLECTORS.iter().any(|path| match_type(cx, ty, path)) {
241 return is_infinite(cx, &args[0]);
245 ExprKind::Binary(op, ref l, ref r) => {
246 if op.node.is_comparison() {
247 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite);
249 }, // TODO: ExprKind::Loop + Match