src/tools/clippy/clippy_utils/src/hir_utils.rs

   1 use crate::consts::constant_simple;
   2 use crate::macros::macro_backtrace;
   3 use crate::source::snippet_opt;
   4 use rustc_ast::ast::InlineAsmTemplatePiece;
   5 use rustc_data_structures::fx::FxHasher;
   6 use rustc_hir::def::Res;
   7 use rustc_hir::HirIdMap;
   8 use rustc_hir::{
   9     ArrayLen, BinOpKind, BindingAnnotation, Block, BodyId, Closure, Expr, ExprField, ExprKind, FnRetTy, GenericArg,
  10     GenericArgs, Guard, HirId, InlineAsmOperand, Let, Lifetime, LifetimeName, Pat, PatField, PatKind, Path,
  11     PathSegment, PrimTy, QPath, Stmt, StmtKind, Ty, TyKind, TypeBinding,
  12 };
  13 use rustc_lexer::{tokenize, TokenKind};
  14 use rustc_lint::LateContext;
  15 use rustc_middle::ty::TypeckResults;
  16 use rustc_span::{sym, Symbol};
  17 use std::hash::{Hash, Hasher};
  18
  19 /// Callback that is called when two expressions are not equal in the sense of `SpanlessEq`, but
  20 /// other conditions would make them equal.
  21 type SpanlessEqCallback<'a> = dyn FnMut(&Expr<'_>, &Expr<'_>) -> bool + 'a;
  22
  23 /// Type used to check whether two ast are the same. This is different from the
  24 /// operator `==` on ast types as this operator would compare true equality with
  25 /// ID and span.
  26 ///
  27 /// Note that some expressions kinds are not considered but could be added.
  28 pub struct SpanlessEq<'a, 'tcx> {
  29     /// Context used to evaluate constant expressions.
  30     cx: &'a LateContext<'tcx>,
  31     maybe_typeck_results: Option<(&'tcx TypeckResults<'tcx>, &'tcx TypeckResults<'tcx>)>,
  32     allow_side_effects: bool,
  33     expr_fallback: Option<Box<SpanlessEqCallback<'a>>>,
  34 }
  35
  36 impl<'a, 'tcx> SpanlessEq<'a, 'tcx> {
  37     pub fn new(cx: &'a LateContext<'tcx>) -> Self {
  38         Self {
  39             cx,
  40             maybe_typeck_results: cx.maybe_typeck_results().map(|x| (x, x)),
  41             allow_side_effects: true,
  42             expr_fallback: None,
  43         }
  44     }
  45
  46     /// Consider expressions containing potential side effects as not equal.
  47     #[must_use]
  48     pub fn deny_side_effects(self) -> Self {
  49         Self {
  50             allow_side_effects: false,
  51             ..self
  52         }
  53     }
  54
  55     #[must_use]
  56     pub fn expr_fallback(self, expr_fallback: impl FnMut(&Expr<'_>, &Expr<'_>) -> bool + 'a) -> Self {
  57         Self {
  58             expr_fallback: Some(Box::new(expr_fallback)),
  59             ..self
  60         }
  61     }
  62
  63     /// Use this method to wrap comparisons that may involve inter-expression context.
  64     /// See `self.locals`.
  65     pub fn inter_expr(&mut self) -> HirEqInterExpr<'_, 'a, 'tcx> {
  66         HirEqInterExpr {
  67             inner: self,
  68             locals: HirIdMap::default(),
  69         }
  70     }
  71
  72     pub fn eq_block(&mut self, left: &Block<'_>, right: &Block<'_>) -> bool {
  73         self.inter_expr().eq_block(left, right)
  74     }
  75
  76     pub fn eq_expr(&mut self, left: &Expr<'_>, right: &Expr<'_>) -> bool {
  77         self.inter_expr().eq_expr(left, right)
  78     }
  79
  80     pub fn eq_path(&mut self, left: &Path<'_>, right: &Path<'_>) -> bool {
  81         self.inter_expr().eq_path(left, right)
  82     }
  83
  84     pub fn eq_path_segment(&mut self, left: &PathSegment<'_>, right: &PathSegment<'_>) -> bool {
  85         self.inter_expr().eq_path_segment(left, right)
  86     }
  87
  88     pub fn eq_path_segments(&mut self, left: &[PathSegment<'_>], right: &[PathSegment<'_>]) -> bool {
  89         self.inter_expr().eq_path_segments(left, right)
  90     }
  91 }
  92
  93 pub struct HirEqInterExpr<'a, 'b, 'tcx> {
  94     inner: &'a mut SpanlessEq<'b, 'tcx>,
  95
  96     // When binding are declared, the binding ID in the left expression is mapped to the one on the
  97     // right. For example, when comparing `{ let x = 1; x + 2 }` and `{ let y = 1; y + 2 }`,
  98     // these blocks are considered equal since `x` is mapped to `y`.
  99     pub locals: HirIdMap<HirId>,
 100 }
 101
 102 impl HirEqInterExpr<'_, '_, '_> {
 103     pub fn eq_stmt(&mut self, left: &Stmt<'_>, right: &Stmt<'_>) -> bool {
 104         match (&left.kind, &right.kind) {
 105             (&StmtKind::Local(l), &StmtKind::Local(r)) => {
 106                 // This additional check ensures that the type of the locals are equivalent even if the init
 107                 // expression or type have some inferred parts.
 108                 if let Some((typeck_lhs, typeck_rhs)) = self.inner.maybe_typeck_results {
 109                     let l_ty = typeck_lhs.pat_ty(l.pat);
 110                     let r_ty = typeck_rhs.pat_ty(r.pat);
 111                     if l_ty != r_ty {
 112                         return false;
 113                     }
 114                 }
 115
 116                 // eq_pat adds the HirIds to the locals map. We therefore call it last to make sure that
 117                 // these only get added if the init and type is equal.
 118                 both(&l.init, &r.init, |l, r| self.eq_expr(l, r))
 119                     && both(&l.ty, &r.ty, |l, r| self.eq_ty(l, r))
 120                     && both(&l.els, &r.els, |l, r| self.eq_block(l, r))
 121                     && self.eq_pat(l.pat, r.pat)
 122             },
 123             (&StmtKind::Expr(l), &StmtKind::Expr(r)) | (&StmtKind::Semi(l), &StmtKind::Semi(r)) => self.eq_expr(l, r),
 124             _ => false,
 125         }
 126     }
 127
 128     /// Checks whether two blocks are the same.
 129     fn eq_block(&mut self, left: &Block<'_>, right: &Block<'_>) -> bool {
 130         match (left.stmts, left.expr, right.stmts, right.expr) {
 131             ([], None, [], None) => {
 132                 // For empty blocks, check to see if the tokens are equal. This will catch the case where a macro
 133                 // expanded to nothing, or the cfg attribute was used.
 134                 let (Some(left), Some(right)) = (
 135                     snippet_opt(self.inner.cx, left.span),
 136                     snippet_opt(self.inner.cx, right.span),
 137                 ) else { return true };
 138                 let mut left_pos = 0;
 139                 let left = tokenize(&left)
 140                     .map(|t| {
 141                         let end = left_pos + t.len as usize;
 142                         let s = &left[left_pos..end];
 143                         left_pos = end;
 144                         (t, s)
 145                     })
 146                     .filter(|(t, _)| {
 147                         !matches!(
 148                             t.kind,
 149                             TokenKind::LineComment { .. } | TokenKind::BlockComment { .. } | TokenKind::Whitespace
 150                         )
 151                     })
 152                     .map(|(_, s)| s);
 153                 let mut right_pos = 0;
 154                 let right = tokenize(&right)
 155                     .map(|t| {
 156                         let end = right_pos + t.len as usize;
 157                         let s = &right[right_pos..end];
 158                         right_pos = end;
 159                         (t, s)
 160                     })
 161                     .filter(|(t, _)| {
 162                         !matches!(
 163                             t.kind,
 164                             TokenKind::LineComment { .. } | TokenKind::BlockComment { .. } | TokenKind::Whitespace
 165                         )
 166                     })
 167                     .map(|(_, s)| s);
 168                 left.eq(right)
 169             },
 170             _ => {
 171                 over(left.stmts, right.stmts, |l, r| self.eq_stmt(l, r))
 172                     && both(&left.expr, &right.expr, |l, r| self.eq_expr(l, r))
 173             },
 174         }
 175     }
 176
 177     fn should_ignore(&mut self, expr: &Expr<'_>) -> bool {
 178         macro_backtrace(expr.span).last().map_or(false, |macro_call| {
 179             matches!(
 180                 &self.inner.cx.tcx.get_diagnostic_name(macro_call.def_id),
 181                 Some(sym::todo_macro | sym::unimplemented_macro)
 182             )
 183         })
 184     }
 185
 186     pub fn eq_array_length(&mut self, left: ArrayLen, right: ArrayLen) -> bool {
 187         match (left, right) {
 188             (ArrayLen::Infer(..), ArrayLen::Infer(..)) => true,
 189             (ArrayLen::Body(l_ct), ArrayLen::Body(r_ct)) => self.eq_body(l_ct.body, r_ct.body),
 190             (_, _) => false,
 191         }
 192     }
 193
 194     pub fn eq_body(&mut self, left: BodyId, right: BodyId) -> bool {
 195         // swap out TypeckResults when hashing a body
 196         let old_maybe_typeck_results = self.inner.maybe_typeck_results.replace((
 197             self.inner.cx.tcx.typeck_body(left),
 198             self.inner.cx.tcx.typeck_body(right),
 199         ));
 200         let res = self.eq_expr(
 201             self.inner.cx.tcx.hir().body(left).value,
 202             self.inner.cx.tcx.hir().body(right).value,
 203         );
 204         self.inner.maybe_typeck_results = old_maybe_typeck_results;
 205         res
 206     }
 207
 208     #[expect(clippy::similar_names)]
 209     pub fn eq_expr(&mut self, left: &Expr<'_>, right: &Expr<'_>) -> bool {
 210         if !self.inner.allow_side_effects && left.span.ctxt() != right.span.ctxt() {
 211             return false;
 212         }
 213
 214         if let Some((typeck_lhs, typeck_rhs)) = self.inner.maybe_typeck_results {
 215             if let (Some(l), Some(r)) = (
 216                 constant_simple(self.inner.cx, typeck_lhs, left),
 217                 constant_simple(self.inner.cx, typeck_rhs, right),
 218             ) {
 219                 if l == r {
 220                     return true;
 221                 }
 222             }
 223         }
 224
 225         let is_eq = match (
 226             reduce_exprkind(self.inner.cx, &left.kind),
 227             reduce_exprkind(self.inner.cx, &right.kind),
 228         ) {
 229             (&ExprKind::AddrOf(lb, l_mut, le), &ExprKind::AddrOf(rb, r_mut, re)) => {
 230                 lb == rb && l_mut == r_mut && self.eq_expr(le, re)
 231             },
 232             (&ExprKind::Continue(li), &ExprKind::Continue(ri)) => {
 233                 both(&li.label, &ri.label, |l, r| l.ident.name == r.ident.name)
 234             },
 235             (&ExprKind::Assign(ll, lr, _), &ExprKind::Assign(rl, rr, _)) => {
 236                 self.inner.allow_side_effects && self.eq_expr(ll, rl) && self.eq_expr(lr, rr)
 237             },
 238             (&ExprKind::AssignOp(ref lo, ll, lr), &ExprKind::AssignOp(ref ro, rl, rr)) => {
 239                 self.inner.allow_side_effects && lo.node == ro.node && self.eq_expr(ll, rl) && self.eq_expr(lr, rr)
 240             },
 241             (&ExprKind::Block(l, _), &ExprKind::Block(r, _)) => self.eq_block(l, r),
 242             (&ExprKind::Binary(l_op, ll, lr), &ExprKind::Binary(r_op, rl, rr)) => {
 243                 l_op.node == r_op.node && self.eq_expr(ll, rl) && self.eq_expr(lr, rr)
 244                     || swap_binop(l_op.node, ll, lr).map_or(false, |(l_op, ll, lr)| {
 245                         l_op == r_op.node && self.eq_expr(ll, rl) && self.eq_expr(lr, rr)
 246                     })
 247             },
 248             (&ExprKind::Break(li, ref le), &ExprKind::Break(ri, ref re)) => {
 249                 both(&li.label, &ri.label, |l, r| l.ident.name == r.ident.name)
 250                     && both(le, re, |l, r| self.eq_expr(l, r))
 251             },
 252             (&ExprKind::Box(l), &ExprKind::Box(r)) => self.eq_expr(l, r),
 253             (&ExprKind::Call(l_fun, l_args), &ExprKind::Call(r_fun, r_args)) => {
 254                 self.inner.allow_side_effects && self.eq_expr(l_fun, r_fun) && self.eq_exprs(l_args, r_args)
 255             },
 256             (&ExprKind::Cast(lx, lt), &ExprKind::Cast(rx, rt)) | (&ExprKind::Type(lx, lt), &ExprKind::Type(rx, rt)) => {
 257                 self.eq_expr(lx, rx) && self.eq_ty(lt, rt)
 258             },
 259             (&ExprKind::Field(l_f_exp, ref l_f_ident), &ExprKind::Field(r_f_exp, ref r_f_ident)) => {
 260                 l_f_ident.name == r_f_ident.name && self.eq_expr(l_f_exp, r_f_exp)
 261             },
 262             (&ExprKind::Index(la, li), &ExprKind::Index(ra, ri)) => self.eq_expr(la, ra) && self.eq_expr(li, ri),
 263             (&ExprKind::If(lc, lt, ref le), &ExprKind::If(rc, rt, ref re)) => {
 264                 self.eq_expr(lc, rc) && self.eq_expr(lt, rt) && both(le, re, |l, r| self.eq_expr(l, r))
 265             },
 266             (&ExprKind::Let(l), &ExprKind::Let(r)) => {
 267                 self.eq_pat(l.pat, r.pat) && both(&l.ty, &r.ty, |l, r| self.eq_ty(l, r)) && self.eq_expr(l.init, r.init)
 268             },
 269             (ExprKind::Lit(l), ExprKind::Lit(r)) => l.node == r.node,
 270             (&ExprKind::Loop(lb, ref ll, ref lls, _), &ExprKind::Loop(rb, ref rl, ref rls, _)) => {
 271                 lls == rls && self.eq_block(lb, rb) && both(ll, rl, |l, r| l.ident.name == r.ident.name)
 272             },
 273             (&ExprKind::Match(le, la, ref ls), &ExprKind::Match(re, ra, ref rs)) => {
 274                 ls == rs
 275                     && self.eq_expr(le, re)
 276                     && over(la, ra, |l, r| {
 277                         self.eq_pat(l.pat, r.pat)
 278                             && both(&l.guard, &r.guard, |l, r| self.eq_guard(l, r))
 279                             && self.eq_expr(l.body, r.body)
 280                     })
 281             },
 282             (
 283                 &ExprKind::MethodCall(l_path, l_receiver, l_args, _),
 284                 &ExprKind::MethodCall(r_path, r_receiver, r_args, _),
 285             ) => {
 286                 self.inner.allow_side_effects
 287                     && self.eq_path_segment(l_path, r_path)
 288                     && self.eq_expr(l_receiver, r_receiver)
 289                     && self.eq_exprs(l_args, r_args)
 290             },
 291             (&ExprKind::Repeat(le, ll), &ExprKind::Repeat(re, rl)) => {
 292                 self.eq_expr(le, re) && self.eq_array_length(ll, rl)
 293             },
 294             (ExprKind::Ret(l), ExprKind::Ret(r)) => both(l, r, |l, r| self.eq_expr(l, r)),
 295             (ExprKind::Path(l), ExprKind::Path(r)) => self.eq_qpath(l, r),
 296             (&ExprKind::Struct(l_path, lf, ref lo), &ExprKind::Struct(r_path, rf, ref ro)) => {
 297                 self.eq_qpath(l_path, r_path)
 298                     && both(lo, ro, |l, r| self.eq_expr(l, r))
 299                     && over(lf, rf, |l, r| self.eq_expr_field(l, r))
 300             },
 301             (&ExprKind::Tup(l_tup), &ExprKind::Tup(r_tup)) => self.eq_exprs(l_tup, r_tup),
 302             (&ExprKind::Unary(l_op, le), &ExprKind::Unary(r_op, re)) => l_op == r_op && self.eq_expr(le, re),
 303             (&ExprKind::Array(l), &ExprKind::Array(r)) => self.eq_exprs(l, r),
 304             (&ExprKind::DropTemps(le), &ExprKind::DropTemps(re)) => self.eq_expr(le, re),
 305             _ => false,
 306         };
 307         (is_eq && (!self.should_ignore(left) || !self.should_ignore(right)))
 308             || self.inner.expr_fallback.as_mut().map_or(false, |f| f(left, right))
 309     }
 310
 311     fn eq_exprs(&mut self, left: &[Expr<'_>], right: &[Expr<'_>]) -> bool {
 312         over(left, right, |l, r| self.eq_expr(l, r))
 313     }
 314
 315     fn eq_expr_field(&mut self, left: &ExprField<'_>, right: &ExprField<'_>) -> bool {
 316         left.ident.name == right.ident.name && self.eq_expr(left.expr, right.expr)
 317     }
 318
 319     fn eq_guard(&mut self, left: &Guard<'_>, right: &Guard<'_>) -> bool {
 320         match (left, right) {
 321             (Guard::If(l), Guard::If(r)) => self.eq_expr(l, r),
 322             (Guard::IfLet(l), Guard::IfLet(r)) => {
 323                 self.eq_pat(l.pat, r.pat) && both(&l.ty, &r.ty, |l, r| self.eq_ty(l, r)) && self.eq_expr(l.init, r.init)
 324             },
 325             _ => false,
 326         }
 327     }
 328
 329     fn eq_generic_arg(&mut self, left: &GenericArg<'_>, right: &GenericArg<'_>) -> bool {
 330         match (left, right) {
 331             (GenericArg::Const(l), GenericArg::Const(r)) => self.eq_body(l.value.body, r.value.body),
 332             (GenericArg::Lifetime(l_lt), GenericArg::Lifetime(r_lt)) => Self::eq_lifetime(l_lt, r_lt),
 333             (GenericArg::Type(l_ty), GenericArg::Type(r_ty)) => self.eq_ty(l_ty, r_ty),
 334             (GenericArg::Infer(l_inf), GenericArg::Infer(r_inf)) => self.eq_ty(&l_inf.to_ty(), &r_inf.to_ty()),
 335             _ => false,
 336         }
 337     }
 338
 339     fn eq_lifetime(left: &Lifetime, right: &Lifetime) -> bool {
 340         left.res == right.res
 341     }
 342
 343     fn eq_pat_field(&mut self, left: &PatField<'_>, right: &PatField<'_>) -> bool {
 344         let (PatField { ident: li, pat: lp, .. }, PatField { ident: ri, pat: rp, .. }) = (&left, &right);
 345         li.name == ri.name && self.eq_pat(lp, rp)
 346     }
 347
 348     /// Checks whether two patterns are the same.
 349     fn eq_pat(&mut self, left: &Pat<'_>, right: &Pat<'_>) -> bool {
 350         match (&left.kind, &right.kind) {
 351             (&PatKind::Box(l), &PatKind::Box(r)) => self.eq_pat(l, r),
 352             (&PatKind::Struct(ref lp, la, ..), &PatKind::Struct(ref rp, ra, ..)) => {
 353                 self.eq_qpath(lp, rp) && over(la, ra, |l, r| self.eq_pat_field(l, r))
 354             },
 355             (&PatKind::TupleStruct(ref lp, la, ls), &PatKind::TupleStruct(ref rp, ra, rs)) => {
 356                 self.eq_qpath(lp, rp) && over(la, ra, |l, r| self.eq_pat(l, r)) && ls == rs
 357             },
 358             (&PatKind::Binding(lb, li, _, ref lp), &PatKind::Binding(rb, ri, _, ref rp)) => {
 359                 let eq = lb == rb && both(lp, rp, |l, r| self.eq_pat(l, r));
 360                 if eq {
 361                     self.locals.insert(li, ri);
 362                 }
 363                 eq
 364             },
 365             (PatKind::Path(l), PatKind::Path(r)) => self.eq_qpath(l, r),
 366             (&PatKind::Lit(l), &PatKind::Lit(r)) => self.eq_expr(l, r),
 367             (&PatKind::Tuple(l, ls), &PatKind::Tuple(r, rs)) => ls == rs && over(l, r, |l, r| self.eq_pat(l, r)),
 368             (&PatKind::Range(ref ls, ref le, li), &PatKind::Range(ref rs, ref re, ri)) => {
 369                 both(ls, rs, |a, b| self.eq_expr(a, b)) && both(le, re, |a, b| self.eq_expr(a, b)) && (li == ri)
 370             },
 371             (&PatKind::Ref(le, ref lm), &PatKind::Ref(re, ref rm)) => lm == rm && self.eq_pat(le, re),
 372             (&PatKind::Slice(ls, ref li, le), &PatKind::Slice(rs, ref ri, re)) => {
 373                 over(ls, rs, |l, r| self.eq_pat(l, r))
 374                     && over(le, re, |l, r| self.eq_pat(l, r))
 375                     && both(li, ri, |l, r| self.eq_pat(l, r))
 376             },
 377             (&PatKind::Wild, &PatKind::Wild) => true,
 378             _ => false,
 379         }
 380     }
 381
 382     #[expect(clippy::similar_names)]
 383     fn eq_qpath(&mut self, left: &QPath<'_>, right: &QPath<'_>) -> bool {
 384         match (left, right) {
 385             (&QPath::Resolved(ref lty, lpath), &QPath::Resolved(ref rty, rpath)) => {
 386                 both(lty, rty, |l, r| self.eq_ty(l, r)) && self.eq_path(lpath, rpath)
 387             },
 388             (&QPath::TypeRelative(lty, lseg), &QPath::TypeRelative(rty, rseg)) => {
 389                 self.eq_ty(lty, rty) && self.eq_path_segment(lseg, rseg)
 390             },
 391             (&QPath::LangItem(llang_item, ..), &QPath::LangItem(rlang_item, ..)) => llang_item == rlang_item,
 392             _ => false,
 393         }
 394     }
 395
 396     pub fn eq_path(&mut self, left: &Path<'_>, right: &Path<'_>) -> bool {
 397         match (left.res, right.res) {
 398             (Res::Local(l), Res::Local(r)) => l == r || self.locals.get(&l) == Some(&r),
 399             (Res::Local(_), _) | (_, Res::Local(_)) => false,
 400             _ => over(left.segments, right.segments, |l, r| self.eq_path_segment(l, r)),
 401         }
 402     }
 403
 404     fn eq_path_parameters(&mut self, left: &GenericArgs<'_>, right: &GenericArgs<'_>) -> bool {
 405         if !(left.parenthesized || right.parenthesized) {
 406             over(left.args, right.args, |l, r| self.eq_generic_arg(l, r)) // FIXME(flip1995): may not work
 407                 && over(left.bindings, right.bindings, |l, r| self.eq_type_binding(l, r))
 408         } else if left.parenthesized && right.parenthesized {
 409             over(left.inputs(), right.inputs(), |l, r| self.eq_ty(l, r))
 410                 && both(&Some(&left.bindings[0].ty()), &Some(&right.bindings[0].ty()), |l, r| {
 411                     self.eq_ty(l, r)
 412                 })
 413         } else {
 414             false
 415         }
 416     }
 417
 418     pub fn eq_path_segments(&mut self, left: &[PathSegment<'_>], right: &[PathSegment<'_>]) -> bool {
 419         left.len() == right.len() && left.iter().zip(right).all(|(l, r)| self.eq_path_segment(l, r))
 420     }
 421
 422     pub fn eq_path_segment(&mut self, left: &PathSegment<'_>, right: &PathSegment<'_>) -> bool {
 423         // The == of idents doesn't work with different contexts,
 424         // we have to be explicit about hygiene
 425         left.ident.name == right.ident.name && both(&left.args, &right.args, |l, r| self.eq_path_parameters(l, r))
 426     }
 427
 428     pub fn eq_ty(&mut self, left: &Ty<'_>, right: &Ty<'_>) -> bool {
 429         match (&left.kind, &right.kind) {
 430             (&TyKind::Slice(l_vec), &TyKind::Slice(r_vec)) => self.eq_ty(l_vec, r_vec),
 431             (&TyKind::Array(lt, ll), &TyKind::Array(rt, rl)) => self.eq_ty(lt, rt) && self.eq_array_length(ll, rl),
 432             (TyKind::Ptr(l_mut), TyKind::Ptr(r_mut)) => l_mut.mutbl == r_mut.mutbl && self.eq_ty(l_mut.ty, r_mut.ty),
 433             (TyKind::Ref(_, l_rmut), TyKind::Ref(_, r_rmut)) => {
 434                 l_rmut.mutbl == r_rmut.mutbl && self.eq_ty(l_rmut.ty, r_rmut.ty)
 435             },
 436             (TyKind::Path(l), TyKind::Path(r)) => self.eq_qpath(l, r),
 437             (&TyKind::Tup(l), &TyKind::Tup(r)) => over(l, r, |l, r| self.eq_ty(l, r)),
 438             (&TyKind::Infer, &TyKind::Infer) => true,
 439             _ => false,
 440         }
 441     }
 442
 443     fn eq_type_binding(&mut self, left: &TypeBinding<'_>, right: &TypeBinding<'_>) -> bool {
 444         left.ident.name == right.ident.name && self.eq_ty(left.ty(), right.ty())
 445     }
 446 }
 447
 448 /// Some simple reductions like `{ return }` => `return`
 449 fn reduce_exprkind<'hir>(cx: &LateContext<'_>, kind: &'hir ExprKind<'hir>) -> &'hir ExprKind<'hir> {
 450     if let ExprKind::Block(block, _) = kind {
 451         match (block.stmts, block.expr) {
 452             // From an `if let` expression without an `else` block. The arm for the implicit wild pattern is an empty
 453             // block with an empty span.
 454             ([], None) if block.span.is_empty() => &ExprKind::Tup(&[]),
 455             // `{}` => `()`
 456             ([], None) => match snippet_opt(cx, block.span) {
 457                 // Don't reduce if there are any tokens contained in the braces
 458                 Some(snip)
 459                     if tokenize(&snip)
 460                         .map(|t| t.kind)
 461                         .filter(|t| {
 462                             !matches!(
 463                                 t,
 464                                 TokenKind::LineComment { .. } | TokenKind::BlockComment { .. } | TokenKind::Whitespace
 465                             )
 466                         })
 467                         .ne([TokenKind::OpenBrace, TokenKind::CloseBrace].iter().copied()) =>
 468                 {
 469                     kind
 470                 },
 471                 _ => &ExprKind::Tup(&[]),
 472             },
 473             ([], Some(expr)) => match expr.kind {
 474                 // `{ return .. }` => `return ..`
 475                 ExprKind::Ret(..) => &expr.kind,
 476                 _ => kind,
 477             },
 478             ([stmt], None) => match stmt.kind {
 479                 StmtKind::Expr(expr) | StmtKind::Semi(expr) => match expr.kind {
 480                     // `{ return ..; }` => `return ..`
 481                     ExprKind::Ret(..) => &expr.kind,
 482                     _ => kind,
 483                 },
 484                 _ => kind,
 485             },
 486             _ => kind,
 487         }
 488     } else {
 489         kind
 490     }
 491 }
 492
 493 fn swap_binop<'a>(
 494     binop: BinOpKind,
 495     lhs: &'a Expr<'a>,
 496     rhs: &'a Expr<'a>,
 497 ) -> Option<(BinOpKind, &'a Expr<'a>, &'a Expr<'a>)> {
 498     match binop {
 499         BinOpKind::Add | BinOpKind::Eq | BinOpKind::Ne | BinOpKind::BitAnd | BinOpKind::BitXor | BinOpKind::BitOr => {
 500             Some((binop, rhs, lhs))
 501         },
 502         BinOpKind::Lt => Some((BinOpKind::Gt, rhs, lhs)),
 503         BinOpKind::Le => Some((BinOpKind::Ge, rhs, lhs)),
 504         BinOpKind::Ge => Some((BinOpKind::Le, rhs, lhs)),
 505         BinOpKind::Gt => Some((BinOpKind::Lt, rhs, lhs)),
 506         BinOpKind::Mul // Not always commutative, e.g. with matrices. See issue #5698
 507         | BinOpKind::Shl
 508         | BinOpKind::Shr
 509         | BinOpKind::Rem
 510         | BinOpKind::Sub
 511         | BinOpKind::Div
 512         | BinOpKind::And
 513         | BinOpKind::Or => None,
 514     }
 515 }
 516
 517 /// Checks if the two `Option`s are both `None` or some equal values as per
 518 /// `eq_fn`.
 519 pub fn both<X>(l: &Option<X>, r: &Option<X>, mut eq_fn: impl FnMut(&X, &X) -> bool) -> bool {
 520     l.as_ref()
 521         .map_or_else(|| r.is_none(), |x| r.as_ref().map_or(false, |y| eq_fn(x, y)))
 522 }
 523
 524 /// Checks if two slices are equal as per `eq_fn`.
 525 pub fn over<X>(left: &[X], right: &[X], mut eq_fn: impl FnMut(&X, &X) -> bool) -> bool {
 526     left.len() == right.len() && left.iter().zip(right).all(|(x, y)| eq_fn(x, y))
 527 }
 528
 529 /// Counts how many elements of the slices are equal as per `eq_fn`.
 530 pub fn count_eq<X: Sized>(
 531     left: &mut dyn Iterator<Item = X>,
 532     right: &mut dyn Iterator<Item = X>,
 533     mut eq_fn: impl FnMut(&X, &X) -> bool,
 534 ) -> usize {
 535     left.zip(right).take_while(|(l, r)| eq_fn(l, r)).count()
 536 }
 537
 538 /// Checks if two expressions evaluate to the same value, and don't contain any side effects.
 539 pub fn eq_expr_value(cx: &LateContext<'_>, left: &Expr<'_>, right: &Expr<'_>) -> bool {
 540     SpanlessEq::new(cx).deny_side_effects().eq_expr(left, right)
 541 }
 542
 543 /// Type used to hash an ast element. This is different from the `Hash` trait
 544 /// on ast types as this
 545 /// trait would consider IDs and spans.
 546 ///
 547 /// All expressions kind are hashed, but some might have a weaker hash.
 548 pub struct SpanlessHash<'a, 'tcx> {
 549     /// Context used to evaluate constant expressions.
 550     cx: &'a LateContext<'tcx>,
 551     maybe_typeck_results: Option<&'tcx TypeckResults<'tcx>>,
 552     s: FxHasher,
 553 }
 554
 555 impl<'a, 'tcx> SpanlessHash<'a, 'tcx> {
 556     pub fn new(cx: &'a LateContext<'tcx>) -> Self {
 557         Self {
 558             cx,
 559             maybe_typeck_results: cx.maybe_typeck_results(),
 560             s: FxHasher::default(),
 561         }
 562     }
 563
 564     pub fn finish(self) -> u64 {
 565         self.s.finish()
 566     }
 567
 568     pub fn hash_block(&mut self, b: &Block<'_>) {
 569         for s in b.stmts {
 570             self.hash_stmt(s);
 571         }
 572
 573         if let Some(e) = b.expr {
 574             self.hash_expr(e);
 575         }
 576
 577         std::mem::discriminant(&b.rules).hash(&mut self.s);
 578     }
 579
 580     #[expect(clippy::too_many_lines)]
 581     pub fn hash_expr(&mut self, e: &Expr<'_>) {
 582         let simple_const = self
 583             .maybe_typeck_results
 584             .and_then(|typeck_results| constant_simple(self.cx, typeck_results, e));
 585
 586         // const hashing may result in the same hash as some unrelated node, so add a sort of
 587         // discriminant depending on which path we're choosing next
 588         simple_const.hash(&mut self.s);
 589         if simple_const.is_some() {
 590             return;
 591         }
 592
 593         std::mem::discriminant(&e.kind).hash(&mut self.s);
 594
 595         match e.kind {
 596             ExprKind::AddrOf(kind, m, e) => {
 597                 std::mem::discriminant(&kind).hash(&mut self.s);
 598                 m.hash(&mut self.s);
 599                 self.hash_expr(e);
 600             },
 601             ExprKind::Continue(i) => {
 602                 if let Some(i) = i.label {
 603                     self.hash_name(i.ident.name);
 604                 }
 605             },
 606             ExprKind::Assign(l, r, _) => {
 607                 self.hash_expr(l);
 608                 self.hash_expr(r);
 609             },
 610             ExprKind::AssignOp(ref o, l, r) => {
 611                 std::mem::discriminant(&o.node).hash(&mut self.s);
 612                 self.hash_expr(l);
 613                 self.hash_expr(r);
 614             },
 615             ExprKind::Block(b, _) => {
 616                 self.hash_block(b);
 617             },
 618             ExprKind::Binary(op, l, r) => {
 619                 std::mem::discriminant(&op.node).hash(&mut self.s);
 620                 self.hash_expr(l);
 621                 self.hash_expr(r);
 622             },
 623             ExprKind::Break(i, ref j) => {
 624                 if let Some(i) = i.label {
 625                     self.hash_name(i.ident.name);
 626                 }
 627                 if let Some(j) = *j {
 628                     self.hash_expr(j);
 629                 }
 630             },
 631             ExprKind::Box(e) | ExprKind::DropTemps(e) | ExprKind::Yield(e, _) => {
 632                 self.hash_expr(e);
 633             },
 634             ExprKind::Call(fun, args) => {
 635                 self.hash_expr(fun);
 636                 self.hash_exprs(args);
 637             },
 638             ExprKind::Cast(e, ty) | ExprKind::Type(e, ty) => {
 639                 self.hash_expr(e);
 640                 self.hash_ty(ty);
 641             },
 642             ExprKind::Closure(&Closure {
 643                 capture_clause, body, ..
 644             }) => {
 645                 std::mem::discriminant(&capture_clause).hash(&mut self.s);
 646                 // closures inherit TypeckResults
 647                 self.hash_expr(self.cx.tcx.hir().body(body).value);
 648             },
 649             ExprKind::Field(e, ref f) => {
 650                 self.hash_expr(e);
 651                 self.hash_name(f.name);
 652             },
 653             ExprKind::Index(a, i) => {
 654                 self.hash_expr(a);
 655                 self.hash_expr(i);
 656             },
 657             ExprKind::InlineAsm(asm) => {
 658                 for piece in asm.template {
 659                     match piece {
 660                         InlineAsmTemplatePiece::String(s) => s.hash(&mut self.s),
 661                         InlineAsmTemplatePiece::Placeholder {
 662                             operand_idx,
 663                             modifier,
 664                             span: _,
 665                         } => {
 666                             operand_idx.hash(&mut self.s);
 667                             modifier.hash(&mut self.s);
 668                         },
 669                     }
 670                 }
 671                 asm.options.hash(&mut self.s);
 672                 for (op, _op_sp) in asm.operands {
 673                     match op {
 674                         InlineAsmOperand::In { reg, expr } => {
 675                             reg.hash(&mut self.s);
 676                             self.hash_expr(expr);
 677                         },
 678                         InlineAsmOperand::Out { reg, late, expr } => {
 679                             reg.hash(&mut self.s);
 680                             late.hash(&mut self.s);
 681                             if let Some(expr) = expr {
 682                                 self.hash_expr(expr);
 683                             }
 684                         },
 685                         InlineAsmOperand::InOut { reg, late, expr } => {
 686                             reg.hash(&mut self.s);
 687                             late.hash(&mut self.s);
 688                             self.hash_expr(expr);
 689                         },
 690                         InlineAsmOperand::SplitInOut {
 691                             reg,
 692                             late,
 693                             in_expr,
 694                             out_expr,
 695                         } => {
 696                             reg.hash(&mut self.s);
 697                             late.hash(&mut self.s);
 698                             self.hash_expr(in_expr);
 699                             if let Some(out_expr) = out_expr {
 700                                 self.hash_expr(out_expr);
 701                             }
 702                         },
 703                         InlineAsmOperand::Const { anon_const } | InlineAsmOperand::SymFn { anon_const } => {
 704                             self.hash_body(anon_const.body);
 705                         },
 706                         InlineAsmOperand::SymStatic { path, def_id: _ } => self.hash_qpath(path),
 707                     }
 708                 }
 709             },
 710             ExprKind::Let(Let { pat, init, ty, .. }) => {
 711                 self.hash_expr(init);
 712                 if let Some(ty) = ty {
 713                     self.hash_ty(ty);
 714                 }
 715                 self.hash_pat(pat);
 716             },
 717             ExprKind::Err(_) => {},
 718             ExprKind::Lit(ref l) => {
 719                 l.node.hash(&mut self.s);
 720             },
 721             ExprKind::Loop(b, ref i, ..) => {
 722                 self.hash_block(b);
 723                 if let Some(i) = *i {
 724                     self.hash_name(i.ident.name);
 725                 }
 726             },
 727             ExprKind::If(cond, then, ref else_opt) => {
 728                 self.hash_expr(cond);
 729                 self.hash_expr(then);
 730                 if let Some(e) = *else_opt {
 731                     self.hash_expr(e);
 732                 }
 733             },
 734             ExprKind::Match(e, arms, ref s) => {
 735                 self.hash_expr(e);
 736
 737                 for arm in arms {
 738                     self.hash_pat(arm.pat);
 739                     if let Some(ref e) = arm.guard {
 740                         self.hash_guard(e);
 741                     }
 742                     self.hash_expr(arm.body);
 743                 }
 744
 745                 s.hash(&mut self.s);
 746             },
 747             ExprKind::MethodCall(path, receiver, args, ref _fn_span) => {
 748                 self.hash_name(path.ident.name);
 749                 self.hash_expr(receiver);
 750                 self.hash_exprs(args);
 751             },
 752             ExprKind::ConstBlock(ref l_id) => {
 753                 self.hash_body(l_id.body);
 754             },
 755             ExprKind::Repeat(e, len) => {
 756                 self.hash_expr(e);
 757                 self.hash_array_length(len);
 758             },
 759             ExprKind::Ret(ref e) => {
 760                 if let Some(e) = *e {
 761                     self.hash_expr(e);
 762                 }
 763             },
 764             ExprKind::Path(ref qpath) => {
 765                 self.hash_qpath(qpath);
 766             },
 767             ExprKind::Struct(path, fields, ref expr) => {
 768                 self.hash_qpath(path);
 769
 770                 for f in fields {
 771                     self.hash_name(f.ident.name);
 772                     self.hash_expr(f.expr);
 773                 }
 774
 775                 if let Some(e) = *expr {
 776                     self.hash_expr(e);
 777                 }
 778             },
 779             ExprKind::Tup(tup) => {
 780                 self.hash_exprs(tup);
 781             },
 782             ExprKind::Array(v) => {
 783                 self.hash_exprs(v);
 784             },
 785             ExprKind::Unary(lop, le) => {
 786                 std::mem::discriminant(&lop).hash(&mut self.s);
 787                 self.hash_expr(le);
 788             },
 789         }
 790     }
 791
 792     pub fn hash_exprs(&mut self, e: &[Expr<'_>]) {
 793         for e in e {
 794             self.hash_expr(e);
 795         }
 796     }
 797
 798     pub fn hash_name(&mut self, n: Symbol) {
 799         n.hash(&mut self.s);
 800     }
 801
 802     pub fn hash_qpath(&mut self, p: &QPath<'_>) {
 803         match *p {
 804             QPath::Resolved(_, path) => {
 805                 self.hash_path(path);
 806             },
 807             QPath::TypeRelative(_, path) => {
 808                 self.hash_name(path.ident.name);
 809             },
 810             QPath::LangItem(lang_item, ..) => {
 811                 std::mem::discriminant(&lang_item).hash(&mut self.s);
 812             },
 813         }
 814         // self.maybe_typeck_results.unwrap().qpath_res(p, id).hash(&mut self.s);
 815     }
 816
 817     pub fn hash_pat(&mut self, pat: &Pat<'_>) {
 818         std::mem::discriminant(&pat.kind).hash(&mut self.s);
 819         match pat.kind {
 820             PatKind::Binding(BindingAnnotation(by_ref, mutability), _, _, pat) => {
 821                 std::mem::discriminant(&by_ref).hash(&mut self.s);
 822                 std::mem::discriminant(&mutability).hash(&mut self.s);
 823                 if let Some(pat) = pat {
 824                     self.hash_pat(pat);
 825                 }
 826             },
 827             PatKind::Box(pat) => self.hash_pat(pat),
 828             PatKind::Lit(expr) => self.hash_expr(expr),
 829             PatKind::Or(pats) => {
 830                 for pat in pats {
 831                     self.hash_pat(pat);
 832                 }
 833             },
 834             PatKind::Path(ref qpath) => self.hash_qpath(qpath),
 835             PatKind::Range(s, e, i) => {
 836                 if let Some(s) = s {
 837                     self.hash_expr(s);
 838                 }
 839                 if let Some(e) = e {
 840                     self.hash_expr(e);
 841                 }
 842                 std::mem::discriminant(&i).hash(&mut self.s);
 843             },
 844             PatKind::Ref(pat, mu) => {
 845                 self.hash_pat(pat);
 846                 std::mem::discriminant(&mu).hash(&mut self.s);
 847             },
 848             PatKind::Slice(l, m, r) => {
 849                 for pat in l {
 850                     self.hash_pat(pat);
 851                 }
 852                 if let Some(pat) = m {
 853                     self.hash_pat(pat);
 854                 }
 855                 for pat in r {
 856                     self.hash_pat(pat);
 857                 }
 858             },
 859             PatKind::Struct(ref qpath, fields, e) => {
 860                 self.hash_qpath(qpath);
 861                 for f in fields {
 862                     self.hash_name(f.ident.name);
 863                     self.hash_pat(f.pat);
 864                 }
 865                 e.hash(&mut self.s);
 866             },
 867             PatKind::Tuple(pats, e) => {
 868                 for pat in pats {
 869                     self.hash_pat(pat);
 870                 }
 871                 e.hash(&mut self.s);
 872             },
 873             PatKind::TupleStruct(ref qpath, pats, e) => {
 874                 self.hash_qpath(qpath);
 875                 for pat in pats {
 876                     self.hash_pat(pat);
 877                 }
 878                 e.hash(&mut self.s);
 879             },
 880             PatKind::Wild => {},
 881         }
 882     }
 883
 884     pub fn hash_path(&mut self, path: &Path<'_>) {
 885         match path.res {
 886             // constant hash since equality is dependant on inter-expression context
 887             // e.g. The expressions `if let Some(x) = foo() {}` and `if let Some(y) = foo() {}` are considered equal
 888             // even though the binding names are different and they have different `HirId`s.
 889             Res::Local(_) => 1_usize.hash(&mut self.s),
 890             _ => {
 891                 for seg in path.segments {
 892                     self.hash_name(seg.ident.name);
 893                     self.hash_generic_args(seg.args().args);
 894                 }
 895             },
 896         }
 897     }
 898
 899     pub fn hash_stmt(&mut self, b: &Stmt<'_>) {
 900         std::mem::discriminant(&b.kind).hash(&mut self.s);
 901
 902         match &b.kind {
 903             StmtKind::Local(local) => {
 904                 self.hash_pat(local.pat);
 905                 if let Some(init) = local.init {
 906                     self.hash_expr(init);
 907                 }
 908                 if let Some(els) = local.els {
 909                     self.hash_block(els);
 910                 }
 911             },
 912             StmtKind::Item(..) => {},
 913             StmtKind::Expr(expr) | StmtKind::Semi(expr) => {
 914                 self.hash_expr(expr);
 915             },
 916         }
 917     }
 918
 919     pub fn hash_guard(&mut self, g: &Guard<'_>) {
 920         match g {
 921             Guard::If(expr) | Guard::IfLet(Let { init: expr, .. }) => {
 922                 self.hash_expr(expr);
 923             },
 924         }
 925     }
 926
 927     pub fn hash_lifetime(&mut self, lifetime: &Lifetime) {
 928         lifetime.ident.name.hash(&mut self.s);
 929         std::mem::discriminant(&lifetime.res).hash(&mut self.s);
 930         if let LifetimeName::Param(param_id) = lifetime.res {
 931             param_id.hash(&mut self.s);
 932         }
 933     }
 934
 935     pub fn hash_ty(&mut self, ty: &Ty<'_>) {
 936         std::mem::discriminant(&ty.kind).hash(&mut self.s);
 937         self.hash_tykind(&ty.kind);
 938     }
 939
 940     pub fn hash_tykind(&mut self, ty: &TyKind<'_>) {
 941         match ty {
 942             TyKind::Slice(ty) => {
 943                 self.hash_ty(ty);
 944             },
 945             &TyKind::Array(ty, len) => {
 946                 self.hash_ty(ty);
 947                 self.hash_array_length(len);
 948             },
 949             TyKind::Ptr(ref mut_ty) => {
 950                 self.hash_ty(mut_ty.ty);
 951                 mut_ty.mutbl.hash(&mut self.s);
 952             },
 953             TyKind::Ref(lifetime, ref mut_ty) => {
 954                 self.hash_lifetime(lifetime);
 955                 self.hash_ty(mut_ty.ty);
 956                 mut_ty.mutbl.hash(&mut self.s);
 957             },
 958             TyKind::BareFn(bfn) => {
 959                 bfn.unsafety.hash(&mut self.s);
 960                 bfn.abi.hash(&mut self.s);
 961                 for arg in bfn.decl.inputs {
 962                     self.hash_ty(arg);
 963                 }
 964                 std::mem::discriminant(&bfn.decl.output).hash(&mut self.s);
 965                 match bfn.decl.output {
 966                     FnRetTy::DefaultReturn(_) => {},
 967                     FnRetTy::Return(ty) => {
 968                         self.hash_ty(ty);
 969                     },
 970                 }
 971                 bfn.decl.c_variadic.hash(&mut self.s);
 972             },
 973             TyKind::Tup(ty_list) => {
 974                 for ty in *ty_list {
 975                     self.hash_ty(ty);
 976                 }
 977             },
 978             TyKind::Path(ref qpath) => self.hash_qpath(qpath),
 979             TyKind::OpaqueDef(_, arg_list, in_trait) => {
 980                 self.hash_generic_args(arg_list);
 981                 in_trait.hash(&mut self.s);
 982             },
 983             TyKind::TraitObject(_, lifetime, _) => {
 984                 self.hash_lifetime(lifetime);
 985             },
 986             TyKind::Typeof(anon_const) => {
 987                 self.hash_body(anon_const.body);
 988             },
 989             TyKind::Err(_) | TyKind::Infer | TyKind::Never => {},
 990         }
 991     }
 992
 993     pub fn hash_array_length(&mut self, length: ArrayLen) {
 994         match length {
 995             ArrayLen::Infer(..) => {},
 996             ArrayLen::Body(anon_const) => self.hash_body(anon_const.body),
 997         }
 998     }
 999
1000     pub fn hash_body(&mut self, body_id: BodyId) {
1001         // swap out TypeckResults when hashing a body
1002         let old_maybe_typeck_results = self.maybe_typeck_results.replace(self.cx.tcx.typeck_body(body_id));
1003         self.hash_expr(self.cx.tcx.hir().body(body_id).value);
1004         self.maybe_typeck_results = old_maybe_typeck_results;
1005     }
1006
1007     fn hash_generic_args(&mut self, arg_list: &[GenericArg<'_>]) {
1008         for arg in arg_list {
1009             match *arg {
1010                 GenericArg::Lifetime(l) => self.hash_lifetime(l),
1011                 GenericArg::Type(ty) => self.hash_ty(ty),
1012                 GenericArg::Const(ref ca) => self.hash_body(ca.value.body),
1013                 GenericArg::Infer(ref inf) => self.hash_ty(&inf.to_ty()),
1014             }
1015         }
1016     }
1017 }
1018
1019 pub fn hash_stmt(cx: &LateContext<'_>, s: &Stmt<'_>) -> u64 {
1020     let mut h = SpanlessHash::new(cx);
1021     h.hash_stmt(s);
1022     h.finish()
1023 }
1024
1025 pub fn is_bool(ty: &Ty<'_>) -> bool {
1026     if let TyKind::Path(QPath::Resolved(_, path)) = ty.kind {
1027         matches!(path.res, Res::PrimTy(PrimTy::Bool))
1028     } else {
1029         false
1030     }
1031 }
1032
1033 pub fn hash_expr(cx: &LateContext<'_>, e: &Expr<'_>) -> u64 {
1034     let mut h = SpanlessHash::new(cx);
1035     h.hash_expr(e);
1036     h.finish()
1037 }