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 use std::iter;
  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     /// ```
  82     #[clippy::version = "1.61.0"]
  83     pub ONLY_USED_IN_RECURSION,
  84     complexity,
  85     "arguments that is only used in recursion can be removed"
  86 }
  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 }
  98
  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(),
 120         }
 121     }
 122 }
 123
 124 #[derive(Debug)]
 125 struct Usage {
 126     span: Span,
 127     idx: usize,
 128 }
 129 impl Usage {
 130     fn new(span: Span, idx: usize) -> Self {
 131         Self { span, idx }
 132     }
 133 }
 134
 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>,
 142 }
 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);
 149     }
 150
 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);
 157         }
 158     }
 159
 160     fn get_by_id_mut(&mut self, id: HirId) -> Option<&mut Param> {
 161         self.params.get_mut(*self.by_id.get(&id)?)
 162     }
 163
 164     fn get_by_fn(&self, id: DefId, idx: usize) -> Option<&Param> {
 165         self.params.get(*self.by_fn.get(&(id, idx))?)
 166     }
 167
 168     fn clear(&mut self) {
 169         self.params.clear();
 170         self.by_id.clear();
 171         self.by_fn.clear();
 172     }
 173
 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);
 180         }
 181     }
 182
 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(&param.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
 211         }
 212     }
 213 }
 214
 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 }
 221
 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;
 226         }
 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.owner_id.to_def_id(), FnKind::Fn, 0),
 231             Some(Node::TraitItem(&TraitItem {
 232                 kind: TraitItemKind::Fn(ref sig, _),
 233                 owner_id,
 234                 ..
 235             })) => (
 236                 owner_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                 owner_id,
 243                 ..
 244             })) => {
 245                 #[allow(trivial_casts)]
 246                 if let Some(Node::Item(item)) = get_parent_node(cx.tcx, owner_id.into())
 247                     && let Some(trait_ref) = cx.tcx.impl_trait_ref(item.owner_id).map(|t| t.subst_identity())
 248                     && let Some(trait_item_id) = cx.tcx.associated_item(owner_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                     (owner_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);
 274         }
 275     }
 276
 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;
 347             }
 348         }
 349     }
 350
 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                     );
 377                 }
 378             }
 379             self.params.clear();
 380         }
 381     }
 382 }
 383
 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,
 394     }
 395 }