3 use utils::{get_trait_def_id, higher, implements_trait, match_qpath, paths, span_lint};
5 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
7 /// **Why is this bad?** While there may be places where this is acceptable
8 /// (e.g. in event streams), in most cases this is simply an error.
10 /// **Known problems:** None.
14 /// repeat(1_u8).iter().collect::<Vec<_>>()
22 /// **What it does:** Checks for iteration that may be infinite.
24 /// **Why is this bad?** While there may be places where this is acceptable
25 /// (e.g. in event streams), in most cases this is simply an error.
27 /// **Known problems:** The code may have a condition to stop iteration, but
28 /// this lint is not clever enough to analyze it.
32 /// [0..].iter().zip(infinite_iter.take_while(|x| x > 5))
35 pub MAYBE_INFINITE_ITER,
37 "possible infinite iteration"
40 #[derive(Copy, Clone)]
43 impl LintPass for Pass {
44 fn get_lints(&self) -> LintArray {
45 lint_array!(INFINITE_ITER, MAYBE_INFINITE_ITER)
49 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Pass {
50 fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr) {
51 let (lint, msg) = match complete_infinite_iter(cx, expr) {
52 Infinite => (INFINITE_ITER, "infinite iteration detected"),
53 MaybeInfinite => (MAYBE_INFINITE_ITER, "possible infinite iteration detected"),
58 span_lint(cx, lint, expr.span, msg)
62 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
69 use self::Finiteness::{Finite, Infinite, MaybeInfinite};
72 fn and(self, b: Self) -> Self {
74 (Finite, _) | (_, Finite) => Finite,
75 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
80 fn or(self, b: Self) -> Self {
82 (Infinite, _) | (_, Infinite) => Infinite,
83 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
89 impl From<bool> for Finiteness {
90 fn from(b: bool) -> Self {
99 /// This tells us what to look for to know if the iterator returned by
100 /// this method is infinite
101 #[derive(Copy, Clone)]
103 /// infinite no matter what
105 /// infinite if the first argument is
107 /// infinite if any of the supplied arguments is
109 /// infinite if all of the supplied arguments are
113 use self::Heuristic::{All, Always, Any, First};
115 /// a slice of (method name, number of args, heuristic, bounds) tuples
116 /// that will be used to determine whether the method in question
117 /// returns an infinite or possibly infinite iterator. The finiteness
118 /// is an upper bound, e.g. some methods can return a possibly
119 /// infinite iterator at worst, e.g. `take_while`.
120 static HEURISTICS: &[(&str, usize, Heuristic, Finiteness)] = &[
121 ("zip", 2, All, Infinite),
122 ("chain", 2, Any, Infinite),
123 ("cycle", 1, Always, Infinite),
124 ("map", 2, First, Infinite),
125 ("by_ref", 1, First, Infinite),
126 ("cloned", 1, First, Infinite),
127 ("rev", 1, First, Infinite),
128 ("inspect", 1, First, Infinite),
129 ("enumerate", 1, First, Infinite),
130 ("peekable", 2, First, Infinite),
131 ("fuse", 1, First, Infinite),
132 ("skip", 2, First, Infinite),
133 ("skip_while", 1, First, Infinite),
134 ("filter", 2, First, Infinite),
135 ("filter_map", 2, First, Infinite),
136 ("flat_map", 2, First, Infinite),
137 ("unzip", 1, First, Infinite),
138 ("take_while", 2, First, MaybeInfinite),
139 ("scan", 3, First, MaybeInfinite),
142 fn is_infinite(cx: &LateContext, expr: &Expr) -> Finiteness {
144 ExprMethodCall(ref method, _, ref args) => {
145 for &(name, len, heuristic, cap) in HEURISTICS.iter() {
146 if method.name == name && args.len() == len {
147 return (match heuristic {
149 First => is_infinite(cx, &args[0]),
150 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
151 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
155 if method.name == "flat_map" && args.len() == 2 {
156 if let ExprClosure(_, _, body_id, _, _) = args[1].node {
157 let body = cx.tcx.hir.body(body_id);
158 return is_infinite(cx, &body.value);
163 ExprBlock(ref block) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
164 ExprBox(ref e) | ExprAddrOf(_, ref e) => is_infinite(cx, e),
165 ExprCall(ref path, _) => if let ExprPath(ref qpath) = path.node {
166 match_qpath(qpath, &paths::REPEAT).into()
170 ExprStruct(..) => higher::range(expr)
171 .map_or(false, |r| r.end.is_none())
177 /// the names and argument lengths of methods that *may* exhaust their
179 static POSSIBLY_COMPLETING_METHODS: &[(&str, usize)] = &[
188 /// the names and argument lengths of methods that *always* exhaust
190 static COMPLETING_METHODS: &[(&str, usize)] = &[
206 fn complete_infinite_iter(cx: &LateContext, expr: &Expr) -> Finiteness {
208 ExprMethodCall(ref method, _, ref args) => {
209 for &(name, len) in COMPLETING_METHODS.iter() {
210 if method.name == name && args.len() == len {
211 return is_infinite(cx, &args[0]);
214 for &(name, len) in POSSIBLY_COMPLETING_METHODS.iter() {
215 if method.name == name && args.len() == len {
216 return MaybeInfinite.and(is_infinite(cx, &args[0]));
219 if method.name == "last" && args.len() == 1 {
220 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR)
221 .map_or(false, |id| !implements_trait(cx, cx.tables.expr_ty(&args[0]), id, &[]));
222 if not_double_ended {
223 return is_infinite(cx, &args[0]);
227 ExprBinary(op, ref l, ref r) => if op.node.is_comparison() {
228 return is_infinite(cx, l)
229 .and(is_infinite(cx, r))
231 }, // TODO: ExprLoop + Match