incr.comp.: Compute hashes of all query results.

17 files changed, 828 insertions, 84 deletions

diff --git a/src/librustc/ich/hcx.rs b/src/librustc/ich/hcx.rs
index 5c011042dee..767868ffda3 100644
--- a/src/librustc/ich/hcx.rs
+++ b/src/librustc/ich/hcx.rs
@@ -13,9 +13,10 @@ use hir::def_id::DefId;
 use hir::map::DefPathHash;
 use ich::{self, CachingCodemapView};
 use session::config::DebugInfoLevel::NoDebugInfo;
-use ty::TyCtxt;
-use util::nodemap::{NodeMap, ItemLocalMap};
+use ty::{self, TyCtxt, fast_reject};
+use util::nodemap::{NodeMap, NodeSet, ItemLocalMap};
 
+use std::cmp::Ord;
 use std::hash as std_hash;
 use std::collections::{HashMap, HashSet, BTreeMap};
 
@@ -47,6 +48,7 @@ pub struct StableHashingContext<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 #[derive(PartialEq, Eq, Clone, Copy)]
 pub enum NodeIdHashingMode {
     Ignore,
+    CheckedIgnore,
     HashDefPath,
     HashTraitsInScope,
 }
@@ -148,7 +150,7 @@ impl<'a, 'gcx, 'tcx> StableHashingContext<'a, 'gcx, 'tcx> {
             self.overflow_checks_enabled = true;
         }
         let prev_hash_node_ids = self.node_id_hashing_mode;
-        self.node_id_hashing_mode = NodeIdHashingMode::Ignore;
+        self.node_id_hashing_mode = NodeIdHashingMode::CheckedIgnore;
 
         f(self);
 
