Implement Hash in terms of HashStable for EvalSnapshot

8 files changed, 105 insertions, 52 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 6250e12f430..677343a85de 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -412,7 +412,7 @@ impl<'a> HashStable<StableHashingContext<'a>> for mir::interpret::AllocId {
         ty::tls::with_opt(|tcx| {
             trace!("hashing {:?}", *self);
             let tcx = tcx.expect("can't hash AllocIds during hir lowering");
-            let alloc_kind = tcx.alloc_map.lock().get(*self).expect("no value for AllocId");
+            let alloc_kind = tcx.alloc_map.lock().get(*self);
             alloc_kind.hash_stable(hcx, hasher);
         });
     }
diff --git a/src/librustc_data_structures/stable_hasher.rs b/src/librustc_data_structures/stable_hasher.rs
index 1024e69cc2b..c70a0abe8c7 100644
--- a/src/librustc_data_structures/stable_hasher.rs
+++ b/src/librustc_data_structures/stable_hasher.rs
@@ -281,6 +281,23 @@ impl<T1, T2, T3, CTX> HashStable<CTX> for (T1, T2, T3)
     }
 }
 
+impl<T1, T2, T3, T4, CTX> HashStable<CTX> for (T1, T2, T3, T4)
+     where T1: HashStable<CTX>,
+           T2: HashStable<CTX>,
+           T3: HashStable<CTX>,
+           T4: HashStable<CTX>,
+{
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          ctx: &mut CTX,
+                                          hasher: &mut StableHasher<W>) {
+        let (ref _0, ref _1, ref _2, ref _3) = *self;
+        _0.hash_stable(ctx, hasher);
+        _1.hash_stable(ctx, hasher);
+        _2.hash_stable(ctx, hasher);
+        _3.hash_stable(ctx, hasher);
+    }
+}
+
 impl<T: HashStable<CTX>, CTX> HashStable<CTX> for [T] {
     default fn hash_stable<W: StableHasherResult>(&self,
                                                   ctx: &mut CTX,
diff --git a/src/librustc_mir/const_eval.rs b/src/librustc_mir/const_eval.rs
index 70addf2c907..92ddd8777f7 100644
--- a/src/librustc_mir/const_eval.rs
+++ b/src/librustc_mir/const_eval.rs
@@ -196,6 +196,8 @@ impl<'tcx> Into<EvalError<'tcx>> for ConstEvalError {
     }
 }
 
+impl_stable_hash_for!(struct CompileTimeEvaluator {});
+
 #[derive(Clone, Debug)]
 enum ConstEvalError {
     NeedsRfc(String),
diff --git a/src/librustc_mir/interpret/eval_context.rs b/src/librustc_mir/interpret/eval_context.rs
index 467634f2896..8d4f3baf3a9 100644
--- a/src/librustc_mir/interpret/eval_context.rs
+++ b/src/librustc_mir/interpret/eval_context.rs
@@ -15,6 +15,7 @@ use std::mem;
 use rustc::hir::def_id::DefId;
 use rustc::hir::def::Def;
 use rustc::hir::map::definitions::DefPathData;
+use rustc::ich::{StableHashingContext, StableHashingContextProvider};
 use rustc::mir;
 use rustc::ty::layout::{
     self, Size, Align, HasDataLayout, LayoutOf, TyLayout
@@ -22,8 +23,9 @@ use rustc::ty::layout::{
 use rustc::ty::subst::{Subst, Substs};
 use rustc::ty::{self, Ty, TyCtxt, TypeFoldable};
 use rustc::ty::query::TyCtxtAt;
-use rustc_data_structures::fx::{FxHashSet, FxHasher};
+use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::indexed_vec::IndexVec;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher, StableHasherResult};
 use rustc::mir::interpret::{
     GlobalId, Scalar, FrameInfo,
     EvalResult, EvalErrorKind,
@@ -134,12 +136,12 @@ impl<'mir, 'tcx: 'mir> PartialEq for Frame<'mir, 'tcx> {
     }
 }
 
-impl<'mir, 'tcx: 'mir> Hash for Frame<'mir, 'tcx> {
-    fn hash<H: Hasher>(&self, state: &mut H) {
+impl<'a, 'mir, 'tcx: 'mir> HashStable<StableHashingContext<'a>> for Frame<'mir, 'tcx> {
+    fn hash_stable<W: StableHasherResult>(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher<W>) {
         let Frame {
-            mir: _,
+            mir,
             instance,
-            span: _,
+            span,
             return_to_block,
             return_place,
             locals,
@@ -147,12 +149,8 @@ impl<'mir, 'tcx: 'mir> Hash for Frame<'mir, 'tcx> {
             stmt,
         } = self;
 
-        instance.hash(state);
-        return_to_block.hash(state);
-        return_place.hash(state);
-        locals.hash(state);
-        block.hash(state);
-        stmt.hash(state);
+        (mir, instance, span, return_to_block).hash_stable(hcx, hasher);
+        (return_place, locals, block, stmt).hash_stable(hcx, hasher);
     }
 }
 
@@ -168,6 +166,15 @@ pub enum StackPopCleanup {
     None { cleanup: bool },
 }
 
+impl<'a> HashStable<StableHashingContext<'a>> for StackPopCleanup {
+    fn hash_stable<W: StableHasherResult>(&self, hcx: &mut StableHashingContext<'b>, hasher: &mut StableHasher<W>) {
+        match self {
+            StackPopCleanup::Goto(ref block) => block.hash_stable(hcx, hasher),
+            StackPopCleanup::None { cleanup } => cleanup.hash_stable(hcx, hasher),
+        }
+    }
+}
+
 // State of a local variable
 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 pub enum LocalValue {
@@ -195,9 +202,14 @@ impl<'tcx> LocalValue {
     }
 }
 
+impl_stable_hash_for!(enum self::LocalValue {
+    Dead,
+    Live(x),
+});
+
 /// The virtual machine state during const-evaluation at a given point in time.
-#[derive(Eq, PartialEq, Hash)]
-pub(crate) struct EvalSnapshot<'a, 'mir, 'tcx: 'a + 'mir, M: Machine<'mir, 'tcx>> {
+#[derive(Eq, PartialEq)]
+struct EvalSnapshot<'a, 'mir, 'tcx: 'a + 'mir, M: Machine<'mir, 'tcx>> {
     machine: M,
     memory: Memory<'a, 'mir, 'tcx, M>,
     stack: Vec<Frame<'mir, 'tcx>>,
@@ -215,6 +227,27 @@ impl<'a, 'mir, 'tcx, M> EvalSnapshot<'a, 'mir, 'tcx, M>
     }
 }
 
