Let a portion of DefPathHash uniquely identify the DefPath's crate.

This allows to directly map from a DefPathHash to the crate it
originates from, without constructing side tables to do that mapping.

It also allows to reliably and cheaply check for DefPathHash collisions.

3 files changed, 118 insertions, 0 deletions

diff --git a/compiler/rustc_span/src/crate_disambiguator.rs b/compiler/rustc_span/src/crate_disambiguator.rs
new file mode 100644
index 00000000000..bd7d8516714
--- /dev/null
+++ b/compiler/rustc_span/src/crate_disambiguator.rs
@@ -0,0 +1,35 @@
+// This is here because `rustc_session` wants to refer to it,
+// and so does `rustc_hir`, but `rustc_hir` shouldn't refer to `rustc_session`.
+
+use rustc_data_structures::fingerprint::Fingerprint;
+use rustc_data_structures::{base_n, impl_stable_hash_via_hash};
+
+use std::fmt;
+
+/// Hash value constructed out of all the `-C metadata` arguments passed to the
+/// compiler. Together with the crate-name forms a unique global identifier for
+/// the crate.
+#[derive(Eq, PartialEq, Ord, PartialOrd, Hash, Debug, Clone, Copy, Encodable, Decodable)]
+pub struct CrateDisambiguator(Fingerprint);
+
+impl CrateDisambiguator {
+    pub fn to_fingerprint(self) -> Fingerprint {
+        self.0
+    }
+}
+
+impl fmt::Display for CrateDisambiguator {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
+        let (a, b) = self.0.as_value();
+        let as_u128 = a as u128 | ((b as u128) << 64);
+        f.write_str(&base_n::encode(as_u128, base_n::CASE_INSENSITIVE))
+    }
+}
+
+impl From<Fingerprint> for CrateDisambiguator {
+    fn from(fingerprint: Fingerprint) -> CrateDisambiguator {
+        CrateDisambiguator(fingerprint)
+    }
+}
+
+impl_stable_hash_via_hash!(CrateDisambiguator);
diff --git a/compiler/rustc_span/src/def_id.rs b/compiler/rustc_span/src/def_id.rs
index b24ede9c53a..7c02056105e 100644
--- a/compiler/rustc_span/src/def_id.rs
+++ b/compiler/rustc_span/src/def_id.rs
@@ -1,3 +1,4 @@
+use crate::crate_disambiguator::CrateDisambiguator;
 use crate::HashStableContext;
 use rustc_data_structures::fingerprint::Fingerprint;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
@@ -105,10 +106,66 @@ impl ::std::fmt::Debug for CrateNum {
     }
 }
 
+/// A `DefPathHash` is a fixed-size representation of a `DefPath` that is
+/// stable across crate and compilation session boundaries. It consists of two
+/// separate 64-bit hashes. The first uniquely identifies the crate this
+/// `DefPathHash` originates from (see [StableCrateId]), and the second
+/// uniquely identifies the corresponding `DefPath` within that crate. Together
+/// they form a unique identifier within an entire crate graph.
+///
+/// There is a very small chance of hash collisions, which would mean that two
+/// different `DefPath`s map to the same `DefPathHash`. Proceeding compilation
+/// with such a hash collision would very probably lead to an ICE, and in the
+/// worst case lead to a silent mis-compilation. The compiler therefore actively
+/// and exhaustively checks for such hash collisions and aborts compilation if
+/// it finds one.
+///
+/// `DefPathHash` uses 64-bit hashes for both the crate-id part and the
+/// crate-internal part, even though it is likely that there are many more
+/// `LocalDefId`s in a single crate than there are individual crates in a crate
+/// graph. Since we use the same number of bits in both cases, the collision
+/// probability for the crate-local part will be quite a bit higher (though
+/// still very small).
+///
+/// This imbalance is not by accident: A hash collision in the
+/// crate-local part of a `DefPathHash` will be detected and reported while
+/// compiling the crate in question. Such a collision does not depend on
+/// outside factors and can be easily fixed by the crate maintainer (e.g. by
+/// renaming the item in question or by bumping the crate version in a harmless
+/// way).
+///
+/// A collision between crate-id hashes on the other hand is harder to fix
+/// because it depends on the set of crates in the entire crate graph of a
+/// compilation session. Again, using the same crate with a different version
+/// number would fix the issue with a high probability -- but that might be
+/// easier said then done if the crates in questions are dependencies of
+/// third-party crates.
+///
+/// That being said, given a high quality hash function, the collision
+/// probabilities in question are very small. For example, for a big crate like
+/// `rustc_middle` (with ~50000 `LocalDefId`s as of the time of writing) there
+/// is a probability of roughly 1 in 14,750,000,000 of a crate-internal
+/// collision occurring. For a big crate graph with 1000 crates in it, there is
+/// a probability of 1 in 36,890,000,000,000 of a `StableCrateId` collision.
 #[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)]
 #[derive(HashStable_Generic, Encodable, Decodable)]
 pub struct DefPathHash(pub Fingerprint);
 
+impl DefPathHash {
+    /// Returns the [StableCrateId] identifying the crate this [DefPathHash]
+    /// originates from.
+    #[inline]
+    pub fn stable_crate_id(&self) -> StableCrateId {
+        StableCrateId(self.0.as_value().0)
+    }
+
+    /// Builds a new [DefPathHash] with the given [StableCrateId] and
+    /// `local_hash`, where `local_hash` must be unique within its crate.
+    pub fn new(stable_crate_id: StableCrateId, local_hash: u64) -> DefPathHash {
+        DefPathHash(Fingerprint::new(stable_crate_id.0, local_hash))
+    }
+}
+
 impl Borrow<Fingerprint> for DefPathHash {
     #[inline]
     fn borrow(&self) -> &Fingerprint {
@@ -116,6 +173,30 @@ impl Borrow<Fingerprint> for DefPathHash {
     }
 }
 
+/// A [StableCrateId] is a 64 bit hash of `(crate-name, crate-disambiguator)`. It
+/// is to [CrateNum] what [DefPathHash] is to [DefId]. It is stable across
+/// compilation sessions.
+///
+/// Since the ID is a hash value there is a (very small) chance that two crates
+/// end up with the same [StableCrateId]. The compiler will check for such
+/// collisions when loading crates and abort compilation in order to avoid
+/// further trouble.
+#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord, Debug, Encodable, Decodable)]
+pub struct StableCrateId(u64);
+
+impl StableCrateId {
+    /// Computes the stable ID for a crate with the given name and
+    /// disambiguator.
+    pub fn new(crate_name: &str, crate_disambiguator: CrateDisambiguator) -> StableCrateId {
+        use std::hash::Hash;
+
+        let mut hasher = StableHasher::new();
+        crate_name.hash(&mut hasher);
+        crate_disambiguator.hash(&mut hasher);
+        StableCrateId(hasher.finish())
+    }
+}
+
 rustc_index::newtype_index! {
     /// A DefIndex is an index into the hir-map for a crate, identifying a
     /// particular definition. It should really be considered an interned
diff --git a/compiler/rustc_span/src/lib.rs b/compiler/rustc_span/src/lib.rs
index f3d876a5770..0f14154047d 100644
--- a/compiler/rustc_span/src/lib.rs
+++ b/compiler/rustc_span/src/lib.rs
@@ -47,6 +47,8 @@ pub mod lev_distance;
 mod span_encoding;
 pub use span_encoding::{Span, DUMMY_SP};
 
+pub mod crate_disambiguator;
+
 pub mod symbol;
 pub use symbol::{sym, Symbol};