]>
Commit | Line | Data |
---|---|---|
f20569fa XL |
1 | use rustc_hir::{BorrowKind, Expr, ExprKind}; |
2 | use rustc_lint::{LateContext, LateLintPass}; | |
3 | use rustc_session::{declare_lint_pass, declare_tool_lint}; | |
4 | ||
5 | use crate::utils::{get_trait_def_id, higher, implements_trait, match_qpath, match_type, paths, span_lint}; | |
6 | ||
7 | declare_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 | ||
26 | declare_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 | ||
45 | declare_lint_pass!(InfiniteIter => [INFINITE_ITER, MAYBE_INFINITE_ITER]); | |
46 | ||
47 | impl<'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)] | |
61 | enum Finiteness { | |
62 | Infinite, | |
63 | MaybeInfinite, | |
64 | Finite, | |
65 | } | |
66 | ||
67 | use self::Finiteness::{Finite, Infinite, MaybeInfinite}; | |
68 | ||
69 | impl 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 | ||
89 | impl 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)] | |
99 | enum 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 | ||
110 | use 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`. | |
117 | const 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 | ||
139 | fn 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 | |
177 | const 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 | |
188 | const 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 | |
204 | const 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 | ||
215 | fn 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 | } |