Track causes for universes created during borrowck

9 files changed, 329 insertions, 129 deletions

diff --git a/compiler/rustc_infer/src/infer/mod.rs b/compiler/rustc_infer/src/infer/mod.rs
index 930d9e7d7c5..8c7a792eaa2 100644
--- a/compiler/rustc_infer/src/infer/mod.rs
+++ b/compiler/rustc_infer/src/infer/mod.rs
@@ -1506,7 +1506,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         self.inner.borrow_mut().projection_cache().clear();
     }
 
-    fn universe(&self) -> ty::UniverseIndex {
+    pub fn universe(&self) -> ty::UniverseIndex {
         self.universe.get()
     }
 
diff --git a/compiler/rustc_mir/src/borrow_check/diagnostics/bound_region_errors.rs b/compiler/rustc_mir/src/borrow_check/diagnostics/bound_region_errors.rs
new file mode 100644
index 00000000000..c771b71fc7f
--- /dev/null
+++ b/compiler/rustc_mir/src/borrow_check/diagnostics/bound_region_errors.rs
@@ -0,0 +1,110 @@
+use rustc_infer::infer::canonical::Canonical;
+use rustc_middle::ty::{self, Ty, TypeFoldable};
+use rustc_span::Span;
+use rustc_trait_selection::traits::query::type_op;
+
+use std::fmt;
+use std::rc::Rc;
+
+use crate::borrow_check::region_infer::values::RegionElement;
+use crate::borrow_check::MirBorrowckCtxt;
+
+#[derive(Clone)]
+crate struct UniverseInfo<'tcx>(UniverseInfoInner<'tcx>);
+
+/// What operation a universe was created for.
+#[derive(Clone)]
+enum UniverseInfoInner<'tcx> {
+    /// Relating two types which have binders.
+    RelateTys { expected: Ty<'tcx>, found: Ty<'tcx> },
+    /// Created from performing a `TypeOp`.
+    TypeOp(Rc<dyn TypeOpInfo<'tcx> + 'tcx>),
+    /// Any other reason.
+    Other,
+}
+
+impl UniverseInfo<'tcx> {
+    crate fn other() -> UniverseInfo<'tcx> {
+        UniverseInfo(UniverseInfoInner::Other)
+    }
+
+    crate fn relate(expected: Ty<'tcx>, found: Ty<'tcx>) -> UniverseInfo<'tcx> {
+        UniverseInfo(UniverseInfoInner::RelateTys { expected, found })
+    }
+
+    crate fn _report_error(
+        &self,
+        _mbcx: &mut MirBorrowckCtxt<'_, 'tcx>,
+        _placeholder: ty::PlaceholderRegion,
+        _error_element: RegionElement,
+        _span: Span,
+    ) {
+        todo!();
+    }
+}
+
+crate trait ToUniverseInfo<'tcx> {
+    fn to_universe_info(self, base_universe: ty::UniverseIndex) -> UniverseInfo<'tcx>;
+}
+
+impl<'tcx> ToUniverseInfo<'tcx>
+    for Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::prove_predicate::ProvePredicate<'tcx>>>
+{
+    fn to_universe_info(self, base_universe: ty::UniverseIndex) -> UniverseInfo<'tcx> {
+        UniverseInfo(UniverseInfoInner::TypeOp(Rc::new(PredicateQuery {
+            _canonical_query: self,
+            _base_universe: base_universe,
+        })))
+    }
+}
+
+impl<'tcx, T: Copy + fmt::Display + TypeFoldable<'tcx> + 'tcx> ToUniverseInfo<'tcx>
+    for Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Normalize<T>>>
+{
+    fn to_universe_info(self, base_universe: ty::UniverseIndex) -> UniverseInfo<'tcx> {
+        UniverseInfo(UniverseInfoInner::TypeOp(Rc::new(NormalizeQuery {
+            _canonical_query: self,
+            _base_universe: base_universe,
+        })))
+    }
+}
+
+impl<'tcx> ToUniverseInfo<'tcx>
+    for Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::AscribeUserType<'tcx>>>
+{
+    fn to_universe_info(self, _base_universe: ty::UniverseIndex) -> UniverseInfo<'tcx> {
+        // Ascribe user type isn't usually called on types that have different
+        // bound regions.
+        UniverseInfo::other()
+    }
+}
+
+impl<'tcx, F, G> ToUniverseInfo<'tcx> for Canonical<'tcx, type_op::custom::CustomTypeOp<F, G>> {
+    fn to_universe_info(self, _base_universe: ty::UniverseIndex) -> UniverseInfo<'tcx> {
+        // We can't rerun custom type ops.
+        UniverseInfo::other()
+    }
+}
+
+#[allow(unused_lifetimes)]
+trait TypeOpInfo<'tcx> {
+    // TODO: Methods for rerunning type op and reporting an error
+}
+
+struct PredicateQuery<'tcx> {
+    _canonical_query:
+        Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::prove_predicate::ProvePredicate<'tcx>>>,
+    _base_universe: ty::UniverseIndex,
+}
+
+impl TypeOpInfo<'tcx> for PredicateQuery<'tcx> {}
+
+struct NormalizeQuery<'tcx, T> {
+    _canonical_query: Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Normalize<T>>>,
+    _base_universe: ty::UniverseIndex,
+}
+
+impl<T> TypeOpInfo<'tcx> for NormalizeQuery<'tcx, T> where
+    T: Copy + fmt::Display + TypeFoldable<'tcx> + 'tcx
+{
+}
diff --git a/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs b/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs
index 1bb8c7ebe5a..55c6410ed32 100644
--- a/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs
+++ b/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs
@@ -28,12 +28,14 @@ mod outlives_suggestion;
 mod region_name;
 mod var_name;
 