@@ -202,6 +204,9 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for ast::N
         let hir_id = hcx.tcx.hir.node_to_hir_id(*self);
         match hcx.node_id_hashing_mode {
             NodeIdHashingMode::Ignore => {
+                // Don't do anything.
+            }
+            NodeIdHashingMode::CheckedIgnore => {
                 // Most NodeIds in the HIR can be ignored, but if there is a
                 // corresponding entry in the `trait_map` we need to hash that.
                 // Make sure we don't ignore too much by checking that there is
@@ -321,7 +326,7 @@ pub fn hash_stable_hashmap<'a, 'gcx, 'tcx, K, V, R, SK, F, W>(
     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.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
     keys.len().hash_stable(hcx, hasher);
     for (stable_key, key) in keys {
         stable_key.hash_stable(hcx, hasher);
@@ -354,8 +359,25 @@ pub fn hash_stable_nodemap<'a, 'tcx, 'gcx, V, W>(
     where V: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>,
           W: StableHasherResult,
 {
-    hash_stable_hashmap(hcx, hasher, map, |hcx, node_id| {
-        hcx.tcx.hir.definitions().node_to_hir_id(*node_id).local_id
+    let definitions = hcx.tcx.hir.definitions();
+    hash_stable_hashmap(hcx, hasher, map, |_, node_id| {
+        let hir_id = definitions.node_to_hir_id(*node_id);
+        let owner_def_path_hash = definitions.def_path_hash(hir_id.owner);
+        (owner_def_path_hash, hir_id.local_id)
+    });
+}
+
+pub fn hash_stable_nodeset<'a, 'tcx, 'gcx, W>(
+    hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+    hasher: &mut StableHasher<W>,
+    map: &NodeSet)
+    where W: StableHasherResult,
+{
+    let definitions = hcx.tcx.hir.definitions();
+    hash_stable_hashset(hcx, hasher, map, |_, node_id| {
+        let hir_id = definitions.node_to_hir_id(*node_id);
+        let owner_def_path_hash = definitions.def_path_hash(hir_id.owner);
+        (owner_def_path_hash, hir_id.local_id)
     });
 }
 
@@ -386,10 +408,56 @@ pub fn hash_stable_btreemap<'a, 'tcx, 'gcx, K, V, SK, F, W>(
     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.sort_unstable_by(|&(ref sk1, _), &(ref sk2, _)| sk1.cmp(sk2));
     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_trait_impls<'a, 'tcx, 'gcx, W, R>(
+    hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+    hasher: &mut StableHasher<W>,
+    blanket_impls: &Vec<DefId>,
+    non_blanket_impls: &HashMap<fast_reject::SimplifiedType, Vec<DefId>, R>)
+    where W: StableHasherResult,
+          R: std_hash::BuildHasher,
+{
+    {
+        let mut blanket_impls: AccumulateVec<[_; 8]> = blanket_impls
+            .iter()
+            .map(|&def_id| hcx.def_path_hash(def_id))
+            .collect();
+
+        if blanket_impls.len() > 1 {
+            blanket_impls.sort_unstable();
+        }
+
+        blanket_impls.hash_stable(hcx, hasher);
+    }
+
+    {
+        let tcx = hcx.tcx();
+        let mut keys: AccumulateVec<[_; 8]> =
+            non_blanket_impls.keys()
+                             .map(|k| (k, k.map_def(|d| tcx.def_path_hash(d))))
+                             .collect();
+        keys.sort_unstable_by(|&(_, ref k1), &(_, ref k2)| k1.cmp(k2));
+        keys.len().hash_stable(hcx, hasher);
+        for (key, ref stable_key) in keys {
+            stable_key.hash_stable(hcx, hasher);
+            let mut impls : AccumulateVec<[_; 8]> = non_blanket_impls[key]
+                .iter()
+                .map(|&impl_id| hcx.def_path_hash(impl_id))
+                .collect();
+
+            if impls.len() > 1 {
+                impls.sort_unstable();
+            }
+
+            impls.hash_stable(hcx, hasher);
+        }
+    }
+}
+
diff --git a/src/librustc/ich/impls_cstore.rs b/src/librustc/ich/impls_cstore.rs
index e95dbdd15c5..dad5c35c1e8 100644
--- a/src/librustc/ich/impls_cstore.rs
+++ b/src/librustc/ich/impls_cstore.rs
@@ -38,3 +38,10 @@ impl_stable_hash_for!(enum middle::cstore::LinkagePreference {
     RequireDynamic,
     RequireStatic
 });
+
+impl_stable_hash_for!(struct middle::cstore::ExternCrate {
+    def_id,
+    span,
+    direct,
+    path_len
+});
diff --git a/src/librustc/ich/impls_hir.rs b/src/librustc/ich/impls_hir.rs
index 411f5e26e4d..a4cbcf04111 100644
--- a/src/librustc/ich/impls_hir.rs
+++ b/src/librustc/ich/impls_hir.rs
@@ -13,13 +13,12 @@
 
 use hir;
 use hir::def_id::{DefId, CrateNum, CRATE_DEF_INDEX};
-use ich::{StableHashingContext, NodeIdHashingMode};
-use std::mem;
-
-use syntax::ast;
-
+use ich::{self, StableHashingContext, NodeIdHashingMode};
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
                                            StableHasherResult};
+use std::mem;
+use syntax::ast;
+use util::nodemap::DefIdSet;
 
 impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for DefId {
     #[inline]
@@ -30,6 +29,16 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for DefId
     }
 }
 
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for DefIdSet
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        ich::hash_stable_hashset(hcx, hasher, self, |hcx, def_id| {
+            hcx.def_path_hash(*def_id)
+        });
+    }
+}
 
 impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for hir::HirId {
     #[inline]
@@ -235,7 +244,7 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for hir::T
             hir::TyTypeof(..)      |
             hir::TyErr             |
             hir::TyInfer           => {
-                NodeIdHashingMode::Ignore
+                NodeIdHashingMode::CheckedIgnore
             }
             hir::TyPath(..) => {
                 NodeIdHashingMode::HashTraitsInScope
@@ -403,7 +412,7 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for hir::P
             hir::PatKind::Lit(..)     |
             hir::PatKind::Range(..)   |
             hir::PatKind::Slice(..)   => {
-                NodeIdHashingMode::Ignore
+                NodeIdHashingMode::CheckedIgnore
             }
             hir::PatKind::Path(..)        |
             hir::PatKind::Struct(..)      |
@@ -574,21 +583,21 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for hir::E
                 hir::ExprRepeat(..)     |
                 hir::ExprTup(..)        => {
                     // For these we only hash the span when debuginfo is on.
-                    (false, NodeIdHashingMode::Ignore)
+                    (false, NodeIdHashingMode::CheckedIgnore)
                 }
                 // For the following, spans might be significant because of
                 // panic messages indicating the source location.
                 hir::ExprBinary(op, ..) => {
-                    (hcx.binop_can_panic_at_runtime(op.node), NodeIdHashingMode::Ignore)
+                    (hcx.binop_can_panic_at_runtime(op.node), NodeIdHashingMode::CheckedIgnore)
                 }
                 hir::ExprUnary(op, _) => {
-                    (hcx.unop_can_panic_at_runtime(op), NodeIdHashingMode::Ignore)
+                    (hcx.unop_can_panic_at_runtime(op), NodeIdHashingMode::CheckedIgnore)
                 }
                 hir::ExprAssignOp(op, ..) => {
-                    (hcx.binop_can_panic_at_runtime(op.node), NodeIdHashingMode::Ignore)
+                    (hcx.binop_can_panic_at_runtime(op.node), NodeIdHashingMode::CheckedIgnore)
                 }
                 hir::ExprIndex(..) => {
-                    (true, NodeIdHashingMode::Ignore)
+                    (true, NodeIdHashingMode::CheckedIgnore)
                 }
                 // For these we don't care about the span, but want to hash the
                 // trait in scope
@@ -899,7 +908,7 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for hir::I
             hir::ItemStatic(..)      |
             hir::ItemConst(..)       |
             hir::ItemFn(..)          => {
-                (NodeIdHashingMode::Ignore, hcx.hash_spans())
+                (NodeIdHashingMode::CheckedIgnore, hcx.hash_spans())
             }
             hir::ItemUse(..) => {
                 (NodeIdHashingMode::HashTraitsInScope, false)
@@ -916,7 +925,7 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for hir::I
             hir::ItemEnum(..)        |
             hir::ItemStruct(..)      |
             hir::ItemUnion(..)       => {
-                (NodeIdHashingMode::Ignore, false)
+                (NodeIdHashingMode::CheckedIgnore, false)
             }
         };
 
@@ -1160,3 +1169,20 @@ for ::middle::lang_items::LangItem {
         ::std::hash::Hash::hash(self, hasher);
     }
 }
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+for hir::TraitCandidate {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+            let hir::TraitCandidate {
+                def_id,
+                import_id,
+            } = *self;
+
+            def_id.hash_stable(hcx, hasher);
+            import_id.hash_stable(hcx, hasher);
+        });
+    }
+}
diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index e933ca4c2b5..53a071fe480 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -11,12 +11,13 @@
 //! 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 middle::region;
+use traits;
 use ty;
 
 impl<'a, 'gcx, 'tcx, T> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
@@ -304,7 +305,9 @@ for ::middle::const_val::ConstVal<'gcx> {
             }
             Function(def_id, substs) => {
                 def_id.hash_stable(hcx, hasher);
-                substs.hash_stable(hcx, hasher);
+                hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+                    substs.hash_stable(hcx, hasher);
+                });
             }
             Aggregate(Struct(ref name_values)) => {
                 let mut values = name_values.to_vec();
@@ -338,6 +341,54 @@ impl_stable_hash_for!(struct ty::Const<'tcx> {
     val
 });
 
