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