ICH: Hash everything that gets encoded into crate metadata.

12 files changed, 576 insertions, 66 deletions

diff --git a/src/librustc/ich/hcx.rs b/src/librustc/ich/hcx.rs
index 5ef30550f11..3a6367c353c 100644
--- a/src/librustc/ich/hcx.rs
+++ b/src/librustc/ich/hcx.rs
@@ -13,8 +13,10 @@ use hir::def_id::DefId;
 use ich::{self, CachingCodemapView};
 use session::config::DebugInfoLevel::NoDebugInfo;
 use ty;
+use util::nodemap::NodeMap;
 
 use std::hash as std_hash;
+use std::collections::{HashMap, HashSet};
 
 use syntax::ast;
 use syntax::attr;
@@ -296,3 +298,53 @@ impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for Span {
         }
     }
 }
+
+pub fn hash_stable_hashmap<'a, 'tcx, K, V, R, SK, F, W>(hcx: &mut StableHashingContext<'a, 'tcx>,
+                                                        hasher: &mut StableHasher<W>,
+                                                        map: &HashMap<K, V, R>,
+                                                        extract_stable_key: F)
+    where K: Eq + std_hash::Hash,
+          V: HashStable<StableHashingContext<'a, 'tcx>>,
+          R: std_hash::BuildHasher,
+          SK: HashStable<StableHashingContext<'a, 'tcx>> + Ord + Clone,
+          F: Fn(&mut StableHashingContext<'a, 'tcx>, &K) -> SK,
+          W: StableHasherResult,
+{
+    let mut keys: Vec<_> = map.keys()
+                              .map(|k| (extract_stable_key(hcx, k), k))
+                              .collect();
+    keys.sort_unstable_by_key(|&(ref stable_key, _)| stable_key.clone());
+    keys.len().hash_stable(hcx, hasher);
+    for (stable_key, key) in keys {
+        stable_key.hash_stable(hcx, hasher);
+        map[key].hash_stable(hcx, hasher);
+    }
+}
+
+pub fn hash_stable_hashset<'a, 'tcx, K, R, SK, F, W>(hcx: &mut StableHashingContext<'a, 'tcx>,
+                                                     hasher: &mut StableHasher<W>,
+                                                     set: &HashSet<K, R>,
+                                                     extract_stable_key: F)
+    where K: Eq + std_hash::Hash,
+          R: std_hash::BuildHasher,
+          SK: HashStable<StableHashingContext<'a, 'tcx>> + Ord + Clone,
+          F: Fn(&mut StableHashingContext<'a, 'tcx>, &K) -> SK,
+          W: StableHasherResult,
+{
+    let mut keys: Vec<_> = set.iter()
+                              .map(|k| extract_stable_key(hcx, k))
+                              .collect();
+    keys.sort_unstable();
+    keys.hash_stable(hcx, hasher);
+}
+
+pub fn hash_stable_nodemap<'a, 'tcx, V, W>(hcx: &mut StableHashingContext<'a, 'tcx>,
+                                           hasher: &mut StableHasher<W>,
+                                           map: &NodeMap<V>)
+    where V: HashStable<StableHashingContext<'a, 'tcx>>,
+          W: StableHasherResult,
+{
+    hash_stable_hashmap(hcx, hasher, map, |hcx, node_id| {
+        hcx.tcx.hir.definitions().node_to_hir_id(*node_id).local_id
+    });
+}
diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 7b6f3af2a11..c682f6b8668 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -11,31 +11,37 @@
 //! This module contains `HashStable` implementations for various data types
 //! from rustc::ty in no particular order.
 
-use ich::StableHashingContext;
+use ich::{self, StableHashingContext, NodeIdHashingMode};
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
                                            StableHasherResult};
 use std::hash as std_hash;
 use std::mem;
 use ty;
 
-
-impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::Ty<'tcx> {
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::TyS<'tcx> {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a, 'tcx>,
                                           hasher: &mut StableHasher<W>) {
-        let type_hash = hcx.tcx().type_id_hash(*self);
-        type_hash.hash_stable(hcx, hasher);
+        let ty::TyS {
+            ref sty,
+
+            // The other fields just provide fast access to information that is
+            // also contained in `sty`, so no need to hash them.
+            ..
+        } = *self;
+
+        sty.hash_stable(hcx, hasher);
     }
 }
 
 impl_stable_hash_for!(struct ty::ItemSubsts<'tcx> { substs });
 
-impl<'a, 'tcx, T> HashStable<StableHashingContext<'a, 'tcx>> for ty::Slice<T>
+impl<'a, 'tcx, T> HashStable<StableHashingContext<'a, 'tcx>> for &'tcx ty::Slice<T>
     where T: HashStable<StableHashingContext<'a, 'tcx>> {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a, 'tcx>,
                                           hasher: &mut StableHasher<W>) {
-        (&**self).hash_stable(hcx, hasher);
+        (&self[..]).hash_stable(hcx, hasher);
     }
 }
 
@@ -67,9 +73,13 @@ impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::Region {
                 index.hash_stable(hcx, hasher);
                 name.hash_stable(hcx, hasher);
             }
+            ty::ReScope(code_extent) => {
+                code_extent.hash_stable(hcx, hasher);
+            }
+            ty::ReFree(ref free_region) => {
+                free_region.hash_stable(hcx, hasher);
+            }
             ty::ReLateBound(..) |