+impl_stable_hash_for!(struct ::middle::const_val::ConstEvalErr<'tcx> {
+    span,
+    kind
+});
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+for ::middle::const_val::ErrKind<'gcx> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        use middle::const_val::ErrKind::*;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+
+        match *self {
+            CannotCast |
+            MissingStructField |
+            NonConstPath |
+            ExpectedConstTuple |
+            ExpectedConstStruct |
+            IndexedNonVec |
+            IndexNotUsize |
+            MiscBinaryOp |
+            MiscCatchAll |
+            IndexOpFeatureGated |
+            TypeckError => {
+                // nothing to do
+            }
+            UnimplementedConstVal(s) => {
+                s.hash_stable(hcx, hasher);
+            }
+            IndexOutOfBounds { len, index } => {
+                len.hash_stable(hcx, hasher);
+                index.hash_stable(hcx, hasher);
+            }
+            Math(ref const_math_err) => {
+                const_math_err.hash_stable(hcx, hasher);
+            }
+            LayoutError(ref layout_error) => {
+                layout_error.hash_stable(hcx, hasher);
+            }
+            ErroneousReferencedConstant(ref const_val) => {
+                const_val.hash_stable(hcx, hasher);
+            }
+        }
+    }
+}
+
 impl_stable_hash_for!(struct ty::ClosureSubsts<'tcx> { substs });
 
 impl_stable_hash_for!(struct ty::GeneratorInterior<'tcx> { witness });
@@ -414,7 +465,6 @@ impl_stable_hash_for!(struct ty::TypeParameterDef {
     pure_wrt_drop
 });
 
-
 impl<'a, 'gcx, 'tcx, T> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
 for ::middle::resolve_lifetime::Set1<T>
     where T: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
@@ -470,19 +520,21 @@ for region::Scope
                                           hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
                                           hasher: &mut StableHasher<W>) {
         mem::discriminant(self).hash_stable(hcx, hasher);
-        match *self {
-            region::Scope::Node(node_id) |
-            region::Scope::Destruction(node_id) => {
-                node_id.hash_stable(hcx, hasher);
-            }
-            region::Scope::CallSite(body_id) |
-            region::Scope::Arguments(body_id) => {
-                body_id.hash_stable(hcx, hasher);
-            }
-            region::Scope::Remainder(block_remainder) => {
-                block_remainder.hash_stable(hcx, hasher);
-            }
-        }
+        hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+            match *self {
+                region::Scope::Node(node_id) |
+                region::Scope::Destruction(node_id) => {
+                    node_id.hash_stable(hcx, hasher);
+                }
+                region::Scope::CallSite(body_id) |
+                region::Scope::Arguments(body_id) => {
+                    body_id.hash_stable(hcx, hasher);
+                }
+                region::Scope::Remainder(block_remainder) => {
+                    block_remainder.hash_stable(hcx, hasher);
+                }
+            }
+        })
     }
 }
 
@@ -520,6 +572,7 @@ for ty::TypeVariants<'gcx>
             TyBool  |
             TyChar  |
             TyStr   |
+            TyError |
             TyNever => {
                 // Nothing more to hash.
             }
@@ -585,10 +638,8 @@ for ty::TypeVariants<'gcx>
             TyParam(param_ty) => {
                 param_ty.hash_stable(hcx, hasher);
             }
-
-            TyError     |
             TyInfer(..) => {
-                bug!("ty::TypeVariants::hash_stable() - Unexpected variant.")
+                bug!("ty::TypeVariants::hash_stable() - Unexpected variant {:?}.", *self)
             }
         }
     }
@@ -636,26 +687,6 @@ impl_stable_hash_for!(struct ty::ExistentialProjection<'tcx> {
     ty
 });
 
