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