Auto merge of #75055 - cjgillot:clean-cache, r=oli-obk

Introduce an abstraction for EvaluationCache and SelectionCache

The small duplicated code has been moved to librustc_query_system.

The remaining changes are some cleanups of structural impls.

8 files changed, 145 insertions, 367 deletions

diff --git a/src/librustc_middle/mir/interpret/error.rs b/src/librustc_middle/mir/interpret/error.rs
index a33fb2e54dd..c904cd83a78 100644
--- a/src/librustc_middle/mir/interpret/error.rs
+++ b/src/librustc_middle/mir/interpret/error.rs
@@ -27,7 +27,7 @@ pub enum ErrorHandled {
     TooGeneric,
 }
 
-CloneTypeFoldableImpls! {
+CloneTypeFoldableAndLiftImpls! {
     ErrorHandled,
 }
 
diff --git a/src/librustc_middle/traits/mod.rs b/src/librustc_middle/traits/mod.rs
index d2747e5fc65..585f29386a8 100644
--- a/src/librustc_middle/traits/mod.rs
+++ b/src/librustc_middle/traits/mod.rs
@@ -30,7 +30,6 @@ pub type ChalkCanonicalGoal<'tcx> = Canonical<'tcx, ChalkEnvironmentAndGoal<'tcx
 
 pub use self::ImplSource::*;
 pub use self::ObligationCauseCode::*;
-pub use self::SelectionError::*;
 
 pub use self::chalk::{
     ChalkEnvironmentAndGoal, ChalkEnvironmentClause, RustInterner as ChalkRustInterner,
@@ -86,7 +85,7 @@ pub enum Reveal {
 ///
 /// We do not want to intern this as there are a lot of obligation causes which
 /// only live for a short period of time.
-#[derive(Clone, PartialEq, Eq, Hash)]
+#[derive(Clone, PartialEq, Eq, Hash, Lift)]
 pub struct ObligationCause<'tcx> {
     /// `None` for `ObligationCause::dummy`, `Some` otherwise.
     data: Option<Rc<ObligationCauseData<'tcx>>>,
@@ -111,7 +110,7 @@ impl Deref for ObligationCause<'tcx> {
     }
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
 pub struct ObligationCauseData<'tcx> {
     pub span: Span,
 
@@ -169,14 +168,14 @@ impl<'tcx> ObligationCause<'tcx> {
     }
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
 pub struct UnifyReceiverContext<'tcx> {
     pub assoc_item: ty::AssocItem,
     pub param_env: ty::ParamEnv<'tcx>,
     pub substs: SubstsRef<'tcx>,
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
 pub enum ObligationCauseCode<'tcx> {
     /// Not well classified or should be obvious from the span.
     MiscObligation,
@@ -343,7 +342,7 @@ impl ObligationCauseCode<'_> {
 #[cfg(target_arch = "x86_64")]
 static_assert_size!(ObligationCauseCode<'_>, 32);
 
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
 pub struct MatchExpressionArmCause<'tcx> {
     pub arm_span: Span,
     pub source: hir::MatchSource,
@@ -359,7 +358,7 @@ pub struct IfExpressionCause {
     pub semicolon: Option<Span>,
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
 pub struct DerivedObligationCause<'tcx> {
     /// The trait reference of the parent obligation that led to the
     /// current obligation. Note that only trait obligations lead to
@@ -371,7 +370,7 @@ pub struct DerivedObligationCause<'tcx> {
     pub parent_code: Rc<ObligationCauseCode<'tcx>>,
 }
 
-#[derive(Clone, Debug, TypeFoldable)]
+#[derive(Clone, Debug, TypeFoldable, Lift)]
 pub enum SelectionError<'tcx> {
     Unimplemented,
     OutputTypeParameterMismatch(
@@ -427,7 +426,7 @@ pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 /// ### The type parameter `N`
 ///
 /// See explanation on `ImplSourceUserDefinedData`.
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub enum ImplSource<'tcx, N> {
     /// ImplSource identifying a particular impl.
     ImplSourceUserDefined(ImplSourceUserDefinedData<'tcx, N>),
@@ -558,14 +557,14 @@ impl<'tcx, N> ImplSource<'tcx, N> {
 /// is `Obligation`, as one might expect. During codegen, however, this
 /// is `()`, because codegen only requires a shallow resolution of an
 /// impl, and nested obligations are satisfied later.
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceUserDefinedData<'tcx, N> {
     pub impl_def_id: DefId,
     pub substs: SubstsRef<'tcx>,
     pub nested: Vec<N>,
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceGeneratorData<'tcx, N> {
     pub generator_def_id: DefId,
     pub substs: SubstsRef<'tcx>,
@@ -574,7 +573,7 @@ pub struct ImplSourceGeneratorData<'tcx, N> {
     pub nested: Vec<N>,
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceClosureData<'tcx, N> {
     pub closure_def_id: DefId,
     pub substs: SubstsRef<'tcx>,
@@ -583,18 +582,18 @@ pub struct ImplSourceClosureData<'tcx, N> {
     pub nested: Vec<N>,
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceAutoImplData<N> {
     pub trait_def_id: DefId,
     pub nested: Vec<N>,
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceBuiltinData<N> {
     pub nested: Vec<N>,
 }
 
-#[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceObjectData<'tcx, N> {
     /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`.
     pub upcast_trait_ref: ty::PolyTraitRef<'tcx>,
@@ -607,17 +606,17 @@ pub struct ImplSourceObjectData<'tcx, N> {
     pub nested: Vec<N>,
 }
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceFnPointerData<'tcx, N> {
     pub fn_ty: Ty<'tcx>,
     pub nested: Vec<N>,
 }
 
 // FIXME(@lcnr): This should be  refactored and merged with other builtin vtables.
-#[derive(Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 pub struct ImplSourceDiscriminantKindData;
 
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable, Lift)]
 pub struct ImplSourceTraitAliasData<'tcx, N> {
     pub alias_def_id: DefId,
     pub substs: SubstsRef<'tcx>,
diff --git a/src/librustc_middle/traits/select.rs b/src/librustc_middle/traits/select.rs
index a12f5910b14..6ad514c6be2 100644
--- a/src/librustc_middle/traits/select.rs
+++ b/src/librustc_middle/traits/select.rs
@@ -6,29 +6,18 @@ use self::EvaluationResult::*;
 
 use super::{SelectionError, SelectionResult};
 
-use crate::dep_graph::DepNodeIndex;
-use crate::ty::{self, TyCtxt};
+use crate::ty;
 
-use rustc_data_structures::fx::FxHashMap;
-use rustc_data_structures::sync::Lock;
 use rustc_hir::def_id::DefId;
+use rustc_query_system::cache::Cache;
 
-#[derive(Clone, Default)]
-pub struct SelectionCache<'tcx> {
-    pub hashmap: Lock<
-        FxHashMap<
-            ty::ParamEnvAnd<'tcx, ty::TraitRef<'tcx>>,
-            WithDepNode<SelectionResult<'tcx, SelectionCandidate<'tcx>>>,
-        >,
-    >,
-}
+pub type SelectionCache<'tcx> = Cache<
+    ty::ParamEnvAnd<'tcx, ty::TraitRef<'tcx>>,
+    SelectionResult<'tcx, SelectionCandidate<'tcx>>,
+>;
 
-impl<'tcx> SelectionCache<'tcx> {
-    /// Actually frees the underlying memory in contrast to what stdlib containers do on `clear`
-    pub fn clear(&self) {
-        *self.hashmap.borrow_mut() = Default::default();
-    }
-}
+pub type EvaluationCache<'tcx> =
+    Cache<ty::ParamEnvAnd<'tcx, ty::PolyTraitRef<'tcx>>, EvaluationResult>;
 
 /// The selection process begins by considering all impls, where
 /// clauses, and so forth that might resolve an obligation. Sometimes
@@ -264,75 +253,3 @@ impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
         SelectionError::Overflow
     }
 }
-
-#[derive(Clone, Default)]
-pub struct EvaluationCache<'tcx> {
-    pub hashmap: Lock<
-        FxHashMap<ty::ParamEnvAnd<'tcx, ty::PolyTraitRef<'tcx>>, WithDepNode<EvaluationResult>>,
-    >,
-}
-
-impl<'tcx> EvaluationCache<'tcx> {
-    /// Actually frees the underlying memory in contrast to what stdlib containers do on `clear`
-    pub fn clear(&self) {
-        *self.hashmap.borrow_mut() = Default::default();
-    }
-}
-
-#[derive(Clone, Eq, PartialEq)]
-pub struct WithDepNode<T> {
-    dep_node: DepNodeIndex,
-    cached_value: T,
-}
-
-impl<T: Clone> WithDepNode<T> {
-    pub fn new(dep_node: DepNodeIndex, cached_value: T) -> Self {
-        WithDepNode { dep_node, cached_value }
-    }
-
-    pub fn get(&self, tcx: TyCtxt<'_>) -> T {
-        tcx.dep_graph.read_index(self.dep_node);
-        self.cached_value.clone()
-    }
-}
-
-#[derive(Clone, Debug)]
-pub enum IntercrateAmbiguityCause {
-    DownstreamCrate { trait_desc: String, self_desc: Option<String> },
-    UpstreamCrateUpdate { trait_desc: String, self_desc: Option<String> },
-    ReservationImpl { message: String },
-}
-
-impl IntercrateAmbiguityCause {
-    /// Emits notes when the overlap is caused by complex intercrate ambiguities.
-    /// See #23980 for details.
-    pub fn add_intercrate_ambiguity_hint(&self, err: &mut rustc_errors::DiagnosticBuilder<'_>) {
-        err.note(&self.intercrate_ambiguity_hint());
-    }
-
-    pub fn intercrate_ambiguity_hint(&self) -> String {
-        match self {
-            &IntercrateAmbiguityCause::DownstreamCrate { ref trait_desc, ref self_desc } => {
-                let self_desc = if let &Some(ref ty) = self_desc {
-                    format!(" for type `{}`", ty)
-                } else {
-                    String::new()
-                };
-                format!("downstream crates may implement trait `{}`{}", trait_desc, self_desc)
-            }
-            &IntercrateAmbiguityCause::UpstreamCrateUpdate { ref trait_desc, ref self_desc } => {
-                let self_desc = if let &Some(ref ty) = self_desc {
-                    format!(" for type `{}`", ty)
-                } else {
-                    String::new()
-                };
-                format!(
-                    "upstream crates may add a new impl of trait `{}`{} \
-                     in future versions",
-                    trait_desc, self_desc
-                )
-            }
-            &IntercrateAmbiguityCause::ReservationImpl { ref message } => message.clone(),
-        }
-    }
-}
diff --git a/src/librustc_middle/traits/structural_impls.rs b/src/librustc_middle/traits/structural_impls.rs
index 18b4371053a..d73fc628ceb 100644
--- a/src/librustc_middle/traits/structural_impls.rs
+++ b/src/librustc_middle/traits/structural_impls.rs
@@ -1,8 +1,6 @@
 use crate::traits;
-use crate::ty::{Lift, TyCtxt};
 
 use std::fmt;
-use std::rc::Rc;
 
 // Structural impls for the structs in `traits`.
 
@@ -107,222 +105,7 @@ impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceTraitAliasData<'tcx,
 ///////////////////////////////////////////////////////////////////////////
 // Lift implementations
 
-impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
-    type Lifted = traits::SelectionError<'tcx>;
-    fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
-        match *self {
-            super::Unimplemented => Some(super::Unimplemented),
-            super::OutputTypeParameterMismatch(a, b, ref err) => {
-                tcx.lift(&(a, b)).and_then(|(a, b)| {
-                    tcx.lift(err).map(|err| super::OutputTypeParameterMismatch(a, b, err))
-                })
-            }
-            super::TraitNotObjectSafe(def_id) => Some(super::TraitNotObjectSafe(def_id)),
-            super::ConstEvalFailure(err) => Some(super::ConstEvalFailure(err)),
-            super::Overflow => Some(super::Overflow),
-        }
-    }
-}
-
-impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
-    type Lifted = traits::ObligationCauseCode<'tcx>;
-    fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
-        match *self {
-            super::ReturnNoExpression => Some(super::ReturnNoExpression),
-            super::MiscObligation => Some(super::MiscObligation),
-            super::SliceOrArrayElem => Some(super::SliceOrArrayElem),
-            super::TupleElem => Some(super::TupleElem),
-            super::ProjectionWf(proj) => tcx.lift(&proj).map(super::ProjectionWf),
-            super::ItemObligation(def_id) => Some(super::ItemObligation(def_id)),
-            super::BindingObligation(def_id, span) => Some(super::BindingObligation(def_id, span)),
-            super::ReferenceOutlivesReferent(ty) => {
-                tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
-            }
-            super::ObjectTypeBound(ty, r) => {
-                tcx.lift(&ty).and_then(|ty| tcx.lift(&r).map(|r| super::ObjectTypeBound(ty, r)))
-            }
-            super::ObjectCastObligation(ty) => tcx.lift(&ty).map(super::ObjectCastObligation),
-            super::Coercion { source, target } => {
-                Some(super::Coercion { source: tcx.lift(&source)?, target: tcx.lift(&target)? })
-            }
-            super::AssignmentLhsSized => Some(super::AssignmentLhsSized),
-            super::TupleInitializerSized => Some(super::TupleInitializerSized),
-            super::StructInitializerSized => Some(super::StructInitializerSized),
-            super::VariableType(id) => Some(super::VariableType(id)),
-            super::ReturnValue(id) => Some(super::ReturnValue(id)),
-            super::ReturnType => Some(super::ReturnType),
-            super::SizedArgumentType(sp) => Some(super::SizedArgumentType(sp)),
-            super::SizedReturnType => Some(super::SizedReturnType),
-            super::SizedYieldType => Some(super::SizedYieldType),
-            super::InlineAsmSized => Some(super::InlineAsmSized),
-            super::RepeatVec(suggest_flag) => Some(super::RepeatVec(suggest_flag)),
-            super::FieldSized { adt_kind, span, last } => {
-                Some(super::FieldSized { adt_kind, span, last })
-            }
-            super::ConstSized => Some(super::ConstSized),
-            super::ConstPatternStructural => Some(super::ConstPatternStructural),
-            super::SharedStatic => Some(super::SharedStatic),
-            super::BuiltinDerivedObligation(ref cause) => {
-                tcx.lift(cause).map(super::BuiltinDerivedObligation)
-            }
-            super::ImplDerivedObligation(ref cause) => {
-                tcx.lift(cause).map(super::ImplDerivedObligation)
-            }
-            super::DerivedObligation(ref cause) => tcx.lift(cause).map(super::DerivedObligation),
-            super::CompareImplConstObligation => Some(super::CompareImplConstObligation),
-            super::CompareImplMethodObligation {
-                item_name,
-                impl_item_def_id,
-                trait_item_def_id,
-            } => Some(super::CompareImplMethodObligation {
-                item_name,
-                impl_item_def_id,
-                trait_item_def_id,
-            }),
-            super::CompareImplTypeObligation { item_name, impl_item_def_id, trait_item_def_id } => {
-                Some(super::CompareImplTypeObligation {
-                    item_name,
-                    impl_item_def_id,
-                    trait_item_def_id,
-                })
-            }
-            super::ExprAssignable => Some(super::ExprAssignable),
-            super::MatchExpressionArm(box super::MatchExpressionArmCause {
-                arm_span,
-                source,
-                ref prior_arms,
-                last_ty,
-                scrut_hir_id,
-            }) => tcx.lift(&last_ty).map(|last_ty| {
-                super::MatchExpressionArm(box super::MatchExpressionArmCause {
-                    arm_span,
-                    source,
-                    prior_arms: prior_arms.clone(),
-                    last_ty,
-                    scrut_hir_id,
-                })
-            }),
-            super::Pattern { span, root_ty, origin_expr } => {
-                tcx.lift(&root_ty).map(|root_ty| super::Pattern { span, root_ty, origin_expr })
-            }
-            super::IfExpression(box super::IfExpressionCause { then, outer, semicolon }) => {
-                Some(super::IfExpression(box super::IfExpressionCause { then, outer, semicolon }))
-            }
-            super::IfExpressionWithNoElse => Some(super::IfExpressionWithNoElse),
-            super::MainFunctionType => Some(super::MainFunctionType),
-            super::StartFunctionType => Some(super::StartFunctionType),
-            super::IntrinsicType => Some(super::IntrinsicType),
-            super::MethodReceiver => Some(super::MethodReceiver),
-            super::UnifyReceiver(ref ctxt) => tcx.lift(ctxt).map(|ctxt| super::UnifyReceiver(ctxt)),
-            super::BlockTailExpression(id) => Some(super::BlockTailExpression(id)),
-            super::TrivialBound => Some(super::TrivialBound),
-        }
-    }
-}
-
-impl<'a, 'tcx> Lift<'tcx> for traits::UnifyReceiverContext<'a> {
-    type Lifted = traits::UnifyReceiverContext<'tcx>;
-    fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
-        tcx.lift(&self.param_env).and_then(|param_env| {
-            tcx.lift(&self.substs).map(|substs| traits::UnifyReceiverContext {
-                assoc_item: self.assoc_item,
-                param_env,
-                substs,
-            })
-        })
-    }
-}
-
-impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
-    type Lifted = traits::DerivedObligationCause<'tcx>;
-    fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
-        tcx.lift(&self.parent_trait_ref).and_then(|trait_ref| {
-            tcx.lift(&*self.parent_code).map(|code| traits::DerivedObligationCause {
-                parent_trait_ref: trait_ref,
-                parent_code: Rc::new(code),
-            })
-        })
-    }
-}
-
-impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
-    type Lifted = traits::ObligationCause<'tcx>;
-    fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
-        tcx.lift(&self.code).map(|code| traits::ObligationCause::new(self.span, self.body_id, code))
-    }
-}
-
-// For codegen only.
-impl<'a, 'tcx> Lift<'tcx> for traits::ImplSource<'a, ()> {
-    type Lifted = traits::ImplSource<'tcx, ()>;
-    fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
-        match self.clone() {
-            traits::ImplSourceUserDefined(traits::ImplSourceUserDefinedData {
-                impl_def_id,
-                substs,
-                nested,
-            }) => tcx.lift(&substs).map(|substs| {
-                traits::ImplSourceUserDefined(traits::ImplSourceUserDefinedData {
-                    impl_def_id,
-                    substs,
-                    nested,
-                })
-            }),
-            traits::ImplSourceAutoImpl(t) => Some(traits::ImplSourceAutoImpl(t)),
-            traits::ImplSourceGenerator(traits::ImplSourceGeneratorData {
-                generator_def_id,
-                substs,
-                nested,
-            }) => tcx.lift(&substs).map(|substs| {
-                traits::ImplSourceGenerator(traits::ImplSourceGeneratorData {
-                    generator_def_id,
-                    substs,
-                    nested,
-                })
-            }),
-            traits::ImplSourceClosure(traits::ImplSourceClosureData {
-                closure_def_id,
-                substs,
-                nested,
-            }) => tcx.lift(&substs).map(|substs| {
-                traits::ImplSourceClosure(traits::ImplSourceClosureData {
-                    closure_def_id,
-                    substs,
-                    nested,
-                })
-            }),
-            traits::ImplSourceFnPointer(traits::ImplSourceFnPointerData { fn_ty, nested }) => {
-                tcx.lift(&fn_ty).map(|fn_ty| {
-                    traits::ImplSourceFnPointer(traits::ImplSourceFnPointerData { fn_ty, nested })
-                })
-            }
-            traits::ImplSourceDiscriminantKind(traits::ImplSourceDiscriminantKindData) => {
-                Some(traits::ImplSourceDiscriminantKind(traits::ImplSourceDiscriminantKindData))
-            }
-            traits::ImplSourceParam(n) => Some(traits::ImplSourceParam(n)),
-            traits::ImplSourceBuiltin(n) => Some(traits::ImplSourceBuiltin(n)),
-            traits::ImplSourceObject(traits::ImplSourceObjectData {
-                upcast_trait_ref,
-                vtable_base,
-                nested,
-            }) => tcx.lift(&upcast_trait_ref).map(|trait_ref| {
-                traits::ImplSourceObject(traits::ImplSourceObjectData {
-                    upcast_trait_ref: trait_ref,
-                    vtable_base,
-                    nested,
-                })
-            }),
-            traits::ImplSourceTraitAlias(traits::ImplSourceTraitAliasData {
-                alias_def_id,
-                substs,
-                nested,
-            }) => tcx.lift(&substs).map(|substs| {
-                traits::ImplSourceTraitAlias(traits::ImplSourceTraitAliasData {
-                    alias_def_id,
-                    substs,
-                    nested,
-                })
-            }),
-        }
-    }
+CloneTypeFoldableAndLiftImpls! {
+    super::IfExpressionCause,
+    super::ImplSourceDiscriminantKindData,
 }
diff --git a/src/librustc_middle/ty/structural_impls.rs b/src/librustc_middle/ty/structural_impls.rs
index 21b8d7101a3..dfa9e38a466 100644
--- a/src/librustc_middle/ty/structural_impls.rs
+++ b/src/librustc_middle/ty/structural_impls.rs
@@ -282,6 +282,7 @@ CloneTypeFoldableAndLiftImpls! {
     ::rustc_hir::def::Res,
     ::rustc_hir::def_id::DefId,
     ::rustc_hir::def_id::LocalDefId,
+    ::rustc_hir::HirId,
     ::rustc_hir::LlvmInlineAsmInner,
     ::rustc_hir::MatchSource,
     ::rustc_hir::Mutability,
@@ -298,6 +299,7 @@ CloneTypeFoldableAndLiftImpls! {
     // really meant to be folded. In general, we can only fold a fully
     // general `Region`.
     crate::ty::BoundRegion,
+    crate::ty::AssocItem,
     crate::ty::Placeholder<crate::ty::BoundRegion>,
     crate::ty::ClosureKind,
     crate::ty::FreeRegion,
diff --git a/src/librustc_query_system/cache.rs b/src/librustc_query_system/cache.rs
new file mode 100644
index 00000000000..be3d3607728
--- /dev/null
+++ b/src/librustc_query_system/cache.rs
@@ -0,0 +1,62 @@
+//! Cache for candidate selection.
+
+use crate::dep_graph::DepNodeIndex;
+use crate::query::QueryContext;
+
+use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::sync::HashMapExt;
+use rustc_data_structures::sync::Lock;
+
+use std::hash::Hash;
+
+#[derive(Clone)]
+pub struct Cache<Key, Value> {
+    hashmap: Lock<FxHashMap<Key, WithDepNode<Value>>>,
+}
+
+impl<Key, Value> Default for Cache<Key, Value> {
+    fn default() -> Self {
+        Self { hashmap: Default::default() }
+    }
+}
+
+impl<Key, Value> Cache<Key, Value> {
+    /// Actually frees the underlying memory in contrast to what stdlib containers do on `clear`
+    pub fn clear(&self) {
+        *self.hashmap.borrow_mut() = Default::default();
+    }
+}
+
+impl<Key: Eq + Hash, Value: Clone> Cache<Key, Value> {
+    pub fn get<CTX: QueryContext>(&self, key: &Key, tcx: CTX) -> Option<Value> {
+        Some(self.hashmap.borrow().get(key)?.get(tcx))
+    }
+
+    pub fn insert(&self, key: Key, dep_node: DepNodeIndex, value: Value) {
+        self.hashmap.borrow_mut().insert(key, WithDepNode::new(dep_node, value));
+    }
+
+    pub fn insert_same(&self, key: Key, dep_node: DepNodeIndex, value: Value)
+    where
+        Value: Eq,
+    {
+        self.hashmap.borrow_mut().insert_same(key, WithDepNode::new(dep_node, value));
+    }
+}
+
+#[derive(Clone, Eq, PartialEq)]
+pub struct WithDepNode<T> {
+    dep_node: DepNodeIndex,
+    cached_value: T,
+}
+
+impl<T: Clone> WithDepNode<T> {
+    pub fn new(dep_node: DepNodeIndex, cached_value: T) -> Self {
+        WithDepNode { dep_node, cached_value }
+    }
+
+    pub fn get<CTX: QueryContext>(&self, tcx: CTX) -> T {
+        tcx.dep_graph().read_index(self.dep_node);
+        self.cached_value.clone()
+    }
+}
diff --git a/src/librustc_query_system/lib.rs b/src/librustc_query_system/lib.rs
index b7615b25c4a..4bbba7befe9 100644
--- a/src/librustc_query_system/lib.rs
+++ b/src/librustc_query_system/lib.rs
@@ -11,5 +11,6 @@ extern crate log;
 #[macro_use]
 extern crate rustc_data_structures;
 
+pub mod cache;
 pub mod dep_graph;
 pub mod query;
diff --git a/src/librustc_trait_selection/traits/select/mod.rs b/src/librustc_trait_selection/traits/select/mod.rs
index 4123f293826..75e11619924 100644
--- a/src/librustc_trait_selection/traits/select/mod.rs
+++ b/src/librustc_trait_selection/traits/select/mod.rs
@@ -51,6 +51,47 @@ pub use rustc_middle::traits::select::*;
 mod candidate_assembly;
 mod confirmation;
 
+#[derive(Clone, Debug)]
+pub enum IntercrateAmbiguityCause {
+    DownstreamCrate { trait_desc: String, self_desc: Option<String> },
+    UpstreamCrateUpdate { trait_desc: String, self_desc: Option<String> },
+    ReservationImpl { message: String },
+}
+
+impl IntercrateAmbiguityCause {
+    /// Emits notes when the overlap is caused by complex intercrate ambiguities.
+    /// See #23980 for details.
+    pub fn add_intercrate_ambiguity_hint(&self, err: &mut rustc_errors::DiagnosticBuilder<'_>) {
+        err.note(&self.intercrate_ambiguity_hint());
+    }
+
+    pub fn intercrate_ambiguity_hint(&self) -> String {
+        match self {
+            &IntercrateAmbiguityCause::DownstreamCrate { ref trait_desc, ref self_desc } => {
+                let self_desc = if let &Some(ref ty) = self_desc {
+                    format!(" for type `{}`", ty)
+                } else {
+                    String::new()
+                };
+                format!("downstream crates may implement trait `{}`{}", trait_desc, self_desc)
+            }
+            &IntercrateAmbiguityCause::UpstreamCrateUpdate { ref trait_desc, ref self_desc } => {
+                let self_desc = if let &Some(ref ty) = self_desc {
+                    format!(" for type `{}`", ty)
+                } else {
+                    String::new()
+                };
+                format!(
+                    "upstream crates may add a new impl of trait `{}`{} \
+                     in future versions",
+                    trait_desc, self_desc
+                )
+            }
+            &IntercrateAmbiguityCause::ReservationImpl { ref message } => message.clone(),
+        }
+    }
+}
+
 pub struct SelectionContext<'cx, 'tcx> {
     infcx: &'cx InferCtxt<'cx, 'tcx>,
 
@@ -833,17 +874,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     ) -> Option<EvaluationResult> {
         let tcx = self.tcx();
         if self.can_use_global_caches(param_env) {
-            let cache = tcx.evaluation_cache.hashmap.borrow();
-            if let Some(cached) = cache.get(&param_env.and(trait_ref)) {
-                return Some(cached.get(tcx));
+            if let Some(res) = tcx.evaluation_cache.get(&param_env.and(trait_ref), tcx) {
+                return Some(res);
             }
         }
-        self.infcx
-            .evaluation_cache
-            .hashmap
-            .borrow()
-            .get(&param_env.and(trait_ref))
-            .map(|v| v.get(tcx))
+        self.infcx.evaluation_cache.get(&param_env.and(trait_ref), tcx)
     }
 
     fn insert_evaluation_cache(
@@ -869,21 +904,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // FIXME: Due to #50507 this overwrites the different values
                 // This should be changed to use HashMapExt::insert_same
                 // when that is fixed
-                self.tcx()
-                    .evaluation_cache
-                    .hashmap
-                    .borrow_mut()
-                    .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, result));
+                self.tcx().evaluation_cache.insert(param_env.and(trait_ref), dep_node, result);
                 return;
             }
         }
 
         debug!("insert_evaluation_cache(trait_ref={:?}, candidate={:?})", trait_ref, result,);
-        self.infcx
-            .evaluation_cache
-            .hashmap
-            .borrow_mut()
-            .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, result));
+        self.infcx.evaluation_cache.insert(param_env.and(trait_ref), dep_node, result);
     }
 
     /// For various reasons, it's possible for a subobligation
@@ -1180,17 +1207,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let tcx = self.tcx();
         let trait_ref = &cache_fresh_trait_pred.skip_binder().trait_ref;
         if self.can_use_global_caches(param_env) {
-            let cache = tcx.selection_cache.hashmap.borrow();
-            if let Some(cached) = cache.get(&param_env.and(*trait_ref)) {
-                return Some(cached.get(tcx));
+            if let Some(res) = tcx.selection_cache.get(&param_env.and(*trait_ref), tcx) {
+                return Some(res);
             }
         }
-        self.infcx
-            .selection_cache
-            .hashmap
-            .borrow()
-            .get(&param_env.and(*trait_ref))
-            .map(|v| v.get(tcx))
+        self.infcx.selection_cache.get(&param_env.and(*trait_ref), tcx)
     }
 
     /// Determines whether can we safely cache the result
@@ -1248,10 +1269,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         trait_ref, candidate,
                     );
                     // This may overwrite the cache with the same value.
-                    tcx.selection_cache
-                        .hashmap
-                        .borrow_mut()
-                        .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, candidate));
+                    tcx.selection_cache.insert(param_env.and(trait_ref), dep_node, candidate);
                     return;
                 }
             }
@@ -1261,11 +1279,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             "insert_candidate_cache(trait_ref={:?}, candidate={:?}) local",
             trait_ref, candidate,
         );
-        self.infcx
-            .selection_cache
-            .hashmap
-            .borrow_mut()
-            .insert(param_env.and(trait_ref), WithDepNode::new(dep_node, candidate));
+        self.infcx.selection_cache.insert(param_env.and(trait_ref), dep_node, candidate);
     }
 
     fn match_projection_obligation_against_definition_bounds(