+mod bound_region_errors;
 mod conflict_errors;
 mod explain_borrow;
 mod move_errors;
 mod mutability_errors;
 mod region_errors;
 
+crate use bound_region_errors::{ToUniverseInfo, UniverseInfo};
 crate use mutability_errors::AccessKind;
 crate use outlives_suggestion::OutlivesSuggestionBuilder;
 crate use region_errors::{ErrorConstraintInfo, RegionErrorKind, RegionErrors};
diff --git a/compiler/rustc_mir/src/borrow_check/nll.rs b/compiler/rustc_mir/src/borrow_check/nll.rs
index bfeafa33a91..7df4f5cfdb6 100644
--- a/compiler/rustc_mir/src/borrow_check/nll.rs
+++ b/compiler/rustc_mir/src/borrow_check/nll.rs
@@ -239,6 +239,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
         outlives_constraints,
         member_constraints,
         closure_bounds_mapping,
+        universe_causes,
         type_tests,
     } = constraints;
     let placeholder_indices = Rc::new(placeholder_indices);
@@ -260,6 +261,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
         outlives_constraints,
         member_constraints,
         closure_bounds_mapping,
+        universe_causes,
         type_tests,
         liveness_constraints,
         elements,
diff --git a/compiler/rustc_mir/src/borrow_check/region_infer/mod.rs b/compiler/rustc_mir/src/borrow_check/region_infer/mod.rs
index 3fe02ece06d..bd6831108dc 100644
--- a/compiler/rustc_mir/src/borrow_check/region_infer/mod.rs
+++ b/compiler/rustc_mir/src/borrow_check/region_infer/mod.rs
@@ -21,7 +21,7 @@ use crate::borrow_check::{
     constraints::{
         graph::NormalConstraintGraph, ConstraintSccIndex, OutlivesConstraint, OutlivesConstraintSet,
     },
-    diagnostics::{RegionErrorKind, RegionErrors},
+    diagnostics::{RegionErrorKind, RegionErrors, UniverseInfo},
     member_constraints::{MemberConstraintSet, NllMemberConstraintIndex},
     nll::{PoloniusOutput, ToRegionVid},
     region_infer::reverse_sccs::ReverseSccGraph,
@@ -84,6 +84,9 @@ pub struct RegionInferenceContext<'tcx> {
     closure_bounds_mapping:
         FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>>,
 
+    /// Map universe indexes to information on why we created it.
+    _universe_causes: IndexVec<ty::UniverseIndex, UniverseInfo<'tcx>>,
+
     /// Contains the minimum universe of any variable within the same
     /// SCC. We will ensure that no SCC contains values that are not
     /// visible from this index.
@@ -253,6 +256,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             Location,
             FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>,
         >,
+        universe_causes: IndexVec<ty::UniverseIndex, UniverseInfo<'tcx>>,
         type_tests: Vec<TypeTest<'tcx>>,
         liveness_constraints: LivenessValues<RegionVid>,
         elements: &Rc<RegionValueElements>,
@@ -293,6 +297,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             member_constraints,
             member_constraints_applied: Vec::new(),
             closure_bounds_mapping,
+            _universe_causes: universe_causes,
             scc_universes,
             scc_representatives,
             scc_values,
diff --git a/compiler/rustc_mir/src/borrow_check/type_check/canonical.rs b/compiler/rustc_mir/src/borrow_check/type_check/canonical.rs
new file mode 100644
index 00000000000..9fafcfafe67
--- /dev/null
+++ b/compiler/rustc_mir/src/borrow_check/type_check/canonical.rs
@@ -0,0 +1,158 @@
+use std::fmt;
+
+use rustc_hir as hir;
+use rustc_infer::infer::canonical::Canonical;
+use rustc_infer::traits::query::NoSolution;
+use rustc_middle::mir::ConstraintCategory;
+use rustc_middle::ty::{self, ToPredicate, TypeFoldable};
+use rustc_span::Span;
+use rustc_trait_selection::traits::query::type_op::{self, TypeOpOutput};
+use rustc_trait_selection::traits::query::Fallible;
+
+use crate::borrow_check::diagnostics::{ToUniverseInfo, UniverseInfo};
+
+use super::{Locations, NormalizeLocation, TypeChecker};
+
+impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
+    /// Given some operation `op` that manipulates types, proves
+    /// predicates, or otherwise uses the inference context, executes
+    /// `op` and then executes all the further obligations that `op`
+    /// returns. This will yield a set of outlives constraints amongst
+    /// regions which are extracted and stored as having occurred at
+    /// `locations`.
+    ///
+    /// **Any `rustc_infer::infer` operations that might generate region
+    /// constraints should occur within this method so that those
+    /// constraints can be properly localized!**
+    pub(super) fn fully_perform_op<R, Op>(
+        &mut self,
+        locations: Locations,
+        category: ConstraintCategory,
+        op: Op,
+    ) -> Fallible<R>
+    where
+        Op: type_op::TypeOp<'tcx, Output = R>,
+        Canonical<'tcx, Op>: ToUniverseInfo<'tcx>,
+    {
+        let old_universe = self.infcx.universe();
+
+        let TypeOpOutput { output, constraints, canonicalized_query } =
+            op.fully_perform(self.infcx)?;
+
+        if let Some(data) = &constraints {
+            self.push_region_constraints(locations, category, data);
+        }
+
+        let universe = self.infcx.universe();
+
+        if old_universe != universe {
+            let universe_info = match canonicalized_query {
+                Some(canonicalized_query) => canonicalized_query.to_universe_info(old_universe),
+                None => UniverseInfo::other(),
+            };
+            for u in old_universe..universe {
+                let info_universe =
+                    self.borrowck_context.constraints.universe_causes.push(universe_info.clone());
+                assert_eq!(u.as_u32() + 1, info_universe.as_u32());
+            }
+        }
+
+        Ok(output)
+    }
+
+    pub(super) fn instantiate_canonical_with_fresh_inference_vars<T>(
+        &mut self,
+        span: Span,
+        canonical: &Canonical<'tcx, T>,
+    ) -> T
+    where
+        T: TypeFoldable<'tcx>,
+    {
+        let (instantiated, _) =
+            self.infcx.instantiate_canonical_with_fresh_inference_vars(span, canonical);
+
+        for _ in 0..canonical.max_universe.as_u32() {
+            let info = UniverseInfo::other();
+            self.borrowck_context.constraints.universe_causes.push(info);
+        }
+
+        instantiated
+    }
+
+    pub(super) fn prove_trait_ref(
+        &mut self,
+        trait_ref: ty::TraitRef<'tcx>,
+        locations: Locations,
+        category: ConstraintCategory,
+    ) {
+        self.prove_predicates(
+            Some(ty::PredicateKind::Trait(ty::TraitPredicate {
+                trait_ref,
+                constness: hir::Constness::NotConst,
+            })),
+            locations,
+            category,
+        );
+    }
+
+    pub(super) fn normalize_and_prove_instantiated_predicates(
+        &mut self,
+        instantiated_predicates: ty::InstantiatedPredicates<'tcx>,
+        locations: Locations,
+    ) {
+        for predicate in instantiated_predicates.predicates {
+            let predicate = self.normalize(predicate, locations);
+            self.prove_predicate(predicate, locations, ConstraintCategory::Boring);
+        }
+    }
+
+    pub(super) fn prove_predicates(
+        &mut self,
+        predicates: impl IntoIterator<Item = impl ToPredicate<'tcx>>,
+        locations: Locations,
+        category: ConstraintCategory,
+    ) {
+        for predicate in predicates {
+            let predicate = predicate.to_predicate(self.tcx());
+            debug!("prove_predicates(predicate={:?}, locations={:?})", predicate, locations,);
+
+            self.prove_predicate(predicate, locations, category);
+        }
+    }
+
+    pub(super) fn prove_predicate(
+        &mut self,
+        predicate: ty::Predicate<'tcx>,
+        locations: Locations,
+        category: ConstraintCategory,
+    ) {
+        debug!("prove_predicate(predicate={:?}, location={:?})", predicate, locations,);
+
+        let param_env = self.param_env;
+        self.fully_perform_op(
+            locations,
+            category,
+            param_env.and(type_op::prove_predicate::ProvePredicate::new(predicate)),
+        )
+        .unwrap_or_else(|NoSolution| {
+            span_mirbug!(self, NoSolution, "could not prove {:?}", predicate);
+        })
+    }
+
+    pub(super) fn normalize<T>(&mut self, value: T, location: impl NormalizeLocation) -> T
+    where
+        T: type_op::normalize::Normalizable<'tcx> + fmt::Display + Copy + 'tcx,
+    {
+        debug!("normalize(value={:?}, location={:?})", value, location);
+        let param_env = self.param_env;
+        self.fully_perform_op(
+            location.to_locations(),
+            ConstraintCategory::Boring,
+            param_env.and(type_op::normalize::Normalize::new(value)),
+        )
+        .unwrap_or_else(|NoSolution| {
+            span_mirbug!(self, NoSolution, "failed to normalize `{:?}`", value);
+            value
+        })
+    }
+}
diff --git a/compiler/rustc_mir/src/borrow_check/type_check/input_output.rs b/compiler/rustc_mir/src/borrow_check/type_check/input_output.rs
index 37e0643228a..f8989a7d9df 100644
--- a/compiler/rustc_mir/src/borrow_check/type_check/input_output.rs
+++ b/compiler/rustc_mir/src/borrow_check/type_check/input_output.rs
@@ -44,7 +44,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                     // Instantiate the canonicalized variables from
                     // user-provided signature (e.g., the `_` in the code
                     // above) with fresh variables.
