Auto merge of #42840 - arielb1:poison-smoke-and-mirrors, r=nikomatsakis

Replace the global fulfillment cache with the evaluation cache

This uses the new "Chalk" ParamEnv refactoring to check "global" predicates in an empty environment, which should be correct because global predicates aren't affected by a consistent environment.

Fixes #39970.
Fixes #42796.

r? @nikomatsakis

6 files changed, 239 insertions, 169 deletions

diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs
index d0bb1adbabb..826d4a28158 100644
--- a/src/librustc/traits/fulfill.rs
+++ b/src/librustc/traits/fulfill.rs
@@ -8,15 +8,14 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use dep_graph::DepGraph;
 use infer::{InferCtxt, InferOk};
-use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, TyCtxt, ToPredicate};
+use ty::{self, Ty, TypeFoldable, ToPolyTraitRef, ToPredicate};
 use ty::error::ExpectedFound;
 use rustc_data_structures::obligation_forest::{ObligationForest, Error};
 use rustc_data_structures::obligation_forest::{ForestObligation, ObligationProcessor};
 use std::marker::PhantomData;
 use syntax::ast;
-use util::nodemap::{FxHashSet, NodeMap};
+use util::nodemap::NodeMap;
 use hir::def_id::DefId;
 
 use super::CodeAmbiguity;
@@ -34,11 +33,6 @@ impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> {
     fn as_predicate(&self) -> &Self::Predicate { &self.obligation.predicate }
 }
 
-pub struct GlobalFulfilledPredicates<'tcx> {
-    set: FxHashSet<ty::PolyTraitPredicate<'tcx>>,
-    dep_graph: DepGraph,
-}
-
 /// The fulfillment context is used to drive trait resolution.  It
 /// consists of a list of obligations that must be (eventually)
 /// satisfied. The job is to track which are satisfied, which yielded
@@ -183,13 +177,6 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
 
         assert!(!infcx.is_in_snapshot());
 
