1 // Copyright 2014-2018 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution.
4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
5 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
7 // option. This file may not be copied, modified, or distributed
8 // except according to those terms.
10 use crate::rustc::hir::*;
11 use crate::rustc::lint::{LateContext, LateLintPass, LintArray, LintPass};
12 use crate::rustc::{declare_tool_lint, lint_array};
13 use crate::utils::{get_trait_def_id, higher, implements_trait, match_qpath, paths, span_lint};
15 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
17 /// **Why is this bad?** While there may be places where this is acceptable
18 /// (e.g. in event streams), in most cases this is simply an error.
20 /// **Known problems:** None.
24 /// repeat(1_u8).iter().collect::<Vec<_>>()
26 declare_clippy_lint! {
32 /// **What it does:** Checks for iteration that may be infinite.
34 /// **Why is this bad?** While there may be places where this is acceptable
35 /// (e.g. in event streams), in most cases this is simply an error.
37 /// **Known problems:** The code may have a condition to stop iteration, but
38 /// this lint is not clever enough to analyze it.
42 /// [0..].iter().zip(infinite_iter.take_while(|x| x > 5))
44 declare_clippy_lint! {
45 pub MAYBE_INFINITE_ITER,
47 "possible infinite iteration"
50 #[derive(Copy, Clone)]
53 impl LintPass for Pass {
54 fn get_lints(&self) -> LintArray {
55 lint_array!(INFINITE_ITER, MAYBE_INFINITE_ITER)
59 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
60 fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
61 let (lint, msg) = match complete_infinite_iter(cx, expr) {
62 Infinite => (INFINITE_ITER, "infinite iteration detected"),
63 MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
68 span_lint(cx, lint, expr.span, msg)
72 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
79 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
82 fn and(self, b: Self) -> Self {
84 (Finite, _) | (_, Finite) => Finite,
85 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
90 fn or(self, b: Self) -> Self {
92 (Infinite, _) | (_, Infinite) => Infinite,
93 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
99 impl From<bool> for Finiteness {
100 fn from(b: bool) -> Self {
109 /// This tells us what to look for to know if the iterator returned by
110 /// this method is infinite
111 #[derive(Copy, Clone)]
113 /// infinite no matter what
115 /// infinite if the first argument is
117 /// infinite if any of the supplied arguments is
119 /// infinite if all of the supplied arguments are
123 use self::Heuristic::{All, Always, Any, First};
125 /// a slice of (method name, number of args, heuristic, bounds) tuples
126 /// that will be used to determine whether the method in question
127 /// returns an infinite or possibly infinite iterator. The finiteness
128 /// is an upper bound, e.g. some methods can return a possibly
129 /// infinite iterator at worst, e.g. `take_while`.
130 static HEURISTICS: &[(&str, usize, Heuristic, Finiteness)] = &[
131 ("zip", 2, All, Infinite),
132 ("chain", 2, Any, Infinite),
133 ("cycle", 1, Always, Infinite),
134 ("map", 2, First, Infinite),
135 ("by_ref", 1, First, Infinite),
136 ("cloned", 1, First, Infinite),
137 ("rev", 1, First, Infinite),
138 ("inspect", 1, First, Infinite),
139 ("enumerate", 1, First, Infinite),
140 ("peekable", 2, First, Infinite),
141 ("fuse", 1, First, Infinite),
142 ("skip", 2, First, Infinite),
143 ("skip_while", 1, First, Infinite),
144 ("filter", 2, First, Infinite),
145 ("filter_map", 2, First, Infinite),
146 ("flat_map", 2, First, Infinite),
147 ("unzip", 1, First, Infinite),
148 ("take_while", 2, First, MaybeInfinite),
149 ("scan", 3, First, MaybeInfinite),
152 fn is_infinite(cx: &LateContext<'_, '_>, expr: &Expr) -> Finiteness {
154 ExprKind::MethodCall(ref method, _, ref args) => {
155 for &(name, len, heuristic, cap) in HEURISTICS.iter() {
156 if method.ident.name == name && args.len() == len {
157 return (match heuristic {
159 First => is_infinite(cx, &args[0]),
160 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
161 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
166 if method.ident.name == "flat_map" && args.len() == 2 {
167 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].node {
168 let body = cx.tcx.hir().body(body_id);
169 return is_infinite(cx, &body.value);
174 ExprKind::Block(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
175 ExprKind::Box(ref e) | ExprKind::AddrOf(_, ref e) => is_infinite(cx, e),
176 ExprKind::Call(ref path, _) => {
177 if let ExprKind::Path(ref qpath) = path.node {
178 match_qpath(qpath, &paths::REPEAT).into()
183 ExprKind::Struct(..) => higher::range(cx, expr).map_or(false, |r| r.end.is_none()).into(),
188 /// the names and argument lengths of methods that *may* exhaust their
190 static POSSIBLY_COMPLETING_METHODS: &[(&str, usize)] = &[
199 /// the names and argument lengths of methods that *always* exhaust
201 static COMPLETING_METHODS: &[(&str, usize)] = &[
217 fn complete_infinite_iter(cx: &LateContext<'_, '_>, expr: &Expr) -> Finiteness {
219 ExprKind::MethodCall(ref method, _, ref args) => {
220 for &(name, len) in COMPLETING_METHODS.iter() {
221 if method.ident.name == name && args.len() == len {
222 return is_infinite(cx, &args[0]);
225 for &(name, len) in POSSIBLY_COMPLETING_METHODS.iter() {
226 if method.ident.name == name && args.len() == len {
227 return MaybeInfinite.and(is_infinite(cx, &args[0]));
230 if method.ident.name == "last" && args.len() == 1 {
231 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR)
232 .map_or(false, |id| !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[]));
233 if not_double_ended {
234 return is_infinite(cx, &args[0]);
238 ExprKind::Binary(op, ref l, ref r) => {
239 if op.node.is_comparison() {
240 return is_infinite(cx, l).and(is_infinite(cx, r)).and(MaybeInfinite);
242 }, // TODO: ExprKind::Loop + Match