4 use std::hash::{Hash, Hasher, SipHasher};
7 use utils::differing_macro_contexts;
9 /// Type used to check whether two ast are the same. This is different from the operator
10 /// `==` on ast types as this operator would compare true equality with ID and span.
12 /// Note that some expressions kinds are not considered but could be added.
13 pub struct SpanlessEq<'a, 'tcx: 'a> {
14 /// Context used to evaluate constant expressions.
15 cx: &'a LateContext<'a, 'tcx>,
16 /// If is true, never consider as equal expressions containing function calls.
20 impl<'a, 'tcx: 'a> SpanlessEq<'a, 'tcx> {
21 pub fn new(cx: &'a LateContext<'a, 'tcx>) -> Self {
28 pub fn ignore_fn(self) -> Self {
35 /// Check whether two statements are the same.
36 pub fn eq_stmt(&self, left: &Stmt, right: &Stmt) -> bool {
37 match (&left.node, &right.node) {
38 (&StmtDecl(ref l, _), &StmtDecl(ref r, _)) => {
39 if let (&DeclLocal(ref l), &DeclLocal(ref r)) = (&l.node, &r.node) {
41 l.ty.is_none() && r.ty.is_none() && both(&l.init, &r.init, |l, r| self.eq_expr(l, r))
46 (&StmtExpr(ref l, _), &StmtExpr(ref r, _)) |
47 (&StmtSemi(ref l, _), &StmtSemi(ref r, _)) => self.eq_expr(l, r),
52 /// Check whether two blocks are the same.
53 pub fn eq_block(&self, left: &Block, right: &Block) -> bool {
54 over(&left.stmts, &right.stmts, |l, r| self.eq_stmt(l, r)) &&
55 both(&left.expr, &right.expr, |l, r| self.eq_expr(l, r))
58 pub fn eq_expr(&self, left: &Expr, right: &Expr) -> bool {
59 if self.ignore_fn && differing_macro_contexts(left.span, right.span) {
63 if let (Some(l), Some(r)) = (constant(self.cx, left), constant(self.cx, right)) {
69 match (&left.node, &right.node) {
70 (&ExprAddrOf(l_mut, ref le), &ExprAddrOf(r_mut, ref re)) => l_mut == r_mut && self.eq_expr(le, re),
71 (&ExprAgain(li), &ExprAgain(ri)) => both(&li, &ri, |l, r| l.node.as_str() == r.node.as_str()),
72 (&ExprAssign(ref ll, ref lr), &ExprAssign(ref rl, ref rr)) => self.eq_expr(ll, rl) && self.eq_expr(lr, rr),
73 (&ExprAssignOp(ref lo, ref ll, ref lr), &ExprAssignOp(ref ro, ref rl, ref rr)) => {
74 lo.node == ro.node && self.eq_expr(ll, rl) && self.eq_expr(lr, rr)
76 (&ExprBlock(ref l), &ExprBlock(ref r)) => self.eq_block(l, r),
77 (&ExprBinary(l_op, ref ll, ref lr), &ExprBinary(r_op, ref rl, ref rr)) => {
78 l_op.node == r_op.node && self.eq_expr(ll, rl) && self.eq_expr(lr, rr) ||
79 swap_binop(l_op.node, ll, lr).map_or(false, |(l_op, ll, lr)| {
80 l_op == r_op.node && self.eq_expr(ll, rl) && self.eq_expr(lr, rr)
83 (&ExprBreak(li), &ExprBreak(ri)) => both(&li, &ri, |l, r| l.node.as_str() == r.node.as_str()),
84 (&ExprBox(ref l), &ExprBox(ref r)) => self.eq_expr(l, r),
85 (&ExprCall(ref l_fun, ref l_args), &ExprCall(ref r_fun, ref r_args)) => {
86 !self.ignore_fn && self.eq_expr(l_fun, r_fun) && self.eq_exprs(l_args, r_args)
88 (&ExprCast(ref lx, ref lt), &ExprCast(ref rx, ref rt)) => self.eq_expr(lx, rx) && self.eq_ty(lt, rt),
89 (&ExprField(ref l_f_exp, ref l_f_ident), &ExprField(ref r_f_exp, ref r_f_ident)) => {
90 l_f_ident.node == r_f_ident.node && self.eq_expr(l_f_exp, r_f_exp)
92 (&ExprIndex(ref la, ref li), &ExprIndex(ref ra, ref ri)) => self.eq_expr(la, ra) && self.eq_expr(li, ri),
93 (&ExprIf(ref lc, ref lt, ref le), &ExprIf(ref rc, ref rt, ref re)) => {
94 self.eq_expr(lc, rc) && self.eq_block(lt, rt) && both(le, re, |l, r| self.eq_expr(l, r))
96 (&ExprLit(ref l), &ExprLit(ref r)) => l.node == r.node,
97 (&ExprLoop(ref lb, ref ll), &ExprLoop(ref rb, ref rl)) => {
98 self.eq_block(lb, rb) && both(ll, rl, |l, r| l.as_str() == r.as_str())
100 (&ExprMatch(ref le, ref la, ref ls), &ExprMatch(ref re, ref ra, ref rs)) => {
101 ls == rs && self.eq_expr(le, re) &&
102 over(la, ra, |l, r| {
103 self.eq_expr(&l.body, &r.body) && both(&l.guard, &r.guard, |l, r| self.eq_expr(l, r)) &&
104 over(&l.pats, &r.pats, |l, r| self.eq_pat(l, r))
107 (&ExprMethodCall(ref l_name, ref l_tys, ref l_args),
108 &ExprMethodCall(ref r_name, ref r_tys, ref r_args)) => {
110 !self.ignore_fn && l_name.node == r_name.node && l_tys.is_empty() && r_tys.is_empty() &&
111 self.eq_exprs(l_args, r_args)
113 (&ExprRepeat(ref le, ref ll), &ExprRepeat(ref re, ref rl)) => self.eq_expr(le, re) && self.eq_expr(ll, rl),
114 (&ExprRet(ref l), &ExprRet(ref r)) => both(l, r, |l, r| self.eq_expr(l, r)),
115 (&ExprPath(ref l_qself, ref l_subpath), &ExprPath(ref r_qself, ref r_subpath)) => {
116 both(l_qself, r_qself, |l, r| self.eq_qself(l, r)) && self.eq_path(l_subpath, r_subpath)
118 (&ExprStruct(ref l_path, ref lf, ref lo), &ExprStruct(ref r_path, ref rf, ref ro)) => {
119 self.eq_path(l_path, r_path) && both(lo, ro, |l, r| self.eq_expr(l, r)) &&
120 over(lf, rf, |l, r| self.eq_field(l, r))
122 (&ExprTup(ref l_tup), &ExprTup(ref r_tup)) => self.eq_exprs(l_tup, r_tup),
123 (&ExprTupField(ref le, li), &ExprTupField(ref re, ri)) => li.node == ri.node && self.eq_expr(le, re),
124 (&ExprUnary(l_op, ref le), &ExprUnary(r_op, ref re)) => l_op == r_op && self.eq_expr(le, re),
125 (&ExprVec(ref l), &ExprVec(ref r)) => self.eq_exprs(l, r),
126 (&ExprWhile(ref lc, ref lb, ref ll), &ExprWhile(ref rc, ref rb, ref rl)) => {
127 self.eq_expr(lc, rc) && self.eq_block(lb, rb) && both(ll, rl, |l, r| l.as_str() == r.as_str())
133 fn eq_exprs(&self, left: &[P<Expr>], right: &[P<Expr>]) -> bool {
134 over(left, right, |l, r| self.eq_expr(l, r))
137 fn eq_field(&self, left: &Field, right: &Field) -> bool {
138 left.name.node == right.name.node && self.eq_expr(&left.expr, &right.expr)
141 /// Check whether two patterns are the same.
142 pub fn eq_pat(&self, left: &Pat, right: &Pat) -> bool {
143 match (&left.node, &right.node) {
144 (&PatKind::Box(ref l), &PatKind::Box(ref r)) => self.eq_pat(l, r),
145 (&PatKind::TupleStruct(ref lp, ref la), &PatKind::TupleStruct(ref rp, ref ra)) => {
146 self.eq_path(lp, rp) && both(la, ra, |l, r| over(l, r, |l, r| self.eq_pat(l, r)))
148 (&PatKind::Ident(ref lb, ref li, ref lp), &PatKind::Ident(ref rb, ref ri, ref rp)) => {
149 lb == rb && li.node.as_str() == ri.node.as_str() && both(lp, rp, |l, r| self.eq_pat(l, r))
151 (&PatKind::Lit(ref l), &PatKind::Lit(ref r)) => self.eq_expr(l, r),
152 (&PatKind::QPath(ref ls, ref lp), &PatKind::QPath(ref rs, ref rp)) => {
153 self.eq_qself(ls, rs) && self.eq_path(lp, rp)
155 (&PatKind::Tup(ref l), &PatKind::Tup(ref r)) => over(l, r, |l, r| self.eq_pat(l, r)),
156 (&PatKind::Range(ref ls, ref le), &PatKind::Range(ref rs, ref re)) => {
157 self.eq_expr(ls, rs) && self.eq_expr(le, re)
159 (&PatKind::Ref(ref le, ref lm), &PatKind::Ref(ref re, ref rm)) => lm == rm && self.eq_pat(le, re),
160 (&PatKind::Vec(ref ls, ref li, ref le), &PatKind::Vec(ref rs, ref ri, ref re)) => {
161 over(ls, rs, |l, r| self.eq_pat(l, r)) && over(le, re, |l, r| self.eq_pat(l, r)) &&
162 both(li, ri, |l, r| self.eq_pat(l, r))
164 (&PatKind::Wild, &PatKind::Wild) => true,
169 fn eq_path(&self, left: &Path, right: &Path) -> bool {
170 // The == of idents doesn't work with different contexts,
171 // we have to be explicit about hygiene
172 left.global == right.global &&
175 |l, r| l.name.as_str() == r.name.as_str() && l.parameters == r.parameters)
178 fn eq_qself(&self, left: &QSelf, right: &QSelf) -> bool {
179 left.ty.node == right.ty.node && left.position == right.position
182 fn eq_ty(&self, left: &Ty, right: &Ty) -> bool {
183 match (&left.node, &right.node) {
184 (&TyVec(ref l_vec), &TyVec(ref r_vec)) => self.eq_ty(l_vec, r_vec),
185 (&TyFixedLengthVec(ref lt, ref ll), &TyFixedLengthVec(ref rt, ref rl)) => {
186 self.eq_ty(lt, rt) && self.eq_expr(ll, rl)
188 (&TyPtr(ref l_mut), &TyPtr(ref r_mut)) => l_mut.mutbl == r_mut.mutbl && self.eq_ty(&*l_mut.ty, &*r_mut.ty),
189 (&TyRptr(_, ref l_rmut), &TyRptr(_, ref r_rmut)) => {
190 l_rmut.mutbl == r_rmut.mutbl && self.eq_ty(&*l_rmut.ty, &*r_rmut.ty)
192 (&TyPath(ref lq, ref l_path), &TyPath(ref rq, ref r_path)) => {
193 both(lq, rq, |l, r| self.eq_qself(l, r)) && self.eq_path(l_path, r_path)
195 (&TyTup(ref l), &TyTup(ref r)) => over(l, r, |l, r| self.eq_ty(l, r)),
196 (&TyInfer, &TyInfer) => true,
202 fn swap_binop<'a>(binop: BinOp_, lhs: &'a Expr, rhs: &'a Expr) -> Option<(BinOp_, &'a Expr, &'a Expr)> {
210 BiBitOr => Some((binop, rhs, lhs)),
211 BiLt => Some((BiGt, rhs, lhs)),
212 BiLe => Some((BiGe, rhs, lhs)),
213 BiGe => Some((BiLe, rhs, lhs)),
214 BiGt => Some((BiLt, rhs, lhs)),
215 BiShl | BiShr | BiRem | BiSub | BiDiv | BiAnd | BiOr => None,
219 /// Check if the two `Option`s are both `None` or some equal values as per `eq_fn`.
220 fn both<X, F>(l: &Option<X>, r: &Option<X>, mut eq_fn: F) -> bool
221 where F: FnMut(&X, &X) -> bool
223 l.as_ref().map_or_else(|| r.is_none(), |x| r.as_ref().map_or(false, |y| eq_fn(x, y)))
226 /// Check if two slices are equal as per `eq_fn`.
227 fn over<X, F>(left: &[X], right: &[X], mut eq_fn: F) -> bool
228 where F: FnMut(&X, &X) -> bool
230 left.len() == right.len() && left.iter().zip(right).all(|(x, y)| eq_fn(x, y))
234 /// Type used to hash an ast element. This is different from the `Hash` trait on ast types as this
235 /// trait would consider IDs and spans.
237 /// All expressions kind are hashed, but some might have a weaker hash.
238 pub struct SpanlessHash<'a, 'tcx: 'a> {
239 /// Context used to evaluate constant expressions.
240 cx: &'a LateContext<'a, 'tcx>,
244 impl<'a, 'tcx: 'a> SpanlessHash<'a, 'tcx> {
245 pub fn new(cx: &'a LateContext<'a, 'tcx>) -> Self {
252 pub fn finish(&self) -> u64 {
256 pub fn hash_block(&mut self, b: &Block) {
261 if let Some(ref e) = b.expr {
265 b.rules.hash(&mut self.s);
268 pub fn hash_expr(&mut self, e: &Expr) {
269 if let Some(e) = constant(self.cx, e) {
270 return e.hash(&mut self.s);
274 ExprAddrOf(m, ref e) => {
275 let c: fn(_, _) -> _ = ExprAddrOf;
281 let c: fn(_) -> _ = ExprAgain;
284 self.hash_name(&i.node);
287 ExprAssign(ref l, ref r) => {
288 let c: fn(_, _) -> _ = ExprAssign;
293 ExprAssignOp(ref o, ref l, ref r) => {
294 let c: fn(_, _, _) -> _ = ExprAssignOp;
300 ExprBlock(ref b) => {
301 let c: fn(_) -> _ = ExprBlock;
305 ExprBinary(op, ref l, ref r) => {
306 let c: fn(_, _, _) -> _ = ExprBinary;
308 op.node.hash(&mut self.s);
313 let c: fn(_) -> _ = ExprBreak;
316 self.hash_name(&i.node);
320 let c: fn(_) -> _ = ExprBox;
324 ExprCall(ref fun, ref args) => {
325 let c: fn(_, _) -> _ = ExprCall;
328 self.hash_exprs(args);
330 ExprCast(ref e, ref _ty) => {
331 let c: fn(_, _) -> _ = ExprCast;
336 ExprClosure(cap, _, ref b, _) => {
337 let c: fn(_, _, _, _) -> _ = ExprClosure;
339 cap.hash(&mut self.s);
342 ExprField(ref e, ref f) => {
343 let c: fn(_, _) -> _ = ExprField;
346 self.hash_name(&f.node);
348 ExprIndex(ref a, ref i) => {
349 let c: fn(_, _) -> _ = ExprIndex;
354 ExprInlineAsm(..) => {
355 let c: fn(_, _, _) -> _ = ExprInlineAsm;
358 ExprIf(ref cond, ref t, ref e) => {
359 let c: fn(_, _, _) -> _ = ExprIf;
361 self.hash_expr(cond);
363 if let Some(ref e) = *e {
368 let c: fn(_) -> _ = ExprLit;
372 ExprLoop(ref b, ref i) => {
373 let c: fn(_, _) -> _ = ExprLoop;
376 if let Some(i) = *i {
380 ExprMatch(ref e, ref arms, ref s) => {
381 let c: fn(_, _, _) -> _ = ExprMatch;
387 if let Some(ref e) = arm.guard {
390 self.hash_expr(&arm.body);
395 ExprMethodCall(ref name, ref _tys, ref args) => {
396 let c: fn(_, _, _) -> _ = ExprMethodCall;
398 self.hash_name(&name.node);
399 self.hash_exprs(args);
401 ExprRepeat(ref e, ref l) => {
402 let c: fn(_, _) -> _ = ExprRepeat;
408 let c: fn(_) -> _ = ExprRet;
410 if let Some(ref e) = *e {
414 ExprPath(ref _qself, ref subpath) => {
415 let c: fn(_, _) -> _ = ExprPath;
417 self.hash_path(subpath);
419 ExprStruct(ref path, ref fields, ref expr) => {
420 let c: fn(_, _, _) -> _ = ExprStruct;
423 self.hash_path(path);
426 self.hash_name(&f.name.node);
427 self.hash_expr(&f.expr);
430 if let Some(ref e) = *expr {
434 ExprTup(ref tup) => {
435 let c: fn(_) -> _ = ExprTup;
437 self.hash_exprs(tup);
439 ExprTupField(ref le, li) => {
440 let c: fn(_, _) -> _ = ExprTupField;
444 li.node.hash(&mut self.s);
447 let c: fn(_, _) -> _ = ExprType;
449 // what’s an ExprType anyway?
451 ExprUnary(lop, ref le) => {
452 let c: fn(_, _) -> _ = ExprUnary;
455 lop.hash(&mut self.s);
459 let c: fn(_) -> _ = ExprVec;
464 ExprWhile(ref cond, ref b, l) => {
465 let c: fn(_, _, _) -> _ = ExprWhile;
468 self.hash_expr(cond);
477 pub fn hash_exprs(&mut self, e: &[P<Expr>]) {
483 pub fn hash_name(&mut self, n: &Name) {
484 n.as_str().hash(&mut self.s);
487 pub fn hash_path(&mut self, p: &Path) {
488 p.global.hash(&mut self.s);
489 for p in &p.segments {
490 self.hash_name(&p.name);
494 pub fn hash_stmt(&mut self, b: &Stmt) {
496 StmtDecl(ref _decl, _) => {
497 let c: fn(_, _) -> _ = StmtDecl;
501 StmtExpr(ref expr, _) => {
502 let c: fn(_, _) -> _ = StmtExpr;
504 self.hash_expr(expr);
506 StmtSemi(ref expr, _) => {
507 let c: fn(_, _) -> _ = StmtSemi;
509 self.hash_expr(expr);