+impl<'a, 'mir, 'tcx, M> Hash for EvalSnapshot<'a, 'mir, 'tcx, M>
+    where M: Machine<'mir, 'tcx>,
+{
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        // Implement in terms of hash stable, so that k1 == k2 -> hash(k1) == hash(k2)
+        let mut hcx = self.memory.tcx.get_stable_hashing_context();
+        let mut hasher = StableHasher::<u64>::new();
+        self.hash_stable(&mut hcx, &mut hasher);
+        hasher.finish().hash(state)
+    }
+}
+
+impl<'a, 'b, 'mir, 'tcx, M> HashStable<StableHashingContext<'b>> for EvalSnapshot<'a, 'mir, 'tcx, M>
+    where M: Machine<'mir, 'tcx>,
+{
+    fn hash_stable<W: StableHasherResult>(&self, hcx: &mut StableHashingContext<'b>, hasher: &mut StableHasher<W>) {
+        let EvalSnapshot{ machine, memory, stack } = self;
+        (machine, &memory.data, stack).hash_stable(hcx, hasher);
+    }
+}
+
 pub(super) struct InfiniteLoopDetector<'a, 'mir, 'tcx: 'a + 'mir, M: Machine<'mir, 'tcx>> {
     /// The set of all `EvalSnapshot` *hashes* observed by this detector.
     ///
