1 use std::collections::VecDeque;
3 use clippy_utils::diagnostics::span_lint_and_sugg;
4 use itertools::{izip, Itertools};
5 use rustc_ast::{walk_list, Label, Mutability};
6 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
7 use rustc_errors::Applicability;
8 use rustc_hir::def::Res;
9 use rustc_hir::intravisit::{walk_expr, FnKind, Visitor};
11 Arm, Block, Body, Expr, ExprKind, Guard, HirId, Let, Local, Pat, PatKind, Path, PathSegment, QPath, Stmt, StmtKind,
14 use rustc_lint::{LateContext, LateLintPass};
16 use rustc_middle::ty::{Ty, TyCtxt, TypeckResults};
17 use rustc_session::{declare_lint_pass, declare_tool_lint};
18 use rustc_span::symbol::kw;
19 use rustc_span::symbol::Ident;
22 declare_clippy_lint! {
24 /// Checks for arguments that is only used in recursion with no side-effects.
25 /// The arguments can be involved in calculations and assignments but as long as
26 /// the calculations have no side-effects (function calls or mutating dereference)
27 /// and the assigned variables are also only in recursion, it is useless.
29 /// ### Why is this bad?
30 /// The could contain a useless calculation and can make function simpler.
33 /// It could not catch the variable that has no side effects but only used in recursion.
37 /// fn f(a: usize, b: usize) -> usize {
45 /// # print!("{}", f(1, 1));
50 /// fn f(a: usize) -> usize {
58 /// # print!("{}", f(1));
61 #[clippy::version = "1.60.0"]
62 pub ONLY_USED_IN_RECURSION,
64 "default lint description"
66 declare_lint_pass!(OnlyUsedInRecursion => [ONLY_USED_IN_RECURSION]);
68 impl<'tcx> LateLintPass<'tcx> for OnlyUsedInRecursion {
71 cx: &LateContext<'tcx>,
73 _: &'tcx rustc_hir::FnDecl<'tcx>,
74 body: &'tcx Body<'tcx>,
78 if let FnKind::ItemFn(ident, ..) | FnKind::Method(ident, ..) = kind {
79 let ty_res = cx.typeck_results();
84 let mut v = Vec::new();
85 param.pat.each_binding(|_, hir_id, span, ident| {
86 v.push((hir_id, span, ident));
91 FnKind::Method(..) => 1,
94 .filter(|(_, _, ident)| !ident.name.as_str().starts_with('_'))
97 let params = body.params.iter().map(|param| param.pat).collect();
99 let mut visitor = SideEffectVisit {
100 graph: FxHashMap::default(),
101 has_side_effect: FxHashSet::default(),
102 ret_vars: Vec::new(),
103 contains_side_effect: false,
104 break_vars: FxHashMap::default(),
107 is_method: matches!(kind, FnKind::Method(..)),
112 visitor.visit_expr(&body.value);
113 let vars = std::mem::take(&mut visitor.ret_vars);
114 visitor.add_side_effect(vars);
116 let mut queue = visitor.has_side_effect.iter().copied().collect::<VecDeque<_>>();
118 while let Some(id) = queue.pop_front() {
119 if let Some(next) = visitor.graph.get(&id) {
121 if !visitor.has_side_effect.contains(i) {
122 visitor.has_side_effect.insert(*i);
129 for (id, span, ident) in param_span {
130 if !visitor.has_side_effect.contains(&id) {
133 ONLY_USED_IN_RECURSION,
135 "parameter is only used in recursion with no side-effects",
136 "if this is intentional, prefix with an underscore",
137 format!("_{}", ident.name.as_str()),
138 Applicability::MaybeIncorrect,
146 pub fn is_primitive(ty: Ty<'_>) -> bool {
148 ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Str => true,
149 ty::Ref(_, t, _) => is_primitive(t),
154 pub fn is_array(ty: Ty<'_>) -> bool {
156 ty::Array(..) | ty::Slice(..) => true,
157 ty::Ref(_, t, _) => is_array(t),
162 pub struct SideEffectVisit<'tcx> {
163 graph: FxHashMap<HirId, FxHashSet<HirId>>,
164 has_side_effect: FxHashSet<HirId>,
165 // bool for if the variable was dereferenced from mutable reference
166 ret_vars: Vec<(HirId, bool)>,
167 contains_side_effect: bool,
169 break_vars: FxHashMap<Ident, Vec<(HirId, bool)>>,
170 params: Vec<&'tcx Pat<'tcx>>,
173 ty_res: &'tcx TypeckResults<'tcx>,
174 ty_ctx: TyCtxt<'tcx>,
177 impl<'tcx> Visitor<'tcx> for SideEffectVisit<'tcx> {
178 fn visit_block(&mut self, b: &'tcx Block<'tcx>) {
179 b.stmts.iter().for_each(|stmt| {
180 self.visit_stmt(stmt);
181 self.ret_vars.clear();
183 walk_list!(self, visit_expr, b.expr);
186 fn visit_stmt(&mut self, s: &'tcx Stmt<'tcx>) {
188 StmtKind::Local(Local {
189 pat, init: Some(init), ..
191 self.visit_pat_expr(pat, init);
193 StmtKind::Item(i) => {
194 let item = self.ty_ctx.hir().item(i);
195 self.visit_item(item);
197 StmtKind::Expr(e) | StmtKind::Semi(e) => self.visit_expr(e),
198 StmtKind::Local(_) => {},
202 fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
203 debug_assert!(self.ret_vars.is_empty());
205 ExprKind::Array(exprs) | ExprKind::Tup(exprs) => {
206 self.ret_vars = exprs
209 self.visit_expr(expr);
210 std::mem::take(&mut self.ret_vars)
214 ExprKind::Call(callee, args) => self.visit_fn(callee, args),
215 ExprKind::MethodCall(path, args, _) => self.visit_method_call(path, args),
216 ExprKind::Binary(_, lhs, rhs) => {
217 self.visit_bin_op(lhs, rhs);
219 ExprKind::Unary(op, expr) => self.visit_un_op(op, expr),
220 ExprKind::Let(Let { pat, init, .. }) => self.visit_pat_expr(pat, init),
221 ExprKind::If(bind, then_expr, else_expr) => {
222 self.visit_if(bind, then_expr, else_expr);
224 ExprKind::Match(expr, arms, _) => self.visit_match(expr, arms),
225 ExprKind::Closure(_, _, body_id, _, _) => {
226 let body = self.ty_ctx.hir().body(body_id);
227 self.visit_body(body);
228 let vars = std::mem::take(&mut self.ret_vars);
229 self.add_side_effect(vars);
231 ExprKind::Loop(block, label, _, _) | ExprKind::Block(block, label) => {
232 self.visit_block_label(block, label);
234 ExprKind::Assign(bind, expr, _) => {
235 self.visit_assign(bind, expr);
237 ExprKind::AssignOp(_, bind, expr) => {
238 self.visit_assign(bind, expr);
239 self.visit_bin_op(bind, expr);
241 ExprKind::Field(expr, _) => {
242 self.visit_expr(expr);
243 if matches!(self.ty_res.expr_ty(expr).kind(), ty::Ref(_, _, Mutability::Mut)) {
244 self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
247 ExprKind::Index(expr, index) => {
248 self.visit_expr(expr);
249 let mut vars = std::mem::take(&mut self.ret_vars);
250 self.visit_expr(index);
251 self.ret_vars.append(&mut vars);
253 if !is_array(self.ty_res.expr_ty(expr)) {
254 self.add_side_effect(self.ret_vars.clone());
255 } else if matches!(self.ty_res.expr_ty(expr).kind(), ty::Ref(_, _, Mutability::Mut)) {
256 self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
259 ExprKind::Break(dest, Some(expr)) => {
260 self.visit_expr(expr);
261 if let Some(label) = dest.label {
264 .or_insert(Vec::new())
265 .append(&mut self.ret_vars);
267 self.contains_side_effect = true;
269 ExprKind::Ret(Some(expr)) => {
270 self.visit_expr(expr);
271 let vars = std::mem::take(&mut self.ret_vars);
272 self.add_side_effect(vars);
273 self.contains_side_effect = true;
275 ExprKind::Break(_, None) | ExprKind::Continue(_) | ExprKind::Ret(None) => {
276 self.contains_side_effect = true;
278 ExprKind::Struct(_, exprs, expr) => {
279 let mut ret_vars = exprs
282 self.visit_expr(field.expr);
283 std::mem::take(&mut self.ret_vars)
287 walk_list!(self, visit_expr, expr);
288 self.ret_vars.append(&mut ret_vars);
290 _ => walk_expr(self, ex),
294 fn visit_path(&mut self, path: &'tcx Path<'tcx>, _id: HirId) {
295 if let Res::Local(id) = path.res {
296 self.ret_vars.push((id, false));
301 impl<'tcx> SideEffectVisit<'tcx> {
302 fn visit_assign(&mut self, lhs: &'tcx Expr<'tcx>, rhs: &'tcx Expr<'tcx>) {
303 // Just support array and tuple unwrapping for now.
305 // ex) `(a, b) = (c, d);`
306 // The graph would look like this:
310 // This would minimize the connection of the side-effect graph.
311 match (&lhs.kind, &rhs.kind) {
312 (ExprKind::Array(lhs), ExprKind::Array(rhs)) | (ExprKind::Tup(lhs), ExprKind::Tup(rhs)) => {
313 // if not, it is a compile error
314 debug_assert!(lhs.len() == rhs.len());
315 izip!(*lhs, *rhs).for_each(|(lhs, rhs)| self.visit_assign(lhs, rhs));
317 // in other assigns, we have to connect all each other
318 // because they can be connected somehow
320 self.visit_expr(lhs);
321 let lhs_vars = std::mem::take(&mut self.ret_vars);
322 self.visit_expr(rhs);
323 let rhs_vars = std::mem::take(&mut self.ret_vars);
324 self.connect_assign(&lhs_vars, &rhs_vars);
329 fn visit_block_label(&mut self, block: &'tcx Block<'tcx>, label: Option<Label>) {
330 self.visit_block(block);
331 let _ = label.and_then(|label| {
333 .remove(&label.ident)
334 .map(|mut break_vars| self.ret_vars.append(&mut break_vars))
338 fn visit_bin_op(&mut self, lhs: &'tcx Expr<'tcx>, rhs: &'tcx Expr<'tcx>) {
339 self.visit_expr(lhs);
340 let mut ret_vars = std::mem::take(&mut self.ret_vars);
341 self.visit_expr(rhs);
342 self.ret_vars.append(&mut ret_vars);
343 if !is_primitive(self.ty_res.expr_ty(lhs)) || !is_primitive(self.ty_res.expr_ty(rhs)) {
344 self.ret_vars.iter().for_each(|id| {
345 self.has_side_effect.insert(id.0);
347 self.contains_side_effect = true;
351 fn visit_un_op(&mut self, op: UnOp, expr: &'tcx Expr<'tcx>) {
352 self.visit_expr(expr);
353 let ty = self.ty_res.expr_ty(expr);
354 // dereferencing a reference has no side-effect
355 if !is_primitive(ty) && !matches!((op, ty.kind()), (UnOp::Deref, ty::Ref(..))) {
356 self.add_side_effect(self.ret_vars.clone());
359 if matches!((op, ty.kind()), (UnOp::Deref, ty::Ref(_, _, Mutability::Mut))) {
360 self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
364 fn visit_pat_expr(&mut self, pat: &'tcx Pat<'tcx>, expr: &'tcx Expr<'tcx>) {
365 match (&pat.kind, &expr.kind) {
366 (PatKind::Tuple(pats, _), ExprKind::Tup(exprs)) => {
367 self.ret_vars = izip!(*pats, *exprs)
368 .flat_map(|(pat, expr)| {
369 self.visit_pat_expr(pat, expr);
370 std::mem::take(&mut self.ret_vars)
374 (PatKind::Slice(front_exprs, _, back_exprs), ExprKind::Array(exprs)) => {
375 let mut vars = izip!(*front_exprs, *exprs)
376 .flat_map(|(pat, expr)| {
377 self.visit_pat_expr(pat, expr);
378 std::mem::take(&mut self.ret_vars)
381 self.ret_vars = izip!(back_exprs.iter().rev(), exprs.iter().rev())
382 .flat_map(|(pat, expr)| {
383 self.visit_pat_expr(pat, expr);
384 std::mem::take(&mut self.ret_vars)
387 self.ret_vars.append(&mut vars);
390 let mut lhs_vars = Vec::new();
391 pat.each_binding(|_, id, _, _| lhs_vars.push((id, false)));
392 self.visit_expr(expr);
393 let rhs_vars = std::mem::take(&mut self.ret_vars);
394 self.connect_assign(&lhs_vars, &rhs_vars);
395 self.ret_vars = rhs_vars;
400 fn visit_fn(&mut self, callee: &'tcx Expr<'tcx>, args: &'tcx [Expr<'tcx>]) {
401 self.visit_expr(callee);
402 let mut ret_vars = std::mem::take(&mut self.ret_vars);
403 self.add_side_effect(ret_vars.clone());
407 if let ExprKind::Path(QPath::Resolved(_, path)) = callee.kind;
408 if let Res::Def(..) = path.res;
409 if path.segments.len() == 1;
410 let ident = path.segments.last().unwrap().ident;
411 if ident == self.fn_ident;
413 izip!(self.params.clone(), args)
414 .for_each(|(pat, expr)| {
415 self.visit_pat_expr(pat, expr);
416 self.ret_vars.clear();
419 // This would set arguments used in closure that does not have side-effect.
420 // Closure itself can be detected whether there is a side-effect, but the
421 // value of variable that is holding closure can change.
422 // So, we just check the variables.
426 self.visit_expr(expr);
427 std::mem::take(&mut self.ret_vars)
432 self.has_side_effect.insert(id.0);
436 self.contains_side_effect = true;
440 self.ret_vars.append(&mut ret_vars);
443 fn visit_method_call(&mut self, path: &'tcx PathSegment<'tcx>, args: &'tcx [Expr<'tcx>]) {
446 if path.ident == self.fn_ident;
447 if let ExprKind::Path(QPath::Resolved(_, path)) = args.first().unwrap().kind;
448 if let Res::Local(..) = path.res;
449 let ident = path.segments.last().unwrap().ident;
450 if ident.name == kw::SelfLower;
452 izip!(self.params.clone(), args.iter())
453 .for_each(|(pat, expr)| {
454 self.visit_pat_expr(pat, expr);
455 self.ret_vars.clear();
461 self.visit_expr(expr);
462 std::mem::take(&mut self.ret_vars)
467 self.has_side_effect.insert(a.0);
471 self.contains_side_effect = true;
476 fn visit_if(&mut self, bind: &'tcx Expr<'tcx>, then_expr: &'tcx Expr<'tcx>, else_expr: Option<&'tcx Expr<'tcx>>) {
477 let contains_side_effect = self.contains_side_effect;
478 self.contains_side_effect = false;
479 self.visit_expr(bind);
480 let mut vars = std::mem::take(&mut self.ret_vars);
481 self.visit_expr(then_expr);
482 let mut then_vars = std::mem::take(&mut self.ret_vars);
483 walk_list!(self, visit_expr, else_expr);
484 if self.contains_side_effect {
485 self.add_side_effect(vars.clone());
487 self.contains_side_effect |= contains_side_effect;
488 self.ret_vars.append(&mut vars);
489 self.ret_vars.append(&mut then_vars);
492 fn visit_match(&mut self, expr: &'tcx Expr<'tcx>, arms: &'tcx [Arm<'tcx>]) {
493 self.visit_expr(expr);
494 let mut expr_vars = std::mem::take(&mut self.ret_vars);
498 let contains_side_effect = self.contains_side_effect;
499 self.contains_side_effect = false;
500 // this would visit `expr` multiple times
501 // but couldn't think of a better way
502 self.visit_pat_expr(arm.pat, expr);
503 let mut vars = std::mem::take(&mut self.ret_vars);
504 let _ = arm.guard.as_ref().map(|guard| {
505 self.visit_expr(match guard {
506 Guard::If(expr) | Guard::IfLet(_, expr) => expr,
508 vars.append(&mut self.ret_vars);
510 self.visit_expr(arm.body);
511 if self.contains_side_effect {
512 self.add_side_effect(vars.clone());
513 self.add_side_effect(expr_vars.clone());
515 self.contains_side_effect |= contains_side_effect;
516 vars.append(&mut self.ret_vars);
520 self.ret_vars.append(&mut expr_vars);
523 fn connect_assign(&mut self, lhs: &[(HirId, bool)], rhs: &[(HirId, bool)]) {
524 // if mutable dereference is on assignment it can have side-effect
525 // (this can lead to parameter mutable dereference and change the original value)
526 // too hard to detect whether this value is from parameter, so this would all
527 // check mutable dereference assignment to side effect
528 lhs.iter().filter(|(_, b)| *b).for_each(|(id, _)| {
529 self.has_side_effect.insert(*id);
530 self.contains_side_effect = true;
533 // there is no connection
534 if lhs.is_empty() || rhs.is_empty() {
538 // by connected rhs in cycle, the connections would decrease
539 // from `n * m` to `n + m`
540 // where `n` and `m` are length of `lhs` and `rhs`.
542 // unwrap is possible since rhs is not empty
543 let rhs_first = rhs.first().unwrap();
544 for (id, _) in lhs.iter() {
547 .or_insert_with(FxHashSet::default)
548 .insert(rhs_first.0);
551 let rhs = rhs.iter();
552 izip!(rhs.clone().cycle().skip(1), rhs).for_each(|(from, to)| {
553 self.graph.entry(from.0).or_insert_with(FxHashSet::default).insert(to.0);
557 fn add_side_effect(&mut self, v: Vec<(HirId, bool)>) {
559 self.has_side_effect.insert(id);
560 self.contains_side_effect = true;