rustc_infer/infer/relate/

generalize.rs

use std::mem;

use rustc_data_structures::sso::SsoHashMap;
use rustc_data_structures::stack::ensure_sufficient_stack;
use rustc_hir::def_id::DefId;
use rustc_middle::bug;
use rustc_middle::ty::error::TypeError;
use rustc_middle::ty::{
    self, InferConst, Term, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitableExt,
    TypeVisitor,
};
use rustc_span::Span;
use tracing::{debug, instrument, warn};

use super::{
    PredicateEmittingRelation, Relate, RelateResult, StructurallyRelateAliases, TypeRelation,
};
use crate::infer::type_variable::TypeVariableValue;
use crate::infer::unify_key::ConstVariableValue;
use crate::infer::{InferCtxt, RegionVariableOrigin, relate};

#[derive(Copy, Clone, Eq, PartialEq, Debug)]
enum TermVid {
    Ty(ty::TyVid),
    Const(ty::ConstVid),
}

impl From<ty::TyVid> for TermVid {
    fn from(value: ty::TyVid) -> Self {
        TermVid::Ty(value)
    }
}

impl From<ty::ConstVid> for TermVid {
    fn from(value: ty::ConstVid) -> Self {
        TermVid::Const(value)
    }
}

impl<'tcx> InferCtxt<'tcx> {
    /// The idea is that we should ensure that the type variable `target_vid`
    /// is equal to, a subtype of, or a supertype of `source_ty`.
    ///
    /// For this, we will instantiate `target_vid` with a *generalized* version
    /// of `source_ty`. Generalization introduces other inference variables wherever
    /// subtyping could occur. This also does the occurs checks, detecting whether
    /// instantiating `target_vid` would result in a cyclic type. We eagerly error
    /// in this case.
    ///
    /// This is *not* expected to be used anywhere except for an implementation of
    /// `TypeRelation`. Do not use this, and instead please use `At::eq`, for all
    /// other usecases (i.e. setting the value of a type var).
    #[instrument(level = "debug", skip(self, relation))]
    pub fn instantiate_ty_var<R: PredicateEmittingRelation<InferCtxt<'tcx>>>(
        &self,
        relation: &mut R,
        target_is_expected: bool,
        target_vid: ty::TyVid,
        instantiation_variance: ty::Variance,
        source_ty: Ty<'tcx>,
    ) -> RelateResult<'tcx, ()> {
        debug_assert!(self.inner.borrow_mut().type_variables().probe(target_vid).is_unknown());

        self.instantiate_var(
            relation,
            target_is_expected,
            target_vid.into(),
            instantiation_variance,
            source_ty.into(),
        )
    }

    /// Instantiates 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 alias 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::Alias` 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, relation))]
    pub(crate) fn instantiate_const_var<R: PredicateEmittingRelation<InferCtxt<'tcx>>>(
        &self,
        relation: &mut R,
        target_is_expected: bool,
        target_vid: ty::ConstVid,
        source_ct: ty::Const<'tcx>,
    ) -> RelateResult<'tcx, ()> {
        // FIXME(generic_const_exprs): Occurs check failures for alias consts
        // and generic expressions are not yet handled correctly.
        debug_assert!(
            self.inner.borrow_mut().const_unification_table().probe_value(target_vid).is_unknown()
        );

        self.instantiate_var(
            relation,
            target_is_expected,
            target_vid.into(),
            ty::Invariant,
            source_ct.into(),
        )
    }

    #[instrument(level = "debug", skip(self, relation))]
    fn instantiate_var<R: PredicateEmittingRelation<Self>>(
        &self,
        relation: &mut R,
        target_is_expected: bool,
        target_vid: TermVid,
        instantiation_variance: ty::Variance,
        source_term: Term<'tcx>,
    ) -> RelateResult<'tcx, ()> {
        // Generalize `source_term` depending on the current variance. As an example, assume
        // `?target <: &'x ?1`, where `'x` is some free region and `?1` is an inference
        // variable.
        //
        // Then the `generalized_term` would be `&'?2 ?3`, where `'?2` and `?3` are fresh
        // region/type inference variables.
        //
        // We then relate `generalized_term <: source_term`, adding constraints like `'x: '?2` and
        // `?1 <: ?3`.
        let Generalization { value_may_be_infer: generalized_term } = self.generalize(
            relation.span(),
            relation.structurally_relate_aliases(),
            target_vid,
            instantiation_variance,
            source_term,
        )?;

        // Constrain `b_vid` to the generalized type `generalized_term`.
        self.union_var_term(target_vid, generalized_term);

        // Finally, relate `generalized_term` to `source_term`, 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 generalized_term.is_infer() {
            // 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`.
            let Some(source_alias) = source_term.to_alias_term() else {
                bug!("generalized `{source_term:?} to infer, not an alias");
            };
            if self.next_trait_solver() {
                if let Some(generalized_ty) = generalized_term.as_type() {
                    match instantiation_variance {
                        ty::Invariant => relation.register_predicates([ty::ProjectionPredicate {
                            projection_term: source_alias.into(),
                            term: generalized_ty.into(),
                        }]),
                        ty::Covariant => {
                            // Generate a new var, then do:
                            // `source_alias == ?A && ?A <: generalized_ty`
                            let new_var = self.next_ty_var(relation.span());
                            relation.register_predicates([
                                ty::PredicateKind::Subtype(ty::SubtypePredicate {
                                    a_is_expected: !target_is_expected,
                                    a: new_var,
                                    b: generalized_ty,
                                }),
                                ty::PredicateKind::Clause(ty::ClauseKind::Projection(
                                    ty::ProjectionPredicate {
                                        projection_term: source_alias.into(),
                                        term: new_var.into(),
                                    },
                                )),
                            ]);
                        }
                        ty::Contravariant => {
                            // a :> b is b <: a
                            let new_var = self.next_ty_var(relation.span());
                            relation.register_predicates([
                                ty::PredicateKind::Subtype(ty::SubtypePredicate {
                                    a_is_expected: target_is_expected,
                                    a: generalized_ty,
                                    b: new_var,
                                }),
                                ty::PredicateKind::Clause(ty::ClauseKind::Projection(
                                    ty::ProjectionPredicate {
                                        projection_term: source_alias.into(),
                                        term: new_var.into(),
                                    },
                                )),
                            ]);
                        }
                        ty::Bivariant => unreachable!("bivariant generalization"),
                    }
                } else {
                    debug_assert_eq!(instantiation_variance, ty::Variance::Invariant);
                    relation.register_predicates([ty::ProjectionPredicate {
                        projection_term: source_alias,
                        term: generalized_term,
                    }]);
                }
            } else {
                match source_alias.kind {
                    ty::AliasTermKind::ProjectionTy { .. }
                    | ty::AliasTermKind::ProjectionConst { .. } => {
                        // FIXME: This does not handle subtyping correctly, we could
                        // instead create a new inference variable `?normalized_source`, emitting
                        // `Projection(normalized_source, ?ty_normalized)` and
                        // `?normalized_source <: generalized_term`.
                        relation.register_predicates([ty::ProjectionPredicate {
                            projection_term: source_alias,
                            term: generalized_term,
                        }]);
                    }
                    // The old solver only accepts projection predicates for associated types.
                    ty::AliasTermKind::InherentTy { .. }
                    | ty::AliasTermKind::FreeTy { .. }
                    | ty::AliasTermKind::OpaqueTy { .. } => {
                        return Err(TypeError::CyclicTy(source_term.expect_type()));
                    }
                    ty::AliasTermKind::InherentConst { .. }
                    | ty::AliasTermKind::FreeConst { .. }
                    | ty::AliasTermKind::AnonConst { .. } => {
                        return Err(TypeError::CyclicConst(source_term.expect_const()));
                    }
                }
            }
        } else {
            // NOTE: The `instantiation_variance` is not the same variance as
            // used by the relation. When instantiating `b`, `target_is_expected`
            // is flipped and the `instantiation_variance` is also flipped. To
            // constrain the `generalized_term` while using the original relation,
            // we therefore only have to flip the arguments.
            //
            // ```ignore (not code)
            // ?a rel B
            // instantiate_ty_var(?a, B) # expected and variance not flipped
            // B' rel B
            // ```
            // or
            // ```ignore (not code)
            // A rel ?b
            // instantiate_ty_var(?b, A) # expected and variance flipped
            // A rel A'
            // ```
            match generalized_term.kind() {
                ty::TermKind::Ty(_) => {
                    if target_is_expected {
                        relation.relate(generalized_term, source_term)?;
                    } else {
                        debug!("flip relation");
                        relation.relate(source_term, generalized_term)?;
                    }
                }
                ty::TermKind::Const(_) => {
                    // Override consts to always be invariant
                    if target_is_expected {
                        relation.relate_with_variance(
                            ty::Invariant,
                            ty::VarianceDiagInfo::default(),
                            generalized_term,
                            source_term,
                        )?;
                    } else {
                        relation.relate_with_variance(
                            ty::Invariant,
                            ty::VarianceDiagInfo::default(),
                            source_term,
                            generalized_term,
                        )?;
                    }
                }
            }
        }

        Ok(())
    }

    /// This is a thin wrapper around inserting into the var tables. You probably want
    /// [`Self::instantiate_var`] instead, which calls this method.
    fn union_var_term(&self, l: TermVid, r: ty::Term<'tcx>) {
        match (l, r.kind()) {
            (TermVid::Ty(l), ty::TermKind::Ty(r)) => {
                if let Some(r) = r.ty_vid() {
                    self.inner.borrow_mut().type_variables().equate(l, r)
                } else {
                    self.inner.borrow_mut().type_variables().instantiate(l, r)
                }
            }
            (TermVid::Const(l), ty::TermKind::Const(r)) => {
                if let Some(r) = r.ct_vid() {
                    self.inner.borrow_mut().const_unification_table().union(l, r)
                } else {
                    self.inner
                        .borrow_mut()
                        .const_unification_table()
                        .union_value(l, ConstVariableValue::Known { value: r })
                }
            }
            _ => bug!("mismatched term kinds in generalize: {l:?}, {r:?}"),
        }
    }

    /// Attempts to generalize `source_term` for the type variable `target_vid`.
    /// This checks for cycles -- that is, whether `source_term` references `target_vid`.
    fn generalize(
        &self,
        span: Span,
        structurally_relate_aliases: StructurallyRelateAliases,
        target_vid: TermVid,
        ambient_variance: ty::Variance,
        source_term: Term<'tcx>,
    ) -> RelateResult<'tcx, Generalization<Term<'tcx>>> {
        assert!(!source_term.has_escaping_bound_vars());
        let (for_universe, root_vid) = match target_vid {
            TermVid::Ty(ty_vid) => {
                (self.try_resolve_ty_var(ty_vid).unwrap_err(), TermVid::Ty(self.root_var(ty_vid)))
            }
            TermVid::Const(ct_vid) => (
                self.try_resolve_const_var(ct_vid).unwrap_err(),
                TermVid::Const(self.inner.borrow_mut().const_unification_table().find(ct_vid).vid),
            ),
        };

        let mut generalizer = Generalizer {
            infcx: self,
            span,
            structurally_relate_aliases,
            root_vid,
            for_universe,
            root_term: source_term,
            ambient_variance,
            in_alias: false,
            cache: Default::default(),
        };

        let value_may_be_infer = generalizer.relate(source_term, source_term)?;
        Ok(Generalization { value_may_be_infer })
    }
}