-impl_stable_hash_for!(enum ty::fast_reject::SimplifiedType {
-    BoolSimplifiedType,
-    CharSimplifiedType,
-    IntSimplifiedType(int_ty),
-    UintSimplifiedType(int_ty),
-    FloatSimplifiedType(float_ty),
-    AdtSimplifiedType(def_id),
-    StrSimplifiedType,
-    ArraySimplifiedType,
-    PtrSimplifiedType,
-    NeverSimplifiedType,
-    TupleSimplifiedType(size),
-    TraitSimplifiedType(def_id),
-    ClosureSimplifiedType(def_id),
-    GeneratorSimplifiedType(def_id),
-    AnonSimplifiedType(def_id),
-    FunctionSimplifiedType(params),
-    ParameterSimplifiedType
-});
-
 impl_stable_hash_for!(struct ty::Instance<'tcx> {
     def,
     substs
@@ -697,3 +728,149 @@ impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for ty::In
     }
 }
 
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for ty::TraitDef {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let ty::TraitDef {
+            // We already have the def_path_hash below, no need to hash it twice
+            def_id: _,
+            unsafety,
+            paren_sugar,
+            has_default_impl,
+            def_path_hash,
+        } = *self;
+
+        unsafety.hash_stable(hcx, hasher);
+        paren_sugar.hash_stable(hcx, hasher);
+        has_default_impl.hash_stable(hcx, hasher);
+        def_path_hash.hash_stable(hcx, hasher);
+    }
+}
+
+impl_stable_hash_for!(struct ty::Destructor {
+    did
+});
+
+impl_stable_hash_for!(struct ty::DtorckConstraint<'tcx> {
+    outlives,
+    dtorck_types
+});
+
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for ty::CrateVariancesMap {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let ty::CrateVariancesMap {
+            ref dependencies,
+            ref variances,
+            // This is just an irrelevant helper value.
+            empty_variance: _,
+        } = *self;
+
+        dependencies.hash_stable(hcx, hasher);
+
+        ich::hash_stable_hashmap(hcx, hasher, variances, |hcx, def_id| {
+            hcx.def_path_hash(*def_id)
+        });
+    }
+}
+
+impl_stable_hash_for!(struct ty::AssociatedItem {
+    def_id,
+    name,
+    kind,
+    vis,
+    defaultness,
+    container,
+    method_has_self_argument
+});
+
+impl_stable_hash_for!(enum ty::AssociatedKind {
+    Const,
+    Method,
+    Type
+});
+
+impl_stable_hash_for!(enum ty::AssociatedItemContainer {
+    TraitContainer(def_id),
+    ImplContainer(def_id)
+});
+
+
+impl<'a, 'gcx, 'tcx, T> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+for ty::steal::Steal<T>
+    where T: HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        self.borrow().hash_stable(hcx, hasher);
+    }
+}
+
+impl_stable_hash_for!(struct ty::ParamEnv<'tcx> {
+    caller_bounds,
+    reveal
+});
+
+impl_stable_hash_for!(enum traits::Reveal {
+    UserFacing,
+    All
+});
+
+impl_stable_hash_for!(enum ::middle::privacy::AccessLevel {
+    Reachable,
+    Exported,
+    Public
+});
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+for ::middle::privacy::AccessLevels {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+            let ::middle::privacy::AccessLevels {
+                ref map
+            } = *self;
+
+            ich::hash_stable_nodemap(hcx, hasher, map);
+        });
+    }
+}
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+for ty::CrateInherentImpls {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let ty::CrateInherentImpls {
+            ref inherent_impls,
+        } = *self;
+
+        ich::hash_stable_hashmap(hcx, hasher, inherent_impls, |hcx, def_id| {
+            hcx.def_path_hash(*def_id)
+        });
+    }
+}
+
+impl_stable_hash_for!(enum ::session::CompileIncomplete {
+    Stopped,
+    Errored(error_reported)
+});
+
+impl_stable_hash_for!(struct ::util::common::ErrorReported {});
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>>
+for ::middle::reachable::ReachableSet {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let ::middle::reachable::ReachableSet(ref reachable_set) = *self;
+
+        ich::hash_stable_nodeset(hcx, hasher, reachable_set);
+    }
+}
+
diff --git a/src/librustc/ich/mod.rs b/src/librustc/ich/mod.rs
index dcf84be0eeb..c24064eb27c 100644
--- a/src/librustc/ich/mod.rs
+++ b/src/librustc/ich/mod.rs
@@ -13,8 +13,9 @@
 pub use self::fingerprint::Fingerprint;
 pub use self::caching_codemap_view::CachingCodemapView;
 pub use self::hcx::{StableHashingContext, NodeIdHashingMode, hash_stable_hashmap,
-                    hash_stable_hashset, hash_stable_nodemap,
-                    hash_stable_btreemap, hash_stable_itemlocalmap};
+                    hash_stable_hashset, hash_stable_nodemap, hash_stable_nodeset,
+                    hash_stable_btreemap, hash_stable_itemlocalmap,
+                    hash_stable_trait_impls};
 mod fingerprint;
 mod caching_codemap_view;
 mod hcx;
diff --git a/src/librustc/lint/levels.rs b/src/librustc/lint/levels.rs
index c5863b5618f..e953afd799d 100644
--- a/src/librustc/lint/levels.rs
+++ b/src/librustc/lint/levels.rs
@@ -12,9 +12,12 @@ use std::cmp;
 
 use errors::DiagnosticBuilder;
 use hir::HirId;
+use ich::{self, StableHashingContext};
 use lint::builtin;
 use lint::context::CheckLintNameResult;
 use lint::{self, Lint, LintId, Level, LintSource};
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
+                                           StableHasherResult};
 use session::Session;
 use syntax::ast;
 use syntax::attr;
@@ -382,3 +385,61 @@ impl LintLevelMap {
         })
     }
 }
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for LintLevelMap {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let LintLevelMap {
+            ref sets,
+            ref id_to_set,
+        } = *self;
+
+        let definitions = hcx.tcx().hir.definitions();
+        ich::hash_stable_hashmap(hcx, hasher, id_to_set, |_, hir_id| {
+            (definitions.def_path_hash(hir_id.owner), hir_id.local_id)
+        });
+
+        let LintLevelSets {
+            ref list,
+            lint_cap,
+        } = *sets;
+
+        lint_cap.hash_stable(hcx, hasher);
+
+        hcx.while_hashing_spans(true, |hcx| {
+            list.len().hash_stable(hcx, hasher);
+
+            // We are working under the assumption here that the list of
+            // lint-sets is built in a deterministic order.
+            for lint_set in list {
+                ::std::mem::discriminant(lint_set).hash_stable(hcx, hasher);
+
+                match *lint_set {
+                    LintSet::CommandLine { ref specs } => {
+                        ich::hash_stable_hashmap(hcx, hasher, specs, |_, lint_id| {
+                            lint_id.lint_name_raw()
+                        });
+                    }
+                    LintSet::Node { ref specs, parent } => {
+                        ich::hash_stable_hashmap(hcx, hasher, specs, |_, lint_id| {
+                            lint_id.lint_name_raw()
+                        });
+                        parent.hash_stable(hcx, hasher);
+                    }
+                }
+            }
+        })
+    }
+}
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for LintId {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        self.lint_name_raw().hash_stable(hcx, hasher);
+    }
+}
+
diff --git a/src/librustc/lint/mod.rs b/src/librustc/lint/mod.rs
index c64e1c08082..42b5e2dd83d 100644
--- a/src/librustc/lint/mod.rs
+++ b/src/librustc/lint/mod.rs
@@ -305,6 +305,10 @@ impl LintId {
         }
     }
 
+    pub fn lint_name_raw(&self) -> &'static str {
+        self.lint.name
+    }
+
     /// Get the name of the lint.
     pub fn to_string(&self) -> String {
         self.lint.name_lower()
@@ -317,6 +321,13 @@ pub enum Level {
     Allow, Warn, Deny, Forbid
 }
 
+impl_stable_hash_for!(enum self::Level {
+    Allow,
+    Warn,
+    Deny,
+    Forbid
+});
+
 impl Level {
     /// Convert a level to a lower-case string.
     pub fn as_str(self) -> &'static str {
@@ -354,6 +365,12 @@ pub enum LintSource {
     CommandLine(Symbol),
 }
 
+impl_stable_hash_for!(enum self::LintSource {
+    Default,
+    Node(name, span),
+    CommandLine(text)
+});
+
 pub type LevelSource = (Level, LintSource);
 
 pub mod builtin;
diff --git a/src/librustc/middle/reachable.rs b/src/librustc/middle/reachable.rs
index 7c442450901..fa29dda86dd 100644
--- a/src/librustc/middle/reachable.rs
+++ b/src/librustc/middle/reachable.rs
@@ -369,7 +369,13 @@ impl<'a, 'tcx: 'a> ItemLikeVisitor<'tcx> for CollectPrivateImplItemsVisitor<'a,
     }
 }
 