-        let tcx = infcx.tcx;
-
-        if tcx.fulfilled_predicates.borrow().check_duplicate(tcx, &obligation.predicate) {
-            debug!("register_predicate_obligation: duplicate");
-            return
-        }
-
         self.predicates.register_obligation(PendingPredicateObligation {
             obligation,
             stalled_on: vec![]
@@ -264,13 +251,6 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> {
             });
             debug!("select: outcome={:?}", outcome);
 
-            // these are obligations that were proven to be true.
-            for pending_obligation in outcome.completed {
-                let predicate = &pending_obligation.obligation.predicate;
-                selcx.tcx().fulfilled_predicates.borrow_mut()
-                           .add_if_global(selcx.tcx(), predicate);
-            }
-
             errors.extend(
                 outcome.errors.into_iter()
                               .map(|e| to_fulfillment_error(e)));
@@ -318,7 +298,7 @@ impl<'a, 'b, 'gcx, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'gcx,
                                _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>)
         where I: Clone + Iterator<Item=&'c PendingPredicateObligation<'tcx>>,
     {
-        if coinductive_match(self.selcx, cycle.clone()) {
+        if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) {
             debug!("process_child_obligations: coinductive match");
         } else {
             let cycle : Vec<_> = cycle.map(|c| c.obligation.clone()).collect();
@@ -375,21 +355,31 @@ fn process_predicate<'a, 'gcx, 'tcx>(
 
     match obligation.predicate {
         ty::Predicate::Trait(ref data) => {
-            let tcx = selcx.tcx();
-            if tcx.fulfilled_predicates.borrow().check_duplicate_trait(tcx, data) {
-                return Ok(Some(vec![]));
+            let trait_obligation = obligation.with(data.clone());
+
+            if data.is_global() {
+                // no type variables present, can use evaluation for better caching.
+                // FIXME: consider caching errors too.
+                if
+                    // make defaulted unit go through the slow path for better warnings,
+                    // please remove this when the warnings are removed.
+                    !trait_obligation.predicate.skip_binder().self_ty().is_defaulted_unit() &&
+                    selcx.evaluate_obligation_conservatively(&obligation) {
+                    debug!("selecting trait `{:?}` at depth {} evaluated to holds",
+                           data, obligation.recursion_depth);
+                    return Ok(Some(vec![]))
+                }
             }
 
-            let trait_obligation = obligation.with(data.clone());
             match selcx.select(&trait_obligation) {
                 Ok(Some(vtable)) => {
                     debug!("selecting trait `{:?}` at depth {} yielded Ok(Some)",
-                          data, obligation.recursion_depth);
+                           data, obligation.recursion_depth);
                     Ok(Some(vtable.nested_obligations()))
                 }
                 Ok(None) => {
                     debug!("selecting trait `{:?}` at depth {} yielded Ok(None)",
-                          data, obligation.recursion_depth);
+                           data, obligation.recursion_depth);
 
                     // This is a bit subtle: for the most part, the
                     // only reason we can fail to make progress on
@@ -549,40 +539,6 @@ fn process_predicate<'a, 'gcx, 'tcx>(
     }
 }
 
-/// For defaulted traits, we use a co-inductive strategy to solve, so
-/// that recursion is ok. This routine returns true if the top of the
-/// stack (`cycle[0]`):
-/// - is a defaulted trait, and
-/// - it also appears in the backtrace at some position `X`; and,
-/// - all the predicates at positions `X..` between `X` an the top are
-///   also defaulted traits.
-fn coinductive_match<'a,'c,'gcx,'tcx,I>(selcx: &mut SelectionContext<'a,'gcx,'tcx>,
-                                        cycle: I) -> bool
-    where I: Iterator<Item=&'c PendingPredicateObligation<'tcx>>,
-          'tcx: 'c
-{
-    let mut cycle = cycle;
-    cycle
-        .all(|bt_obligation| {
-            let result = coinductive_obligation(selcx, &bt_obligation.obligation);
-            debug!("coinductive_match: bt_obligation={:?} coinductive={}",
-                   bt_obligation, result);
-            result
-        })
-}
-
-fn coinductive_obligation<'a,'gcx,'tcx>(selcx: &SelectionContext<'a,'gcx,'tcx>,
-                                          obligation: &PredicateObligation<'tcx>)
-                                          -> bool {
-    match obligation.predicate {
-        ty::Predicate::Trait(ref data) => {
-            selcx.tcx().trait_has_default_impl(data.def_id())
-        }
-        _ => {
-            false
-        }
-    }
-}
 
 fn register_region_obligation<'tcx>(t_a: Ty<'tcx>,
                                     r_b: ty::Region<'tcx>,
@@ -602,55 +558,6 @@ fn register_region_obligation<'tcx>(t_a: Ty<'tcx>,
 
 }
 
-impl<'a, 'gcx, 'tcx> GlobalFulfilledPredicates<'gcx> {
-    pub fn new(dep_graph: DepGraph) -> GlobalFulfilledPredicates<'gcx> {
-        GlobalFulfilledPredicates {
-            set: FxHashSet(),
-            dep_graph,
-        }
-    }
-
-    pub fn check_duplicate(&self, tcx: TyCtxt, key: &ty::Predicate<'tcx>) -> bool {
-        if let ty::Predicate::Trait(ref data) = *key {
-            self.check_duplicate_trait(tcx, data)
-        } else {
-            false
-        }
-    }
-
-    pub fn check_duplicate_trait(&self, tcx: TyCtxt, data: &ty::PolyTraitPredicate<'tcx>) -> bool {
-        // For the global predicate registry, when we find a match, it
-        // may have been computed by some other task, so we want to
-        // add a read from the node corresponding to the predicate
-        // processing to make sure we get the transitive dependencies.
-        if self.set.contains(data) {
-            debug_assert!(data.is_global());
-            self.dep_graph.read(data.dep_node(tcx));
-            debug!("check_duplicate: global predicate `{:?}` already proved elsewhere", data);
-
-            true
-        } else {
-            false
-        }
-    }
-
-    fn add_if_global(&mut self, tcx: TyCtxt<'a, 'gcx, 'tcx>, key: &ty::Predicate<'tcx>) {
-        if let ty::Predicate::Trait(ref data) = *key {
-            // We only add things to the global predicate registry
-            // after the current task has proved them, and hence
-            // already has the required read edges, so we don't need
-            // to add any more edges here.
-            if data.is_global() {
-                if let Some(data) = tcx.lift_to_global(data) {
-                    if self.set.insert(data.clone()) {
-                        debug!("add_if_global: global predicate `{:?}` added", data);
-                    }
-                }
-            }
-        }
-    }
-}
-
 fn to_fulfillment_error<'tcx>(
     error: Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>)
     -> FulfillmentError<'tcx>
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index 6b243ffa5fe..e14203b34a1 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -31,7 +31,7 @@ use syntax_pos::{Span, DUMMY_SP};
 pub use self::coherence::orphan_check;
 pub use self::coherence::overlapping_impls;
 pub use self::coherence::OrphanCheckErr;