@@ -258,9 +291,10 @@ impl<'a, 'mir, 'tcx, M> InfiniteLoopDetector<'a, 'mir, 'tcx, M>
         stack: &[Frame<'mir, 'tcx>],
     ) -> EvalResult<'tcx, ()> {
 
-        let mut fx = FxHasher::default();
-        (machine, memory, stack).hash(&mut fx);
-        let hash = fx.finish();
+        let mut hcx = memory.tcx.get_stable_hashing_context();
+        let mut hasher = StableHasher::<u64>::new();
+        (machine, stack).hash_stable(&mut hcx, &mut hasher);
+        let hash = hasher.finish();
 
         if self.hashes.insert(hash) {
             // No collision
diff --git a/src/librustc_mir/interpret/machine.rs b/src/librustc_mir/interpret/machine.rs
index 57af63d63d9..61963f6d3d3 100644
--- a/src/librustc_mir/interpret/machine.rs
+++ b/src/librustc_mir/interpret/machine.rs
@@ -15,17 +15,19 @@
 use std::hash::Hash;
 
 use rustc::hir::def_id::DefId;
+use rustc::ich::StableHashingContext;
 use rustc::mir::interpret::{Allocation, EvalResult, Scalar};
 use rustc::mir;
 use rustc::ty::{self, layout::TyLayout, query::TyCtxtAt};
+use rustc_data_structures::stable_hasher::HashStable;
 
 use super::{EvalContext, PlaceTy, OpTy};
 
 /// Methods of this trait signifies a point where CTFE evaluation would fail
 /// and some use case dependent behaviour can instead be applied
-pub trait Machine<'mir, 'tcx>: Clone + Eq + Hash {
+pub trait Machine<'mir, 'tcx>: Clone + Eq + Hash + for<'a> HashStable<StableHashingContext<'a>> {
     /// Additional data that can be accessed via the Memory
-    type MemoryData: Clone + Eq + Hash;
+    type MemoryData: Clone + Eq + Hash + for<'a> HashStable<StableHashingContext<'a>>;
 
     /// Additional memory kinds a machine wishes to distinguish from the builtin ones
     type MemoryKinds: ::std::fmt::Debug + Copy + Clone + Eq + Hash;
diff --git a/src/librustc_mir/interpret/memory.rs b/src/librustc_mir/interpret/memory.rs
index 59bebbb87a7..4a291f164cc 100644
--- a/src/librustc_mir/interpret/memory.rs
+++ b/src/librustc_mir/interpret/memory.rs
@@ -17,7 +17,6 @@
 //! short-circuiting the empty case!
 
 use std::collections::VecDeque;
-use std::hash::{Hash, Hasher};
 use std::ptr;
 
 use rustc::ty::{self, Instance, query::TyCtxtAt};
@@ -26,7 +25,7 @@ use rustc::mir::interpret::{Pointer, AllocId, Allocation, ConstValue, ScalarMayb
                             EvalResult, Scalar, EvalErrorKind, AllocType, PointerArithmetic,
                             truncate};
 pub use rustc::mir::interpret::{write_target_uint, read_target_uint};
-use rustc_data_structures::fx::{FxHashSet, FxHashMap, FxHasher};
+use rustc_data_structures::fx::{FxHashSet, FxHashMap};
 
 use syntax::ast::Mutability;
 
@@ -91,37 +90,6 @@ impl<'a, 'mir, 'tcx, M> PartialEq for Memory<'a, 'mir, 'tcx, M>
     }
 }
 
-impl<'a, 'mir, 'tcx, M> Hash for Memory<'a, 'mir, 'tcx, M>
-    where M: Machine<'mir, 'tcx>,
-          'tcx: 'a + 'mir,
-{
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        let Memory {
-            data,
-            alloc_map: _,
-            tcx: _,
-        } = self;
-
-        data.hash(state);
-
-        // We ignore some fields which don't change between evaluation steps.
-
-        // Since HashMaps which contain the same items may have different
-        // iteration orders, we use a commutative operation (in this case
-        // addition, but XOR would also work), to combine the hash of each
-        // `Allocation`.
-        self.alloc_map.iter()
-            .map(|(&id, alloc)| {
-                let mut h = FxHasher::default();
-                id.hash(&mut h);
-                alloc.hash(&mut h);
-                h.finish()
-            })
-            .fold(0u64, |hash, x| hash.wrapping_add(x))
-            .hash(state);
-    }
-}
-
 impl<'a, 'mir, 'tcx, M: Machine<'mir, 'tcx>> Memory<'a, 'mir, 'tcx, M> {
     pub fn new(tcx: TyCtxtAt<'a, 'tcx, 'tcx>, data: M::MemoryData) -> Self {
         Memory {
diff --git a/src/librustc_mir/interpret/operand.rs b/src/librustc_mir/interpret/operand.rs
index 6f9e0cf3e37..9970816dc2a 100644
--- a/src/librustc_mir/interpret/operand.rs
+++ b/src/librustc_mir/interpret/operand.rs
@@ -81,6 +81,11 @@ impl<'tcx> Value {
     }
 }
 
+impl_stable_hash_for!(enum ::interpret::Value {
+    Scalar(x),
+    ScalarPair(x, y),
+});
+
 // ScalarPair needs a type to interpret, so we often have a value and a type together
 // as input for binary and cast operations.
 #[derive(Copy, Clone, Debug)]
@@ -126,6 +131,11 @@ impl Operand {
     }
 }
 
