relate_tys.rs

use rustc_data_structures::fx::FxHashMap;
use rustc_errors::ErrorGuaranteed;
use rustc_infer::infer::type_variable::TypeVariableOrigin;
use rustc_infer::infer::NllRegionVariableOrigin;
use rustc_infer::infer::{ObligationEmittingRelation, StructurallyRelateAliases};
use rustc_infer::traits::{Obligation, PredicateObligations};
use rustc_middle::mir::ConstraintCategory;
use rustc_middle::traits::query::NoSolution;
use rustc_middle::traits::ObligationCause;
use rustc_middle::ty::fold::FnMutDelegate;
use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
use rustc_span::symbol::sym;
use rustc_span::{Span, Symbol};

use crate::constraints::OutlivesConstraint;
use crate::diagnostics::UniverseInfo;
use crate::renumber::RegionCtxt;
use crate::type_check::{InstantiateOpaqueType, Locations, TypeChecker};

impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
    /// Adds sufficient constraints to ensure that `a R b` where `R` depends on `v`:
    ///
    /// - "Covariant" `a <: b`
    /// - "Invariant" `a == b`
    /// - "Contravariant" `a :> b`
    ///
    /// N.B., the type `a` is permitted to have unresolved inference
    /// variables, but not the type `b`.
    #[instrument(skip(self), level = "debug")]
    pub(super) fn relate_types(
        &mut self,
        a: Ty<'tcx>,
        v: ty::Variance,
        b: Ty<'tcx>,
        locations: Locations,
        category: ConstraintCategory<'tcx>,
    ) -> Result<(), NoSolution> {
        NllTypeRelating::new(self, locations, category, UniverseInfo::relate(a, b), v)
            .relate(a, b)?;
        Ok(())
    }

    /// Add sufficient constraints to ensure `a == b`. See also [Self::relate_types].
    pub(super) fn eq_args(
        &mut self,
        a: ty::GenericArgsRef<'tcx>,
        b: ty::GenericArgsRef<'tcx>,
        locations: Locations,
        category: ConstraintCategory<'tcx>,
    ) -> Result<(), NoSolution> {
        NllTypeRelating::new(
            self,
            locations,
            category,
            UniverseInfo::other(),
            ty::Variance::Invariant,
        )
        .relate(a, b)?;
        Ok(())
    }
}

pub struct NllTypeRelating<'me, 'bccx, 'tcx> {
    type_checker: &'me mut TypeChecker<'bccx, 'tcx>,

    /// Where (and why) is this relation taking place?
    locations: Locations,

    /// What category do we assign the resulting `'a: 'b` relationships?
    category: ConstraintCategory<'tcx>,

    /// Information so that error reporting knows what types we are relating
    /// when reporting a bound region error.
    universe_info: UniverseInfo<'tcx>,

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

impl<'me, 'bccx, 'tcx> NllTypeRelating<'me, 'bccx, 'tcx> {
    pub fn new(
        type_checker: &'me mut TypeChecker<'bccx, 'tcx>,
        locations: Locations,
        category: ConstraintCategory<'tcx>,
        universe_info: UniverseInfo<'tcx>,
        ambient_variance: ty::Variance,
    ) -> Self {
        Self {
            type_checker,
            locations,
            category,
            universe_info,
            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,
        }
    }

    fn relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()> {
        let infcx = self.type_checker.infcx;
        debug_assert!(!infcx.next_trait_solver());
        // `handle_opaque_type` cannot handle subtyping, so to support subtyping
        // we instead eagerly generalize here. This is a bit of a mess but will go
        // away once we're using the new solver.
        //
        // Given `opaque rel B`, we create a new infer var `ty_vid` constrain it
        // by using `ty_vid rel B` and then finally and end by equating `ty_vid` to
        // the opaque.
        let mut enable_subtyping = |ty, opaque_is_expected| {
            let ty_vid = infcx.next_ty_var_id_in_universe(
                TypeVariableOrigin { param_def_id: None, span: self.span() },
                ty::UniverseIndex::ROOT,
            );

            let variance = if opaque_is_expected {
                self.ambient_variance
            } else {
                self.ambient_variance.xform(ty::Contravariant)
            };

            self.type_checker.infcx.instantiate_ty_var(
                self,
                opaque_is_expected,
                ty_vid,
                variance,
                ty,
            )?;
            Ok(infcx.resolve_vars_if_possible(Ty::new_infer(infcx.tcx, ty::TyVar(ty_vid))))
        };

        let (a, b) = match (a.kind(), b.kind()) {
            (&ty::Alias(ty::Opaque, ..), _) => (a, enable_subtyping(b, true)?),
            (_, &ty::Alias(ty::Opaque, ..)) => (enable_subtyping(a, false)?, b),
            _ => unreachable!(
                "expected at least one opaque type in `relate_opaques`, got {a} and {b}."
            ),
        };
        let cause = ObligationCause::dummy_with_span(self.span());
        let obligations = infcx.handle_opaque_type(a, b, &cause, self.param_env())?.obligations;
        self.register_obligations(obligations);
        Ok(())
    }