-            ty::ReFree(..) |
-            ty::ReScope(..) |
             ty::ReVar(..) |
             ty::ReSkolemized(..) => {
                 bug!("TypeIdHasher: unexpected region {:?}", *self)
@@ -127,7 +137,6 @@ impl_stable_hash_for!(enum ty::BorrowKind {
     MutBorrow
 });
 
-
 impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::UpvarCapture<'tcx> {
     fn hash_stable<W: StableHasherResult>(&self,
                                           hcx: &mut StableHashingContext<'a, 'tcx>,
@@ -223,7 +232,6 @@ impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::Predicate<'tcx
     }
 }
 
-
 impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::AdtFlags {
     fn hash_stable<W: StableHasherResult>(&self,
                                           _: &mut StableHashingContext<'a, 'tcx>,
@@ -303,7 +311,6 @@ for ::middle::const_val::ConstVal<'tcx> {
 
 impl_stable_hash_for!(struct ty::ClosureSubsts<'tcx> { substs });
 
-
 impl_stable_hash_for!(struct ty::GenericPredicates<'tcx> {
     parent,
     predicates
@@ -413,3 +420,263 @@ impl_stable_hash_for!(struct ::middle::region::CallSiteScopeData {
 impl_stable_hash_for!(struct ty::DebruijnIndex {
     depth
 });
+
+impl_stable_hash_for!(enum ty::cast::CastKind {
+    CoercionCast,
+    PtrPtrCast,
+    PtrAddrCast,
+    AddrPtrCast,
+    NumericCast,
+    EnumCast,
+    PrimIntCast,
+    U8CharCast,
+    ArrayPtrCast,
+    FnPtrPtrCast,
+    FnPtrAddrCast
+});
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ::middle::region::CodeExtent
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+            hcx.tcx().region_maps.code_extent_data(*self).hash_stable(hcx, hasher);
+        });
+    }
+}
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ::middle::region::CodeExtentData
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        use middle::region::CodeExtentData;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            CodeExtentData::Misc(node_id) |
+            CodeExtentData::DestructionScope(node_id) => {
+                node_id.hash_stable(hcx, hasher);
+            }
+            CodeExtentData::CallSiteScope { fn_id, body_id } |
+            CodeExtentData::ParameterScope { fn_id, body_id } => {
+                fn_id.hash_stable(hcx, hasher);
+                body_id.hash_stable(hcx, hasher);
+            }
+            CodeExtentData::Remainder(block_remainder) => {
+                block_remainder.hash_stable(hcx, hasher);
+            }
+        }
+    }
+}
+
+impl_stable_hash_for!(struct ::middle::region::BlockRemainder {
+    block,
+    first_statement_index
+});
+
+impl_stable_hash_for!(struct ty::adjustment::CoerceUnsizedInfo {
+    custom_kind
+});
+
+impl_stable_hash_for!(struct ty::FreeRegion {
+    scope,
+    bound_region
+});
+
+impl_stable_hash_for!(enum ty::BoundRegion {
+    BrAnon(index),
+    BrNamed(def_id, name),
+    BrFresh(index),
+    BrEnv
+});
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::TypeVariants<'tcx>
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        use ty::TypeVariants::*;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            TyBool  |
+            TyChar  |
+            TyStr   |
+            TyNever => {
+                // Nothing more to hash.
+            }
+            TyInt(int_ty) => {
+                int_ty.hash_stable(hcx, hasher);
+            }
+            TyUint(uint_ty) => {
+                uint_ty.hash_stable(hcx, hasher);
+            }
+            TyFloat(float_ty)  => {
+                float_ty.hash_stable(hcx, hasher);
+            }
+            TyAdt(adt_def, substs) => {
+                adt_def.hash_stable(hcx, hasher);
+                substs.hash_stable(hcx, hasher);
+            }
+            TyArray(inner_ty, len) => {
+                inner_ty.hash_stable(hcx, hasher);
+                len.hash_stable(hcx, hasher);
+            }
+            TySlice(inner_ty) => {
+                inner_ty.hash_stable(hcx, hasher);
+            }
+            TyRawPtr(pointee_ty) => {
+                pointee_ty.hash_stable(hcx, hasher);
+            }
+            TyRef(region, pointee_ty) => {
+                region.hash_stable(hcx, hasher);
+                pointee_ty.hash_stable(hcx, hasher);
+            }
+            TyFnDef(def_id, substs, ref sig) => {
+                def_id.hash_stable(hcx, hasher);
+                substs.hash_stable(hcx, hasher);
+                sig.hash_stable(hcx, hasher);
+            }
+            TyFnPtr(ref sig) => {
+                sig.hash_stable(hcx, hasher);
+            }
+            TyDynamic(ref existential_predicates, region) => {
+                existential_predicates.hash_stable(hcx, hasher);
+                region.hash_stable(hcx, hasher);
+            }
+            TyClosure(def_id, closure_substs) => {
+                def_id.hash_stable(hcx, hasher);
+                closure_substs.hash_stable(hcx, hasher);
+            }
+            TyTuple(inner_tys, from_diverging_type_var) => {
+                inner_tys.hash_stable(hcx, hasher);
+                from_diverging_type_var.hash_stable(hcx, hasher);
+            }
+            TyProjection(ref projection_ty) => {
+                projection_ty.hash_stable(hcx, hasher);
+            }
+            TyAnon(def_id, substs) => {
+                def_id.hash_stable(hcx, hasher);
+                substs.hash_stable(hcx, hasher);
+            }
+            TyParam(param_ty) => {
+                param_ty.hash_stable(hcx, hasher);
+            }
+
+            TyError     |
+            TyInfer(..) => {
+                bug!("ty::TypeVariants::hash_stable() - Unexpected variant.")
+            }
+        }
+    }
+}
+
+impl_stable_hash_for!(struct ty::ParamTy {
+    idx,
+    name
+});
+
+impl_stable_hash_for!(struct ty::TypeAndMut<'tcx> {
+    ty,
+    mutbl
+});
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::ExistentialPredicate<'tcx>
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            ty::ExistentialPredicate::Trait(ref trait_ref) => {
+                trait_ref.hash_stable(hcx, hasher);
+            }
+            ty::ExistentialPredicate::Projection(ref projection) => {
+                projection.hash_stable(hcx, hasher);
+            }
+            ty::ExistentialPredicate::AutoTrait(def_id) => {
+                def_id.hash_stable(hcx, hasher);
+            }
+        }
+    }
+}
+
+impl_stable_hash_for!(struct ty::ExistentialTraitRef<'tcx> {
+    def_id,
+    substs
+});
+
+impl_stable_hash_for!(struct ty::ExistentialProjection<'tcx> {
+    trait_ref,
+    item_name,
+    ty
+});
+
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a, 'tcx>> for ty::TypeckTables<'tcx> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let ty::TypeckTables {
+            ref type_relative_path_defs,
+            ref node_types,
+            ref item_substs,
+            ref adjustments,
+            ref method_map,
+            ref upvar_capture_map,
+            ref closure_tys,
+            ref closure_kinds,
+            ref liberated_fn_sigs,
+            ref fru_field_types,
+
+            ref cast_kinds,
+            lints: _,
+            ref used_trait_imports,
+            tainted_by_errors,
+            ref free_region_map,
+        } = *self;
+
+        hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+            ich::hash_stable_nodemap(hcx, hasher, type_relative_path_defs);
+            ich::hash_stable_nodemap(hcx, hasher, node_types);
+            ich::hash_stable_nodemap(hcx, hasher, item_substs);
+            ich::hash_stable_nodemap(hcx, hasher, adjustments);
+
+            ich::hash_stable_hashmap(hcx, hasher, method_map, |hcx, method_call| {
+                let ty::MethodCall {
+                    expr_id,
+                    autoderef
+                } = *method_call;
+
+                let def_id = hcx.tcx().hir.local_def_id(expr_id);
+                (hcx.def_path_hash(def_id), autoderef)
+            });
+
+            ich::hash_stable_hashmap(hcx, hasher, upvar_capture_map, |hcx, up_var_id| {
+                let ty::UpvarId {
+                    var_id,
+                    closure_expr_id
+                } = *up_var_id;
+
+                let var_def_id = hcx.tcx().hir.local_def_id(var_id);
+                let closure_def_id = hcx.tcx().hir.local_def_id(closure_expr_id);
+                (hcx.def_path_hash(var_def_id), hcx.def_path_hash(closure_def_id))
+            });
+
+            ich::hash_stable_nodemap(hcx, hasher, closure_tys);
+            ich::hash_stable_nodemap(hcx, hasher, closure_kinds);
+            ich::hash_stable_nodemap(hcx, hasher, liberated_fn_sigs);
+            ich::hash_stable_nodemap(hcx, hasher, fru_field_types);
+            ich::hash_stable_nodemap(hcx, hasher, cast_kinds);
+
+            ich::hash_stable_hashset(hcx, hasher, used_trait_imports, |hcx, def_id| {
+                hcx.tcx().def_path_hash(*def_id)
+            });
+
+            tainted_by_errors.hash_stable(hcx, hasher);
+            free_region_map.hash_stable(hcx, hasher);
+        })
+    }
+}
diff --git a/src/librustc/ich/mod.rs b/src/librustc/ich/mod.rs
index f932c90a331..d70ed051ac4 100644
--- a/src/librustc/ich/mod.rs
+++ b/src/librustc/ich/mod.rs
@@ -12,8 +12,8 @@
 
 pub use self::fingerprint::Fingerprint;
 pub use self::caching_codemap_view::CachingCodemapView;