-                    let (poly_sig, _) = self.infcx.instantiate_canonical_with_fresh_inference_vars(
+                    let poly_sig = self.instantiate_canonical_with_fresh_inference_vars(
                         body.span,
                         &user_provided_poly_sig,
                     );
diff --git a/compiler/rustc_mir/src/borrow_check/type_check/mod.rs b/compiler/rustc_mir/src/borrow_check/type_check/mod.rs
index e7cd98e1cc9..b6b25a75991 100644
--- a/compiler/rustc_mir/src/borrow_check/type_check/mod.rs
+++ b/compiler/rustc_mir/src/borrow_check/type_check/mod.rs
@@ -38,9 +38,8 @@ use rustc_trait_selection::opaque_types::{GenerateMemberConstraints, InferCtxtEx
 use rustc_trait_selection::traits::error_reporting::InferCtxtExt as _;
 use rustc_trait_selection::traits::query::type_op;
 use rustc_trait_selection::traits::query::type_op::custom::CustomTypeOp;
-use rustc_trait_selection::traits::query::{Fallible, NoSolution};
+use rustc_trait_selection::traits::query::Fallible;
 use rustc_trait_selection::traits::{self, ObligationCause, PredicateObligations};
-use type_op::TypeOpOutput;
 
 use crate::dataflow::impls::MaybeInitializedPlaces;
 use crate::dataflow::move_paths::MoveData;
@@ -52,6 +51,7 @@ use crate::transform::{
 use crate::borrow_check::{
     borrow_set::BorrowSet,
     constraints::{OutlivesConstraint, OutlivesConstraintSet},
+    diagnostics::UniverseInfo,
     facts::AllFacts,
     location::LocationTable,
     member_constraints::MemberConstraintSet,
@@ -90,6 +90,7 @@ macro_rules! span_mirbug_and_err {
     })
 }
 
+mod canonical;
 mod constraint_conversion;
 pub mod free_region_relations;
 mod input_output;
@@ -143,6 +144,7 @@ pub(crate) fn type_check<'mir, 'tcx>(
         member_constraints: MemberConstraintSet::default(),
         closure_bounds_mapping: Default::default(),
         type_tests: Vec::default(),
+        universe_causes: IndexVec::from_elem_n(UniverseInfo::other(), 1),
     };
 
     let CreateResult {
@@ -157,6 +159,11 @@ pub(crate) fn type_check<'mir, 'tcx>(
         &mut constraints,
     );
 
+    for _ in ty::UniverseIndex::ROOT..infcx.universe() {
+        let info = UniverseInfo::other();
+        constraints.universe_causes.push(info);
+    }
+
     let mut borrowck_context = BorrowCheckContext {
         universal_regions,
         location_table,
@@ -377,8 +384,8 @@ impl<'a, 'b, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'tcx> {
                                      ty,
                                      san_ty| {
                         if let Err(terr) = verifier.cx.eq_types(
-                            san_ty,
                             ty,
+                            san_ty,
                             location.to_locations(),
                             ConstraintCategory::Boring,
                         ) {
@@ -426,8 +433,8 @@ impl<'a, 'b, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'tcx> {
                 let literal_ty = constant.literal.ty().builtin_deref(true).unwrap().ty;
 
                 if let Err(terr) = self.cx.eq_types(
-                    normalized_ty,
                     literal_ty,
+                    normalized_ty,
                     locations,
                     ConstraintCategory::Boring,
                 ) {
@@ -543,7 +550,7 @@ impl<'a, 'b, 'tcx> TypeVerifier<'a, 'b, 'tcx> {
                     return PlaceTy::from_ty(self.tcx().ty_error());
                 }
             }
-            place_ty = self.sanitize_projection(place_ty, elem, place, location)
+            place_ty = self.sanitize_projection(place_ty, elem, place, location);
         }
 
         if let PlaceContext::NonMutatingUse(NonMutatingUseContext::Copy) = context {
@@ -917,6 +924,8 @@ crate struct MirTypeckRegionConstraints<'tcx> {
     crate closure_bounds_mapping:
         FxHashMap<Location, FxHashMap<(RegionVid, RegionVid), (ConstraintCategory, Span)>>,
 
+    crate universe_causes: IndexVec<ty::UniverseIndex, UniverseInfo<'tcx>>,
+
     crate type_tests: Vec<TypeTest<'tcx>>,
 }
 
@@ -1044,8 +1053,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         );
         for user_annotation in self.user_type_annotations {
             let CanonicalUserTypeAnnotation { span, ref user_ty, inferred_ty } = *user_annotation;
-            let (annotation, _) =
-                self.infcx.instantiate_canonical_with_fresh_inference_vars(span, user_ty);
+            let annotation = self.instantiate_canonical_with_fresh_inference_vars(span, user_ty);
             match annotation {
                 UserType::Ty(mut ty) => {
                     ty = self.normalize(ty, Locations::All(span));
@@ -1098,31 +1106,6 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         }
     }
 
-    /// Given some operation `op` that manipulates types, proves
-    /// predicates, or otherwise uses the inference context, executes
-    /// `op` and then executes all the further obligations that `op`
-    /// returns. This will yield a set of outlives constraints amongst
-    /// regions which are extracted and stored as having occurred at
-    /// `locations`.
-    ///
-    /// **Any `rustc_infer::infer` operations that might generate region
-    /// constraints should occur within this method so that those
-    /// constraints can be properly localized!**
-    fn fully_perform_op<R>(
-        &mut self,
-        locations: Locations,
-        category: ConstraintCategory,
-        op: impl type_op::TypeOp<'tcx, Output = R>,
-    ) -> Fallible<R> {
-        let TypeOpOutput { output, constraints, .. } = op.fully_perform(self.infcx)?;
-
-        if let Some(data) = &constraints {
-            self.push_region_constraints(locations, category, data);
-        }
-
-        Ok(output)
-    }
-
     fn push_region_constraints(
         &mut self,
         locations: Locations,
@@ -1174,17 +1157,19 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         locations: Locations,
         category: ConstraintCategory,
     ) -> Fallible<()> {
-        self.relate_types(sub, ty::Variance::Covariant, sup, locations, category)
+        // Use this order of parameters because the sup type is usually the
+        // "expected" type in diagnostics.
+        self.relate_types(sup, ty::Variance::Contravariant, sub, locations, category)
     }
 
     fn eq_types(
         &mut self,
-        a: Ty<'tcx>,
-        b: Ty<'tcx>,
+        expected: Ty<'tcx>,
+        found: Ty<'tcx>,
         locations: Locations,
         category: ConstraintCategory,
     ) -> Fallible<()> {
-        self.relate_types(a, ty::Variance::Invariant, b, locations, category)
+        self.relate_types(expected, ty::Variance::Invariant, found, locations, category)
     }
 
     fn relate_type_and_user_type(
@@ -1223,7 +1208,7 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         );
 
         let ty = curr_projected_ty.ty;
-        self.relate_types(a, v, ty, locations, category)?;
+        self.relate_types(ty, v.xform(ty::Variance::Contravariant), a, locations, category)?;
 
         Ok(())
     }
@@ -2054,8 +2039,8 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                         let ty_fn_ptr_from = tcx.mk_fn_ptr(fn_sig);
 
                         if let Err(terr) = self.eq_types(
-                            ty_fn_ptr_from,
                             ty,
+                            ty_fn_ptr_from,
                             location.to_locations(),
                             ConstraintCategory::Cast,
                         ) {
@@ -2078,8 +2063,8 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                         let ty_fn_ptr_from = tcx.mk_fn_ptr(tcx.signature_unclosure(sig, *unsafety));
 
                         if let Err(terr) = self.eq_types(
-                            ty_fn_ptr_from,
                             ty,
+                            ty_fn_ptr_from,
                             location.to_locations(),
                             ConstraintCategory::Cast,
                         ) {
@@ -2107,8 +2092,8 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                         let ty_fn_ptr_from = tcx.safe_to_unsafe_fn_ty(fn_sig);
 
                         if let Err(terr) = self.eq_types(
-                            ty_fn_ptr_from,
                             ty,
+                            ty_fn_ptr_from,
                             location.to_locations(),
                             ConstraintCategory::Cast,
                         ) {
@@ -2295,20 +2280,18 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
                             kind: TypeVariableOriginKind::MiscVariable,
                             span: body.source_info(location).span,
                         });
-                        self.relate_types(
-                            common_ty,
-                            ty::Variance::Contravariant,
+                        self.sub_types(
                             ty_left,
+                            common_ty,
                             location.to_locations(),
                             ConstraintCategory::Boring,
                         )
                         .unwrap_or_else(|err| {
                             bug!("Could not equate type variable with {:?}: {:?}", ty_left, err)
                         });
-                        if let Err(terr) = self.relate_types(
-                            common_ty,
-                            ty::Variance::Contravariant,
+                        if let Err(terr) = self.sub_types(
                             ty_right,
+                            common_ty,
                             location.to_locations(),
                             ConstraintCategory::Boring,
                         ) {
@@ -2683,66 +2666,6 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
         tcx.predicates_of(def_id).instantiate(tcx, substs)
     }
 
-    fn prove_trait_ref(
-        &mut self,
-        trait_ref: ty::TraitRef<'tcx>,
-        locations: Locations,
-        category: ConstraintCategory,
-    ) {
-        self.prove_predicates(
-            Some(ty::PredicateKind::Trait(ty::TraitPredicate {
-                trait_ref,
-                constness: hir::Constness::NotConst,
-            })),
-            locations,
-            category,
-        );
-    }
-
-    fn normalize_and_prove_instantiated_predicates(
-        &mut self,
-        instantiated_predicates: ty::InstantiatedPredicates<'tcx>,
-        locations: Locations,
-    ) {
-        for predicate in instantiated_predicates.predicates {
-            let predicate = self.normalize(predicate, locations);
-            self.prove_predicate(predicate, locations, ConstraintCategory::Boring);
-        }
-    }
-
-    fn prove_predicates(
-        &mut self,
-        predicates: impl IntoIterator<Item = impl ToPredicate<'tcx>>,
-        locations: Locations,
-        category: ConstraintCategory,
-    ) {
-        for predicate in predicates {
-            let predicate = predicate.to_predicate(self.tcx());
-            debug!("prove_predicates(predicate={:?}, locations={:?})", predicate, locations,);
-
-            self.prove_predicate(predicate, locations, category);
-        }
-    }
-
-    fn prove_predicate(
-        &mut self,
-        predicate: ty::Predicate<'tcx>,
-        locations: Locations,
-        category: ConstraintCategory,
-    ) {
-        debug!("prove_predicate(predicate={:?}, location={:?})", predicate, locations,);
-
-        let param_env = self.param_env;
-        self.fully_perform_op(
-            locations,
-            category,
-            param_env.and(type_op::prove_predicate::ProvePredicate::new(predicate)),
-        )
-        .unwrap_or_else(|NoSolution| {
-            span_mirbug!(self, NoSolution, "could not prove {:?}", predicate);
-        })
-    }
-
     fn typeck_mir(&mut self, body: &Body<'tcx>) {
         self.last_span = body.span;
         debug!("run_on_mir: {:?}", body.span);
@@ -2765,23 +2688,6 @@ impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
             self.check_iscleanup(&body, block_data);
         }
     }
-
-    fn normalize<T>(&mut self, value: T, location: impl NormalizeLocation) -> T
-    where
-        T: type_op::normalize::Normalizable<'tcx> + Copy + 'tcx,
-    {
-        debug!("normalize(value={:?}, location={:?})", value, location);
-        let param_env = self.param_env;
-        self.fully_perform_op(
-            location.to_locations(),
-            ConstraintCategory::Boring,
-            param_env.and(type_op::normalize::Normalize::new(value)),
-        )
-        .unwrap_or_else(|NoSolution| {
-            span_mirbug!(self, NoSolution, "failed to normalize `{:?}`", value);
-            value
-        })
-    }
 }
 
 trait NormalizeLocation: fmt::Debug + Copy {
diff --git a/compiler/rustc_mir/src/borrow_check/type_check/relate_tys.rs b/compiler/rustc_mir/src/borrow_check/type_check/relate_tys.rs
index 6e07a90f04b..971c4daa6b3 100644
--- a/compiler/rustc_mir/src/borrow_check/type_check/relate_tys.rs
+++ b/compiler/rustc_mir/src/borrow_check/type_check/relate_tys.rs
@@ -6,6 +6,7 @@ use rustc_middle::ty::{self, Const, Ty};
 use rustc_trait_selection::traits::query::Fallible;
 
 use crate::borrow_check::constraints::OutlivesConstraint;
+use crate::borrow_check::diagnostics::UniverseInfo;
 use crate::borrow_check::type_check::{BorrowCheckContext, Locations};
 
 /// Adds sufficient constraints to ensure that `a R b` where `R` depends on `v`:
@@ -29,7 +30,14 @@ pub(super) fn relate_types<'tcx>(
     debug!("relate_types(a={:?}, v={:?}, b={:?}, locations={:?})", a, v, b, locations);
     TypeRelating::new(
         infcx,
-        NllTypeRelatingDelegate::new(infcx, borrowck_context, param_env, locations, category),
+        NllTypeRelatingDelegate::new(
+            infcx,
+            borrowck_context,
+            param_env,
+            locations,
+            category,
+            UniverseInfo::relate(a, b),
+        ),
         v,
     )
     .relate(a, b)?;
@@ -47,6 +55,10 @@ struct NllTypeRelatingDelegate<'me, 'bccx, 'tcx> {
 
     /// What category do we assign the resulting `'a: 'b` relationships?
     category: ConstraintCategory,
+
+    /// Information so that error reporting knows what types we are relating
+    /// when reporting a bound region error.
+    universe_info: UniverseInfo<'tcx>,
 }
 
 impl NllTypeRelatingDelegate<'me, 'bccx, 'tcx> {
@@ -56,8 +68,9 @@ impl NllTypeRelatingDelegate<'me, 'bccx, 'tcx> {
         param_env: ty::ParamEnv<'tcx>,
         locations: Locations,
         category: ConstraintCategory,
+        universe_info: UniverseInfo<'tcx>,
     ) -> Self {
-        Self { infcx, borrowck_context, param_env, locations, category }
+        Self { infcx, borrowck_context, param_env, locations, category, universe_info }
     }
 }
 
@@ -67,7 +80,11 @@ impl TypeRelatingDelegate<'tcx> for NllTypeRelatingDelegate<'_, '_, 'tcx> {
     }
 
     fn create_next_universe(&mut self) -> ty::UniverseIndex {
-        self.infcx.create_next_universe()
+        let info_universe =
+            self.borrowck_context.constraints.universe_causes.push(self.universe_info.clone());
+        let universe = self.infcx.create_next_universe();
+        assert_eq!(info_universe, universe);
+        universe
     }
 
     fn next_existential_region_var(&mut self, from_forall: bool) -> ty::Region<'tcx> {