]> git.proxmox.com Git - rustc.git/blame - src/tools/clippy/clippy_lints/src/infinite_iter.rs
New upstream version 1.52.1+dfsg1
[rustc.git] / src / tools / clippy / clippy_lints / src / infinite_iter.rs
CommitLineData
f20569fa
XL
1use rustc_hir::{BorrowKind, Expr, ExprKind};
2use rustc_lint::{LateContext, LateLintPass};
3use rustc_session::{declare_lint_pass, declare_tool_lint};
4
5use crate::utils::{get_trait_def_id, higher, implements_trait, match_qpath, match_type, paths, span_lint};
6
7declare_clippy_lint! {
8 /// **What it does:** Checks for iteration that is guaranteed to be infinite.
9 ///
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.
12 ///
13 /// **Known problems:** None.
14 ///
15 /// **Example:**
16 /// ```no_run
17 /// use std::iter;
18 ///
19 /// iter::repeat(1_u8).collect::<Vec<_>>();
20 /// ```
21 pub INFINITE_ITER,
22 correctness,
23 "infinite iteration"
24}
25
26declare_clippy_lint! {
27 /// **What it does:** Checks for iteration that may be infinite.
28 ///
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.
31 ///
32 /// **Known problems:** The code may have a condition to stop iteration, but
33 /// this lint is not clever enough to analyze it.
34 ///
35 /// **Example:**
36 /// ```rust
37 /// let infinite_iter = 0..;
38 /// [0..].iter().zip(infinite_iter.take_while(|x| *x > 5));
39 /// ```
40 pub MAYBE_INFINITE_ITER,
41 pedantic,
42 "possible infinite iteration"
43}
44
45declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]);
46
47impl<'tcx> LateLintPass<'tcx> for InfiniteIter {
48 fn check_expr(&mut self, cx: &LateContext<'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"),
52 Finite => {
53 return;
54 },
55 };
56 span_lint(cx, lint, expr.span, msg)
57 }
58}
59
60#[derive(Copy, Clone, Debug, PartialEq, Eq)]
61enum Finiteness {
62 Infinite,
63 MaybeInfinite,
64 Finite,
65}
66
67use self::Finiteness::{Finite, Infinite, MaybeInfinite};
68
69impl Finiteness {
70 #[must_use]
71 fn and(self, b: Self) -> Self {
72 match (self, b) {
73 (Finite, _) | (_, Finite) => Finite,
74 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
75 _ => Infinite,
76 }
77 }
78
79 #[must_use]
80 fn or(self, b: Self) -> Self {
81 match (self, b) {
82 (Infinite, _) | (_, Infinite) => Infinite,
83 (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite,
84 _ => Finite,
85 }
86 }
87}
88
89impl From<bool> for Finiteness {
90 #[must_use]
91 fn from(b: bool) -> Self {
92 if b { Infinite } else { Finite }
93 }
94}
95
96/// This tells us what to look for to know if the iterator returned by
97/// this method is infinite
98#[derive(Copy, Clone)]
99enum Heuristic {
100 /// infinite no matter what
101 Always,
102 /// infinite if the first argument is
103 First,
104 /// infinite if any of the supplied arguments is
105 Any,
106 /// infinite if all of the supplied arguments are
107 All,
108}
109
110use self::Heuristic::{All, Always, Any, First};
111
112/// a slice of (method name, number of args, heuristic, bounds) tuples
113/// that will be used to determine whether the method in question
114/// returns an infinite or possibly infinite iterator. The finiteness
115/// is an upper bound, e.g., some methods can return a possibly
116/// infinite iterator at worst, e.g., `take_while`.
117const HEURISTICS: [(&str, usize, Heuristic, Finiteness); 19] = [
118 ("zip", 2, All, Infinite),
119 ("chain", 2, Any, Infinite),
120 ("cycle", 1, Always, Infinite),
121 ("map", 2, First, Infinite),
122 ("by_ref", 1, First, Infinite),
123 ("cloned", 1, First, Infinite),
124 ("rev", 1, First, Infinite),
125 ("inspect", 1, First, Infinite),
126 ("enumerate", 1, First, Infinite),
127 ("peekable", 2, First, Infinite),
128 ("fuse", 1, First, Infinite),
129 ("skip", 2, First, Infinite),
130 ("skip_while", 1, First, Infinite),
131 ("filter", 2, First, Infinite),
132 ("filter_map", 2, First, Infinite),
133 ("flat_map", 2, First, Infinite),
134 ("unzip", 1, First, Infinite),
135 ("take_while", 2, First, MaybeInfinite),
136 ("scan", 3, First, MaybeInfinite),
137];
138
139fn is_infinite(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
140 match expr.kind {
141 ExprKind::MethodCall(ref method, _, ref args, _) => {
142 for &(name, len, heuristic, cap) in &HEURISTICS {
143 if method.ident.name.as_str() == name && args.len() == len {
144 return (match heuristic {
145 Always => Infinite,
146 First => is_infinite(cx, &args[0]),
147 Any => is_infinite(cx, &args[0]).or(is_infinite(cx, &args[1])),
148 All => is_infinite(cx, &args[0]).and(is_infinite(cx, &args[1])),
149 })
150 .and(cap);
151 }
152 }
153 if method.ident.name == sym!(flat_map) && args.len() == 2 {
154 if let ExprKind::Closure(_, _, body_id, _, _) = args[1].kind {
155 let body = cx.tcx.hir().body(body_id);
156 return is_infinite(cx, &body.value);
157 }
158 }
159 Finite
160 },
161 ExprKind::Block(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)),
162 ExprKind::Box(ref e) | ExprKind::AddrOf(BorrowKind::Ref, _, ref e) => is_infinite(cx, e),
163 ExprKind::Call(ref path, _) => {
164 if let ExprKind::Path(ref qpath) = path.kind {
165 match_qpath(qpath, &paths::REPEAT).into()
166 } else {
167 Finite
168 }
169 },
170 ExprKind::Struct(..) => higher::range(expr).map_or(false, |r| r.end.is_none()).into(),
171 _ => Finite,
172 }
173}
174
175/// the names and argument lengths of methods that *may* exhaust their
176/// iterators
177const POSSIBLY_COMPLETING_METHODS: [(&str, usize); 6] = [
178 ("find", 2),
179 ("rfind", 2),
180 ("position", 2),
181 ("rposition", 2),
182 ("any", 2),
183 ("all", 2),
184];
185
186/// the names and argument lengths of methods that *always* exhaust
187/// their iterators
188const COMPLETING_METHODS: [(&str, usize); 12] = [
189 ("count", 1),
190 ("fold", 3),
191 ("for_each", 2),
192 ("partition", 2),
193 ("max", 1),
194 ("max_by", 2),
195 ("max_by_key", 2),
196 ("min", 1),
197 ("min_by", 2),
198 ("min_by_key", 2),
199 ("sum", 1),
200 ("product", 1),
201];
202
203/// the paths of types that are known to be infinitely allocating
204const INFINITE_COLLECTORS: [&[&str]; 8] = [
205 &paths::BINARY_HEAP,
206 &paths::BTREEMAP,
207 &paths::BTREESET,
208 &paths::HASHMAP,
209 &paths::HASHSET,
210 &paths::LINKED_LIST,
211 &paths::VEC,
212 &paths::VEC_DEQUE,
213];
214
215fn complete_infinite_iter(cx: &LateContext<'_>, expr: &Expr<'_>) -> Finiteness {
216 match expr.kind {
217 ExprKind::MethodCall(ref method, _, ref args, _) => {
218 for &(name, len) in &COMPLETING_METHODS {
219 if method.ident.name.as_str() == name && args.len() == len {
220 return is_infinite(cx, &args[0]);
221 }
222 }
223 for &(name, len) in &POSSIBLY_COMPLETING_METHODS {
224 if method.ident.name.as_str() == name && args.len() == len {
225 return MaybeInfinite.and(is_infinite(cx, &args[0]));
226 }
227 }
228 if method.ident.name == sym!(last) && args.len() == 1 {
229 let not_double_ended = get_trait_def_id(cx, &paths::DOUBLE_ENDED_ITERATOR).map_or(false, |id| {
230 !implements_trait(cx, cx.typeck_results().expr_ty(&args[0]), id, &[])
231 });
232 if not_double_ended {
233 return is_infinite(cx, &args[0]);
234 }
235 } else if method.ident.name == sym!(collect) {
236 let ty = cx.typeck_results().expr_ty(expr);
237 if INFINITE_COLLECTORS.iter().any(|path| match_type(cx, ty, path)) {
238 return is_infinite(cx, &args[0]);
239 }
240 }
241 },
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);
245 }
246 }, // TODO: ExprKind::Loop + Match
247 _ => (),
248 }
249 Finite
250}