-pub use self::hcx::{StableHashingContext, NodeIdHashingMode};
-
+pub use self::hcx::{StableHashingContext, NodeIdHashingMode, hash_stable_hashmap,
+                    hash_stable_hashset, hash_stable_nodemap};
 mod fingerprint;
 mod caching_codemap_view;
 mod hcx;
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 3b002fd4dfc..1f96330d51d 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -42,6 +42,7 @@
 #![feature(staged_api)]
 #![feature(unboxed_closures)]
 #![feature(discriminant_value)]
+#![feature(sort_unstable)]
 
 extern crate arena;
 extern crate core;
diff --git a/src/librustc/middle/free_region.rs b/src/librustc/middle/free_region.rs
index cdb081ab400..a8eb6a10743 100644
--- a/src/librustc/middle/free_region.rs
+++ b/src/librustc/middle/free_region.rs
@@ -180,3 +180,7 @@ fn lub() {
     map.relate_free_regions(frs[1], frs[2]);
     assert_eq!(map.lub_free_regions(frs[0], frs[1]), ty::ReFree(frs[2]));
 }
+
+impl_stable_hash_for!(struct FreeRegionMap {
+    relation
+});
diff --git a/src/librustc_data_structures/array_vec.rs b/src/librustc_data_structures/array_vec.rs
index adb22197226..848e5a076bb 100644
--- a/src/librustc_data_structures/array_vec.rs
+++ b/src/librustc_data_structures/array_vec.rs
@@ -40,6 +40,12 @@ unsafe impl<T> Array for [T; 8] {
     const LEN: usize = 8;
 }
 
