2 use rustc::lint::{LateContext, LateLintPass, LintArray, LintPass};
3 use rustc::{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};
70 fn and(self, b: Self) -> Self {
72 (Finite, _) | (_, Finite) => Finite,
73 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
78 fn or(self, b: Self) -> Self {
80 (Infinite, _) | (_, Infinite) => Infinite,
81 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
87 impl From<bool> for Finiteness {
88 fn from(b: bool) -> Self {
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(ref method, _, ref 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].node {
156 let body = cx.tcx.hir().body(body_id);
157 return is_infinite(cx, &body.value);
162 ExprKind::Block(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
163 ExprKind::Box(ref e) | ExprKind::AddrOf(_, ref e) => is_infinite(cx, e),
164 ExprKind::Call(ref path, _) => {
165 if let ExprKind::Path(ref qpath) = path.node {
166 match_qpath(qpath, &paths::REPEAT).into()
171 ExprKind::Struct(..) => higher::range(cx, 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(ref method, _, ref 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)
231 .map_or(false, |id| !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[]));
232 if not_double_ended {
233 return is_infinite(cx, &args[0]);
235 } else if method.ident.name == sym!(collect) {
236 let ty = cx.tables.expr_ty(expr);
237 if INFINITE_COLLECTORS.iter().any(|path| match_type(cx, ty, path)) {
238 return is_infinite(cx, &args[0]);
242 ExprKind::Binary(op, ref l, ref r) => {
243 if op.node.is_comparison() {
244 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite);
246 }, // TODO: ExprKind::Loop + Match