src/utils/hir.rs

   1 use consts::constant;
   2 use rustc::lint::*;
   3 use rustc_front::hir::*;
   4 use std::hash::{Hash, Hasher, SipHasher};
   5 use syntax::ast::Name;
   6 use syntax::ptr::P;
   7 use utils::differing_macro_contexts;
   8
   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.
  11 ///
  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 fonction calls.
  17     ignore_fn: bool,
  18 }
  19
  20 impl<'a, 'tcx: 'a> SpanlessEq<'a, 'tcx> {
  21     pub fn new(cx: &'a LateContext<'a, 'tcx>) -> Self {
  22         SpanlessEq {
  23             cx: cx,
  24             ignore_fn: false,
  25         }
  26     }
  27
  28     pub fn ignore_fn(self) -> Self {
  29         SpanlessEq {
  30             cx: self.cx,
  31             ignore_fn: true,
  32         }
  33     }
  34
  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) {
  40                     // TODO: tys
  41                     l.ty.is_none() && r.ty.is_none() && both(&l.init, &r.init, |l, r| self.eq_expr(l, r))
  42                 } else {
  43                     false
  44                 }
  45             }
  46             (&StmtExpr(ref l, _), &StmtExpr(ref r, _)) |
  47             (&StmtSemi(ref l, _), &StmtSemi(ref r, _)) => self.eq_expr(l, r),
  48             _ => false,
  49         }
  50     }
  51
  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))
  56     }
  57
  58     pub fn eq_expr(&self, left: &Expr, right: &Expr) -> bool {
  59         if self.ignore_fn && differing_macro_contexts(left.span, right.span) {
  60             return false;
  61         }
  62
  63         if let (Some(l), Some(r)) = (constant(self.cx, left), constant(self.cx, right)) {
  64             if l == r {
  65                 return true;
  66             }
  67         }
  68
  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.name.as_str() == r.node.name.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)
  75             }
  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             }
  80             (&ExprBreak(li), &ExprBreak(ri)) => both(&li, &ri, |l, r| l.node.name.as_str() == r.node.name.as_str()),
  81             (&ExprBox(ref l), &ExprBox(ref r)) => self.eq_expr(l, r),
  82             (&ExprCall(ref l_fun, ref l_args), &ExprCall(ref r_fun, ref r_args)) => {
  83                 !self.ignore_fn && self.eq_expr(l_fun, r_fun) && self.eq_exprs(l_args, r_args)
  84             }
  85             (&ExprCast(ref lx, ref lt), &ExprCast(ref rx, ref rt)) => self.eq_expr(lx, rx) && self.eq_ty(lt, rt),
  86             (&ExprField(ref l_f_exp, ref l_f_ident), &ExprField(ref r_f_exp, ref r_f_ident)) => {
  87                 l_f_ident.node == r_f_ident.node && self.eq_expr(l_f_exp, r_f_exp)
  88             }
  89             (&ExprIndex(ref la, ref li), &ExprIndex(ref ra, ref ri)) => self.eq_expr(la, ra) && self.eq_expr(li, ri),
  90             (&ExprIf(ref lc, ref lt, ref le), &ExprIf(ref rc, ref rt, ref re)) => {
  91                 self.eq_expr(lc, rc) && self.eq_block(lt, rt) && both(le, re, |l, r| self.eq_expr(l, r))
  92             }
  93             (&ExprLit(ref l), &ExprLit(ref r)) => l.node == r.node,
  94             (&ExprLoop(ref lb, ref ll), &ExprLoop(ref rb, ref rl)) => {
  95                 self.eq_block(lb, rb) && both(ll, rl, |l, r| l.name.as_str() == r.name.as_str())
  96             }
  97             (&ExprMatch(ref le, ref la, ref ls), &ExprMatch(ref re, ref ra, ref rs)) => {
  98                 ls == rs && self.eq_expr(le, re) &&
  99                 over(la, ra, |l, r| {
 100                     self.eq_expr(&l.body, &r.body) && both(&l.guard, &r.guard, |l, r| self.eq_expr(l, r)) &&
 101                     over(&l.pats, &r.pats, |l, r| self.eq_pat(l, r))
 102                 })
 103             }
 104             (&ExprMethodCall(ref l_name, ref l_tys, ref l_args),
 105              &ExprMethodCall(ref r_name, ref r_tys, ref r_args)) => {
 106                 // TODO: tys
 107                 !self.ignore_fn && l_name.node == r_name.node && l_tys.is_empty() && r_tys.is_empty() &&
 108                 self.eq_exprs(l_args, r_args)
 109             }
 110             (&ExprRepeat(ref le, ref ll), &ExprRepeat(ref re, ref rl)) => self.eq_expr(le, re) && self.eq_expr(ll, rl),
 111             (&ExprRet(ref l), &ExprRet(ref r)) => both(l, r, |l, r| self.eq_expr(l, r)),
 112             (&ExprPath(ref l_qself, ref l_subpath), &ExprPath(ref r_qself, ref r_subpath)) => {
 113                 both(l_qself, r_qself, |l, r| self.eq_qself(l, r)) && self.eq_path(l_subpath, r_subpath)
 114             }
 115             (&ExprStruct(ref l_path, ref lf, ref lo), &ExprStruct(ref r_path, ref rf, ref ro)) => {
 116                 self.eq_path(l_path, r_path) &&
 117                     both(lo, ro, |l, r| self.eq_expr(l, r)) &&
 118                     over(lf, rf, |l, r| self.eq_field(l, r))
 119             }
 120             (&ExprTup(ref l_tup), &ExprTup(ref r_tup)) => self.eq_exprs(l_tup, r_tup),
 121             (&ExprTupField(ref le, li), &ExprTupField(ref re, ri)) => li.node == ri.node && self.eq_expr(le, re),
 122             (&ExprUnary(l_op, ref le), &ExprUnary(r_op, ref re)) => l_op == r_op && self.eq_expr(le, re),
 123             (&ExprVec(ref l), &ExprVec(ref r)) => self.eq_exprs(l, r),
 124             (&ExprWhile(ref lc, ref lb, ref ll), &ExprWhile(ref rc, ref rb, ref rl)) => {
 125                 self.eq_expr(lc, rc) && self.eq_block(lb, rb) && both(ll, rl, |l, r| l.name.as_str() == r.name.as_str())
 126             }
 127             _ => false,
 128         }
 129     }
 130
 131     fn eq_exprs(&self, left: &[P<Expr>], right: &[P<Expr>]) -> bool {
 132         over(left, right, |l, r| self.eq_expr(l, r))
 133     }
 134
 135     fn eq_field(&self, left: &Field, right: &Field) -> bool {
 136         left.name.node == right.name.node && self.eq_expr(&left.expr, &right.expr)
 137     }
 138
 139     /// Check whether two patterns are the same.
 140     pub fn eq_pat(&self, left: &Pat, right: &Pat) -> bool {
 141         match (&left.node, &right.node) {
 142             (&PatKind::Box(ref l), &PatKind::Box(ref r)) => self.eq_pat(l, r),
 143             (&PatKind::TupleStruct(ref lp, ref la), &PatKind::TupleStruct(ref rp, ref ra)) => {
 144                 self.eq_path(lp, rp) && both(la, ra, |l, r| over(l, r, |l, r| self.eq_pat(l, r)))
 145             }
 146             (&PatKind::Ident(ref lb, ref li, ref lp), &PatKind::Ident(ref rb, ref ri, ref rp)) => {
 147                 lb == rb && li.node.name.as_str() == ri.node.name.as_str() && both(lp, rp, |l, r| self.eq_pat(l, r))
 148             }
 149             (&PatKind::Lit(ref l), &PatKind::Lit(ref r)) => self.eq_expr(l, r),
 150             (&PatKind::QPath(ref ls, ref lp), &PatKind::QPath(ref rs, ref rp)) => {
 151                 self.eq_qself(ls, rs) && self.eq_path(lp, rp)
 152             }
 153             (&PatKind::Tup(ref l), &PatKind::Tup(ref r)) => over(l, r, |l, r| self.eq_pat(l, r)),
 154             (&PatKind::Range(ref ls, ref le), &PatKind::Range(ref rs, ref re)) => {
 155                 self.eq_expr(ls, rs) && self.eq_expr(le, re)
 156             }
 157             (&PatKind::Ref(ref le, ref lm), &PatKind::Ref(ref re, ref rm)) => lm == rm && self.eq_pat(le, re),
 158             (&PatKind::Vec(ref ls, ref li, ref le), &PatKind::Vec(ref rs, ref ri, ref re)) => {
 159                 over(ls, rs, |l, r| self.eq_pat(l, r)) && over(le, re, |l, r| self.eq_pat(l, r)) &&
 160                 both(li, ri, |l, r| self.eq_pat(l, r))
 161             }
 162             (&PatKind::Wild, &PatKind::Wild) => true,
 163             _ => false,
 164         }
 165     }
 166
 167     fn eq_path(&self, left: &Path, right: &Path) -> bool {
 168         // The == of idents doesn't work with different contexts,
 169         // we have to be explicit about hygiene
 170         left.global == right.global &&
 171         over(&left.segments,
 172              &right.segments,
 173              |l, r| l.identifier.name.as_str() == r.identifier.name.as_str() && l.parameters == r.parameters)
 174     }
 175
 176     fn eq_qself(&self, left: &QSelf, right: &QSelf) -> bool {
 177         left.ty.node == right.ty.node && left.position == right.position
 178     }
 179
 180     fn eq_ty(&self, left: &Ty, right: &Ty) -> bool {
 181         match (&left.node, &right.node) {
 182             (&TyVec(ref l_vec), &TyVec(ref r_vec)) => self.eq_ty(l_vec, r_vec),
 183             (&TyFixedLengthVec(ref lt, ref ll), &TyFixedLengthVec(ref rt, ref rl)) => {
 184                 self.eq_ty(lt, rt) && self.eq_expr(ll, rl)
 185             }
 186             (&TyPtr(ref l_mut), &TyPtr(ref r_mut)) => l_mut.mutbl == r_mut.mutbl && self.eq_ty(&*l_mut.ty, &*r_mut.ty),
 187             (&TyRptr(_, ref l_rmut), &TyRptr(_, ref r_rmut)) => {
 188                 l_rmut.mutbl == r_rmut.mutbl && self.eq_ty(&*l_rmut.ty, &*r_rmut.ty)
 189             }
 190             (&TyPath(ref lq, ref l_path), &TyPath(ref rq, ref r_path)) => {
 191                 both(lq, rq, |l, r| self.eq_qself(l, r)) && self.eq_path(l_path, r_path)
 192             }
 193             (&TyTup(ref l), &TyTup(ref r)) => over(l, r, |l, r| self.eq_ty(l, r)),
 194             (&TyInfer, &TyInfer) => true,
 195             _ => false,
 196         }
 197     }
 198 }
 199
 200 /// Check if the two `Option`s are both `None` or some equal values as per `eq_fn`.
 201 fn both<X, F>(l: &Option<X>, r: &Option<X>, mut eq_fn: F) -> bool
 202     where F: FnMut(&X, &X) -> bool
 203 {
 204     l.as_ref().map_or_else(|| r.is_none(), |x| r.as_ref().map_or(false, |y| eq_fn(x, y)))
 205 }
 206
 207 /// Check if two slices are equal as per `eq_fn`.
 208 fn over<X, F>(left: &[X], right: &[X], mut eq_fn: F) -> bool
 209     where F: FnMut(&X, &X) -> bool
 210 {
 211     left.len() == right.len() && left.iter().zip(right).all(|(x, y)| eq_fn(x, y))
 212 }
 213
 214
 215 /// Type used to hash an ast element. This is different from the `Hash` trait on ast types as this
 216 /// trait would consider IDs and spans.
 217 ///
 218 /// All expressions kind are hashed, but some might have a weaker hash.
 219 pub struct SpanlessHash<'a, 'tcx: 'a> {
 220     /// Context used to evaluate constant expressions.
 221     cx: &'a LateContext<'a, 'tcx>,
 222     s: SipHasher,
 223 }
 224
 225 impl<'a, 'tcx: 'a> SpanlessHash<'a, 'tcx> {
 226     pub fn new(cx: &'a LateContext<'a, 'tcx>) -> Self {
 227         SpanlessHash {
 228             cx: cx,
 229             s: SipHasher::new(),
 230         }
 231     }
 232
 233     pub fn finish(&self) -> u64 {
 234         self.s.finish()
 235     }
 236
 237     pub fn hash_block(&mut self, b: &Block) {
 238         for s in &b.stmts {
 239             self.hash_stmt(s);
 240         }
 241
 242         if let Some(ref e) = b.expr {
 243             self.hash_expr(e);
 244         }
 245
 246         b.rules.hash(&mut self.s);
 247     }
 248
 249     pub fn hash_expr(&mut self, e: &Expr) {
 250         if let Some(e) = constant(self.cx, e) {
 251             return e.hash(&mut self.s);
 252         }
 253
 254         match e.node {
 255             ExprAddrOf(m, ref e) => {
 256                 let c: fn(_, _) -> _ = ExprAddrOf;
 257                 c.hash(&mut self.s);
 258                 m.hash(&mut self.s);
 259                 self.hash_expr(e);
 260             }
 261             ExprAgain(i) => {
 262                 let c: fn(_) -> _ = ExprAgain;
 263                 c.hash(&mut self.s);
 264                 if let Some(i) = i {
 265                     self.hash_name(&i.node.name);
 266                 }
 267             }
 268             ExprAssign(ref l, ref r) => {
 269                 let c: fn(_, _) -> _ = ExprAssign;
 270                 c.hash(&mut self.s);
 271                 self.hash_expr(l);
 272                 self.hash_expr(r);
 273             }
 274             ExprAssignOp(ref o, ref l, ref r) => {
 275                 let c: fn(_, _, _) -> _ = ExprAssignOp;
 276                 c.hash(&mut self.s);
 277                 o.hash(&mut self.s);
 278                 self.hash_expr(l);
 279                 self.hash_expr(r);
 280             }
 281             ExprBlock(ref b) => {
 282                 let c: fn(_) -> _ = ExprBlock;
 283                 c.hash(&mut self.s);
 284                 self.hash_block(b);
 285             }
 286             ExprBinary(op, ref l, ref r) => {
 287                 let c: fn(_, _, _) -> _ = ExprBinary;
 288                 c.hash(&mut self.s);
 289                 op.node.hash(&mut self.s);
 290                 self.hash_expr(l);
 291                 self.hash_expr(r);
 292             }
 293             ExprBreak(i) => {
 294                 let c: fn(_) -> _ = ExprBreak;
 295                 c.hash(&mut self.s);
 296                 if let Some(i) = i {
 297                     self.hash_name(&i.node.name);
 298                 }
 299             }
 300             ExprBox(ref e) => {
 301                 let c: fn(_) -> _ = ExprBox;
 302                 c.hash(&mut self.s);
 303                 self.hash_expr(e);
 304             }
 305             ExprCall(ref fun, ref args) => {
 306                 let c: fn(_, _) -> _ = ExprCall;
 307                 c.hash(&mut self.s);
 308                 self.hash_expr(fun);
 309                 self.hash_exprs(args);
 310             }
 311             ExprCast(ref e, ref _ty) => {
 312                 let c: fn(_, _) -> _ = ExprCast;
 313                 c.hash(&mut self.s);
 314                 self.hash_expr(e);
 315                 // TODO: _ty
 316             }
 317             ExprClosure(cap, _, ref b) => {
 318                 let c: fn(_, _, _) -> _ = ExprClosure;
 319                 c.hash(&mut self.s);
 320                 cap.hash(&mut self.s);
 321                 self.hash_block(b);
 322             }
 323             ExprField(ref e, ref f) => {
 324                 let c: fn(_, _) -> _ = ExprField;
 325                 c.hash(&mut self.s);
 326                 self.hash_expr(e);
 327                 self.hash_name(&f.node);
 328             }
 329             ExprIndex(ref a, ref i) => {
 330                 let c: fn(_, _) -> _ = ExprIndex;
 331                 c.hash(&mut self.s);
 332                 self.hash_expr(a);
 333                 self.hash_expr(i);
 334             }
 335             ExprInlineAsm(..) => {
 336                 let c: fn(_, _, _) -> _ = ExprInlineAsm;
 337                 c.hash(&mut self.s);
 338             }
 339             ExprIf(ref cond, ref t, ref e) => {
 340                 let c: fn(_, _, _) -> _ = ExprIf;
 341                 c.hash(&mut self.s);
 342                 self.hash_expr(cond);
 343                 self.hash_block(t);
 344                 if let Some(ref e) = *e {
 345                     self.hash_expr(e);
 346                 }
 347             }
 348             ExprLit(ref l) => {
 349                 let c: fn(_) -> _ = ExprLit;
 350                 c.hash(&mut self.s);
 351                 l.hash(&mut self.s);
 352             }
 353             ExprLoop(ref b, ref i) => {
 354                 let c: fn(_, _) -> _ = ExprLoop;
 355                 c.hash(&mut self.s);
 356                 self.hash_block(b);
 357                 if let Some(i) = *i {
 358                     self.hash_name(&i.name);
 359                 }
 360             }
 361             ExprMatch(ref e, ref arms, ref s) => {
 362                 let c: fn(_, _, _) -> _ = ExprMatch;
 363                 c.hash(&mut self.s);
 364                 self.hash_expr(e);
 365
 366                 for arm in arms {
 367                     // TODO: arm.pat?
 368                     if let Some(ref e) = arm.guard {
 369                         self.hash_expr(e);
 370                     }
 371                     self.hash_expr(&arm.body);
 372                 }
 373
 374                 s.hash(&mut self.s);
 375             }
 376             ExprMethodCall(ref name, ref _tys, ref args) => {
 377                 let c: fn(_, _, _) -> _ = ExprMethodCall;
 378                 c.hash(&mut self.s);
 379                 self.hash_name(&name.node);
 380                 self.hash_exprs(args);
 381             }
 382             ExprRepeat(ref e, ref l) => {
 383                 let c: fn(_, _) -> _ = ExprRepeat;
 384                 c.hash(&mut self.s);
 385                 self.hash_expr(e);
 386                 self.hash_expr(l);
 387             }
 388             ExprRet(ref e) => {
 389                 let c: fn(_) -> _ = ExprRet;
 390                 c.hash(&mut self.s);
 391                 if let Some(ref e) = *e {
 392                     self.hash_expr(e);
 393                 }
 394             }
 395             ExprPath(ref _qself, ref subpath) => {
 396                 let c: fn(_, _) -> _ = ExprPath;
 397                 c.hash(&mut self.s);
 398                 self.hash_path(subpath);
 399             }
 400             ExprStruct(ref path, ref fields, ref expr) => {
 401                 let c: fn(_, _, _) -> _ = ExprStruct;
 402                 c.hash(&mut self.s);
 403
 404                 self.hash_path(path);
 405
 406                 for f in fields {
 407                     self.hash_name(&f.name.node);
 408                     self.hash_expr(&f.expr);
 409                 }
 410
 411                 if let Some(ref e) = *expr {
 412                     self.hash_expr(e);
 413                 }
 414             }
 415             ExprTup(ref tup) => {
 416                 let c: fn(_) -> _ = ExprTup;
 417                 c.hash(&mut self.s);
 418                 self.hash_exprs(tup);
 419             }
 420             ExprTupField(ref le, li) => {
 421                 let c: fn(_, _) -> _ = ExprTupField;
 422                 c.hash(&mut self.s);
 423
 424                 self.hash_expr(le);
 425                 li.node.hash(&mut self.s);
 426             }
 427             ExprType(_, _) => {
 428                 let c: fn(_, _) -> _ = ExprType;
 429                 c.hash(&mut self.s);
 430                 // what’s an ExprType anyway?
 431             }
 432             ExprUnary(lop, ref le) => {
 433                 let c: fn(_, _) -> _ = ExprUnary;
 434                 c.hash(&mut self.s);
 435
 436                 lop.hash(&mut self.s);
 437                 self.hash_expr(le);
 438             }
 439             ExprVec(ref v) => {
 440                 let c: fn(_) -> _ = ExprVec;
 441                 c.hash(&mut self.s);
 442
 443                 self.hash_exprs(v);
 444             }
 445             ExprWhile(ref cond, ref b, l) => {
 446                 let c: fn(_, _, _) -> _ = ExprWhile;
 447                 c.hash(&mut self.s);
 448
 449                 self.hash_expr(cond);
 450                 self.hash_block(b);
 451                 if let Some(l) = l {
 452                     self.hash_name(&l.name);
 453                 }
 454             }
 455         }
 456     }
 457
 458     pub fn hash_exprs(&mut self, e: &[P<Expr>]) {
 459         for e in e {
 460             self.hash_expr(e);
 461         }
 462     }
 463
 464     pub fn hash_name(&mut self, n: &Name) {
 465         n.as_str().hash(&mut self.s);
 466     }
 467
 468     pub fn hash_path(&mut self, p: &Path) {
 469         p.global.hash(&mut self.s);
 470         for p in &p.segments {
 471             self.hash_name(&p.identifier.name);
 472         }
 473     }
 474
 475     pub fn hash_stmt(&mut self, b: &Stmt) {
 476         match b.node {
 477             StmtDecl(ref _decl, _) => {
 478                 let c: fn(_, _) -> _ = StmtDecl;
 479                 c.hash(&mut self.s);
 480                 // TODO: decl
 481             }
 482             StmtExpr(ref expr, _) => {
 483                 let c: fn(_, _) -> _ = StmtExpr;
 484                 c.hash(&mut self.s);
 485                 self.hash_expr(expr);
 486             }
 487             StmtSemi(ref expr, _) => {
 488                 let c: fn(_, _) -> _ = StmtSemi;
 489                 c.hash(&mut self.s);
 490                 self.hash_expr(expr);
 491             }
 492         }
 493     }
 494 }