-fn reachable_set<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) -> Rc<NodeSet> {
+// We introduce a new-type here, so we can have a specialized HashStable
+// implementation for it.
+#[derive(Clone)]
+pub struct ReachableSet(pub Rc<NodeSet>);
+
+
+fn reachable_set<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) -> ReachableSet {
     debug_assert!(crate_num == LOCAL_CRATE);
 
     let access_levels = &tcx.privacy_access_levels(LOCAL_CRATE);
@@ -414,7 +420,7 @@ fn reachable_set<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) ->
     reachable_context.propagate();
 
     // Return the set of reachable symbols.
-    Rc::new(reachable_context.reachable_symbols)
+    ReachableSet(Rc::new(reachable_context.reachable_symbols))
 }
 
 pub fn provide(providers: &mut Providers) {
diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index ae9866edc53..562536ced3c 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -14,6 +14,7 @@
 //! Most of the documentation on regions can be found in
 //! `middle/infer/region_inference/README.md`
 
+use ich::{self, StableHashingContext, NodeIdHashingMode};
 use util::nodemap::{FxHashMap, FxHashSet};
 use ty;
 
@@ -31,6 +32,8 @@ use hir::def_id::DefId;
 use hir::intravisit::{self, Visitor, NestedVisitorMap};
 use hir::{Block, Arm, Pat, PatKind, Stmt, Expr, Local};
 use mir::transform::MirSource;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
+                                           StableHasherResult};
 
 /// Scope represents a statically-describable scope that can be
 /// used to bound the lifetime/region for values.
@@ -1235,3 +1238,43 @@ pub fn provide(providers: &mut Providers) {
         ..*providers
     };
 }
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for ScopeTree {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let ScopeTree {
+            root_body,
+            root_parent,
+            ref parent_map,
+            ref var_map,
+            ref destruction_scopes,
+            ref rvalue_scopes,
+            ref closure_tree,
+            ref yield_in_scope,
+        } = *self;
+
+        hcx.with_node_id_hashing_mode(NodeIdHashingMode::HashDefPath, |hcx| {
+            root_body.hash_stable(hcx, hasher);
+            root_parent.hash_stable(hcx, hasher);
+        });
+
+        ich::hash_stable_hashmap(hcx, hasher, parent_map, |hcx, scope| {
+            let mut hasher = StableHasher::new();
+            scope.hash_stable(hcx, &mut hasher);
+            let stable: u64 = hasher.finish();
+            stable
+        });
+
+        ich::hash_stable_itemlocalmap(hcx, hasher, var_map);
+        ich::hash_stable_itemlocalmap(hcx, hasher, destruction_scopes);
+        ich::hash_stable_itemlocalmap(hcx, hasher, rvalue_scopes);
+        ich::hash_stable_itemlocalmap(hcx, hasher, closure_tree);
+        ich::hash_stable_hashmap(hcx, hasher, yield_in_scope, |hcx, scope| {
+            let mut hasher = StableHasher::new();
+            scope.hash_stable(hcx, &mut hasher);
+            let stable: u64 = hasher.finish();
+            stable
+        });
+    }
+}
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index 2640542ad10..ecaf14659ae 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -11,6 +11,9 @@
 use super::OverlapError;
 
 use hir::def_id::DefId;
+use ich::{self, StableHashingContext};
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
+                                           StableHasherResult};
 use traits;
 use ty::{self, TyCtxt, TypeFoldable};
 use ty::fast_reject::{self, SimplifiedType};
@@ -365,3 +368,34 @@ pub fn ancestors(tcx: TyCtxt,
         current_source: Some(Node::Impl(start_from_impl)),
     }
 }
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for Children {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let Children {
+            ref nonblanket_impls,
+            ref blanket_impls,
+        } = *self;
+
+        ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, nonblanket_impls);
+    }
+}
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for Graph {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let Graph {
+            ref parent,
+            ref children,
+        } = *self;
+
+        ich::hash_stable_hashmap(hcx, hasher, parent, |hcx, def_id| {
+            hcx.def_path_hash(*def_id)
+        });
+        ich::hash_stable_hashmap(hcx, hasher, children, |hcx, def_id| {
+            hcx.def_path_hash(*def_id)
+        });
+    }
+}
diff --git a/src/librustc/ty/fast_reject.rs b/src/librustc/ty/fast_reject.rs
index 353a1cd5355..86ae4bb92df 100644
--- a/src/librustc/ty/fast_reject.rs
+++ b/src/librustc/ty/fast_reject.rs
@@ -9,29 +9,44 @@
 // except according to those terms.
 
 use hir::def_id::DefId;
-use ty::{self, Ty, TyCtxt};
+use ich::StableHashingContext;
+use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult,
+                                           HashStable};
+use std::fmt::Debug;
+use std::hash::Hash;
+use std::mem;
 use syntax::ast;
+use ty::{self, Ty, TyCtxt};
 
-use self::SimplifiedType::*;
+use self::SimplifiedTypeGen::*;
 
