1 use std::collections::VecDeque;
3 use clippy_utils::diagnostics::span_lint_and_sugg;
4 use clippy_utils::is_lint_allowed;
5 use itertools::{izip, Itertools};
6 use rustc_ast::{walk_list, Label, Mutability};
7 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
8 use rustc_errors::Applicability;
9 use rustc_hir::def::{DefKind, Res};
10 use rustc_hir::def_id::DefId;
11 use rustc_hir::definitions::{DefPathData, DisambiguatedDefPathData};
12 use rustc_hir::intravisit::{walk_expr, walk_stmt, FnKind, Visitor};
14 Arm, Block, Body, Expr, ExprKind, Guard, HirId, ImplicitSelfKind, Let, Local, Pat, PatKind, Path, PathSegment,
15 QPath, Stmt, StmtKind, TyKind, UnOp,
17 use rustc_lint::{LateContext, LateLintPass};
19 use rustc_middle::ty::{Ty, TyCtxt, TypeckResults};
20 use rustc_session::{declare_lint_pass, declare_tool_lint};
21 use rustc_span::symbol::kw;
22 use rustc_span::symbol::Ident;
25 declare_clippy_lint! {
27 /// Checks for arguments that are only used in recursion with no side-effects.
29 /// ### Why is this bad?
30 /// It could contain a useless calculation and can make function simpler.
32 /// The arguments can be involved in calculations and assignments but as long as
33 /// the calculations have no side-effects (function calls or mutating dereference)
34 /// and the assigned variables are also only in recursion, it is useless.
36 /// ### Known problems
37 /// Too many code paths in the linting code are currently untested and prone to produce false
38 /// positives or are prone to have performance implications.
40 /// In some cases, this would not catch all useless arguments.
43 /// fn foo(a: usize, b: usize) -> usize {
44 /// let f = |x| x + 1;
54 /// For example, the argument `b` is only used in recursion, but the lint would not catch it.
56 /// List of some examples that can not be caught:
57 /// - binary operation of non-primitive types
59 /// - some `break` relative operations
60 /// - struct pattern binding
62 /// Also, when you recurse the function name with path segments, it is not possible to detect.
66 /// fn f(a: usize, b: usize) -> usize {
74 /// # print!("{}", f(1, 1));
79 /// fn f(a: usize) -> usize {
87 /// # print!("{}", f(1));
90 #[clippy::version = "1.60.0"]
91 pub ONLY_USED_IN_RECURSION,
93 "arguments that is only used in recursion can be removed"
95 declare_lint_pass!(OnlyUsedInRecursion => [ONLY_USED_IN_RECURSION]);
97 impl<'tcx> LateLintPass<'tcx> for OnlyUsedInRecursion {
100 cx: &LateContext<'tcx>,
102 decl: &'tcx rustc_hir::FnDecl<'tcx>,
103 body: &'tcx Body<'tcx>,
107 if is_lint_allowed(cx, ONLY_USED_IN_RECURSION, id) {
110 if let FnKind::ItemFn(ident, ..) | FnKind::Method(ident, ..) = kind {
111 let def_id = id.owner.to_def_id();
112 let data = cx.tcx.def_path(def_id).data;
115 match data.get(data.len() - 2) {
116 Some(DisambiguatedDefPathData {
117 data: DefPathData::Impl,
119 }) if *disambiguator != 0 => return,
124 let has_self = !matches!(decl.implicit_self, ImplicitSelfKind::None);
126 let ty_res = cx.typeck_results();
127 let param_span = body
131 let mut v = Vec::new();
132 param.pat.each_binding(|_, hir_id, span, ident| {
133 v.push((hir_id, span, ident));
137 .skip(if has_self { 1 } else { 0 })
138 .filter(|(_, _, ident)| !ident.name.as_str().starts_with('_'))
141 let params = body.params.iter().map(|param| param.pat).collect();
143 let mut visitor = SideEffectVisit {
144 graph: FxHashMap::default(),
145 has_side_effect: FxHashSet::default(),
146 ret_vars: Vec::new(),
147 contains_side_effect: false,
148 break_vars: FxHashMap::default(),
152 is_method: matches!(kind, FnKind::Method(..)),
156 visited_exprs: FxHashSet::default(),
159 visitor.visit_expr(&body.value);
160 let vars = std::mem::take(&mut visitor.ret_vars);
161 // this would set the return variables to side effect
162 visitor.add_side_effect(vars);
164 let mut queue = visitor.has_side_effect.iter().copied().collect::<VecDeque<_>>();
166 // a simple BFS to check all the variables that have side effect
167 while let Some(id) = queue.pop_front() {
168 if let Some(next) = visitor.graph.get(&id) {
170 if !visitor.has_side_effect.contains(i) {
171 visitor.has_side_effect.insert(*i);
178 for (id, span, ident) in param_span {
179 // if the variable is not used in recursion, it would be marked as unused
180 if !visitor.has_side_effect.contains(&id) {
181 let mut queue = VecDeque::new();
182 let mut visited = FxHashSet::default();
186 // a simple BFS to check the graph can reach to itself
187 // if it can't, it means the variable is never used in recursion
188 while let Some(id) = queue.pop_front() {
189 if let Some(next) = visitor.graph.get(&id) {
191 if !visited.contains(i) {
199 if visited.contains(&id) {
202 ONLY_USED_IN_RECURSION,
204 "parameter is only used in recursion",
205 "if this is intentional, prefix with an underscore",
206 format!("_{}", ident.name.as_str()),
207 Applicability::MaybeIncorrect,
216 pub fn is_primitive(ty: Ty<'_>) -> bool {
217 let ty = ty.peel_refs();
218 ty.is_primitive() || ty.is_str()
221 pub fn is_array(ty: Ty<'_>) -> bool {
222 let ty = ty.peel_refs();
223 ty.is_array() || ty.is_array_slice()
226 /// This builds the graph of side effect.
227 /// The edge `a -> b` means if `a` has side effect, `b` will have side effect.
229 /// There are some example in following code:
232 /// let a = b; // a -> b
233 /// let (c, d) = (a, b); // c -> b, d -> b
235 /// let e = if a == 0 { // e -> a
241 pub struct SideEffectVisit<'tcx> {
242 graph: FxHashMap<HirId, FxHashSet<HirId>>,
243 has_side_effect: FxHashSet<HirId>,
244 // bool for if the variable was dereferenced from mutable reference
245 ret_vars: Vec<(HirId, bool)>,
246 contains_side_effect: bool,
248 break_vars: FxHashMap<Ident, Vec<(HirId, bool)>>,
249 params: Vec<&'tcx Pat<'tcx>>,
254 ty_res: &'tcx TypeckResults<'tcx>,
256 visited_exprs: FxHashSet<HirId>,
259 impl<'tcx> Visitor<'tcx> for SideEffectVisit<'tcx> {
260 fn visit_stmt(&mut self, s: &'tcx Stmt<'tcx>) {
262 StmtKind::Local(Local {
263 pat, init: Some(init), ..
265 self.visit_pat_expr(pat, init, false);
267 StmtKind::Item(_) | StmtKind::Expr(_) | StmtKind::Semi(_) => {
270 StmtKind::Local(_) => {},
272 self.ret_vars.clear();
275 fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
276 if !self.visited_exprs.insert(ex.hir_id) {
280 ExprKind::Array(exprs) | ExprKind::Tup(exprs) => {
281 self.ret_vars = exprs
284 self.visit_expr(expr);
285 std::mem::take(&mut self.ret_vars)
289 ExprKind::Call(callee, args) => self.visit_fn(callee, args),
290 ExprKind::MethodCall(path, args, _) => self.visit_method_call(path, args),
291 ExprKind::Binary(_, lhs, rhs) => {
292 self.visit_bin_op(lhs, rhs);
294 ExprKind::Unary(op, expr) => self.visit_un_op(op, expr),
295 ExprKind::Let(Let { pat, init, .. }) => self.visit_pat_expr(pat, init, false),
296 ExprKind::If(bind, then_expr, else_expr) => {
297 self.visit_if(bind, then_expr, else_expr);
299 ExprKind::Match(expr, arms, _) => self.visit_match(expr, arms),
300 // since analysing the closure is not easy, just set all variables in it to side-effect
301 ExprKind::Closure(_, _, body_id, _, _) => {
302 let body = self.tcx.hir().body(body_id);
303 self.visit_body(body);
304 let vars = std::mem::take(&mut self.ret_vars);
305 self.add_side_effect(vars);
307 ExprKind::Loop(block, label, _, _) | ExprKind::Block(block, label) => {
308 self.visit_block_label(block, label);
310 ExprKind::Assign(bind, expr, _) => {
311 self.visit_assign(bind, expr);
313 ExprKind::AssignOp(_, bind, expr) => {
314 self.visit_assign(bind, expr);
315 self.visit_bin_op(bind, expr);
317 ExprKind::Field(expr, _) => {
318 self.visit_expr(expr);
319 if matches!(self.ty_res.expr_ty(expr).kind(), ty::Ref(_, _, Mutability::Mut)) {
320 self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
323 ExprKind::Index(expr, index) => {
324 self.visit_expr(expr);
325 let mut vars = std::mem::take(&mut self.ret_vars);
326 self.visit_expr(index);
327 self.ret_vars.append(&mut vars);
329 if !is_array(self.ty_res.expr_ty(expr)) {
330 self.add_side_effect(self.ret_vars.clone());
331 } else if matches!(self.ty_res.expr_ty(expr).kind(), ty::Ref(_, _, Mutability::Mut)) {
332 self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
335 ExprKind::Break(dest, Some(expr)) => {
336 self.visit_expr(expr);
337 if let Some(label) = dest.label {
340 .or_insert(Vec::new())
341 .append(&mut self.ret_vars);
343 self.contains_side_effect = true;
345 ExprKind::Ret(Some(expr)) => {
346 self.visit_expr(expr);
347 let vars = std::mem::take(&mut self.ret_vars);
348 self.add_side_effect(vars);
349 self.contains_side_effect = true;
351 ExprKind::Break(_, None) | ExprKind::Continue(_) | ExprKind::Ret(None) => {
352 self.contains_side_effect = true;
354 ExprKind::Struct(_, exprs, expr) => {
355 let mut ret_vars = exprs
358 self.visit_expr(field.expr);
359 std::mem::take(&mut self.ret_vars)
363 walk_list!(self, visit_expr, expr);
364 self.ret_vars.append(&mut ret_vars);
366 _ => walk_expr(self, ex),
370 fn visit_path(&mut self, path: &'tcx Path<'tcx>, _id: HirId) {
371 if let Res::Local(id) = path.res {
372 self.ret_vars.push((id, false));
377 impl<'tcx> SideEffectVisit<'tcx> {
378 fn visit_assign(&mut self, lhs: &'tcx Expr<'tcx>, rhs: &'tcx Expr<'tcx>) {
379 // Just support array and tuple unwrapping for now.
381 // ex) `(a, b) = (c, d);`
382 // The graph would look like this:
386 // This would minimize the connection of the side-effect graph.
387 match (&lhs.kind, &rhs.kind) {
388 (ExprKind::Array(lhs), ExprKind::Array(rhs)) | (ExprKind::Tup(lhs), ExprKind::Tup(rhs)) => {
389 // if not, it is a compile error
390 debug_assert!(lhs.len() == rhs.len());
391 izip!(*lhs, *rhs).for_each(|(lhs, rhs)| self.visit_assign(lhs, rhs));
393 // in other assigns, we have to connect all each other
394 // because they can be connected somehow
396 self.visit_expr(lhs);
397 let lhs_vars = std::mem::take(&mut self.ret_vars);
398 self.visit_expr(rhs);
399 let rhs_vars = std::mem::take(&mut self.ret_vars);
400 self.connect_assign(&lhs_vars, &rhs_vars, false);
405 fn visit_block_label(&mut self, block: &'tcx Block<'tcx>, label: Option<Label>) {
406 self.visit_block(block);
407 let _ = label.and_then(|label| {
409 .remove(&label.ident)
410 .map(|mut break_vars| self.ret_vars.append(&mut break_vars))
414 fn visit_bin_op(&mut self, lhs: &'tcx Expr<'tcx>, rhs: &'tcx Expr<'tcx>) {
415 self.visit_expr(lhs);
416 let mut ret_vars = std::mem::take(&mut self.ret_vars);
417 self.visit_expr(rhs);
418 self.ret_vars.append(&mut ret_vars);
420 // the binary operation between non primitive values are overloaded operators
421 // so they can have side-effects
422 if !is_primitive(self.ty_res.expr_ty(lhs)) || !is_primitive(self.ty_res.expr_ty(rhs)) {
423 self.ret_vars.iter().for_each(|id| {
424 self.has_side_effect.insert(id.0);
426 self.contains_side_effect = true;
430 fn visit_un_op(&mut self, op: UnOp, expr: &'tcx Expr<'tcx>) {
431 self.visit_expr(expr);
432 let ty = self.ty_res.expr_ty(expr);
433 // dereferencing a reference has no side-effect
434 if !is_primitive(ty) && !matches!((op, ty.kind()), (UnOp::Deref, ty::Ref(..))) {
435 self.add_side_effect(self.ret_vars.clone());
438 if matches!((op, ty.kind()), (UnOp::Deref, ty::Ref(_, _, Mutability::Mut))) {
439 self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
443 fn visit_pat_expr(&mut self, pat: &'tcx Pat<'tcx>, expr: &'tcx Expr<'tcx>, connect_self: bool) {
444 match (&pat.kind, &expr.kind) {
445 (PatKind::Tuple(pats, _), ExprKind::Tup(exprs)) => {
446 self.ret_vars = izip!(*pats, *exprs)
447 .flat_map(|(pat, expr)| {
448 self.visit_pat_expr(pat, expr, connect_self);
449 std::mem::take(&mut self.ret_vars)
453 (PatKind::Slice(front_exprs, _, back_exprs), ExprKind::Array(exprs)) => {
454 let mut vars = izip!(*front_exprs, *exprs)
455 .flat_map(|(pat, expr)| {
456 self.visit_pat_expr(pat, expr, connect_self);
457 std::mem::take(&mut self.ret_vars)
460 self.ret_vars = izip!(back_exprs.iter().rev(), exprs.iter().rev())
461 .flat_map(|(pat, expr)| {
462 self.visit_pat_expr(pat, expr, connect_self);
463 std::mem::take(&mut self.ret_vars)
466 self.ret_vars.append(&mut vars);
469 let mut lhs_vars = Vec::new();
470 pat.each_binding(|_, id, _, _| lhs_vars.push((id, false)));
471 self.visit_expr(expr);
472 let rhs_vars = std::mem::take(&mut self.ret_vars);
473 self.connect_assign(&lhs_vars, &rhs_vars, connect_self);
474 self.ret_vars = rhs_vars;
479 fn visit_fn(&mut self, callee: &'tcx Expr<'tcx>, args: &'tcx [Expr<'tcx>]) {
480 self.visit_expr(callee);
481 let mut ret_vars = std::mem::take(&mut self.ret_vars);
482 self.add_side_effect(ret_vars.clone());
484 let mut is_recursive = false;
488 if let ExprKind::Path(QPath::Resolved(_, path)) = callee.kind;
489 if let Res::Def(DefKind::Fn, def_id) = path.res;
490 if self.fn_def_id == def_id;
497 if !self.has_self && self.is_method;
498 if let ExprKind::Path(QPath::TypeRelative(ty, segment)) = callee.kind;
499 if segment.ident == self.fn_ident;
500 if let TyKind::Path(QPath::Resolved(_, path)) = ty.kind;
501 if let Res::SelfTy{ .. } = path.res;
508 izip!(self.params.clone(), args).for_each(|(pat, expr)| {
509 self.visit_pat_expr(pat, expr, true);
510 self.ret_vars.clear();
513 // This would set arguments used in closure that does not have side-effect.
514 // Closure itself can be detected whether there is a side-effect, but the
515 // value of variable that is holding closure can change.
516 // So, we just check the variables.
520 self.visit_expr(expr);
521 std::mem::take(&mut self.ret_vars)
526 self.has_side_effect.insert(id.0);
530 self.contains_side_effect = true;
533 self.ret_vars.append(&mut ret_vars);
536 fn visit_method_call(&mut self, path: &'tcx PathSegment<'tcx>, args: &'tcx [Expr<'tcx>]) {
539 if path.ident == self.fn_ident;
540 if let ExprKind::Path(QPath::Resolved(_, path)) = args.first().unwrap().kind;
541 if let Res::Local(..) = path.res;
542 let ident = path.segments.last().unwrap().ident;
543 if ident.name == kw::SelfLower;
545 izip!(self.params.clone(), args.iter())
546 .for_each(|(pat, expr)| {
547 self.visit_pat_expr(pat, expr, true);
548 self.ret_vars.clear();
554 self.visit_expr(expr);
555 std::mem::take(&mut self.ret_vars)
560 self.has_side_effect.insert(a.0);
564 self.contains_side_effect = true;
569 fn visit_if(&mut self, bind: &'tcx Expr<'tcx>, then_expr: &'tcx Expr<'tcx>, else_expr: Option<&'tcx Expr<'tcx>>) {
570 let contains_side_effect = self.contains_side_effect;
571 self.contains_side_effect = false;
572 self.visit_expr(bind);
573 let mut vars = std::mem::take(&mut self.ret_vars);
574 self.visit_expr(then_expr);
575 let mut then_vars = std::mem::take(&mut self.ret_vars);
576 walk_list!(self, visit_expr, else_expr);
577 if self.contains_side_effect {
578 self.add_side_effect(vars.clone());
580 self.contains_side_effect |= contains_side_effect;
581 self.ret_vars.append(&mut vars);
582 self.ret_vars.append(&mut then_vars);
585 fn visit_match(&mut self, expr: &'tcx Expr<'tcx>, arms: &'tcx [Arm<'tcx>]) {
586 self.visit_expr(expr);
587 let mut expr_vars = std::mem::take(&mut self.ret_vars);
591 let contains_side_effect = self.contains_side_effect;
592 self.contains_side_effect = false;
593 // this would visit `expr` multiple times
594 // but couldn't think of a better way
595 self.visit_pat_expr(arm.pat, expr, false);
596 let mut vars = std::mem::take(&mut self.ret_vars);
597 let _ = arm.guard.as_ref().map(|guard| {
598 self.visit_expr(match guard {
599 Guard::If(expr) | Guard::IfLet(Let { init: expr, .. }) => expr,
601 vars.append(&mut self.ret_vars);
603 self.visit_expr(arm.body);
604 if self.contains_side_effect {
605 self.add_side_effect(vars.clone());
606 self.add_side_effect(expr_vars.clone());
608 self.contains_side_effect |= contains_side_effect;
609 vars.append(&mut self.ret_vars);
613 self.ret_vars.append(&mut expr_vars);
616 fn connect_assign(&mut self, lhs: &[(HirId, bool)], rhs: &[(HirId, bool)], connect_self: bool) {
617 // if mutable dereference is on assignment it can have side-effect
618 // (this can lead to parameter mutable dereference and change the original value)
619 // too hard to detect whether this value is from parameter, so this would all
620 // check mutable dereference assignment to side effect
621 lhs.iter().filter(|(_, b)| *b).for_each(|(id, _)| {
622 self.has_side_effect.insert(*id);
623 self.contains_side_effect = true;
626 // there is no connection
627 if lhs.is_empty() || rhs.is_empty() {
631 // by connected rhs in cycle, the connections would decrease
632 // from `n * m` to `n + m`
633 // where `n` and `m` are length of `lhs` and `rhs`.
635 // unwrap is possible since rhs is not empty
636 let rhs_first = rhs.first().unwrap();
637 for (id, _) in lhs.iter() {
638 if connect_self || *id != rhs_first.0 {
641 .or_insert_with(FxHashSet::default)
642 .insert(rhs_first.0);
646 let rhs = rhs.iter();
647 izip!(rhs.clone().cycle().skip(1), rhs).for_each(|(from, to)| {
648 if connect_self || from.0 != to.0 {
649 self.graph.entry(from.0).or_insert_with(FxHashSet::default).insert(to.0);
654 fn add_side_effect(&mut self, v: Vec<(HirId, bool)>) {
656 self.has_side_effect.insert(id);
657 self.contains_side_effect = true;