Rollup merge of #40878 - michaelwoerister:dmh, r=nikomatsakis

Introduce HashStable trait and base ICH implementations on it.

This PR introduces the `HashStable` trait which marks that a type can be hashed in a way that is stable across multiple compilation sessions. The PR also moves HIR incr. comp. hashing over to implementations of this trait instead of doing this via a HIR visitor. It also provides many `HashStable` implementations that are not used yet (e.g. for MIR types) but soon will be used when we directly hash crate metadata for incr. comp.

I've only done superficial performance measurements but it looks like the new implementation is a bit faster than the current one (due, I suppose, to some bugs I fixed and some unnecessary inefficiencies I removed). Here is the time in seconds for the `compute_incremental_hashes_map` pass for various crates:

|                 |  OLD  |  NEW  |
|:---------------:|:-----:|:-----:|
| libcore         | 0.507 | 0.409 |
| libsyntax       | 0.320 | 0.260 |
| librustc        | 0.730 | 0.611 |
| librustc_driver | 0.024 | 0.015 |

Some notes regarding the implementation:
* Most `HashStable` implementations are provided via the `impl_hash_stable_for!` macro (as suggested by @nikomatsakis). This works out quite well. A custom_derive would have been better but Macros 1.1 are not available in the compiler.
* The trait implementation take care to exhaustively destructure everything they hash so that fields added in the future don't fall through the cracks. This is a bit verbose but I think it's well worth the trouble since we've had quite a few issues with missing fields or visitor callbacks in this area in the past. Most of it is behind the macro anyway.

cc @rust-lang/compiler
r? @nikomatsakis

2 files changed, 193 insertions, 1 deletions

diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 9ccd95dd8d8..c1735b4a4ec 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -37,6 +37,8 @@
 #![feature(unsize)]
 #![feature(i128_type)]
 #![feature(conservative_impl_trait)]
+#![feature(discriminant_value)]
+#![feature(specialization)]
 
 #![cfg_attr(unix, feature(libc))]
 #![cfg_attr(test, feature(test))]
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 231c01c9ab7..dc412a0763e 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use std::hash::Hasher;
+use std::hash::{Hash, Hasher};
 use std::marker::PhantomData;
 use std::mem;
 use blake2b::Blake2bHasher;
@@ -174,3 +174,193 @@ impl<W> Hasher for StableHasher<W> {
         self.write_ileb128(i as i64);
     }
 }
+
+
+/// Something that implements `HashStable<CTX>` can be hashed in a way that is
+/// stable across multiple compiliation sessions.
+pub trait HashStable<CTX> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>);
+}
+
+// Implement HashStable by just calling `Hash::hash()`. This works fine for
+// self-contained values that don't depend on the hashing context `CTX`.
+macro_rules! impl_stable_hash_via_hash {
+    ($t:ty) => (
+        impl<CTX> HashStable<CTX> for $t {
+            #[inline]
+            fn hash_stable<W: StableHasherResult>(&self,
+                                                  _: &mut CTX,
+                                                  hasher: &mut StableHasher<W>) {
+                ::std::hash::Hash::hash(self, hasher);
+            }
+        }
+    );
+}
+
+impl_stable_hash_via_hash!(i8);
+impl_stable_hash_via_hash!(i16);
+impl_stable_hash_via_hash!(i32);
+impl_stable_hash_via_hash!(i64);
+impl_stable_hash_via_hash!(isize);
+
+impl_stable_hash_via_hash!(u8);
+impl_stable_hash_via_hash!(u16);
+impl_stable_hash_via_hash!(u32);
+impl_stable_hash_via_hash!(u64);
+impl_stable_hash_via_hash!(usize);
+
+impl_stable_hash_via_hash!(u128);
+impl_stable_hash_via_hash!(i128);
+
+impl_stable_hash_via_hash!(char);
+impl_stable_hash_via_hash!(());
+
+impl<CTX> HashStable<CTX> for f32 {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        let val: u32 = unsafe {
+            ::std::mem::transmute(*self)
+        };
+        val.hash_stable(ctx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for f64 {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        let val: u64 = unsafe {
+            ::std::mem::transmute(*self)
+        };
+        val.hash_stable(ctx, hasher);
+    }
+}
+
+impl<T1: HashStable<CTX>, T2: HashStable<CTX>, CTX> HashStable<CTX> for (T1, T2) {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.0.hash_stable(ctx, hasher);
+        self.1.hash_stable(ctx, hasher);
+    }
+}
+
+impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
+    default fn hash_stable<W: StableHasherResult>(&self,
+                                                  ctx: &mut CTX,
+                                                  hasher: &mut StableHasher<W>) {
+        self.len().hash_stable(ctx, hasher);
+        for item in self {
+            item.hash_stable(ctx, hasher);
+        }
+    }
+}
+
+impl<T: HashStable<CTX>, CTX> HashStable<CTX> for Vec<T> {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        (&self[..]).hash_stable(ctx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for str {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          _: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.len().hash(hasher);
+        self.as_bytes().hash(hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for bool {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        (if *self { 1u8 } else { 0u8 }).hash_stable(ctx, hasher);
+    }
+}
+
+
+impl<T, CTX> HashStable<CTX> for Option<T>
+    where T: HashStable<CTX>
+{
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        if let Some(ref value) = *self {
+            1u8.hash_stable(ctx, hasher);
+            value.hash_stable(ctx, hasher);
+        } else {
+            0u8.hash_stable(ctx, hasher);
+        }
+    }
+}
+
+impl<'a, T, CTX> HashStable<CTX> for &'a T
+    where T: HashStable<CTX>
+{
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        (**self).hash_stable(ctx, hasher);
+    }
+}
+
+impl<T, CTX> HashStable<CTX> for ::std::mem::Discriminant<T> {
+    #[inline]
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          _: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        ::std::hash::Hash::hash(self, hasher);
+    }
+}
+
+impl<K, V, CTX> HashStable<CTX> for ::std::collections::BTreeMap<K, V>
+    where K: Ord + HashStable<CTX>,
+          V: HashStable<CTX>,
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.len().hash_stable(ctx, hasher);
+        for (k, v) in self {
+            k.hash_stable(ctx, hasher);
+            v.hash_stable(ctx, hasher);
+        }
+    }
+}
+
+impl<T, CTX> HashStable<CTX> for ::std::collections::BTreeSet<T>
+    where T: Ord + HashStable<CTX>,
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.len().hash_stable(ctx, hasher);
+        for v in self {
+            v.hash_stable(ctx, hasher);
+        }
+    }
+}
+
+impl<I: ::indexed_vec::Idx, T, CTX> HashStable<CTX> for ::indexed_vec::IndexVec<I, T>
+    where T: HashStable<CTX>,
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        self.len().hash_stable(ctx, hasher);
+        for v in &self.raw {
+            v.hash_stable(ctx, hasher);
+        }
+    }
+}