-/// See `simplify_type
-#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
-pub enum SimplifiedType {
+pub type SimplifiedType = SimplifiedTypeGen<DefId>;
+
+/// See `simplify_type`
+///
+/// Note that we keep this type generic over the type of identifier it uses
+/// because we sometimes need to use SimplifiedTypeGen values as stable sorting
+/// keys (in which case we use a DefPathHash as id-type) but in the general case
+/// the non-stable but fast to construct DefId-version is the better choice.
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
+pub enum SimplifiedTypeGen<D>
+    where D: Copy + Debug + Ord + Eq + Hash
+{
     BoolSimplifiedType,
     CharSimplifiedType,
     IntSimplifiedType(ast::IntTy),
     UintSimplifiedType(ast::UintTy),
     FloatSimplifiedType(ast::FloatTy),
-    AdtSimplifiedType(DefId),
+    AdtSimplifiedType(D),
     StrSimplifiedType,
     ArraySimplifiedType,
     PtrSimplifiedType,
     NeverSimplifiedType,
     TupleSimplifiedType(usize),
-    TraitSimplifiedType(DefId),
-    ClosureSimplifiedType(DefId),
-    GeneratorSimplifiedType(DefId),
-    AnonSimplifiedType(DefId),
+    TraitSimplifiedType(D),
+    ClosureSimplifiedType(D),
+    GeneratorSimplifiedType(D),
+    AnonSimplifiedType(D),
     FunctionSimplifiedType(usize),
     ParameterSimplifiedType,
 }
@@ -101,3 +116,62 @@ pub fn simplify_type<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
         ty::TyInfer(_) | ty::TyError => None,
     }
 }
+
+impl<D: Copy + Debug + Ord + Eq + Hash> SimplifiedTypeGen<D> {
+    pub fn map_def<U, F>(self, map: F) -> SimplifiedTypeGen<U>
+        where F: Fn(D) -> U,
+              U: Copy + Debug + Ord + Eq + Hash,
+    {
+        match self {
+            BoolSimplifiedType => BoolSimplifiedType,
+            CharSimplifiedType => CharSimplifiedType,
+            IntSimplifiedType(t) => IntSimplifiedType(t),
+            UintSimplifiedType(t) => UintSimplifiedType(t),
+            FloatSimplifiedType(t) => FloatSimplifiedType(t),
+            AdtSimplifiedType(d) => AdtSimplifiedType(map(d)),
+            StrSimplifiedType => StrSimplifiedType,
+            ArraySimplifiedType => ArraySimplifiedType,
+            PtrSimplifiedType => PtrSimplifiedType,
+            NeverSimplifiedType => NeverSimplifiedType,
+            TupleSimplifiedType(n) => TupleSimplifiedType(n),
+            TraitSimplifiedType(d) => TraitSimplifiedType(map(d)),
+            ClosureSimplifiedType(d) => ClosureSimplifiedType(map(d)),
+            GeneratorSimplifiedType(d) => GeneratorSimplifiedType(map(d)),
+            AnonSimplifiedType(d) => AnonSimplifiedType(map(d)),
+            FunctionSimplifiedType(n) => FunctionSimplifiedType(n),
+            ParameterSimplifiedType => ParameterSimplifiedType,
+        }
+    }
+}
+
+impl<'a, 'gcx, 'tcx, D> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for SimplifiedTypeGen<D>
+    where D: Copy + Debug + Ord + Eq + Hash +
+             HashStable<StableHashingContext<'a, 'gcx, 'tcx>>,
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            BoolSimplifiedType |
+            CharSimplifiedType |
+            StrSimplifiedType |
+            ArraySimplifiedType |
+            PtrSimplifiedType |
+            NeverSimplifiedType |
+            ParameterSimplifiedType => {
+                // nothing to do
+            }
+            IntSimplifiedType(t) => t.hash_stable(hcx, hasher),
+            UintSimplifiedType(t) => t.hash_stable(hcx, hasher),
+            FloatSimplifiedType(t) => t.hash_stable(hcx, hasher),
+            AdtSimplifiedType(d) => d.hash_stable(hcx, hasher),
+            TupleSimplifiedType(n) => n.hash_stable(hcx, hasher),
+            TraitSimplifiedType(d) => d.hash_stable(hcx, hasher),
+            ClosureSimplifiedType(d) => d.hash_stable(hcx, hasher),
+            GeneratorSimplifiedType(d) => d.hash_stable(hcx, hasher),
+            AnonSimplifiedType(d) => d.hash_stable(hcx, hasher),
+            FunctionSimplifiedType(n) => n.hash_stable(hcx, hasher),
+        }
+    }
+}
diff --git a/src/librustc/ty/layout.rs b/src/librustc/ty/layout.rs
index 84d7745a64f..1ae1e7007ac 100644
--- a/src/librustc/ty/layout.rs
+++ b/src/librustc/ty/layout.rs
@@ -23,8 +23,13 @@ use std::cmp;
 use std::fmt;
 use std::i64;
 use std::iter;
+use std::mem;
 use std::ops::Deref;
 
