src/tools/clippy/clippy_lints/src/only_used_in_recursion.rs

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