rustc_borrowck/type_check/
relate_tys.rs

1use rustc_data_structures::fx::FxHashMap;
2use rustc_errors::ErrorGuaranteed;
3use rustc_infer::infer::relate::{
4    PredicateEmittingRelation, Relate, RelateResult, StructurallyRelateAliases, TypeRelation,
5};
6use rustc_infer::infer::{InferCtxt, NllRegionVariableOrigin};
7use rustc_infer::traits::Obligation;
8use rustc_infer::traits::solve::Goal;
9use rustc_middle::mir::ConstraintCategory;
10use rustc_middle::span_bug;
11use rustc_middle::traits::ObligationCause;
12use rustc_middle::traits::query::NoSolution;
13use rustc_middle::ty::fold::FnMutDelegate;
14use rustc_middle::ty::relate::combine::{super_combine_consts, super_combine_tys};
15use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitableExt};
16use rustc_span::{Span, Symbol, sym};
17use tracing::{debug, instrument};
18
19use crate::constraints::OutlivesConstraint;
20use crate::diagnostics::UniverseInfo;
21use crate::renumber::RegionCtxt;
22use crate::type_check::{InstantiateOpaqueType, Locations, TypeChecker};
23
24impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
25    /// Adds sufficient constraints to ensure that `a R b` where `R` depends on `v`:
26    ///
27    /// - "Covariant" `a <: b`
28    /// - "Invariant" `a == b`
29    /// - "Contravariant" `a :> b`
30    ///
31    /// N.B., the type `a` is permitted to have unresolved inference
32    /// variables, but not the type `b`.
33    #[instrument(skip(self), level = "debug")]
34    pub(super) fn relate_types(
35        &mut self,
36        a: Ty<'tcx>,
37        v: ty::Variance,
38        b: Ty<'tcx>,
39        locations: Locations,
40        category: ConstraintCategory<'tcx>,
41    ) -> Result<(), NoSolution> {
42        NllTypeRelating::new(self, locations, category, UniverseInfo::relate(a, b), v)
43            .relate(a, b)?;
44        Ok(())
45    }
46
47    /// Add sufficient constraints to ensure `a == b`. See also [Self::relate_types].
48    pub(super) fn eq_args(
49        &mut self,
50        a: ty::GenericArgsRef<'tcx>,
51        b: ty::GenericArgsRef<'tcx>,
52        locations: Locations,
53        category: ConstraintCategory<'tcx>,
54    ) -> Result<(), NoSolution> {
55        NllTypeRelating::new(self, locations, category, UniverseInfo::other(), ty::Invariant)
56            .relate(a, b)?;
57        Ok(())
58    }
59}
60
61struct NllTypeRelating<'a, 'b, 'tcx> {
62    type_checker: &'a mut TypeChecker<'b, 'tcx>,
63
64    /// Where (and why) is this relation taking place?
65    locations: Locations,
66
67    /// What category do we assign the resulting `'a: 'b` relationships?
68    category: ConstraintCategory<'tcx>,
69
70    /// Information so that error reporting knows what types we are relating
71    /// when reporting a bound region error.
72    universe_info: UniverseInfo<'tcx>,
73
74    /// How are we relating `a` and `b`?
75    ///
76    /// - Covariant means `a <: b`.
77    /// - Contravariant means `b <: a`.
78    /// - Invariant means `a == b`.
79    /// - Bivariant means that it doesn't matter.
80    ambient_variance: ty::Variance,
81
82    ambient_variance_info: ty::VarianceDiagInfo<TyCtxt<'tcx>>,
83}
84
85impl<'a, 'b, 'tcx> NllTypeRelating<'a, 'b, 'tcx> {
86    fn new(
87        type_checker: &'a mut TypeChecker<'b, 'tcx>,
88        locations: Locations,
89        category: ConstraintCategory<'tcx>,
90        universe_info: UniverseInfo<'tcx>,
91        ambient_variance: ty::Variance,
92    ) -> Self {
93        Self {
94            type_checker,
95            locations,
96            category,
97            universe_info,
98            ambient_variance,
99            ambient_variance_info: ty::VarianceDiagInfo::default(),
100        }
101    }
102
103    fn ambient_covariance(&self) -> bool {
104        match self.ambient_variance {
105            ty::Covariant | ty::Invariant => true,
106            ty::Contravariant | ty::Bivariant => false,
107        }
108    }
109
110    fn ambient_contravariance(&self) -> bool {
111        match self.ambient_variance {
112            ty::Contravariant | ty::Invariant => true,
113            ty::Covariant | ty::Bivariant => false,
114        }
115    }
116
117    fn relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, ()> {
118        let infcx = self.type_checker.infcx;
119        debug_assert!(!infcx.next_trait_solver());
120        // `handle_opaque_type` cannot handle subtyping, so to support subtyping
121        // we instead eagerly generalize here. This is a bit of a mess but will go
122        // away once we're using the new solver.
123        //
124        // Given `opaque rel B`, we create a new infer var `ty_vid` constrain it
125        // by using `ty_vid rel B` and then finally and end by equating `ty_vid` to
126        // the opaque.
127        let mut enable_subtyping = |ty, opaque_is_expected| {
128            let ty_vid = infcx.next_ty_var_id_in_universe(self.span(), ty::UniverseIndex::ROOT);
129
130            let variance = if opaque_is_expected {
131                self.ambient_variance
132            } else {
133                self.ambient_variance.xform(ty::Contravariant)
134            };
135
136            self.type_checker.infcx.instantiate_ty_var(
137                self,
138                opaque_is_expected,
139                ty_vid,
140                variance,
141                ty,
142            )?;
143            Ok(infcx.resolve_vars_if_possible(Ty::new_infer(infcx.tcx, ty::TyVar(ty_vid))))
144        };
145
146        let (a, b) = match (a.kind(), b.kind()) {
147            (&ty::Alias(ty::Opaque, ..), _) => (a, enable_subtyping(b, true)?),
148            (_, &ty::Alias(ty::Opaque, ..)) => (enable_subtyping(a, false)?, b),
149            _ => unreachable!(
150                "expected at least one opaque type in `relate_opaques`, got {a} and {b}."
151            ),
152        };
153        self.register_goals(infcx.handle_opaque_type(a, b, self.span(), self.param_env())?);
154        Ok(())
155    }
156
157    fn enter_forall<T, U>(
158        &mut self,
159        binder: ty::Binder<'tcx, T>,
160        f: impl FnOnce(&mut Self, T) -> U,
161    ) -> U
162    where
163        T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
164    {
165        let value = if let Some(inner) = binder.no_bound_vars() {
166            inner
167        } else {
168            let infcx = self.type_checker.infcx;
169            let mut lazy_universe = None;
170            let delegate = FnMutDelegate {
171                regions: &mut |br: ty::BoundRegion| {
172                    // The first time this closure is called, create a
173                    // new universe for the placeholders we will make
174                    // from here out.
175                    let universe = lazy_universe.unwrap_or_else(|| {
176                        let universe = self.create_next_universe();
177                        lazy_universe = Some(universe);
178                        universe
179                    });
180
181                    let placeholder = ty::PlaceholderRegion { universe, bound: br };
182                    debug!(?placeholder);
183                    let placeholder_reg = self.next_placeholder_region(placeholder);
184                    debug!(?placeholder_reg);
185
186                    placeholder_reg
187                },
188                types: &mut |_bound_ty: ty::BoundTy| {
189                    unreachable!("we only replace regions in nll_relate, not types")
190                },
191                consts: &mut |_bound_var: ty::BoundVar| {
192                    unreachable!("we only replace regions in nll_relate, not consts")
193                },
194            };
195
196            infcx.tcx.replace_bound_vars_uncached(binder, delegate)
197        };
198
199        debug!(?value);
200        f(self, value)
201    }
202
203    #[instrument(skip(self), level = "debug")]
204    fn instantiate_binder_with_existentials<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T
205    where
206        T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
207    {
208        if let Some(inner) = binder.no_bound_vars() {
209            return inner;
210        }
211
212        let infcx = self.type_checker.infcx;
213        let mut reg_map = FxHashMap::default();
214        let delegate = FnMutDelegate {
215            regions: &mut |br: ty::BoundRegion| {
216                if let Some(ex_reg_var) = reg_map.get(&br) {
217                    *ex_reg_var
218                } else {
219                    let ex_reg_var = self.next_existential_region_var(true, br.kind.get_name());
220                    debug!(?ex_reg_var);
221                    reg_map.insert(br, ex_reg_var);
222
223                    ex_reg_var
224                }
225            },
226            types: &mut |_bound_ty: ty::BoundTy| {
227                unreachable!("we only replace regions in nll_relate, not types")
228            },
229            consts: &mut |_bound_var: ty::BoundVar| {
230                unreachable!("we only replace regions in nll_relate, not consts")
231            },
232        };
233
234        let replaced = infcx.tcx.replace_bound_vars_uncached(binder, delegate);
235        debug!(?replaced);
236
237        replaced
238    }
239
240    fn create_next_universe(&mut self) -> ty::UniverseIndex {
241        let universe = self.type_checker.infcx.create_next_universe();
242        self.type_checker.constraints.universe_causes.insert(universe, self.universe_info.clone());
243        universe
244    }
245
246    #[instrument(skip(self), level = "debug")]
247    fn next_existential_region_var(
248        &mut self,
249        from_forall: bool,
250        name: Option<Symbol>,
251    ) -> ty::Region<'tcx> {
252        let origin = NllRegionVariableOrigin::Existential { from_forall };
253
254        let reg_var =
255            self.type_checker.infcx.next_nll_region_var(origin, || RegionCtxt::Existential(name));
256
257        reg_var
258    }
259
260    #[instrument(skip(self), level = "debug")]
261    fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx> {
262        let reg =
263            self.type_checker.constraints.placeholder_region(self.type_checker.infcx, placeholder);
264
265        let reg_info = match placeholder.bound.kind {
266            ty::BoundRegionKind::Anon => sym::anon,
267            ty::BoundRegionKind::Named(_, name) => name,
268            ty::BoundRegionKind::ClosureEnv => sym::env,
269        };
270
271        if cfg!(debug_assertions) {
272            let mut var_to_origin = self.type_checker.infcx.reg_var_to_origin.borrow_mut();
273            let new = RegionCtxt::Placeholder(reg_info);
274            let prev = var_to_origin.insert(reg.as_var(), new);
275            if let Some(prev) = prev {
276                assert_eq!(new, prev);
277            }
278        }
279
280        reg
281    }
282
283    fn push_outlives(
284        &mut self,
285        sup: ty::Region<'tcx>,
286        sub: ty::Region<'tcx>,
287        info: ty::VarianceDiagInfo<TyCtxt<'tcx>>,
288    ) {
289        let sub = self.type_checker.universal_regions.to_region_vid(sub);
290        let sup = self.type_checker.universal_regions.to_region_vid(sup);
291        self.type_checker.constraints.outlives_constraints.push(OutlivesConstraint {
292            sup,
293            sub,
294            locations: self.locations,
295            span: self.locations.span(self.type_checker.body),
296            category: self.category,
297            variance_info: info,
298            from_closure: false,
299        });
300    }
301}
302
303impl<'b, 'tcx> TypeRelation<TyCtxt<'tcx>> for NllTypeRelating<'_, 'b, 'tcx> {
304    fn cx(&self) -> TyCtxt<'tcx> {
305        self.type_checker.infcx.tcx
306    }
307
308    #[instrument(skip(self, info), level = "trace", ret)]
309    fn relate_with_variance<T: Relate<TyCtxt<'tcx>>>(
310        &mut self,
311        variance: ty::Variance,
312        info: ty::VarianceDiagInfo<TyCtxt<'tcx>>,
313        a: T,
314        b: T,
315    ) -> RelateResult<'tcx, T> {
316        let old_ambient_variance = self.ambient_variance;
317        self.ambient_variance = self.ambient_variance.xform(variance);
318        self.ambient_variance_info = self.ambient_variance_info.xform(info);
319
320        debug!(?self.ambient_variance);
321        // In a bivariant context this always succeeds.
322        let r = if self.ambient_variance == ty::Bivariant { Ok(a) } else { self.relate(a, b) };
323
324        self.ambient_variance = old_ambient_variance;
325
326        r
327    }
328
329    #[instrument(skip(self), level = "debug")]
330    fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
331        let infcx = self.type_checker.infcx;
332
333        let a = self.type_checker.infcx.shallow_resolve(a);
334        assert!(!b.has_non_region_infer(), "unexpected inference var {:?}", b);
335
336        if a == b {
337            return Ok(a);
338        }
339
340        match (a.kind(), b.kind()) {
341            (_, &ty::Infer(ty::TyVar(_))) => {
342                span_bug!(
343                    self.span(),
344                    "should not be relating type variables on the right in MIR typeck"
345                );
346            }
347
348            (&ty::Infer(ty::TyVar(a_vid)), _) => {
349                infcx.instantiate_ty_var(self, true, a_vid, self.ambient_variance, b)?
350            }
351
352            (
353                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }),
354                &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }),
355            ) if a_def_id == b_def_id || infcx.next_trait_solver() => {
356                super_combine_tys(&infcx.infcx, self, a, b).map(|_| ()).or_else(|err| {
357                    // This behavior is only there for the old solver, the new solver
358                    // shouldn't ever fail. Instead, it unconditionally emits an
359                    // alias-relate goal.
360                    assert!(!self.type_checker.infcx.next_trait_solver());
361                    self.cx().dcx().span_delayed_bug(
362                        self.span(),
363                        "failure to relate an opaque to itself should result in an error later on",
364                    );
365                    if a_def_id.is_local() { self.relate_opaques(a, b) } else { Err(err) }
366                })?;
367            }
368            (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _)
369            | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }))
370                if def_id.is_local() && !self.type_checker.infcx.next_trait_solver() =>
371            {
372                self.relate_opaques(a, b)?;
373            }
374
375            _ => {
376                debug!(?a, ?b, ?self.ambient_variance);
377
378                // Will also handle unification of `IntVar` and `FloatVar`.
379                super_combine_tys(&self.type_checker.infcx.infcx, self, a, b)?;
380            }
381        }
382
383        Ok(a)
384    }
385
386    #[instrument(skip(self), level = "trace")]
387    fn regions(
388        &mut self,
389        a: ty::Region<'tcx>,
390        b: ty::Region<'tcx>,
391    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
392        debug!(?self.ambient_variance);
393
394        if self.ambient_covariance() {
395            // Covariant: &'a u8 <: &'b u8. Hence, `'a: 'b`.
396            self.push_outlives(a, b, self.ambient_variance_info);
397        }
398
399        if self.ambient_contravariance() {
400            // Contravariant: &'b u8 <: &'a u8. Hence, `'b: 'a`.
401            self.push_outlives(b, a, self.ambient_variance_info);
402        }
403
404        Ok(a)
405    }
406
407    fn consts(
408        &mut self,
409        a: ty::Const<'tcx>,
410        b: ty::Const<'tcx>,
411    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
412        let a = self.type_checker.infcx.shallow_resolve_const(a);
413        assert!(!a.has_non_region_infer(), "unexpected inference var {:?}", a);
414        assert!(!b.has_non_region_infer(), "unexpected inference var {:?}", b);
415
416        super_combine_consts(&self.type_checker.infcx.infcx, self, a, b)
417    }
418
419    #[instrument(skip(self), level = "trace")]
420    fn binders<T>(
421        &mut self,
422        a: ty::Binder<'tcx, T>,
423        b: ty::Binder<'tcx, T>,
424    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
425    where
426        T: Relate<TyCtxt<'tcx>>,
427    {
428        // We want that
429        //
430        // ```
431        // for<'a> fn(&'a u32) -> &'a u32 <:
432        //   fn(&'b u32) -> &'b u32
433        // ```
434        //
435        // but not
436        //
437        // ```
438        // fn(&'a u32) -> &'a u32 <:
439        //   for<'b> fn(&'b u32) -> &'b u32
440        // ```
441        //
442        // We therefore proceed as follows:
443        //
444        // - Instantiate binders on `b` universally, yielding a universe U1.
445        // - Instantiate binders on `a` existentially in U1.
446
447        debug!(?self.ambient_variance);
448
449        if let (Some(a), Some(b)) = (a.no_bound_vars(), b.no_bound_vars()) {
450            // Fast path for the common case.
451            self.relate(a, b)?;
452            return Ok(ty::Binder::dummy(a));
453        }
454
455        match self.ambient_variance {
456            ty::Covariant => {
457                // Covariance, so we want `for<..> A <: for<..> B` --
458                // therefore we compare any instantiation of A (i.e., A
459                // instantiated with existentials) against every
460                // instantiation of B (i.e., B instantiated with
461                // universals).
462
463                // Note: the order here is important. Create the placeholders first, otherwise
464                // we assign the wrong universe to the existential!
465                self.enter_forall(b, |this, b| {
466                    let a = this.instantiate_binder_with_existentials(a);
467                    this.relate(a, b)
468                })?;
469            }
470
471            ty::Contravariant => {
472                // Contravariance, so we want `for<..> A :> for<..> B` --
473                // therefore we compare every instantiation of A (i.e., A
474                // instantiated with universals) against any
475                // instantiation of B (i.e., B instantiated with
476                // existentials). Opposite of above.
477
478                // Note: the order here is important. Create the placeholders first, otherwise
479                // we assign the wrong universe to the existential!
480                self.enter_forall(a, |this, a| {
481                    let b = this.instantiate_binder_with_existentials(b);
482                    this.relate(a, b)
483                })?;
484            }
485
486            ty::Invariant => {
487                // Invariant, so we want `for<..> A == for<..> B` --
488                // therefore we want `exists<..> A == for<..> B` and
489                // `exists<..> B == for<..> A`.
490                //
491                // See the comment in `fn Equate::binders` for more details.
492
493                // Note: the order here is important. Create the placeholders first, otherwise
494                // we assign the wrong universe to the existential!
495                self.enter_forall(b, |this, b| {
496                    let a = this.instantiate_binder_with_existentials(a);
497                    this.relate(a, b)
498                })?;
499                // Note: the order here is important. Create the placeholders first, otherwise
500                // we assign the wrong universe to the existential!
501                self.enter_forall(a, |this, a| {
502                    let b = this.instantiate_binder_with_existentials(b);
503                    this.relate(a, b)
504                })?;
505            }
506
507            ty::Bivariant => {}
508        }
509
510        Ok(a)
511    }
512}
513
514impl<'b, 'tcx> PredicateEmittingRelation<InferCtxt<'tcx>> for NllTypeRelating<'_, 'b, 'tcx> {
515    fn span(&self) -> Span {
516        self.locations.span(self.type_checker.body)
517    }
518
519    fn structurally_relate_aliases(&self) -> StructurallyRelateAliases {
520        StructurallyRelateAliases::No
521    }
522
523    fn param_env(&self) -> ty::ParamEnv<'tcx> {
524        self.type_checker.infcx.param_env
525    }
526
527    fn register_predicates(
528        &mut self,
529        obligations: impl IntoIterator<Item: ty::Upcast<TyCtxt<'tcx>, ty::Predicate<'tcx>>>,
530    ) {
531        let tcx = self.cx();
532        let param_env = self.param_env();
533        self.register_goals(
534            obligations.into_iter().map(|to_pred| Goal::new(tcx, param_env, to_pred)),
535        );
536    }
537
538    fn register_goals(
539        &mut self,
540        obligations: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>,
541    ) {
542        let _: Result<_, ErrorGuaranteed> = self.type_checker.fully_perform_op(
543            self.locations,
544            self.category,
545            InstantiateOpaqueType {
546                obligations: obligations
547                    .into_iter()
548                    .map(|goal| {
549                        Obligation::new(
550                            self.cx(),
551                            ObligationCause::dummy_with_span(self.span()),
552                            goal.param_env,
553                            goal.predicate,
554                        )
555                    })
556                    .collect(),
557                // These fields are filled in during execution of the operation
558                base_universe: None,
559                region_constraints: None,
560            },
561        );
562    }
563
564    fn register_alias_relate_predicate(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) {
565        self.register_predicates([ty::Binder::dummy(match self.ambient_variance {
566            ty::Covariant => ty::PredicateKind::AliasRelate(
567                a.into(),
568                b.into(),
569                ty::AliasRelationDirection::Subtype,
570            ),
571            // a :> b is b <: a
572            ty::Contravariant => ty::PredicateKind::AliasRelate(
573                b.into(),
574                a.into(),
575                ty::AliasRelationDirection::Subtype,
576            ),
577            ty::Invariant => ty::PredicateKind::AliasRelate(
578                a.into(),
579                b.into(),
580                ty::AliasRelationDirection::Equate,
581            ),
582            ty::Bivariant => {
583                unreachable!("cannot defer an alias-relate goal with Bivariant variance (yet?)")
584            }
585        })]);
586    }
587}