    fn enter_forall<T, U>(
        &mut self,
        binder: ty::Binder<'tcx, T>,
        f: impl FnOnce(&mut Self, T) -> U,
    ) -> U
    where
        T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
    {
        let value = if let Some(inner) = binder.no_bound_vars() {
            inner
        } else {
            let infcx = self.type_checker.infcx;
            let mut lazy_universe = None;
            let delegate = FnMutDelegate {
                regions: &mut |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 = self.create_next_universe();
                        lazy_universe = Some(universe);
                        universe
                    });

                    let placeholder = ty::PlaceholderRegion { universe, bound: br };
                    debug!(?placeholder);
                    let placeholder_reg = self.next_placeholder_region(placeholder);
                    debug!(?placeholder_reg);

                    placeholder_reg
                },
                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")
                },
            };

            infcx.tcx.replace_bound_vars_uncached(binder, delegate)
        };

        debug!(?value);
        f(self, value)
    }

    #[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 infcx = self.type_checker.infcx;
        let mut reg_map = FxHashMap::default();
        let delegate = FnMutDelegate {
            regions: &mut |br: ty::BoundRegion| {
                if let Some(ex_reg_var) = reg_map.get(&br) {
                    return *ex_reg_var;
                } else {
                    let ex_reg_var = self.next_existential_region_var(true, br.kind.get_name());
                    debug!(?ex_reg_var);
                    reg_map.insert(br, ex_reg_var);

                    ex_reg_var
                }
            },
            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 = infcx.tcx.replace_bound_vars_uncached(binder, delegate);
        debug!(?replaced);

        replaced
    }

    fn create_next_universe(&mut self) -> ty::UniverseIndex {
        let universe = self.type_checker.infcx.create_next_universe();
        self.type_checker
            .borrowck_context
            .constraints
            .universe_causes
            .insert(universe, self.universe_info.clone());
        universe
    }

    #[instrument(skip(self), level = "debug")]
    fn next_existential_region_var(
        &mut self,
        from_forall: bool,
        name: Option<Symbol>,
    ) -> ty::Region<'tcx> {
        let origin = NllRegionVariableOrigin::Existential { from_forall };

        let reg_var =
            self.type_checker.infcx.next_nll_region_var(origin, || RegionCtxt::Existential(name));

        reg_var
    }

    #[instrument(skip(self), level = "debug")]
    fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> {
        let reg = self
            .type_checker
            .borrowck_context
            .constraints
            .placeholder_region(self.type_checker.infcx, placeholder);

        let reg_info = match placeholder.bound.kind {
            ty::BoundRegionKind::BrAnon => sym::anon,
            ty::BoundRegionKind::BrNamed(_, name) => name,
            ty::BoundRegionKind::BrEnv => sym::env,
        };

        if cfg!(debug_assertions) {
            let mut var_to_origin = self.type_checker.infcx.reg_var_to_origin.borrow_mut();
            let new = RegionCtxt::Placeholder(reg_info);
            let prev = var_to_origin.insert(reg.as_var(), new);
            if let Some(prev) = prev {
                assert_eq!(new, prev);
            }
        }

        reg
    }

    fn push_outlives(
        &mut self,
        sup: ty::Region<'tcx>,
        sub: ty::Region<'tcx>,
        info: ty::VarianceDiagInfo<'tcx>,
    ) {
        let sub = self.type_checker.borrowck_context.universal_regions.to_region_vid(sub);
        let sup = self.type_checker.borrowck_context.universal_regions.to_region_vid(sup);
        self.type_checker.borrowck_context.constraints.outlives_constraints.push(
            OutlivesConstraint {
                sup,
                sub,
                locations: self.locations,
                span: self.locations.span(self.type_checker.body),
                category: self.category,
                variance_info: info,
                from_closure: false,
            },
        );
    }
}

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

    fn tag(&self) -> &'static str {
        "nll::subtype"
    }

    #[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 {
            Ok(a)
        } else {
            self.relate(a, b)
        };

        self.ambient_variance = old_ambient_variance;

        r
    }

    #[instrument(skip(self), level = "debug")]
    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
        let infcx = self.type_checker.infcx;

        let a = self.type_checker.infcx.shallow_resolve(a);
        assert!(!b.has_non_region_infer(), "unexpected inference var {:?}", b);

        if a == b {
            return Ok(a);
        }

        match (a.kind(), b.kind()) {
            (_, &ty::Infer(ty::TyVar(_))) => {
                span_bug!(
                    self.span(),
                    "should not be relating type variables on the right in MIR typeck"
                );
            }

            (&ty::Infer(ty::TyVar(a_vid)), _) => {
                infcx.instantiate_ty_var(self, true, a_vid, self.ambient_variance, 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).map(|_| ()).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.type_checker.infcx.next_trait_solver());
                    self.tcx().dcx().span_delayed_bug(
                        self.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.type_checker.infcx.next_trait_solver() =>
            {
                self.relate_opaques(a, b)?;
            }

            _ => {
                debug!(?a, ?b, ?self.ambient_variance);

                // Will also handle unification of `IntVar` and `FloatVar`.
                self.type_checker.infcx.super_combine_tys(self, a, b)?;
            }
        }

        Ok(a)
    }

    #[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>,
        b: ty::Const<'tcx>,
    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
        let a = self.type_checker.infcx.shallow_resolve(a);
        assert!(!a.has_non_region_infer(), "unexpected inference var {:?}", a);
        assert!(!b.has_non_region_infer(), "unexpected inference var {:?}", b);

        self.type_checker.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));
        }

        match self.ambient_variance {
            ty::Variance::Covariant => {
                // 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).

                // Note: the order here is important. Create the placeholders first, otherwise
                // we assign the wrong universe to the existential!
                self.enter_forall(b, |this, b| {
                    let a = this.instantiate_binder_with_existentials(a);
                    this.relate(a, b)
                })?;
            }

            ty::Variance::Contravariant => {
                // 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.

                // Note: the order here is important. Create the placeholders first, otherwise
                // we assign the wrong universe to the existential!
                self.enter_forall(a, |this, a| {
                    let b = this.instantiate_binder_with_existentials(b);
                    this.relate(a, b)
                })?;
            }

            ty::Variance::Invariant => {
                // Invariant, so we want `for<..> A == for<..> B` --
                // therefore we want `exists<..> A == for<..> B` and
                // `exists<..> B == for<..> A`.
                //
                // See the comment in `fn Equate::binders` for more details.

                // Note: the order here is important. Create the placeholders first, otherwise
                // we assign the wrong universe to the existential!
                self.enter_forall(b, |this, b| {
                    let a = this.instantiate_binder_with_existentials(a);
                    this.relate(a, b)
                })?;
                // Note: the order here is important. Create the placeholders first, otherwise
                // we assign the wrong universe to the existential!
                self.enter_forall(a, |this, a| {
                    let b = this.instantiate_binder_with_existentials(b);
                    this.relate(a, b)
                })?;
            }

            ty::Variance::Bivariant => {}
        }

        Ok(a)
    }
}

impl<'bccx, 'tcx> ObligationEmittingRelation<'tcx> for NllTypeRelating<'_, 'bccx, 'tcx> {
    fn span(&self) -> Span {
        self.locations.span(self.type_checker.body)
    }

    fn structurally_relate_aliases(&self) -> StructurallyRelateAliases {
        StructurallyRelateAliases::No
    }

    fn param_env(&self) -> ty::ParamEnv<'tcx> {
        self.type_checker.param_env
    }

    fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) {
        self.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>) {
        let _: Result<_, ErrorGuaranteed> = self.type_checker.fully_perform_op(
            self.locations,
            self.category,
            InstantiateOpaqueType {
                obligations,
                // These fields are filled in during execution of the operation
                base_universe: None,
                region_constraints: None,
            },
        );
    }

    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,
            ),
            ty::Variance::Bivariant => {
                unreachable!("cannot defer an alias-relate goal with Bivariant variance (yet?)")
            }
        })]);
    }
}