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