summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_infer/src/infer/nll_relate
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/rustc_infer/src/infer/nll_relate')
-rw-r--r--compiler/rustc_infer/src/infer/nll_relate/mod.rs1080
1 files changed, 1080 insertions, 0 deletions
diff --git a/compiler/rustc_infer/src/infer/nll_relate/mod.rs b/compiler/rustc_infer/src/infer/nll_relate/mod.rs
new file mode 100644
index 000000000..bab4f3e9e
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/nll_relate/mod.rs
@@ -0,0 +1,1080 @@
+//! 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 crate::infer::combine::ConstEquateRelation;
+use crate::infer::InferCtxt;
+use crate::infer::{ConstVarValue, ConstVariableValue};
+use crate::infer::{TypeVariableOrigin, TypeVariableOriginKind};
+use rustc_data_structures::fx::FxHashMap;
+use rustc_middle::ty::error::TypeError;
+use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation};
+use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor};
+use rustc_middle::ty::{self, InferConst, Ty, TyCtxt};
+use rustc_span::Span;
+use std::fmt::Debug;
+use std::ops::ControlFlow;
+
+#[derive(PartialEq)]
+pub enum NormalizationStrategy {
+ Lazy,
+ Eager,
+}
+
+pub struct TypeRelating<'me, 'tcx, D>
+where
+ D: TypeRelatingDelegate<'tcx>,
+{
+ infcx: &'me InferCtxt<'me, '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>,
+
+ /// When we pass through a set of binders (e.g., when looking into
+ /// a `fn` type), we push a new bound region scope onto here. This
+ /// will contain the instantiated region for each region in those
+ /// binders. When we then encounter a `ReLateBound(d, br)`, we can
+ /// use the De Bruijn index `d` to find the right scope, and then
+ /// bound region name `br` to find the specific instantiation from
+ /// within that scope. See `replace_bound_region`.
+ ///
+ /// This field stores the instantiations for late-bound regions in
+ /// the `a` type.
+ a_scopes: Vec<BoundRegionScope<'tcx>>,
+
+ /// Same as `a_scopes`, but for the `b` type.
+ b_scopes: Vec<BoundRegionScope<'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 const_equate(&mut self, a: ty::Const<'tcx>, b: ty::Const<'tcx>);
+ fn register_opaque_type(
+ &mut self,
+ a: Ty<'tcx>,
+ b: Ty<'tcx>,
+ a_is_expected: bool,
+ ) -> Result<(), TypeError<'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) -> 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>;
+
+ /// Define the normalization strategy to use, eager or lazy.
+ fn normalization() -> NormalizationStrategy;
+
+ /// Enables some optimizations if we do not expect inference variables
+ /// in the RHS of the relation.
+ fn forbid_inference_vars() -> bool;
+}
+
+#[derive(Clone, Debug, Default)]
+struct BoundRegionScope<'tcx> {
+ map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>,
+}
+
+#[derive(Copy, Clone)]
+struct UniversallyQuantified(bool);
+
+impl<'me, 'tcx, D> TypeRelating<'me, 'tcx, D>
+where
+ D: TypeRelatingDelegate<'tcx>,
+{
+ pub fn new(
+ infcx: &'me InferCtxt<'me, 'tcx>,
+ delegate: D,
+ ambient_variance: ty::Variance,
+ ) -> Self {
+ Self {
+ infcx,
+ delegate,
+ ambient_variance,
+ ambient_variance_info: ty::VarianceDiagInfo::default(),
+ a_scopes: vec![],
+ b_scopes: vec![],
+ }
+ }
+
+ 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 create_scope(
+ &mut self,
+ value: ty::Binder<'tcx, impl Relate<'tcx>>,
+ universally_quantified: UniversallyQuantified,
+ ) -> BoundRegionScope<'tcx> {
+ let mut scope = BoundRegionScope::default();
+
+ // Create a callback that creates (via the delegate) either an
+ // existential or placeholder region as needed.
+ let mut next_region = {
+ let delegate = &mut self.delegate;
+ let mut lazy_universe = None;
+ move |br: ty::BoundRegion| {
+ if universally_quantified.0 {
+ // 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 = delegate.create_next_universe();
+ lazy_universe = Some(universe);
+ universe
+ });
+
+ let placeholder = ty::PlaceholderRegion { universe, name: br.kind };
+ delegate.next_placeholder_region(placeholder)
+ } else {
+ delegate.next_existential_region_var(true)
+ }
+ }
+ };
+
+ value.skip_binder().visit_with(&mut ScopeInstantiator {
+ next_region: &mut next_region,
+ target_index: ty::INNERMOST,
+ bound_region_scope: &mut scope,
+ });
+
+ scope
+ }
+
+ /// When we encounter binders during the type traversal, we record
+ /// the value to substitute for each of the things contained in
+ /// that binder. (This will be either a universal placeholder or
+ /// an existential inference variable.) Given the De Bruijn index
+ /// `debruijn` (and name `br`) of some binder we have now
+ /// encountered, this routine finds the value that we instantiated
+ /// the region with; to do so, it indexes backwards into the list
+ /// of ambient scopes `scopes`.
+ fn lookup_bound_region(
+ debruijn: ty::DebruijnIndex,
+ br: &ty::BoundRegion,
+ first_free_index: ty::DebruijnIndex,
+ scopes: &[BoundRegionScope<'tcx>],
+ ) -> ty::Region<'tcx> {
+ // The debruijn index is a "reverse index" into the
+ // scopes listing. So when we have INNERMOST (0), we
+ // want the *last* scope pushed, and so forth.
+ let debruijn_index = debruijn.index() - first_free_index.index();
+ let scope = &scopes[scopes.len() - debruijn_index - 1];
+
+ // Find this bound region in that scope to map to a
+ // particular region.
+ scope.map[br]
+ }
+
+ /// If `r` is a bound region, find the scope in which it is bound
+ /// (from `scopes`) and return the value that we instantiated it
+ /// with. Otherwise just return `r`.
+ fn replace_bound_region(
+ &self,
+ r: ty::Region<'tcx>,
+ first_free_index: ty::DebruijnIndex,
+ scopes: &[BoundRegionScope<'tcx>],
+ ) -> ty::Region<'tcx> {
+ debug!("replace_bound_regions(scopes={:?})", scopes);
+ if let ty::ReLateBound(debruijn, br) = *r {
+ Self::lookup_bound_region(debruijn, &br, first_free_index, scopes)
+ } else {
+ r
+ }
+ }
+
+ /// 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 projection type and some value type lazily. This will always
+ /// succeed, but we push an additional `ProjectionEq` goal depending
+ /// on the value type:
+ /// - if the value type is any type `T` which is not a projection, we push
+ /// `ProjectionEq(projection = T)`.
+ /// - if the value type is another projection `other_projection`, we create
+ /// a new inference variable `?U` and push the two goals
+ /// `ProjectionEq(projection = ?U)`, `ProjectionEq(other_projection = ?U)`.
+ fn relate_projection_ty(
+ &mut self,
+ projection_ty: ty::ProjectionTy<'tcx>,
+ value_ty: Ty<'tcx>,
+ ) -> Ty<'tcx> {
+ use rustc_span::DUMMY_SP;
+
+ match *value_ty.kind() {
+ ty::Projection(other_projection_ty) => {
+ let var = self.infcx.next_ty_var(TypeVariableOrigin {
+ kind: TypeVariableOriginKind::MiscVariable,
+ span: DUMMY_SP,
+ });
+ // FIXME(lazy-normalization): This will always ICE, because the recursive
+ // call will end up in the _ arm below.
+ self.relate_projection_ty(projection_ty, var);
+ self.relate_projection_ty(other_projection_ty, var);
+ var
+ }
+
+ _ => bug!("should never be invoked with eager normalization"),
+ }
+ }
+
+ /// 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);
+ }
+
+ ty::Projection(projection_ty) if D::normalization() == NormalizationStrategy::Lazy => {
+ return Ok(self.relate_projection_ty(projection_ty, self.infcx.tcx.mk_ty_var(vid)));
+ }
+
+ _ => (),
+ }
+
+ let generalized_ty = self.generalize_value(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_infer_types_or_consts());
+ }
+
+ self.infcx.inner.borrow_mut().type_variables().instantiate(vid, generalized_ty);
+
+ // The generalized values we extract from `canonical_var_values` have
+ // been fully instantiated and hence the set of scopes we have
+ // doesn't matter -- just to be sure, put an empty vector
+ // in there.
+ let old_a_scopes = std::mem::take(pair.vid_scopes(self));
+
+ // Relate the generalized kind to the original one.
+ let result = pair.relate_generalized_ty(self, generalized_ty);
+
+ // Restore the old scopes now.
+ *pair.vid_scopes(self) = old_a_scopes;
+
+ debug!("relate_ty_var: complete, result = {:?}", result);
+ result
+ }
+
+ fn generalize_value<T: Relate<'tcx>>(
+ &mut self,
+ value: T,
+ for_vid: ty::TyVid,
+ ) -> RelateResult<'tcx, T> {
+ let universe = self.infcx.probe_ty_var(for_vid).unwrap_err();
+
+ let mut generalizer = TypeGeneralizer {
+ infcx: self.infcx,
+ delegate: &mut self.delegate,
+ first_free_index: ty::INNERMOST,
+ ambient_variance: self.ambient_variance,
+ for_vid_sub_root: self.infcx.inner.borrow_mut().type_variables().sub_root_var(for_vid),
+ universe,
+ };
+
+ generalizer.relate(value, value)
+ }
+}
+
+/// 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>;
+
+ /// Extract the scopes that apply to whichever side of the tuple
+ /// the vid was found on. See the comment where this is called
+ /// for more details on why we want them.
+ fn vid_scopes<'r, D: TypeRelatingDelegate<'tcx>>(
+ &self,
+ relate: &'r mut TypeRelating<'_, 'tcx, D>,
+ ) -> &'r mut Vec<BoundRegionScope<'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 vid_scopes<'r, D>(
+ &self,
+ relate: &'r mut TypeRelating<'_, 'tcx, D>,
+ ) -> &'r mut Vec<BoundRegionScope<'tcx>>
+ where
+ D: TypeRelatingDelegate<'tcx>,
+ {
+ &mut relate.a_scopes
+ }
+
+ 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 vid_scopes<'r, D>(
+ &self,
+ relate: &'r mut TypeRelating<'_, 'tcx, D>,
+ ) -> &'r mut Vec<BoundRegionScope<'tcx>>
+ where
+ D: TypeRelatingDelegate<'tcx>,
+ {
+ &mut relate.b_scopes
+ }
+
+ 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 param_env(&self) -> ty::ParamEnv<'tcx> {
+ self.delegate.param_env()
+ }
+
+ fn tag(&self) -> &'static str {
+ "nll::subtype"
+ }
+
+ fn a_is_expected(&self) -> bool {
+ true
+ }
+
+ #[instrument(skip(self, info), level = "trace")]
+ 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);
+
+ let r = self.relate(a, b)?;
+
+ self.ambient_variance = old_ambient_variance;
+
+ debug!(?r);
+
+ 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 {
+ // Subtle: if a or b has a bound variable that we are lazily
+ // substituting, then even if a == b, it could be that the values we
+ // will substitute for those bound variables are *not* the same, and
+ // hence returning `Ok(a)` is incorrect.
+ if !a.has_escaping_bound_vars() && !b.has_escaping_bound_vars() {
+ 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::Opaque(a_def_id, _), &ty::Opaque(b_def_id, _)) if a_def_id == b_def_id => {
+ self.infcx.super_combine_tys(self, a, b)
+ }
+ (&ty::Opaque(did, ..), _) | (_, &ty::Opaque(did, ..)) if did.is_local() => {
+ let (a, b) = if self.a_is_expected() { (a, b) } else { (b, a) };
+ let mut generalize = |ty, ty_is_expected| {
+ let var = 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::Opaque(..), _) => (a, generalize(b, false)?),
+ (_, &ty::Opaque(..)) => (generalize(a, true)?, b),
+ _ => unreachable!(),
+ };
+ self.delegate.register_opaque_type(a, b, true)?;
+ trace!(a = ?a.kind(), b = ?b.kind(), "opaque type instantiated");
+ Ok(a)
+ }
+
+ (&ty::Projection(projection_ty), _)
+ if D::normalization() == NormalizationStrategy::Lazy =>
+ {
+ Ok(self.relate_projection_ty(projection_ty, b))
+ }
+
+ (_, &ty::Projection(projection_ty))
+ if D::normalization() == NormalizationStrategy::Lazy =>
+ {
+ Ok(self.relate_projection_ty(projection_ty, a))
+ }
+
+ _ => {
+ 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);
+
+ let v_a = self.replace_bound_region(a, ty::INNERMOST, &self.a_scopes);
+ let v_b = self.replace_bound_region(b, ty::INNERMOST, &self.b_scopes);
+
+ debug!(?v_a);
+ debug!(?v_b);
+
+ if self.ambient_covariance() {
+ // Covariance: a <= b. Hence, `b: a`.
+ self.push_outlives(v_b, v_a, self.ambient_variance_info);
+ }
+
+ if self.ambient_contravariance() {
+ // Contravariant: b <= a. Hence, `a: b`.
+ self.push_outlives(v_a, v_b, 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.delay_span_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).
+
+ let b_scope = self.create_scope(b, UniversallyQuantified(true));
+ let a_scope = self.create_scope(a, UniversallyQuantified(false));
+
+ debug!(?a_scope, "(existential)");
+ debug!(?b_scope, "(universal)");
+
+ self.b_scopes.push(b_scope);
+ self.a_scopes.push(a_scope);
+
+ // 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);
+
+ self.relate(a.skip_binder(), b.skip_binder())?;
+
+ self.ambient_variance = variance;
+
+ self.b_scopes.pop().unwrap();
+ self.a_scopes.pop().unwrap();
+ }
+
+ 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.
+
+ let a_scope = self.create_scope(a, UniversallyQuantified(true));
+ let b_scope = self.create_scope(b, UniversallyQuantified(false));
+
+ debug!(?a_scope, "(universal)");
+ debug!(?b_scope, "(existential)");
+
+ self.a_scopes.push(a_scope);
+ self.b_scopes.push(b_scope);
+
+ // 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);
+
+ self.relate(a.skip_binder(), b.skip_binder())?;
+
+ self.ambient_variance = variance;
+
+ self.b_scopes.pop().unwrap();
+ self.a_scopes.pop().unwrap();
+ }
+
+ Ok(a)
+ }
+}
+
+impl<'tcx, D> ConstEquateRelation<'tcx> for TypeRelating<'_, 'tcx, D>
+where
+ D: TypeRelatingDelegate<'tcx>,
+{
+ fn const_equate_obligation(&mut self, a: ty::Const<'tcx>, b: ty::Const<'tcx>) {
+ self.delegate.const_equate(a, b);
+ }
+}
+
+/// When we encounter a binder like `for<..> fn(..)`, we actually have
+/// to walk the `fn` value to find all the values bound by the `for`
+/// (these are not explicitly present in the ty representation right
+/// now). This visitor handles that: it descends the type, tracking
+/// binder depth, and finds late-bound regions targeting the
+/// `for<..`>. For each of those, it creates an entry in
+/// `bound_region_scope`.
+struct ScopeInstantiator<'me, 'tcx> {
+ next_region: &'me mut dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
+ // The debruijn index of the scope we are instantiating.
+ target_index: ty::DebruijnIndex,
+ bound_region_scope: &'me mut BoundRegionScope<'tcx>,
+}
+
+impl<'me, 'tcx> TypeVisitor<'tcx> for ScopeInstantiator<'me, 'tcx> {
+ fn visit_binder<T: TypeVisitable<'tcx>>(
+ &mut self,
+ t: &ty::Binder<'tcx, T>,
+ ) -> ControlFlow<Self::BreakTy> {
+ self.target_index.shift_in(1);
+ t.super_visit_with(self);
+ self.target_index.shift_out(1);
+
+ ControlFlow::CONTINUE
+ }
+
+ fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+ let ScopeInstantiator { bound_region_scope, next_region, .. } = self;
+
+ match *r {
+ ty::ReLateBound(debruijn, br) if debruijn == self.target_index => {
+ bound_region_scope.map.entry(br).or_insert_with(|| next_region(br));
+ }
+
+ _ => {}
+ }
+
+ ControlFlow::CONTINUE
+ }
+}
+
+/// The "type 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 type `B` -- this replaces
+/// all the lifetimes in the type `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.
+///
+/// As a side-effect of this generalization procedure, we also replace
+/// all the bound regions that we have traversed with concrete values,
+/// so that the resulting generalized type is independent from the
+/// scopes.
+///
+/// [blog post]: https://is.gd/0hKvIr
+struct TypeGeneralizer<'me, 'tcx, D>
+where
+ D: TypeRelatingDelegate<'tcx>,
+{
+ infcx: &'me InferCtxt<'me, 'tcx>,
+
+ 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,
+
+ first_free_index: ty::DebruijnIndex,
+
+ /// 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.
+ for_vid_sub_root: ty::TyVid,
+
+ /// 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.
+ universe: ty::UniverseIndex,
+}
+
+impl<'tcx, D> TypeRelation<'tcx> for TypeGeneralizer<'_, 'tcx, D>
+where
+ D: TypeRelatingDelegate<'tcx>,
+{
+ fn tcx(&self) -> TyCtxt<'tcx> {
+ self.infcx.tcx
+ }
+
+ fn param_env(&self) -> ty::ParamEnv<'tcx> {
+ self.delegate.param_env()
+ }
+
+ fn tag(&self) -> &'static str {
+ "nll::generalizer"
+ }
+
+ fn a_is_expected(&self) -> bool {
+ true
+ }
+
+ fn relate_with_variance<T: Relate<'tcx>>(
+ &mut self,
+ variance: ty::Variance,
+ _info: ty::VarianceDiagInfo<'tcx>,
+ a: T,
+ b: T,
+ ) -> RelateResult<'tcx, T> {
+ debug!(
+ "TypeGeneralizer::relate_with_variance(variance={:?}, a={:?}, b={:?})",
+ variance, a, b
+ );
+
+ let old_ambient_variance = self.ambient_variance;
+ self.ambient_variance = self.ambient_variance.xform(variance);
+
+ debug!(
+ "TypeGeneralizer::relate_with_variance: ambient_variance = {:?}",
+ self.ambient_variance
+ );
+
+ let r = self.relate(a, b)?;
+
+ self.ambient_variance = old_ambient_variance;
+
+ debug!("TypeGeneralizer::relate_with_variance: r={:?}", r);
+
+ Ok(r)
+ }
+
+ fn tys(&mut self, a: Ty<'tcx>, _: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+ use crate::infer::type_variable::TypeVariableValue;
+
+ debug!("TypeGeneralizer::tys(a={:?})", a);
+
+ match *a.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: {:?}", a);
+ }
+
+ ty::Infer(ty::TyVar(vid)) => {
+ let mut inner = self.infcx.inner.borrow_mut();
+ let variables = &mut inner.type_variables();
+ let vid = variables.root_var(vid);
+ let sub_vid = variables.sub_root_var(vid);
+ if sub_vid == self.for_vid_sub_root {
+ // If sub-roots are equal, then `for_vid` and
+ // `vid` are related via subtyping.
+ debug!("TypeGeneralizer::tys: occurs check failed");
+ Err(TypeError::Mismatch)
+ } else {
+ match variables.probe(vid) {
+ TypeVariableValue::Known { value: u } => {
+ drop(variables);
+ self.relate(u, u)
+ }
+ TypeVariableValue::Unknown { universe: _universe } => {
+ if self.ambient_variance == ty::Bivariant {
+ // FIXME: we may need a WF predicate (related to #54105).
+ }
+
+ let origin = *variables.var_origin(vid);
+
+ // Replacing with a new variable in the universe `self.universe`,
+ // it will be unified later with the original type variable in
+ // the universe `_universe`.
+ let new_var_id = variables.new_var(self.universe, origin);
+
+ let u = self.tcx().mk_ty_var(new_var_id);
+ debug!("generalize: 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(a)
+ }
+
+ ty::Placeholder(placeholder) => {
+ if self.universe.cannot_name(placeholder.universe) {
+ debug!(
+ "TypeGeneralizer::tys: root universe {:?} cannot name\
+ placeholder in universe {:?}",
+ self.universe, placeholder.universe
+ );
+ Err(TypeError::Mismatch)
+ } else {
+ Ok(a)
+ }
+ }
+
+ _ => relate::super_relate_tys(self, a, a),
+ }
+ }
+
+ fn regions(
+ &mut self,
+ a: ty::Region<'tcx>,
+ _: ty::Region<'tcx>,
+ ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+ debug!("TypeGeneralizer::regions(a={:?})", a);
+
+ if let ty::ReLateBound(debruijn, _) = *a && debruijn < self.first_free_index {
+ return Ok(a);
+ }
+
+ // For now, we just always create a fresh region variable to
+ // replace all the regions in the source type. In the main
+ // type checker, we special case the case where the ambient
+ // variance is `Invariant` and try to avoid creating a fresh
+ // region variable, but since this comes up so much less in
+ // NLL (only when users use `_` etc) it is much less
+ // important.
+ //
+ // As an aside, since these new variables are created in
+ // `self.universe` universe, this also serves to enforce the
+ // universe scoping rules.
+ //
+ // FIXME(#54105) -- if the ambient variance is bivariant,
+ // though, we may however need to check well-formedness or
+ // risk a problem like #41677 again.
+
+ let replacement_region_vid = self.delegate.generalize_existential(self.universe);
+
+ Ok(replacement_region_vid)
+ }
+
+ fn consts(
+ &mut self,
+ a: ty::Const<'tcx>,
+ _: ty::Const<'tcx>,
+ ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+ match a.kind() {
+ ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => {
+ bug!("unexpected inference variable encountered in NLL generalization: {:?}", a);
+ }
+ ty::ConstKind::Infer(InferConst::Var(vid)) => {
+ 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.known() {
+ Some(u) => self.relate(u, u),
+ None => {
+ let new_var_id = variable_table.new_key(ConstVarValue {
+ origin: var_value.origin,
+ val: ConstVariableValue::Unknown { universe: self.universe },
+ });
+ Ok(self.tcx().mk_const_var(new_var_id, a.ty()))
+ }
+ }
+ }
+ ty::ConstKind::Unevaluated(..) if self.tcx().lazy_normalization() => Ok(a),
+ _ => relate::super_relate_consts(self, a, a),
+ }
+ }
+
+ fn binders<T>(
+ &mut self,
+ a: ty::Binder<'tcx, T>,
+ _: ty::Binder<'tcx, T>,
+ ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+ where
+ T: Relate<'tcx>,
+ {
+ debug!("TypeGeneralizer::binders(a={:?})", a);
+
+ self.first_free_index.shift_in(1);
+ let result = self.relate(a.skip_binder(), a.skip_binder())?;
+ self.first_free_index.shift_out(1);
+ Ok(a.rebind(result))
+ }
+}