]>
Commit | Line | Data |
---|---|---|
f2b60f7d FG |
1 | use clippy_utils::diagnostics::span_lint_and_then; |
2 | use clippy_utils::{get_expr_use_or_unification_node, get_parent_node, path_def_id, path_to_local, path_to_local_id}; | |
3 | use core::cell::Cell; | |
4 | use rustc_data_structures::fx::FxHashMap; | |
5e7ed085 | 5 | use rustc_errors::Applicability; |
5e7ed085 | 6 | use rustc_hir::def_id::DefId; |
f2b60f7d FG |
7 | use rustc_hir::hir_id::HirIdMap; |
8 | use rustc_hir::{Body, Expr, ExprKind, HirId, ImplItem, ImplItemKind, Node, PatKind, TraitItem, TraitItemKind}; | |
5e7ed085 | 9 | use rustc_lint::{LateContext, LateLintPass}; |
f2b60f7d FG |
10 | use rustc_middle::ty::subst::{GenericArgKind, SubstsRef}; |
11 | use rustc_middle::ty::{self, ConstKind}; | |
12 | use rustc_session::{declare_tool_lint, impl_lint_pass}; | |
13 | use rustc_span::symbol::{kw, Ident}; | |
5e7ed085 | 14 | use rustc_span::Span; |
f2b60f7d | 15 | use std::iter; |
5e7ed085 FG |
16 | |
17 | declare_clippy_lint! { | |
18 | /// ### What it does | |
19 | /// Checks for arguments that are only used in recursion with no side-effects. | |
20 | /// | |
21 | /// ### Why is this bad? | |
22 | /// It could contain a useless calculation and can make function simpler. | |
23 | /// | |
24 | /// The arguments can be involved in calculations and assignments but as long as | |
25 | /// the calculations have no side-effects (function calls or mutating dereference) | |
26 | /// and the assigned variables are also only in recursion, it is useless. | |
27 | /// | |
28 | /// ### Known problems | |
29 | /// Too many code paths in the linting code are currently untested and prone to produce false | |
30 | /// positives or are prone to have performance implications. | |
31 | /// | |
32 | /// In some cases, this would not catch all useless arguments. | |
33 | /// | |
34 | /// ```rust | |
35 | /// fn foo(a: usize, b: usize) -> usize { | |
36 | /// let f = |x| x + 1; | |
37 | /// | |
38 | /// if a == 0 { | |
39 | /// 1 | |
40 | /// } else { | |
41 | /// foo(a - 1, f(b)) | |
42 | /// } | |
43 | /// } | |
44 | /// ``` | |
45 | /// | |
46 | /// For example, the argument `b` is only used in recursion, but the lint would not catch it. | |
47 | /// | |
48 | /// List of some examples that can not be caught: | |
49 | /// - binary operation of non-primitive types | |
50 | /// - closure usage | |
51 | /// - some `break` relative operations | |
52 | /// - struct pattern binding | |
53 | /// | |
54 | /// Also, when you recurse the function name with path segments, it is not possible to detect. | |
55 | /// | |
56 | /// ### Example | |
57 | /// ```rust | |
58 | /// fn f(a: usize, b: usize) -> usize { | |
59 | /// if a == 0 { | |
60 | /// 1 | |
61 | /// } else { | |
62 | /// f(a - 1, b + 1) | |
63 | /// } | |
64 | /// } | |
65 | /// # fn main() { | |
66 | /// # print!("{}", f(1, 1)); | |
67 | /// # } | |
68 | /// ``` | |
69 | /// Use instead: | |
70 | /// ```rust | |
71 | /// fn f(a: usize) -> usize { | |
72 | /// if a == 0 { | |
73 | /// 1 | |
74 | /// } else { | |
75 | /// f(a - 1) | |
76 | /// } | |
77 | /// } | |
78 | /// # fn main() { | |
79 | /// # print!("{}", f(1)); | |
80 | /// # } | |
81 | /// ``` | |
923072b8 | 82 | #[clippy::version = "1.61.0"] |
5e7ed085 | 83 | pub ONLY_USED_IN_RECURSION, |
f2b60f7d | 84 | complexity, |
5e7ed085 FG |
85 | "arguments that is only used in recursion can be removed" |
86 | } | |
f2b60f7d FG |
87 | impl_lint_pass!(OnlyUsedInRecursion => [ONLY_USED_IN_RECURSION]); |
88 | ||
89 | #[derive(Clone, Copy)] | |
90 | enum FnKind { | |
91 | Fn, | |
92 | TraitFn, | |
93 | // This is a hack. Ideally we would store a `SubstsRef<'tcx>` type here, but a lint pass must be `'static`. | |
94 | // Substitutions are, however, interned. This allows us to store the pointer as a `usize` when comparing for | |
95 | // equality. | |
96 | ImplTraitFn(usize), | |
97 | } | |
5e7ed085 | 98 | |
f2b60f7d FG |
99 | struct Param { |
100 | /// The function this is a parameter for. | |
101 | fn_id: DefId, | |
102 | fn_kind: FnKind, | |
103 | /// The index of this parameter. | |
104 | idx: usize, | |
105 | ident: Ident, | |
106 | /// Whether this parameter should be linted. Set by `Params::flag_for_linting`. | |
107 | apply_lint: Cell<bool>, | |
108 | /// All the uses of this parameter. | |
109 | uses: Vec<Usage>, | |
110 | } | |
111 | impl Param { | |
112 | fn new(fn_id: DefId, fn_kind: FnKind, idx: usize, ident: Ident) -> Self { | |
113 | Self { | |
114 | fn_id, | |
115 | fn_kind, | |
116 | idx, | |
117 | ident, | |
118 | apply_lint: Cell::new(true), | |
119 | uses: Vec::new(), | |
5e7ed085 FG |
120 | } |
121 | } | |
122 | } | |
123 | ||
f2b60f7d FG |
124 | #[derive(Debug)] |
125 | struct Usage { | |
126 | span: Span, | |
127 | idx: usize, | |
5e7ed085 | 128 | } |
f2b60f7d FG |
129 | impl Usage { |
130 | fn new(span: Span, idx: usize) -> Self { | |
131 | Self { span, idx } | |
132 | } | |
5e7ed085 FG |
133 | } |
134 | ||
f2b60f7d FG |
135 | /// The parameters being checked by the lint, indexed by both the parameter's `HirId` and the |
136 | /// `DefId` of the function paired with the parameter's index. | |
137 | #[derive(Default)] | |
138 | struct Params { | |
139 | params: Vec<Param>, | |
140 | by_id: HirIdMap<usize>, | |
141 | by_fn: FxHashMap<(DefId, usize), usize>, | |
5e7ed085 | 142 | } |
f2b60f7d FG |
143 | impl Params { |
144 | fn insert(&mut self, param: Param, id: HirId) { | |
145 | let idx = self.params.len(); | |
146 | self.by_id.insert(id, idx); | |
147 | self.by_fn.insert((param.fn_id, param.idx), idx); | |
148 | self.params.push(param); | |
5e7ed085 FG |
149 | } |
150 | ||
f2b60f7d FG |
151 | fn remove_by_id(&mut self, id: HirId) { |
152 | if let Some(param) = self.get_by_id_mut(id) { | |
153 | param.uses = Vec::new(); | |
154 | let key = (param.fn_id, param.idx); | |
155 | self.by_fn.remove(&key); | |
156 | self.by_id.remove(&id); | |
5e7ed085 FG |
157 | } |
158 | } | |
159 | ||
f2b60f7d FG |
160 | fn get_by_id_mut(&mut self, id: HirId) -> Option<&mut Param> { |
161 | self.params.get_mut(*self.by_id.get(&id)?) | |
5e7ed085 | 162 | } |
5e7ed085 | 163 | |
f2b60f7d FG |
164 | fn get_by_fn(&self, id: DefId, idx: usize) -> Option<&Param> { |
165 | self.params.get(*self.by_fn.get(&(id, idx))?) | |
5e7ed085 FG |
166 | } |
167 | ||
f2b60f7d FG |
168 | fn clear(&mut self) { |
169 | self.params.clear(); | |
170 | self.by_id.clear(); | |
171 | self.by_fn.clear(); | |
5e7ed085 FG |
172 | } |
173 | ||
f2b60f7d FG |
174 | /// Sets the `apply_lint` flag on each parameter. |
175 | fn flag_for_linting(&mut self) { | |
176 | // Stores the list of parameters currently being resolved. Needed to avoid cycles. | |
177 | let mut eval_stack = Vec::new(); | |
178 | for param in &self.params { | |
179 | self.try_disable_lint_for_param(param, &mut eval_stack); | |
5e7ed085 FG |
180 | } |
181 | } | |
182 | ||
f2b60f7d FG |
183 | // Use by calling `flag_for_linting`. |
184 | fn try_disable_lint_for_param(&self, param: &Param, eval_stack: &mut Vec<usize>) -> bool { | |
185 | if !param.apply_lint.get() { | |
186 | true | |
187 | } else if param.uses.is_empty() { | |
188 | // Don't lint on unused parameters. | |
189 | param.apply_lint.set(false); | |
190 | true | |
191 | } else if eval_stack.contains(¶m.idx) { | |
192 | // Already on the evaluation stack. Returning false will continue to evaluate other dependencies. | |
193 | false | |
194 | } else { | |
195 | eval_stack.push(param.idx); | |
196 | // Check all cases when used at a different parameter index. | |
197 | // Needed to catch cases like: `fn f(x: u32, y: u32) { f(y, x) }` | |
198 | for usage in param.uses.iter().filter(|u| u.idx != param.idx) { | |
199 | if self | |
200 | .get_by_fn(param.fn_id, usage.idx) | |
201 | // If the parameter can't be found, then it's used for more than just recursion. | |
202 | .map_or(true, |p| self.try_disable_lint_for_param(p, eval_stack)) | |
203 | { | |
204 | param.apply_lint.set(false); | |
205 | eval_stack.pop(); | |
206 | return true; | |
207 | } | |
208 | } | |
209 | eval_stack.pop(); | |
210 | false | |
5e7ed085 FG |
211 | } |
212 | } | |
f2b60f7d | 213 | } |
5e7ed085 | 214 | |
f2b60f7d FG |
215 | #[derive(Default)] |
216 | pub struct OnlyUsedInRecursion { | |
217 | /// Track the top-level body entered. Needed to delay reporting when entering nested bodies. | |
218 | entered_body: Option<HirId>, | |
219 | params: Params, | |
220 | } | |
5e7ed085 | 221 | |
f2b60f7d FG |
222 | impl<'tcx> LateLintPass<'tcx> for OnlyUsedInRecursion { |
223 | fn check_body(&mut self, cx: &LateContext<'tcx>, body: &'tcx Body<'tcx>) { | |
224 | if body.value.span.from_expansion() { | |
225 | return; | |
5e7ed085 | 226 | } |
f2b60f7d FG |
227 | // `skip_params` is either `0` or `1` to skip the `self` parameter in trait functions. |
228 | // It can't be renamed, and it can't be removed without removing it from multiple functions. | |
229 | let (fn_id, fn_kind, skip_params) = match get_parent_node(cx.tcx, body.value.hir_id) { | |
230 | Some(Node::Item(i)) => (i.def_id.to_def_id(), FnKind::Fn, 0), | |
231 | Some(Node::TraitItem(&TraitItem { | |
232 | kind: TraitItemKind::Fn(ref sig, _), | |
233 | def_id, | |
234 | .. | |
235 | })) => ( | |
236 | def_id.to_def_id(), | |
237 | FnKind::TraitFn, | |
238 | usize::from(sig.decl.implicit_self.has_implicit_self()), | |
239 | ), | |
240 | Some(Node::ImplItem(&ImplItem { | |
241 | kind: ImplItemKind::Fn(ref sig, _), | |
242 | def_id, | |
243 | .. | |
244 | })) => { | |
245 | #[allow(trivial_casts)] | |
246 | if let Some(Node::Item(item)) = get_parent_node(cx.tcx, cx.tcx.hir().local_def_id_to_hir_id(def_id)) | |
247 | && let Some(trait_ref) = cx.tcx.impl_trait_ref(item.def_id) | |
248 | && let Some(trait_item_id) = cx.tcx.associated_item(def_id).trait_item_def_id | |
249 | { | |
250 | ( | |
251 | trait_item_id, | |
252 | FnKind::ImplTraitFn(cx.tcx.erase_regions(trait_ref.substs) as *const _ as usize), | |
253 | usize::from(sig.decl.implicit_self.has_implicit_self()), | |
254 | ) | |
255 | } else { | |
256 | (def_id.to_def_id(), FnKind::Fn, 0) | |
257 | } | |
258 | }, | |
259 | _ => return, | |
260 | }; | |
261 | body.params | |
262 | .iter() | |
263 | .enumerate() | |
264 | .skip(skip_params) | |
265 | .filter_map(|(idx, p)| match p.pat.kind { | |
266 | PatKind::Binding(_, id, ident, None) if !ident.as_str().starts_with('_') => { | |
267 | Some((id, Param::new(fn_id, fn_kind, idx, ident))) | |
268 | }, | |
269 | _ => None, | |
270 | }) | |
271 | .for_each(|(id, param)| self.params.insert(param, id)); | |
272 | if self.entered_body.is_none() { | |
273 | self.entered_body = Some(body.value.hir_id); | |
5e7ed085 | 274 | } |
5e7ed085 FG |
275 | } |
276 | ||
f2b60f7d FG |
277 | fn check_expr(&mut self, cx: &LateContext<'tcx>, e: &'tcx Expr<'tcx>) { |
278 | if let Some(id) = path_to_local(e) | |
279 | && let Some(param) = self.params.get_by_id_mut(id) | |
280 | { | |
281 | let typeck = cx.typeck_results(); | |
282 | let span = e.span; | |
283 | let mut e = e; | |
284 | loop { | |
285 | match get_expr_use_or_unification_node(cx.tcx, e) { | |
286 | None | Some((Node::Stmt(_), _)) => return, | |
287 | Some((Node::Expr(parent), child_id)) => match parent.kind { | |
288 | // Recursive call. Track which index the parameter is used in. | |
289 | ExprKind::Call(callee, args) | |
290 | if path_def_id(cx, callee).map_or(false, |id| { | |
291 | id == param.fn_id | |
292 | && has_matching_substs(param.fn_kind, typeck.node_substs(callee.hir_id)) | |
293 | }) => | |
294 | { | |
295 | if let Some(idx) = args.iter().position(|arg| arg.hir_id == child_id) { | |
296 | param.uses.push(Usage::new(span, idx)); | |
297 | } | |
298 | return; | |
299 | }, | |
300 | ExprKind::MethodCall(_, receiver, args, _) | |
301 | if typeck.type_dependent_def_id(parent.hir_id).map_or(false, |id| { | |
302 | id == param.fn_id | |
303 | && has_matching_substs(param.fn_kind, typeck.node_substs(parent.hir_id)) | |
304 | }) => | |
305 | { | |
306 | if let Some(idx) = iter::once(receiver).chain(args).position(|arg| arg.hir_id == child_id) { | |
307 | param.uses.push(Usage::new(span, idx)); | |
308 | } | |
309 | return; | |
310 | }, | |
311 | // Assignment to a parameter is fine. | |
312 | ExprKind::Assign(lhs, _, _) | ExprKind::AssignOp(_, lhs, _) if lhs.hir_id == child_id => { | |
313 | return; | |
314 | }, | |
315 | // Parameter update e.g. `x = x + 1` | |
316 | ExprKind::Assign(lhs, rhs, _) | ExprKind::AssignOp(_, lhs, rhs) | |
317 | if rhs.hir_id == child_id && path_to_local_id(lhs, id) => | |
318 | { | |
319 | return; | |
320 | }, | |
321 | // Side-effect free expressions. Walk to the parent expression. | |
322 | ExprKind::Binary(_, lhs, rhs) | |
323 | if typeck.expr_ty(lhs).is_primitive() && typeck.expr_ty(rhs).is_primitive() => | |
324 | { | |
325 | e = parent; | |
326 | continue; | |
327 | }, | |
328 | ExprKind::Unary(_, arg) if typeck.expr_ty(arg).is_primitive() => { | |
329 | e = parent; | |
330 | continue; | |
331 | }, | |
332 | ExprKind::AddrOf(..) | ExprKind::Cast(..) => { | |
333 | e = parent; | |
334 | continue; | |
335 | }, | |
336 | // Only allow field accesses without auto-deref | |
337 | ExprKind::Field(..) if typeck.adjustments().get(child_id).is_none() => { | |
338 | e = parent; | |
339 | continue | |
340 | } | |
341 | _ => (), | |
342 | }, | |
343 | _ => (), | |
344 | } | |
345 | self.params.remove_by_id(id); | |
346 | return; | |
5e7ed085 FG |
347 | } |
348 | } | |
349 | } | |
350 | ||
f2b60f7d FG |
351 | fn check_body_post(&mut self, cx: &LateContext<'tcx>, body: &'tcx Body<'tcx>) { |
352 | if self.entered_body == Some(body.value.hir_id) { | |
353 | self.entered_body = None; | |
354 | self.params.flag_for_linting(); | |
355 | for param in &self.params.params { | |
356 | if param.apply_lint.get() { | |
357 | span_lint_and_then( | |
358 | cx, | |
359 | ONLY_USED_IN_RECURSION, | |
360 | param.ident.span, | |
361 | "parameter is only used in recursion", | |
362 | |diag| { | |
363 | if param.ident.name != kw::SelfLower { | |
364 | diag.span_suggestion( | |
365 | param.ident.span, | |
366 | "if this is intentional, prefix it with an underscore", | |
367 | format!("_{}", param.ident.name), | |
368 | Applicability::MaybeIncorrect, | |
369 | ); | |
370 | } | |
371 | diag.span_note( | |
372 | param.uses.iter().map(|x| x.span).collect::<Vec<_>>(), | |
373 | "parameter used here", | |
374 | ); | |
375 | }, | |
376 | ); | |
5e7ed085 | 377 | } |
5e7ed085 | 378 | } |
f2b60f7d | 379 | self.params.clear(); |
5e7ed085 | 380 | } |
5e7ed085 | 381 | } |
f2b60f7d | 382 | } |
5e7ed085 | 383 | |
f2b60f7d FG |
384 | fn has_matching_substs(kind: FnKind, substs: SubstsRef<'_>) -> bool { |
385 | match kind { | |
386 | FnKind::Fn => true, | |
387 | FnKind::TraitFn => substs.iter().enumerate().all(|(idx, subst)| match subst.unpack() { | |
388 | GenericArgKind::Lifetime(_) => true, | |
389 | GenericArgKind::Type(ty) => matches!(*ty.kind(), ty::Param(ty) if ty.index as usize == idx), | |
390 | GenericArgKind::Const(c) => matches!(c.kind(), ConstKind::Param(c) if c.index as usize == idx), | |
391 | }), | |
392 | #[allow(trivial_casts)] | |
393 | FnKind::ImplTraitFn(expected_substs) => substs as *const _ as usize == expected_substs, | |
5e7ed085 FG |
394 | } |
395 | } |