1 use crate::rustc::hir::*;
2 use crate::rustc::lint::{LateContext, LateLintPass, LintArray, LintPass};
3 use crate::rustc::{declare_tool_lint, lint_array};
4 use crate::utils::{get_trait_def_id, higher, implements_trait, match_qpath, paths, span_lint};
6 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
8 /// **Why is this bad?** While there may be places where this is acceptable
9 /// (e.g. in event streams), in most cases this is simply an error.
11 /// **Known problems:** None.
15 /// repeat(1_u8).iter().collect::<Vec<_>>()
17 declare_clippy_lint! {
23 /// **What it does:** Checks for iteration that may be infinite.
25 /// **Why is this bad?** While there may be places where this is acceptable
26 /// (e.g. in event streams), in most cases this is simply an error.
28 /// **Known problems:** The code may have a condition to stop iteration, but
29 /// this lint is not clever enough to analyze it.
33 /// [0..].iter().zip(infinite_iter.take_while(|x| x > 5))
35 declare_clippy_lint! {
36 pub MAYBE_INFINITE_ITER,
38 "possible infinite iteration"
41 #[derive(Copy, Clone)]
44 impl LintPass for Pass {
45 fn get_lints(&self) -> LintArray {
46 lint_array!(INFINITE_ITER, MAYBE_INFINITE_ITER)
50 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
51 fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
52 let (lint, msg) = match complete_infinite_iter(cx, expr) {
53 Infinite => (INFINITE_ITER, "infinite iteration detected"),
54 MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
59 span_lint(cx, lint, expr.span, msg)
63 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
70 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
73 fn and(self, b: Self) -> Self {
75 (Finite, _) | (_, Finite) => Finite,
76 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
81 fn or(self, b: Self) -> Self {
83 (Infinite, _) | (_, Infinite) => Infinite,
84 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
90 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 static HEURISTICS: &[(&str, usize, Heuristic, Finiteness)] = &[
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.iter() {
147 if method.ident.name == 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])),
156 if method.ident.name == "flat_map" && args.len() == 2 {
157 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].node {
158 let body = cx.tcx.hir.body(body_id);
159 return is_infinite(cx, &body.value);
164 ExprKind::Block(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
165 ExprKind::Box(ref e) | ExprKind::AddrOf(_, ref e) => is_infinite(cx, e),
166 ExprKind::Call(ref path, _) => if let ExprKind::Path(ref qpath) = path.node {
167 match_qpath(qpath, &paths::REPEAT).into()
171 ExprKind::Struct(..) => higher::range(cx, expr)
172 .map_or(false, |r| r.end.is_none())
178 /// the names and argument lengths of methods that *may* exhaust their
180 static POSSIBLY_COMPLETING_METHODS: &[(&str, usize)] = &[
189 /// the names and argument lengths of methods that *always* exhaust
191 static COMPLETING_METHODS: &[(&str, usize)] = &[
207 fn complete_infinite_iter(cx: &LateContext<'_, '_>, expr: &Expr) -> Finiteness {
209 ExprKind::MethodCall(ref method, _, ref args) => {
210 for &(name, len) in COMPLETING_METHODS.iter() {
211 if method.ident.name == name && args.len() == len {
212 return is_infinite(cx, &args[0]);
215 for &(name, len) in POSSIBLY_COMPLETING_METHODS.iter() {
216 if method.ident.name == name && args.len() == len {
217 return MaybeInfinite.and(is_infinite(cx, &args[0]));
220 if method.ident.name == "last" && args.len() == 1 {
221 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR)
222 .map_or(false, |id| !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[]));
223 if not_double_ended {
224 return is_infinite(cx, &args[0]);
228 ExprKind::Binary(op, ref l, ref r) => if op.node.is_comparison() {
229 return is_infinite(cx, l)
230 .and(is_infinite(cx, r))
232 }, // TODO: ExprKind::Loop + Match