-pub use self::fulfill::{FulfillmentContext, GlobalFulfilledPredicates, RegionObligation};
+pub use self::fulfill::{FulfillmentContext, RegionObligation};
 pub use self::project::MismatchedProjectionTypes;
 pub use self::project::{normalize, normalize_projection_type, Normalized};
 pub use self::project::{ProjectionCache, ProjectionCacheSnapshot, Reveal};
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 4d4693f1c64..452ad43cd69 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -43,6 +43,7 @@ use middle::lang_items;
 use rustc_data_structures::bitvec::BitVector;
 use rustc_data_structures::snapshot_vec::{SnapshotVecDelegate, SnapshotVec};
 use std::cell::RefCell;
+use std::cmp;
 use std::fmt;
 use std::marker::PhantomData;
 use std::mem;
@@ -271,17 +272,101 @@ enum BuiltinImplConditions<'tcx> {
 /// The result of trait evaluation. The order is important
 /// here as the evaluation of a list is the maximum of the
 /// evaluations.
+///
+/// The evaluation results are ordered:
+///     - `EvaluatedToOk` implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
+///     - `EvaluatedToErr` implies `EvaluatedToRecur`
+///     - the "union" of evaluation results is equal to their maximum -
+///     all the "potential success" candidates can potentially succeed,
+///     so they are no-ops when unioned with a definite error, and within
+///     the categories it's easy to see that the unions are correct.
 enum EvaluationResult {
     /// Evaluation successful
     EvaluatedToOk,
-    /// Evaluation failed because of recursion - treated as ambiguous
-    EvaluatedToUnknown,
-    /// Evaluation is known to be ambiguous
+    /// Evaluation is known to be ambiguous - it *might* hold for some
+    /// assignment of inference variables, but it might not.
+    ///
+    /// While this has the same meaning as `EvaluatedToUnknown` - we can't
+    /// know whether this obligation holds or not - it is the result we
+    /// would get with an empty stack, and therefore is cacheable.
     EvaluatedToAmbig,
+    /// Evaluation failed because of recursion involving inference
+    /// variables. We are somewhat imprecise there, so we don't actually
+    /// know the real result.
+    ///
+    /// This can't be trivially cached for the same reason as `EvaluatedToRecur`.
+    EvaluatedToUnknown,
+    /// Evaluation failed because we encountered an obligation we are already
+    /// trying to prove on this branch.
+    ///
+    /// We know this branch can't be a part of a minimal proof-tree for
+    /// the "root" of our cycle, because then we could cut out the recursion
+    /// and maintain a valid proof tree. However, this does not mean
+    /// that all the obligations on this branch do not hold - it's possible
+    /// that we entered this branch "speculatively", and that there
+    /// might be some other way to prove this obligation that does not
+    /// go through this cycle - so we can't cache this as a failure.
+    ///
+    /// For example, suppose we have this:
+    ///
+    /// ```rust,ignore (pseudo-Rust)
+    ///     pub trait Trait { fn xyz(); }
+    ///     // This impl is "useless", but we can still have
+    ///     // an `impl Trait for SomeUnsizedType` somewhere.
+    ///     impl<T: Trait + Sized> Trait for T { fn xyz() {} }
+    ///
+    ///     pub fn foo<T: Trait + ?Sized>() {
+    ///         <T as Trait>::xyz();
+    ///     }
+    /// ```
+    ///
+    /// When checking `foo`, we have to prove `T: Trait`. This basically
+    /// translates into this:
+    ///
+    ///     (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait
+    ///
+    /// When we try to prove it, we first go the first option, which
+    /// recurses. This shows us that the impl is "useless" - it won't
+    /// tell us that `T: Trait` unless it already implemented `Trait`
+    /// by some other means. However, that does not prevent `T: Trait`
+    /// does not hold, because of the bound (which can indeed be satisfied
+    /// by `SomeUnsizedType` from another crate).
+    ///
+    /// FIXME: when an `EvaluatedToRecur` goes past its parent root, we
+    /// ought to convert it to an `EvaluatedToErr`, because we know
+    /// there definitely isn't a proof tree for that obligation. Not
+    /// doing so is still sound - there isn't any proof tree, so the
+    /// branch still can't be a part of a minimal one - but does not
+    /// re-enable caching.
+    EvaluatedToRecur,
     /// Evaluation failed
     EvaluatedToErr,
 }
 
