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