/// Finds the max universe present
struct MaxUniverse {
    max_universe: ty::UniverseIndex,
}

impl MaxUniverse {
    fn new() -> Self {
        MaxUniverse { max_universe: ty::UniverseIndex::ROOT }
    }

    fn max_universe(self) -> ty::UniverseIndex {
        self.max_universe
    }
}

impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxUniverse {
    fn visit_ty(&mut self, t: Ty<'tcx>) {
        if let ty::Placeholder(placeholder) = t.kind() {
            self.max_universe = self.max_universe.max(placeholder.universe);
        }

        t.super_visit_with(self)
    }

    fn visit_const(&mut self, c: ty::Const<'tcx>) {
        if let ty::ConstKind::Placeholder(placeholder) = c.kind() {
            self.max_universe = self.max_universe.max(placeholder.universe);
        }

        c.super_visit_with(self)
    }

    fn visit_region(&mut self, r: ty::Region<'tcx>) {
        if let ty::RePlaceholder(placeholder) = r.kind() {
            self.max_universe = self.max_universe.max(placeholder.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> {
    infcx: &'me InferCtxt<'tcx>,

    span: Span,

    /// Whether aliases should be related structurally. If not, we have to
    /// be careful when generalizing aliases.
    structurally_relate_aliases: StructurallyRelateAliases,

    /// 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: 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>,

    /// 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,

    /// 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,

    cache: SsoHashMap<(Ty<'tcx>, ty::Variance, bool), Ty<'tcx>>,
}

impl<'tcx> Generalizer<'_, 'tcx> {
    /// Create an error that corresponds to the term kind in `root_term`
    fn cyclic_term_error(&self) -> TypeError<'tcx> {
        match self.root_term.kind() {
            ty::TermKind::Ty(ty) => TypeError::CyclicTy(ty),
            ty::TermKind::Const(ct) => TypeError::CyclicConst(ct),
        }
    }

    /// Create a new type variable in the universe of the target when
    /// generalizing an alias.
    fn next_var_for_alias_of_kind(&self, alias: ty::AliasTerm<'tcx>) -> ty::Term<'tcx> {
        if alias.kind.is_type() {
            self.infcx.next_ty_var_in_universe(self.span, self.for_universe).into()
        } else {
            self.infcx.next_const_var_in_universe(self.span, self.for_universe).into()
        }
    }

    /// We only handle potentially normalizable aliases via this method. For rigid alias,
    /// we always generalize structurally.
    ///
    /// 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 normalizable alias
    /// and generalizing it to an inference variable. In the new solver,
    /// we always generalize to an infer var unless the alias contains escaping
    /// bound variables.
    ///
    /// Correctly handling aliases with escaping bound variables is
    /// difficult and currently incomplete in two opposite ways:
    /// - if we get an occurs check failure in the alias, replace it with a new infer var.
    ///   This causes us to later emit an alias-relate goal and is incomplete in case the
    ///   alias normalizes to type containing one of the bound variables.
    /// - if the alias contains an inference variable not nameable by `for_universe`, we
    ///   continue generalizing the alias. This ends up pulling down the universe of the
    ///   inference variable and is incomplete in case the alias would normalize to a type
    ///   which does not mention that inference variable.
    fn generalize_alias_term(
        &mut self,
        alias: ty::AliasTerm<'tcx>,
    ) -> Result<Term<'tcx>, TypeError<'tcx>> {
        // We do not eagerly replace aliases with inference variables if they have
        // escaping bound vars, see the method comment for details. However, when we
        // are inside of an alias with escaping bound vars replacing nested aliases
        // with inference variables can cause incorrect ambiguity.
        //
        // cc trait-system-refactor-initiative#110
        if self.infcx.next_trait_solver() && !alias.has_escaping_bound_vars() && !self.in_alias {
            return Ok(self.next_var_for_alias_of_kind(alias));
        }

        let is_nested_alias = mem::replace(&mut self.in_alias, true);
        let result = match self.relate(alias, alias) {
            Ok(alias) => Ok(alias.to_term(self.cx(), ty::IsRigid::No)),
            Err(e) => {
                if is_nested_alias {
                    return Err(e);
                } else {
                    let mut visitor = MaxUniverse::new();
                    alias.visit_with(&mut visitor);
                    let infer_replacement_is_complete =
                        self.for_universe.can_name(visitor.max_universe())
                            && !alias.has_escaping_bound_vars();
                    if !infer_replacement_is_complete {
                        warn!("may incompletely handle alias type: {alias:?}");
                    }

                    debug!("generalization failure in alias");
                    Ok(self.next_var_for_alias_of_kind(alias))
                }
            }
        };
        self.in_alias = is_nested_alias;
        result
    }
}

impl<'tcx> TypeRelation<TyCtxt<'tcx>> for Generalizer<'_, 'tcx> {
    fn cx(&self) -> TyCtxt<'tcx> {
        self.infcx.tcx
    }

    fn relate_ty_args(
        &mut self,
        a_ty: Ty<'tcx>,
        _: Ty<'tcx>,
        def_id: DefId,
        a_args: ty::GenericArgsRef<'tcx>,
        b_args: ty::GenericArgsRef<'tcx>,
        mk: impl FnOnce(ty::GenericArgsRef<'tcx>) -> Ty<'tcx>,
    ) -> RelateResult<'tcx, Ty<'tcx>> {
        let args = if self.ambient_variance == ty::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_args, b_args)
        } else {
            let tcx = self.cx();
            let variances = tcx.variances_of(def_id);
            relate::relate_args_with_variances(self, variances, a_args, b_args)
        }?;
        if args == a_args { Ok(a_ty) } else { Ok(mk(args)) }
    }

    #[instrument(level = "debug", skip(self, variance, b), ret)]
    fn relate_with_variance<T: Relate<TyCtxt<'tcx>>>(
        &mut self,
        variance: ty::Variance,
        _info: ty::VarianceDiagInfo<TyCtxt<'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");
        // Recursive calls to `relate` can overflow the stack. For example a deeper version of
        // `ui/associated-consts/issue-93775.rs`.
        let r = ensure_sufficient_stack(|| self.relate(a, b));
        self.ambient_variance = old_ambient_variance;
        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, self.ambient_variance, self.in_alias)) {
            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::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);
                if TermVid::Ty(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);
                                    }
                                }

                                // We do need a fresh type variable otherwise.
                                ty::Bivariant | 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);
                            // Record that `vid` and `new_var_id` have to be subtypes
                            // of each other. This is currently only used for diagnostics.
                            // To see why, see the docs in the `type_variables` module.
                            inner.type_variables().sub_unify(vid, new_var_id);
                            // If we're in the new solver and create a new inference
                            // variable inside of an alias we eagerly constrain that
                            // inference variable to prevent unexpected ambiguity errors.
                            //
                            // This is incomplete as it pulls down the universe of the
                            // original inference variable, even though the alias could
                            // normalize to a type which does not refer to that type at
                            // all. I don't expect this to cause unexpected errors in
                            // practice.
                            //
                            // We only need to do so for type and const variables, as
                            // region variables do not impact normalization, and will get
                            // correctly constrained by `AliasRelate` later on.
                            //
                            // cc trait-system-refactor-initiative#108
                            if self.infcx.next_trait_solver()
                                && !self.infcx.typing_mode_raw().is_coherence()
                                && self.in_alias
                            {
                                inner.type_variables().equate(vid, new_var_id);
                            }

                            debug!("replacing original vid={:?} with new={:?}", vid, new_var_id);
                            Ok(Ty::new_var(self.cx(), new_var_id))
                        }
                    }
                }
            }

            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)
                }
            }

            // We only need to be careful with potentially normalizeable
            // aliases here. See `generalize_alias_term` for more information.
            ty::Alias(ty::IsRigid::No, data) => match self.structurally_relate_aliases {
                StructurallyRelateAliases::No => {
                    self.generalize_alias_term(data.into()).map(|v| v.expect_type())
                }
                StructurallyRelateAliases::Yes => relate::structurally_relate_tys(self, t, t),
            },

            _ => relate::structurally_relate_tys(self, t, t),
        }?;

        self.cache.insert((t, self.ambient_variance, self.in_alias), 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.kind() {
            // 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
            .infcx
            .next_region_var_in_universe(RegionVariableOrigin::Misc(self.span), 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>> {
        let tcx = self.cx();
        assert_eq!(c, c2); // we are misusing TypeRelation here; both LHS and RHS ought to be ==

        match c.kind() {
            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 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();
                match variable_table.probe_value(vid) {
                    ConstVariableValue::Known { value: u } => {
                        drop(inner);
                        self.relate(u, u)
                    }
                    ConstVariableValue::Unknown { origin, universe } => {
                        if self.for_universe.can_name(universe) {
                            Ok(c)
                        } else {
                            let new_var_id = variable_table
                                .new_key(ConstVariableValue::Unknown {
                                    origin,
                                    universe: self.for_universe,
                                })
                                .vid;

                            // See the comment for type inference variables
                            // for more details.
                            if self.infcx.next_trait_solver()
                                && !self.infcx.typing_mode_raw().is_coherence()
                                && self.in_alias
                            {
                                variable_table.union(vid, new_var_id);
                            }
                            Ok(ty::Const::new_var(tcx, new_var_id))
                        }
                    }
                }
            }
            // FIXME: Alias consts are also not rigid, so the current
            // approach of always relating them structurally is incomplete.
            //
            // FIXME: replace the StructurallyRelateAliases::Yes branch with
            // `structurally_relate_consts` once it is fully structural.
            //
            // We only need to be careful with potentially normalizeable
            // aliases here. See `generalize_alias_term` for more information.
            ty::ConstKind::Alias(ty::IsRigid::No, alias_const) => {
                match self.structurally_relate_aliases {
                    // Hack: Fall back to old behavior if GCE is enabled (it used to just be the Yes
                    // path), as doing this new No path breaks some GCE things. I expect GCE to be
                    // ripped out soon so this shouldn't matter soon.
                    StructurallyRelateAliases::No if !tcx.features().generic_const_exprs() => {
                        self.generalize_alias_term(alias_const.into()).map(|v| v.expect_const())
                    }
                    _ => {
                        let ty::AliasConst { kind, args, .. } = alias_const;
                        let args = self.relate_with_variance(
                            ty::Invariant,
                            ty::VarianceDiagInfo::default(),
                            args,
                            args,
                        )?;
                        Ok(ty::Const::new_alias(
                            tcx,
                            ty::IsRigid::No,
                            ty::AliasConst::new(tcx, kind, args),
                        ))
                    }
                }
            }
            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<TyCtxt<'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)]
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 with care as it can
    /// otherwise very easily result in infinite
    /// recursion.
    pub value_may_be_infer: T,
}