Rollup merge of #42082 - michaelwoerister:wider_def_path_hashes, r=eddyb

incr. comp.: Use more bits for DefPath hashes

Use 128 instead of 64 bits for DefPath hashes, like we do for everything else. Collision probability is unnecessarily high with 64 bits.

Also change the representation of `ich::Fingerprint` from `Fingerprint([u8; 16])` to `Fingerprint(u64, u64)` which is better for hashers like `FxHasher`.

10 files changed, 51 insertions, 66 deletions

diff --git a/src/librustc/hir/map/definitions.rs b/src/librustc/hir/map/definitions.rs
index 6118df2ddfc..9537b40b28a 100644
--- a/src/librustc/hir/map/definitions.rs
+++ b/src/librustc/hir/map/definitions.rs
@@ -16,6 +16,7 @@
 
 use hir;
 use hir::def_id::{CrateNum, DefId, DefIndex, LOCAL_CRATE, DefIndexAddressSpace};
+use ich::Fingerprint;
 use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_data_structures::stable_hasher::StableHasher;
@@ -34,7 +35,7 @@ use util::nodemap::NodeMap;
 pub struct DefPathTable {
     index_to_key: [Vec<DefKey>; 2],
     key_to_index: FxHashMap<DefKey, DefIndex>,
-    def_path_hashes: [Vec<u64>; 2],
+    def_path_hashes: [Vec<Fingerprint>; 2],
 }
 
 // Unfortunately we have to provide a manual impl of Clone because of the