+unsafe impl<T> Array for [T; 32] {
+    type Element = T;
+    type PartialStorage = [ManuallyDrop<T>; 32];
+    const LEN: usize = 32;
+}
+
 pub struct ArrayVec<A: Array> {
     count: usize,
     values: A::PartialStorage
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index 2bce7faf08c..2631108aeb5 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -9,11 +9,14 @@
 // except according to those terms.
 
 use bitvec::BitMatrix;
+use stable_hasher::{HashStable, StableHasher, StableHasherResult};
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
 use std::cell::RefCell;
 use std::fmt::Debug;
 use std::mem;
 
+
+
 #[derive(Clone)]
 pub struct TransitiveRelation<T: Debug + PartialEq> {
     // List of elements. This is used to map from a T to a usize.  We
@@ -334,6 +337,49 @@ impl<T> Decodable for TransitiveRelation<T>
     }
 }
 
+impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
+    where T: HashStable<CTX> + PartialEq + Debug
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        // We are assuming here that the relation graph has been built in a
+        // deterministic way and we can just hash it the way it is.
+        let TransitiveRelation {
+            ref elements,
+            ref edges,
+            // "closure" is just a copy of the data above
+            closure: _
+        } = *self;
+
+        elements.hash_stable(hcx, hasher);
+        edges.hash_stable(hcx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for Edge {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        let Edge {
+            ref source,
+            ref target,
+        } = *self;
+
+        source.hash_stable(hcx, hasher);
+        target.hash_stable(hcx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for Index {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        let Index(idx) = *self;
+        idx.hash_stable(hcx, hasher);
+    }
+}
+
 #[test]
 fn test_one_step() {
     let mut relation = TransitiveRelation::new();
diff --git a/src/librustc_metadata/astencode.rs b/src/librustc_metadata/astencode.rs
index 459132eb9c6..d9008ce555c 100644
--- a/src/librustc_metadata/astencode.rs
+++ b/src/librustc_metadata/astencode.rs
@@ -10,14 +10,12 @@
 
 use rustc::hir::intravisit::{Visitor, NestedVisitorMap};
 
-use encoder::EncodeContext;
+use index_builder::EntryBuilder;
 use schema::*;
 
 use rustc::hir;
 use rustc::ty;
 
-use rustc_serialize::Encodable;
-
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct Ast<'tcx> {
     pub body: Lazy<hir::Body>,
@@ -26,7 +24,14 @@ pub struct Ast<'tcx> {
     pub rvalue_promotable_to_static: bool,
 }
 
-impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
+impl_stable_hash_for!(struct Ast<'tcx> {
+    body,
+    tables,
+    nested_bodies,
+    rvalue_promotable_to_static
+});
+
+impl<'a, 'b, 'tcx> EntryBuilder<'a, 'b, 'tcx> {
     pub fn encode_body(&mut self, body_id: hir::BodyId) -> Lazy<Ast<'tcx>> {
         let body = self.tcx.hir.body(body_id);
         let lazy_body = self.lazy(body);
@@ -34,15 +39,12 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
         let tables = self.tcx.body_tables(body_id);
         let lazy_tables = self.lazy(tables);
 
-        let nested_pos = self.position();
-        let nested_count = {
-            let mut visitor = NestedBodyEncodingVisitor {
-                ecx: self,
-                count: 0,
-            };
-            visitor.visit_body(body);
-            visitor.count
+        let mut visitor = NestedBodyCollector {
+            tcx: self.tcx,
+            bodies_found: Vec::new(),
         };
+        visitor.visit_body(body);
+        let lazy_nested_bodies = self.lazy_seq_ref_from_slice(&visitor.bodies_found);
 
         let rvalue_promotable_to_static =
             self.tcx.rvalue_promotable_to_static.borrow()[&body.value.id];
@@ -50,27 +52,25 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
         self.lazy(&Ast {
             body: lazy_body,
             tables: lazy_tables,
-            nested_bodies: LazySeq::with_position_and_length(nested_pos, nested_count),
+            nested_bodies: lazy_nested_bodies,
             rvalue_promotable_to_static: rvalue_promotable_to_static
         })
     }
 }
 
-struct NestedBodyEncodingVisitor<'a, 'b: 'a, 'tcx: 'b> {
-    ecx: &'a mut EncodeContext<'b, 'tcx>,
-    count: usize,
+struct NestedBodyCollector<'a, 'tcx: 'a> {
+    tcx: ty::TyCtxt<'a, 'tcx, 'tcx>,
+    bodies_found: Vec<&'tcx hir::Body>,
 }
 