+impl EvaluationResult {
+    fn may_apply(self) -> bool {
+        match self {
+            EvaluatedToOk |
+            EvaluatedToAmbig |
+            EvaluatedToUnknown => true,
+
+            EvaluatedToErr |
+            EvaluatedToRecur => false
+        }
+    }
+
+    fn is_stack_dependent(self) -> bool {
+        match self {
+            EvaluatedToUnknown |
+            EvaluatedToRecur => true,
+
+            EvaluatedToOk |
+            EvaluatedToAmbig |
+            EvaluatedToErr => false,
+        }
+    }
+}
+
 #[derive(Clone)]
 pub struct EvaluationCache<'tcx> {
     hashmap: RefCell<FxHashMap<ty::PolyTraitRef<'tcx>, EvaluationResult>>
@@ -492,15 +577,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             let eval = self.evaluate_predicate_recursively(stack, obligation);
             debug!("evaluate_predicate_recursively({:?}) = {:?}",
                    obligation, eval);
-            match eval {
-                EvaluatedToErr => { return EvaluatedToErr; }
-                EvaluatedToAmbig => { result = EvaluatedToAmbig; }
-                EvaluatedToUnknown => {
-                    if result < EvaluatedToUnknown {
-                        result = EvaluatedToUnknown;
-                    }
-                }
-                EvaluatedToOk => { }
+            if let EvaluatedToErr = eval {
+                // fast-path - EvaluatedToErr is the top of the lattice,
+                // so we don't need to look on the other predicates.
+                return EvaluatedToErr;
+            } else {
+                result = cmp::max(result, eval);
             }
         }
         result
@@ -514,21 +596,11 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         debug!("evaluate_predicate_recursively({:?})",
                obligation);
 