@@ -55,7 +56,7 @@ impl DefPathTable {
 
     fn allocate(&mut self,
                 key: DefKey,
-                def_path_hash: u64,
+                def_path_hash: Fingerprint,
                 address_space: DefIndexAddressSpace)
                 -> DefIndex {
         let index = {
@@ -79,7 +80,7 @@ impl DefPathTable {
     }
 
     #[inline(always)]
-    pub fn def_path_hash(&self, index: DefIndex) -> u64 {
+    pub fn def_path_hash(&self, index: DefIndex) -> Fingerprint {
         self.def_path_hashes[index.address_space().index()]
                             [index.as_array_index()]
     }
@@ -146,8 +147,8 @@ impl Decodable for DefPathTable {
         let index_to_key_lo: Vec<DefKey> = Decodable::decode(d)?;
         let index_to_key_hi: Vec<DefKey> = Decodable::decode(d)?;
 
-        let def_path_hashes_lo: Vec<u64> = Decodable::decode(d)?;
-        let def_path_hashes_hi: Vec<u64> = Decodable::decode(d)?;
+        let def_path_hashes_lo: Vec<Fingerprint> = Decodable::decode(d)?;
+        let def_path_hashes_hi: Vec<Fingerprint> = Decodable::decode(d)?;
 
         let index_to_key = [index_to_key_lo, index_to_key_hi];
         let def_path_hashes = [def_path_hashes_lo, def_path_hashes_hi];
@@ -210,7 +211,7 @@ pub struct DefKey {
 }
 
 impl DefKey {
-    fn compute_stable_hash(&self, parent_hash: u64) -> u64 {
+    fn compute_stable_hash(&self, parent_hash: Fingerprint) -> Fingerprint {
         let mut hasher = StableHasher::new();
 
         // We hash a 0u8 here to disambiguate between regular DefPath hashes,
@@ -221,7 +222,7 @@ impl DefKey {
         hasher.finish()
     }
 
-    fn root_parent_stable_hash(crate_name: &str, crate_disambiguator: &str) -> u64 {
+    fn root_parent_stable_hash(crate_name: &str, crate_disambiguator: &str) -> Fingerprint {
         let mut hasher = StableHasher::new();
         // Disambiguate this from a regular DefPath hash,
         // see compute_stable_hash() above.
@@ -396,7 +397,7 @@ impl Definitions {
     }
 
     #[inline(always)]
-    pub fn def_path_hash(&self, index: DefIndex) -> u64 {
+    pub fn def_path_hash(&self, index: DefIndex) -> Fingerprint {
         self.table.def_path_hash(index)
     }
 
diff --git a/src/librustc/ich/fingerprint.rs b/src/librustc/ich/fingerprint.rs
index ccdbab88b8b..a947f6aeff7 100644
--- a/src/librustc/ich/fingerprint.rs
+++ b/src/librustc/ich/fingerprint.rs
@@ -10,95 +10,75 @@
 
 use rustc_serialize::{Encodable, Decodable, Encoder, Decoder};
 use rustc_data_structures::stable_hasher;
-use rustc_data_structures::ToHex;
-
-const FINGERPRINT_LENGTH: usize = 16;
+use std::mem;
+use std::slice;
 
 #[derive(Eq, PartialEq, Ord, PartialOrd, Hash, Debug, Clone, Copy)]
-pub struct Fingerprint(pub [u8; FINGERPRINT_LENGTH]);
+pub struct Fingerprint(u64, u64);
 
 impl Fingerprint {
     #[inline]
     pub fn zero() -> Fingerprint {
-        Fingerprint([0; FINGERPRINT_LENGTH])
+        Fingerprint(0, 0)
     }
 
+    #[inline]
     pub fn from_smaller_hash(hash: u64) -> Fingerprint {
-        let mut result = Fingerprint::zero();
-        result.0[0] = (hash >>  0) as u8;
-        result.0[1] = (hash >>  8) as u8;
-        result.0[2] = (hash >> 16) as u8;
-        result.0[3] = (hash >> 24) as u8;
-        result.0[4] = (hash >> 32) as u8;
-        result.0[5] = (hash >> 40) as u8;
-        result.0[6] = (hash >> 48) as u8;
-        result.0[7] = (hash >> 56) as u8;
-        result
+        Fingerprint(hash, hash)
     }
 
+    #[inline]
     pub fn to_smaller_hash(&self) -> u64 {
-        ((self.0[0] as u64) <<  0) |
-        ((self.0[1] as u64) <<  8) |
-        ((self.0[2] as u64) << 16) |
-        ((self.0[3] as u64) << 24) |
-        ((self.0[4] as u64) << 32) |
-        ((self.0[5] as u64) << 40) |
-        ((self.0[6] as u64) << 48) |
-        ((self.0[7] as u64) << 56)
+        self.0
     }
 
     pub fn to_hex(&self) -> String {
-        self.0.to_hex()
+        format!("{:x}{:x}", self.0, self.1)
     }
 }
 
 impl Encodable for Fingerprint {
     #[inline]
     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
-        for &byte in &self.0 {
-            s.emit_u8(byte)?;
-        }
-        Ok(())
+        s.emit_u64(self.0.to_le())?;
+        s.emit_u64(self.1.to_le())
     }
 }
 
 impl Decodable for Fingerprint {
     #[inline]
     fn decode<D: Decoder>(d: &mut D) -> Result<Fingerprint, D::Error> {
-        let mut result = Fingerprint([0u8; FINGERPRINT_LENGTH]);
-        for byte in &mut result.0 {
-            *byte = d.read_u8()?;
-        }
-        Ok(result)
+        let _0 = u64::from_le(d.read_u64()?);
+        let _1 = u64::from_le(d.read_u64()?);
+        Ok(Fingerprint(_0, _1))
     }
 }
 
 impl ::std::fmt::Display for Fingerprint {
     fn fmt(&self, formatter: &mut ::std::fmt::Formatter) -> Result<(), ::std::fmt::Error> {
-        for i in 0 .. self.0.len() {
-            if i > 0 {
-                write!(formatter, "::")?;
-            }
-
-            write!(formatter, "{}", self.0[i])?;
-        }
-        Ok(())
+        write!(formatter, "{:x}-{:x}", self.0, self.1)
     }
 }
 
-
 impl stable_hasher::StableHasherResult for Fingerprint {
     fn finish(mut hasher: stable_hasher::StableHasher<Self>) -> Self {
-        let mut fingerprint = Fingerprint::zero();
-        fingerprint.0.copy_from_slice(hasher.finalize());
-        fingerprint
+        let hash_bytes: &[u8] = hasher.finalize();
+
+        assert!(hash_bytes.len() >= mem::size_of::<u64>() * 2);
+        let hash_bytes: &[u64] = unsafe {
+            slice::from_raw_parts(hash_bytes.as_ptr() as *const u64, 2)
+        };
+
+        // The bytes returned bytes the Blake2B hasher are always little-endian.
+        Fingerprint(u64::from_le(hash_bytes[0]), u64::from_le(hash_bytes[1]))
     }
 }
 
 impl<CTX> stable_hasher::HashStable<CTX> for Fingerprint {
+    #[inline]
     fn hash_stable<W: stable_hasher::StableHasherResult>(&self,
                                           _: &mut CTX,
                                           hasher: &mut stable_hasher::StableHasher<W>) {
-        ::std::hash::Hash::hash(&self.0, hasher);
+        ::std::hash::Hash::hash(self, hasher);
     }
 }
diff --git a/src/librustc/ich/hcx.rs b/src/librustc/ich/hcx.rs
index 786d1c5035d..f25ec8ecd4d 100644
--- a/src/librustc/ich/hcx.rs
+++ b/src/librustc/ich/hcx.rs
@@ -110,7 +110,7 @@ impl<'a, 'tcx: 'a> StableHashingContext<'a, 'tcx> {
     }
 
     #[inline]
-    pub fn def_path_hash(&mut self, def_id: DefId) -> u64 {
+    pub fn def_path_hash(&mut self, def_id: DefId) -> ich::Fingerprint {
         self.tcx.def_path_hash(def_id)
     }
 
diff --git a/src/librustc/middle/cstore.rs b/src/librustc/middle/cstore.rs
index a68aca46000..8ad1db78595 100644
--- a/src/librustc/middle/cstore.rs
+++ b/src/librustc/middle/cstore.rs
@@ -282,7 +282,7 @@ pub trait CrateStore {
                     -> Option<DefId>;
     fn def_key(&self, def: DefId) -> DefKey;
     fn def_path(&self, def: DefId) -> hir_map::DefPath;
-    fn def_path_hash(&self, def: DefId) -> u64;
+    fn def_path_hash(&self, def: DefId) -> ich::Fingerprint;
     fn struct_field_names(&self, def: DefId) -> Vec<ast::Name>;
     fn item_children(&self, did: DefId) -> Vec<def::Export>;
     fn load_macro(&self, did: DefId, sess: &Session) -> LoadedMacro;
@@ -414,7 +414,7 @@ impl CrateStore for DummyCrateStore {
     fn def_path(&self, def: DefId) -> hir_map::DefPath {
         bug!("relative_def_path")
     }
-    fn def_path_hash(&self, def: DefId) -> u64 {
+    fn def_path_hash(&self, def: DefId) -> ich::Fingerprint {
         bug!("wa")
     }
     fn struct_field_names(&self, def: DefId) -> Vec<ast::Name> { bug!("struct_field_names") }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index a86d7351ef4..359722ce96e 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -19,7 +19,7 @@ use dep_graph::DepNode;
 use hir::{map as hir_map, FreevarMap, TraitMap};
 use hir::def::{Def, CtorKind, ExportMap};
 use hir::def_id::{CrateNum, DefId, DefIndex, CRATE_DEF_INDEX, LOCAL_CRATE};
-use ich::StableHashingContext;
+use ich::{self, StableHashingContext};
 use middle::const_val::ConstVal;
 use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem};
 use middle::privacy::AccessLevels;
@@ -2248,7 +2248,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     }
 
     #[inline]
-    pub fn def_path_hash(self, def_id: DefId) -> u64 {
+    pub fn def_path_hash(self, def_id: DefId) -> ich::Fingerprint {
         if def_id.is_local() {
             self.hir.definitions().def_path_hash(def_id.index)
         } else {
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index cfbf1244db3..348d164af41 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -29,6 +29,7 @@ use util::nodemap::FxHashMap;
 use serialize;
 
 use hir;
+use ich;
 
 use self::InferTy::*;
 use self::TypeVariants::*;
@@ -849,7 +850,7 @@ impl<'a, 'tcx, 'gcx> ExistentialProjection<'tcx> {
         self.item_name // safe to skip the binder to access a name
     }
 
-    pub fn sort_key(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> (u64, InternedString) {
+    pub fn sort_key(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> (ich::Fingerprint, InternedString) {
         // We want something here that is stable across crate boundaries.
         // The DefId isn't but the `deterministic_hash` of the corresponding
         // DefPath is.
@@ -884,7 +885,7 @@ impl<'a, 'tcx, 'gcx> PolyExistentialProjection<'tcx> {
         self.skip_binder().item_name()
     }
 
-    pub fn sort_key(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> (u64, InternedString) {
+    pub fn sort_key(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> (ich::Fingerprint, InternedString) {
         self.skip_binder().sort_key(tcx)
     }
 
diff --git a/src/librustc/ty/trait_def.rs b/src/librustc/ty/trait_def.rs
index 865297c7ecb..86774136bd6 100644
--- a/src/librustc/ty/trait_def.rs
+++ b/src/librustc/ty/trait_def.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 use hir::def_id::DefId;
+use ich::Fingerprint;
 use traits::specialization_graph;
 use ty::fast_reject;
 use ty::fold::TypeFoldable;
@@ -32,7 +33,7 @@ pub struct TraitDef {
 
     /// The ICH of this trait's DefPath, cached here so it doesn't have to be
     /// recomputed all the time.
-    pub def_path_hash: u64,
+    pub def_path_hash: Fingerprint,
 }
 
 // We don't store the list of impls in a flat list because each cached list of
@@ -94,7 +95,7 @@ impl<'a, 'gcx, 'tcx> TraitDef {
                unsafety: hir::Unsafety,
                paren_sugar: bool,
                has_default_impl: bool,
-               def_path_hash: u64)
+               def_path_hash: Fingerprint)
                -> TraitDef {
         TraitDef {
             def_id,
diff --git a/src/librustc_incremental/calculate_svh/mod.rs b/src/librustc_incremental/calculate_svh/mod.rs
index 8cdabc1d894..c9ed9ad3c7d 100644
--- a/src/librustc_incremental/calculate_svh/mod.rs
+++ b/src/librustc_incremental/calculate_svh/mod.rs
@@ -224,7 +224,7 @@ impl<'a, 'tcx: 'a> ComputeItemHashesVisitor<'a, 'tcx> {
     {
         let tcx = self.hcx.tcx();
 
-        let mut impls: Vec<(u64, Fingerprint)> = krate
+        let mut impls: Vec<(Fingerprint, Fingerprint)> = krate
             .trait_impls
             .iter()
             .map(|(&trait_id, impls)| {
diff --git a/src/librustc_metadata/cstore_impl.rs b/src/librustc_metadata/cstore_impl.rs
index 4b7083590d2..7478f902e06 100644
--- a/src/librustc_metadata/cstore_impl.rs
+++ b/src/librustc_metadata/cstore_impl.rs
@@ -17,6 +17,7 @@ use rustc::middle::cstore::{CrateStore, CrateSource, LibSource, DepKind,
                             ExternCrate, NativeLibrary, MetadataLoader, LinkMeta,
                             LinkagePreference, LoadedMacro, EncodedMetadata};
 use rustc::hir::def;
+use rustc::ich;
 use rustc::middle::lang_items;
 use rustc::session::Session;
 use rustc::ty::{self, TyCtxt};
@@ -337,7 +338,7 @@ impl CrateStore for cstore::CStore {
         self.get_crate_data(def.krate).def_path(def.index)
     }
 
-    fn def_path_hash(&self, def: DefId) -> u64 {
+    fn def_path_hash(&self, def: DefId) -> ich::Fingerprint {
         self.get_crate_data(def.krate).def_path_hash(def.index)
     }
 
diff --git a/src/librustc_metadata/decoder.rs b/src/librustc_metadata/decoder.rs
index 754f27810c4..d8826d87d4d 100644
--- a/src/librustc_metadata/decoder.rs
+++ b/src/librustc_metadata/decoder.rs
@@ -16,6 +16,7 @@ use schema::*;
 use rustc::dep_graph::{DepGraph, DepNode, GlobalMetaDataKind};
 use rustc::hir::map::{DefKey, DefPath, DefPathData};
 use rustc::hir;
+use rustc::ich;
 
 use rustc::middle::cstore::LinkagePreference;
 use rustc::hir::def::{self, Def, CtorKind};
@@ -1106,7 +1107,7 @@ impl<'a, 'tcx> CrateMetadata {
     }
 
     #[inline]
-    pub fn def_path_hash(&self, index: DefIndex) -> u64 {
+    pub fn def_path_hash(&self, index: DefIndex) -> ich::Fingerprint {
         self.def_path_table.def_path_hash(index)
     }