src/librustc_incremental/calculate_svh/svh_visitor.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use self::SawExprComponent::*;
  12 use self::SawAbiComponent::*;
  13 use self::SawItemComponent::*;
  14 use self::SawPatComponent::*;
  15 use self::SawTyComponent::*;
  16 use self::SawTraitOrImplItemComponent::*;
  17 use syntax::abi::Abi;
  18 use syntax::ast::{self, Name, NodeId};
  19 use syntax::attr;
  20 use syntax::parse::token;
  21 use syntax_pos::{Span, NO_EXPANSION, COMMAND_LINE_EXPN, BytePos};
  22 use syntax::tokenstream;
  23 use rustc::hir;
  24 use rustc::hir::*;
  25 use rustc::hir::def::{Def, PathResolution};
  26 use rustc::hir::def_id::DefId;
  27 use rustc::hir::intravisit as visit;
  28 use rustc::ty::TyCtxt;
  29 use rustc_data_structures::fnv;
  30 use std::hash::Hash;
  31
  32 use super::def_path_hash::DefPathHashes;
  33 use super::caching_codemap_view::CachingCodemapView;
  34 use super::hasher::IchHasher;
  35
  36 const IGNORED_ATTRIBUTES: &'static [&'static str] = &[
  37     "cfg",
  38     ::ATTR_IF_THIS_CHANGED,
  39     ::ATTR_THEN_THIS_WOULD_NEED,
  40     ::ATTR_DIRTY,
  41     ::ATTR_CLEAN,
  42     ::ATTR_DIRTY_METADATA,
  43     ::ATTR_CLEAN_METADATA
  44 ];
  45
  46 pub struct StrictVersionHashVisitor<'a, 'hash: 'a, 'tcx: 'hash> {
  47     pub tcx: TyCtxt<'hash, 'tcx, 'tcx>,
  48     pub st: &'a mut IchHasher,
  49     // collect a deterministic hash of def-ids that we have seen
  50     def_path_hashes: &'a mut DefPathHashes<'hash, 'tcx>,
  51     hash_spans: bool,
  52     codemap: &'a mut CachingCodemapView<'tcx>,
  53     overflow_checks_enabled: bool,
  54 }
  55
  56 impl<'a, 'hash, 'tcx> StrictVersionHashVisitor<'a, 'hash, 'tcx> {
  57     pub fn new(st: &'a mut IchHasher,
  58                tcx: TyCtxt<'hash, 'tcx, 'tcx>,
  59                def_path_hashes: &'a mut DefPathHashes<'hash, 'tcx>,
  60                codemap: &'a mut CachingCodemapView<'tcx>,
  61                hash_spans: bool)
  62                -> Self {
  63         let check_overflow = tcx.sess.opts.debugging_opts.force_overflow_checks
  64             .unwrap_or(tcx.sess.opts.debug_assertions);
  65
  66         StrictVersionHashVisitor {
  67             st: st,
  68             tcx: tcx,
  69             def_path_hashes: def_path_hashes,
  70             hash_spans: hash_spans,
  71             codemap: codemap,
  72             overflow_checks_enabled: check_overflow,
  73         }
  74     }
  75
  76     fn compute_def_id_hash(&mut self, def_id: DefId) -> u64 {
  77         self.def_path_hashes.hash(def_id)
  78     }
  79
  80     // Hash a span in a stable way. We can't directly hash the span's BytePos
  81     // fields (that would be similar to hashing pointers, since those are just
  82     // offsets into the CodeMap). Instead, we hash the (file name, line, column)
  83     // triple, which stays the same even if the containing FileMap has moved
  84     // within the CodeMap.
  85     // Also note that we are hashing byte offsets for the column, not unicode
  86     // codepoint offsets. For the purpose of the hash that's sufficient.
  87     // Also, hashing filenames is expensive so we avoid doing it twice when the
  88     // span starts and ends in the same file, which is almost always the case.
  89     fn hash_span(&mut self, span: Span) {
  90         debug!("hash_span: st={:?}", self.st);
  91
  92         // If this is not an empty or invalid span, we want to hash the last
  93         // position that belongs to it, as opposed to hashing the first
  94         // position past it.
  95         let span_hi = if span.hi > span.lo {
  96             // We might end up in the middle of a multibyte character here,
  97             // but that's OK, since we are not trying to decode anything at
  98             // this position.
  99             span.hi - BytePos(1)
 100         } else {
 101             span.hi
 102         };
 103
 104         let expn_kind = match span.expn_id {
 105             NO_EXPANSION => SawSpanExpnKind::NoExpansion,
 106             COMMAND_LINE_EXPN => SawSpanExpnKind::CommandLine,
 107             _ => SawSpanExpnKind::SomeExpansion,
 108         };
 109
 110         let loc1 = self.codemap.byte_pos_to_line_and_col(span.lo);
 111         let loc1 = loc1.as_ref()
 112                        .map(|&(ref fm, line, col)| (&fm.name[..], line, col))
 113                        .unwrap_or(("???", 0, BytePos(0)));
 114
 115         let loc2 = self.codemap.byte_pos_to_line_and_col(span_hi);
 116         let loc2 = loc2.as_ref()
 117                        .map(|&(ref fm, line, col)| (&fm.name[..], line, col))
 118                        .unwrap_or(("???", 0, BytePos(0)));
 119
 120         let saw = if loc1.0 == loc2.0 {
 121             SawSpan(loc1.0,
 122                     loc1.1, loc1.2,
 123                     loc2.1, loc2.2,
 124                     expn_kind)
 125         } else {
 126             SawSpanTwoFiles(loc1.0, loc1.1, loc1.2,
 127                             loc2.0, loc2.1, loc2.2,
 128                             expn_kind)
 129         };
 130         saw.hash(self.st);
 131
 132         if expn_kind == SawSpanExpnKind::SomeExpansion {
 133             let call_site = self.codemap.codemap().source_callsite(span);
 134             self.hash_span(call_site);
 135         }
 136     }
 137
 138     fn hash_discriminant<T>(&mut self, v: &T) {
 139         unsafe {
 140             let disr = ::std::intrinsics::discriminant_value(v);
 141             debug!("hash_discriminant: disr={}, st={:?}", disr, self.st);
 142             disr.hash(self.st);
 143         }
 144     }
 145 }
 146
 147 // To off-load the bulk of the hash-computation on #[derive(Hash)],
 148 // we define a set of enums corresponding to the content that our
 149 // crate visitor will encounter as it traverses the ast.
 150 //
 151 // The important invariant is that all of the Saw*Component enums
 152 // do not carry any Spans, Names, or Idents.
 153 //
 154 // Not carrying any Names/Idents is the important fix for problem
 155 // noted on PR #13948: using the ident.name as the basis for a
 156 // hash leads to unstable SVH, because ident.name is just an index
 157 // into intern table (i.e. essentially a random address), not
 158 // computed from the name content.
 159 //
 160 // With the below enums, the SVH computation is not sensitive to
 161 // artifacts of how rustc was invoked nor of how the source code
 162 // was laid out.  (Or at least it is *less* sensitive.)
 163
 164 // This enum represents the different potential bits of code the
 165 // visitor could encounter that could affect the ABI for the crate,
 166 // and assigns each a distinct tag to feed into the hash computation.
 167 #[derive(Hash)]
 168 enum SawAbiComponent<'a> {
 169
 170     // FIXME (#14132): should we include (some function of)
 171     // ident.ctxt as well?
 172     SawIdent(token::InternedString),
 173     SawStructDef(token::InternedString),
 174
 175     SawLifetime,
 176     SawLifetimeDef(usize),
 177
 178     SawMod,
 179     SawForeignItem,
 180     SawItem(SawItemComponent),
 181     SawTy(SawTyComponent),
 182     SawGenerics,
 183     SawTraitItem(SawTraitOrImplItemComponent),
 184     SawImplItem(SawTraitOrImplItemComponent),
 185     SawStructField,
 186     SawVariant,
 187     SawPath(bool),
 188     SawPathSegment,
 189     SawPathParameters,
 190     SawPathListItem,
 191     SawBlock,
 192     SawPat(SawPatComponent),
 193     SawLocal,
 194     SawArm,
 195     SawExpr(SawExprComponent<'a>),
 196     SawStmt,
 197     SawVis,
 198     SawAssociatedItemKind(hir::AssociatedItemKind),
 199     SawDefaultness(hir::Defaultness),
 200     SawWherePredicate,
 201     SawTyParamBound,
 202     SawPolyTraitRef,
 203     SawAssocTypeBinding,
 204     SawAttribute(ast::AttrStyle),
 205     SawMacroDef,
 206     SawSpan(&'a str,
 207             usize, BytePos,
 208             usize, BytePos,
 209             SawSpanExpnKind),
 210     SawSpanTwoFiles(&'a str, usize, BytePos,
 211                     &'a str, usize, BytePos,
 212                     SawSpanExpnKind),
 213 }
 214
 215 /// SawExprComponent carries all of the information that we want
 216 /// to include in the hash that *won't* be covered by the
 217 /// subsequent recursive traversal of the expression's
 218 /// substructure by the visitor.
 219 ///
 220 /// We know every Expr_ variant is covered by a variant because
 221 /// `fn saw_expr` maps each to some case below.  Ensuring that
 222 /// each variant carries an appropriate payload has to be verified
 223 /// by hand.
 224 ///
 225 /// (However, getting that *exactly* right is not so important
 226 /// because the SVH is just a developer convenience; there is no
 227 /// guarantee of collision-freedom, hash collisions are just
 228 /// (hopefully) unlikely.)
 229 ///
 230 /// The xxxComponent enums and saw_xxx functions for Item, Pat,
 231 /// Ty, TraitItem and ImplItem follow the same methodology.
 232 #[derive(Hash)]
 233 enum SawExprComponent<'a> {
 234
 235     SawExprLoop(Option<token::InternedString>),
 236     SawExprField(token::InternedString),
 237     SawExprTupField(usize),
 238     SawExprBreak(Option<token::InternedString>),
 239     SawExprAgain(Option<token::InternedString>),
 240
 241     SawExprBox,
 242     SawExprArray,
 243     SawExprCall,
 244     SawExprMethodCall,
 245     SawExprTup,
 246     SawExprBinary(hir::BinOp_),
 247     SawExprUnary(hir::UnOp),
 248     SawExprLit(ast::LitKind),
 249     SawExprCast,
 250     SawExprType,
 251     SawExprIf,
 252     SawExprWhile,
 253     SawExprMatch,
 254     SawExprClosure(CaptureClause),
 255     SawExprBlock,
 256     SawExprAssign,
 257     SawExprAssignOp(hir::BinOp_),
 258     SawExprIndex,
 259     SawExprPath(Option<usize>),
 260     SawExprAddrOf(hir::Mutability),
 261     SawExprRet,
 262     SawExprInlineAsm(&'a hir::InlineAsm),
 263     SawExprStruct,
 264     SawExprRepeat,
 265 }
 266
 267 // The boolean returned indicates whether the span of this expression is always
 268 // significant, regardless of debuginfo.
 269 fn saw_expr<'a>(node: &'a Expr_,
 270                 overflow_checks_enabled: bool)
 271                 -> (SawExprComponent<'a>, bool) {
 272     let binop_can_panic_at_runtime = |binop| {
 273         match binop {
 274             BiAdd |
 275             BiSub |
 276             BiMul => overflow_checks_enabled,
 277
 278             BiDiv |
 279             BiRem => true,
 280
 281             BiAnd |
 282             BiOr |
 283             BiBitXor |
 284             BiBitAnd |
 285             BiBitOr |
 286             BiShl |
 287             BiShr |
 288             BiEq |
 289             BiLt |
 290             BiLe |
 291             BiNe |
 292             BiGe |
 293             BiGt => false
 294         }
 295     };
 296
 297     let unop_can_panic_at_runtime = |unop| {
 298         match unop {
 299             UnDeref |
 300             UnNot => false,
 301             UnNeg => overflow_checks_enabled,
 302         }
 303     };
 304
 305     match *node {
 306         ExprBox(..)              => (SawExprBox, false),
 307         ExprArray(..)            => (SawExprArray, false),
 308         ExprCall(..)             => (SawExprCall, false),
 309         ExprMethodCall(..)       => (SawExprMethodCall, false),
 310         ExprTup(..)              => (SawExprTup, false),
 311         ExprBinary(op, ..)       => {
 312             (SawExprBinary(op.node), binop_can_panic_at_runtime(op.node))
 313         }
 314         ExprUnary(op, _)         => {
 315             (SawExprUnary(op), unop_can_panic_at_runtime(op))
 316         }
 317         ExprLit(ref lit)         => (SawExprLit(lit.node.clone()), false),
 318         ExprCast(..)             => (SawExprCast, false),
 319         ExprType(..)             => (SawExprType, false),
 320         ExprIf(..)               => (SawExprIf, false),
 321         ExprWhile(..)            => (SawExprWhile, false),
 322         ExprLoop(_, id)          => (SawExprLoop(id.map(|id| id.node.as_str())), false),
 323         ExprMatch(..)            => (SawExprMatch, false),
 324         ExprClosure(cc, _, _, _) => (SawExprClosure(cc), false),
 325         ExprBlock(..)            => (SawExprBlock, false),
 326         ExprAssign(..)           => (SawExprAssign, false),
 327         ExprAssignOp(op, ..)     => {
 328             (SawExprAssignOp(op.node), binop_can_panic_at_runtime(op.node))
 329         }
 330         ExprField(_, name)       => (SawExprField(name.node.as_str()), false),
 331         ExprTupField(_, id)      => (SawExprTupField(id.node), false),
 332         ExprIndex(..)            => (SawExprIndex, true),
 333         ExprPath(ref qself, _)   => (SawExprPath(qself.as_ref().map(|q| q.position)), false),
 334         ExprAddrOf(m, _)         => (SawExprAddrOf(m), false),
 335         ExprBreak(id)            => (SawExprBreak(id.map(|id| id.node.as_str())), false),
 336         ExprAgain(id)            => (SawExprAgain(id.map(|id| id.node.as_str())), false),
 337         ExprRet(..)              => (SawExprRet, false),
 338         ExprInlineAsm(ref a,..)  => (SawExprInlineAsm(a), false),
 339         ExprStruct(..)           => (SawExprStruct, false),
 340         ExprRepeat(..)           => (SawExprRepeat, false),
 341     }
 342 }
 343
 344 #[derive(Hash)]
 345 enum SawItemComponent {
 346     SawItemExternCrate,
 347     SawItemUse,
 348     SawItemStatic(Mutability),
 349     SawItemConst,
 350     SawItemFn(Unsafety, Constness, Abi),
 351     SawItemMod,
 352     SawItemForeignMod,
 353     SawItemTy,
 354     SawItemEnum,
 355     SawItemStruct,
 356     SawItemUnion,
 357     SawItemTrait(Unsafety),
 358     SawItemDefaultImpl(Unsafety),
 359     SawItemImpl(Unsafety, ImplPolarity)
 360 }
 361
 362 fn saw_item(node: &Item_) -> SawItemComponent {
 363     match *node {
 364         ItemExternCrate(..) => SawItemExternCrate,
 365         ItemUse(..) => SawItemUse,
 366         ItemStatic(_, mutability, _) => SawItemStatic(mutability),
 367         ItemConst(..) =>SawItemConst,
 368         ItemFn(_, unsafety, constness, abi, _, _) => SawItemFn(unsafety, constness, abi),
 369         ItemMod(..) => SawItemMod,
 370         ItemForeignMod(..) => SawItemForeignMod,
 371         ItemTy(..) => SawItemTy,
 372         ItemEnum(..) => SawItemEnum,
 373         ItemStruct(..) => SawItemStruct,
 374         ItemUnion(..) => SawItemUnion,
 375         ItemTrait(unsafety, ..) => SawItemTrait(unsafety),
 376         ItemDefaultImpl(unsafety, _) => SawItemDefaultImpl(unsafety),
 377         ItemImpl(unsafety, implpolarity, ..) => SawItemImpl(unsafety, implpolarity)
 378     }
 379 }
 380
 381 #[derive(Hash)]
 382 enum SawPatComponent {
 383     SawPatWild,
 384     SawPatBinding(BindingMode),
 385     SawPatStruct,
 386     SawPatTupleStruct,
 387     SawPatPath,
 388     SawPatTuple,
 389     SawPatBox,
 390     SawPatRef(Mutability),
 391     SawPatLit,
 392     SawPatRange,
 393     SawPatSlice
 394 }
 395
 396 fn saw_pat(node: &PatKind) -> SawPatComponent {
 397     match *node {
 398         PatKind::Wild => SawPatWild,
 399         PatKind::Binding(bindingmode, ..) => SawPatBinding(bindingmode),
 400         PatKind::Struct(..) => SawPatStruct,
 401         PatKind::TupleStruct(..) => SawPatTupleStruct,
 402         PatKind::Path(..) => SawPatPath,
 403         PatKind::Tuple(..) => SawPatTuple,
 404         PatKind::Box(..) => SawPatBox,
 405         PatKind::Ref(_, mutability) => SawPatRef(mutability),
 406         PatKind::Lit(..) => SawPatLit,
 407         PatKind::Range(..) => SawPatRange,
 408         PatKind::Slice(..) => SawPatSlice
 409     }
 410 }
 411
 412 #[derive(Hash)]
 413 enum SawTyComponent {
 414     SawTySlice,
 415     SawTyArray,
 416     SawTyPtr(Mutability),
 417     SawTyRptr(Mutability),
 418     SawTyBareFn(Unsafety, Abi),
 419     SawTyNever,
 420     SawTyTup,
 421     SawTyPath,
 422     SawTyObjectSum,
 423     SawTyPolyTraitRef,
 424     SawTyImplTrait,
 425     SawTyTypeof,
 426     SawTyInfer
 427 }
 428
 429 fn saw_ty(node: &Ty_) -> SawTyComponent {
 430     match *node {
 431       TySlice(..) => SawTySlice,
 432       TyArray(..) => SawTyArray,
 433       TyPtr(ref mty) => SawTyPtr(mty.mutbl),
 434       TyRptr(_, ref mty) => SawTyRptr(mty.mutbl),
 435       TyBareFn(ref barefnty) => SawTyBareFn(barefnty.unsafety, barefnty.abi),
 436       TyNever => SawTyNever,
 437       TyTup(..) => SawTyTup,
 438       TyPath(..) => SawTyPath,
 439       TyObjectSum(..) => SawTyObjectSum,
 440       TyPolyTraitRef(..) => SawTyPolyTraitRef,
 441       TyImplTrait(..) => SawTyImplTrait,
 442       TyTypeof(..) => SawTyTypeof,
 443       TyInfer => SawTyInfer
 444     }
 445 }
 446
 447 #[derive(Hash)]
 448 enum SawTraitOrImplItemComponent {
 449     SawTraitOrImplItemConst,
 450     SawTraitOrImplItemMethod(Unsafety, Constness, Abi),
 451     SawTraitOrImplItemType
 452 }
 453
 454 fn saw_trait_item(ti: &TraitItem_) -> SawTraitOrImplItemComponent {
 455     match *ti {
 456         ConstTraitItem(..) => SawTraitOrImplItemConst,
 457         MethodTraitItem(ref sig, _) =>
 458             SawTraitOrImplItemMethod(sig.unsafety, sig.constness, sig.abi),
 459         TypeTraitItem(..) => SawTraitOrImplItemType
 460     }
 461 }
 462
 463 fn saw_impl_item(ii: &ImplItemKind) -> SawTraitOrImplItemComponent {
 464     match *ii {
 465         ImplItemKind::Const(..) => SawTraitOrImplItemConst,
 466         ImplItemKind::Method(ref sig, _) =>
 467             SawTraitOrImplItemMethod(sig.unsafety, sig.constness, sig.abi),
 468         ImplItemKind::Type(..) => SawTraitOrImplItemType
 469     }
 470 }
 471
 472 #[derive(Clone, Copy, Hash, Eq, PartialEq)]
 473 enum SawSpanExpnKind {
 474     NoExpansion,
 475     CommandLine,
 476     SomeExpansion,
 477 }
 478
 479 macro_rules! hash_attrs {
 480     ($visitor:expr, $attrs:expr) => ({
 481         let attrs = $attrs;
 482         if attrs.len() > 0 {
 483             $visitor.hash_attributes(attrs);
 484         }
 485     })
 486 }
 487
 488 macro_rules! hash_span {
 489     ($visitor:expr, $span:expr) => ({
 490         hash_span!($visitor, $span, false)
 491     });
 492     ($visitor:expr, $span:expr, $force:expr) => ({
 493         if $force || $visitor.hash_spans {
 494             $visitor.hash_span($span);
 495         }
 496     });
 497 }
 498
 499 impl<'a, 'hash, 'tcx> visit::Visitor<'tcx> for StrictVersionHashVisitor<'a, 'hash, 'tcx> {
 500     fn visit_variant_data(&mut self,
 501                           s: &'tcx VariantData,
 502                           name: Name,
 503                           _: &'tcx Generics,
 504                           _: NodeId,
 505                           span: Span) {
 506         debug!("visit_variant_data: st={:?}", self.st);
 507         SawStructDef(name.as_str()).hash(self.st);
 508         hash_span!(self, span);
 509         visit::walk_struct_def(self, s);
 510     }
 511
 512     fn visit_variant(&mut self,
 513                      v: &'tcx Variant,
 514                      g: &'tcx Generics,
 515                      item_id: NodeId) {
 516         debug!("visit_variant: st={:?}", self.st);
 517         SawVariant.hash(self.st);
 518         hash_attrs!(self, &v.node.attrs);
 519         visit::walk_variant(self, v, g, item_id)
 520     }
 521
 522     fn visit_name(&mut self, span: Span, name: Name) {
 523         debug!("visit_name: st={:?}", self.st);
 524         SawIdent(name.as_str()).hash(self.st);
 525         hash_span!(self, span);
 526     }
 527
 528     fn visit_lifetime(&mut self, l: &'tcx Lifetime) {
 529         debug!("visit_lifetime: st={:?}", self.st);
 530         SawLifetime.hash(self.st);
 531         visit::walk_lifetime(self, l);
 532     }
 533
 534     fn visit_lifetime_def(&mut self, l: &'tcx LifetimeDef) {
 535         debug!("visit_lifetime_def: st={:?}", self.st);
 536         SawLifetimeDef(l.bounds.len()).hash(self.st);
 537         visit::walk_lifetime_def(self, l);
 538     }
 539
 540     fn visit_expr(&mut self, ex: &'tcx Expr) {
 541         debug!("visit_expr: st={:?}", self.st);
 542         let (saw_expr, force_span) = saw_expr(&ex.node,
 543                                               self.overflow_checks_enabled);
 544         SawExpr(saw_expr).hash(self.st);
 545         // No need to explicitly hash the discriminant here, since we are
 546         // implicitly hashing the discriminant of SawExprComponent.
 547         hash_span!(self, ex.span, force_span);
 548         hash_attrs!(self, &ex.attrs);
 549         visit::walk_expr(self, ex)
 550     }
 551
 552     fn visit_stmt(&mut self, s: &'tcx Stmt) {
 553         debug!("visit_stmt: st={:?}", self.st);
 554
 555         // We don't want to modify the hash for decls, because
 556         // they might be item decls (if they are local decls,
 557         // we'll hash that fact in visit_local); but we do want to
 558         // remember if this was a StmtExpr or StmtSemi (the later
 559         // had an explicit semi-colon; this affects the typing
 560         // rules).
 561         match s.node {
 562             StmtDecl(..) => (),
 563             StmtExpr(..) => {
 564                 SawStmt.hash(self.st);
 565                 self.hash_discriminant(&s.node);
 566                 hash_span!(self, s.span);
 567             }
 568             StmtSemi(..) => {
 569                 SawStmt.hash(self.st);
 570                 self.hash_discriminant(&s.node);
 571                 hash_span!(self, s.span);
 572             }
 573         }
 574
 575         visit::walk_stmt(self, s)
 576     }
 577
 578     fn visit_foreign_item(&mut self, i: &'tcx ForeignItem) {
 579         debug!("visit_foreign_item: st={:?}", self.st);
 580
 581         SawForeignItem.hash(self.st);
 582         hash_span!(self, i.span);
 583         hash_attrs!(self, &i.attrs);
 584         visit::walk_foreign_item(self, i)
 585     }
 586
 587     fn visit_item(&mut self, i: &'tcx Item) {
 588         debug!("visit_item: {:?} st={:?}", i, self.st);
 589
 590         self.maybe_enable_overflow_checks(&i.attrs);
 591
 592         SawItem(saw_item(&i.node)).hash(self.st);
 593         hash_span!(self, i.span);
 594         hash_attrs!(self, &i.attrs);
 595         visit::walk_item(self, i)
 596     }
 597
 598     fn visit_mod(&mut self, m: &'tcx Mod, _s: Span, n: NodeId) {
 599         debug!("visit_mod: st={:?}", self.st);
 600         SawMod.hash(self.st); visit::walk_mod(self, m, n)
 601     }
 602
 603     fn visit_ty(&mut self, t: &'tcx Ty) {
 604         debug!("visit_ty: st={:?}", self.st);
 605         SawTy(saw_ty(&t.node)).hash(self.st);
 606         hash_span!(self, t.span);
 607         visit::walk_ty(self, t)
 608     }
 609
 610     fn visit_generics(&mut self, g: &'tcx Generics) {
 611         debug!("visit_generics: st={:?}", self.st);
 612         SawGenerics.hash(self.st);
 613         visit::walk_generics(self, g)
 614     }
 615
 616     fn visit_trait_item(&mut self, ti: &'tcx TraitItem) {
 617         debug!("visit_trait_item: st={:?}", self.st);
 618
 619         self.maybe_enable_overflow_checks(&ti.attrs);
 620
 621         SawTraitItem(saw_trait_item(&ti.node)).hash(self.st);
 622         hash_span!(self, ti.span);
 623         hash_attrs!(self, &ti.attrs);
 624         visit::walk_trait_item(self, ti)
 625     }
 626
 627     fn visit_impl_item(&mut self, ii: &'tcx ImplItem) {
 628         debug!("visit_impl_item: st={:?}", self.st);
 629
 630         self.maybe_enable_overflow_checks(&ii.attrs);
 631
 632         SawImplItem(saw_impl_item(&ii.node)).hash(self.st);
 633         hash_span!(self, ii.span);
 634         hash_attrs!(self, &ii.attrs);
 635         visit::walk_impl_item(self, ii)
 636     }
 637
 638     fn visit_struct_field(&mut self, s: &'tcx StructField) {
 639         debug!("visit_struct_field: st={:?}", self.st);
 640         SawStructField.hash(self.st);
 641         hash_span!(self, s.span);
 642         hash_attrs!(self, &s.attrs);
 643         visit::walk_struct_field(self, s)
 644     }
 645
 646     fn visit_path(&mut self, path: &'tcx Path, _: ast::NodeId) {
 647         debug!("visit_path: st={:?}", self.st);
 648         SawPath(path.global).hash(self.st);
 649         hash_span!(self, path.span);
 650         visit::walk_path(self, path)
 651     }
 652
 653     fn visit_block(&mut self, b: &'tcx Block) {
 654         debug!("visit_block: st={:?}", self.st);
 655         SawBlock.hash(self.st);
 656         hash_span!(self, b.span);
 657         visit::walk_block(self, b)
 658     }
 659
 660     fn visit_pat(&mut self, p: &'tcx Pat) {
 661         debug!("visit_pat: st={:?}", self.st);
 662         SawPat(saw_pat(&p.node)).hash(self.st);
 663         hash_span!(self, p.span);
 664         visit::walk_pat(self, p)
 665     }
 666
 667     fn visit_local(&mut self, l: &'tcx Local) {
 668         debug!("visit_local: st={:?}", self.st);
 669         SawLocal.hash(self.st);
 670         hash_attrs!(self, &l.attrs);
 671         visit::walk_local(self, l)
 672         // No need to hash span, we are hashing all component spans
 673     }
 674
 675     fn visit_arm(&mut self, a: &'tcx Arm) {
 676         debug!("visit_arm: st={:?}", self.st);
 677         SawArm.hash(self.st);
 678         hash_attrs!(self, &a.attrs);
 679         visit::walk_arm(self, a)
 680     }
 681
 682     fn visit_id(&mut self, id: NodeId) {
 683         debug!("visit_id: id={} st={:?}", id, self.st);
 684         self.hash_resolve(id)
 685     }
 686
 687     fn visit_vis(&mut self, v: &'tcx Visibility) {
 688         debug!("visit_vis: st={:?}", self.st);
 689         SawVis.hash(self.st);
 690         self.hash_discriminant(v);
 691         visit::walk_vis(self, v)
 692     }
 693
 694     fn visit_associated_item_kind(&mut self, kind: &'tcx AssociatedItemKind) {
 695         debug!("visit_associated_item_kind: st={:?}", self.st);
 696         SawAssociatedItemKind(*kind).hash(self.st);
 697         visit::walk_associated_item_kind(self, kind);
 698     }
 699
 700     fn visit_defaultness(&mut self, defaultness: &'tcx Defaultness) {
 701         debug!("visit_associated_item_kind: st={:?}", self.st);
 702         SawDefaultness(*defaultness).hash(self.st);
 703         visit::walk_defaultness(self, defaultness);
 704     }
 705
 706     fn visit_where_predicate(&mut self, predicate: &'tcx WherePredicate) {
 707         debug!("visit_where_predicate: st={:?}", self.st);
 708         SawWherePredicate.hash(self.st);
 709         self.hash_discriminant(predicate);
 710         // Ignoring span. Any important nested components should be visited.
 711         visit::walk_where_predicate(self, predicate)
 712     }
 713
 714     fn visit_ty_param_bound(&mut self, bounds: &'tcx TyParamBound) {
 715         debug!("visit_ty_param_bound: st={:?}", self.st);
 716         SawTyParamBound.hash(self.st);
 717         self.hash_discriminant(bounds);
 718         // The TraitBoundModifier in TraitTyParamBound will be hash in
 719         // visit_poly_trait_ref()
 720         visit::walk_ty_param_bound(self, bounds)
 721     }
 722
 723     fn visit_poly_trait_ref(&mut self, t: &'tcx PolyTraitRef, m: &'tcx TraitBoundModifier) {
 724         debug!("visit_poly_trait_ref: st={:?}", self.st);
 725         SawPolyTraitRef.hash(self.st);
 726         m.hash(self.st);
 727         visit::walk_poly_trait_ref(self, t, m)
 728     }
 729
 730     fn visit_path_list_item(&mut self, prefix: &'tcx Path, item: &'tcx PathListItem) {
 731         debug!("visit_path_list_item: st={:?}", self.st);
 732         SawPathListItem.hash(self.st);
 733         self.hash_discriminant(&item.node);
 734         hash_span!(self, item.span);
 735         visit::walk_path_list_item(self, prefix, item)
 736     }
 737
 738     fn visit_path_segment(&mut self, path_span: Span, path_segment: &'tcx PathSegment) {
 739         debug!("visit_path_segment: st={:?}", self.st);
 740         SawPathSegment.hash(self.st);
 741         visit::walk_path_segment(self, path_span, path_segment)
 742     }
 743
 744     fn visit_path_parameters(&mut self, path_span: Span, path_parameters: &'tcx PathParameters) {
 745         debug!("visit_path_parameters: st={:?}", self.st);
 746         SawPathParameters.hash(self.st);
 747         self.hash_discriminant(path_parameters);
 748         visit::walk_path_parameters(self, path_span, path_parameters)
 749     }
 750
 751     fn visit_assoc_type_binding(&mut self, type_binding: &'tcx TypeBinding) {
 752         debug!("visit_assoc_type_binding: st={:?}", self.st);
 753         SawAssocTypeBinding.hash(self.st);
 754         hash_span!(self, type_binding.span);
 755         visit::walk_assoc_type_binding(self, type_binding)
 756     }
 757
 758     fn visit_attribute(&mut self, _: &ast::Attribute) {
 759         // We explicitly do not use this method, since doing that would
 760         // implicitly impose an order on the attributes being hashed, while we
 761         // explicitly don't want their order to matter
 762     }
 763
 764     fn visit_macro_def(&mut self, macro_def: &'tcx MacroDef) {
 765         debug!("visit_macro_def: st={:?}", self.st);
 766         SawMacroDef.hash(self.st);
 767         hash_attrs!(self, &macro_def.attrs);
 768         for tt in &macro_def.body {
 769             self.hash_token_tree(tt);
 770         }
 771         visit::walk_macro_def(self, macro_def)
 772     }
 773 }
 774
 775 #[derive(Hash)]
 776 pub enum DefHash {
 777     SawDefId,
 778     SawLabel,
 779     SawPrimTy,
 780     SawSelfTy,
 781     SawErr,
 782 }
 783
 784 impl<'a, 'hash, 'tcx> StrictVersionHashVisitor<'a, 'hash, 'tcx> {
 785     fn hash_resolve(&mut self, id: ast::NodeId) {
 786         // Because whether or not a given id has an entry is dependent
 787         // solely on expr variant etc, we don't need to hash whether
 788         // or not an entry was present (we are already hashing what
 789         // variant it is above when we visit the HIR).
 790
 791         if let Some(def) = self.tcx.def_map.borrow().get(&id) {
 792             debug!("hash_resolve: id={:?} def={:?} st={:?}", id, def, self.st);
 793             self.hash_partial_def(def);
 794         }
 795
 796         if let Some(traits) = self.tcx.trait_map.get(&id) {
 797             debug!("hash_resolve: id={:?} traits={:?} st={:?}", id, traits, self.st);
 798             traits.len().hash(self.st);
 799
 800             // The ordering of the candidates is not fixed. So we hash
 801             // the def-ids and then sort them and hash the collection.
 802             let mut candidates: Vec<_> =
 803                 traits.iter()
 804                       .map(|&TraitCandidate { def_id, import_id: _ }| {
 805                           self.compute_def_id_hash(def_id)
 806                       })
 807                       .collect();
 808             candidates.sort();
 809             candidates.hash(self.st);
 810         }
 811     }
 812
 813     fn hash_def_id(&mut self, def_id: DefId) {
 814         self.compute_def_id_hash(def_id).hash(self.st);
 815     }
 816
 817     fn hash_partial_def(&mut self, def: &PathResolution) {
 818         self.hash_def(def.base_def);
 819         def.depth.hash(self.st);
 820     }
 821
 822     fn hash_def(&mut self, def: Def) {
 823         match def {
 824             // Crucial point: for all of these variants, the variant +
 825             // add'l data that is added is always the same if the
 826             // def-id is the same, so it suffices to hash the def-id
 827             Def::Fn(..) |
 828             Def::Mod(..) |
 829             Def::Static(..) |
 830             Def::Variant(..) |
 831             Def::VariantCtor(..) |
 832             Def::Enum(..) |
 833             Def::TyAlias(..) |
 834             Def::AssociatedTy(..) |
 835             Def::TyParam(..) |
 836             Def::Struct(..) |
 837             Def::StructCtor(..) |
 838             Def::Union(..) |
 839             Def::Trait(..) |
 840             Def::Method(..) |
 841             Def::Const(..) |
 842             Def::AssociatedConst(..) |
 843             Def::Local(..) |
 844             Def::Upvar(..) |
 845             Def::Macro(..) => {
 846                 DefHash::SawDefId.hash(self.st);
 847                 self.hash_def_id(def.def_id());
 848             }
 849
 850             Def::Label(..) => {
 851                 DefHash::SawLabel.hash(self.st);
 852                 // we don't encode the `id` because it always refers to something
 853                 // within this item, so if it changed, there would have to be other
 854                 // changes too
 855             }
 856             Def::PrimTy(ref prim_ty) => {
 857                 DefHash::SawPrimTy.hash(self.st);
 858                 prim_ty.hash(self.st);
 859             }
 860             Def::SelfTy(..) => {
 861                 DefHash::SawSelfTy.hash(self.st);
 862                 // the meaning of Self is always the same within a
 863                 // given context, so we don't need to hash the other
 864                 // fields
 865             }
 866             Def::Err => {
 867                 DefHash::SawErr.hash(self.st);
 868             }
 869         }
 870     }
 871
 872     fn hash_meta_item(&mut self, meta_item: &ast::MetaItem) {
 873         debug!("hash_meta_item: st={:?}", self.st);
 874
 875         // ignoring span information, it doesn't matter here
 876         self.hash_discriminant(&meta_item.node);
 877         match meta_item.node {
 878             ast::MetaItemKind::Word(ref s) => {
 879                 s.len().hash(self.st);
 880                 s.hash(self.st);
 881             }
 882             ast::MetaItemKind::NameValue(ref s, ref lit) => {
 883                 s.len().hash(self.st);
 884                 s.hash(self.st);
 885                 lit.node.hash(self.st);
 886             }
 887             ast::MetaItemKind::List(ref s, ref items) => {
 888                 s.len().hash(self.st);
 889                 s.hash(self.st);
 890                 // Sort subitems so the hash does not depend on their order
 891                 let indices = self.indices_sorted_by(&items, |p| {
 892                     (p.name(), fnv::hash(&p.literal().map(|i| &i.node)))
 893                 });
 894                 items.len().hash(self.st);
 895                 for (index, &item_index) in indices.iter().enumerate() {
 896                     index.hash(self.st);
 897                     let nested_meta_item: &ast::NestedMetaItemKind = &items[item_index].node;
 898                     self.hash_discriminant(nested_meta_item);
 899                     match *nested_meta_item {
 900                         ast::NestedMetaItemKind::MetaItem(ref meta_item) => {
 901                             self.hash_meta_item(meta_item);
 902                         }
 903                         ast::NestedMetaItemKind::Literal(ref lit) => {
 904                             lit.node.hash(self.st);
 905                         }
 906                     }
 907                 }
 908             }
 909         }
 910     }
 911
 912     pub fn hash_attributes(&mut self, attributes: &[ast::Attribute]) {
 913         debug!("hash_attributes: st={:?}", self.st);
 914         let indices = self.indices_sorted_by(attributes, |attr| attr.name());
 915
 916         for i in indices {
 917             let attr = &attributes[i].node;
 918             if !attr.is_sugared_doc &&
 919                !IGNORED_ATTRIBUTES.contains(&&*attr.value.name()) {
 920                 SawAttribute(attr.style).hash(self.st);
 921                 self.hash_meta_item(&*attr.value);
 922             }
 923         }
 924     }
 925
 926     fn indices_sorted_by<T, K, F>(&mut self, items: &[T], get_key: F) -> Vec<usize>
 927         where K: Ord,
 928               F: Fn(&T) -> K
 929     {
 930         let mut indices = Vec::with_capacity(items.len());
 931         indices.extend(0 .. items.len());
 932         indices.sort_by_key(|index| get_key(&items[*index]));
 933         indices
 934     }
 935
 936     fn maybe_enable_overflow_checks(&mut self, item_attrs: &[ast::Attribute]) {
 937         if attr::contains_name(item_attrs, "rustc_inherit_overflow_checks") {
 938             self.overflow_checks_enabled = true;
 939         }
 940     }
 941
 942     fn hash_token_tree(&mut self, tt: &tokenstream::TokenTree) {
 943         self.hash_discriminant(tt);
 944         match *tt {
 945             tokenstream::TokenTree::Token(span, ref token) => {
 946                 hash_span!(self, span);
 947                 self.hash_token(token);
 948             }
 949             tokenstream::TokenTree::Delimited(span, ref delimited) => {
 950                 hash_span!(self, span);
 951                 let tokenstream::Delimited {
 952                     ref delim,
 953                     open_span,
 954                     ref tts,
 955                     close_span,
 956                 } = **delimited;
 957
 958                 delim.hash(self.st);
 959                 hash_span!(self, open_span);
 960                 tts.len().hash(self.st);
 961                 for sub_tt in tts {
 962                     self.hash_token_tree(sub_tt);
 963                 }
 964                 hash_span!(self, close_span);
 965             }
 966             tokenstream::TokenTree::Sequence(span, ref sequence_repetition) => {
 967                 hash_span!(self, span);
 968                 let tokenstream::SequenceRepetition {
 969                     ref tts,
 970                     ref separator,
 971                     op,
 972                     num_captures,
 973                 } = **sequence_repetition;
 974
 975                 tts.len().hash(self.st);
 976                 for sub_tt in tts {
 977                     self.hash_token_tree(sub_tt);
 978                 }
 979                 self.hash_discriminant(separator);
 980                 if let Some(ref separator) = *separator {
 981                     self.hash_token(separator);
 982                 }
 983                 op.hash(self.st);
 984                 num_captures.hash(self.st);
 985             }
 986         }
 987     }
 988
 989     fn hash_token(&mut self, token: &token::Token) {
 990         self.hash_discriminant(token);
 991         match *token {
 992             token::Token::Eq |
 993             token::Token::Lt |
 994             token::Token::Le |
 995             token::Token::EqEq |
 996             token::Token::Ne |
 997             token::Token::Ge |
 998             token::Token::Gt |
 999             token::Token::AndAnd |
1000             token::Token::OrOr |
1001             token::Token::Not |
1002             token::Token::Tilde |
1003             token::Token::At |
1004             token::Token::Dot |
1005             token::Token::DotDot |
1006             token::Token::DotDotDot |
1007             token::Token::Comma |
1008             token::Token::Semi |
1009             token::Token::Colon |
1010             token::Token::ModSep |
1011             token::Token::RArrow |
1012             token::Token::LArrow |
1013             token::Token::FatArrow |
1014             token::Token::Pound |
1015             token::Token::Dollar |
1016             token::Token::Question |
1017             token::Token::Underscore |
1018             token::Token::Whitespace |
1019             token::Token::Comment |
1020             token::Token::Eof => {}
1021
1022             token::Token::BinOp(bin_op_token) |
1023             token::Token::BinOpEq(bin_op_token) => bin_op_token.hash(self.st),
1024
1025             token::Token::OpenDelim(delim_token) |
1026             token::Token::CloseDelim(delim_token) => delim_token.hash(self.st),
1027
1028             token::Token::Literal(ref lit, ref opt_name) => {
1029                 self.hash_discriminant(lit);
1030                 match *lit {
1031                     token::Lit::Byte(val) |
1032                     token::Lit::Char(val) |
1033                     token::Lit::Integer(val) |
1034                     token::Lit::Float(val) |
1035                     token::Lit::Str_(val) |
1036                     token::Lit::ByteStr(val) => val.as_str().hash(self.st),
1037                     token::Lit::StrRaw(val, n) |
1038                     token::Lit::ByteStrRaw(val, n) => {
1039                         val.as_str().hash(self.st);
1040                         n.hash(self.st);
1041                     }
1042                 };
1043                 opt_name.map(ast::Name::as_str).hash(self.st);
1044             }
1045
1046             token::Token::Ident(ident) |
1047             token::Token::Lifetime(ident) |
1048             token::Token::SubstNt(ident) => ident.name.as_str().hash(self.st),
1049             token::Token::MatchNt(ident1, ident2) => {
1050                 ident1.name.as_str().hash(self.st);
1051                 ident2.name.as_str().hash(self.st);
1052             }
1053
1054             token::Token::Interpolated(ref non_terminal) => {
1055                 // FIXME(mw): This could be implemented properly. It's just a
1056                 //            lot of work, since we would need to hash the AST
1057                 //            in a stable way, in addition to the HIR.
1058                 //            Since this is hardly used anywhere, just emit a
1059                 //            warning for now.
1060                 if self.tcx.sess.opts.debugging_opts.incremental.is_some() {
1061                     let msg = format!("Quasi-quoting might make incremental \
1062                                        compilation very inefficient: {:?}",
1063                                       non_terminal);
1064                     self.tcx.sess.warn(&msg[..]);
1065                 }
1066
1067                 non_terminal.hash(self.st);
1068             }
1069
1070             token::Token::DocComment(val) |
1071             token::Token::Shebang(val) => val.as_str().hash(self.st),
1072         }
1073     }
1074 }