+impl_stable_hash_for!(enum ::interpret::Operand {
+    Immediate(x),
+    Indirect(x),
+});
+
 #[derive(Copy, Clone, Debug)]
 pub struct OpTy<'tcx> {
     crate op: Operand, // ideally we'd make this private, but const_prop needs this
diff --git a/src/librustc_mir/interpret/place.rs b/src/librustc_mir/interpret/place.rs
index 5bf6b2b46b7..6236a4784fb 100644
--- a/src/librustc_mir/interpret/place.rs
+++ b/src/librustc_mir/interpret/place.rs
@@ -14,10 +14,12 @@
 
 use std::convert::TryFrom;
 
+use rustc::ich::StableHashingContext;
 use rustc::mir;
 use rustc::ty::{self, Ty};
 use rustc::ty::layout::{self, Size, Align, LayoutOf, TyLayout, HasDataLayout};
 use rustc_data_structures::indexed_vec::Idx;
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher, StableHasherResult};
 
 use rustc::mir::interpret::{
     GlobalId, Scalar, EvalResult, Pointer, ScalarMaybeUndef, PointerArithmetic
@@ -37,6 +39,12 @@ pub struct MemPlace {
     pub extra: Option<Scalar>,
 }
 
+impl_stable_hash_for!(struct ::interpret::MemPlace {
+    ptr,
+    align,
+    extra,
+});
+
 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 pub enum Place {
     /// A place referring to a value allocated in the `Memory` system.
@@ -50,6 +58,18 @@ pub enum Place {
     },
 }
 
+impl<'a> HashStable<StableHashingContext<'a>> for Place {
+    fn hash_stable<W: StableHasherResult>(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher<W>) {
+        match self {
+            Place::Ptr(mem_place) => mem_place.hash_stable(hcx, hasher),
+
+            Place::Local { frame, local } => {
+                frame.hash_stable(hcx, hasher);
+                local.hash_stable(hcx, hasher);
+            },
+        }
+    }
+}
 #[derive(Copy, Clone, Debug)]
 pub struct PlaceTy<'tcx> {
     place: Place,