ICH: Hash lists of local trait impls as part of the HIR.

11 files changed, 127 insertions, 17 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 25fc5b7a4f6..93dd76a6984 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -116,6 +116,8 @@ pub enum DepNode<D: Clone + Debug> {
     // than changes in the impl body.
     TraitImpls(D),
 
+    AllLocalTraitImpls,
+
     // Nodes representing caches. To properly handle a true cache, we
     // don't use a DepTrackingMap, but rather we push a task node.
     // Otherwise the write into the map would be incorrectly
@@ -263,6 +265,7 @@ impl<D: Clone + Debug> DepNode<D> {
             ConstEval(ref d) => op(d).map(ConstEval),
             SymbolName(ref d) => op(d).map(SymbolName),
             TraitImpls(ref d) => op(d).map(TraitImpls),
+            AllLocalTraitImpls => Some(AllLocalTraitImpls),
             TraitItems(ref d) => op(d).map(TraitItems),
             ReprHints(ref d) => op(d).map(ReprHints),
             TraitSelect { ref trait_def_id, ref input_def_id } => {
diff --git a/src/librustc/hir/map/mod.rs b/src/librustc/hir/map/mod.rs
index c715484a934..868730edfed 100644
--- a/src/librustc/hir/map/mod.rs
+++ b/src/librustc/hir/map/mod.rs
@@ -497,7 +497,7 @@ impl<'hir> Map<'hir> {
     }
 
     pub fn trait_impls(&self, trait_did: DefId) -> &'hir [NodeId] {
-        self.dep_graph.read(DepNode::TraitImpls(trait_did));
+        self.dep_graph.read(DepNode::AllLocalTraitImpls);
 
         // NB: intentionally bypass `self.forest.krate()` so that we
         // do not trigger a read of the whole krate here
@@ -505,7 +505,7 @@ impl<'hir> Map<'hir> {
     }
 
     pub fn trait_default_impl(&self, trait_did: DefId) -> Option<NodeId> {
-        self.dep_graph.read(DepNode::TraitImpls(trait_did));
+        self.dep_graph.read(DepNode::AllLocalTraitImpls);
 
         // NB: intentionally bypass `self.forest.krate()` so that we
         // do not trigger a read of the whole krate here
diff --git a/src/librustc/ich/fingerprint.rs b/src/librustc/ich/fingerprint.rs
index e760f7efc93..ccdbab88b8b 100644
--- a/src/librustc/ich/fingerprint.rs
+++ b/src/librustc/ich/fingerprint.rs
@@ -94,3 +94,11 @@ impl stable_hasher::StableHasherResult for Fingerprint {
         fingerprint
     }
 }
+
+impl<CTX> stable_hasher::HashStable<CTX> for Fingerprint {
+    fn hash_stable<W: stable_hasher::StableHasherResult>(&self,
+                                          _: &mut CTX,
+                                          hasher: &mut stable_hasher::StableHasher<W>) {
+        ::std::hash::Hash::hash(&self.0, hasher);
+    }
+}
diff --git a/src/librustc/ich/hcx.rs b/src/librustc/ich/hcx.rs
index 3a6367c353c..786d1c5035d 100644
--- a/src/librustc/ich/hcx.rs
+++ b/src/librustc/ich/hcx.rs
@@ -16,7 +16,7 @@ use ty;
 use util::nodemap::NodeMap;
 
 use std::hash as std_hash;
-use std::collections::{HashMap, HashSet};
+use std::collections::{HashMap, HashSet, BTreeMap};
 
 use syntax::ast;
 use syntax::attr;
@@ -348,3 +348,25 @@ pub fn hash_stable_nodemap<'a, 'tcx, V, W>(hcx: &mut StableHashingContext<'a, 't
         hcx.tcx.hir.definitions().node_to_hir_id(*node_id).local_id
     });
 }
+
+
+pub fn hash_stable_btreemap<'a, 'tcx, K, V, SK, F, W>(hcx: &mut StableHashingContext<'a, 'tcx>,
+                                                      hasher: &mut StableHasher<W>,
+                                                      map: &BTreeMap<K, V>,
+                                                      extract_stable_key: F)
+    where K: Eq + Ord,
+          V: HashStable<StableHashingContext<'a, 'tcx>>,
+          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);
+    }
+}
diff --git a/src/librustc/ich/mod.rs b/src/librustc/ich/mod.rs
index d881a1cc45a..5b238090850 100644
--- a/src/librustc/ich/mod.rs
+++ b/src/librustc/ich/mod.rs
@@ -13,7 +13,8 @@
 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_hashset, hash_stable_nodemap,