-        let tcx = self.tcx();
-
-        // Check the cache from the tcx of predicates that we know
-        // have been proven elsewhere. This cache only contains
-        // predicates that are global in scope and hence unaffected by
-        // the current environment.
-        if tcx.fulfilled_predicates.borrow().check_duplicate(tcx, &obligation.predicate) {
-            return EvaluatedToOk;
-        }
-
         match obligation.predicate {
             ty::Predicate::Trait(ref t) => {
                 assert!(!t.has_escaping_regions());
                 let obligation = obligation.with(t.clone());
-                self.evaluate_obligation_recursively(previous_stack, &obligation)
+                self.evaluate_trait_predicate_recursively(previous_stack, obligation)
             }
 
             ty::Predicate::Equate(ref p) => {
@@ -613,15 +685,23 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
     }
 
-    fn evaluate_obligation_recursively<'o>(&mut self,
-                                           previous_stack: TraitObligationStackList<'o, 'tcx>,
-                                           obligation: &TraitObligation<'tcx>)
-                                           -> EvaluationResult
+    fn evaluate_trait_predicate_recursively<'o>(&mut self,
+                                                previous_stack: TraitObligationStackList<'o, 'tcx>,
+                                                mut obligation: TraitObligation<'tcx>)
+                                                -> EvaluationResult
     {
-        debug!("evaluate_obligation_recursively({:?})",
+        debug!("evaluate_trait_predicate_recursively({:?})",
                obligation);
 
-        let stack = self.push_stack(previous_stack, obligation);
+        if !self.intercrate && obligation.is_global() {
+            // If a param env is consistent, global obligations do not depend on its particular
+            // value in order to work, so we can clear out the param env and get better
+            // caching. (If the current param env is inconsistent, we don't care what happens).
+            debug!("evaluate_trait_predicate_recursively({:?}) - in global", obligation);
+            obligation.param_env = ty::ParamEnv::empty(obligation.param_env.reveal);
+        }
+
+        let stack = self.push_stack(previous_stack, &obligation);
         let fresh_trait_ref = stack.fresh_trait_ref;
         if let Some(result) = self.check_evaluation_cache(obligation.param_env, fresh_trait_ref) {
             debug!("CACHE HIT: EVAL({:?})={:?}",
@@ -676,8 +756,9 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
         if unbound_input_types &&
               stack.iter().skip(1).any(
-                  |prev| self.match_fresh_trait_refs(&stack.fresh_trait_ref,
-                                                     &prev.fresh_trait_ref))
+                  |prev| stack.obligation.param_env == prev.obligation.param_env &&
+                      self.match_fresh_trait_refs(&stack.fresh_trait_ref,
+                                                  &prev.fresh_trait_ref))
         {
             debug!("evaluate_stack({:?}) --> unbound argument, recursive --> giving up",
                    stack.fresh_trait_ref);
@@ -703,14 +784,25 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         // affect the inferencer state and (b) that if we see two
         // skolemized types with the same index, they refer to the
         // same unbound type variable.
-        if
+        if let Some(rec_index) =
             stack.iter()
             .skip(1) // skip top-most frame
-            .any(|prev| stack.fresh_trait_ref == prev.fresh_trait_ref)
+            .position(|prev| stack.obligation.param_env == prev.obligation.param_env &&
+                      stack.fresh_trait_ref == prev.fresh_trait_ref)
         {
             debug!("evaluate_stack({:?}) --> recursive",
                    stack.fresh_trait_ref);
-            return EvaluatedToOk;
+            let cycle = stack.iter().skip(1).take(rec_index+1);
+            let cycle = cycle.map(|stack| ty::Predicate::Trait(stack.obligation.predicate));
+            if self.coinductive_match(cycle) {
+                debug!("evaluate_stack({:?}) --> recursive, coinductive",
+                       stack.fresh_trait_ref);
+                return EvaluatedToOk;
+            } else {
+                debug!("evaluate_stack({:?}) --> recursive, inductive",
+                       stack.fresh_trait_ref);
+                return EvaluatedToRecur;
+            }
         }
 
         match self.candidate_from_obligation(stack) {
@@ -720,6 +812,33 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         }
     }
 
+    /// For defaulted traits, we use a co-inductive strategy to solve, so
+    /// that recursion is ok. This routine returns true if the top of the
+    /// stack (`cycle[0]`):
+    /// - is a defaulted trait, and
+    /// - it also appears in the backtrace at some position `X`; and,
+    /// - all the predicates at positions `X..` between `X` an the top are
+    ///   also defaulted traits.
+    pub fn coinductive_match<I>(&mut self, cycle: I) -> bool
+        where I: Iterator<Item=ty::Predicate<'tcx>>
+    {
+        let mut cycle = cycle;
+        cycle.all(|predicate| self.coinductive_predicate(predicate))
+    }
+
+    fn coinductive_predicate(&self, predicate: ty::Predicate<'tcx>) -> bool {
+        let result = match predicate {
+            ty::Predicate::Trait(ref data) => {
+                self.tcx().trait_has_default_impl(data.def_id())
+            }
+            _ => {
+                false
+            }
+        };
+        debug!("coinductive_predicate({:?}) = {:?}", predicate, result);
+        result
+    }
+
     /// Further evaluate `candidate` to decide whether all type parameters match and whether nested
     /// obligations are met. Returns true if `candidate` remains viable after this further
     /// scrutiny.
@@ -754,6 +873,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         if self.can_use_global_caches(param_env) {
             let cache = self.tcx().evaluation_cache.hashmap.borrow();
             if let Some(cached) = cache.get(&trait_ref) {
+                let dep_node = trait_ref
+                    .to_poly_trait_predicate()
+                    .dep_node(self.tcx());
+                self.tcx().hir.dep_graph.read(dep_node);
                 return Some(cached.clone());
             }
         }
@@ -766,10 +889,10 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                                result: EvaluationResult)
     {
         // Avoid caching results that depend on more than just the trait-ref:
-        // The stack can create EvaluatedToUnknown, and closure signatures
+        // The stack can create recursion, and closure signatures
         // being yet uninferred can create "spurious" EvaluatedToAmbig
         // and EvaluatedToOk.
-        if result == EvaluatedToUnknown ||
+        if result.is_stack_dependent() ||
             ((result == EvaluatedToAmbig || result == EvaluatedToOk)
              && trait_ref.has_closure_types())
         {
@@ -3014,15 +3137,3 @@ impl<'o,'tcx> fmt::Debug for TraitObligationStack<'o,'tcx> {
         write!(f, "TraitObligationStack({:?})", self.obligation)
     }
 }
-
-impl EvaluationResult {
-    fn may_apply(&self) -> bool {
-        match *self {
-            EvaluatedToOk |
-            EvaluatedToAmbig |
-            EvaluatedToUnknown => true,
-
-            EvaluatedToErr => false
-        }
-    }
-}
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 316f871a7a4..1f20993f96c 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -507,12 +507,6 @@ pub struct GlobalCtxt<'tcx> {
     /// Merge this with `selection_cache`?
     pub evaluation_cache: traits::EvaluationCache<'tcx>,
 
-    /// A set of predicates that have been fulfilled *somewhere*.
-    /// This is used to avoid duplicate work. Predicates are only
-    /// added to this set when they mention only "global" names
-    /// (i.e., no type or lifetime parameters).
-    pub fulfilled_predicates: RefCell<traits::GlobalFulfilledPredicates<'tcx>>,
-
     /// Maps Expr NodeId's to `true` iff `&expr` can have 'static lifetime.
     pub rvalue_promotable_to_static: RefCell<NodeMap<bool>>,
 
@@ -686,7 +680,6 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         let interners = CtxtInterners::new(arena);
         let common_types = CommonTypes::new(&interners);
         let dep_graph = hir.dep_graph.clone();
-        let fulfilled_predicates = traits::GlobalFulfilledPredicates::new(dep_graph.clone());
         let max_cnum = s.cstore.crates().iter().map(|c| c.as_usize()).max().unwrap_or(0);
         let mut providers = IndexVec::from_elem_n(extern_providers, max_cnum + 1);
         providers[LOCAL_CRATE] = local_providers;
@@ -735,7 +728,6 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             named_region_map,
             trait_map: resolutions.trait_map,
             export_map: resolutions.export_map,
-            fulfilled_predicates: RefCell::new(fulfilled_predicates),
             hir,
             def_path_hash_to_def_id,
             maps: maps::Maps::new(providers),
diff --git a/src/test/compile-fail/issue-39970.rs b/src/test/compile-fail/issue-39970.rs
new file mode 100644
index 00000000000..65ea1baa4a1
--- /dev/null
+++ b/src/test/compile-fail/issue-39970.rs
@@ -0,0 +1,31 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+trait Array<'a> {
+    type Element: 'a;
+}
+
+trait Visit {
+    fn visit() {}
+}
+
+impl<'a> Array<'a> for () {
+    type Element = &'a ();
+}
+
+impl Visit for () where
+    //(): for<'a> Array<'a, Element=&'a ()>, // No ICE
+    (): for<'a> Array<'a, Element=()>, // ICE
+{}
+
+fn main() {
+    <() as Visit>::visit();
+    //~^ ERROR type mismatch resolving `for<'a> <() as Array<'a>>::Element == ()`
+}
diff --git a/src/test/compile-fail/issue-42796.rs b/src/test/compile-fail/issue-42796.rs
new file mode 100644
index 00000000000..10622eccbdc
--- /dev/null
+++ b/src/test/compile-fail/issue-42796.rs
@@ -0,0 +1,29 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+pub trait Mirror<Smoke> {
+    type Image;
+}
+
+impl<T, Smoke> Mirror<Smoke> for T {
+    type Image = T;
+}
+
+pub fn poison<S>(victim: String) where <String as Mirror<S>>::Image: Copy {
+    loop { drop(victim); } //~ ERROR use of moved value
+}
+
+fn main() {
+    let s = "Hello!".to_owned();
+    let mut s_copy = s;
+    s_copy.push_str("World!");
+    "0wned!".to_owned();
+    println!("{}", s); //~ ERROR use of moved value
+}