Merging upstream version 1.76.0+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

10 files changed, 2868 insertions, 0 deletions

diff --git a/compiler/rustc_infer/src/infer/relate/combine.rs b/compiler/rustc_infer/src/infer/relate/combine.rs
new file mode 100644
index 000000000..ee911c432
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/combine.rs
@@ -0,0 +1,613 @@
+//! There are four type combiners: [Equate], [Sub], [Lub], and [Glb].
+//! Each implements the trait [TypeRelation] and contains methods for
+//! combining two instances of various things and yielding a new instance.
+//! These combiner methods always yield a `Result<T>`. To relate two
+//! types, you can use `infcx.at(cause, param_env)` which then allows
+//! you to use the relevant methods of [At](crate::infer::at::At).
+//!
+//! Combiners mostly do their specific behavior and then hand off the
+//! bulk of the work to [InferCtxt::super_combine_tys] and
+//! [InferCtxt::super_combine_consts].
+//!
+//! Combining two types may have side-effects on the inference contexts
+//! which can be undone by using snapshots. You probably want to use
+//! either [InferCtxt::commit_if_ok] or [InferCtxt::probe].
+//!
+//! On success, the  LUB/GLB operations return the appropriate bound. The
+//! return value of `Equate` or `Sub` shouldn't really be used.
+//!
+//! ## Contravariance
+//!
+//! We explicitly track which argument is expected using
+//! [TypeRelation::a_is_expected], so when dealing with contravariance
+//! this should be correctly updated.
+
+use super::equate::Equate;
+use super::generalize::{self, CombineDelegate, Generalization};
+use super::glb::Glb;
+use super::lub::Lub;
+use super::sub::Sub;
+use crate::infer::{DefineOpaqueTypes, InferCtxt, TypeTrace};
+use crate::traits::{Obligation, PredicateObligations};
+use rustc_middle::infer::canonical::OriginalQueryValues;
+use rustc_middle::infer::unify_key::{ConstVarValue, ConstVariableValue, EffectVarValue};
+use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
+use rustc_middle::ty::error::{ExpectedFound, TypeError};
+use rustc_middle::ty::relate::{RelateResult, TypeRelation};
+use rustc_middle::ty::{self, InferConst, ToPredicate, Ty, TyCtxt, TypeVisitableExt};
+use rustc_middle::ty::{AliasRelationDirection, TyVar};
+use rustc_middle::ty::{IntType, UintType};
+use rustc_span::DUMMY_SP;
+
+#[derive(Clone)]
+pub struct CombineFields<'infcx, 'tcx> {
+    pub infcx: &'infcx InferCtxt<'tcx>,
+    pub trace: TypeTrace<'tcx>,
+    pub cause: Option<ty::relate::Cause>,
+    pub param_env: ty::ParamEnv<'tcx>,
+    pub obligations: PredicateObligations<'tcx>,
+    pub define_opaque_types: DefineOpaqueTypes,
+}
+
+impl<'tcx> InferCtxt<'tcx> {
+    pub fn super_combine_tys<R>(
+        &self,
+        relation: &mut R,
+        a: Ty<'tcx>,
+        b: Ty<'tcx>,
+    ) -> RelateResult<'tcx, Ty<'tcx>>
+    where
+        R: ObligationEmittingRelation<'tcx>,
+    {
+        let a_is_expected = relation.a_is_expected();
+        debug_assert!(!a.has_escaping_bound_vars());
+        debug_assert!(!b.has_escaping_bound_vars());
+
+        match (a.kind(), b.kind()) {
+            // Relate integral variables to other types
+            (&ty::Infer(ty::IntVar(a_id)), &ty::Infer(ty::IntVar(b_id))) => {
+                self.inner
+                    .borrow_mut()
+                    .int_unification_table()
+                    .unify_var_var(a_id, b_id)
+                    .map_err(|e| int_unification_error(a_is_expected, e))?;
+                Ok(a)
+            }
+            (&ty::Infer(ty::IntVar(v_id)), &ty::Int(v)) => {
+                self.unify_integral_variable(a_is_expected, v_id, IntType(v))
+            }
+            (&ty::Int(v), &ty::Infer(ty::IntVar(v_id))) => {
+                self.unify_integral_variable(!a_is_expected, v_id, IntType(v))
+            }
+            (&ty::Infer(ty::IntVar(v_id)), &ty::Uint(v)) => {
+                self.unify_integral_variable(a_is_expected, v_id, UintType(v))
+            }
+            (&ty::Uint(v), &ty::Infer(ty::IntVar(v_id))) => {
+                self.unify_integral_variable(!a_is_expected, v_id, UintType(v))
+            }
+
+            // Relate floating-point variables to other types
+            (&ty::Infer(ty::FloatVar(a_id)), &ty::Infer(ty::FloatVar(b_id))) => {
+                self.inner
+                    .borrow_mut()
+                    .float_unification_table()
+                    .unify_var_var(a_id, b_id)
+                    .map_err(|e| float_unification_error(a_is_expected, e))?;
+                Ok(a)
+            }
+            (&ty::Infer(ty::FloatVar(v_id)), &ty::Float(v)) => {
+                self.unify_float_variable(a_is_expected, v_id, v)
+            }
+            (&ty::Float(v), &ty::Infer(ty::FloatVar(v_id))) => {
+                self.unify_float_variable(!a_is_expected, v_id, v)
+            }
+
+            // We don't expect `TyVar` or `Fresh*` vars at this point with lazy norm.
+            (ty::Alias(..), ty::Infer(ty::TyVar(_))) | (ty::Infer(ty::TyVar(_)), ty::Alias(..))
+                if self.next_trait_solver() =>
+            {
+                bug!(
+                    "We do not expect to encounter `TyVar` this late in combine \
+                    -- they should have been handled earlier"
+                )
+            }
+            (_, ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)))
+            | (ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)), _)
+                if self.next_trait_solver() =>
+            {
+                bug!("We do not expect to encounter `Fresh` variables in the new solver")
+            }
+
+            (_, ty::Alias(..)) | (ty::Alias(..), _) if self.next_trait_solver() => {
+                relation.register_type_relate_obligation(a, b);
+                Ok(a)
+            }
+
+            // All other cases of inference are errors
+            (&ty::Infer(_), _) | (_, &ty::Infer(_)) => {
+                Err(TypeError::Sorts(ty::relate::expected_found(relation, a, b)))
+            }
+
+            // During coherence, opaque types should be treated as *possibly*
+            // equal to any other type (except for possibly itself). This is an
+            // extremely heavy hammer, but can be relaxed in a fowards-compatible
+            // way later.
+            (&ty::Alias(ty::Opaque, _), _) | (_, &ty::Alias(ty::Opaque, _)) if self.intercrate => {
+                relation.register_predicates([ty::Binder::dummy(ty::PredicateKind::Ambiguous)]);
+                Ok(a)
+            }
+
+            _ => ty::relate::structurally_relate_tys(relation, a, b),
+        }
+    }
+
+    pub fn super_combine_consts<R>(
+        &self,
+        relation: &mut R,
+        a: ty::Const<'tcx>,
+        b: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>>
+    where
+        R: ObligationEmittingRelation<'tcx>,
+    {
+        debug!("{}.consts({:?}, {:?})", relation.tag(), a, b);
+        debug_assert!(!a.has_escaping_bound_vars());
+        debug_assert!(!b.has_escaping_bound_vars());
+        if a == b {
+            return Ok(a);
+        }
+
+        let a = self.shallow_resolve(a);
+        let b = self.shallow_resolve(b);
+
+        // We should never have to relate the `ty` field on `Const` as it is checked elsewhere that consts have the
+        // correct type for the generic param they are an argument for. However there have been a number of cases
+        // historically where asserting that the types are equal has found bugs in the compiler so this is valuable
+        // to check even if it is a bit nasty impl wise :(
+        //
+        // This probe is probably not strictly necessary but it seems better to be safe and not accidentally find
+        // ourselves with a check to find bugs being required for code to compile because it made inference progress.
+        let compatible_types = self.probe(|_| {
+            if a.ty() == b.ty() {
+                return Ok(());
+            }
+
+            // We don't have access to trait solving machinery in `rustc_infer` so the logic for determining if the
+            // two const param's types are able to be equal has to go through a canonical query with the actual logic
+            // in `rustc_trait_selection`.
+            let canonical = self.canonicalize_query(
+                relation.param_env().and((a.ty(), b.ty())),
+                &mut OriginalQueryValues::default(),
+            );
+            self.tcx.check_tys_might_be_eq(canonical).map_err(|_| {
+                self.tcx.sess.span_delayed_bug(
+                    DUMMY_SP,
+                    format!("cannot relate consts of different types (a={a:?}, b={b:?})",),
+                )
+            })
+        });
+
+        // If the consts have differing types, just bail with a const error with
+        // the expected const's type. Specifically, we don't want const infer vars
+        // to do any type shapeshifting before and after resolution.
+        if let Err(guar) = compatible_types {
+            // HACK: equating both sides with `[const error]` eagerly prevents us
+            // from leaving unconstrained inference vars during things like impl
+            // matching in the solver.
+            let a_error = ty::Const::new_error(self.tcx, guar, a.ty());
+            if let ty::ConstKind::Infer(InferConst::Var(vid)) = a.kind() {
+                return self.unify_const_variable(vid, a_error, relation.param_env());
+            }
+            let b_error = ty::Const::new_error(self.tcx, guar, b.ty());
+            if let ty::ConstKind::Infer(InferConst::Var(vid)) = b.kind() {
+                return self.unify_const_variable(vid, b_error, relation.param_env());
+            }
+
+            return Ok(if relation.a_is_expected() { a_error } else { b_error });
+        }
+
+        match (a.kind(), b.kind()) {
+            (
+                ty::ConstKind::Infer(InferConst::Var(a_vid)),
+                ty::ConstKind::Infer(InferConst::Var(b_vid)),
+            ) => {
+                self.inner.borrow_mut().const_unification_table().union(a_vid, b_vid);
+                return Ok(a);
+            }
+
+            (
+                ty::ConstKind::Infer(InferConst::EffectVar(a_vid)),
+                ty::ConstKind::Infer(InferConst::EffectVar(b_vid)),
+            ) => {
+                self.inner
+                    .borrow_mut()
+                    .effect_unification_table()
+                    .unify_var_var(a_vid, b_vid)
+                    .map_err(|a| effect_unification_error(self.tcx, relation.a_is_expected(), a))?;
+                return Ok(a);
+            }
+
+            // All other cases of inference with other variables are errors.
+            (
+                ty::ConstKind::Infer(InferConst::Var(_) | InferConst::EffectVar(_)),
+                ty::ConstKind::Infer(_),
+            )
+            | (
+                ty::ConstKind::Infer(_),
+                ty::ConstKind::Infer(InferConst::Var(_) | InferConst::EffectVar(_)),
+            ) => {
+                bug!(
+                    "tried to combine ConstKind::Infer/ConstKind::Infer(InferConst::Var): {a:?} and {b:?}"
+                )
+            }
+
+            (ty::ConstKind::Infer(InferConst::Var(vid)), _) => {
+                return self.unify_const_variable(vid, b, relation.param_env());
+            }
+
+            (_, ty::ConstKind::Infer(InferConst::Var(vid))) => {
+                return self.unify_const_variable(vid, a, relation.param_env());
+            }
+
+            (ty::ConstKind::Infer(InferConst::EffectVar(vid)), _) => {
+                return self.unify_effect_variable(
+                    relation.a_is_expected(),
+                    vid,
+                    EffectVarValue::Const(b),
+                );
+            }
+
+            (_, ty::ConstKind::Infer(InferConst::EffectVar(vid))) => {
+                return self.unify_effect_variable(
+                    !relation.a_is_expected(),
+                    vid,
+                    EffectVarValue::Const(a),
+                );
+            }
+
+            (ty::ConstKind::Unevaluated(..), _) | (_, ty::ConstKind::Unevaluated(..))
+                if self.tcx.features().generic_const_exprs || self.next_trait_solver() =>
+            {
+                let (a, b) = if relation.a_is_expected() { (a, b) } else { (b, a) };
+
+                relation.register_predicates([ty::Binder::dummy(if self.next_trait_solver() {
+                    ty::PredicateKind::AliasRelate(
+                        a.into(),
+                        b.into(),
+                        ty::AliasRelationDirection::Equate,
+                    )
+                } else {
+                    ty::PredicateKind::ConstEquate(a, b)
+                })]);
+
+                return Ok(b);
+            }
+            _ => {}
+        }
+
+        ty::relate::structurally_relate_consts(relation, a, b)
+    }
+
+    /// Unifies the const variable `target_vid` with the given constant.
+    ///
+    /// This also tests if the given const `ct` contains an inference variable which was previously
+    /// unioned with `target_vid`. If this is the case, inferring `target_vid` to `ct`
+    /// would result in an infinite type as we continuously replace an inference variable
+    /// in `ct` with `ct` itself.
+    ///
+    /// This is especially important as unevaluated consts use their parents generics.
+    /// They therefore often contain unused args, making these errors far more likely.
+    ///
+    /// A good example of this is the following:
+    ///
+    /// ```compile_fail,E0308
+    /// #![feature(generic_const_exprs)]
+    ///
+    /// fn bind<const N: usize>(value: [u8; N]) -> [u8; 3 + 4] {
+    ///     todo!()
+    /// }
+    ///
+    /// fn main() {
+    ///     let mut arr = Default::default();
+    ///     arr = bind(arr);
+    /// }
+    /// ```
+    ///
+    /// Here `3 + 4` ends up as `ConstKind::Unevaluated` which uses the generics
+    /// of `fn bind` (meaning that its args contain `N`).
+    ///
+    /// `bind(arr)` now infers that the type of `arr` must be `[u8; N]`.
+    /// The assignment `arr = bind(arr)` now tries to equate `N` with `3 + 4`.
+    ///
+    /// As `3 + 4` contains `N` in its args, this must not succeed.
+    ///
+    /// See `tests/ui/const-generics/occurs-check/` for more examples where this is relevant.
+    #[instrument(level = "debug", skip(self))]
+    fn unify_const_variable(
+        &self,
+        target_vid: ty::ConstVid,
+        ct: ty::Const<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        let span =
+            self.inner.borrow_mut().const_unification_table().probe_value(target_vid).origin.span;
+        // FIXME(generic_const_exprs): Occurs check failures for unevaluated
+        // constants and generic expressions are not yet handled correctly.
+        let Generalization { value_may_be_infer: value, needs_wf: _ } = generalize::generalize(
+            self,
+            &mut CombineDelegate { infcx: self, span, param_env },
+            ct,
+            target_vid,
+            ty::Variance::Invariant,
+        )?;
+
+        self.inner.borrow_mut().const_unification_table().union_value(
+            target_vid,
+            ConstVarValue {
+                origin: ConstVariableOrigin {
+                    kind: ConstVariableOriginKind::ConstInference,
+                    span: DUMMY_SP,
+                },
+                val: ConstVariableValue::Known { value },
+            },
+        );
+        Ok(value)
+    }
+
+    fn unify_integral_variable(
+        &self,
+        vid_is_expected: bool,
+        vid: ty::IntVid,
+        val: ty::IntVarValue,
+    ) -> RelateResult<'tcx, Ty<'tcx>> {
+        self.inner
+            .borrow_mut()
+            .int_unification_table()
+            .unify_var_value(vid, Some(val))
+            .map_err(|e| int_unification_error(vid_is_expected, e))?;
+        match val {
+            IntType(v) => Ok(Ty::new_int(self.tcx, v)),
+            UintType(v) => Ok(Ty::new_uint(self.tcx, v)),
+        }
+    }
+
+    fn unify_float_variable(
+        &self,
+        vid_is_expected: bool,
+        vid: ty::FloatVid,
+        val: ty::FloatTy,
+    ) -> RelateResult<'tcx, Ty<'tcx>> {
+        self.inner
+            .borrow_mut()
+            .float_unification_table()
+            .unify_var_value(vid, Some(ty::FloatVarValue(val)))
+            .map_err(|e| float_unification_error(vid_is_expected, e))?;
+        Ok(Ty::new_float(self.tcx, val))
+    }
+
+    fn unify_effect_variable(
+        &self,
+        vid_is_expected: bool,
+        vid: ty::EffectVid,
+        val: EffectVarValue<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        self.inner
+            .borrow_mut()
+            .effect_unification_table()
+            .unify_var_value(vid, Some(val))
+            .map_err(|e| effect_unification_error(self.tcx, vid_is_expected, e))?;
+        Ok(val.as_const(self.tcx))
+    }
+}
+
+impl<'infcx, 'tcx> CombineFields<'infcx, 'tcx> {
+    pub fn tcx(&self) -> TyCtxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    pub fn equate<'a>(&'a mut self, a_is_expected: bool) -> Equate<'a, 'infcx, 'tcx> {
+        Equate::new(self, a_is_expected)
+    }
+
+    pub fn sub<'a>(&'a mut self, a_is_expected: bool) -> Sub<'a, 'infcx, 'tcx> {
+        Sub::new(self, a_is_expected)
+    }
+
+    pub fn lub<'a>(&'a mut self, a_is_expected: bool) -> Lub<'a, 'infcx, 'tcx> {
+        Lub::new(self, a_is_expected)
+    }
+
+    pub fn glb<'a>(&'a mut self, a_is_expected: bool) -> Glb<'a, 'infcx, 'tcx> {
+        Glb::new(self, a_is_expected)
+    }
+
+    /// Here, `dir` is either `EqTo`, `SubtypeOf`, or `SupertypeOf`.
+    /// The idea is that we should ensure that the type `a_ty` is equal
+    /// to, a subtype of, or a supertype of (respectively) the type
+    /// to which `b_vid` is bound.
+    ///
+    /// Since `b_vid` has not yet been instantiated with a type, we
+    /// will first instantiate `b_vid` with a *generalized* version
+    /// of `a_ty`. Generalization introduces other inference
+    /// variables wherever subtyping could occur.
+    #[instrument(skip(self), level = "debug")]
+    pub fn instantiate(
+        &mut self,
+        a_ty: Ty<'tcx>,
+        ambient_variance: ty::Variance,
+        b_vid: ty::TyVid,
+        a_is_expected: bool,
+    ) -> RelateResult<'tcx, ()> {
+        // Get the actual variable that b_vid has been inferred to
+        debug_assert!(self.infcx.inner.borrow_mut().type_variables().probe(b_vid).is_unknown());
+
+        // Generalize type of `a_ty` appropriately depending on the
+        // direction. As an example, assume:
+        //
+        // - `a_ty == &'x ?1`, where `'x` is some free region and `?1` is an
+        //   inference variable,
+        // - and `dir` == `SubtypeOf`.
+        //
+        // Then the generalized form `b_ty` would be `&'?2 ?3`, where
+        // `'?2` and `?3` are fresh region/type inference
+        // variables. (Down below, we will relate `a_ty <: b_ty`,
+        // adding constraints like `'x: '?2` and `?1 <: ?3`.)
+        let Generalization { value_may_be_infer: b_ty, needs_wf } = generalize::generalize(
+            self.infcx,
+            &mut CombineDelegate {
+                infcx: self.infcx,
+                param_env: self.param_env,
+                span: self.trace.span(),
+            },
+            a_ty,
+            b_vid,
+            ambient_variance,
+        )?;
+
+        // Constrain `b_vid` to the generalized type `b_ty`.
+        if let &ty::Infer(TyVar(b_ty_vid)) = b_ty.kind() {
+            self.infcx.inner.borrow_mut().type_variables().equate(b_vid, b_ty_vid);
+        } else {
+            self.infcx.inner.borrow_mut().type_variables().instantiate(b_vid, b_ty);
+        }
+
+        if needs_wf {
+            self.obligations.push(Obligation::new(
+                self.tcx(),
+                self.trace.cause.clone(),
+                self.param_env,
+                ty::Binder::dummy(ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(
+                    b_ty.into(),
+                ))),
+            ));
+        }
+
+        // Finally, relate `b_ty` to `a_ty`, as described in previous comment.
+        //
+        // FIXME(#16847): This code is non-ideal because all these subtype
+        // relations wind up attributed to the same spans. We need
+        // to associate causes/spans with each of the relations in
+        // the stack to get this right.
+        if b_ty.is_ty_var() {
+            // This happens for cases like `<?0 as Trait>::Assoc == ?0`.
+            // We can't instantiate `?0` here as that would result in a
+            // cyclic type. We instead delay the unification in case
+            // the alias can be normalized to something which does not
+            // mention `?0`.
+            if self.infcx.next_trait_solver() {
+                let (lhs, rhs, direction) = match ambient_variance {
+                    ty::Variance::Invariant => {
+                        (a_ty.into(), b_ty.into(), AliasRelationDirection::Equate)
+                    }
+                    ty::Variance::Covariant => {
+                        (a_ty.into(), b_ty.into(), AliasRelationDirection::Subtype)
+                    }
+                    ty::Variance::Contravariant => {
+                        (b_ty.into(), a_ty.into(), AliasRelationDirection::Subtype)
+                    }
+                    ty::Variance::Bivariant => unreachable!("bivariant generalization"),
+                };
+                self.obligations.push(Obligation::new(
+                    self.tcx(),
+                    self.trace.cause.clone(),
+                    self.param_env,
+                    ty::PredicateKind::AliasRelate(lhs, rhs, direction),
+                ));
+            } else {
+                match a_ty.kind() {
+                    &ty::Alias(ty::AliasKind::Projection, data) => {
+                        // FIXME: This does not handle subtyping correctly, we could
+                        // instead create a new inference variable for `a_ty`, emitting
+                        // `Projection(a_ty, a_infer)` and `a_infer <: b_ty`.
+                        self.obligations.push(Obligation::new(
+                            self.tcx(),
+                            self.trace.cause.clone(),
+                            self.param_env,
+                            ty::ProjectionPredicate { projection_ty: data, term: b_ty.into() },
+                        ))
+                    }
+                    // The old solver only accepts projection predicates for associated types.
+                    ty::Alias(
+                        ty::AliasKind::Inherent | ty::AliasKind::Weak | ty::AliasKind::Opaque,
+                        _,
+                    ) => return Err(TypeError::CyclicTy(a_ty)),
+                    _ => bug!("generalizated `{a_ty:?} to infer, not an alias"),
+                }
+            }
+        } else {
+            match ambient_variance {
+                ty::Variance::Invariant => self.equate(a_is_expected).relate(a_ty, b_ty),
+                ty::Variance::Covariant => self.sub(a_is_expected).relate(a_ty, b_ty),
+                ty::Variance::Contravariant => self.sub(a_is_expected).relate_with_variance(
+                    ty::Contravariant,
+                    ty::VarianceDiagInfo::default(),
+                    a_ty,
+                    b_ty,
+                ),
+                ty::Variance::Bivariant => unreachable!("bivariant generalization"),
+            }?;
+        }
+
+        Ok(())
+    }
+
+    pub fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
+        self.obligations.extend(obligations);
+    }
+
+    pub fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ToPredicate<'tcx>>) {
+        self.obligations.extend(obligations.into_iter().map(|to_pred| {
+            Obligation::new(self.infcx.tcx, self.trace.cause.clone(), self.param_env, to_pred)
+        }))
+    }
+}
+
+pub trait ObligationEmittingRelation<'tcx>: TypeRelation<'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx>;
+
+    /// Register obligations that must hold in order for this relation to hold
+    fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>);
+
+    /// Register predicates that must hold in order for this relation to hold. Uses
+    /// a default obligation cause, [`ObligationEmittingRelation::register_obligations`] should
+    /// be used if control over the obligation causes is required.
+    fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ToPredicate<'tcx>>);
+
+    /// Register an obligation that both types must be related to each other according to
+    /// the [`ty::AliasRelationDirection`] given by [`ObligationEmittingRelation::alias_relate_direction`]
+    fn register_type_relate_obligation(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) {
+        self.register_predicates([ty::Binder::dummy(ty::PredicateKind::AliasRelate(
+            a.into(),
+            b.into(),
+            self.alias_relate_direction(),
+        ))]);
+    }
+
+    /// Relation direction emitted for `AliasRelate` predicates, corresponding to the direction
+    /// of the relation.
+    fn alias_relate_direction(&self) -> ty::AliasRelationDirection;
+}
+
+fn int_unification_error<'tcx>(
+    a_is_expected: bool,
+    v: (ty::IntVarValue, ty::IntVarValue),
+) -> TypeError<'tcx> {
+    let (a, b) = v;
+    TypeError::IntMismatch(ExpectedFound::new(a_is_expected, a, b))
+}
+
+fn float_unification_error<'tcx>(
+    a_is_expected: bool,
+    v: (ty::FloatVarValue, ty::FloatVarValue),
+) -> TypeError<'tcx> {
+    let (ty::FloatVarValue(a), ty::FloatVarValue(b)) = v;
+    TypeError::FloatMismatch(ExpectedFound::new(a_is_expected, a, b))
+}
+
+fn effect_unification_error<'tcx>(
+    _tcx: TyCtxt<'tcx>,
+    _a_is_expected: bool,
+    (_a, _b): (EffectVarValue<'tcx>, EffectVarValue<'tcx>),
+) -> TypeError<'tcx> {
+    bug!("unexpected effect unification error")
+}
diff --git a/compiler/rustc_infer/src/infer/relate/equate.rs b/compiler/rustc_infer/src/infer/relate/equate.rs
new file mode 100644
index 000000000..cb62f2583
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/equate.rs
@@ -0,0 +1,188 @@
+use super::combine::{CombineFields, ObligationEmittingRelation};
+use crate::infer::{DefineOpaqueTypes, SubregionOrigin};
+use crate::traits::PredicateObligations;
+
+use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::GenericArgsRef;
+use rustc_middle::ty::TyVar;
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
+
+use rustc_hir::def_id::DefId;
+
+/// Ensures `a` is made equal to `b`. Returns `a` on success.
+pub struct Equate<'combine, 'infcx, 'tcx> {
+    fields: &'combine mut CombineFields<'infcx, 'tcx>,
+    a_is_expected: bool,
+}
+
+impl<'combine, 'infcx, 'tcx> Equate<'combine, 'infcx, 'tcx> {
+    pub fn new(
+        fields: &'combine mut CombineFields<'infcx, 'tcx>,
+        a_is_expected: bool,
+    ) -> Equate<'combine, 'infcx, 'tcx> {
+        Equate { fields, a_is_expected }
+    }
+}
+
+impl<'tcx> TypeRelation<'tcx> for Equate<'_, '_, 'tcx> {
+    fn tag(&self) -> &'static str {
+        "Equate"
+    }
+
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.fields.tcx()
+    }
+
+    fn a_is_expected(&self) -> bool {
+        self.a_is_expected
+    }
+
+    fn relate_item_args(
+        &mut self,
+        _item_def_id: DefId,
+        a_arg: GenericArgsRef<'tcx>,
+        b_arg: GenericArgsRef<'tcx>,
+    ) -> RelateResult<'tcx, GenericArgsRef<'tcx>> {
+        // N.B., once we are equating types, we don't care about
+        // variance, so don't try to lookup the variance here. This
+        // also avoids some cycles (e.g., #41849) since looking up
+        // variance requires computing types which can require
+        // performing trait matching (which then performs equality
+        // unification).
+
+        relate::relate_args_invariantly(self, a_arg, b_arg)
+    }
+
+    fn relate_with_variance<T: Relate<'tcx>>(
+        &mut self,
+        _: ty::Variance,
+        _info: ty::VarianceDiagInfo<'tcx>,
+        a: T,
+        b: T,
+    ) -> RelateResult<'tcx, T> {
+        self.relate(a, b)
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        if a == b {
+            return Ok(a);
+        }
+
+        trace!(a = ?a.kind(), b = ?b.kind());
+
+        let infcx = self.fields.infcx;
+
+        let a = infcx.inner.borrow_mut().type_variables().replace_if_possible(a);
+        let b = infcx.inner.borrow_mut().type_variables().replace_if_possible(b);
+
+        match (a.kind(), b.kind()) {
+            (&ty::Infer(TyVar(a_id)), &ty::Infer(TyVar(b_id))) => {
+                infcx.inner.borrow_mut().type_variables().equate(a_id, b_id);
+            }
+
+            (&ty::Infer(TyVar(a_id)), _) => {
+                self.fields.instantiate(b, ty::Invariant, a_id, self.a_is_expected)?;
+            }
+
+            (_, &ty::Infer(TyVar(b_id))) => {
+                self.fields.instantiate(a, ty::Invariant, b_id, self.a_is_expected)?;
+            }
+
+            (
+                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }),
+                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }),
+            ) if a_def_id == b_def_id => {
+                self.fields.infcx.super_combine_tys(self, a, b)?;
+            }
+            (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _)
+            | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }))
+                if self.fields.define_opaque_types == DefineOpaqueTypes::Yes
+                    && def_id.is_local()
+                    && !self.fields.infcx.next_trait_solver() =>
+            {
+                self.fields.obligations.extend(
+                    infcx
+                        .handle_opaque_type(
+                            a,
+                            b,
+                            self.a_is_expected(),
+                            &self.fields.trace.cause,
+                            self.param_env(),
+                        )?
+                        .obligations,
+                );
+            }
+            _ => {
+                self.fields.infcx.super_combine_tys(self, a, b)?;
+            }
+        }
+
+        Ok(a)
+    }
+
+    fn regions(
+        &mut self,
+        a: ty::Region<'tcx>,
+        b: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        debug!("{}.regions({:?}, {:?})", self.tag(), a, b);
+        let origin = SubregionOrigin::Subtype(Box::new(self.fields.trace.clone()));
+        self.fields
+            .infcx
+            .inner
+            .borrow_mut()
+            .unwrap_region_constraints()
+            .make_eqregion(origin, a, b);
+        Ok(a)
+    }
+
+    fn consts(
+        &mut self,
+        a: ty::Const<'tcx>,
+        b: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        self.fields.infcx.super_combine_consts(self, a, b)
+    }
+
+    fn binders<T>(
+        &mut self,
+        a: ty::Binder<'tcx, T>,
+        b: ty::Binder<'tcx, T>,
+    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+    where
+        T: Relate<'tcx>,
+    {
+        // A binder is equal to itself if it's structurally equal to itself
+        if a == b {
+            return Ok(a);
+        }
+
+        if a.skip_binder().has_escaping_bound_vars() || b.skip_binder().has_escaping_bound_vars() {
+            self.fields.higher_ranked_sub(a, b, self.a_is_expected)?;
+            self.fields.higher_ranked_sub(b, a, self.a_is_expected)?;
+        } else {
+            // Fast path for the common case.
+            self.relate(a.skip_binder(), b.skip_binder())?;
+        }
+        Ok(a)
+    }
+}
+
+impl<'tcx> ObligationEmittingRelation<'tcx> for Equate<'_, '_, 'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        self.fields.param_env
+    }
+
+    fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) {
+        self.fields.register_predicates(obligations);
+    }
+
+    fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
+        self.fields.register_obligations(obligations);
+    }
+
+    fn alias_relate_direction(&self) -> ty::AliasRelationDirection {
+        ty::AliasRelationDirection::Equate
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/relate/generalize.rs b/compiler/rustc_infer/src/infer/relate/generalize.rs
new file mode 100644
index 000000000..665af7381
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/generalize.rs
@@ -0,0 +1,551 @@
+use std::mem;
+
+use rustc_data_structures::sso::SsoHashMap;
+use rustc_hir::def_id::DefId;
+use rustc_middle::infer::unify_key::{ConstVarValue, ConstVariableValue};
+use rustc_middle::ty::error::TypeError;
+use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::visit::MaxUniverse;
+use rustc_middle::ty::{self, InferConst, Term, Ty, TyCtxt, TypeVisitable, TypeVisitableExt};
+use rustc_span::Span;
+
+use crate::infer::nll_relate::TypeRelatingDelegate;
+use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind, TypeVariableValue};
+use crate::infer::{InferCtxt, RegionVariableOrigin};
+
+/// Attempts to generalize `term` for the type variable `for_vid`.
+/// This checks for cycles -- that is, whether the type `term`
+/// references `for_vid`.
+pub fn generalize<'tcx, D: GeneralizerDelegate<'tcx>, T: Into<Term<'tcx>> + Relate<'tcx>>(
+    infcx: &InferCtxt<'tcx>,
+    delegate: &mut D,
+    term: T,
+    for_vid: impl Into<ty::TermVid>,
+    ambient_variance: ty::Variance,
+) -> RelateResult<'tcx, Generalization<T>> {
+    let (for_universe, root_vid) = match for_vid.into() {
+        ty::TermVid::Ty(ty_vid) => (
+            infcx.probe_ty_var(ty_vid).unwrap_err(),
+            ty::TermVid::Ty(infcx.inner.borrow_mut().type_variables().sub_root_var(ty_vid)),
+        ),
+        ty::TermVid::Const(ct_vid) => (
+            infcx.probe_const_var(ct_vid).unwrap_err(),
+            ty::TermVid::Const(infcx.inner.borrow_mut().const_unification_table().find(ct_vid).vid),
+        ),
+    };
+
+    let mut generalizer = Generalizer {
+        infcx,
+        delegate,
+        ambient_variance,
+        root_vid,
+        for_universe,
+        root_term: term.into(),
+        in_alias: false,
+        needs_wf: false,
+        cache: Default::default(),
+    };
+
+    assert!(!term.has_escaping_bound_vars());
+    let value_may_be_infer = generalizer.relate(term, term)?;
+    let needs_wf = generalizer.needs_wf;
+    Ok(Generalization { value_may_be_infer, needs_wf })
+}
+
+/// Abstracts the handling of region vars between HIR and MIR/NLL typechecking
+/// in the generalizer code.
+pub trait GeneralizerDelegate<'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx>;
+
+    fn forbid_inference_vars() -> bool;
+
+    fn span(&self) -> Span;
+
+    fn generalize_region(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>;
+}
+
+pub struct CombineDelegate<'cx, 'tcx> {
+    pub infcx: &'cx InferCtxt<'tcx>,
+    pub param_env: ty::ParamEnv<'tcx>,
+    pub span: Span,
+}
+
+impl<'tcx> GeneralizerDelegate<'tcx> for CombineDelegate<'_, 'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        self.param_env
+    }
+
+    fn forbid_inference_vars() -> bool {
+        false
+    }
+
+    fn span(&self) -> Span {
+        self.span
+    }
+
+    fn generalize_region(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx> {
+        // FIXME: This is non-ideal because we don't give a
+        // very descriptive origin for this region variable.
+        self.infcx
+            .next_region_var_in_universe(RegionVariableOrigin::MiscVariable(self.span), universe)
+    }
+}
+
+impl<'tcx, T> GeneralizerDelegate<'tcx> for T
+where
+    T: TypeRelatingDelegate<'tcx>,
+{
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        <Self as TypeRelatingDelegate<'tcx>>::param_env(self)
+    }
+
+    fn forbid_inference_vars() -> bool {
+        <Self as TypeRelatingDelegate<'tcx>>::forbid_inference_vars()
+    }
+
+    fn span(&self) -> Span {
+        <Self as TypeRelatingDelegate<'tcx>>::span(&self)
+    }
+
+    fn generalize_region(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx> {
+        <Self as TypeRelatingDelegate<'tcx>>::generalize_existential(self, universe)
+    }
+}
+
+/// The "generalizer" is used when handling inference variables.
+///
+/// The basic strategy for handling a constraint like `?A <: B` is to
+/// apply a "generalization strategy" to the term `B` -- this replaces
+/// all the lifetimes in the term `B` with fresh inference variables.
+/// (You can read more about the strategy in this [blog post].)
+///
+/// As an example, if we had `?A <: &'x u32`, we would generalize `&'x
+/// u32` to `&'0 u32` where `'0` is a fresh variable. This becomes the
+/// value of `A`. Finally, we relate `&'0 u32 <: &'x u32`, which
+/// establishes `'0: 'x` as a constraint.
+///
+/// [blog post]: https://is.gd/0hKvIr
+struct Generalizer<'me, 'tcx, D> {
+    infcx: &'me InferCtxt<'tcx>,
+
+    /// This is used to abstract the behaviors of the three previous
+    /// generalizer-like implementations (`Generalizer`, `TypeGeneralizer`,
+    /// and `ConstInferUnifier`). See [`GeneralizerDelegate`] for more
+    /// information.
+    delegate: &'me mut D,
+
+    /// After we generalize this type, we are going to relate it to
+    /// some other type. What will be the variance at this point?
+    ambient_variance: ty::Variance,
+
+    /// The vid of the type variable that is in the process of being
+    /// instantiated. If we find this within the value we are folding,
+    /// that means we would have created a cyclic value.
+    root_vid: ty::TermVid,
+
+    /// The universe of the type variable that is in the process of being
+    /// instantiated. If we find anything that this universe cannot name,
+    /// we reject the relation.
+    for_universe: ty::UniverseIndex,
+
+    /// The root term (const or type) we're generalizing. Used for cycle errors.
+    root_term: Term<'tcx>,
+
+    cache: SsoHashMap<Ty<'tcx>, Ty<'tcx>>,
+
+    /// This is set once we're generalizing the arguments of an alias.
+    ///
+    /// This is necessary to correctly handle
+    /// `<T as Bar<<?0 as Foo>::Assoc>::Assoc == ?0`. This equality can
+    /// hold by either normalizing the outer or the inner associated type.
+    in_alias: bool,
+
+    /// See the field `needs_wf` in `Generalization`.
+    needs_wf: bool,
+}
+
+impl<'tcx, D> Generalizer<'_, 'tcx, D> {
+    /// Create an error that corresponds to the term kind in `root_term`
+    fn cyclic_term_error(&self) -> TypeError<'tcx> {
+        match self.root_term.unpack() {
+            ty::TermKind::Ty(ty) => TypeError::CyclicTy(ty),
+            ty::TermKind::Const(ct) => TypeError::CyclicConst(ct),
+        }
+    }
+}
+
+impl<'tcx, D> TypeRelation<'tcx> for Generalizer<'_, 'tcx, D>
+where
+    D: GeneralizerDelegate<'tcx>,
+{
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    fn tag(&self) -> &'static str {
+        "Generalizer"
+    }
+
+    fn a_is_expected(&self) -> bool {
+        true
+    }
+
+    fn relate_item_args(
+        &mut self,
+        item_def_id: DefId,
+        a_subst: ty::GenericArgsRef<'tcx>,
+        b_subst: ty::GenericArgsRef<'tcx>,
+    ) -> RelateResult<'tcx, ty::GenericArgsRef<'tcx>> {
+        if self.ambient_variance == ty::Variance::Invariant {
+            // Avoid fetching the variance if we are in an invariant
+            // context; no need, and it can induce dependency cycles
+            // (e.g., #41849).
+            relate::relate_args_invariantly(self, a_subst, b_subst)
+        } else {
+            let tcx = self.tcx();
+            let opt_variances = tcx.variances_of(item_def_id);
+            relate::relate_args_with_variances(
+                self,
+                item_def_id,
+                opt_variances,
+                a_subst,
+                b_subst,
+                false,
+            )
+        }
+    }
+
+    #[instrument(level = "debug", skip(self, variance, b), ret)]
+    fn relate_with_variance<T: Relate<'tcx>>(
+        &mut self,
+        variance: ty::Variance,
+        _info: ty::VarianceDiagInfo<'tcx>,
+        a: T,
+        b: T,
+    ) -> RelateResult<'tcx, T> {
+        let old_ambient_variance = self.ambient_variance;
+        self.ambient_variance = self.ambient_variance.xform(variance);
+        debug!(?self.ambient_variance, "new ambient variance");
+        let r = self.relate(a, b)?;
+        self.ambient_variance = old_ambient_variance;
+        Ok(r)
+    }
+
+    #[instrument(level = "debug", skip(self, t2), ret)]
+    fn tys(&mut self, t: Ty<'tcx>, t2: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        assert_eq!(t, t2); // we are misusing TypeRelation here; both LHS and RHS ought to be ==
+
+        if let Some(&result) = self.cache.get(&t) {
+            return Ok(result);
+        }
+
+        // Check to see whether the type we are generalizing references
+        // any other type variable related to `vid` via
+        // subtyping. This is basically our "occurs check", preventing
+        // us from creating infinitely sized types.
+        let g = match *t.kind() {
+            ty::Infer(ty::TyVar(_)) | ty::Infer(ty::IntVar(_)) | ty::Infer(ty::FloatVar(_))
+                if D::forbid_inference_vars() =>
+            {
+                bug!("unexpected inference variable encountered in NLL generalization: {t}");
+            }
+
+            ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
+                bug!("unexpected infer type: {t}")
+            }
+
+            ty::Infer(ty::TyVar(vid)) => {
+                let mut inner = self.infcx.inner.borrow_mut();
+                let vid = inner.type_variables().root_var(vid);
+                let sub_vid = inner.type_variables().sub_root_var(vid);
+
+                if ty::TermVid::Ty(sub_vid) == self.root_vid {
+                    // If sub-roots are equal, then `root_vid` and
+                    // `vid` are related via subtyping.
+                    Err(self.cyclic_term_error())
+                } else {
+                    let probe = inner.type_variables().probe(vid);
+                    match probe {
+                        TypeVariableValue::Known { value: u } => {
+                            drop(inner);
+                            self.relate(u, u)
+                        }
+                        TypeVariableValue::Unknown { universe } => {
+                            match self.ambient_variance {
+                                // Invariant: no need to make a fresh type variable
+                                // if we can name the universe.
+                                ty::Invariant => {
+                                    if self.for_universe.can_name(universe) {
+                                        return Ok(t);
+                                    }
+                                }
+
+                                // Bivariant: make a fresh var, but we
+                                // may need a WF predicate. See
+                                // comment on `needs_wf` field for
+                                // more info.
+                                ty::Bivariant => self.needs_wf = true,
+
+                                // Co/contravariant: this will be
+                                // sufficiently constrained later on.
+                                ty::Covariant | ty::Contravariant => (),
+                            }
+
+                            let origin = inner.type_variables().var_origin(vid);
+                            let new_var_id =
+                                inner.type_variables().new_var(self.for_universe, origin);
+                            let u = Ty::new_var(self.tcx(), new_var_id);
+
+                            // Record that we replaced `vid` with `new_var_id` as part of a generalization
+                            // operation. This is needed to detect cyclic types. To see why, see the
+                            // docs in the `type_variables` module.
+                            inner.type_variables().sub(vid, new_var_id);
+                            debug!("replacing original vid={:?} with new={:?}", vid, u);
+                            Ok(u)
+                        }
+                    }
+                }
+            }
+
+            ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => {
+                // No matter what mode we are in,
+                // integer/floating-point types must be equal to be
+                // relatable.
+                Ok(t)
+            }
+
+            ty::Placeholder(placeholder) => {
+                if self.for_universe.can_name(placeholder.universe) {
+                    Ok(t)
+                } else {
+                    debug!(
+                        "root universe {:?} cannot name placeholder in universe {:?}",
+                        self.for_universe, placeholder.universe
+                    );
+                    Err(TypeError::Mismatch)
+                }
+            }
+
+            ty::Alias(kind, data) => {
+                // An occurs check failure inside of an alias does not mean
+                // that the types definitely don't unify. We may be able
+                // to normalize the alias after all.
+                //
+                // We handle this by lazily equating the alias and generalizing
+                // it to an inference variable.
+                let is_nested_alias = mem::replace(&mut self.in_alias, true);
+                let result = match self.relate(data, data) {
+                    Ok(data) => Ok(Ty::new_alias(self.tcx(), kind, data)),
+                    Err(e) => {
+                        if is_nested_alias {
+                            return Err(e);
+                        } else {
+                            let mut visitor = MaxUniverse::new();
+                            t.visit_with(&mut visitor);
+                            let infer_replacement_is_complete =
+                                self.for_universe.can_name(visitor.max_universe())
+                                    && !t.has_escaping_bound_vars();
+                            if !infer_replacement_is_complete {
+                                warn!("may incompletely handle alias type: {t:?}");
+                            }
+
+                            debug!("generalization failure in alias");
+                            Ok(self.infcx.next_ty_var_in_universe(
+                                TypeVariableOrigin {
+                                    kind: TypeVariableOriginKind::MiscVariable,
+                                    span: self.delegate.span(),
+                                },
+                                self.for_universe,
+                            ))
+                        }
+                    }
+                };
+                self.in_alias = is_nested_alias;
+                result
+            }
+
+            _ => relate::structurally_relate_tys(self, t, t),
+        }?;
+
+        self.cache.insert(t, g);
+        Ok(g)
+    }
+
+    #[instrument(level = "debug", skip(self, r2), ret)]
+    fn regions(
+        &mut self,
+        r: ty::Region<'tcx>,
+        r2: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        assert_eq!(r, r2); // we are misusing TypeRelation here; both LHS and RHS ought to be ==
+
+        match *r {
+            // Never make variables for regions bound within the type itself,
+            // nor for erased regions.
+            ty::ReBound(..) | ty::ReErased => {
+                return Ok(r);
+            }
+
+            // It doesn't really matter for correctness if we generalize ReError,
+            // since we're already on a doomed compilation path.
+            ty::ReError(_) => {
+                return Ok(r);
+            }
+
+            ty::RePlaceholder(..)
+            | ty::ReVar(..)
+            | ty::ReStatic
+            | ty::ReEarlyParam(..)
+            | ty::ReLateParam(..) => {
+                // see common code below
+            }
+        }
+
+        // If we are in an invariant context, we can re-use the region
+        // as is, unless it happens to be in some universe that we
+        // can't name.
+        if let ty::Invariant = self.ambient_variance {
+            let r_universe = self.infcx.universe_of_region(r);
+            if self.for_universe.can_name(r_universe) {
+                return Ok(r);
+            }
+        }
+
+        Ok(self.delegate.generalize_region(self.for_universe))
+    }
+
+    #[instrument(level = "debug", skip(self, c2), ret)]
+    fn consts(
+        &mut self,
+        c: ty::Const<'tcx>,
+        c2: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        assert_eq!(c, c2); // we are misusing TypeRelation here; both LHS and RHS ought to be ==
+
+        match c.kind() {
+            ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => {
+                bug!("unexpected inference variable encountered in NLL generalization: {:?}", c);
+            }
+            ty::ConstKind::Infer(InferConst::Var(vid)) => {
+                // If root const vids are equal, then `root_vid` and
+                // `vid` are related and we'd be inferring an infinitely
+                // deep const.
+                if ty::TermVid::Const(
+                    self.infcx.inner.borrow_mut().const_unification_table().find(vid).vid,
+                ) == self.root_vid
+                {
+                    return Err(self.cyclic_term_error());
+                }
+
+                let mut inner = self.infcx.inner.borrow_mut();
+                let variable_table = &mut inner.const_unification_table();
+                let var_value = variable_table.probe_value(vid);
+                match var_value.val {
+                    ConstVariableValue::Known { value: u } => {
+                        drop(inner);
+                        self.relate(u, u)
+                    }
+                    ConstVariableValue::Unknown { universe } => {
+                        if self.for_universe.can_name(universe) {
+                            Ok(c)
+                        } else {
+                            let new_var_id = variable_table
+                                .new_key(ConstVarValue {
+                                    origin: var_value.origin,
+                                    val: ConstVariableValue::Unknown {
+                                        universe: self.for_universe,
+                                    },
+                                })
+                                .vid;
+                            Ok(ty::Const::new_var(self.tcx(), new_var_id, c.ty()))
+                        }
+                    }
+                }
+            }
+            ty::ConstKind::Infer(InferConst::EffectVar(_)) => Ok(c),
+            // FIXME: remove this branch once `structurally_relate_consts` is fully
+            // structural.
+            ty::ConstKind::Unevaluated(ty::UnevaluatedConst { def, args }) => {
+                let args = self.relate_with_variance(
+                    ty::Variance::Invariant,
+                    ty::VarianceDiagInfo::default(),
+                    args,
+                    args,
+                )?;
+                Ok(ty::Const::new_unevaluated(
+                    self.tcx(),
+                    ty::UnevaluatedConst { def, args },
+                    c.ty(),
+                ))
+            }
+            ty::ConstKind::Placeholder(placeholder) => {
+                if self.for_universe.can_name(placeholder.universe) {
+                    Ok(c)
+                } else {
+                    debug!(
+                        "root universe {:?} cannot name placeholder in universe {:?}",
+                        self.for_universe, placeholder.universe
+                    );
+                    Err(TypeError::Mismatch)
+                }
+            }
+            _ => relate::structurally_relate_consts(self, c, c),
+        }
+    }
+
+    #[instrument(level = "debug", skip(self), ret)]
+    fn binders<T>(
+        &mut self,
+        a: ty::Binder<'tcx, T>,
+        _: ty::Binder<'tcx, T>,
+    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+    where
+        T: Relate<'tcx>,
+    {
+        let result = self.relate(a.skip_binder(), a.skip_binder())?;
+        Ok(a.rebind(result))
+    }
+}
+
+/// Result from a generalization operation. This includes
+/// not only the generalized type, but also a bool flag
+/// indicating whether further WF checks are needed.
+#[derive(Debug)]
+pub struct Generalization<T> {
+    /// When generalizing `<?0 as Trait>::Assoc` or
+    /// `<T as Bar<<?0 as Foo>::Assoc>>::Assoc`
+    /// for `?0` generalization returns an inference
+    /// variable.
+    ///
+    /// This has to be handled wotj care as it can
+    /// otherwise very easily result in infinite
+    /// recursion.
+    pub value_may_be_infer: T,
+
+    /// If true, then the generalized type may not be well-formed,
+    /// even if the source type is well-formed, so we should add an
+    /// additional check to enforce that it is. This arises in
+    /// particular around 'bivariant' type parameters that are only
+    /// constrained by a where-clause. As an example, imagine a type:
+    ///
+    ///     struct Foo<A, B> where A: Iterator<Item = B> {
+    ///         data: A
+    ///     }
+    ///
+    /// here, `A` will be covariant, but `B` is
+    /// unconstrained. However, whatever it is, for `Foo` to be WF, it
+    /// must be equal to `A::Item`. If we have an input `Foo<?A, ?B>`,
+    /// then after generalization we will wind up with a type like
+    /// `Foo<?C, ?D>`. When we enforce that `Foo<?A, ?B> <: Foo<?C,
+    /// ?D>` (or `>:`), we will wind up with the requirement that `?A
+    /// <: ?C`, but no particular relationship between `?B` and `?D`
+    /// (after all, we do not know the variance of the normalized form
+    /// of `A::Item` with respect to `A`). If we do nothing else, this
+    /// may mean that `?D` goes unconstrained (as in #41677). So, in
+    /// this scenario where we create a new type variable in a
+    /// bivariant context, we set the `needs_wf` flag to true. This
+    /// will force the calling code to check that `WF(Foo<?C, ?D>)`
+    /// holds, which in turn implies that `?C::Item == ?D`. So once
+    /// `?C` is constrained, that should suffice to restrict `?D`.
+    pub needs_wf: bool,
+}
diff --git a/compiler/rustc_infer/src/infer/relate/glb.rs b/compiler/rustc_infer/src/infer/relate/glb.rs
new file mode 100644
index 000000000..aa8912430
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/glb.rs
@@ -0,0 +1,153 @@
+//! Greatest lower bound. See [`lattice`].
+
+use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
+
+use super::combine::{CombineFields, ObligationEmittingRelation};
+use super::lattice::{self, LatticeDir};
+use crate::infer::{DefineOpaqueTypes, InferCtxt, SubregionOrigin};
+use crate::traits::{ObligationCause, PredicateObligations};
+
+/// "Greatest lower bound" (common subtype)
+pub struct Glb<'combine, 'infcx, 'tcx> {
+    fields: &'combine mut CombineFields<'infcx, 'tcx>,
+    a_is_expected: bool,
+}
+
+impl<'combine, 'infcx, 'tcx> Glb<'combine, 'infcx, 'tcx> {
+    pub fn new(
+        fields: &'combine mut CombineFields<'infcx, 'tcx>,
+        a_is_expected: bool,
+    ) -> Glb<'combine, 'infcx, 'tcx> {
+        Glb { fields, a_is_expected }
+    }
+}
+
+impl<'tcx> TypeRelation<'tcx> for Glb<'_, '_, 'tcx> {
+    fn tag(&self) -> &'static str {
+        "Glb"
+    }
+
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.fields.tcx()
+    }
+
+    fn a_is_expected(&self) -> bool {
+        self.a_is_expected
+    }
+
+    fn relate_with_variance<T: Relate<'tcx>>(
+        &mut self,
+        variance: ty::Variance,
+        _info: ty::VarianceDiagInfo<'tcx>,
+        a: T,
+        b: T,
+    ) -> RelateResult<'tcx, T> {
+        match variance {
+            ty::Invariant => self.fields.equate(self.a_is_expected).relate(a, b),
+            ty::Covariant => self.relate(a, b),
+            // FIXME(#41044) -- not correct, need test
+            ty::Bivariant => Ok(a),
+            ty::Contravariant => self.fields.lub(self.a_is_expected).relate(a, b),
+        }
+    }
+
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        lattice::super_lattice_tys(self, a, b)
+    }
+
+    fn regions(
+        &mut self,
+        a: ty::Region<'tcx>,
+        b: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        debug!("{}.regions({:?}, {:?})", self.tag(), a, b);
+
+        let origin = SubregionOrigin::Subtype(Box::new(self.fields.trace.clone()));
+        // GLB(&'static u8, &'a u8) == &RegionLUB('static, 'a) u8 == &'static u8
+        Ok(self.fields.infcx.inner.borrow_mut().unwrap_region_constraints().lub_regions(
+            self.tcx(),
+            origin,
+            a,
+            b,
+        ))
+    }
+
+    fn consts(
+        &mut self,
+        a: ty::Const<'tcx>,
+        b: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        self.fields.infcx.super_combine_consts(self, a, b)
+    }
+
+    fn binders<T>(
+        &mut self,
+        a: ty::Binder<'tcx, T>,
+        b: ty::Binder<'tcx, T>,
+    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+    where
+        T: Relate<'tcx>,
+    {
+        // GLB of a binder and itself is just itself
+        if a == b {
+            return Ok(a);
+        }
+
+        debug!("binders(a={:?}, b={:?})", a, b);
+        if a.skip_binder().has_escaping_bound_vars() || b.skip_binder().has_escaping_bound_vars() {
+            // When higher-ranked types are involved, computing the GLB is
+            // very challenging, switch to invariance. This is obviously
+            // overly conservative but works ok in practice.
+            self.relate_with_variance(
+                ty::Variance::Invariant,
+                ty::VarianceDiagInfo::default(),
+                a,
+                b,
+            )?;
+            Ok(a)
+        } else {
+            Ok(ty::Binder::dummy(self.relate(a.skip_binder(), b.skip_binder())?))
+        }
+    }
+}
+
+impl<'combine, 'infcx, 'tcx> LatticeDir<'infcx, 'tcx> for Glb<'combine, 'infcx, 'tcx> {
+    fn infcx(&self) -> &'infcx InferCtxt<'tcx> {
+        self.fields.infcx
+    }
+
+    fn cause(&self) -> &ObligationCause<'tcx> {
+        &self.fields.trace.cause
+    }
+
+    fn relate_bound(&mut self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()> {
+        let mut sub = self.fields.sub(self.a_is_expected);
+        sub.relate(v, a)?;
+        sub.relate(v, b)?;
+        Ok(())
+    }
+
+    fn define_opaque_types(&self) -> DefineOpaqueTypes {
+        self.fields.define_opaque_types
+    }
+}
+
+impl<'tcx> ObligationEmittingRelation<'tcx> for Glb<'_, '_, 'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        self.fields.param_env
+    }
+
+    fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) {
+        self.fields.register_predicates(obligations);
+    }
+
+    fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
+        self.fields.register_obligations(obligations);
+    }
+
+    fn alias_relate_direction(&self) -> ty::AliasRelationDirection {
+        // FIXME(deferred_projection_equality): This isn't right, I think?
+        ty::AliasRelationDirection::Equate
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/relate/higher_ranked.rs b/compiler/rustc_infer/src/infer/relate/higher_ranked.rs
new file mode 100644
index 000000000..440df8c89
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/higher_ranked.rs
@@ -0,0 +1,136 @@
+//! Helper routines for higher-ranked things. See the `doc` module at
+//! the end of the file for details.
+
+use super::combine::CombineFields;
+use crate::infer::CombinedSnapshot;
+use crate::infer::{HigherRankedType, InferCtxt};
+use rustc_middle::ty::fold::FnMutDelegate;
+use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::{self, Binder, Ty, TyCtxt, TypeFoldable};
+
+impl<'a, 'tcx> CombineFields<'a, 'tcx> {
+    /// Checks whether `for<..> sub <: for<..> sup` holds.
+    ///
+    /// For this to hold, **all** instantiations of the super type
+    /// have to be a super type of **at least one** instantiation of
+    /// the subtype.
+    ///
+    /// This is implemented by first entering a new universe.
+    /// We then replace all bound variables in `sup` with placeholders,
+    /// and all bound variables in `sub` with inference vars.
+    /// We can then just relate the two resulting types as normal.
+    ///
+    /// Note: this is a subtle algorithm. For a full explanation, please see
+    /// the [rustc dev guide][rd]
+    ///
+    /// [rd]: https://rustc-dev-guide.rust-lang.org/borrow_check/region_inference/placeholders_and_universes.html
+    #[instrument(skip(self), level = "debug")]
+    pub fn higher_ranked_sub<T>(
+        &mut self,
+        sub: Binder<'tcx, T>,
+        sup: Binder<'tcx, T>,
+        sub_is_expected: bool,
+    ) -> RelateResult<'tcx, ()>
+    where
+        T: Relate<'tcx>,
+    {
+        let span = self.trace.cause.span;
+        // First, we instantiate each bound region in the supertype with a
+        // fresh placeholder region. Note that this automatically creates
+        // a new universe if needed.
+        let sup_prime = self.infcx.instantiate_binder_with_placeholders(sup);
+
+        // Next, we instantiate each bound region in the subtype
+        // with a fresh region variable. These region variables --
+        // but no other preexisting region variables -- can name
+        // the placeholders.
+        let sub_prime = self.infcx.instantiate_binder_with_fresh_vars(span, HigherRankedType, sub);
+
+        debug!("a_prime={:?}", sub_prime);
+        debug!("b_prime={:?}", sup_prime);
+
+        // Compare types now that bound regions have been replaced.
+        let result = self.sub(sub_is_expected).relate(sub_prime, sup_prime)?;
+
+        debug!("OK result={result:?}");
+        // NOTE: returning the result here would be dangerous as it contains
+        // placeholders which **must not** be named afterwards.
+        Ok(())
+    }
+}
+
+impl<'tcx> InferCtxt<'tcx> {
+    /// Replaces all bound variables (lifetimes, types, and constants) bound by
+    /// `binder` with placeholder variables in a new universe. This means that the
+    /// new placeholders can only be named by inference variables created after
+    /// this method has been called.
+    ///
+    /// This is the first step of checking subtyping when higher-ranked things are involved.
+    /// For more details visit the relevant sections of the [rustc dev guide].
+    ///
+    /// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
+    #[instrument(level = "debug", skip(self), ret)]
+    pub fn instantiate_binder_with_placeholders<T>(&self, binder: ty::Binder<'tcx, T>) -> T
+    where
+        T: TypeFoldable<TyCtxt<'tcx>> + Copy,
+    {
+        if let Some(inner) = binder.no_bound_vars() {
+            return inner;
+        }
+
+        let next_universe = self.create_next_universe();
+
+        let delegate = FnMutDelegate {
+            regions: &mut |br: ty::BoundRegion| {
+                ty::Region::new_placeholder(
+                    self.tcx,
+                    ty::PlaceholderRegion { universe: next_universe, bound: br },
+                )
+            },
+            types: &mut |bound_ty: ty::BoundTy| {
+                Ty::new_placeholder(
+                    self.tcx,
+                    ty::PlaceholderType { universe: next_universe, bound: bound_ty },
+                )
+            },
+            consts: &mut |bound_var: ty::BoundVar, ty| {
+                ty::Const::new_placeholder(
+                    self.tcx,
+                    ty::PlaceholderConst { universe: next_universe, bound: bound_var },
+                    ty,
+                )
+            },
+        };
+
+        debug!(?next_universe);
+        self.tcx.replace_bound_vars_uncached(binder, delegate)
+    }
+
+    /// See [RegionConstraintCollector::leak_check][1]. We only check placeholder
+    /// leaking into `outer_universe`, i.e. placeholders which cannot be named by that
+    /// universe.
+    ///
+    /// [1]: crate::infer::region_constraints::RegionConstraintCollector::leak_check
+    pub fn leak_check(
+        &self,
+        outer_universe: ty::UniverseIndex,
+        only_consider_snapshot: Option<&CombinedSnapshot<'tcx>>,
+    ) -> RelateResult<'tcx, ()> {
+        // If the user gave `-Zno-leak-check`, or we have been
+        // configured to skip the leak check, then skip the leak check
+        // completely. The leak check is deprecated. Any legitimate
+        // subtyping errors that it would have caught will now be
+        // caught later on, during region checking. However, we
+        // continue to use it for a transition period.
+        if self.tcx.sess.opts.unstable_opts.no_leak_check || self.skip_leak_check {
+            return Ok(());
+        }
+
+        self.inner.borrow_mut().unwrap_region_constraints().leak_check(
+            self.tcx,
+            outer_universe,
+            self.universe(),
+            only_consider_snapshot,
+        )
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/relate/lattice.rs b/compiler/rustc_infer/src/infer/relate/lattice.rs
new file mode 100644
index 000000000..744e2dfa3
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/lattice.rs
@@ -0,0 +1,128 @@
+//! # Lattice variables
+//!
+//! Generic code for operating on [lattices] of inference variables
+//! that are characterized by an upper- and lower-bound.
+//!
+//! The code is defined quite generically so that it can be
+//! applied both to type variables, which represent types being inferred,
+//! and fn variables, which represent function types being inferred.
+//! (It may eventually be applied to their types as well.)
+//! In some cases, the functions are also generic with respect to the
+//! operation on the lattice (GLB vs LUB).
+//!
+//! ## Note
+//!
+//! Although all the functions are generic, for simplicity, comments in the source code
+//! generally refer to type variables and the LUB operation.
+//!
+//! [lattices]: https://en.wikipedia.org/wiki/Lattice_(order)
+
+use super::combine::ObligationEmittingRelation;
+use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
+use crate::infer::{DefineOpaqueTypes, InferCtxt};
+use crate::traits::ObligationCause;
+
+use rustc_middle::ty::relate::RelateResult;
+use rustc_middle::ty::TyVar;
+use rustc_middle::ty::{self, Ty};
+
+/// Trait for returning data about a lattice, and for abstracting
+/// over the "direction" of the lattice operation (LUB/GLB).
+///
+/// GLB moves "down" the lattice (to smaller values); LUB moves
+/// "up" the lattice (to bigger values).
+pub trait LatticeDir<'f, 'tcx>: ObligationEmittingRelation<'tcx> {
+    fn infcx(&self) -> &'f InferCtxt<'tcx>;
+
+    fn cause(&self) -> &ObligationCause<'tcx>;
+
+    fn define_opaque_types(&self) -> DefineOpaqueTypes;
+
+    // Relates the type `v` to `a` and `b` such that `v` represents
+    // the LUB/GLB of `a` and `b` as appropriate.
+    //
+    // Subtle hack: ordering *may* be significant here. This method
+    // relates `v` to `a` first, which may help us to avoid unnecessary
+    // type variable obligations. See caller for details.
+    fn relate_bound(&mut self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()>;
+}
+
+/// Relates two types using a given lattice.
+#[instrument(skip(this), level = "debug")]
+pub fn super_lattice_tys<'a, 'tcx: 'a, L>(
+    this: &mut L,
+    a: Ty<'tcx>,
+    b: Ty<'tcx>,
+) -> RelateResult<'tcx, Ty<'tcx>>
+where
+    L: LatticeDir<'a, 'tcx>,
+{
+    debug!("{}", this.tag());
+
+    if a == b {
+        return Ok(a);
+    }
+
+    let infcx = this.infcx();
+
+    let a = infcx.inner.borrow_mut().type_variables().replace_if_possible(a);
+    let b = infcx.inner.borrow_mut().type_variables().replace_if_possible(b);
+
+    match (a.kind(), b.kind()) {
+        // If one side is known to be a variable and one is not,
+        // create a variable (`v`) to represent the LUB. Make sure to
+        // relate `v` to the non-type-variable first (by passing it
+        // first to `relate_bound`). Otherwise, we would produce a
+        // subtype obligation that must then be processed.
+        //
+        // Example: if the LHS is a type variable, and RHS is
+        // `Box<i32>`, then we current compare `v` to the RHS first,
+        // which will instantiate `v` with `Box<i32>`. Then when `v`
+        // is compared to the LHS, we instantiate LHS with `Box<i32>`.
+        // But if we did in reverse order, we would create a `v <:
+        // LHS` (or vice versa) constraint and then instantiate
+        // `v`. This would require further processing to achieve same
+        // end-result; in particular, this screws up some of the logic
+        // in coercion, which expects LUB to figure out that the LHS
+        // is (e.g.) `Box<i32>`. A more obvious solution might be to
+        // iterate on the subtype obligations that are returned, but I
+        // think this suffices. -nmatsakis
+        (&ty::Infer(TyVar(..)), _) => {
+            let v = infcx.next_ty_var(TypeVariableOrigin {
+                kind: TypeVariableOriginKind::LatticeVariable,
+                span: this.cause().span,
+            });
+            this.relate_bound(v, b, a)?;
+            Ok(v)
+        }
+        (_, &ty::Infer(TyVar(..))) => {
+            let v = infcx.next_ty_var(TypeVariableOrigin {
+                kind: TypeVariableOriginKind::LatticeVariable,
+                span: this.cause().span,
+            });
+            this.relate_bound(v, a, b)?;
+            Ok(v)
+        }
+
+        (
+            &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }),
+            &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }),
+        ) if a_def_id == b_def_id => infcx.super_combine_tys(this, a, b),
+
+        (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _)
+        | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }))
+            if this.define_opaque_types() == DefineOpaqueTypes::Yes
+                && def_id.is_local()
+                && !this.infcx().next_trait_solver() =>
+        {
+            this.register_obligations(
+                infcx
+                    .handle_opaque_type(a, b, this.a_is_expected(), this.cause(), this.param_env())?
+                    .obligations,
+            );
+            Ok(a)
+        }
+
+        _ => infcx.super_combine_tys(this, a, b),
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/relate/lub.rs b/compiler/rustc_infer/src/infer/relate/lub.rs
new file mode 100644
index 000000000..87d777530
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/lub.rs
@@ -0,0 +1,153 @@
+//! Least upper bound. See [`lattice`].
+
+use super::combine::{CombineFields, ObligationEmittingRelation};
+use super::lattice::{self, LatticeDir};
+use crate::infer::{DefineOpaqueTypes, InferCtxt, SubregionOrigin};
+use crate::traits::{ObligationCause, PredicateObligations};
+
+use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
+
+/// "Least upper bound" (common supertype)
+pub struct Lub<'combine, 'infcx, 'tcx> {
+    fields: &'combine mut CombineFields<'infcx, 'tcx>,
+    a_is_expected: bool,
+}
+
+impl<'combine, 'infcx, 'tcx> Lub<'combine, 'infcx, 'tcx> {
+    pub fn new(
+        fields: &'combine mut CombineFields<'infcx, 'tcx>,
+        a_is_expected: bool,
+    ) -> Lub<'combine, 'infcx, 'tcx> {
+        Lub { fields, a_is_expected }
+    }
+}
+
+impl<'tcx> TypeRelation<'tcx> for Lub<'_, '_, 'tcx> {
+    fn tag(&self) -> &'static str {
+        "Lub"
+    }
+
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.fields.tcx()
+    }
+
+    fn a_is_expected(&self) -> bool {
+        self.a_is_expected
+    }
+
+    fn relate_with_variance<T: Relate<'tcx>>(
+        &mut self,
+        variance: ty::Variance,
+        _info: ty::VarianceDiagInfo<'tcx>,
+        a: T,
+        b: T,
+    ) -> RelateResult<'tcx, T> {
+        match variance {
+            ty::Invariant => self.fields.equate(self.a_is_expected).relate(a, b),
+            ty::Covariant => self.relate(a, b),
+            // FIXME(#41044) -- not correct, need test
+            ty::Bivariant => Ok(a),
+            ty::Contravariant => self.fields.glb(self.a_is_expected).relate(a, b),
+        }
+    }
+
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        lattice::super_lattice_tys(self, a, b)
+    }
+
+    fn regions(
+        &mut self,
+        a: ty::Region<'tcx>,
+        b: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        debug!("{}.regions({:?}, {:?})", self.tag(), a, b);
+
+        let origin = SubregionOrigin::Subtype(Box::new(self.fields.trace.clone()));
+        // LUB(&'static u8, &'a u8) == &RegionGLB('static, 'a) u8 == &'a u8
+        Ok(self.fields.infcx.inner.borrow_mut().unwrap_region_constraints().glb_regions(
+            self.tcx(),
+            origin,
+            a,
+            b,
+        ))
+    }
+
+    fn consts(
+        &mut self,
+        a: ty::Const<'tcx>,
+        b: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        self.fields.infcx.super_combine_consts(self, a, b)
+    }
+
+    fn binders<T>(
+        &mut self,
+        a: ty::Binder<'tcx, T>,
+        b: ty::Binder<'tcx, T>,
+    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+    where
+        T: Relate<'tcx>,
+    {
+        // LUB of a binder and itself is just itself
+        if a == b {
+            return Ok(a);
+        }
+
+        debug!("binders(a={:?}, b={:?})", a, b);
+        if a.skip_binder().has_escaping_bound_vars() || b.skip_binder().has_escaping_bound_vars() {
+            // When higher-ranked types are involved, computing the LUB is
+            // very challenging, switch to invariance. This is obviously
+            // overly conservative but works ok in practice.
+            self.relate_with_variance(
+                ty::Variance::Invariant,
+                ty::VarianceDiagInfo::default(),
+                a,
+                b,
+            )?;
+            Ok(a)
+        } else {
+            Ok(ty::Binder::dummy(self.relate(a.skip_binder(), b.skip_binder())?))
+        }
+    }
+}
+
+impl<'combine, 'infcx, 'tcx> LatticeDir<'infcx, 'tcx> for Lub<'combine, 'infcx, 'tcx> {
+    fn infcx(&self) -> &'infcx InferCtxt<'tcx> {
+        self.fields.infcx
+    }
+
+    fn cause(&self) -> &ObligationCause<'tcx> {
+        &self.fields.trace.cause
+    }
+
+    fn relate_bound(&mut self, v: Ty<'tcx>, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()> {
+        let mut sub = self.fields.sub(self.a_is_expected);
+        sub.relate(a, v)?;
+        sub.relate(b, v)?;
+        Ok(())
+    }
+
+    fn define_opaque_types(&self) -> DefineOpaqueTypes {
+        self.fields.define_opaque_types
+    }
+}
+
+impl<'tcx> ObligationEmittingRelation<'tcx> for Lub<'_, '_, 'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        self.fields.param_env
+    }
+
+    fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) {
+        self.fields.register_predicates(obligations);
+    }
+
+    fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
+        self.fields.register_obligations(obligations)
+    }
+
+    fn alias_relate_direction(&self) -> ty::AliasRelationDirection {
+        // FIXME(deferred_projection_equality): This isn't right, I think?
+        ty::AliasRelationDirection::Equate
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/relate/mod.rs b/compiler/rustc_infer/src/infer/relate/mod.rs
new file mode 100644
index 000000000..f688c2b74
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/mod.rs
@@ -0,0 +1,12 @@
+//! This module contains the definitions of most `TypeRelation`s in the type system
+//! (except for some relations used for diagnostics and heuristics in the compiler).
+
+pub(super) mod combine;
+mod equate;
+pub(super) mod generalize;
+mod glb;
+mod higher_ranked;
+mod lattice;
+mod lub;
+pub mod nll;
+mod sub;
diff --git a/compiler/rustc_infer/src/infer/relate/nll.rs b/compiler/rustc_infer/src/infer/relate/nll.rs
new file mode 100644
index 000000000..1ef865cfc
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/nll.rs
@@ -0,0 +1,717 @@
+//! This code is kind of an alternate way of doing subtyping,
+//! supertyping, and type equating, distinct from the `combine.rs`
+//! code but very similar in its effect and design. Eventually the two
+//! ought to be merged. This code is intended for use in NLL and chalk.
+//!
+//! Here are the key differences:
+//!
+//! - This code may choose to bypass some checks (e.g., the occurs check)
+//!   in the case where we know that there are no unbound type inference
+//!   variables. This is the case for NLL, because at NLL time types are fully
+//!   inferred up-to regions.
+//! - This code uses "universes" to handle higher-ranked regions and
+//!   not the leak-check. This is "more correct" than what rustc does
+//!   and we are generally migrating in this direction, but NLL had to
+//!   get there first.
+//!
+//! Also, this code assumes that there are no bound types at all, not even
+//! free ones. This is ok because:
+//! - we are not relating anything quantified over some type variable
+//! - we will have instantiated all the bound type vars already (the one
+//!   thing we relate in chalk are basically domain goals and their
+//!   constituents)
+
+use rustc_data_structures::fx::FxHashMap;
+use rustc_middle::traits::ObligationCause;
+use rustc_middle::ty::fold::FnMutDelegate;
+use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::visit::TypeVisitableExt;
+use rustc_middle::ty::{self, InferConst, Ty, TyCtxt};
+use rustc_span::{Span, Symbol};
+use std::fmt::Debug;
+
+use super::combine::ObligationEmittingRelation;
+use super::generalize::{self, Generalization};
+use crate::infer::InferCtxt;
+use crate::infer::{TypeVariableOrigin, TypeVariableOriginKind};
+use crate::traits::{Obligation, PredicateObligations};
+
+pub struct TypeRelating<'me, 'tcx, D>
+where
+    D: TypeRelatingDelegate<'tcx>,
+{
+    infcx: &'me InferCtxt<'tcx>,
+
+    /// Callback to use when we deduce an outlives relationship.
+    delegate: D,
+
+    /// How are we relating `a` and `b`?
+    ///
+    /// - Covariant means `a <: b`.
+    /// - Contravariant means `b <: a`.
+    /// - Invariant means `a == b`.
+    /// - Bivariant means that it doesn't matter.
+    ambient_variance: ty::Variance,
+
+    ambient_variance_info: ty::VarianceDiagInfo<'tcx>,
+}
+
+pub trait TypeRelatingDelegate<'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx>;
+    fn span(&self) -> Span;
+
+    /// Push a constraint `sup: sub` -- this constraint must be
+    /// satisfied for the two types to be related. `sub` and `sup` may
+    /// be regions from the type or new variables created through the
+    /// delegate.
+    fn push_outlives(
+        &mut self,
+        sup: ty::Region<'tcx>,
+        sub: ty::Region<'tcx>,
+        info: ty::VarianceDiagInfo<'tcx>,
+    );
+
+    fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>);
+
+    /// Creates a new universe index. Used when instantiating placeholders.
+    fn create_next_universe(&mut self) -> ty::UniverseIndex;
+
+    /// Creates a new region variable representing a higher-ranked
+    /// region that is instantiated existentially. This creates an
+    /// inference variable, typically.
+    ///
+    /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
+    /// we will invoke this method to instantiate `'a` with an
+    /// inference variable (though `'b` would be instantiated first,
+    /// as a placeholder).
+    fn next_existential_region_var(
+        &mut self,
+        was_placeholder: bool,
+        name: Option<Symbol>,
+    ) -> ty::Region<'tcx>;
+
+    /// Creates a new region variable representing a
+    /// higher-ranked region that is instantiated universally.
+    /// This creates a new region placeholder, typically.
+    ///
+    /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
+    /// we will invoke this method to instantiate `'b` with a
+    /// placeholder region.
+    fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>;
+
+    /// Creates a new existential region in the given universe. This
+    /// is used when handling subtyping and type variables -- if we
+    /// have that `?X <: Foo<'a>`, for example, we would instantiate
+    /// `?X` with a type like `Foo<'?0>` where `'?0` is a fresh
+    /// existential variable created by this function. We would then
+    /// relate `Foo<'?0>` with `Foo<'a>` (and probably add an outlives
+    /// relation stating that `'?0: 'a`).
+    fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>;
+
+    /// Enables some optimizations if we do not expect inference variables
+    /// in the RHS of the relation.
+    fn forbid_inference_vars() -> bool;
+}
+
+impl<'me, 'tcx, D> TypeRelating<'me, 'tcx, D>
+where
+    D: TypeRelatingDelegate<'tcx>,
+{
+    pub fn new(infcx: &'me InferCtxt<'tcx>, delegate: D, ambient_variance: ty::Variance) -> Self {
+        Self {
+            infcx,
+            delegate,
+            ambient_variance,
+            ambient_variance_info: ty::VarianceDiagInfo::default(),
+        }
+    }
+
+    fn ambient_covariance(&self) -> bool {
+        match self.ambient_variance {
+            ty::Variance::Covariant | ty::Variance::Invariant => true,
+            ty::Variance::Contravariant | ty::Variance::Bivariant => false,
+        }
+    }
+
+    fn ambient_contravariance(&self) -> bool {
+        match self.ambient_variance {
+            ty::Variance::Contravariant | ty::Variance::Invariant => true,
+            ty::Variance::Covariant | ty::Variance::Bivariant => false,
+        }
+    }
+
+    /// Push a new outlives requirement into our output set of
+    /// constraints.
+    fn push_outlives(
+        &mut self,
+        sup: ty::Region<'tcx>,
+        sub: ty::Region<'tcx>,
+        info: ty::VarianceDiagInfo<'tcx>,
+    ) {
+        debug!("push_outlives({:?}: {:?})", sup, sub);
+
+        self.delegate.push_outlives(sup, sub, info);
+    }
+
+    /// Relate a type inference variable with a value type. This works
+    /// by creating a "generalization" G of the value where all the
+    /// lifetimes are replaced with fresh inference values. This
+    /// generalization G becomes the value of the inference variable,
+    /// and is then related in turn to the value. So e.g. if you had
+    /// `vid = ?0` and `value = &'a u32`, we might first instantiate
+    /// `?0` to a type like `&'0 u32` where `'0` is a fresh variable,
+    /// and then relate `&'0 u32` with `&'a u32` (resulting in
+    /// relations between `'0` and `'a`).
+    ///
+    /// The variable `pair` can be either a `(vid, ty)` or `(ty, vid)`
+    /// -- in other words, it is always an (unresolved) inference
+    /// variable `vid` and a type `ty` that are being related, but the
+    /// vid may appear either as the "a" type or the "b" type,
+    /// depending on where it appears in the tuple. The trait
+    /// `VidValuePair` lets us work with the vid/type while preserving
+    /// the "sidedness" when necessary -- the sidedness is relevant in
+    /// particular for the variance and set of in-scope things.
+    fn relate_ty_var<PAIR: VidValuePair<'tcx>>(
+        &mut self,
+        pair: PAIR,
+    ) -> RelateResult<'tcx, Ty<'tcx>> {
+        debug!("relate_ty_var({:?})", pair);
+
+        let vid = pair.vid();
+        let value_ty = pair.value_ty();
+
+        // FIXME(invariance) -- this logic assumes invariance, but that is wrong.
+        // This only presently applies to chalk integration, as NLL
+        // doesn't permit type variables to appear on both sides (and
+        // doesn't use lazy norm).
+        match *value_ty.kind() {
+            ty::Infer(ty::TyVar(value_vid)) => {
+                // Two type variables: just equate them.
+                self.infcx.inner.borrow_mut().type_variables().equate(vid, value_vid);
+                return Ok(value_ty);
+            }
+
+            _ => (),
+        }
+
+        let generalized_ty = self.generalize(value_ty, vid)?;
+        debug!("relate_ty_var: generalized_ty = {:?}", generalized_ty);
+
+        if D::forbid_inference_vars() {
+            // In NLL, we don't have type inference variables
+            // floating around, so we can do this rather imprecise
+            // variant of the occurs-check.
+            assert!(!generalized_ty.has_non_region_infer());
+        }
+
+        self.infcx.inner.borrow_mut().type_variables().instantiate(vid, generalized_ty);
+
+        // Relate the generalized kind to the original one.
+        let result = pair.relate_generalized_ty(self, generalized_ty);
+
+        debug!("relate_ty_var: complete, result = {:?}", result);
+        result
+    }
+
+    fn generalize(&mut self, ty: Ty<'tcx>, for_vid: ty::TyVid) -> RelateResult<'tcx, Ty<'tcx>> {
+        let Generalization { value_may_be_infer: ty, needs_wf: _ } = generalize::generalize(
+            self.infcx,
+            &mut self.delegate,
+            ty,
+            for_vid,
+            self.ambient_variance,
+        )?;
+
+        if ty.is_ty_var() {
+            span_bug!(self.delegate.span(), "occurs check failure in MIR typeck");
+        }
+        Ok(ty)
+    }
+
+    fn relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        let (a, b) = if self.a_is_expected() { (a, b) } else { (b, a) };
+        let mut generalize = |ty, ty_is_expected| {
+            let var = self.infcx.next_ty_var_id_in_universe(
+                TypeVariableOrigin {
+                    kind: TypeVariableOriginKind::MiscVariable,
+                    span: self.delegate.span(),
+                },
+                ty::UniverseIndex::ROOT,
+            );
+            if ty_is_expected {
+                self.relate_ty_var((ty, var))
+            } else {
+                self.relate_ty_var((var, ty))
+            }
+        };
+        let (a, b) = match (a.kind(), b.kind()) {
+            (&ty::Alias(ty::Opaque, ..), _) => (a, generalize(b, false)?),
+            (_, &ty::Alias(ty::Opaque, ..)) => (generalize(a, true)?, b),
+            _ => unreachable!(
+                "expected at least one opaque type in `relate_opaques`, got {a} and {b}."
+            ),
+        };
+        let cause = ObligationCause::dummy_with_span(self.delegate.span());
+        let obligations = self
+            .infcx
+            .handle_opaque_type(a, b, true, &cause, self.delegate.param_env())?
+            .obligations;
+        self.delegate.register_obligations(obligations);
+        trace!(a = ?a.kind(), b = ?b.kind(), "opaque type instantiated");
+        Ok(a)
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn instantiate_binder_with_placeholders<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T
+    where
+        T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
+    {
+        if let Some(inner) = binder.no_bound_vars() {
+            return inner;
+        }
+
+        let mut next_region = {
+            let nll_delegate = &mut self.delegate;
+            let mut lazy_universe = None;
+
+            move |br: ty::BoundRegion| {
+                // The first time this closure is called, create a
+                // new universe for the placeholders we will make
+                // from here out.
+                let universe = lazy_universe.unwrap_or_else(|| {
+                    let universe = nll_delegate.create_next_universe();
+                    lazy_universe = Some(universe);
+                    universe
+                });
+
+                let placeholder = ty::PlaceholderRegion { universe, bound: br };
+                debug!(?placeholder);
+                let placeholder_reg = nll_delegate.next_placeholder_region(placeholder);
+                debug!(?placeholder_reg);
+
+                placeholder_reg
+            }
+        };
+
+        let delegate = FnMutDelegate {
+            regions: &mut next_region,
+            types: &mut |_bound_ty: ty::BoundTy| {
+                unreachable!("we only replace regions in nll_relate, not types")
+            },
+            consts: &mut |_bound_var: ty::BoundVar, _ty| {
+                unreachable!("we only replace regions in nll_relate, not consts")
+            },
+        };
+
+        let replaced = self.infcx.tcx.replace_bound_vars_uncached(binder, delegate);
+        debug!(?replaced);
+
+        replaced
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn instantiate_binder_with_existentials<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T
+    where
+        T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
+    {
+        if let Some(inner) = binder.no_bound_vars() {
+            return inner;
+        }
+
+        let mut next_region = {
+            let nll_delegate = &mut self.delegate;
+            let mut reg_map = FxHashMap::default();
+
+            move |br: ty::BoundRegion| {
+                if let Some(ex_reg_var) = reg_map.get(&br) {
+                    return *ex_reg_var;
+                } else {
+                    let ex_reg_var =
+                        nll_delegate.next_existential_region_var(true, br.kind.get_name());
+                    debug!(?ex_reg_var);
+                    reg_map.insert(br, ex_reg_var);
+
+                    ex_reg_var
+                }
+            }
+        };
+
+        let delegate = FnMutDelegate {
+            regions: &mut next_region,
+            types: &mut |_bound_ty: ty::BoundTy| {
+                unreachable!("we only replace regions in nll_relate, not types")
+            },
+            consts: &mut |_bound_var: ty::BoundVar, _ty| {
+                unreachable!("we only replace regions in nll_relate, not consts")
+            },
+        };
+
+        let replaced = self.infcx.tcx.replace_bound_vars_uncached(binder, delegate);
+        debug!(?replaced);
+
+        replaced
+    }
+}
+
+/// When we instantiate an inference variable with a value in
+/// `relate_ty_var`, we always have the pair of a `TyVid` and a `Ty`,
+/// but the ordering may vary (depending on whether the inference
+/// variable was found on the `a` or `b` sides). Therefore, this trait
+/// allows us to factor out common code, while preserving the order
+/// when needed.
+trait VidValuePair<'tcx>: Debug {
+    /// Extract the inference variable (which could be either the
+    /// first or second part of the tuple).
+    fn vid(&self) -> ty::TyVid;
+
+    /// Extract the value it is being related to (which will be the
+    /// opposite part of the tuple from the vid).
+    fn value_ty(&self) -> Ty<'tcx>;
+
+    /// Given a generalized type G that should replace the vid, relate
+    /// G to the value, putting G on whichever side the vid would have
+    /// appeared.
+    fn relate_generalized_ty<D>(
+        &self,
+        relate: &mut TypeRelating<'_, 'tcx, D>,
+        generalized_ty: Ty<'tcx>,
+    ) -> RelateResult<'tcx, Ty<'tcx>>
+    where
+        D: TypeRelatingDelegate<'tcx>;
+}
+
+impl<'tcx> VidValuePair<'tcx> for (ty::TyVid, Ty<'tcx>) {
+    fn vid(&self) -> ty::TyVid {
+        self.0
+    }
+
+    fn value_ty(&self) -> Ty<'tcx> {
+        self.1
+    }
+
+    fn relate_generalized_ty<D>(
+        &self,
+        relate: &mut TypeRelating<'_, 'tcx, D>,
+        generalized_ty: Ty<'tcx>,
+    ) -> RelateResult<'tcx, Ty<'tcx>>
+    where
+        D: TypeRelatingDelegate<'tcx>,
+    {
+        relate.relate(generalized_ty, self.value_ty())
+    }
+}
+
+// In this case, the "vid" is the "b" type.
+impl<'tcx> VidValuePair<'tcx> for (Ty<'tcx>, ty::TyVid) {
+    fn vid(&self) -> ty::TyVid {
+        self.1
+    }
+
+    fn value_ty(&self) -> Ty<'tcx> {
+        self.0
+    }
+
+    fn relate_generalized_ty<D>(
+        &self,
+        relate: &mut TypeRelating<'_, 'tcx, D>,
+        generalized_ty: Ty<'tcx>,
+    ) -> RelateResult<'tcx, Ty<'tcx>>
+    where
+        D: TypeRelatingDelegate<'tcx>,
+    {
+        relate.relate(self.value_ty(), generalized_ty)
+    }
+}
+
+impl<'tcx, D> TypeRelation<'tcx> for TypeRelating<'_, 'tcx, D>
+where
+    D: TypeRelatingDelegate<'tcx>,
+{
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    fn tag(&self) -> &'static str {
+        "nll::subtype"
+    }
+
+    fn a_is_expected(&self) -> bool {
+        true
+    }
+
+    #[instrument(skip(self, info), level = "trace", ret)]
+    fn relate_with_variance<T: Relate<'tcx>>(
+        &mut self,
+        variance: ty::Variance,
+        info: ty::VarianceDiagInfo<'tcx>,
+        a: T,
+        b: T,
+    ) -> RelateResult<'tcx, T> {
+        let old_ambient_variance = self.ambient_variance;
+        self.ambient_variance = self.ambient_variance.xform(variance);
+        self.ambient_variance_info = self.ambient_variance_info.xform(info);
+
+        debug!(?self.ambient_variance);
+        // In a bivariant context this always succeeds.
+        let r =
+            if self.ambient_variance == ty::Variance::Bivariant { a } else { self.relate(a, b)? };
+
+        self.ambient_variance = old_ambient_variance;
+
+        Ok(r)
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        let infcx = self.infcx;
+
+        let a = self.infcx.shallow_resolve(a);
+
+        if !D::forbid_inference_vars() {
+            b = self.infcx.shallow_resolve(b);
+        }
+
+        if a == b {
+            return Ok(a);
+        }
+
+        match (a.kind(), b.kind()) {
+            (_, &ty::Infer(ty::TyVar(vid))) => {
+                if D::forbid_inference_vars() {
+                    // Forbid inference variables in the RHS.
+                    bug!("unexpected inference var {:?}", b)
+                } else {
+                    self.relate_ty_var((a, vid))
+                }
+            }
+
+            (&ty::Infer(ty::TyVar(vid)), _) => self.relate_ty_var((vid, b)),
+
+            (
+                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }),
+                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }),
+            ) if a_def_id == b_def_id || infcx.next_trait_solver() => {
+                infcx.super_combine_tys(self, a, b).or_else(|err| {
+                    // This behavior is only there for the old solver, the new solver
+                    // shouldn't ever fail. Instead, it unconditionally emits an
+                    // alias-relate goal.
+                    assert!(!self.infcx.next_trait_solver());
+                    self.tcx().sess.span_delayed_bug(
+                        self.delegate.span(),
+                        "failure to relate an opaque to itself should result in an error later on",
+                    );
+                    if a_def_id.is_local() { self.relate_opaques(a, b) } else { Err(err) }
+                })
+            }
+            (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _)
+            | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }))
+                if def_id.is_local() && !self.infcx.next_trait_solver() =>
+            {
+                self.relate_opaques(a, b)
+            }
+
+            _ => {
+                debug!(?a, ?b, ?self.ambient_variance);
+
+                // Will also handle unification of `IntVar` and `FloatVar`.
+                self.infcx.super_combine_tys(self, a, b)
+            }
+        }
+    }
+
+    #[instrument(skip(self), level = "trace")]
+    fn regions(
+        &mut self,
+        a: ty::Region<'tcx>,
+        b: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        debug!(?self.ambient_variance);
+
+        if self.ambient_covariance() {
+            // Covariant: &'a u8 <: &'b u8. Hence, `'a: 'b`.
+            self.push_outlives(a, b, self.ambient_variance_info);
+        }
+
+        if self.ambient_contravariance() {
+            // Contravariant: &'b u8 <: &'a u8. Hence, `'b: 'a`.
+            self.push_outlives(b, a, self.ambient_variance_info);
+        }
+
+        Ok(a)
+    }
+
+    fn consts(
+        &mut self,
+        a: ty::Const<'tcx>,
+        mut b: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        let a = self.infcx.shallow_resolve(a);
+
+        if !D::forbid_inference_vars() {
+            b = self.infcx.shallow_resolve(b);
+        }
+
+        match b.kind() {
+            ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => {
+                // Forbid inference variables in the RHS.
+                self.infcx.tcx.sess.span_delayed_bug(
+                    self.delegate.span(),
+                    format!("unexpected inference var {b:?}",),
+                );
+                Ok(a)
+            }
+            // FIXME(invariance): see the related FIXME above.
+            _ => self.infcx.super_combine_consts(self, a, b),
+        }
+    }
+
+    #[instrument(skip(self), level = "trace")]
+    fn binders<T>(
+        &mut self,
+        a: ty::Binder<'tcx, T>,
+        b: ty::Binder<'tcx, T>,
+    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+    where
+        T: Relate<'tcx>,
+    {
+        // We want that
+        //
+        // ```
+        // for<'a> fn(&'a u32) -> &'a u32 <:
+        //   fn(&'b u32) -> &'b u32
+        // ```
+        //
+        // but not
+        //
+        // ```
+        // fn(&'a u32) -> &'a u32 <:
+        //   for<'b> fn(&'b u32) -> &'b u32
+        // ```
+        //
+        // We therefore proceed as follows:
+        //
+        // - Instantiate binders on `b` universally, yielding a universe U1.
+        // - Instantiate binders on `a` existentially in U1.
+
+        debug!(?self.ambient_variance);
+
+        if let (Some(a), Some(b)) = (a.no_bound_vars(), b.no_bound_vars()) {
+            // Fast path for the common case.
+            self.relate(a, b)?;
+            return Ok(ty::Binder::dummy(a));
+        }
+
+        if self.ambient_covariance() {
+            // Covariance, so we want `for<..> A <: for<..> B` --
+            // therefore we compare any instantiation of A (i.e., A
+            // instantiated with existentials) against every
+            // instantiation of B (i.e., B instantiated with
+            // universals).
+
+            // Reset the ambient variance to covariant. This is needed
+            // to correctly handle cases like
+            //
+            //     for<'a> fn(&'a u32, &'a u32) == for<'b, 'c> fn(&'b u32, &'c u32)
+            //
+            // Somewhat surprisingly, these two types are actually
+            // **equal**, even though the one on the right looks more
+            // polymorphic. The reason is due to subtyping. To see it,
+            // consider that each function can call the other:
+            //
+            // - The left function can call the right with `'b` and
+            //   `'c` both equal to `'a`
+            //
+            // - The right function can call the left with `'a` set to
+            //   `{P}`, where P is the point in the CFG where the call
+            //   itself occurs. Note that `'b` and `'c` must both
+            //   include P. At the point, the call works because of
+            //   subtyping (i.e., `&'b u32 <: &{P} u32`).
+            let variance = std::mem::replace(&mut self.ambient_variance, ty::Variance::Covariant);
+
+            // Note: the order here is important. Create the placeholders first, otherwise
+            // we assign the wrong universe to the existential!
+            let b_replaced = self.instantiate_binder_with_placeholders(b);
+            let a_replaced = self.instantiate_binder_with_existentials(a);
+
+            self.relate(a_replaced, b_replaced)?;
+
+            self.ambient_variance = variance;
+        }
+
+        if self.ambient_contravariance() {
+            // Contravariance, so we want `for<..> A :> for<..> B`
+            // -- therefore we compare every instantiation of A (i.e.,
+            // A instantiated with universals) against any
+            // instantiation of B (i.e., B instantiated with
+            // existentials). Opposite of above.
+
+            // Reset ambient variance to contravariance. See the
+            // covariant case above for an explanation.
+            let variance =
+                std::mem::replace(&mut self.ambient_variance, ty::Variance::Contravariant);
+
+            let a_replaced = self.instantiate_binder_with_placeholders(a);
+            let b_replaced = self.instantiate_binder_with_existentials(b);
+
+            self.relate(a_replaced, b_replaced)?;
+
+            self.ambient_variance = variance;
+        }
+
+        Ok(a)
+    }
+}
+
+impl<'tcx, D> ObligationEmittingRelation<'tcx> for TypeRelating<'_, 'tcx, D>
+where
+    D: TypeRelatingDelegate<'tcx>,
+{
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        self.delegate.param_env()
+    }
+
+    fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) {
+        self.delegate.register_obligations(
+            obligations
+                .into_iter()
+                .map(|to_pred| {
+                    Obligation::new(self.tcx(), ObligationCause::dummy(), self.param_env(), to_pred)
+                })
+                .collect(),
+        );
+    }
+
+    fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
+        self.delegate.register_obligations(obligations);
+    }
+
+    fn alias_relate_direction(&self) -> ty::AliasRelationDirection {
+        unreachable!("manually overridden to handle ty::Variance::Contravariant ambient variance")
+    }
+
+    fn register_type_relate_obligation(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) {
+        self.register_predicates([ty::Binder::dummy(match self.ambient_variance {
+            ty::Variance::Covariant => ty::PredicateKind::AliasRelate(
+                a.into(),
+                b.into(),
+                ty::AliasRelationDirection::Subtype,
+            ),
+            // a :> b is b <: a
+            ty::Variance::Contravariant => ty::PredicateKind::AliasRelate(
+                b.into(),
+                a.into(),
+                ty::AliasRelationDirection::Subtype,
+            ),
+            ty::Variance::Invariant => ty::PredicateKind::AliasRelate(
+                a.into(),
+                b.into(),
+                ty::AliasRelationDirection::Equate,
+            ),
+            // FIXME(deferred_projection_equality): Implement this when we trigger it.
+            // Probably just need to do nothing here.
+            ty::Variance::Bivariant => {
+                unreachable!("cannot defer an alias-relate goal with Bivariant variance (yet?)")
+            }
+        })]);
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/relate/sub.rs b/compiler/rustc_infer/src/infer/relate/sub.rs
new file mode 100644
index 000000000..36876acd7
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/relate/sub.rs
@@ -0,0 +1,217 @@
+use super::combine::CombineFields;
+use crate::infer::{DefineOpaqueTypes, ObligationEmittingRelation, SubregionOrigin};
+use crate::traits::{Obligation, PredicateObligations};
+
+use rustc_middle::ty::relate::{Cause, Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::visit::TypeVisitableExt;
+use rustc_middle::ty::TyVar;
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use std::mem;
+
+/// Ensures `a` is made a subtype of `b`. Returns `a` on success.
+pub struct Sub<'combine, 'a, 'tcx> {
+    fields: &'combine mut CombineFields<'a, 'tcx>,
+    a_is_expected: bool,
+}
+
+impl<'combine, 'infcx, 'tcx> Sub<'combine, 'infcx, 'tcx> {
+    pub fn new(
+        f: &'combine mut CombineFields<'infcx, 'tcx>,
+        a_is_expected: bool,
+    ) -> Sub<'combine, 'infcx, 'tcx> {
+        Sub { fields: f, a_is_expected }
+    }
+
+    fn with_expected_switched<R, F: FnOnce(&mut Self) -> R>(&mut self, f: F) -> R {
+        self.a_is_expected = !self.a_is_expected;
+        let result = f(self);
+        self.a_is_expected = !self.a_is_expected;
+        result
+    }
+}
+
+impl<'tcx> TypeRelation<'tcx> for Sub<'_, '_, 'tcx> {
+    fn tag(&self) -> &'static str {
+        "Sub"
+    }
+
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.fields.infcx.tcx
+    }
+
+    fn a_is_expected(&self) -> bool {
+        self.a_is_expected
+    }
+
+    fn with_cause<F, R>(&mut self, cause: Cause, f: F) -> R
+    where
+        F: FnOnce(&mut Self) -> R,
+    {
+        debug!("sub with_cause={:?}", cause);
+        let old_cause = mem::replace(&mut self.fields.cause, Some(cause));
+        let r = f(self);
+        debug!("sub old_cause={:?}", old_cause);
+        self.fields.cause = old_cause;
+        r
+    }
+
+    fn relate_with_variance<T: Relate<'tcx>>(
+        &mut self,
+        variance: ty::Variance,
+        _info: ty::VarianceDiagInfo<'tcx>,
+        a: T,
+        b: T,
+    ) -> RelateResult<'tcx, T> {
+        match variance {
+            ty::Invariant => self.fields.equate(self.a_is_expected).relate(a, b),
+            ty::Covariant => self.relate(a, b),
+            ty::Bivariant => Ok(a),
+            ty::Contravariant => self.with_expected_switched(|this| this.relate(b, a)),
+        }
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        if a == b {
+            return Ok(a);
+        }
+
+        let infcx = self.fields.infcx;
+        let a = infcx.inner.borrow_mut().type_variables().replace_if_possible(a);
+        let b = infcx.inner.borrow_mut().type_variables().replace_if_possible(b);
+
+        match (a.kind(), b.kind()) {
+            (&ty::Infer(TyVar(_)), &ty::Infer(TyVar(_))) => {
+                // Shouldn't have any LBR here, so we can safely put
+                // this under a binder below without fear of accidental
+                // capture.
+                assert!(!a.has_escaping_bound_vars());
+                assert!(!b.has_escaping_bound_vars());
+
+                // can't make progress on `A <: B` if both A and B are
+                // type variables, so record an obligation.
+                self.fields.obligations.push(Obligation::new(
+                    self.tcx(),
+                    self.fields.trace.cause.clone(),
+                    self.fields.param_env,
+                    ty::Binder::dummy(ty::PredicateKind::Subtype(ty::SubtypePredicate {
+                        a_is_expected: self.a_is_expected,
+                        a,
+                        b,
+                    })),
+                ));
+
+                Ok(a)
+            }
+            (&ty::Infer(TyVar(a_id)), _) => {
+                self.fields.instantiate(b, ty::Contravariant, a_id, !self.a_is_expected)?;
+                Ok(a)
+            }
+            (_, &ty::Infer(TyVar(b_id))) => {
+                self.fields.instantiate(a, ty::Covariant, b_id, self.a_is_expected)?;
+                Ok(a)
+            }
+
+            (&ty::Error(e), _) | (_, &ty::Error(e)) => {
+                infcx.set_tainted_by_errors(e);
+                Ok(Ty::new_error(self.tcx(), e))
+            }
+
+            (
+                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }),
+                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }),
+            ) if a_def_id == b_def_id => {
+                self.fields.infcx.super_combine_tys(self, a, b)?;
+                Ok(a)
+            }
+            (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _)
+            | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }))
+                if self.fields.define_opaque_types == DefineOpaqueTypes::Yes
+                    && def_id.is_local()
+                    && !self.fields.infcx.next_trait_solver() =>
+            {
+                self.fields.obligations.extend(
+                    infcx
+                        .handle_opaque_type(
+                            a,
+                            b,
+                            self.a_is_expected,
+                            &self.fields.trace.cause,
+                            self.param_env(),
+                        )?
+                        .obligations,
+                );
+                Ok(a)
+            }
+            _ => {
+                self.fields.infcx.super_combine_tys(self, a, b)?;
+                Ok(a)
+            }
+        }
+    }
+
+    fn regions(
+        &mut self,
+        a: ty::Region<'tcx>,
+        b: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        debug!("{}.regions({:?}, {:?}) self.cause={:?}", self.tag(), a, b, self.fields.cause);
+
+        // FIXME -- we have more fine-grained information available
+        // from the "cause" field, we could perhaps give more tailored
+        // error messages.
+        let origin = SubregionOrigin::Subtype(Box::new(self.fields.trace.clone()));
+        // Subtype(&'a u8, &'b u8) => Outlives('a: 'b) => SubRegion('b, 'a)
+        self.fields
+            .infcx
+            .inner
+            .borrow_mut()
+            .unwrap_region_constraints()
+            .make_subregion(origin, b, a);
+
+        Ok(a)
+    }
+
+    fn consts(
+        &mut self,
+        a: ty::Const<'tcx>,
+        b: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        self.fields.infcx.super_combine_consts(self, a, b)
+    }
+
+    fn binders<T>(
+        &mut self,
+        a: ty::Binder<'tcx, T>,
+        b: ty::Binder<'tcx, T>,
+    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+    where
+        T: Relate<'tcx>,
+    {
+        // A binder is always a subtype of itself if it's structurally equal to itself
+        if a == b {
+            return Ok(a);
+        }
+
+        self.fields.higher_ranked_sub(a, b, self.a_is_expected)?;
+        Ok(a)
+    }
+}
+
+impl<'tcx> ObligationEmittingRelation<'tcx> for Sub<'_, '_, 'tcx> {
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        self.fields.param_env
+    }
+
+    fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) {
+        self.fields.register_predicates(obligations);
+    }
+
+    fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
+        self.fields.register_obligations(obligations);
+    }
+
+    fn alias_relate_direction(&self) -> ty::AliasRelationDirection {
+        ty::AliasRelationDirection::Subtype
+    }
+}