clippy_lints/src/only_used_in_recursion.rs

   1 use std::collections::VecDeque;
   2
   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};
  10 use rustc_hir::{
  11     Arm, Block, Body, Expr, ExprKind, Guard, HirId, Let, Local, Pat, PatKind, Path, PathSegment, QPath, Stmt, StmtKind,
  12     UnOp,
  13 };
  14 use rustc_lint::{LateContext, LateLintPass};
  15 use rustc_middle::ty;
  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;
  20 use rustc_span::Span;
  21
  22 declare_clippy_lint! {
  23     /// ### What it does
  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.
  28     ///
  29     /// ### Why is this bad?
  30     /// The could contain a useless calculation and can make function simpler.
  31     ///
  32     /// ### Known Issues
  33     /// It could not catch the variable that has no side effects but only used in recursion.
  34     ///
  35     /// ### Example
  36     /// ```rust
  37     /// fn f(a: usize, b: usize) -> usize {
  38     ///     if a == 0 {
  39     ///         1
  40     ///     } else {
  41     ///         f(a - 1, b + 1)
  42     ///     }
  43     /// }
  44     /// # fn main() {
  45     /// #     print!("{}", f(1, 1));
  46     /// # }
  47     /// ```
  48     /// Use instead:
  49     /// ```rust
  50     /// fn f(a: usize) -> usize {
  51     ///     if a == 0 {
  52     ///         1
  53     ///     } else {
  54     ///         f(a - 1)
  55     ///     }
  56     /// }
  57     /// # fn main() {
  58     /// #     print!("{}", f(1));
  59     /// # }
  60     /// ```
  61     #[clippy::version = "1.60.0"]
  62     pub ONLY_USED_IN_RECURSION,
  63     complexity,
  64     "default lint description"
  65 }
  66 declare_lint_pass!(OnlyUsedInRecursion => [ONLY_USED_IN_RECURSION]);
  67
  68 impl<'tcx> LateLintPass<'tcx> for OnlyUsedInRecursion {
  69     fn check_fn(
  70         &mut self,
  71         cx: &LateContext<'tcx>,
  72         kind: FnKind<'tcx>,
  73         _: &'tcx rustc_hir::FnDecl<'tcx>,
  74         body: &'tcx Body<'tcx>,
  75         _: Span,
  76         _: HirId,
  77     ) {
  78         if let FnKind::ItemFn(ident, ..) | FnKind::Method(ident, ..) = kind {
  79             let ty_res = cx.typeck_results();
  80             let param_span = body
  81                 .params
  82                 .iter()
  83                 .flat_map(|param| {
  84                     let mut v = Vec::new();
  85                     param.pat.each_binding(|_, hir_id, span, ident| {
  86                         v.push((hir_id, span, ident));
  87                     });
  88                     v
  89                 })
  90                 .skip(match kind {
  91                     FnKind::Method(..) => 1,
  92                     _ => 0,
  93                 })
  94                 .filter(|(_, _, ident)| !ident.name.as_str().starts_with('_'))
  95                 .collect_vec();
  96
  97             let params = body.params.iter().map(|param| param.pat).collect();
  98
  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(),
 105                 params,
 106                 fn_ident: ident,
 107                 is_method: matches!(kind, FnKind::Method(..)),
 108                 ty_res,
 109                 ty_ctx: cx.tcx,
 110             };
 111
 112             visitor.visit_expr(&body.value);
 113             let vars = std::mem::take(&mut visitor.ret_vars);
 114             visitor.add_side_effect(vars);
 115
 116             let mut queue = visitor.has_side_effect.iter().copied().collect::<VecDeque<_>>();
 117
 118             while let Some(id) = queue.pop_front() {
 119                 if let Some(next) = visitor.graph.get(&id) {
 120                     for i in next {
 121                         if !visitor.has_side_effect.contains(i) {
 122                             visitor.has_side_effect.insert(*i);
 123                             queue.push_back(*i);
 124                         }
 125                     }
 126                 }
 127             }
 128
 129             let mut pre_order = FxHashMap::default();
 130
 131             visitor.graph.iter().for_each(|(_, next)| {
 132                 next.iter().for_each(|i| {
 133                     *pre_order.entry(*i).or_insert(0) += 1;
 134                 });
 135             });
 136
 137             for (id, span, ident) in param_span {
 138                 // if the variable is not used in recursion, it would be marked as unused
 139                 if !visitor.has_side_effect.contains(&id)
 140                     && *pre_order.get(&id).unwrap_or(&0) > 0
 141                     && visitor.graph.contains_key(&id)
 142                 {
 143                     span_lint_and_sugg(
 144                         cx,
 145                         ONLY_USED_IN_RECURSION,
 146                         span,
 147                         "parameter is only used in recursion with no side-effects",
 148                         "if this is intentional, prefix with an underscore",
 149                         format!("_{}", ident.name.as_str()),
 150                         Applicability::MaybeIncorrect,
 151                     );
 152                 }
 153             }
 154         }
 155     }
 156 }
 157
 158 pub fn is_primitive(ty: Ty<'_>) -> bool {
 159     match ty.kind() {
 160         ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Str => true,
 161         ty::Ref(_, t, _) => is_primitive(t),
 162         _ => false,
 163     }
 164 }
 165
 166 pub fn is_array(ty: Ty<'_>) -> bool {
 167     match ty.kind() {
 168         ty::Array(..) | ty::Slice(..) => true,
 169         ty::Ref(_, t, _) => is_array(t),
 170         _ => false,
 171     }
 172 }
 173
 174 pub struct SideEffectVisit<'tcx> {
 175     graph: FxHashMap<HirId, FxHashSet<HirId>>,
 176     has_side_effect: FxHashSet<HirId>,
 177     // bool for if the variable was dereferenced from mutable reference
 178     ret_vars: Vec<(HirId, bool)>,
 179     contains_side_effect: bool,
 180     // break label
 181     break_vars: FxHashMap<Ident, Vec<(HirId, bool)>>,
 182     params: Vec<&'tcx Pat<'tcx>>,
 183     fn_ident: Ident,
 184     is_method: bool,
 185     ty_res: &'tcx TypeckResults<'tcx>,
 186     ty_ctx: TyCtxt<'tcx>,
 187 }
 188
 189 impl<'tcx> Visitor<'tcx> for SideEffectVisit<'tcx> {
 190     fn visit_block(&mut self, b: &'tcx Block<'tcx>) {
 191         b.stmts.iter().for_each(|stmt| {
 192             self.visit_stmt(stmt);
 193             self.ret_vars.clear();
 194         });
 195         walk_list!(self, visit_expr, b.expr);
 196     }
 197
 198     fn visit_stmt(&mut self, s: &'tcx Stmt<'tcx>) {
 199         match s.kind {
 200             StmtKind::Local(Local {
 201                 pat, init: Some(init), ..
 202             }) => {
 203                 self.visit_pat_expr(pat, init);
 204             },
 205             StmtKind::Item(i) => {
 206                 let item = self.ty_ctx.hir().item(i);
 207                 self.visit_item(item);
 208             },
 209             StmtKind::Expr(e) | StmtKind::Semi(e) => self.visit_expr(e),
 210             StmtKind::Local(_) => {},
 211         }
 212     }
 213
 214     fn visit_expr(&mut self, ex: &'tcx Expr<'tcx>) {
 215         debug_assert!(self.ret_vars.is_empty());
 216         match ex.kind {
 217             ExprKind::Array(exprs) | ExprKind::Tup(exprs) => {
 218                 self.ret_vars = exprs
 219                     .iter()
 220                     .flat_map(|expr| {
 221                         self.visit_expr(expr);
 222                         std::mem::take(&mut self.ret_vars)
 223                     })
 224                     .collect();
 225             },
 226             ExprKind::Call(callee, args) => self.visit_fn(callee, args),
 227             ExprKind::MethodCall(path, args, _) => self.visit_method_call(path, args),
 228             ExprKind::Binary(_, lhs, rhs) => {
 229                 self.visit_bin_op(lhs, rhs);
 230             },
 231             ExprKind::Unary(op, expr) => self.visit_un_op(op, expr),
 232             ExprKind::Let(Let { pat, init, .. }) => self.visit_pat_expr(pat, init),
 233             ExprKind::If(bind, then_expr, else_expr) => {
 234                 self.visit_if(bind, then_expr, else_expr);
 235             },
 236             ExprKind::Match(expr, arms, _) => self.visit_match(expr, arms),
 237             ExprKind::Closure(_, _, body_id, _, _) => {
 238                 let body = self.ty_ctx.hir().body(body_id);
 239                 self.visit_body(body);
 240                 let vars = std::mem::take(&mut self.ret_vars);
 241                 self.add_side_effect(vars);
 242             },
 243             ExprKind::Loop(block, label, _, _) | ExprKind::Block(block, label) => {
 244                 self.visit_block_label(block, label);
 245             },
 246             ExprKind::Assign(bind, expr, _) => {
 247                 self.visit_assign(bind, expr);
 248             },
 249             ExprKind::AssignOp(_, bind, expr) => {
 250                 self.visit_assign(bind, expr);
 251                 self.visit_bin_op(bind, expr);
 252             },
 253             ExprKind::Field(expr, _) => {
 254                 self.visit_expr(expr);
 255                 if matches!(self.ty_res.expr_ty(expr).kind(), ty::Ref(_, _, Mutability::Mut)) {
 256                     self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
 257                 }
 258             },
 259             ExprKind::Index(expr, index) => {
 260                 self.visit_expr(expr);
 261                 let mut vars = std::mem::take(&mut self.ret_vars);
 262                 self.visit_expr(index);
 263                 self.ret_vars.append(&mut vars);
 264
 265                 if !is_array(self.ty_res.expr_ty(expr)) {
 266                     self.add_side_effect(self.ret_vars.clone());
 267                 } else if matches!(self.ty_res.expr_ty(expr).kind(), ty::Ref(_, _, Mutability::Mut)) {
 268                     self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
 269                 }
 270             },
 271             ExprKind::Break(dest, Some(expr)) => {
 272                 self.visit_expr(expr);
 273                 if let Some(label) = dest.label {
 274                     self.break_vars
 275                         .entry(label.ident)
 276                         .or_insert(Vec::new())
 277                         .append(&mut self.ret_vars);
 278                 }
 279                 self.contains_side_effect = true;
 280             },
 281             ExprKind::Ret(Some(expr)) => {
 282                 self.visit_expr(expr);
 283                 let vars = std::mem::take(&mut self.ret_vars);
 284                 self.add_side_effect(vars);
 285                 self.contains_side_effect = true;
 286             },
 287             ExprKind::Break(_, None) | ExprKind::Continue(_) | ExprKind::Ret(None) => {
 288                 self.contains_side_effect = true;
 289             },
 290             ExprKind::Struct(_, exprs, expr) => {
 291                 let mut ret_vars = exprs
 292                     .iter()
 293                     .flat_map(|field| {
 294                         self.visit_expr(field.expr);
 295                         std::mem::take(&mut self.ret_vars)
 296                     })
 297                     .collect();
 298
 299                 walk_list!(self, visit_expr, expr);
 300                 self.ret_vars.append(&mut ret_vars);
 301             },
 302             _ => walk_expr(self, ex),
 303         }
 304     }
 305
 306     fn visit_path(&mut self, path: &'tcx Path<'tcx>, _id: HirId) {
 307         if let Res::Local(id) = path.res {
 308             self.ret_vars.push((id, false));
 309         }
 310     }
 311 }
 312
 313 impl<'tcx> SideEffectVisit<'tcx> {
 314     fn visit_assign(&mut self, lhs: &'tcx Expr<'tcx>, rhs: &'tcx Expr<'tcx>) {
 315         // Just support array and tuple unwrapping for now.
 316         //
 317         // ex) `(a, b) = (c, d);`
 318         // The graph would look like this:
 319         //   a -> c
 320         //   b -> d
 321         //
 322         // This would minimize the connection of the side-effect graph.
 323         match (&lhs.kind, &rhs.kind) {
 324             (ExprKind::Array(lhs), ExprKind::Array(rhs)) | (ExprKind::Tup(lhs), ExprKind::Tup(rhs)) => {
 325                 // if not, it is a compile error
 326                 debug_assert!(lhs.len() == rhs.len());
 327                 izip!(*lhs, *rhs).for_each(|(lhs, rhs)| self.visit_assign(lhs, rhs));
 328             },
 329             // in other assigns, we have to connect all each other
 330             // because they can be connected somehow
 331             _ => {
 332                 self.visit_expr(lhs);
 333                 let lhs_vars = std::mem::take(&mut self.ret_vars);
 334                 self.visit_expr(rhs);
 335                 let rhs_vars = std::mem::take(&mut self.ret_vars);
 336                 self.connect_assign(&lhs_vars, &rhs_vars);
 337             },
 338         }
 339     }
 340
 341     fn visit_block_label(&mut self, block: &'tcx Block<'tcx>, label: Option<Label>) {
 342         self.visit_block(block);
 343         let _ = label.and_then(|label| {
 344             self.break_vars
 345                 .remove(&label.ident)
 346                 .map(|mut break_vars| self.ret_vars.append(&mut break_vars))
 347         });
 348     }
 349
 350     fn visit_bin_op(&mut self, lhs: &'tcx Expr<'tcx>, rhs: &'tcx Expr<'tcx>) {
 351         self.visit_expr(lhs);
 352         let mut ret_vars = std::mem::take(&mut self.ret_vars);
 353         self.visit_expr(rhs);
 354         self.ret_vars.append(&mut ret_vars);
 355         if !is_primitive(self.ty_res.expr_ty(lhs)) || !is_primitive(self.ty_res.expr_ty(rhs)) {
 356             self.ret_vars.iter().for_each(|id| {
 357                 self.has_side_effect.insert(id.0);
 358             });
 359             self.contains_side_effect = true;
 360         }
 361     }
 362
 363     fn visit_un_op(&mut self, op: UnOp, expr: &'tcx Expr<'tcx>) {
 364         self.visit_expr(expr);
 365         let ty = self.ty_res.expr_ty(expr);
 366         // dereferencing a reference has no side-effect
 367         if !is_primitive(ty) && !matches!((op, ty.kind()), (UnOp::Deref, ty::Ref(..))) {
 368             self.add_side_effect(self.ret_vars.clone());
 369         }
 370
 371         if matches!((op, ty.kind()), (UnOp::Deref, ty::Ref(_, _, Mutability::Mut))) {
 372             self.ret_vars.iter_mut().for_each(|(_, b)| *b = true);
 373         }
 374     }
 375
 376     fn visit_pat_expr(&mut self, pat: &'tcx Pat<'tcx>, expr: &'tcx Expr<'tcx>) {
 377         match (&pat.kind, &expr.kind) {
 378             (PatKind::Tuple(pats, _), ExprKind::Tup(exprs)) => {
 379                 self.ret_vars = izip!(*pats, *exprs)
 380                     .flat_map(|(pat, expr)| {
 381                         self.visit_pat_expr(pat, expr);
 382                         std::mem::take(&mut self.ret_vars)
 383                     })
 384                     .collect();
 385             },
 386             (PatKind::Slice(front_exprs, _, back_exprs), ExprKind::Array(exprs)) => {
 387                 let mut vars = izip!(*front_exprs, *exprs)
 388                     .flat_map(|(pat, expr)| {
 389                         self.visit_pat_expr(pat, expr);
 390                         std::mem::take(&mut self.ret_vars)
 391                     })
 392                     .collect();
 393                 self.ret_vars = izip!(back_exprs.iter().rev(), exprs.iter().rev())
 394                     .flat_map(|(pat, expr)| {
 395                         self.visit_pat_expr(pat, expr);
 396                         std::mem::take(&mut self.ret_vars)
 397                     })
 398                     .collect();
 399                 self.ret_vars.append(&mut vars);
 400             },
 401             _ => {
 402                 let mut lhs_vars = Vec::new();
 403                 pat.each_binding(|_, id, _, _| lhs_vars.push((id, false)));
 404                 self.visit_expr(expr);
 405                 let rhs_vars = std::mem::take(&mut self.ret_vars);
 406                 self.connect_assign(&lhs_vars, &rhs_vars);
 407                 self.ret_vars = rhs_vars;
 408             },
 409         }
 410     }
 411
 412     fn visit_fn(&mut self, callee: &'tcx Expr<'tcx>, args: &'tcx [Expr<'tcx>]) {
 413         self.visit_expr(callee);
 414         let mut ret_vars = std::mem::take(&mut self.ret_vars);
 415         self.add_side_effect(ret_vars.clone());
 416
 417         if_chain! {
 418             if !self.is_method;
 419             if let ExprKind::Path(QPath::Resolved(_, path)) = callee.kind;
 420             if let Res::Def(..) = path.res;
 421             if path.segments.len() == 1;
 422             let ident = path.segments.last().unwrap().ident;
 423             if ident == self.fn_ident;
 424             then {
 425                 izip!(self.params.clone(), args)
 426                     .for_each(|(pat, expr)| {
 427                         self.visit_pat_expr(pat, expr);
 428                         self.ret_vars.clear();
 429                     });
 430             } else {
 431                 // This would set arguments used in closure that does not have side-effect.
 432                 // Closure itself can be detected whether there is a side-effect, but the
 433                 // value of variable that is holding closure can change.
 434                 // So, we just check the variables.
 435                 self.ret_vars = args
 436                     .iter()
 437                     .flat_map(|expr| {
 438                         self.visit_expr(expr);
 439                         std::mem::take(&mut self.ret_vars)
 440                     })
 441                     .collect_vec()
 442                     .into_iter()
 443                     .map(|id| {
 444                         self.has_side_effect.insert(id.0);
 445                         id
 446                     })
 447                     .collect();
 448                 self.contains_side_effect = true;
 449             }
 450         }
 451
 452         self.ret_vars.append(&mut ret_vars);
 453     }
 454
 455     fn visit_method_call(&mut self, path: &'tcx PathSegment<'tcx>, args: &'tcx [Expr<'tcx>]) {
 456         if_chain! {
 457             if self.is_method;
 458             if path.ident == self.fn_ident;
 459             if let ExprKind::Path(QPath::Resolved(_, path)) = args.first().unwrap().kind;
 460             if let Res::Local(..) = path.res;
 461             let ident = path.segments.last().unwrap().ident;
 462             if ident.name == kw::SelfLower;
 463             then {
 464                 izip!(self.params.clone(), args.iter())
 465                     .for_each(|(pat, expr)| {
 466                         self.visit_pat_expr(pat, expr);
 467                         self.ret_vars.clear();
 468                     });
 469             } else {
 470                 self.ret_vars = args
 471                     .iter()
 472                     .flat_map(|expr| {
 473                         self.visit_expr(expr);
 474                         std::mem::take(&mut self.ret_vars)
 475                     })
 476                     .collect_vec()
 477                     .into_iter()
 478                     .map(|a| {
 479                         self.has_side_effect.insert(a.0);
 480                         a
 481                     })
 482                     .collect();
 483                 self.contains_side_effect = true;
 484             }
 485         }
 486     }
 487
 488     fn visit_if(&mut self, bind: &'tcx Expr<'tcx>, then_expr: &'tcx Expr<'tcx>, else_expr: Option<&'tcx Expr<'tcx>>) {
 489         let contains_side_effect = self.contains_side_effect;
 490         self.contains_side_effect = false;
 491         self.visit_expr(bind);
 492         let mut vars = std::mem::take(&mut self.ret_vars);
 493         self.visit_expr(then_expr);
 494         let mut then_vars = std::mem::take(&mut self.ret_vars);
 495         walk_list!(self, visit_expr, else_expr);
 496         if self.contains_side_effect {
 497             self.add_side_effect(vars.clone());
 498         }
 499         self.contains_side_effect |= contains_side_effect;
 500         self.ret_vars.append(&mut vars);
 501         self.ret_vars.append(&mut then_vars);
 502     }
 503
 504     fn visit_match(&mut self, expr: &'tcx Expr<'tcx>, arms: &'tcx [Arm<'tcx>]) {
 505         self.visit_expr(expr);
 506         let mut expr_vars = std::mem::take(&mut self.ret_vars);
 507         self.ret_vars = arms
 508             .iter()
 509             .flat_map(|arm| {
 510                 let contains_side_effect = self.contains_side_effect;
 511                 self.contains_side_effect = false;
 512                 // this would visit `expr` multiple times
 513                 // but couldn't think of a better way
 514                 self.visit_pat_expr(arm.pat, expr);
 515                 let mut vars = std::mem::take(&mut self.ret_vars);
 516                 let _ = arm.guard.as_ref().map(|guard| {
 517                     self.visit_expr(match guard {
 518                         Guard::If(expr) | Guard::IfLet(_, expr) => expr,
 519                     });
 520                     vars.append(&mut self.ret_vars);
 521                 });
 522                 self.visit_expr(arm.body);
 523                 if self.contains_side_effect {
 524                     self.add_side_effect(vars.clone());
 525                     self.add_side_effect(expr_vars.clone());
 526                 }
 527                 self.contains_side_effect |= contains_side_effect;
 528                 vars.append(&mut self.ret_vars);
 529                 vars
 530             })
 531             .collect();
 532         self.ret_vars.append(&mut expr_vars);
 533     }
 534
 535     fn connect_assign(&mut self, lhs: &[(HirId, bool)], rhs: &[(HirId, bool)]) {
 536         // if mutable dereference is on assignment it can have side-effect
 537         // (this can lead to parameter mutable dereference and change the original value)
 538         // too hard to detect whether this value is from parameter, so this would all
 539         // check mutable dereference assignment to side effect
 540         lhs.iter().filter(|(_, b)| *b).for_each(|(id, _)| {
 541             self.has_side_effect.insert(*id);
 542             self.contains_side_effect = true;
 543         });
 544
 545         // there is no connection
 546         if lhs.is_empty() || rhs.is_empty() {
 547             return;
 548         }
 549
 550         // by connected rhs in cycle, the connections would decrease
 551         // from `n * m` to `n + m`
 552         // where `n` and `m` are length of `lhs` and `rhs`.
 553
 554         // unwrap is possible since rhs is not empty
 555         let rhs_first = rhs.first().unwrap();
 556         for (id, _) in lhs.iter() {
 557             self.graph
 558                 .entry(*id)
 559                 .or_insert_with(FxHashSet::default)
 560                 .insert(rhs_first.0);
 561         }
 562
 563         let rhs = rhs.iter();
 564         izip!(rhs.clone().cycle().skip(1), rhs).for_each(|(from, to)| {
 565             self.graph.entry(from.0).or_insert_with(FxHashSet::default).insert(to.0);
 566         });
 567     }
 568
 569     fn add_side_effect(&mut self, v: Vec<(HirId, bool)>) {
 570         for (id, _) in v {
 571             self.has_side_effect.insert(id);
 572             self.contains_side_effect = true;
 573         }
 574     }
 575 }