+use ich::StableHashingContext;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
+                                           StableHasherResult};
+
 /// Parsed [Data layout](http://llvm.org/docs/LangRef.html#data-layout)
 /// for a target, which contains everything needed to compute layouts.
 pub struct TargetDataLayout {
@@ -2300,3 +2305,128 @@ impl<'a, 'tcx> TyLayout<'tcx> {
         cx.layout_of(cx.normalize_projections(self.field_type(cx, i)))
     }
 }
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for Layout
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        use ty::layout::Layout::*;
+        mem::discriminant(self).hash_stable(hcx, hasher);
+
+        match *self {
+            Scalar { value, non_zero } => {
+                value.hash_stable(hcx, hasher);
+                non_zero.hash_stable(hcx, hasher);
+            }
+            Vector { element, count } => {
+                element.hash_stable(hcx, hasher);
+                count.hash_stable(hcx, hasher);
+            }
+            Array { sized, align, primitive_align, element_size, count } => {
+                sized.hash_stable(hcx, hasher);
+                align.hash_stable(hcx, hasher);
+                primitive_align.hash_stable(hcx, hasher);
+                element_size.hash_stable(hcx, hasher);
+                count.hash_stable(hcx, hasher);
+            }
+            FatPointer { ref metadata, non_zero } => {
+                metadata.hash_stable(hcx, hasher);
+                non_zero.hash_stable(hcx, hasher);
+            }
+            CEnum { discr, signed, non_zero, min, max } => {
+                discr.hash_stable(hcx, hasher);
+                signed.hash_stable(hcx, hasher);
+                non_zero.hash_stable(hcx, hasher);
+                min.hash_stable(hcx, hasher);
+                max.hash_stable(hcx, hasher);
+            }
+            Univariant { ref variant, non_zero } => {
+                variant.hash_stable(hcx, hasher);
+                non_zero.hash_stable(hcx, hasher);
+            }
+            UntaggedUnion { ref variants } => {
+                variants.hash_stable(hcx, hasher);
+            }
+            General { discr, ref variants, size, align, primitive_align } => {
+                discr.hash_stable(hcx, hasher);
+                variants.hash_stable(hcx, hasher);
+                size.hash_stable(hcx, hasher);
+                align.hash_stable(hcx, hasher);
+                primitive_align.hash_stable(hcx, hasher);
+            }
+            RawNullablePointer { nndiscr, ref value } => {
+                nndiscr.hash_stable(hcx, hasher);
+                value.hash_stable(hcx, hasher);
+            }
+            StructWrappedNullablePointer {
+                nndiscr,
+                ref nonnull,
+                ref discrfield,
+                ref discrfield_source
+            } => {
+                nndiscr.hash_stable(hcx, hasher);
+                nonnull.hash_stable(hcx, hasher);
+                discrfield.hash_stable(hcx, hasher);
+                discrfield_source.hash_stable(hcx, hasher);
+            }
+        }
+    }
+}
+
+impl_stable_hash_for!(enum ::ty::layout::Integer {
+    I1,
+    I8,
+    I16,
+    I32,
+    I64,
+    I128
+});
+
+impl_stable_hash_for!(enum ::ty::layout::Primitive {
+    Int(integer),
+    F32,
+    F64,
+    Pointer
+});
+
+impl_stable_hash_for!(struct ::ty::layout::Align {
+    abi,
+    pref
+});
+
+impl_stable_hash_for!(struct ::ty::layout::Size {
+    raw
+});
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for LayoutError<'gcx>
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        use ty::layout::LayoutError::*;
+        mem::discriminant(self).hash_stable(hcx, hasher);
+
+        match *self {
+            Unknown(t) |
+            SizeOverflow(t) => t.hash_stable(hcx, hasher)
+        }
+    }
+}
+
+impl_stable_hash_for!(struct ::ty::layout::Struct {
+    align,
+    primitive_align,
+    packed,
+    sized,
+    offsets,
+    memory_index,
+    min_size
+});
+
+impl_stable_hash_for!(struct ::ty::layout::Union {
+    align,
+    primitive_align,
+    min_size,
+    packed
+});
diff --git a/src/librustc/ty/maps.rs b/src/librustc/ty/maps.rs
index bf17b82535c..48502dc2e8c 100644
--- a/src/librustc/ty/maps.rs
+++ b/src/librustc/ty/maps.rs
@@ -14,11 +14,13 @@ use hir::def_id::{CrateNum, DefId, LOCAL_CRATE, DefIndex};
 use hir::def::{Def, Export};
 use hir::{self, TraitCandidate, ItemLocalId};
 use hir::svh::Svh;
+use ich::{Fingerprint, StableHashingContext};
 use lint;
 use middle::const_val;
 use middle::cstore::{ExternCrate, LinkagePreference, NativeLibrary};
 use middle::cstore::{NativeLibraryKind, DepKind, CrateSource};
 use middle::privacy::AccessLevels;
+use middle::reachable::ReachableSet;
 use middle::region;
 use middle::resolve_lifetime::{Region, ObjectLifetimeDefault};
 use middle::stability::{self, DeprecationEntry};
@@ -36,7 +38,7 @@ use ty::item_path;
 use ty::steal::Steal;
 use ty::subst::Substs;
 use ty::fast_reject::SimplifiedType;
-use util::nodemap::{DefIdSet, NodeSet, DefIdMap};
+use util::nodemap::{DefIdSet, DefIdMap};
 use util::common::{profq_msg, ProfileQueriesMsg};
 
 use rustc_data_structures::indexed_set::IdxSetBuf;
@@ -44,6 +46,7 @@ use rustc_back::PanicStrategy;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use std::cell::{RefCell, RefMut, Cell};
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 use std::fmt::Debug;
 use std::hash::Hash;
 use std::marker::PhantomData;
@@ -925,9 +928,8 @@ macro_rules! define_maps {
                     span = key.default_span(tcx)
                 }
 
