]>
Commit | Line | Data |
---|---|---|
ea8adc8c XL |
1 | use rustc::hir::*; |
2 | use rustc::lint::*; | |
abe05a73 | 3 | use utils::{get_trait_def_id, higher, implements_trait, match_qpath, paths, span_lint}; |
ea8adc8c XL |
4 | |
5 | /// **What it does:** Checks for iteration that is guaranteed to be infinite. | |
6 | /// | |
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. | |
9 | /// | |
10 | /// **Known problems:** None. | |
11 | /// | |
12 | /// **Example:** | |
13 | /// ```rust | |
14 | /// repeat(1_u8).iter().collect::<Vec<_>>() | |
15 | /// ``` | |
0531ce1d | 16 | declare_clippy_lint! { |
ea8adc8c | 17 | pub INFINITE_ITER, |
0531ce1d | 18 | correctness, |
ea8adc8c XL |
19 | "infinite iteration" |
20 | } | |
21 | ||
22 | /// **What it does:** Checks for iteration that may be infinite. | |
23 | /// | |
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. | |
26 | /// | |
27 | /// **Known problems:** The code may have a condition to stop iteration, but | |
28 | /// this lint is not clever enough to analyze it. | |
29 | /// | |
30 | /// **Example:** | |
31 | /// ```rust | |
32 | /// [0..].iter().zip(infinite_iter.take_while(|x| x > 5)) | |
33 | /// ``` | |
0531ce1d | 34 | declare_clippy_lint! { |
ea8adc8c | 35 | pub MAYBE_INFINITE_ITER, |
0531ce1d | 36 | pedantic, |
ea8adc8c XL |
37 | "possible infinite iteration" |
38 | } | |
39 | ||
40 | #[derive(Copy, Clone)] | |
41 | pub struct Pass; | |
42 | ||
43 | impl LintPass for Pass { | |
44 | fn get_lints(&self) -> LintArray { | |
45 | lint_array!(INFINITE_ITER, MAYBE_INFINITE_ITER) | |
46 | } | |
47 | } | |
48 | ||
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"), | |
54 | Finite => { | |
55 | return; | |
56 | }, | |
57 | }; | |
58 | span_lint(cx, lint, expr.span, msg) | |
59 | } | |
60 | } | |
61 | ||
62 | #[derive(Copy, Clone, Debug, PartialEq, Eq)] | |
63 | enum Finiteness { | |
64 | Infinite, | |
65 | MaybeInfinite, | |
66 | Finite, | |
67 | } | |
68 | ||
abe05a73 | 69 | use self::Finiteness::{Finite, Infinite, MaybeInfinite}; |
ea8adc8c XL |
70 | |
71 | impl Finiteness { | |
72 | fn and(self, b: Self) -> Self { | |
73 | match (self, b) { | |
74 | (Finite, _) | (_, Finite) => Finite, | |
abe05a73 | 75 | (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite, |
ea8adc8c XL |
76 | _ => Infinite, |
77 | } | |
78 | } | |
79 | ||
80 | fn or(self, b: Self) -> Self { | |
81 | match (self, b) { | |
82 | (Infinite, _) | (_, Infinite) => Infinite, | |
abe05a73 | 83 | (MaybeInfinite, _) | (_, MaybeInfinite) => MaybeInfinite, |
ea8adc8c XL |
84 | _ => Finite, |
85 | } | |
86 | } | |
87 | } | |
88 | ||
89 | impl From<bool> for Finiteness { | |
90 | fn from(b: bool) -> Self { | |
abe05a73 XL |
91 | if b { |
92 | Infinite | |
93 | } else { | |
94 | Finite | |
95 | } | |
ea8adc8c XL |
96 | } |
97 | } | |
98 | ||
99 | /// This tells us what to look for to know if the iterator returned by | |
100 | /// this method is infinite | |
101 | #[derive(Copy, Clone)] | |
102 | enum Heuristic { | |
103 | /// infinite no matter what | |
104 | Always, | |
105 | /// infinite if the first argument is | |
106 | First, | |
107 | /// infinite if any of the supplied arguments is | |
108 | Any, | |
109 | /// infinite if all of the supplied arguments are | |
110 | All, | |
111 | } | |
112 | ||
abe05a73 | 113 | use self::Heuristic::{All, Always, Any, First}; |
ea8adc8c XL |
114 | |
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), | |
140 | ]; | |
141 | ||
142 | fn is_infinite(cx: &LateContext, expr: &Expr) -> Finiteness { | |
143 | match expr.node { | |
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 { | |
abe05a73 XL |
148 | Always => Infinite, |
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])), | |
152 | }).and(cap); | |
ea8adc8c XL |
153 | } |
154 | } | |
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); | |
159 | } | |
160 | } | |
161 | Finite | |
162 | }, | |
94b46f34 | 163 | ExprBlock(ref block, _) => block.expr.as_ref().map_or(Finite, |e| is_infinite(cx, e)), |
abe05a73 XL |
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() | |
167 | } else { | |
168 | Finite | |
ea8adc8c | 169 | }, |
94b46f34 | 170 | ExprStruct(..) => higher::range(cx, expr) |
abe05a73 XL |
171 | .map_or(false, |r| r.end.is_none()) |
172 | .into(), | |
ea8adc8c XL |
173 | _ => Finite, |
174 | } | |
175 | } | |
176 | ||
177 | /// the names and argument lengths of methods that *may* exhaust their | |
178 | /// iterators | |
179 | static POSSIBLY_COMPLETING_METHODS: &[(&str, usize)] = &[ | |
180 | ("find", 2), | |
181 | ("rfind", 2), | |
182 | ("position", 2), | |
183 | ("rposition", 2), | |
184 | ("any", 2), | |
185 | ("all", 2), | |
186 | ]; | |
187 | ||
188 | /// the names and argument lengths of methods that *always* exhaust | |
189 | /// their iterators | |
190 | static COMPLETING_METHODS: &[(&str, usize)] = &[ | |
191 | ("count", 1), | |
192 | ("collect", 1), | |
193 | ("fold", 3), | |
194 | ("for_each", 2), | |
195 | ("partition", 2), | |
196 | ("max", 1), | |
197 | ("max_by", 2), | |
198 | ("max_by_key", 2), | |
199 | ("min", 1), | |
200 | ("min_by", 2), | |
201 | ("min_by_key", 2), | |
202 | ("sum", 1), | |
203 | ("product", 1), | |
204 | ]; | |
205 | ||
206 | fn complete_infinite_iter(cx: &LateContext, expr: &Expr) -> Finiteness { | |
207 | match expr.node { | |
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]); | |
212 | } | |
213 | } | |
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])); | |
217 | } | |
218 | } | |
abe05a73 XL |
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]); | |
224 | } | |
ea8adc8c XL |
225 | } |
226 | }, | |
abe05a73 XL |
227 | ExprBinary(op, ref l, ref r) => if op.node.is_comparison() { |
228 | return is_infinite(cx, l) | |
229 | .and(is_infinite(cx, r)) | |
230 | .and(MaybeInfinite); | |
231 | }, // TODO: ExprLoop + Match | |
ea8adc8c XL |
232 | _ => (), |
233 | } | |
234 | Finite | |
235 | } |