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 // FIXME (#14132): Even this SVH computation still has implementation
  12 // artifacts: namely, the order of item declaration will affect the
  13 // hash computation, but for many kinds of items the order of
  14 // declaration should be irrelevant to the ABI.
  15
  16 use self::SawExprComponent::*;
  17 use self::SawAbiComponent::*;
  18 use syntax::ast::{self, Name, NodeId};
  19 use syntax::parse::token;
  20 use syntax_pos::{Span, NO_EXPANSION, COMMAND_LINE_EXPN, BytePos};
  21 use rustc::hir;
  22 use rustc::hir::*;
  23 use rustc::hir::def::{Def, PathResolution};
  24 use rustc::hir::def_id::DefId;
  25 use rustc::hir::intravisit as visit;
  26 use rustc::ty::TyCtxt;
  27 use rustc_data_structures::fnv;
  28 use std::hash::{Hash, SipHasher};
  29
  30 use super::def_path_hash::DefPathHashes;
  31 use super::caching_codemap_view::CachingCodemapView;
  32
  33 const IGNORED_ATTRIBUTES: &'static [&'static str] = &[
  34     "cfg",
  35     ::ATTR_IF_THIS_CHANGED,
  36     ::ATTR_THEN_THIS_WOULD_NEED,
  37     ::ATTR_DIRTY,
  38     ::ATTR_CLEAN,
  39     ::ATTR_DIRTY_METADATA,
  40     ::ATTR_CLEAN_METADATA
  41 ];
  42
  43 pub struct StrictVersionHashVisitor<'a, 'hash: 'a, 'tcx: 'hash> {
  44     pub tcx: TyCtxt<'hash, 'tcx, 'tcx>,
  45     pub st: &'a mut SipHasher,
  46     // collect a deterministic hash of def-ids that we have seen
  47     def_path_hashes: &'a mut DefPathHashes<'hash, 'tcx>,
  48     hash_spans: bool,
  49     codemap: &'a mut CachingCodemapView<'tcx>,
  50 }
  51
  52 impl<'a, 'hash, 'tcx> StrictVersionHashVisitor<'a, 'hash, 'tcx> {
  53     pub fn new(st: &'a mut SipHasher,
  54                tcx: TyCtxt<'hash, 'tcx, 'tcx>,
  55                def_path_hashes: &'a mut DefPathHashes<'hash, 'tcx>,
  56                codemap: &'a mut CachingCodemapView<'tcx>,
  57                hash_spans: bool)
  58                -> Self {
  59         StrictVersionHashVisitor {
  60             st: st,
  61             tcx: tcx,
  62             def_path_hashes: def_path_hashes,
  63             hash_spans: hash_spans,
  64             codemap: codemap,
  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     fn hash_span(&mut self, span: Span) {
  80         debug_assert!(self.hash_spans);
  81         debug!("hash_span: st={:?}", self.st);
  82
  83         // If this is not an empty or invalid span, we want to hash the last
  84         // position that belongs to it, as opposed to hashing the first
  85         // position past it.
  86         let span_hi = if span.hi > span.lo {
  87             // We might end up in the middle of a multibyte character here,
  88             // but that's OK, since we are not trying to decode anything at
  89             // this position.
  90             span.hi - BytePos(1)
  91         } else {
  92             span.hi
  93         };
  94
  95         let loc1 = self.codemap.byte_pos_to_line_and_col(span.lo);
  96         let loc2 = self.codemap.byte_pos_to_line_and_col(span_hi);
  97
  98         let expansion_kind = match span.expn_id {
  99             NO_EXPANSION => SawSpanExpnKind::NoExpansion,
 100             COMMAND_LINE_EXPN => SawSpanExpnKind::CommandLine,
 101             _ => SawSpanExpnKind::SomeExpansion,
 102         };
 103
 104         SawSpan(loc1.as_ref().map(|&(ref fm, line, col)| (&fm.name[..], line, col)),
 105                 loc2.as_ref().map(|&(ref fm, line, col)| (&fm.name[..], line, col)),
 106                 expansion_kind)
 107             .hash(self.st);
 108
 109         if expansion_kind == SawSpanExpnKind::SomeExpansion {
 110             let call_site = self.codemap.codemap().source_callsite(span);
 111             self.hash_span(call_site);
 112         }
 113     }
 114
 115     fn hash_discriminant<T>(&mut self, v: &T) {
 116         unsafe {
 117             let disr = ::std::intrinsics::discriminant_value(v);
 118             debug!("hash_discriminant: disr={}, st={:?}", disr, self.st);
 119             disr.hash(self.st);
 120         }
 121     }
 122 }
 123
 124 // To off-load the bulk of the hash-computation on #[derive(Hash)],
 125 // we define a set of enums corresponding to the content that our
 126 // crate visitor will encounter as it traverses the ast.
 127 //
 128 // The important invariant is that all of the Saw*Component enums
 129 // do not carry any Spans, Names, or Idents.
 130 //
 131 // Not carrying any Names/Idents is the important fix for problem
 132 // noted on PR #13948: using the ident.name as the basis for a
 133 // hash leads to unstable SVH, because ident.name is just an index
 134 // into intern table (i.e. essentially a random address), not
 135 // computed from the name content.
 136 //
 137 // With the below enums, the SVH computation is not sensitive to
 138 // artifacts of how rustc was invoked nor of how the source code
 139 // was laid out.  (Or at least it is *less* sensitive.)
 140
 141 // This enum represents the different potential bits of code the
 142 // visitor could encounter that could affect the ABI for the crate,
 143 // and assigns each a distinct tag to feed into the hash computation.
 144 #[derive(Hash)]
 145 enum SawAbiComponent<'a> {
 146
 147     // FIXME (#14132): should we include (some function of)
 148     // ident.ctxt as well?
 149     SawIdent(token::InternedString),
 150     SawStructDef(token::InternedString),
 151
 152     SawLifetime,
 153     SawLifetimeDef(usize),
 154
 155     SawMod,
 156     SawForeignItem,
 157     SawItem,
 158     SawTy,
 159     SawGenerics,
 160     SawTraitItem,
 161     SawImplItem,
 162     SawStructField,
 163     SawVariant,
 164     SawPath(bool),
 165     SawPathSegment,
 166     SawPathParameters,
 167     SawPathListItem,
 168     SawBlock,
 169     SawPat,
 170     SawLocal,
 171     SawArm,
 172     SawExpr(SawExprComponent<'a>),
 173     SawStmt,
 174     SawVis,
 175     SawWherePredicate,
 176     SawTyParamBound,
 177     SawPolyTraitRef,
 178     SawAssocTypeBinding,
 179     SawAttribute(ast::AttrStyle),
 180     SawMacroDef,
 181     SawSpan(Option<(&'a str, usize, BytePos)>,
 182             Option<(&'a str, usize, BytePos)>,
 183             SawSpanExpnKind),
 184 }
 185
 186 /// SawExprComponent carries all of the information that we want
 187 /// to include in the hash that *won't* be covered by the
 188 /// subsequent recursive traversal of the expression's
 189 /// substructure by the visitor.
 190 ///
 191 /// We know every Expr_ variant is covered by a variant because
 192 /// `fn saw_expr` maps each to some case below.  Ensuring that
 193 /// each variant carries an appropriate payload has to be verified
 194 /// by hand.
 195 ///
 196 /// (However, getting that *exactly* right is not so important
 197 /// because the SVH is just a developer convenience; there is no
 198 /// guarantee of collision-freedom, hash collisions are just
 199 /// (hopefully) unlikely.)
 200 #[derive(Hash)]
 201 enum SawExprComponent<'a> {
 202
 203     SawExprLoop(Option<token::InternedString>),
 204     SawExprField(token::InternedString),
 205     SawExprTupField(usize),
 206     SawExprBreak(Option<token::InternedString>),
 207     SawExprAgain(Option<token::InternedString>),
 208
 209     SawExprBox,
 210     SawExprVec,
 211     SawExprCall,
 212     SawExprMethodCall,
 213     SawExprTup,
 214     SawExprBinary(hir::BinOp_),
 215     SawExprUnary(hir::UnOp),
 216     SawExprLit(ast::LitKind),
 217     SawExprCast,
 218     SawExprType,
 219     SawExprIf,
 220     SawExprWhile,
 221     SawExprMatch,
 222     SawExprClosure(CaptureClause),
 223     SawExprBlock,
 224     SawExprAssign,
 225     SawExprAssignOp(hir::BinOp_),
 226     SawExprIndex,
 227     SawExprPath(Option<usize>),
 228     SawExprAddrOf(hir::Mutability),
 229     SawExprRet,
 230     SawExprInlineAsm(&'a hir::InlineAsm),
 231     SawExprStruct,
 232     SawExprRepeat,
 233 }
 234
 235 fn saw_expr<'a>(node: &'a Expr_) -> SawExprComponent<'a> {
 236     match *node {
 237         ExprBox(..)              => SawExprBox,
 238         ExprVec(..)              => SawExprVec,
 239         ExprCall(..)             => SawExprCall,
 240         ExprMethodCall(..)       => SawExprMethodCall,
 241         ExprTup(..)              => SawExprTup,
 242         ExprBinary(op, ..)       => SawExprBinary(op.node),
 243         ExprUnary(op, _)         => SawExprUnary(op),
 244         ExprLit(ref lit)         => SawExprLit(lit.node.clone()),
 245         ExprCast(..)             => SawExprCast,
 246         ExprType(..)             => SawExprType,
 247         ExprIf(..)               => SawExprIf,
 248         ExprWhile(..)            => SawExprWhile,
 249         ExprLoop(_, id)          => SawExprLoop(id.map(|id| id.node.as_str())),
 250         ExprMatch(..)            => SawExprMatch,
 251         ExprClosure(cc, _, _, _) => SawExprClosure(cc),
 252         ExprBlock(..)            => SawExprBlock,
 253         ExprAssign(..)           => SawExprAssign,
 254         ExprAssignOp(op, ..)     => SawExprAssignOp(op.node),
 255         ExprField(_, name)       => SawExprField(name.node.as_str()),
 256         ExprTupField(_, id)      => SawExprTupField(id.node),
 257         ExprIndex(..)            => SawExprIndex,
 258         ExprPath(ref qself, _)   => SawExprPath(qself.as_ref().map(|q| q.position)),
 259         ExprAddrOf(m, _)         => SawExprAddrOf(m),
 260         ExprBreak(id)            => SawExprBreak(id.map(|id| id.node.as_str())),
 261         ExprAgain(id)            => SawExprAgain(id.map(|id| id.node.as_str())),
 262         ExprRet(..)              => SawExprRet,
 263         ExprInlineAsm(ref a,..)  => SawExprInlineAsm(a),
 264         ExprStruct(..)           => SawExprStruct,
 265         ExprRepeat(..)           => SawExprRepeat,
 266     }
 267 }
 268
 269 #[derive(Clone, Copy, Hash, Eq, PartialEq)]
 270 enum SawSpanExpnKind {
 271     NoExpansion,
 272     CommandLine,
 273     SomeExpansion,
 274 }
 275
 276 macro_rules! hash_attrs {
 277     ($visitor:expr, $attrs:expr) => ({
 278         let attrs = $attrs;
 279         if attrs.len() > 0 {
 280             $visitor.hash_attributes(attrs);
 281         }
 282     })
 283 }
 284
 285 macro_rules! hash_span {
 286     ($visitor:expr, $span:expr) => ({
 287         if $visitor.hash_spans {
 288             $visitor.hash_span($span);
 289         }
 290     })
 291 }
 292
 293 impl<'a, 'hash, 'tcx> visit::Visitor<'tcx> for StrictVersionHashVisitor<'a, 'hash, 'tcx> {
 294     fn visit_nested_item(&mut self, _: ItemId) {
 295         // Each item is hashed independently; ignore nested items.
 296     }
 297
 298     fn visit_variant_data(&mut self,
 299                           s: &'tcx VariantData,
 300                           name: Name,
 301                           _: &'tcx Generics,
 302                           _: NodeId,
 303                           span: Span) {
 304         debug!("visit_variant_data: st={:?}", self.st);
 305         SawStructDef(name.as_str()).hash(self.st);
 306         hash_span!(self, span);
 307         visit::walk_struct_def(self, s);
 308     }
 309
 310     fn visit_variant(&mut self,
 311                      v: &'tcx Variant,
 312                      g: &'tcx Generics,
 313                      item_id: NodeId) {
 314         debug!("visit_variant: st={:?}", self.st);
 315         SawVariant.hash(self.st);
 316         hash_attrs!(self, &v.node.attrs);
 317         visit::walk_variant(self, v, g, item_id)
 318     }
 319
 320     fn visit_name(&mut self, span: Span, name: Name) {
 321         debug!("visit_name: st={:?}", self.st);
 322         SawIdent(name.as_str()).hash(self.st);
 323         hash_span!(self, span);
 324     }
 325
 326     fn visit_lifetime(&mut self, l: &'tcx Lifetime) {
 327         debug!("visit_lifetime: st={:?}", self.st);
 328         SawLifetime.hash(self.st);
 329         visit::walk_lifetime(self, l);
 330     }
 331
 332     fn visit_lifetime_def(&mut self, l: &'tcx LifetimeDef) {
 333         debug!("visit_lifetime_def: st={:?}", self.st);
 334         SawLifetimeDef(l.bounds.len()).hash(self.st);
 335         visit::walk_lifetime_def(self, l);
 336     }
 337
 338     fn visit_expr(&mut self, ex: &'tcx Expr) {
 339         debug!("visit_expr: st={:?}", self.st);
 340         SawExpr(saw_expr(&ex.node)).hash(self.st);
 341         // No need to explicitly hash the discriminant here, since we are
 342         // implicitly hashing the discriminant of SawExprComponent.
 343         hash_span!(self, ex.span);
 344         hash_attrs!(self, &ex.attrs);
 345         visit::walk_expr(self, ex)
 346     }
 347
 348     fn visit_stmt(&mut self, s: &'tcx Stmt) {
 349         debug!("visit_stmt: st={:?}", self.st);
 350
 351         // We don't want to modify the hash for decls, because
 352         // they might be item decls (if they are local decls,
 353         // we'll hash that fact in visit_local); but we do want to
 354         // remember if this was a StmtExpr or StmtSemi (the later
 355         // had an explicit semi-colon; this affects the typing
 356         // rules).
 357         match s.node {
 358             StmtDecl(..) => (),
 359             StmtExpr(..) => {
 360                 SawStmt.hash(self.st);
 361                 self.hash_discriminant(&s.node);
 362                 hash_span!(self, s.span);
 363             }
 364             StmtSemi(..) => {
 365                 SawStmt.hash(self.st);
 366                 self.hash_discriminant(&s.node);
 367                 hash_span!(self, s.span);
 368             }
 369         }
 370
 371         visit::walk_stmt(self, s)
 372     }
 373
 374     fn visit_foreign_item(&mut self, i: &'tcx ForeignItem) {
 375         debug!("visit_foreign_item: st={:?}", self.st);
 376
 377         SawForeignItem.hash(self.st);
 378         hash_span!(self, i.span);
 379         hash_attrs!(self, &i.attrs);
 380         visit::walk_foreign_item(self, i)
 381     }
 382
 383     fn visit_item(&mut self, i: &'tcx Item) {
 384         debug!("visit_item: {:?} st={:?}", i, self.st);
 385
 386         SawItem.hash(self.st);
 387         // Hash the value of the discriminant of the Item variant.
 388         self.hash_discriminant(&i.node);
 389         hash_span!(self, i.span);
 390         hash_attrs!(self, &i.attrs);
 391         visit::walk_item(self, i)
 392     }
 393
 394     fn visit_mod(&mut self, m: &'tcx Mod, _s: Span, n: NodeId) {
 395         debug!("visit_mod: st={:?}", self.st);
 396         SawMod.hash(self.st); visit::walk_mod(self, m, n)
 397     }
 398
 399     fn visit_ty(&mut self, t: &'tcx Ty) {
 400         debug!("visit_ty: st={:?}", self.st);
 401         SawTy.hash(self.st);
 402         hash_span!(self, t.span);
 403         visit::walk_ty(self, t)
 404     }
 405
 406     fn visit_generics(&mut self, g: &'tcx Generics) {
 407         debug!("visit_generics: st={:?}", self.st);
 408         SawGenerics.hash(self.st);
 409         visit::walk_generics(self, g)
 410     }
 411
 412     fn visit_trait_item(&mut self, ti: &'tcx TraitItem) {
 413         debug!("visit_trait_item: st={:?}", self.st);
 414         SawTraitItem.hash(self.st);
 415         self.hash_discriminant(&ti.node);
 416         hash_span!(self, ti.span);
 417         hash_attrs!(self, &ti.attrs);
 418         visit::walk_trait_item(self, ti)
 419     }
 420
 421     fn visit_impl_item(&mut self, ii: &'tcx ImplItem) {
 422         debug!("visit_impl_item: st={:?}", self.st);
 423         SawImplItem.hash(self.st);
 424         self.hash_discriminant(&ii.node);
 425         hash_span!(self, ii.span);
 426         hash_attrs!(self, &ii.attrs);
 427         visit::walk_impl_item(self, ii)
 428     }
 429
 430     fn visit_struct_field(&mut self, s: &'tcx StructField) {
 431         debug!("visit_struct_field: st={:?}", self.st);
 432         SawStructField.hash(self.st);
 433         hash_span!(self, s.span);
 434         hash_attrs!(self, &s.attrs);
 435         visit::walk_struct_field(self, s)
 436     }
 437
 438     fn visit_path(&mut self, path: &'tcx Path, _: ast::NodeId) {
 439         debug!("visit_path: st={:?}", self.st);
 440         SawPath(path.global).hash(self.st);
 441         hash_span!(self, path.span);
 442         visit::walk_path(self, path)
 443     }
 444
 445     fn visit_block(&mut self, b: &'tcx Block) {
 446         debug!("visit_block: st={:?}", self.st);
 447         SawBlock.hash(self.st);
 448         hash_span!(self, b.span);
 449         visit::walk_block(self, b)
 450     }
 451
 452     fn visit_pat(&mut self, p: &'tcx Pat) {
 453         debug!("visit_pat: st={:?}", self.st);
 454         SawPat.hash(self.st);
 455         self.hash_discriminant(&p.node);
 456         hash_span!(self, p.span);
 457         visit::walk_pat(self, p)
 458     }
 459
 460     fn visit_local(&mut self, l: &'tcx Local) {
 461         debug!("visit_local: st={:?}", self.st);
 462         SawLocal.hash(self.st);
 463         hash_attrs!(self, &l.attrs);
 464         visit::walk_local(self, l)
 465         // No need to hash span, we are hashing all component spans
 466     }
 467
 468     fn visit_arm(&mut self, a: &'tcx Arm) {
 469         debug!("visit_arm: st={:?}", self.st);
 470         SawArm.hash(self.st);
 471         hash_attrs!(self, &a.attrs);
 472         visit::walk_arm(self, a)
 473     }
 474
 475     fn visit_id(&mut self, id: NodeId) {
 476         debug!("visit_id: id={} st={:?}", id, self.st);
 477         self.hash_resolve(id)
 478     }
 479
 480     fn visit_vis(&mut self, v: &'tcx Visibility) {
 481         debug!("visit_vis: st={:?}", self.st);
 482         SawVis.hash(self.st);
 483         self.hash_discriminant(v);
 484         visit::walk_vis(self, v)
 485     }
 486
 487     fn visit_where_predicate(&mut self, predicate: &'tcx WherePredicate) {
 488         debug!("visit_where_predicate: st={:?}", self.st);
 489         SawWherePredicate.hash(self.st);
 490         self.hash_discriminant(predicate);
 491         // Ignoring span. Any important nested components should be visited.
 492         visit::walk_where_predicate(self, predicate)
 493     }
 494
 495     fn visit_ty_param_bound(&mut self, bounds: &'tcx TyParamBound) {
 496         debug!("visit_ty_param_bound: st={:?}", self.st);
 497         SawTyParamBound.hash(self.st);
 498         self.hash_discriminant(bounds);
 499         // The TraitBoundModifier in TraitTyParamBound will be hash in
 500         // visit_poly_trait_ref()
 501         visit::walk_ty_param_bound(self, bounds)
 502     }
 503
 504     fn visit_poly_trait_ref(&mut self, t: &'tcx PolyTraitRef, m: &'tcx TraitBoundModifier) {
 505         debug!("visit_poly_trait_ref: st={:?}", self.st);
 506         SawPolyTraitRef.hash(self.st);
 507         m.hash(self.st);
 508         visit::walk_poly_trait_ref(self, t, m)
 509     }
 510
 511     fn visit_path_list_item(&mut self, prefix: &'tcx Path, item: &'tcx PathListItem) {
 512         debug!("visit_path_list_item: st={:?}", self.st);
 513         SawPathListItem.hash(self.st);
 514         self.hash_discriminant(&item.node);
 515         hash_span!(self, item.span);
 516         visit::walk_path_list_item(self, prefix, item)
 517     }
 518
 519     fn visit_path_segment(&mut self, path_span: Span, path_segment: &'tcx PathSegment) {
 520         debug!("visit_path_segment: st={:?}", self.st);
 521         SawPathSegment.hash(self.st);
 522         visit::walk_path_segment(self, path_span, path_segment)
 523     }
 524
 525     fn visit_path_parameters(&mut self, path_span: Span, path_parameters: &'tcx PathParameters) {
 526         debug!("visit_path_parameters: st={:?}", self.st);
 527         SawPathParameters.hash(self.st);
 528         self.hash_discriminant(path_parameters);
 529         visit::walk_path_parameters(self, path_span, path_parameters)
 530     }
 531
 532     fn visit_assoc_type_binding(&mut self, type_binding: &'tcx TypeBinding) {
 533         debug!("visit_assoc_type_binding: st={:?}", self.st);
 534         SawAssocTypeBinding.hash(self.st);
 535         hash_span!(self, type_binding.span);
 536         visit::walk_assoc_type_binding(self, type_binding)
 537     }
 538
 539     fn visit_attribute(&mut self, _: &ast::Attribute) {
 540         // We explicitly do not use this method, since doing that would
 541         // implicitly impose an order on the attributes being hashed, while we
 542         // explicitly don't want their order to matter
 543     }
 544
 545     fn visit_macro_def(&mut self, macro_def: &'tcx MacroDef) {
 546         debug!("visit_macro_def: st={:?}", self.st);
 547         if macro_def.export {
 548             SawMacroDef.hash(self.st);
 549             hash_attrs!(self, &macro_def.attrs);
 550             visit::walk_macro_def(self, macro_def)
 551             // FIXME(mw): We should hash the body of the macro too but we don't
 552             //            have a stable way of doing so yet.
 553         }
 554     }
 555 }
 556
 557 #[derive(Hash)]
 558 pub enum DefHash {
 559     SawDefId,
 560     SawLabel,
 561     SawPrimTy,
 562     SawSelfTy,
 563     SawErr,
 564 }
 565
 566 impl<'a, 'hash, 'tcx> StrictVersionHashVisitor<'a, 'hash, 'tcx> {
 567     fn hash_resolve(&mut self, id: ast::NodeId) {
 568         // Because whether or not a given id has an entry is dependent
 569         // solely on expr variant etc, we don't need to hash whether
 570         // or not an entry was present (we are already hashing what
 571         // variant it is above when we visit the HIR).
 572
 573         if let Some(def) = self.tcx.def_map.borrow().get(&id) {
 574             debug!("hash_resolve: id={:?} def={:?} st={:?}", id, def, self.st);
 575             self.hash_partial_def(def);
 576         }
 577
 578         if let Some(traits) = self.tcx.trait_map.get(&id) {
 579             debug!("hash_resolve: id={:?} traits={:?} st={:?}", id, traits, self.st);
 580             traits.len().hash(self.st);
 581
 582             // The ordering of the candidates is not fixed. So we hash
 583             // the def-ids and then sort them and hash the collection.
 584             let mut candidates: Vec<_> =
 585                 traits.iter()
 586                       .map(|&TraitCandidate { def_id, import_id: _ }| {
 587                           self.compute_def_id_hash(def_id)
 588                       })
 589                       .collect();
 590             candidates.sort();
 591             candidates.hash(self.st);
 592         }
 593     }
 594
 595     fn hash_def_id(&mut self, def_id: DefId) {
 596         self.compute_def_id_hash(def_id).hash(self.st);
 597     }
 598
 599     fn hash_partial_def(&mut self, def: &PathResolution) {
 600         self.hash_def(def.base_def);
 601         def.depth.hash(self.st);
 602     }
 603
 604     fn hash_def(&mut self, def: Def) {
 605         match def {
 606             // Crucial point: for all of these variants, the variant +
 607             // add'l data that is added is always the same if the
 608             // def-id is the same, so it suffices to hash the def-id
 609             Def::Fn(..) |
 610             Def::Mod(..) |
 611             Def::Static(..) |
 612             Def::Variant(..) |
 613             Def::Enum(..) |
 614             Def::TyAlias(..) |
 615             Def::AssociatedTy(..) |
 616             Def::TyParam(..) |
 617             Def::Struct(..) |
 618             Def::Union(..) |
 619             Def::Trait(..) |
 620             Def::Method(..) |
 621             Def::Const(..) |
 622             Def::AssociatedConst(..) |
 623             Def::Local(..) |
 624             Def::Upvar(..) => {
 625                 DefHash::SawDefId.hash(self.st);
 626                 self.hash_def_id(def.def_id());
 627             }
 628
 629             Def::Label(..) => {
 630                 DefHash::SawLabel.hash(self.st);
 631                 // we don't encode the `id` because it always refers to something
 632                 // within this item, so if it changed, there would have to be other
 633                 // changes too
 634             }
 635             Def::PrimTy(ref prim_ty) => {
 636                 DefHash::SawPrimTy.hash(self.st);
 637                 prim_ty.hash(self.st);
 638             }
 639             Def::SelfTy(..) => {
 640                 DefHash::SawSelfTy.hash(self.st);
 641                 // the meaning of Self is always the same within a
 642                 // given context, so we don't need to hash the other
 643                 // fields
 644             }
 645             Def::Err => {
 646                 DefHash::SawErr.hash(self.st);
 647             }
 648         }
 649     }
 650
 651     fn hash_meta_item(&mut self, meta_item: &ast::MetaItem) {
 652         debug!("hash_meta_item: st={:?}", self.st);
 653
 654         // ignoring span information, it doesn't matter here
 655         self.hash_discriminant(&meta_item.node);
 656         match meta_item.node {
 657             ast::MetaItemKind::Word(ref s) => {
 658                 s.len().hash(self.st);
 659                 s.hash(self.st);
 660             }
 661             ast::MetaItemKind::NameValue(ref s, ref lit) => {
 662                 s.len().hash(self.st);
 663                 s.hash(self.st);
 664                 lit.node.hash(self.st);
 665             }
 666             ast::MetaItemKind::List(ref s, ref items) => {
 667                 s.len().hash(self.st);
 668                 s.hash(self.st);
 669                 // Sort subitems so the hash does not depend on their order
 670                 let indices = self.indices_sorted_by(&items, |p| {
 671                     (p.name(), fnv::hash(&p.literal().map(|i| &i.node)))
 672                 });
 673                 items.len().hash(self.st);
 674                 for (index, &item_index) in indices.iter().enumerate() {
 675                     index.hash(self.st);
 676                     let nested_meta_item: &ast::NestedMetaItemKind = &items[item_index].node;
 677                     self.hash_discriminant(nested_meta_item);
 678                     match *nested_meta_item {
 679                         ast::NestedMetaItemKind::MetaItem(ref meta_item) => {
 680                             self.hash_meta_item(meta_item);
 681                         }
 682                         ast::NestedMetaItemKind::Literal(ref lit) => {
 683                             lit.node.hash(self.st);
 684                         }
 685                     }
 686                 }
 687             }
 688         }
 689     }
 690
 691     pub fn hash_attributes(&mut self, attributes: &[ast::Attribute]) {
 692         debug!("hash_attributes: st={:?}", self.st);
 693         let indices = self.indices_sorted_by(attributes, |attr| attr.name());
 694
 695         for i in indices {
 696             let attr = &attributes[i].node;
 697             if !attr.is_sugared_doc &&
 698                !IGNORED_ATTRIBUTES.contains(&&*attr.value.name()) {
 699                 SawAttribute(attr.style).hash(self.st);
 700                 self.hash_meta_item(&*attr.value);
 701             }
 702         }
 703     }
 704
 705     fn indices_sorted_by<T, K, F>(&mut self, items: &[T], get_key: F) -> Vec<usize>
 706         where K: Ord,
 707               F: Fn(&T) -> K
 708     {
 709         let mut indices = Vec::with_capacity(items.len());
 710         indices.extend(0 .. items.len());
 711         indices.sort_by_key(|index| get_key(&items[*index]));
 712         indices
 713     }
 714 }