• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //! This code is kind of an alternate way of doing subtyping,
2 //! supertyping, and type equating, distinct from the `combine.rs`
3 //! code but very similar in its effect and design. Eventually the two
4 //! ought to be merged. This code is intended for use in NLL and chalk.
5 //!
6 //! Here are the key differences:
7 //!
8 //! - This code may choose to bypass some checks (e.g., the occurs check)
9 //!   in the case where we know that there are no unbound type inference
10 //!   variables. This is the case for NLL, because at NLL time types are fully
11 //!   inferred up-to regions.
12 //! - This code uses "universes" to handle higher-ranked regions and
13 //!   not the leak-check. This is "more correct" than what rustc does
14 //!   and we are generally migrating in this direction, but NLL had to
15 //!   get there first.
16 //!
17 //! Also, this code assumes that there are no bound types at all, not even
18 //! free ones. This is ok because:
19 //! - we are not relating anything quantified over some type variable
20 //! - we will have instantiated all the bound type vars already (the one
21 //!   thing we relate in chalk are basically domain goals and their
22 //!   constituents)
23 
24 use rustc_data_structures::fx::FxHashMap;
25 use rustc_middle::traits::ObligationCause;
26 use rustc_middle::ty::fold::FnMutDelegate;
27 use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
28 use rustc_middle::ty::visit::TypeVisitableExt;
29 use rustc_middle::ty::{self, InferConst, Ty, TyCtxt};
30 use rustc_span::{Span, Symbol};
31 use std::fmt::Debug;
32 
33 use crate::infer::combine::ObligationEmittingRelation;
34 use crate::infer::generalize::{self, Generalization};
35 use crate::infer::InferCtxt;
36 use crate::infer::{TypeVariableOrigin, TypeVariableOriginKind};
37 use crate::traits::{Obligation, PredicateObligations};
38 
39 pub struct TypeRelating<'me, 'tcx, D>
40 where
41     D: TypeRelatingDelegate<'tcx>,
42 {
43     infcx: &'me InferCtxt<'tcx>,
44 
45     /// Callback to use when we deduce an outlives relationship.
46     delegate: D,
47 
48     /// How are we relating `a` and `b`?
49     ///
50     /// - Covariant means `a <: b`.
51     /// - Contravariant means `b <: a`.
52     /// - Invariant means `a == b`.
53     /// - Bivariant means that it doesn't matter.
54     ambient_variance: ty::Variance,
55 
56     ambient_variance_info: ty::VarianceDiagInfo<'tcx>,
57 }
58 
59 pub trait TypeRelatingDelegate<'tcx> {
param_env(&self) -> ty::ParamEnv<'tcx>60     fn param_env(&self) -> ty::ParamEnv<'tcx>;
span(&self) -> Span61     fn span(&self) -> Span;
62 
63     /// Push a constraint `sup: sub` -- this constraint must be
64     /// satisfied for the two types to be related. `sub` and `sup` may
65     /// be regions from the type or new variables created through the
66     /// delegate.
push_outlives( &mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>, info: ty::VarianceDiagInfo<'tcx>, )67     fn push_outlives(
68         &mut self,
69         sup: ty::Region<'tcx>,
70         sub: ty::Region<'tcx>,
71         info: ty::VarianceDiagInfo<'tcx>,
72     );
73 
register_obligations(&mut self, obligations: PredicateObligations<'tcx>)74     fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>);
75 
76     /// Creates a new universe index. Used when instantiating placeholders.
create_next_universe(&mut self) -> ty::UniverseIndex77     fn create_next_universe(&mut self) -> ty::UniverseIndex;
78 
79     /// Creates a new region variable representing a higher-ranked
80     /// region that is instantiated existentially. This creates an
81     /// inference variable, typically.
82     ///
83     /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
84     /// we will invoke this method to instantiate `'a` with an
85     /// inference variable (though `'b` would be instantiated first,
86     /// as a placeholder).
next_existential_region_var( &mut self, was_placeholder: bool, name: Option<Symbol>, ) -> ty::Region<'tcx>87     fn next_existential_region_var(
88         &mut self,
89         was_placeholder: bool,
90         name: Option<Symbol>,
91     ) -> ty::Region<'tcx>;
92 
93     /// Creates a new region variable representing a
94     /// higher-ranked region that is instantiated universally.
95     /// This creates a new region placeholder, typically.
96     ///
97     /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then
98     /// we will invoke this method to instantiate `'b` with a
99     /// placeholder region.
next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>100     fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>;
101 
102     /// Creates a new existential region in the given universe. This
103     /// is used when handling subtyping and type variables -- if we
104     /// have that `?X <: Foo<'a>`, for example, we would instantiate
105     /// `?X` with a type like `Foo<'?0>` where `'?0` is a fresh
106     /// existential variable created by this function. We would then
107     /// relate `Foo<'?0>` with `Foo<'a>` (and probably add an outlives
108     /// relation stating that `'?0: 'a`).
generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>109     fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>;
110 
111     /// Enables some optimizations if we do not expect inference variables
112     /// in the RHS of the relation.
forbid_inference_vars() -> bool113     fn forbid_inference_vars() -> bool;
114 }
115 
116 #[derive(Copy, Clone)]
117 struct UniversallyQuantified(bool);
118 
119 impl<'me, 'tcx, D> TypeRelating<'me, 'tcx, D>
120 where
121     D: TypeRelatingDelegate<'tcx>,
122 {
new(infcx: &'me InferCtxt<'tcx>, delegate: D, ambient_variance: ty::Variance) -> Self123     pub fn new(infcx: &'me InferCtxt<'tcx>, delegate: D, ambient_variance: ty::Variance) -> Self {
124         Self {
125             infcx,
126             delegate,
127             ambient_variance,
128             ambient_variance_info: ty::VarianceDiagInfo::default(),
129         }
130     }
131 
ambient_covariance(&self) -> bool132     fn ambient_covariance(&self) -> bool {
133         match self.ambient_variance {
134             ty::Variance::Covariant | ty::Variance::Invariant => true,
135             ty::Variance::Contravariant | ty::Variance::Bivariant => false,
136         }
137     }
138 
ambient_contravariance(&self) -> bool139     fn ambient_contravariance(&self) -> bool {
140         match self.ambient_variance {
141             ty::Variance::Contravariant | ty::Variance::Invariant => true,
142             ty::Variance::Covariant | ty::Variance::Bivariant => false,
143         }
144     }
145 
146     /// Push a new outlives requirement into our output set of
147     /// constraints.
push_outlives( &mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>, info: ty::VarianceDiagInfo<'tcx>, )148     fn push_outlives(
149         &mut self,
150         sup: ty::Region<'tcx>,
151         sub: ty::Region<'tcx>,
152         info: ty::VarianceDiagInfo<'tcx>,
153     ) {
154         debug!("push_outlives({:?}: {:?})", sup, sub);
155 
156         self.delegate.push_outlives(sup, sub, info);
157     }
158 
159     /// Relate a type inference variable with a value type. This works
160     /// by creating a "generalization" G of the value where all the
161     /// lifetimes are replaced with fresh inference values. This
162     /// generalization G becomes the value of the inference variable,
163     /// and is then related in turn to the value. So e.g. if you had
164     /// `vid = ?0` and `value = &'a u32`, we might first instantiate
165     /// `?0` to a type like `&'0 u32` where `'0` is a fresh variable,
166     /// and then relate `&'0 u32` with `&'a u32` (resulting in
167     /// relations between `'0` and `'a`).
168     ///
169     /// The variable `pair` can be either a `(vid, ty)` or `(ty, vid)`
170     /// -- in other words, it is always an (unresolved) inference
171     /// variable `vid` and a type `ty` that are being related, but the
172     /// vid may appear either as the "a" type or the "b" type,
173     /// depending on where it appears in the tuple. The trait
174     /// `VidValuePair` lets us work with the vid/type while preserving
175     /// the "sidedness" when necessary -- the sidedness is relevant in
176     /// particular for the variance and set of in-scope things.
relate_ty_var<PAIR: VidValuePair<'tcx>>( &mut self, pair: PAIR, ) -> RelateResult<'tcx, Ty<'tcx>>177     fn relate_ty_var<PAIR: VidValuePair<'tcx>>(
178         &mut self,
179         pair: PAIR,
180     ) -> RelateResult<'tcx, Ty<'tcx>> {
181         debug!("relate_ty_var({:?})", pair);
182 
183         let vid = pair.vid();
184         let value_ty = pair.value_ty();
185 
186         // FIXME(invariance) -- this logic assumes invariance, but that is wrong.
187         // This only presently applies to chalk integration, as NLL
188         // doesn't permit type variables to appear on both sides (and
189         // doesn't use lazy norm).
190         match *value_ty.kind() {
191             ty::Infer(ty::TyVar(value_vid)) => {
192                 // Two type variables: just equate them.
193                 self.infcx.inner.borrow_mut().type_variables().equate(vid, value_vid);
194                 return Ok(value_ty);
195             }
196 
197             _ => (),
198         }
199 
200         let generalized_ty = self.generalize(value_ty, vid)?;
201         debug!("relate_ty_var: generalized_ty = {:?}", generalized_ty);
202 
203         if D::forbid_inference_vars() {
204             // In NLL, we don't have type inference variables
205             // floating around, so we can do this rather imprecise
206             // variant of the occurs-check.
207             assert!(!generalized_ty.has_non_region_infer());
208         }
209 
210         self.infcx.inner.borrow_mut().type_variables().instantiate(vid, generalized_ty);
211 
212         // Relate the generalized kind to the original one.
213         let result = pair.relate_generalized_ty(self, generalized_ty);
214 
215         debug!("relate_ty_var: complete, result = {:?}", result);
216         result
217     }
218 
generalize(&mut self, ty: Ty<'tcx>, for_vid: ty::TyVid) -> RelateResult<'tcx, Ty<'tcx>>219     fn generalize(&mut self, ty: Ty<'tcx>, for_vid: ty::TyVid) -> RelateResult<'tcx, Ty<'tcx>> {
220         let Generalization { value: ty, needs_wf: _ } = generalize::generalize(
221             self.infcx,
222             &mut self.delegate,
223             ty,
224             for_vid,
225             self.ambient_variance,
226         )?;
227         Ok(ty)
228     }
229 
relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>>230     fn relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
231         let (a, b) = if self.a_is_expected() { (a, b) } else { (b, a) };
232         let mut generalize = |ty, ty_is_expected| {
233             let var = self.infcx.next_ty_var_id_in_universe(
234                 TypeVariableOrigin {
235                     kind: TypeVariableOriginKind::MiscVariable,
236                     span: self.delegate.span(),
237                 },
238                 ty::UniverseIndex::ROOT,
239             );
240             if ty_is_expected {
241                 self.relate_ty_var((ty, var))
242             } else {
243                 self.relate_ty_var((var, ty))
244             }
245         };
246         let (a, b) = match (a.kind(), b.kind()) {
247             (&ty::Alias(ty::Opaque, ..), _) => (a, generalize(b, false)?),
248             (_, &ty::Alias(ty::Opaque, ..)) => (generalize(a, true)?, b),
249             _ => unreachable!(),
250         };
251         let cause = ObligationCause::dummy_with_span(self.delegate.span());
252         let obligations = self
253             .infcx
254             .handle_opaque_type(a, b, true, &cause, self.delegate.param_env())?
255             .obligations;
256         self.delegate.register_obligations(obligations);
257         trace!(a = ?a.kind(), b = ?b.kind(), "opaque type instantiated");
258         Ok(a)
259     }
260 
261     #[instrument(skip(self), level = "debug")]
instantiate_binder_with_placeholders<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T where T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,262     fn instantiate_binder_with_placeholders<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T
263     where
264         T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
265     {
266         if let Some(inner) = binder.no_bound_vars() {
267             return inner;
268         }
269 
270         let mut next_region = {
271             let nll_delegate = &mut self.delegate;
272             let mut lazy_universe = None;
273 
274             move |br: ty::BoundRegion| {
275                 // The first time this closure is called, create a
276                 // new universe for the placeholders we will make
277                 // from here out.
278                 let universe = lazy_universe.unwrap_or_else(|| {
279                     let universe = nll_delegate.create_next_universe();
280                     lazy_universe = Some(universe);
281                     universe
282                 });
283 
284                 let placeholder = ty::PlaceholderRegion { universe, bound: br };
285                 debug!(?placeholder);
286                 let placeholder_reg = nll_delegate.next_placeholder_region(placeholder);
287                 debug!(?placeholder_reg);
288 
289                 placeholder_reg
290             }
291         };
292 
293         let delegate = FnMutDelegate {
294             regions: &mut next_region,
295             types: &mut |_bound_ty: ty::BoundTy| {
296                 unreachable!("we only replace regions in nll_relate, not types")
297             },
298             consts: &mut |_bound_var: ty::BoundVar, _ty| {
299                 unreachable!("we only replace regions in nll_relate, not consts")
300             },
301         };
302 
303         let replaced = self.infcx.tcx.replace_bound_vars_uncached(binder, delegate);
304         debug!(?replaced);
305 
306         replaced
307     }
308 
309     #[instrument(skip(self), level = "debug")]
instantiate_binder_with_existentials<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T where T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,310     fn instantiate_binder_with_existentials<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T
311     where
312         T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,
313     {
314         if let Some(inner) = binder.no_bound_vars() {
315             return inner;
316         }
317 
318         let mut next_region = {
319             let nll_delegate = &mut self.delegate;
320             let mut reg_map = FxHashMap::default();
321 
322             move |br: ty::BoundRegion| {
323                 if let Some(ex_reg_var) = reg_map.get(&br) {
324                     return *ex_reg_var;
325                 } else {
326                     let ex_reg_var =
327                         nll_delegate.next_existential_region_var(true, br.kind.get_name());
328                     debug!(?ex_reg_var);
329                     reg_map.insert(br, ex_reg_var);
330 
331                     ex_reg_var
332                 }
333             }
334         };
335 
336         let delegate = FnMutDelegate {
337             regions: &mut next_region,
338             types: &mut |_bound_ty: ty::BoundTy| {
339                 unreachable!("we only replace regions in nll_relate, not types")
340             },
341             consts: &mut |_bound_var: ty::BoundVar, _ty| {
342                 unreachable!("we only replace regions in nll_relate, not consts")
343             },
344         };
345 
346         let replaced = self.infcx.tcx.replace_bound_vars_uncached(binder, delegate);
347         debug!(?replaced);
348 
349         replaced
350     }
351 }
352 
353 /// When we instantiate an inference variable with a value in
354 /// `relate_ty_var`, we always have the pair of a `TyVid` and a `Ty`,
355 /// but the ordering may vary (depending on whether the inference
356 /// variable was found on the `a` or `b` sides). Therefore, this trait
357 /// allows us to factor out common code, while preserving the order
358 /// when needed.
359 trait VidValuePair<'tcx>: Debug {
360     /// Extract the inference variable (which could be either the
361     /// first or second part of the tuple).
vid(&self) -> ty::TyVid362     fn vid(&self) -> ty::TyVid;
363 
364     /// Extract the value it is being related to (which will be the
365     /// opposite part of the tuple from the vid).
value_ty(&self) -> Ty<'tcx>366     fn value_ty(&self) -> Ty<'tcx>;
367 
368     /// Given a generalized type G that should replace the vid, relate
369     /// G to the value, putting G on whichever side the vid would have
370     /// appeared.
relate_generalized_ty<D>( &self, relate: &mut TypeRelating<'_, 'tcx, D>, generalized_ty: Ty<'tcx>, ) -> RelateResult<'tcx, Ty<'tcx>> where D: TypeRelatingDelegate<'tcx>371     fn relate_generalized_ty<D>(
372         &self,
373         relate: &mut TypeRelating<'_, 'tcx, D>,
374         generalized_ty: Ty<'tcx>,
375     ) -> RelateResult<'tcx, Ty<'tcx>>
376     where
377         D: TypeRelatingDelegate<'tcx>;
378 }
379 
380 impl<'tcx> VidValuePair<'tcx> for (ty::TyVid, Ty<'tcx>) {
vid(&self) -> ty::TyVid381     fn vid(&self) -> ty::TyVid {
382         self.0
383     }
384 
value_ty(&self) -> Ty<'tcx>385     fn value_ty(&self) -> Ty<'tcx> {
386         self.1
387     }
388 
relate_generalized_ty<D>( &self, relate: &mut TypeRelating<'_, 'tcx, D>, generalized_ty: Ty<'tcx>, ) -> RelateResult<'tcx, Ty<'tcx>> where D: TypeRelatingDelegate<'tcx>,389     fn relate_generalized_ty<D>(
390         &self,
391         relate: &mut TypeRelating<'_, 'tcx, D>,
392         generalized_ty: Ty<'tcx>,
393     ) -> RelateResult<'tcx, Ty<'tcx>>
394     where
395         D: TypeRelatingDelegate<'tcx>,
396     {
397         relate.relate(generalized_ty, self.value_ty())
398     }
399 }
400 
401 // In this case, the "vid" is the "b" type.
402 impl<'tcx> VidValuePair<'tcx> for (Ty<'tcx>, ty::TyVid) {
vid(&self) -> ty::TyVid403     fn vid(&self) -> ty::TyVid {
404         self.1
405     }
406 
value_ty(&self) -> Ty<'tcx>407     fn value_ty(&self) -> Ty<'tcx> {
408         self.0
409     }
410 
relate_generalized_ty<D>( &self, relate: &mut TypeRelating<'_, 'tcx, D>, generalized_ty: Ty<'tcx>, ) -> RelateResult<'tcx, Ty<'tcx>> where D: TypeRelatingDelegate<'tcx>,411     fn relate_generalized_ty<D>(
412         &self,
413         relate: &mut TypeRelating<'_, 'tcx, D>,
414         generalized_ty: Ty<'tcx>,
415     ) -> RelateResult<'tcx, Ty<'tcx>>
416     where
417         D: TypeRelatingDelegate<'tcx>,
418     {
419         relate.relate(self.value_ty(), generalized_ty)
420     }
421 }
422 
423 impl<'tcx, D> TypeRelation<'tcx> for TypeRelating<'_, 'tcx, D>
424 where
425     D: TypeRelatingDelegate<'tcx>,
426 {
tcx(&self) -> TyCtxt<'tcx>427     fn tcx(&self) -> TyCtxt<'tcx> {
428         self.infcx.tcx
429     }
430 
param_env(&self) -> ty::ParamEnv<'tcx>431     fn param_env(&self) -> ty::ParamEnv<'tcx> {
432         self.delegate.param_env()
433     }
434 
tag(&self) -> &'static str435     fn tag(&self) -> &'static str {
436         "nll::subtype"
437     }
438 
a_is_expected(&self) -> bool439     fn a_is_expected(&self) -> bool {
440         true
441     }
442 
443     #[instrument(skip(self, info), level = "trace", ret)]
relate_with_variance<T: Relate<'tcx>>( &mut self, variance: ty::Variance, info: ty::VarianceDiagInfo<'tcx>, a: T, b: T, ) -> RelateResult<'tcx, T>444     fn relate_with_variance<T: Relate<'tcx>>(
445         &mut self,
446         variance: ty::Variance,
447         info: ty::VarianceDiagInfo<'tcx>,
448         a: T,
449         b: T,
450     ) -> RelateResult<'tcx, T> {
451         let old_ambient_variance = self.ambient_variance;
452         self.ambient_variance = self.ambient_variance.xform(variance);
453         self.ambient_variance_info = self.ambient_variance_info.xform(info);
454 
455         debug!(?self.ambient_variance);
456         // In a bivariant context this always succeeds.
457         let r =
458             if self.ambient_variance == ty::Variance::Bivariant { a } else { self.relate(a, b)? };
459 
460         self.ambient_variance = old_ambient_variance;
461 
462         Ok(r)
463     }
464 
465     #[instrument(skip(self), level = "debug")]
tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>>466     fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
467         let infcx = self.infcx;
468 
469         let a = self.infcx.shallow_resolve(a);
470 
471         if !D::forbid_inference_vars() {
472             b = self.infcx.shallow_resolve(b);
473         }
474 
475         if a == b {
476             return Ok(a);
477         }
478 
479         match (a.kind(), b.kind()) {
480             (_, &ty::Infer(ty::TyVar(vid))) => {
481                 if D::forbid_inference_vars() {
482                     // Forbid inference variables in the RHS.
483                     bug!("unexpected inference var {:?}", b)
484                 } else {
485                     self.relate_ty_var((a, vid))
486                 }
487             }
488 
489             (&ty::Infer(ty::TyVar(vid)), _) => self.relate_ty_var((vid, b)),
490 
491             (
492                 &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }),
493                 &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }),
494             ) if a_def_id == b_def_id || infcx.next_trait_solver() => {
495                 infcx.super_combine_tys(self, a, b).or_else(|err| {
496                     // This behavior is only there for the old solver, the new solver
497                     // shouldn't ever fail. Instead, it unconditionally emits an
498                     // alias-relate goal.
499                     assert!(!self.infcx.next_trait_solver());
500                     self.tcx().sess.delay_span_bug(
501                         self.delegate.span(),
502                         "failure to relate an opaque to itself should result in an error later on",
503                     );
504                     if a_def_id.is_local() { self.relate_opaques(a, b) } else { Err(err) }
505                 })
506             }
507             (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _)
508             | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }))
509                 if def_id.is_local() && !self.infcx.next_trait_solver() =>
510             {
511                 self.relate_opaques(a, b)
512             }
513 
514             _ => {
515                 debug!(?a, ?b, ?self.ambient_variance);
516 
517                 // Will also handle unification of `IntVar` and `FloatVar`.
518                 self.infcx.super_combine_tys(self, a, b)
519             }
520         }
521     }
522 
523     #[instrument(skip(self), level = "trace")]
regions( &mut self, a: ty::Region<'tcx>, b: ty::Region<'tcx>, ) -> RelateResult<'tcx, ty::Region<'tcx>>524     fn regions(
525         &mut self,
526         a: ty::Region<'tcx>,
527         b: ty::Region<'tcx>,
528     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
529         debug!(?self.ambient_variance);
530 
531         if self.ambient_covariance() {
532             // Covariant: &'a u8 <: &'b u8. Hence, `'a: 'b`.
533             self.push_outlives(a, b, self.ambient_variance_info);
534         }
535 
536         if self.ambient_contravariance() {
537             // Contravariant: &'b u8 <: &'a u8. Hence, `'b: 'a`.
538             self.push_outlives(b, a, self.ambient_variance_info);
539         }
540 
541         Ok(a)
542     }
543 
consts( &mut self, a: ty::Const<'tcx>, mut b: ty::Const<'tcx>, ) -> RelateResult<'tcx, ty::Const<'tcx>>544     fn consts(
545         &mut self,
546         a: ty::Const<'tcx>,
547         mut b: ty::Const<'tcx>,
548     ) -> RelateResult<'tcx, ty::Const<'tcx>> {
549         let a = self.infcx.shallow_resolve(a);
550 
551         if !D::forbid_inference_vars() {
552             b = self.infcx.shallow_resolve(b);
553         }
554 
555         match b.kind() {
556             ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => {
557                 // Forbid inference variables in the RHS.
558                 self.infcx.tcx.sess.delay_span_bug(
559                     self.delegate.span(),
560                     format!("unexpected inference var {:?}", b,),
561                 );
562                 Ok(a)
563             }
564             // FIXME(invariance): see the related FIXME above.
565             _ => self.infcx.super_combine_consts(self, a, b),
566         }
567     }
568 
569     #[instrument(skip(self), level = "trace")]
binders<T>( &mut self, a: ty::Binder<'tcx, T>, b: ty::Binder<'tcx, T>, ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> where T: Relate<'tcx>,570     fn binders<T>(
571         &mut self,
572         a: ty::Binder<'tcx, T>,
573         b: ty::Binder<'tcx, T>,
574     ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
575     where
576         T: Relate<'tcx>,
577     {
578         // We want that
579         //
580         // ```
581         // for<'a> fn(&'a u32) -> &'a u32 <:
582         //   fn(&'b u32) -> &'b u32
583         // ```
584         //
585         // but not
586         //
587         // ```
588         // fn(&'a u32) -> &'a u32 <:
589         //   for<'b> fn(&'b u32) -> &'b u32
590         // ```
591         //
592         // We therefore proceed as follows:
593         //
594         // - Instantiate binders on `b` universally, yielding a universe U1.
595         // - Instantiate binders on `a` existentially in U1.
596 
597         debug!(?self.ambient_variance);
598 
599         if let (Some(a), Some(b)) = (a.no_bound_vars(), b.no_bound_vars()) {
600             // Fast path for the common case.
601             self.relate(a, b)?;
602             return Ok(ty::Binder::dummy(a));
603         }
604 
605         if self.ambient_covariance() {
606             // Covariance, so we want `for<..> A <: for<..> B` --
607             // therefore we compare any instantiation of A (i.e., A
608             // instantiated with existentials) against every
609             // instantiation of B (i.e., B instantiated with
610             // universals).
611 
612             // Reset the ambient variance to covariant. This is needed
613             // to correctly handle cases like
614             //
615             //     for<'a> fn(&'a u32, &'a u32) == for<'b, 'c> fn(&'b u32, &'c u32)
616             //
617             // Somewhat surprisingly, these two types are actually
618             // **equal**, even though the one on the right looks more
619             // polymorphic. The reason is due to subtyping. To see it,
620             // consider that each function can call the other:
621             //
622             // - The left function can call the right with `'b` and
623             //   `'c` both equal to `'a`
624             //
625             // - The right function can call the left with `'a` set to
626             //   `{P}`, where P is the point in the CFG where the call
627             //   itself occurs. Note that `'b` and `'c` must both
628             //   include P. At the point, the call works because of
629             //   subtyping (i.e., `&'b u32 <: &{P} u32`).
630             let variance = std::mem::replace(&mut self.ambient_variance, ty::Variance::Covariant);
631 
632             // Note: the order here is important. Create the placeholders first, otherwise
633             // we assign the wrong universe to the existential!
634             let b_replaced = self.instantiate_binder_with_placeholders(b);
635             let a_replaced = self.instantiate_binder_with_existentials(a);
636 
637             self.relate(a_replaced, b_replaced)?;
638 
639             self.ambient_variance = variance;
640         }
641 
642         if self.ambient_contravariance() {
643             // Contravariance, so we want `for<..> A :> for<..> B`
644             // -- therefore we compare every instantiation of A (i.e.,
645             // A instantiated with universals) against any
646             // instantiation of B (i.e., B instantiated with
647             // existentials). Opposite of above.
648 
649             // Reset ambient variance to contravariance. See the
650             // covariant case above for an explanation.
651             let variance =
652                 std::mem::replace(&mut self.ambient_variance, ty::Variance::Contravariant);
653 
654             let a_replaced = self.instantiate_binder_with_placeholders(a);
655             let b_replaced = self.instantiate_binder_with_existentials(b);
656 
657             self.relate(a_replaced, b_replaced)?;
658 
659             self.ambient_variance = variance;
660         }
661 
662         Ok(a)
663     }
664 }
665 
666 impl<'tcx, D> ObligationEmittingRelation<'tcx> for TypeRelating<'_, 'tcx, D>
667 where
668     D: TypeRelatingDelegate<'tcx>,
669 {
register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>)670     fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) {
671         self.delegate.register_obligations(
672             obligations
673                 .into_iter()
674                 .map(|to_pred| {
675                     Obligation::new(self.tcx(), ObligationCause::dummy(), self.param_env(), to_pred)
676                 })
677                 .collect(),
678         );
679     }
680 
register_obligations(&mut self, obligations: PredicateObligations<'tcx>)681     fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) {
682         self.delegate.register_obligations(obligations);
683     }
684 
alias_relate_direction(&self) -> ty::AliasRelationDirection685     fn alias_relate_direction(&self) -> ty::AliasRelationDirection {
686         unreachable!("manually overridden to handle ty::Variance::Contravariant ambient variance")
687     }
688 
register_type_relate_obligation(&mut self, a: Ty<'tcx>, b: Ty<'tcx>)689     fn register_type_relate_obligation(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) {
690         self.register_predicates([ty::Binder::dummy(match self.ambient_variance {
691             ty::Variance::Covariant => ty::PredicateKind::AliasRelate(
692                 a.into(),
693                 b.into(),
694                 ty::AliasRelationDirection::Subtype,
695             ),
696             // a :> b is b <: a
697             ty::Variance::Contravariant => ty::PredicateKind::AliasRelate(
698                 b.into(),
699                 a.into(),
700                 ty::AliasRelationDirection::Subtype,
701             ),
702             ty::Variance::Invariant => ty::PredicateKind::AliasRelate(
703                 a.into(),
704                 b.into(),
705                 ty::AliasRelationDirection::Equate,
706             ),
707             // FIXME(deferred_projection_equality): Implement this when we trigger it.
708             // Probably just need to do nothing here.
709             ty::Variance::Bivariant => unreachable!(),
710         })]);
711     }
712 }
713