-impl<'a, 'b, 'tcx> Visitor<'tcx> for NestedBodyEncodingVisitor<'a, 'b, 'tcx> {
+impl<'a, 'tcx: 'a> Visitor<'tcx> for NestedBodyCollector<'a, 'tcx> {
     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
         NestedVisitorMap::None
     }
 
     fn visit_nested_body(&mut self, body: hir::BodyId) {
-        let body = self.ecx.tcx.hir.body(body);
-        body.encode(self.ecx).unwrap();
-        self.count += 1;
-
+        let body = self.tcx.hir.body(body);
+        self.bodies_found.push(body);
         self.visit_body(body);
     }
 }
diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs
index 38d774992a5..a74ce3f6502 100644
--- a/src/librustc_metadata/encoder.rs
+++ b/src/librustc_metadata/encoder.rs
@@ -15,6 +15,7 @@ use schema::*;
 use rustc::middle::cstore::{LinkMeta, LinkagePreference, NativeLibrary};
 use rustc::hir::def_id::{CrateNum, CRATE_DEF_INDEX, DefIndex, DefId};
 use rustc::hir::map::definitions::DefPathTable;
+use rustc::ich;
 use rustc::middle::dependency_format::Linkage;
 use rustc::middle::lang_items;
 use rustc::mir;
@@ -42,7 +43,7 @@ use rustc::hir::itemlikevisit::ItemLikeVisitor;
 use rustc::hir::intravisit::{Visitor, NestedVisitorMap};
 use rustc::hir::intravisit;
 
-use super::index_builder::{FromId, IndexBuilder, Untracked};
+use super::index_builder::{FromId, IndexBuilder, Untracked, EntryBuilder};
 
 pub struct EncodeContext<'a, 'tcx: 'a> {
     opaque: opaque::Encoder<'a>,
@@ -54,6 +55,8 @@ pub struct EncodeContext<'a, 'tcx: 'a> {
     lazy_state: LazyState,
     type_shorthands: FxHashMap<Ty<'tcx>, usize>,
     predicate_shorthands: FxHashMap<ty::Predicate<'tcx>, usize>,
+
+    pub metadata_hashes: Vec<(DefIndex, ich::Fingerprint)>,
 }
 
 macro_rules! encoder_methods {
@@ -172,7 +175,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
         })
     }
 
-    fn lazy_seq<I, T>(&mut self, iter: I) -> LazySeq<T>
+    pub fn lazy_seq<I, T>(&mut self, iter: I) -> LazySeq<T>
         where I: IntoIterator<Item = T>,
               T: Encodable
     {
@@ -184,7 +187,7 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
         })
     }
 
-    fn lazy_seq_ref<'b, I, T>(&mut self, iter: I) -> LazySeq<T>
+    pub fn lazy_seq_ref<'b, I, T>(&mut self, iter: I) -> LazySeq<T>
         where I: IntoIterator<Item = &'b T>,
               T: 'b + Encodable
     {
@@ -233,10 +236,12 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 
         Ok(())
     }
+}
 
+impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     fn encode_item_variances(&mut self, def_id: DefId) -> LazySeq<ty::Variance> {
         let tcx = self.tcx;
-        self.lazy_seq(tcx.item_variances(def_id).iter().cloned())
+        self.lazy_seq_from_slice(&tcx.item_variances(def_id))
     }
 
     fn encode_item_type(&mut self, def_id: DefId) -> Lazy<Ty<'tcx>> {
@@ -305,7 +310,9 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
 
         let data = ModData {
             reexports: match tcx.export_map.get(&id) {
-                Some(exports) if *vis == hir::Public => self.lazy_seq_ref(exports),
+                Some(exports) if *vis == hir::Public => {
+                    self.lazy_seq_from_slice(exports.as_slice())
+                }
                 _ => LazySeq::empty(),
             },
         };
@@ -339,14 +346,14 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
         for (variant_index, variant) in def.variants.iter().enumerate() {
             for (field_index, field) in variant.fields.iter().enumerate() {
                 self.record(field.did,
-                            EncodeContext::encode_field,
+                            EntryBuilder::encode_field,
                             (adt_def_id, Untracked((variant_index, field_index))));
             }
         }
     }
 }
 
-impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
+impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     /// Encode data for the given field of the given variant of the
     /// given ADT. The indices of the variant/field are untracked:
     /// this is ok because we will have to lookup the adt-def by its
@@ -907,7 +914,7 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
                 let def = self.tcx.lookup_adt_def(def_id);
                 for (i, variant) in def.variants.iter().enumerate() {
                     self.record(variant.did,
-                                EncodeContext::encode_enum_variant_info,
+                                EntryBuilder::encode_enum_variant_info,
                                 (def_id, Untracked(i)));
                 }
             }
@@ -918,7 +925,7 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
                 if !struct_def.is_struct() {
                     let ctor_def_id = self.tcx.hir.local_def_id(struct_def.id());
                     self.record(ctor_def_id,
-                                EncodeContext::encode_struct_ctor,
+                                EntryBuilder::encode_struct_ctor,
                                 (def_id, ctor_def_id));
                 }
             }
