Rollup merge of #41141 - michaelwoerister:direct-metadata-ich-final, r=nikomatsakis

ICH: Replace old, transitive metadata hashing with direct hashing approach.

This PR replaces the old crate metadata hashing strategy with a new one that directly (but stably) hashes all values we encode into the metadata. Previously we would track what data got accessed during metadata encoding and then hash the input nodes (HIR and upstream metadata) that were transitively reachable from the accessed data. While this strategy was sound, it had two major downsides:

1. It was susceptible to generating false positives, i.e. some input node might have changed without actually affecting the content of the metadata. That metadata entry would still show up as changed.
2. It was susceptible to quadratic blow-up when many metadata nodes shared the same input nodes, which would then get hashed over and over again.

The new method does not have these disadvantages and it's also a first step towards caching more intermediate results in the compiler.

Metadata hashing/cross-crate incremental compilation is still kept behind the `-Zincremental-cc` flag even after this PR. Once the new method has proven itself with more tests, we can remove the flag and enable cross-crate support by default again.

r? @nikomatsakis
cc @rust-lang/compiler

5 files changed, 86 insertions, 8 deletions

diff --git a/src/librustc_data_structures/array_vec.rs b/src/librustc_data_structures/array_vec.rs
index adb22197226..848e5a076bb 100644
--- a/src/librustc_data_structures/array_vec.rs
+++ b/src/librustc_data_structures/array_vec.rs
@@ -40,6 +40,12 @@ unsafe impl<T> Array for [T; 8] {
     const LEN: usize = 8;
 }
 
+unsafe impl<T> Array for [T; 32] {
+    type Element = T;
+    type PartialStorage = [ManuallyDrop<T>; 32];
+    const LEN: usize = 32;
+}
+
 pub struct ArrayVec<A: Array> {
     count: usize,
     values: A::PartialStorage
diff --git a/src/librustc_data_structures/blake2b.rs b/src/librustc_data_structures/blake2b.rs
index 9d97a83f693..bdef9fefd41 100644
--- a/src/librustc_data_structures/blake2b.rs
+++ b/src/librustc_data_structures/blake2b.rs
@@ -29,16 +29,23 @@ pub struct Blake2bCtx {
     t: [u64; 2],
     c: usize,
     outlen: u16,
-    finalized: bool
+    finalized: bool,
+
+    #[cfg(debug_assertions)]
+    fnv_hash: u64,
 }
 
+#[cfg(debug_assertions)]
 impl ::std::fmt::Debug for Blake2bCtx {
-    fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> Result<(), ::std::fmt::Error> {
-        try!(write!(fmt, "hash: "));
-        for v in &self.h {
-            try!(write!(fmt, "{:x}", v));
-        }
-        Ok(())
+    fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
+        write!(fmt, "{:x}", self.fnv_hash)
+    }
+}
+
+#[cfg(not(debug_assertions))]
+impl ::std::fmt::Debug for Blake2bCtx {
+    fn fmt(&self, fmt: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
+        write!(fmt, "Enable debug_assertions() for more info.")
     }
 }
 
@@ -157,6 +164,9 @@ fn blake2b_new(outlen: usize, key: &[u8]) -> Blake2bCtx {
         c: 0,
         outlen: outlen as u16,
         finalized: false,
+
+        #[cfg(debug_assertions)]
+        fnv_hash: 0xcbf29ce484222325,
     };
 
     ctx.h[0] ^= 0x01010000 ^ ((key.len() << 8) as u64) ^ (outlen as u64);
@@ -194,6 +204,16 @@ fn blake2b_update(ctx: &mut Blake2bCtx, mut data: &[u8]) {
         checked_mem_copy(data, &mut ctx.b[ctx.c .. ], bytes_to_copy);
         ctx.c += bytes_to_copy;
     }
+
+    #[cfg(debug_assertions)]
+    {
+        // compute additional FNV hash for simpler to read debug output
+        const MAGIC_PRIME: u64 = 0x00000100000001b3;
+
+        for &byte in data {
+            ctx.fnv_hash = (ctx.fnv_hash ^ byte as u64).wrapping_mul(MAGIC_PRIME);
+        }
+    }
 }
 
 fn blake2b_final(ctx: &mut Blake2bCtx)
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index 72c533a7461..00c46d992bf 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -40,6 +40,7 @@
 #![feature(discriminant_value)]
 #![feature(specialization)]
 #![feature(manually_drop)]
+#![feature(struct_field_attributes)]
 
 #![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 dc412a0763e..95f063976d4 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -40,13 +40,18 @@ fn write_signed_leb128_to_buf(buf: &mut [u8; 16], value: i64) -> usize {
 /// This hasher currently always uses the stable Blake2b algorithm
 /// and allows for variable output lengths through its type
 /// parameter.
-#[derive(Debug)]
 pub struct StableHasher<W> {
     state: Blake2bHasher,
     bytes_hashed: u64,
     width: PhantomData<W>,
 }
 
+impl<W: StableHasherResult> ::std::fmt::Debug for StableHasher<W> {
+    fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
+        write!(f, "{:?}", self.state)
+    }
+}
+
 pub trait StableHasherResult: Sized {
     fn finish(hasher: StableHasher<Self>) -> Self;
 }
diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs
index 2bce7faf08c..2631108aeb5 100644
--- a/src/librustc_data_structures/transitive_relation.rs
+++ b/src/librustc_data_structures/transitive_relation.rs
@@ -9,11 +9,14 @@
 // except according to those terms.
 
 use bitvec::BitMatrix;
+use stable_hasher::{HashStable, StableHasher, StableHasherResult};
 use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
 use std::cell::RefCell;
 use std::fmt::Debug;
 use std::mem;
 
+
+
 #[derive(Clone)]
 pub struct TransitiveRelation<T: Debug + PartialEq> {
     // List of elements. This is used to map from a T to a usize.  We
@@ -334,6 +337,49 @@ impl<T> Decodable for TransitiveRelation<T>
     }
 }
 
+impl<CTX, T> HashStable<CTX> for TransitiveRelation<T>
+    where T: HashStable<CTX> + PartialEq + Debug
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        // We are assuming here that the relation graph has been built in a
+        // deterministic way and we can just hash it the way it is.
+        let TransitiveRelation {
+            ref elements,
+            ref edges,
+            // "closure" is just a copy of the data above
+            closure: _
+        } = *self;
+
+        elements.hash_stable(hcx, hasher);
+        edges.hash_stable(hcx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for Edge {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        let Edge {
+            ref source,
+            ref target,
+        } = *self;
+
+        source.hash_stable(hcx, hasher);
+        target.hash_stable(hcx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for Index {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        let Index(idx) = *self;
+        idx.hash_stable(hcx, hasher);
+    }
+}
+
 #[test]
 fn test_one_step() {
     let mut relation = TransitiveRelation::new();