]>
Commit | Line | Data |
---|---|---|
0bf4aa26 XL |
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 | |
a1dfa0c6 | 4 | //! ought to be merged. This code is intended for use in NLL and chalk. |
0bf4aa26 XL |
5 | //! |
6 | //! Here are the key differences: | |
7 | //! | |
0731742a | 8 | //! - This code may choose to bypass some checks (e.g., the occurs check) |
a1dfa0c6 XL |
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. | |
0bf4aa26 XL |
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. | |
a1dfa0c6 XL |
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) | |
0bf4aa26 | 23 | |
0bf4aa26 | 24 | use rustc_data_structures::fx::FxHashMap; |
2b03887a | 25 | use rustc_middle::traits::ObligationCause; |
353b0b11 | 26 | use rustc_middle::ty::fold::FnMutDelegate; |
49aad941 FG |
27 | use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation}; |
28 | use rustc_middle::ty::visit::TypeVisitableExt; | |
ba9703b0 | 29 | use rustc_middle::ty::{self, InferConst, Ty, TyCtxt}; |
9ffffee4 | 30 | use rustc_span::{Span, Symbol}; |
532ac7d7 | 31 | use std::fmt::Debug; |
0bf4aa26 | 32 | |
49aad941 FG |
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}; | |
a1dfa0c6 | 38 | |
dc9dc135 | 39 | pub struct TypeRelating<'me, 'tcx, D> |
0bf4aa26 XL |
40 | where |
41 | D: TypeRelatingDelegate<'tcx>, | |
42 | { | |
2b03887a | 43 | infcx: &'me InferCtxt<'tcx>, |
0bf4aa26 | 44 | |
6a06907d | 45 | /// Callback to use when we deduce an outlives relationship. |
0bf4aa26 XL |
46 | delegate: D, |
47 | ||
48 | /// How are we relating `a` and `b`? | |
49 | /// | |
9fa01778 XL |
50 | /// - Covariant means `a <: b`. |
51 | /// - Contravariant means `b <: a`. | |
9ffffee4 | 52 | /// - Invariant means `a == b`. |
9fa01778 | 53 | /// - Bivariant means that it doesn't matter. |
0bf4aa26 XL |
54 | ambient_variance: ty::Variance, |
55 | ||
17df50a5 | 56 | ambient_variance_info: ty::VarianceDiagInfo<'tcx>, |
0bf4aa26 XL |
57 | } |
58 | ||
59 | pub trait TypeRelatingDelegate<'tcx> { | |
6a06907d | 60 | fn param_env(&self) -> ty::ParamEnv<'tcx>; |
5e7ed085 | 61 | fn span(&self) -> Span; |
6a06907d | 62 | |
0bf4aa26 XL |
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. | |
17df50a5 XL |
67 | fn push_outlives( |
68 | &mut self, | |
69 | sup: ty::Region<'tcx>, | |
70 | sub: ty::Region<'tcx>, | |
71 | info: ty::VarianceDiagInfo<'tcx>, | |
72 | ); | |
0bf4aa26 | 73 | |
9ffffee4 | 74 | fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>); |
a1dfa0c6 | 75 | |
0bf4aa26 XL |
76 | /// Creates a new universe index. Used when instantiating placeholders. |
77 | 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 | /// | |
0731742a | 83 | /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then |
0bf4aa26 XL |
84 | /// we will invoke this method to instantiate `'a` with an |
85 | /// inference variable (though `'b` would be instantiated first, | |
86 | /// as a placeholder). | |
9ffffee4 FG |
87 | fn next_existential_region_var( |
88 | &mut self, | |
89 | was_placeholder: bool, | |
90 | name: Option<Symbol>, | |
91 | ) -> ty::Region<'tcx>; | |
0bf4aa26 XL |
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 | /// | |
0731742a | 97 | /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then |
0bf4aa26 XL |
98 | /// we will invoke this method to instantiate `'b` with a |
99 | /// placeholder region. | |
a1dfa0c6 | 100 | fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>; |
0bf4aa26 XL |
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`). | |
109 | fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>; | |
a1dfa0c6 | 110 | |
9fa01778 | 111 | /// Enables some optimizations if we do not expect inference variables |
a1dfa0c6 XL |
112 | /// in the RHS of the relation. |
113 | fn forbid_inference_vars() -> bool; | |
0bf4aa26 XL |
114 | } |
115 | ||
0bf4aa26 XL |
116 | #[derive(Copy, Clone)] |
117 | struct UniversallyQuantified(bool); | |
118 | ||
dc9dc135 | 119 | impl<'me, 'tcx, D> TypeRelating<'me, 'tcx, D> |
0bf4aa26 XL |
120 | where |
121 | D: TypeRelatingDelegate<'tcx>, | |
122 | { | |
2b03887a | 123 | pub fn new(infcx: &'me InferCtxt<'tcx>, delegate: D, ambient_variance: ty::Variance) -> Self { |
17df50a5 XL |
124 | Self { |
125 | infcx, | |
126 | delegate, | |
127 | ambient_variance, | |
128 | ambient_variance_info: ty::VarianceDiagInfo::default(), | |
17df50a5 | 129 | } |
0bf4aa26 XL |
130 | } |
131 | ||
132 | 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 | ||
139 | 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 | ||
0bf4aa26 XL |
146 | /// Push a new outlives requirement into our output set of |
147 | /// constraints. | |
17df50a5 XL |
148 | fn push_outlives( |
149 | &mut self, | |
150 | sup: ty::Region<'tcx>, | |
151 | sub: ty::Region<'tcx>, | |
152 | info: ty::VarianceDiagInfo<'tcx>, | |
153 | ) { | |
0bf4aa26 XL |
154 | debug!("push_outlives({:?}: {:?})", sup, sub); |
155 | ||
17df50a5 | 156 | self.delegate.push_outlives(sup, sub, info); |
0bf4aa26 XL |
157 | } |
158 | ||
532ac7d7 XL |
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 | |
cdc7bbd5 | 162 | /// generalization G becomes the value of the inference variable, |
532ac7d7 XL |
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)` | |
94222f64 | 170 | /// -- in other words, it is always an (unresolved) inference |
532ac7d7 XL |
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. | |
177 | fn relate_ty_var<PAIR: VidValuePair<'tcx>>( | |
a1dfa0c6 | 178 | &mut self, |
532ac7d7 | 179 | pair: PAIR, |
a1dfa0c6 | 180 | ) -> RelateResult<'tcx, Ty<'tcx>> { |
532ac7d7 | 181 | debug!("relate_ty_var({:?})", pair); |
a1dfa0c6 | 182 | |
532ac7d7 XL |
183 | let vid = pair.vid(); |
184 | let value_ty = pair.value_ty(); | |
185 | ||
e74abb32 | 186 | // FIXME(invariance) -- this logic assumes invariance, but that is wrong. |
532ac7d7 XL |
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). | |
1b1a35ee | 190 | match *value_ty.kind() { |
a1dfa0c6 XL |
191 | ty::Infer(ty::TyVar(value_vid)) => { |
192 | // Two type variables: just equate them. | |
f9f354fc | 193 | self.infcx.inner.borrow_mut().type_variables().equate(vid, value_vid); |
a1dfa0c6 XL |
194 | return Ok(value_ty); |
195 | } | |
196 | ||
a1dfa0c6 XL |
197 | _ => (), |
198 | } | |
199 | ||
49aad941 | 200 | let generalized_ty = self.generalize(value_ty, vid)?; |
a1dfa0c6 XL |
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. | |
2b03887a | 207 | assert!(!generalized_ty.has_non_region_infer()); |
a1dfa0c6 | 208 | } |
0bf4aa26 | 209 | |
f9f354fc | 210 | self.infcx.inner.borrow_mut().type_variables().instantiate(vid, generalized_ty); |
0bf4aa26 | 211 | |
0bf4aa26 | 212 | // Relate the generalized kind to the original one. |
532ac7d7 | 213 | let result = pair.relate_generalized_ty(self, generalized_ty); |
0bf4aa26 | 214 | |
a1dfa0c6 | 215 | debug!("relate_ty_var: complete, result = {:?}", result); |
0bf4aa26 XL |
216 | result |
217 | } | |
218 | ||
49aad941 FG |
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) | |
0bf4aa26 | 228 | } |
f2b60f7d FG |
229 | |
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()) { | |
9c376795 FG |
247 | (&ty::Alias(ty::Opaque, ..), _) => (a, generalize(b, false)?), |
248 | (_, &ty::Alias(ty::Opaque, ..)) => (generalize(a, true)?, b), | |
f2b60f7d FG |
249 | _ => unreachable!(), |
250 | }; | |
2b03887a FG |
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; | |
487cf647 | 256 | self.delegate.register_obligations(obligations); |
f2b60f7d FG |
257 | trace!(a = ?a.kind(), b = ?b.kind(), "opaque type instantiated"); |
258 | Ok(a) | |
259 | } | |
353b0b11 FG |
260 | |
261 | #[instrument(skip(self), level = "debug")] | |
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")] | |
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 | } | |
0bf4aa26 XL |
351 | } |
352 | ||
94222f64 | 353 | /// When we instantiate an inference variable with a value in |
532ac7d7 XL |
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). | |
362 | 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). | |
366 | fn value_ty(&self) -> Ty<'tcx>; | |
367 | ||
532ac7d7 XL |
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. | |
371 | fn relate_generalized_ty<D>( | |
372 | &self, | |
dc9dc135 | 373 | relate: &mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
374 | generalized_ty: Ty<'tcx>, |
375 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
376 | where | |
377 | D: TypeRelatingDelegate<'tcx>; | |
378 | } | |
379 | ||
a2a8927a | 380 | impl<'tcx> VidValuePair<'tcx> for (ty::TyVid, Ty<'tcx>) { |
532ac7d7 XL |
381 | fn vid(&self) -> ty::TyVid { |
382 | self.0 | |
383 | } | |
384 | ||
385 | fn value_ty(&self) -> Ty<'tcx> { | |
386 | self.1 | |
387 | } | |
388 | ||
532ac7d7 XL |
389 | fn relate_generalized_ty<D>( |
390 | &self, | |
dc9dc135 | 391 | relate: &mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
392 | generalized_ty: Ty<'tcx>, |
393 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
394 | where | |
395 | D: TypeRelatingDelegate<'tcx>, | |
396 | { | |
5099ac24 | 397 | relate.relate(generalized_ty, self.value_ty()) |
532ac7d7 XL |
398 | } |
399 | } | |
400 | ||
401 | // In this case, the "vid" is the "b" type. | |
a2a8927a | 402 | impl<'tcx> VidValuePair<'tcx> for (Ty<'tcx>, ty::TyVid) { |
532ac7d7 XL |
403 | fn vid(&self) -> ty::TyVid { |
404 | self.1 | |
405 | } | |
406 | ||
407 | fn value_ty(&self) -> Ty<'tcx> { | |
408 | self.0 | |
409 | } | |
410 | ||
532ac7d7 XL |
411 | fn relate_generalized_ty<D>( |
412 | &self, | |
dc9dc135 | 413 | relate: &mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
414 | generalized_ty: Ty<'tcx>, |
415 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
416 | where | |
417 | D: TypeRelatingDelegate<'tcx>, | |
418 | { | |
5099ac24 | 419 | relate.relate(self.value_ty(), generalized_ty) |
532ac7d7 XL |
420 | } |
421 | } | |
422 | ||
a2a8927a | 423 | impl<'tcx, D> TypeRelation<'tcx> for TypeRelating<'_, 'tcx, D> |
0bf4aa26 XL |
424 | where |
425 | D: TypeRelatingDelegate<'tcx>, | |
426 | { | |
dc9dc135 | 427 | fn tcx(&self) -> TyCtxt<'tcx> { |
0bf4aa26 XL |
428 | self.infcx.tcx |
429 | } | |
430 | ||
dfeec247 | 431 | fn param_env(&self) -> ty::ParamEnv<'tcx> { |
6a06907d | 432 | self.delegate.param_env() |
dfeec247 | 433 | } |
416331ca | 434 | |
0bf4aa26 XL |
435 | fn tag(&self) -> &'static str { |
436 | "nll::subtype" | |
437 | } | |
438 | ||
439 | fn a_is_expected(&self) -> bool { | |
440 | true | |
441 | } | |
442 | ||
f2b60f7d | 443 | #[instrument(skip(self, info), level = "trace", ret)] |
0bf4aa26 XL |
444 | fn relate_with_variance<T: Relate<'tcx>>( |
445 | &mut self, | |
446 | variance: ty::Variance, | |
17df50a5 | 447 | info: ty::VarianceDiagInfo<'tcx>, |
f035d41b XL |
448 | a: T, |
449 | b: T, | |
0bf4aa26 | 450 | ) -> RelateResult<'tcx, T> { |
0bf4aa26 XL |
451 | let old_ambient_variance = self.ambient_variance; |
452 | self.ambient_variance = self.ambient_variance.xform(variance); | |
c295e0f8 | 453 | self.ambient_variance_info = self.ambient_variance_info.xform(info); |
0bf4aa26 | 454 | |
c295e0f8 | 455 | debug!(?self.ambient_variance); |
487cf647 FG |
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)? }; | |
0bf4aa26 XL |
459 | |
460 | self.ambient_variance = old_ambient_variance; | |
461 | ||
0bf4aa26 XL |
462 | Ok(r) |
463 | } | |
464 | ||
c295e0f8 | 465 | #[instrument(skip(self), level = "debug")] |
a1dfa0c6 | 466 | fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { |
5e7ed085 FG |
467 | let infcx = self.infcx; |
468 | ||
0bf4aa26 | 469 | let a = self.infcx.shallow_resolve(a); |
a1dfa0c6 XL |
470 | |
471 | if !D::forbid_inference_vars() { | |
472 | b = self.infcx.shallow_resolve(b); | |
473 | } | |
474 | ||
74b04a01 | 475 | if a == b { |
49aad941 | 476 | return Ok(a); |
74b04a01 XL |
477 | } |
478 | ||
1b1a35ee | 479 | match (a.kind(), b.kind()) { |
a1dfa0c6 XL |
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 { | |
532ac7d7 | 485 | self.relate_ty_var((a, vid)) |
a1dfa0c6 XL |
486 | } |
487 | } | |
488 | ||
532ac7d7 | 489 | (&ty::Infer(ty::TyVar(vid)), _) => self.relate_ty_var((vid, b)), |
a1dfa0c6 | 490 | |
9c376795 FG |
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, .. }), | |
49aad941 FG |
494 | ) if a_def_id == b_def_id || infcx.tcx.trait_solver_next() => { |
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.tcx().trait_solver_next()); | |
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 | } | |
9c376795 FG |
507 | (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _) |
508 | | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. })) | |
49aad941 | 509 | if def_id.is_local() && !self.tcx().trait_solver_next() => |
9c376795 | 510 | { |
f2b60f7d | 511 | self.relate_opaques(a, b) |
5e7ed085 FG |
512 | } |
513 | ||
0bf4aa26 | 514 | _ => { |
c295e0f8 | 515 | debug!(?a, ?b, ?self.ambient_variance); |
0bf4aa26 | 516 | |
a1dfa0c6 XL |
517 | // Will also handle unification of `IntVar` and `FloatVar`. |
518 | self.infcx.super_combine_tys(self, a, b) | |
0bf4aa26 XL |
519 | } |
520 | } | |
521 | } | |
522 | ||
c295e0f8 | 523 | #[instrument(skip(self), level = "trace")] |
0bf4aa26 XL |
524 | fn regions( |
525 | &mut self, | |
526 | a: ty::Region<'tcx>, | |
527 | b: ty::Region<'tcx>, | |
528 | ) -> RelateResult<'tcx, ty::Region<'tcx>> { | |
c295e0f8 | 529 | debug!(?self.ambient_variance); |
0bf4aa26 | 530 | |
0bf4aa26 | 531 | if self.ambient_covariance() { |
9ffffee4 | 532 | // Covariant: &'a u8 <: &'b u8. Hence, `'a: 'b`. |
353b0b11 | 533 | self.push_outlives(a, b, self.ambient_variance_info); |
0bf4aa26 XL |
534 | } |
535 | ||
536 | if self.ambient_contravariance() { | |
9ffffee4 | 537 | // Contravariant: &'b u8 <: &'a u8. Hence, `'b: 'a`. |
353b0b11 | 538 | self.push_outlives(b, a, self.ambient_variance_info); |
0bf4aa26 XL |
539 | } |
540 | ||
541 | Ok(a) | |
542 | } | |
543 | ||
48663c56 XL |
544 | fn consts( |
545 | &mut self, | |
5099ac24 FG |
546 | a: ty::Const<'tcx>, |
547 | mut b: ty::Const<'tcx>, | |
548 | ) -> RelateResult<'tcx, ty::Const<'tcx>> { | |
e74abb32 XL |
549 | let a = self.infcx.shallow_resolve(a); |
550 | ||
551 | if !D::forbid_inference_vars() { | |
552 | b = self.infcx.shallow_resolve(b); | |
553 | } | |
554 | ||
923072b8 | 555 | match b.kind() { |
60c5eb7d | 556 | ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => { |
e74abb32 | 557 | // Forbid inference variables in the RHS. |
923072b8 FG |
558 | self.infcx.tcx.sess.delay_span_bug( |
559 | self.delegate.span(), | |
560 | format!("unexpected inference var {:?}", b,), | |
561 | ); | |
562 | Ok(a) | |
e74abb32 XL |
563 | } |
564 | // FIXME(invariance): see the related FIXME above. | |
dfeec247 | 565 | _ => self.infcx.super_combine_consts(self, a, b), |
48663c56 XL |
566 | } |
567 | } | |
568 | ||
c295e0f8 | 569 | #[instrument(skip(self), level = "trace")] |
0bf4aa26 XL |
570 | fn binders<T>( |
571 | &mut self, | |
cdc7bbd5 XL |
572 | a: ty::Binder<'tcx, T>, |
573 | b: ty::Binder<'tcx, T>, | |
574 | ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> | |
0bf4aa26 XL |
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 | ||
c295e0f8 | 597 | debug!(?self.ambient_variance); |
0bf4aa26 | 598 | |
f035d41b | 599 | if let (Some(a), Some(b)) = (a.no_bound_vars(), b.no_bound_vars()) { |
74b04a01 | 600 | // Fast path for the common case. |
f035d41b | 601 | self.relate(a, b)?; |
29967ef6 | 602 | return Ok(ty::Binder::dummy(a)); |
74b04a01 XL |
603 | } |
604 | ||
0bf4aa26 XL |
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 | ||
0bf4aa26 XL |
612 | // Reset the ambient variance to covariant. This is needed |
613 | // to correctly handle cases like | |
614 | // | |
f9f354fc | 615 | // for<'a> fn(&'a u32, &'a u32) == for<'b, 'c> fn(&'b u32, &'c u32) |
0bf4aa26 XL |
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`). | |
29967ef6 | 630 | let variance = std::mem::replace(&mut self.ambient_variance, ty::Variance::Covariant); |
0bf4aa26 | 631 | |
353b0b11 FG |
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); | |
0bf4aa26 | 636 | |
353b0b11 | 637 | self.relate(a_replaced, b_replaced)?; |
0bf4aa26 | 638 | |
353b0b11 | 639 | self.ambient_variance = variance; |
0bf4aa26 XL |
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 | ||
0bf4aa26 XL |
649 | // Reset ambient variance to contravariance. See the |
650 | // covariant case above for an explanation. | |
651 | let variance = | |
29967ef6 | 652 | std::mem::replace(&mut self.ambient_variance, ty::Variance::Contravariant); |
0bf4aa26 | 653 | |
353b0b11 FG |
654 | let a_replaced = self.instantiate_binder_with_placeholders(a); |
655 | let b_replaced = self.instantiate_binder_with_existentials(b); | |
0bf4aa26 | 656 | |
353b0b11 | 657 | self.relate(a_replaced, b_replaced)?; |
0bf4aa26 | 658 | |
353b0b11 | 659 | self.ambient_variance = variance; |
0bf4aa26 XL |
660 | } |
661 | ||
3dfed10e | 662 | Ok(a) |
0bf4aa26 XL |
663 | } |
664 | } | |
665 | ||
9ffffee4 | 666 | impl<'tcx, D> ObligationEmittingRelation<'tcx> for TypeRelating<'_, 'tcx, D> |
f9f354fc XL |
667 | where |
668 | D: TypeRelatingDelegate<'tcx>, | |
669 | { | |
9ffffee4 FG |
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 | ||
681 | fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) { | |
682 | self.delegate.register_obligations(obligations); | |
f9f354fc | 683 | } |
353b0b11 FG |
684 | |
685 | fn alias_relate_direction(&self) -> ty::AliasRelationDirection { | |
686 | unreachable!("manually overridden to handle ty::Variance::Contravariant ambient variance") | |
687 | } | |
688 | ||
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 | } | |
f9f354fc | 712 | } |