@@ -928,14 +935,14 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
             hir::ItemImpl(..) => {
                 for &trait_item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
                     self.record(trait_item_def_id,
-                                EncodeContext::encode_info_for_impl_item,
+                                EntryBuilder::encode_info_for_impl_item,
                                 trait_item_def_id);
                 }
             }
             hir::ItemTrait(..) => {
                 for &item_def_id in self.tcx.associated_item_def_ids(def_id).iter() {
                     self.record(item_def_id,
-                                EncodeContext::encode_info_for_trait_item,
+                                EntryBuilder::encode_info_for_trait_item,
                                 item_def_id);
                 }
             }
@@ -943,7 +950,7 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
     }
 }
 
-impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
+impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     fn encode_info_for_foreign_item(&mut self,
                                     (def_id, nitem): (DefId, &hir::ForeignItem))
                                     -> Entry<'tcx> {
@@ -1002,7 +1009,7 @@ impl<'a, 'b, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'tcx> {
         match item.node {
             hir::ItemExternCrate(_) |
             hir::ItemUse(..) => (), // ignore these
-            _ => self.index.record(def_id, EncodeContext::encode_info_for_item, (def_id, item)),
+            _ => self.index.record(def_id, EntryBuilder::encode_info_for_item, (def_id, item)),
         }
         self.index.encode_addl_info_for_item(item);
     }
@@ -1010,7 +1017,7 @@ impl<'a, 'b, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'tcx> {
         intravisit::walk_foreign_item(self, ni);
         let def_id = self.index.tcx.hir.local_def_id(ni.id);
         self.index.record(def_id,
-                          EncodeContext::encode_info_for_foreign_item,
+                          EntryBuilder::encode_info_for_foreign_item,
                           (def_id, ni));
     }
     fn visit_generics(&mut self, generics: &'tcx hir::Generics) {
@@ -1023,7 +1030,7 @@ impl<'a, 'b, 'tcx> Visitor<'tcx> for EncodeVisitor<'a, 'b, 'tcx> {
     }
     fn visit_macro_def(&mut self, macro_def: &'tcx hir::MacroDef) {
         let def_id = self.index.tcx.hir.local_def_id(macro_def.id);
-        self.index.record(def_id, EncodeContext::encode_info_for_macro_def, macro_def);
+        self.index.record(def_id, EntryBuilder::encode_info_for_macro_def, macro_def);
     }
 }
 
@@ -1032,14 +1039,14 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
         for ty_param in &generics.ty_params {
             let def_id = self.tcx.hir.local_def_id(ty_param.id);
             let has_default = Untracked(ty_param.default.is_some());
-            self.record(def_id, EncodeContext::encode_info_for_ty_param, (def_id, has_default));
+            self.record(def_id, EntryBuilder::encode_info_for_ty_param, (def_id, has_default));
         }
     }
 
     fn encode_info_for_ty(&mut self, ty: &hir::Ty) {
         if let hir::TyImplTrait(_) = ty.node {
             let def_id = self.tcx.hir.local_def_id(ty.id);
-            self.record(def_id, EncodeContext::encode_info_for_anon_ty, def_id);
+            self.record(def_id, EntryBuilder::encode_info_for_anon_ty, def_id);
         }
     }
 
@@ -1047,14 +1054,14 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
         match expr.node {
             hir::ExprClosure(..) => {
                 let def_id = self.tcx.hir.local_def_id(expr.id);
-                self.record(def_id, EncodeContext::encode_info_for_closure, def_id);
+                self.record(def_id, EntryBuilder::encode_info_for_closure, def_id);
             }
             _ => {}
         }
     }
 }
 
-impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
+impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
     fn encode_info_for_ty_param(&mut self,
                                 (def_id, Untracked(has_default)): (DefId, Untracked<bool>))
                                 -> Entry<'tcx> {
@@ -1133,11 +1140,17 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
         }
     }
 
+    fn encode_attributes(&mut self, attrs: &[ast::Attribute]) -> LazySeq<ast::Attribute> {
+        self.lazy_seq_from_slice(attrs)
+    }
+}
+
+impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
     fn encode_info_for_items(&mut self) -> Index {
         let krate = self.tcx.hir.krate();
         let mut index = IndexBuilder::new(self);
         index.record(DefId::local(CRATE_DEF_INDEX),
-                     EncodeContext::encode_info_for_mod,
+                     EntryBuilder::encode_info_for_mod,
                      FromId(CRATE_NODE_ID, (&krate.module, &krate.attrs, &hir::Public)));
         let mut visitor = EncodeVisitor { index: index };
         krate.visit_all_item_likes(&mut visitor.as_deep_visitor());
@@ -1147,10 +1160,6 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
         visitor.index.into_items()
     }
 
-    fn encode_attributes(&mut self, attrs: &[ast::Attribute]) -> LazySeq<ast::Attribute> {
-        self.lazy_seq_ref(attrs)
-    }
-
     fn encode_crate_deps(&mut self) -> LazySeq<CrateDep> {
         fn get_ordered_deps(cstore: &cstore::CStore) -> Vec<(CrateNum, Rc<cstore::CrateMetadata>)> {
             // Pull the cnums and name,vers,hash out of cstore
@@ -1298,7 +1307,9 @@ impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
             None => LazySeq::empty(),
         }
     }
