1 use rustc::declare_lint_pass;
3 use rustc::lint::{LateContext, LateLintPass, LintArray, LintPass};
4 use rustc_session::declare_tool_lint;
6 use crate::utils::{get_trait_def_id, higher, implements_trait, match_qpath, match_type, paths, span_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<'a, 'tcx> LateLintPass<'a, 'tcx> for InfiniteIter {
49 fn check_expr(&mut self, cx: &LateContext<'a, '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 {
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(ref method, _, ref 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(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
167 ExprKind::Box(ref e) | ExprKind::AddrOf(BorrowKind::Ref, _, ref e) => is_infinite(cx, e),
168 ExprKind::Call(ref path, _) => {
169 if let ExprKind::Path(ref qpath) = path.kind {
170 match_qpath(qpath, &paths::REPEAT).into()
175 ExprKind::Struct(..) => higher::range(cx, 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: [&[&str]; 8] = [
220 fn complete_infinite_iter(cx: &LateContext<'_, '_>, expr: &Expr) -> Finiteness {
222 ExprKind::MethodCall(ref method, _, ref 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)
235 .map_or(false, |id| !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[]));
236 if not_double_ended {
237 return is_infinite(cx, &args[0]);
239 } else if method.ident.name == sym!(collect) {
240 let ty = cx.tables.expr_ty(expr);
241 if INFINITE_COLLECTORS.iter().any(|path| match_type(cx, ty, path)) {
242 return is_infinite(cx, &args[0]);
246 ExprKind::Binary(op, ref l, ref r) => {
247 if op.node.is_comparison() {
248 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite);
250 }, // TODO: ExprKind::Loop + Match