+                    hash_stable_btreemap};
 mod fingerprint;
 mod caching_codemap_view;
 mod hcx;
diff --git a/src/librustc_incremental/calculate_svh/mod.rs b/src/librustc_incremental/calculate_svh/mod.rs
index 6f5cc1f3f45..8cdabc1d894 100644
--- a/src/librustc_incremental/calculate_svh/mod.rs
+++ b/src/librustc_incremental/calculate_svh/mod.rs
@@ -36,9 +36,10 @@ use rustc::hir::def_id::{LOCAL_CRATE, CRATE_DEF_INDEX, DefId};
 use rustc::hir::itemlikevisit::ItemLikeVisitor;
 use rustc::ich::{Fingerprint, StableHashingContext};
 use rustc::ty::TyCtxt;
+use rustc::util::common::record_time;
 use rustc_data_structures::stable_hasher::{StableHasher, HashStable};
 use rustc_data_structures::fx::FxHashMap;
-use rustc::util::common::record_time;
+use rustc_data_structures::accumulate_vec::AccumulateVec;
 
 pub type IchHasher = StableHasher<Fingerprint>;
 
@@ -159,6 +160,11 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
                                         // difference, filter them out.
                                         return None
                                     }
+                                    DepNode::AllLocalTraitImpls => {
+                                        // These are already covered by hashing
+                                        // the HIR.
+                                        return None
+                                    }
                                     ref other => {
                                         bug!("Found unexpected DepNode during \
                                               SVH computation: {:?}",
@@ -213,6 +219,49 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
                                                  true,
                                                  (module, (span, attrs)));
     }
+
+    fn compute_and_store_ich_for_trait_impls(&mut self, krate: &'tcx hir::Crate)
+    {
+        let tcx = self.hcx.tcx();
+
+        let mut impls: Vec<(u64, Fingerprint)> = krate
+            .trait_impls
+            .iter()
+            .map(|(&trait_id, impls)| {
+                let trait_id = tcx.def_path_hash(trait_id);
+                let mut impls: AccumulateVec<[_; 32]> = impls
+                    .iter()
+                    .map(|&node_id| {
+                        let def_id = tcx.hir.local_def_id(node_id);
+                        tcx.def_path_hash(def_id)
+                    })
+                    .collect();
+
+                impls.sort_unstable();
+                let mut hasher = StableHasher::new();
+                impls.hash_stable(&mut self.hcx, &mut hasher);
+                (trait_id, hasher.finish())
+            })
+            .collect();
+
+        impls.sort_unstable();
+
+        let mut default_impls: AccumulateVec<[_; 32]> = krate
+            .trait_default_impl
+            .iter()
+            .map(|(&trait_def_id, &impl_node_id)| {
+                let impl_def_id = tcx.hir.local_def_id(impl_node_id);
+                (tcx.def_path_hash(trait_def_id), tcx.def_path_hash(impl_def_id))
+            })
+            .collect();
+
+        default_impls.sort_unstable();
+
+        let mut hasher = StableHasher::new();
+        impls.hash_stable(&mut self.hcx, &mut hasher);
+
+        self.hashes.insert(DepNode::AllLocalTraitImpls, hasher.finish());
+    }
 }
 
 impl<'a, 'tcx: 'a> ItemLikeVisitor<'tcx> for ComputeItemHashesVisitor<'a, 'tcx> {
@@ -235,6 +284,8 @@ impl<'a, 'tcx: 'a> ItemLikeVisitor<'tcx> for ComputeItemHashesVisitor<'a, 'tcx>
     }
 }
 
+
+
 pub fn compute_incremental_hashes_map<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
                                                     -> IncrementalHashesMap {
     let _ignore = tcx.dep_graph.in_ignore();
@@ -272,6 +323,8 @@ pub fn compute_incremental_hashes_map<'a, 'tcx: 'a>(tcx: TyCtxt<'a, 'tcx, 'tcx>)
             let fingerprint = hasher.finish();
             visitor.hashes.insert(dep_node, fingerprint);
         }