+}
 
+impl<'a, 'tcx> EncodeContext<'a, 'tcx> {
     fn encode_crate_root(&mut self) -> Lazy<CrateRoot> {
         let mut i = self.position();
         let crate_deps = self.encode_crate_deps();
@@ -1448,6 +1459,7 @@ pub fn encode_metadata<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             lazy_state: LazyState::NoNode,
             type_shorthands: Default::default(),
             predicate_shorthands: Default::default(),
+            metadata_hashes: Vec::new(),
         };
 
         // Encode the rustc version string in a predictable location.
diff --git a/src/librustc_metadata/index_builder.rs b/src/librustc_metadata/index_builder.rs
index a811f72bc95..389ada12da8 100644
--- a/src/librustc_metadata/index_builder.rs
+++ b/src/librustc_metadata/index_builder.rs
@@ -59,14 +59,19 @@ use encoder::EncodeContext;
 use index::Index;
 use schema::*;
 
-use rustc::dep_graph::DepNode;
 use rustc::hir;
 use rustc::hir::def_id::DefId;
+use rustc::ich::{StableHashingContext, Fingerprint};
 use rustc::ty::TyCtxt;
 use syntax::ast;
 
 use std::ops::{Deref, DerefMut};
 
+use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
+use rustc_serialize::Encodable;
+
+use rustc::dep_graph::DepNode;
+
 /// Builder that can encode new items, adding them into the index.
 /// Item encoding cannot be nested.
 pub struct IndexBuilder<'a, 'b: 'a, 'tcx: 'b> {
@@ -112,16 +117,29 @@ impl<'a, 'b, 'tcx> IndexBuilder<'a, 'b, 'tcx> {
     /// holds, and that it is therefore not gaining "secret" access to
     /// bits of HIR or other state that would not be trackd by the
     /// content system.
-    pub fn record<DATA>(&mut self,
-                        id: DefId,
-                        op: fn(&mut EncodeContext<'b, 'tcx>, DATA) -> Entry<'tcx>,
-                        data: DATA)
+    pub fn record<'x, DATA>(&'x mut self,
+                            id: DefId,
+                            op: fn(&mut EntryBuilder<'x, 'b, 'tcx>, DATA) -> Entry<'tcx>,
+                            data: DATA)
         where DATA: DepGraphRead
     {
         let _task = self.tcx.dep_graph.in_task(DepNode::MetaData(id));
         data.read(self.tcx);
-        let entry = op(&mut self.ecx, data);
-        self.items.record(id, self.ecx.lazy(&entry));
+
+        assert!(id.is_local());
+        let tcx: TyCtxt<'b, 'tcx, 'tcx> = self.ecx.tcx;
+        let ecx: &'x mut EncodeContext<'b, 'tcx> = &mut *self.ecx;
+        let mut entry_builder = EntryBuilder {
+            tcx: tcx,
+            ecx: ecx,
+            hasher: StableHasher::new(),
+            hcx: StableHashingContext::new(tcx),
+        };
+
+        let entry = op(&mut entry_builder, data);
+        let entry = entry_builder.ecx.lazy(&entry);
+        entry_builder.finish(id);
+        self.items.record(id, entry);
     }
 
     pub fn into_items(self) -> Index {
@@ -223,3 +241,48 @@ impl<T> DepGraphRead for FromId<T> {
         tcx.hir.read(self.0);
     }
 }
+
+pub struct EntryBuilder<'a, 'b: 'a, 'tcx: 'b> {
+    pub tcx: TyCtxt<'b, 'tcx, 'tcx>,
+    ecx: &'a mut EncodeContext<'b, 'tcx>,
+    hasher: StableHasher<Fingerprint>,
+    hcx: StableHashingContext<'b, 'tcx>,
+}
+
+impl<'a, 'b: 'a, 'tcx: 'b> EntryBuilder<'a, 'b, 'tcx> {
+
+    pub fn finish(self, def_id: DefId) {
+        let hash = self.hasher.finish();
+        self.ecx.metadata_hashes.push((def_id.index, hash));
+    }
+
+    pub fn lazy<T>(&mut self, value: &T) -> Lazy<T>
+        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        value.hash_stable(&mut self.hcx, &mut self.hasher);
+        self.ecx.lazy(value)
+    }
+
+    pub fn lazy_seq<I, T>(&mut self, iter: I) -> LazySeq<T>
+        where I: IntoIterator<Item = T>,
+              T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        let items: Vec<T> = iter.into_iter().collect();
+        items.hash_stable(&mut self.hcx, &mut self.hasher);
+        self.ecx.lazy_seq(items)
+    }
+
+    pub fn lazy_seq_from_slice<T>(&mut self, slice: &[T]) -> LazySeq<T>
+        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        slice.hash_stable(&mut self.hcx, &mut self.hasher);
+        self.ecx.lazy_seq_ref(slice.iter())
+    }
+
+    pub fn lazy_seq_ref_from_slice<T>(&mut self, slice: &[&T]) -> LazySeq<T>
+        where T: Encodable + HashStable<StableHashingContext<'b, 'tcx>>
+    {
+        slice.hash_stable(&mut self.hcx, &mut self.hasher);
+        self.ecx.lazy_seq_ref(slice.iter().map(|x| *x))
+    }
+}
diff --git a/src/librustc_metadata/lib.rs b/src/librustc_metadata/lib.rs
index 2fbdb8c0de6..b9e142ac650 100644
--- a/src/librustc_metadata/lib.rs
+++ b/src/librustc_metadata/lib.rs
@@ -27,6 +27,7 @@
 #![feature(rustc_private)]
 #![feature(specialization)]
 #![feature(staged_api)]