+                let dep_node = Self::to_dep_node(tcx, &key);
                 let res = tcx.cycle_check(span, Query::$name(key), || {
-                    let dep_node = Self::to_dep_node(tcx, &key);
-
                     tcx.sess.diagnostic().track_diagnostics(|| {
                         if dep_node.kind.is_anon() {
                             tcx.dep_graph.with_anon_task(dep_node.kind, || {
@@ -951,6 +953,20 @@ macro_rules! define_maps {
 
                 tcx.dep_graph.read_index(dep_node_index);
 
+                // In incremental mode, hash the result of the query. We don't
+                // do anything with the hash yet, but we are computing it
+                // anyway so that
+                //  - we make sure that the infrastructure works and
+                //  - we can get an idea of the runtime cost.
+                if !dep_node.kind.is_anon() && tcx.sess.opts.incremental.is_some() {
+                    let mut hcx = StableHashingContext::new(tcx);
+                    let mut hasher = StableHasher::new();
+
+                    result.hash_stable(&mut hcx, &mut hasher);
+
+                    let _: Fingerprint = hasher.finish();
+                }
+
                 let value = QueryValue {
                     value: result,
                     index: dep_node_index,
@@ -1300,7 +1316,7 @@ define_maps! { <'tcx>
     /// Performs the privacy check and computes "access levels".
     [] fn privacy_access_levels: PrivacyAccessLevels(CrateNum) -> Rc<AccessLevels>,
 
-    [] fn reachable_set: reachability_dep_node(CrateNum) -> Rc<NodeSet>,
+    [] fn reachable_set: reachability_dep_node(CrateNum) -> ReachableSet,
 
     /// Per-body `region::ScopeTree`. The `DefId` should be the owner-def-id for the body;
     /// in the case of closures, this will be redirected to the enclosing function.
diff --git a/src/librustc/ty/trait_def.rs b/src/librustc/ty/trait_def.rs
index 3aadacfe826..9ae6c3516a5 100644
--- a/src/librustc/ty/trait_def.rs
+++ b/src/librustc/ty/trait_def.rs
@@ -11,13 +11,15 @@
 use hir;
 use hir::def_id::DefId;
 use hir::map::DefPathHash;
+use ich::{self, StableHashingContext};
 use traits::specialization_graph;
 use ty::fast_reject;
 use ty::fold::TypeFoldable;
 use ty::{Ty, TyCtxt};
 
 use rustc_data_structures::fx::FxHashMap;
-
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
+                                           StableHasherResult};
 use std::rc::Rc;
 
 /// A trait's definition with type information.
@@ -183,3 +185,16 @@ pub(super) fn trait_impls_of_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         non_blanket_impls: non_blanket_impls,
     })
 }
+
+impl<'a, 'gcx, 'tcx> HashStable<StableHashingContext<'a, 'gcx, 'tcx>> for TraitImpls {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'gcx, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let TraitImpls {
+            ref blanket_impls,
+            ref non_blanket_impls,
+        } = *self;
+
+        ich::hash_stable_trait_impls(hcx, hasher, blanket_impls, non_blanket_impls);
+    }
+}
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 33c4a041cff..0d0cf672489 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -365,8 +365,24 @@ impl<T, CTX> HashStable<CTX> for Option<T>
     }
 }
 
+impl<T1, T2, CTX> HashStable<CTX> for Result<T1, T2>
+    where T1: HashStable<CTX>,
+          T2: HashStable<CTX>,
+{
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        mem::discriminant(self).hash_stable(ctx, hasher);
+        match *self {
+            Ok(ref x) => x.hash_stable(ctx, hasher),
+            Err(ref x) => x.hash_stable(ctx, hasher),
+        }
+    }
+}
+
 impl<'a, T, CTX> HashStable<CTX> for &'a T
-    where T: HashStable<CTX>
+    where T: HashStable<CTX> + ?Sized
 {
     #[inline]
     fn hash_stable<W: StableHasherResult>(&self,
@@ -425,3 +441,13 @@ impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for ::indexed_vec::IndexVec<
         }
     }
 }
+
+
+impl<I: ::indexed_vec::Idx, CTX> HashStable<CTX> for ::indexed_set::IdxSetBuf<I>
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.words().hash_stable(ctx, hasher);
+    }
+}
diff --git a/src/librustc_mir/transform/erase_regions.rs b/src/librustc_mir/transform/erase_regions.rs
index dc18cdd8f0d..6ed928ca09d 100644
--- a/src/librustc_mir/transform/erase_regions.rs
+++ b/src/librustc_mir/transform/erase_regions.rs
@@ -15,7 +15,8 @@
 //! "types-as-contracts"-validation, namely, AcquireValid, ReleaseValid, and EndRegion.
 
 use rustc::ty::subst::Substs;
-use rustc::ty::{self, Ty, TyCtxt};
+use rustc::ty::{self, Ty, TyCtxt, ClosureSubsts};
+use rustc::middle::const_val::ConstVal;
 use rustc::mir::*;
 use rustc::mir::visit::{MutVisitor, Lookup};
 use rustc::mir::transform::{MirPass, MirSource};
@@ -79,6 +80,45 @@ impl<'a, 'tcx> MutVisitor<'tcx> for EraseRegionsVisitor<'a, 'tcx> {
         self.super_statement(block, statement, location);
         self.in_validation_statement = false;
     }
+
+    fn visit_const_val(&mut self,
+                       const_val: &mut ConstVal<'tcx>,
+                       _: Location) {
+        erase_const_val(self.tcx, const_val);
+        self.super_const_val(const_val);
+
+        fn erase_const_val<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
+                                     const_val: &mut ConstVal<'tcx>) {
+            match *const_val {
+                ConstVal::Float(_)    |
+                ConstVal::Integral(_) |
+                ConstVal::Str(_)      |
+                ConstVal::ByteStr(_)  |
+                ConstVal::Bool(_)     |
+                ConstVal::Char(_)     |
+                ConstVal::Variant(_)  => {
+                    // nothing to do
+                }
+                ConstVal::Function(_, ref mut substs) => {
+                    *substs = tcx.erase_regions(&{*substs});
+                }
+                ConstVal::Struct(ref mut field_map) => {
+                    for (_, field_val) in field_map {
+                        erase_const_val(tcx, field_val);
+                    }
+                }
+                ConstVal::Tuple(ref mut fields) |
+                ConstVal::Array(ref mut fields) => {
+                    for field_val in fields {
+                        erase_const_val(tcx, field_val);
+                    }
+                }
+                ConstVal::Repeat(ref mut expr, _) => {
+                    erase_const_val(tcx, &mut **expr);
+                }
+            }
+        }
+    }
 }
 
 pub struct EraseRegions;
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index 5248f874a6e..496be8b3eb2 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -1221,7 +1221,8 @@ pub enum ImplItemKind {
     Macro(Mac),
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy,
+         PartialOrd, Ord)]
 pub enum IntTy {
     Is,
     I8,
@@ -1274,7 +1275,8 @@ impl IntTy {
     }
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy,
+         PartialOrd, Ord)]
 pub enum UintTy {
     Us,
     U8,
@@ -1324,7 +1326,8 @@ impl fmt::Display for UintTy {
     }
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy,
+         PartialOrd, Ord)]
 pub enum FloatTy {
     F32,
     F64,