+
+        visitor.compute_and_store_ich_for_trait_impls(krate);
     });
 
     tcx.sess.perf_stats.incr_comp_hashes_count.set(visitor.hashes.len() as u64);
diff --git a/src/librustc_metadata/creader.rs b/src/librustc_metadata/creader.rs
index d2874f16289..54f09a0f319 100644
--- a/src/librustc_metadata/creader.rs
+++ b/src/librustc_metadata/creader.rs
@@ -315,11 +315,20 @@ impl<'a> CrateLoader<'a> {
         let exported_symbols = crate_root.exported_symbols
                                          .map(|x| x.decode(&metadata).collect());
 
+        let trait_impls = crate_root
+            .impls
+            .map(|impls| {
+                impls.decode(&metadata)
+                     .map(|trait_impls| (trait_impls.trait_id, trait_impls.impls))
+                     .collect()
+            });
+
         let mut cmeta = cstore::CrateMetadata {
             name: name,
             extern_crate: Cell::new(None),
             def_path_table: def_path_table,
             exported_symbols: exported_symbols,
+            trait_impls: trait_impls,
             proc_macros: crate_root.macro_derive_registrar.map(|_| {
                 self.load_derive_macros(&crate_root, dylib.clone().map(|p| p.0), span)
             }),
diff --git a/src/librustc_metadata/cstore.rs b/src/librustc_metadata/cstore.rs
index c12b4209675..4e70387c8b0 100644
--- a/src/librustc_metadata/cstore.rs
+++ b/src/librustc_metadata/cstore.rs
@@ -85,6 +85,8 @@ pub struct CrateMetadata {
 
     pub exported_symbols: Tracked<FxHashSet<DefIndex>>,
 
+    pub trait_impls: Tracked<FxHashMap<(u32, DefIndex), schema::LazySeq<DefIndex>>>,
+
     pub dep_kind: Cell<DepKind>,
     pub source: CrateSource,
 
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index dbf3e94832f..d42aab60c6e 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -147,10 +147,8 @@ impl CrateStore for cstore::CStore {
 
     fn implementations_of_trait(&self, filter: Option<DefId>) -> Vec<DefId>
     {
-        if let Some(def_id) = filter {
-            self.dep_graph.read(DepNode::MetaData(def_id));
-        }
         let mut result = vec![];
+
         self.iter_crate_data(|_, cdata| {
             cdata.get_implementations_for_trait(filter, &self.dep_graph, &mut result)
         });
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 819095e2628..51822474254 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -961,17 +961,17 @@ impl<'a, 'tcx> CrateMetadata {
             None => None,
         };
 
-        // FIXME(eddyb) Make this O(1) instead of O(n).
         let dep_node = self.metadata_dep_node(GlobalMetaDataKind::Impls);
-        for trait_impls in self.root.impls.get(dep_graph, dep_node).decode(self) {
-            if filter.is_some() && filter != Some(trait_impls.trait_id) {
-                continue;
-            }
-
-            result.extend(trait_impls.impls.decode(self).map(|index| self.local_def_id(index)));
 
-            if filter.is_some() {
-                break;
+        if let Some(filter) = filter {
+            if let Some(impls) = self.trait_impls
+                                     .get(dep_graph, dep_node)
+                                     .get(&filter) {
+                result.extend(impls.decode(self).map(|idx| self.local_def_id(idx)));
+            }
+        } else {
+            for impls in self.trait_impls.get(dep_graph, dep_node).values() {
+                result.extend(impls.decode(self).map(|idx| self.local_def_id(idx)));
             }
         }
     }
diff --git a/src/librustc_metadata/schema.rs b/src/librustc_metadata/schema.rs
index 5abe1adfb6f..91a22d92219 100644
--- a/src/librustc_metadata/schema.rs
+++ b/src/librustc_metadata/schema.rs
@@ -221,6 +221,20 @@ impl<T> Tracked<T> {
     }
 }
 
+impl<'a, 'tcx, T> HashStable<StableHashingContext<'a, 'tcx>> for Tracked<T>
+    where T: HashStable<StableHashingContext<'a, 'tcx>>
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a, 'tcx>,
+                                          hasher: &mut StableHasher<W>) {
+        let Tracked {
+            ref state
+        } = *self;
+
+        state.hash_stable(hcx, hasher);
+    }
+}
+
 
 #[derive(RustcEncodable, RustcDecodable)]
 pub struct CrateRoot {