+#![feature(discriminant_value)]
 
 #[macro_use]
 extern crate log;
diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs
index abb482a50eb..6ffa31c0727 100644
--- a/src/librustc_metadata/schema.rs
+++ b/src/librustc_metadata/schema.rs
@@ -28,6 +28,9 @@ use syntax_pos::{self, Span};
 
 use std::marker::PhantomData;
 
+use rustc_data_structures::stable_hasher::{StableHasher, HashStable,
+                                           StableHasherResult};
+
 pub fn rustc_version() -> String {
     format!("rustc {}",
             option_env!("CFG_VERSION").unwrap_or("unknown version"))
@@ -100,6 +103,15 @@ impl<T> Clone for Lazy<T> {
 impl<T> serialize::UseSpecializedEncodable for Lazy<T> {}
 impl<T> serialize::UseSpecializedDecodable for Lazy<T> {}
 
+impl<CTX, T> HashStable<CTX> for Lazy<T> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          _: &mut CTX,
+                                          _: &mut StableHasher<W>) {
+            // There's nothing to do. Whatever got encoded within this Lazy<>
+            // wrapper has already been hashed.
+    }
+}
+
 /// A sequence of type T referred to by its absolute position
 /// in the metadata and length, and which can be decoded lazily.
 /// The sequence is a single node for the purposes of `Lazy`.
@@ -148,6 +160,15 @@ impl<T> Clone for LazySeq<T> {
 impl<T> serialize::UseSpecializedEncodable for LazySeq<T> {}
 impl<T> serialize::UseSpecializedDecodable for LazySeq<T> {}
 
+impl<CTX, T> HashStable<CTX> for LazySeq<T> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          _: &mut CTX,
+                                          _: &mut StableHasher<W>) {
+            // There's nothing to do. Whatever got encoded within this Lazy<>
+            // wrapper has already been hashed.
+    }
+}
+
 /// Encoding / decoding state for `Lazy` and `LazySeq`.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
 pub enum LazyState {
@@ -251,17 +272,23 @@ pub struct ModData {
     pub reexports: LazySeq<def::Export>,
 }
 
+impl_stable_hash_for!(struct ModData { reexports });
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct MacroDef {
     pub body: String,
 }
 
+impl_stable_hash_for!(struct MacroDef { body });
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct FnData {
     pub constness: hir::Constness,
     pub arg_names: LazySeq<ast::Name>,
 }
 
+impl_stable_hash_for!(struct FnData { constness, arg_names });
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct VariantData<'tcx> {
     pub ctor_kind: CtorKind,
@@ -273,6 +300,13 @@ pub struct VariantData<'tcx> {
     pub struct_ctor: Option<DefIndex>,
 }
 
+impl_stable_hash_for!(struct VariantData<'tcx> {
+    ctor_kind,
+    discr,
+    evaluated_discr,
+    struct_ctor
+});
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct TraitData<'tcx> {
     pub unsafety: hir::Unsafety,
@@ -281,6 +315,13 @@ pub struct TraitData<'tcx> {
     pub super_predicates: Lazy<ty::GenericPredicates<'tcx>>,
 }
 
+impl_stable_hash_for!(struct TraitData<'tcx> {
+    unsafety,
+    paren_sugar,
+    has_default_impl,
+    super_predicates
+});
+
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct ImplData<'tcx> {
     pub polarity: hir::ImplPolarity,
@@ -291,6 +332,14 @@ pub struct ImplData<'tcx> {
     pub trait_ref: Option<Lazy<ty::TraitRef<'tcx>>>,
 }
 
+impl_stable_hash_for!(struct ImplData<'tcx> {
+    polarity,
+    parent_impl,
+    coerce_unsized_info,
+    trait_ref
+});
+
+
 /// Describes whether the container of an associated item
 /// is a trait or an impl and whether, in a trait, it has
 /// a default, or an in impl, whether it's marked "default".
@@ -302,6 +351,13 @@ pub enum AssociatedContainer {
     ImplFinal,
 }
 
+impl_stable_hash_for!(enum ::schema::AssociatedContainer {
+    TraitRequired,
+    TraitWithDefault,
+    ImplDefault,
+    ImplFinal
+});
+
 impl AssociatedContainer {
     pub fn with_def_id(&self, def_id: DefId) -> ty::AssociatedItemContainer {
         match *self {
@@ -335,9 +391,11 @@ pub struct MethodData {
     pub container: AssociatedContainer,
     pub has_self: bool,
 }
+impl_stable_hash_for!(struct MethodData { fn_data, container, has_self });
 
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct ClosureData<'tcx> {
     pub kind: ty::ClosureKind,
     pub ty: Lazy<ty::PolyFnSig<'tcx>>,
 }
+impl_stable_hash_for!(struct ClosureData<'tcx> { kind, ty });