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