]>
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 | |
f9f354fc | 24 | use crate::infer::combine::ConstEquateRelation; |
0bf4aa26 | 25 | use crate::infer::InferCtxt; |
dfeec247 | 26 | use crate::infer::{ConstVarValue, ConstVariableValue}; |
0bf4aa26 | 27 | use rustc_data_structures::fx::FxHashMap; |
ba9703b0 XL |
28 | use rustc_middle::ty::error::TypeError; |
29 | use rustc_middle::ty::fold::{TypeFoldable, TypeVisitor}; | |
30 | use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation}; | |
ba9703b0 | 31 | use rustc_middle::ty::{self, InferConst, Ty, TyCtxt}; |
532ac7d7 | 32 | use std::fmt::Debug; |
29967ef6 | 33 | use std::ops::ControlFlow; |
0bf4aa26 | 34 | |
e74abb32 | 35 | #[derive(PartialEq)] |
a1dfa0c6 XL |
36 | pub enum NormalizationStrategy { |
37 | Lazy, | |
38 | Eager, | |
39 | } | |
40 | ||
dc9dc135 | 41 | pub struct TypeRelating<'me, 'tcx, D> |
0bf4aa26 XL |
42 | where |
43 | D: TypeRelatingDelegate<'tcx>, | |
44 | { | |
dc9dc135 | 45 | infcx: &'me InferCtxt<'me, 'tcx>, |
0bf4aa26 | 46 | |
6a06907d | 47 | /// Callback to use when we deduce an outlives relationship. |
0bf4aa26 XL |
48 | delegate: D, |
49 | ||
50 | /// How are we relating `a` and `b`? | |
51 | /// | |
9fa01778 XL |
52 | /// - Covariant means `a <: b`. |
53 | /// - Contravariant means `b <: a`. | |
54 | /// - Invariant means `a == b. | |
55 | /// - Bivariant means that it doesn't matter. | |
0bf4aa26 XL |
56 | ambient_variance: ty::Variance, |
57 | ||
17df50a5 XL |
58 | ambient_variance_info: ty::VarianceDiagInfo<'tcx>, |
59 | ||
0bf4aa26 | 60 | /// When we pass through a set of binders (e.g., when looking into |
9fa01778 | 61 | /// a `fn` type), we push a new bound region scope onto here. This |
0bf4aa26 XL |
62 | /// will contain the instantiated region for each region in those |
63 | /// binders. When we then encounter a `ReLateBound(d, br)`, we can | |
9fa01778 | 64 | /// use the De Bruijn index `d` to find the right scope, and then |
0bf4aa26 XL |
65 | /// bound region name `br` to find the specific instantiation from |
66 | /// within that scope. See `replace_bound_region`. | |
67 | /// | |
68 | /// This field stores the instantiations for late-bound regions in | |
69 | /// the `a` type. | |
70 | a_scopes: Vec<BoundRegionScope<'tcx>>, | |
71 | ||
72 | /// Same as `a_scopes`, but for the `b` type. | |
73 | b_scopes: Vec<BoundRegionScope<'tcx>>, | |
74 | } | |
75 | ||
76 | pub trait TypeRelatingDelegate<'tcx> { | |
6a06907d XL |
77 | fn param_env(&self) -> ty::ParamEnv<'tcx>; |
78 | ||
0bf4aa26 XL |
79 | /// Push a constraint `sup: sub` -- this constraint must be |
80 | /// satisfied for the two types to be related. `sub` and `sup` may | |
81 | /// be regions from the type or new variables created through the | |
82 | /// delegate. | |
17df50a5 XL |
83 | fn push_outlives( |
84 | &mut self, | |
85 | sup: ty::Region<'tcx>, | |
86 | sub: ty::Region<'tcx>, | |
87 | info: ty::VarianceDiagInfo<'tcx>, | |
88 | ); | |
0bf4aa26 | 89 | |
f9f354fc | 90 | fn const_equate(&mut self, a: &'tcx ty::Const<'tcx>, b: &'tcx ty::Const<'tcx>); |
a1dfa0c6 | 91 | |
0bf4aa26 XL |
92 | /// Creates a new universe index. Used when instantiating placeholders. |
93 | fn create_next_universe(&mut self) -> ty::UniverseIndex; | |
94 | ||
95 | /// Creates a new region variable representing a higher-ranked | |
96 | /// region that is instantiated existentially. This creates an | |
97 | /// inference variable, typically. | |
98 | /// | |
0731742a | 99 | /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then |
0bf4aa26 XL |
100 | /// we will invoke this method to instantiate `'a` with an |
101 | /// inference variable (though `'b` would be instantiated first, | |
102 | /// as a placeholder). | |
e74abb32 | 103 | fn next_existential_region_var(&mut self, was_placeholder: bool) -> ty::Region<'tcx>; |
0bf4aa26 XL |
104 | |
105 | /// Creates a new region variable representing a | |
106 | /// higher-ranked region that is instantiated universally. | |
107 | /// This creates a new region placeholder, typically. | |
108 | /// | |
0731742a | 109 | /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then |
0bf4aa26 XL |
110 | /// we will invoke this method to instantiate `'b` with a |
111 | /// placeholder region. | |
a1dfa0c6 | 112 | fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>; |
0bf4aa26 XL |
113 | |
114 | /// Creates a new existential region in the given universe. This | |
115 | /// is used when handling subtyping and type variables -- if we | |
116 | /// have that `?X <: Foo<'a>`, for example, we would instantiate | |
117 | /// `?X` with a type like `Foo<'?0>` where `'?0` is a fresh | |
118 | /// existential variable created by this function. We would then | |
119 | /// relate `Foo<'?0>` with `Foo<'a>` (and probably add an outlives | |
120 | /// relation stating that `'?0: 'a`). | |
121 | fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>; | |
a1dfa0c6 XL |
122 | |
123 | /// Define the normalization strategy to use, eager or lazy. | |
124 | fn normalization() -> NormalizationStrategy; | |
125 | ||
9fa01778 | 126 | /// Enables some optimizations if we do not expect inference variables |
a1dfa0c6 XL |
127 | /// in the RHS of the relation. |
128 | fn forbid_inference_vars() -> bool; | |
0bf4aa26 XL |
129 | } |
130 | ||
0bf4aa26 XL |
131 | #[derive(Clone, Debug, Default)] |
132 | struct BoundRegionScope<'tcx> { | |
133 | map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>, | |
134 | } | |
135 | ||
136 | #[derive(Copy, Clone)] | |
137 | struct UniversallyQuantified(bool); | |
138 | ||
dc9dc135 | 139 | impl<'me, 'tcx, D> TypeRelating<'me, 'tcx, D> |
0bf4aa26 XL |
140 | where |
141 | D: TypeRelatingDelegate<'tcx>, | |
142 | { | |
143 | pub fn new( | |
dc9dc135 | 144 | infcx: &'me InferCtxt<'me, 'tcx>, |
0bf4aa26 XL |
145 | delegate: D, |
146 | ambient_variance: ty::Variance, | |
147 | ) -> Self { | |
17df50a5 XL |
148 | Self { |
149 | infcx, | |
150 | delegate, | |
151 | ambient_variance, | |
152 | ambient_variance_info: ty::VarianceDiagInfo::default(), | |
153 | a_scopes: vec![], | |
154 | b_scopes: vec![], | |
155 | } | |
0bf4aa26 XL |
156 | } |
157 | ||
158 | fn ambient_covariance(&self) -> bool { | |
159 | match self.ambient_variance { | |
160 | ty::Variance::Covariant | ty::Variance::Invariant => true, | |
161 | ty::Variance::Contravariant | ty::Variance::Bivariant => false, | |
162 | } | |
163 | } | |
164 | ||
165 | fn ambient_contravariance(&self) -> bool { | |
166 | match self.ambient_variance { | |
167 | ty::Variance::Contravariant | ty::Variance::Invariant => true, | |
168 | ty::Variance::Covariant | ty::Variance::Bivariant => false, | |
169 | } | |
170 | } | |
171 | ||
172 | fn create_scope( | |
173 | &mut self, | |
cdc7bbd5 | 174 | value: ty::Binder<'tcx, impl Relate<'tcx>>, |
0bf4aa26 XL |
175 | universally_quantified: UniversallyQuantified, |
176 | ) -> BoundRegionScope<'tcx> { | |
177 | let mut scope = BoundRegionScope::default(); | |
178 | ||
179 | // Create a callback that creates (via the delegate) either an | |
180 | // existential or placeholder region as needed. | |
181 | let mut next_region = { | |
182 | let delegate = &mut self.delegate; | |
183 | let mut lazy_universe = None; | |
184 | move |br: ty::BoundRegion| { | |
185 | if universally_quantified.0 { | |
186 | // The first time this closure is called, create a | |
187 | // new universe for the placeholders we will make | |
188 | // from here out. | |
189 | let universe = lazy_universe.unwrap_or_else(|| { | |
190 | let universe = delegate.create_next_universe(); | |
191 | lazy_universe = Some(universe); | |
192 | universe | |
193 | }); | |
194 | ||
fc512014 | 195 | let placeholder = ty::PlaceholderRegion { universe, name: br.kind }; |
0bf4aa26 XL |
196 | delegate.next_placeholder_region(placeholder) |
197 | } else { | |
e74abb32 | 198 | delegate.next_existential_region_var(true) |
0bf4aa26 XL |
199 | } |
200 | } | |
201 | }; | |
202 | ||
203 | value.skip_binder().visit_with(&mut ScopeInstantiator { | |
94222f64 | 204 | tcx: self.infcx.tcx, |
0bf4aa26 XL |
205 | next_region: &mut next_region, |
206 | target_index: ty::INNERMOST, | |
207 | bound_region_scope: &mut scope, | |
208 | }); | |
209 | ||
210 | scope | |
211 | } | |
212 | ||
213 | /// When we encounter binders during the type traversal, we record | |
214 | /// the value to substitute for each of the things contained in | |
215 | /// that binder. (This will be either a universal placeholder or | |
9fa01778 | 216 | /// an existential inference variable.) Given the De Bruijn index |
0bf4aa26 XL |
217 | /// `debruijn` (and name `br`) of some binder we have now |
218 | /// encountered, this routine finds the value that we instantiated | |
219 | /// the region with; to do so, it indexes backwards into the list | |
220 | /// of ambient scopes `scopes`. | |
221 | fn lookup_bound_region( | |
222 | debruijn: ty::DebruijnIndex, | |
223 | br: &ty::BoundRegion, | |
224 | first_free_index: ty::DebruijnIndex, | |
225 | scopes: &[BoundRegionScope<'tcx>], | |
226 | ) -> ty::Region<'tcx> { | |
227 | // The debruijn index is a "reverse index" into the | |
228 | // scopes listing. So when we have INNERMOST (0), we | |
229 | // want the *last* scope pushed, and so forth. | |
230 | let debruijn_index = debruijn.index() - first_free_index.index(); | |
231 | let scope = &scopes[scopes.len() - debruijn_index - 1]; | |
232 | ||
233 | // Find this bound region in that scope to map to a | |
234 | // particular region. | |
235 | scope.map[br] | |
236 | } | |
237 | ||
238 | /// If `r` is a bound region, find the scope in which it is bound | |
239 | /// (from `scopes`) and return the value that we instantiated it | |
240 | /// with. Otherwise just return `r`. | |
241 | fn replace_bound_region( | |
242 | &self, | |
243 | r: ty::Region<'tcx>, | |
244 | first_free_index: ty::DebruijnIndex, | |
245 | scopes: &[BoundRegionScope<'tcx>], | |
246 | ) -> ty::Region<'tcx> { | |
532ac7d7 | 247 | debug!("replace_bound_regions(scopes={:?})", scopes); |
0bf4aa26 XL |
248 | if let ty::ReLateBound(debruijn, br) = r { |
249 | Self::lookup_bound_region(*debruijn, br, first_free_index, scopes) | |
250 | } else { | |
251 | r | |
252 | } | |
253 | } | |
254 | ||
255 | /// Push a new outlives requirement into our output set of | |
256 | /// constraints. | |
17df50a5 XL |
257 | fn push_outlives( |
258 | &mut self, | |
259 | sup: ty::Region<'tcx>, | |
260 | sub: ty::Region<'tcx>, | |
261 | info: ty::VarianceDiagInfo<'tcx>, | |
262 | ) { | |
0bf4aa26 XL |
263 | debug!("push_outlives({:?}: {:?})", sup, sub); |
264 | ||
17df50a5 | 265 | self.delegate.push_outlives(sup, sub, info); |
0bf4aa26 XL |
266 | } |
267 | ||
a1dfa0c6 XL |
268 | /// Relate a projection type and some value type lazily. This will always |
269 | /// succeed, but we push an additional `ProjectionEq` goal depending | |
270 | /// on the value type: | |
271 | /// - if the value type is any type `T` which is not a projection, we push | |
272 | /// `ProjectionEq(projection = T)`. | |
273 | /// - if the value type is another projection `other_projection`, we create | |
274 | /// a new inference variable `?U` and push the two goals | |
275 | /// `ProjectionEq(projection = ?U)`, `ProjectionEq(other_projection = ?U)`. | |
276 | fn relate_projection_ty( | |
277 | &mut self, | |
278 | projection_ty: ty::ProjectionTy<'tcx>, | |
48663c56 | 279 | value_ty: Ty<'tcx>, |
a1dfa0c6 | 280 | ) -> Ty<'tcx> { |
dc9dc135 | 281 | use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; |
dfeec247 | 282 | use rustc_span::DUMMY_SP; |
a1dfa0c6 | 283 | |
1b1a35ee | 284 | match *value_ty.kind() { |
a1dfa0c6 | 285 | ty::Projection(other_projection_ty) => { |
dc9dc135 XL |
286 | let var = self.infcx.next_ty_var(TypeVariableOrigin { |
287 | kind: TypeVariableOriginKind::MiscVariable, | |
288 | span: DUMMY_SP, | |
289 | }); | |
a1dfa0c6 XL |
290 | self.relate_projection_ty(projection_ty, var); |
291 | self.relate_projection_ty(other_projection_ty, var); | |
292 | var | |
293 | } | |
294 | ||
f9f354fc | 295 | _ => bug!("should never be invoked with eager normalization"), |
a1dfa0c6 XL |
296 | } |
297 | } | |
298 | ||
532ac7d7 XL |
299 | /// Relate a type inference variable with a value type. This works |
300 | /// by creating a "generalization" G of the value where all the | |
301 | /// lifetimes are replaced with fresh inference values. This | |
cdc7bbd5 | 302 | /// generalization G becomes the value of the inference variable, |
532ac7d7 XL |
303 | /// and is then related in turn to the value. So e.g. if you had |
304 | /// `vid = ?0` and `value = &'a u32`, we might first instantiate | |
305 | /// `?0` to a type like `&'0 u32` where `'0` is a fresh variable, | |
306 | /// and then relate `&'0 u32` with `&'a u32` (resulting in | |
307 | /// relations between `'0` and `'a`). | |
308 | /// | |
309 | /// The variable `pair` can be either a `(vid, ty)` or `(ty, vid)` | |
94222f64 | 310 | /// -- in other words, it is always an (unresolved) inference |
532ac7d7 XL |
311 | /// variable `vid` and a type `ty` that are being related, but the |
312 | /// vid may appear either as the "a" type or the "b" type, | |
313 | /// depending on where it appears in the tuple. The trait | |
314 | /// `VidValuePair` lets us work with the vid/type while preserving | |
315 | /// the "sidedness" when necessary -- the sidedness is relevant in | |
316 | /// particular for the variance and set of in-scope things. | |
317 | fn relate_ty_var<PAIR: VidValuePair<'tcx>>( | |
a1dfa0c6 | 318 | &mut self, |
532ac7d7 | 319 | pair: PAIR, |
a1dfa0c6 | 320 | ) -> RelateResult<'tcx, Ty<'tcx>> { |
532ac7d7 | 321 | debug!("relate_ty_var({:?})", pair); |
a1dfa0c6 | 322 | |
532ac7d7 XL |
323 | let vid = pair.vid(); |
324 | let value_ty = pair.value_ty(); | |
325 | ||
e74abb32 | 326 | // FIXME(invariance) -- this logic assumes invariance, but that is wrong. |
532ac7d7 XL |
327 | // This only presently applies to chalk integration, as NLL |
328 | // doesn't permit type variables to appear on both sides (and | |
329 | // doesn't use lazy norm). | |
1b1a35ee | 330 | match *value_ty.kind() { |
a1dfa0c6 XL |
331 | ty::Infer(ty::TyVar(value_vid)) => { |
332 | // Two type variables: just equate them. | |
f9f354fc | 333 | self.infcx.inner.borrow_mut().type_variables().equate(vid, value_vid); |
a1dfa0c6 XL |
334 | return Ok(value_ty); |
335 | } | |
336 | ||
532ac7d7 XL |
337 | ty::Projection(projection_ty) if D::normalization() == NormalizationStrategy::Lazy => { |
338 | return Ok(self.relate_projection_ty(projection_ty, self.infcx.tcx.mk_ty_var(vid))); | |
a1dfa0c6 XL |
339 | } |
340 | ||
341 | _ => (), | |
342 | } | |
343 | ||
344 | let generalized_ty = self.generalize_value(value_ty, vid)?; | |
345 | debug!("relate_ty_var: generalized_ty = {:?}", generalized_ty); | |
346 | ||
347 | if D::forbid_inference_vars() { | |
348 | // In NLL, we don't have type inference variables | |
349 | // floating around, so we can do this rather imprecise | |
350 | // variant of the occurs-check. | |
74b04a01 | 351 | assert!(!generalized_ty.has_infer_types_or_consts()); |
a1dfa0c6 | 352 | } |
0bf4aa26 | 353 | |
f9f354fc | 354 | self.infcx.inner.borrow_mut().type_variables().instantiate(vid, generalized_ty); |
0bf4aa26 XL |
355 | |
356 | // The generalized values we extract from `canonical_var_values` have | |
357 | // been fully instantiated and hence the set of scopes we have | |
358 | // doesn't matter -- just to be sure, put an empty vector | |
359 | // in there. | |
29967ef6 | 360 | let old_a_scopes = std::mem::take(pair.vid_scopes(self)); |
0bf4aa26 XL |
361 | |
362 | // Relate the generalized kind to the original one. | |
532ac7d7 | 363 | let result = pair.relate_generalized_ty(self, generalized_ty); |
0bf4aa26 XL |
364 | |
365 | // Restore the old scopes now. | |
532ac7d7 | 366 | *pair.vid_scopes(self) = old_a_scopes; |
0bf4aa26 | 367 | |
a1dfa0c6 | 368 | debug!("relate_ty_var: complete, result = {:?}", result); |
0bf4aa26 XL |
369 | result |
370 | } | |
371 | ||
a1dfa0c6 XL |
372 | fn generalize_value<T: Relate<'tcx>>( |
373 | &mut self, | |
374 | value: T, | |
532ac7d7 | 375 | for_vid: ty::TyVid, |
a1dfa0c6 XL |
376 | ) -> RelateResult<'tcx, T> { |
377 | let universe = self.infcx.probe_ty_var(for_vid).unwrap_err(); | |
378 | ||
379 | let mut generalizer = TypeGeneralizer { | |
380 | infcx: self.infcx, | |
0bf4aa26 XL |
381 | delegate: &mut self.delegate, |
382 | first_free_index: ty::INNERMOST, | |
383 | ambient_variance: self.ambient_variance, | |
f9f354fc | 384 | for_vid_sub_root: self.infcx.inner.borrow_mut().type_variables().sub_root_var(for_vid), |
a1dfa0c6 XL |
385 | universe, |
386 | }; | |
0bf4aa26 | 387 | |
f035d41b | 388 | generalizer.relate(value, value) |
0bf4aa26 XL |
389 | } |
390 | } | |
391 | ||
94222f64 | 392 | /// When we instantiate an inference variable with a value in |
532ac7d7 XL |
393 | /// `relate_ty_var`, we always have the pair of a `TyVid` and a `Ty`, |
394 | /// but the ordering may vary (depending on whether the inference | |
395 | /// variable was found on the `a` or `b` sides). Therefore, this trait | |
396 | /// allows us to factor out common code, while preserving the order | |
397 | /// when needed. | |
398 | trait VidValuePair<'tcx>: Debug { | |
399 | /// Extract the inference variable (which could be either the | |
400 | /// first or second part of the tuple). | |
401 | fn vid(&self) -> ty::TyVid; | |
402 | ||
403 | /// Extract the value it is being related to (which will be the | |
404 | /// opposite part of the tuple from the vid). | |
405 | fn value_ty(&self) -> Ty<'tcx>; | |
406 | ||
407 | /// Extract the scopes that apply to whichever side of the tuple | |
408 | /// the vid was found on. See the comment where this is called | |
409 | /// for more details on why we want them. | |
410 | fn vid_scopes<D: TypeRelatingDelegate<'tcx>>( | |
411 | &self, | |
dc9dc135 | 412 | relate: &'r mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
413 | ) -> &'r mut Vec<BoundRegionScope<'tcx>>; |
414 | ||
415 | /// Given a generalized type G that should replace the vid, relate | |
416 | /// G to the value, putting G on whichever side the vid would have | |
417 | /// appeared. | |
418 | fn relate_generalized_ty<D>( | |
419 | &self, | |
dc9dc135 | 420 | relate: &mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
421 | generalized_ty: Ty<'tcx>, |
422 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
423 | where | |
424 | D: TypeRelatingDelegate<'tcx>; | |
425 | } | |
426 | ||
427 | impl VidValuePair<'tcx> for (ty::TyVid, Ty<'tcx>) { | |
428 | fn vid(&self) -> ty::TyVid { | |
429 | self.0 | |
430 | } | |
431 | ||
432 | fn value_ty(&self) -> Ty<'tcx> { | |
433 | self.1 | |
434 | } | |
435 | ||
436 | fn vid_scopes<D>( | |
437 | &self, | |
dc9dc135 | 438 | relate: &'r mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
439 | ) -> &'r mut Vec<BoundRegionScope<'tcx>> |
440 | where | |
441 | D: TypeRelatingDelegate<'tcx>, | |
442 | { | |
443 | &mut relate.a_scopes | |
444 | } | |
445 | ||
446 | fn relate_generalized_ty<D>( | |
447 | &self, | |
dc9dc135 | 448 | relate: &mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
449 | generalized_ty: Ty<'tcx>, |
450 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
451 | where | |
452 | D: TypeRelatingDelegate<'tcx>, | |
453 | { | |
454 | relate.relate(&generalized_ty, &self.value_ty()) | |
455 | } | |
456 | } | |
457 | ||
458 | // In this case, the "vid" is the "b" type. | |
459 | impl VidValuePair<'tcx> for (Ty<'tcx>, ty::TyVid) { | |
460 | fn vid(&self) -> ty::TyVid { | |
461 | self.1 | |
462 | } | |
463 | ||
464 | fn value_ty(&self) -> Ty<'tcx> { | |
465 | self.0 | |
466 | } | |
467 | ||
468 | fn vid_scopes<D>( | |
469 | &self, | |
dc9dc135 | 470 | relate: &'r mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
471 | ) -> &'r mut Vec<BoundRegionScope<'tcx>> |
472 | where | |
473 | D: TypeRelatingDelegate<'tcx>, | |
474 | { | |
475 | &mut relate.b_scopes | |
476 | } | |
477 | ||
478 | fn relate_generalized_ty<D>( | |
479 | &self, | |
dc9dc135 | 480 | relate: &mut TypeRelating<'_, 'tcx, D>, |
532ac7d7 XL |
481 | generalized_ty: Ty<'tcx>, |
482 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
483 | where | |
484 | D: TypeRelatingDelegate<'tcx>, | |
485 | { | |
486 | relate.relate(&self.value_ty(), &generalized_ty) | |
487 | } | |
488 | } | |
489 | ||
dc9dc135 | 490 | impl<D> TypeRelation<'tcx> for TypeRelating<'me, 'tcx, D> |
0bf4aa26 XL |
491 | where |
492 | D: TypeRelatingDelegate<'tcx>, | |
493 | { | |
dc9dc135 | 494 | fn tcx(&self) -> TyCtxt<'tcx> { |
0bf4aa26 XL |
495 | self.infcx.tcx |
496 | } | |
497 | ||
dfeec247 | 498 | fn param_env(&self) -> ty::ParamEnv<'tcx> { |
6a06907d | 499 | self.delegate.param_env() |
dfeec247 | 500 | } |
416331ca | 501 | |
0bf4aa26 XL |
502 | fn tag(&self) -> &'static str { |
503 | "nll::subtype" | |
504 | } | |
505 | ||
506 | fn a_is_expected(&self) -> bool { | |
507 | true | |
508 | } | |
509 | ||
c295e0f8 | 510 | #[instrument(skip(self, info), level = "trace")] |
0bf4aa26 XL |
511 | fn relate_with_variance<T: Relate<'tcx>>( |
512 | &mut self, | |
513 | variance: ty::Variance, | |
17df50a5 | 514 | info: ty::VarianceDiagInfo<'tcx>, |
f035d41b XL |
515 | a: T, |
516 | b: T, | |
0bf4aa26 | 517 | ) -> RelateResult<'tcx, T> { |
0bf4aa26 XL |
518 | let old_ambient_variance = self.ambient_variance; |
519 | self.ambient_variance = self.ambient_variance.xform(variance); | |
c295e0f8 | 520 | self.ambient_variance_info = self.ambient_variance_info.xform(info); |
0bf4aa26 | 521 | |
c295e0f8 | 522 | debug!(?self.ambient_variance); |
0bf4aa26 XL |
523 | |
524 | let r = self.relate(a, b)?; | |
525 | ||
526 | self.ambient_variance = old_ambient_variance; | |
527 | ||
c295e0f8 | 528 | debug!(?r); |
0bf4aa26 XL |
529 | |
530 | Ok(r) | |
531 | } | |
532 | ||
c295e0f8 | 533 | #[instrument(skip(self), level = "debug")] |
a1dfa0c6 | 534 | fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { |
0bf4aa26 | 535 | let a = self.infcx.shallow_resolve(a); |
a1dfa0c6 XL |
536 | |
537 | if !D::forbid_inference_vars() { | |
538 | b = self.infcx.shallow_resolve(b); | |
539 | } | |
540 | ||
74b04a01 | 541 | if a == b { |
f035d41b XL |
542 | // Subtle: if a or b has a bound variable that we are lazilly |
543 | // substituting, then even if a == b, it could be that the values we | |
544 | // will substitute for those bound variables are *not* the same, and | |
545 | // hence returning `Ok(a)` is incorrect. | |
546 | if !a.has_escaping_bound_vars() && !b.has_escaping_bound_vars() { | |
547 | return Ok(a); | |
548 | } | |
74b04a01 XL |
549 | } |
550 | ||
1b1a35ee | 551 | match (a.kind(), b.kind()) { |
a1dfa0c6 XL |
552 | (_, &ty::Infer(ty::TyVar(vid))) => { |
553 | if D::forbid_inference_vars() { | |
554 | // Forbid inference variables in the RHS. | |
555 | bug!("unexpected inference var {:?}", b) | |
556 | } else { | |
532ac7d7 | 557 | self.relate_ty_var((a, vid)) |
a1dfa0c6 XL |
558 | } |
559 | } | |
560 | ||
532ac7d7 | 561 | (&ty::Infer(ty::TyVar(vid)), _) => self.relate_ty_var((vid, b)), |
a1dfa0c6 XL |
562 | |
563 | (&ty::Projection(projection_ty), _) | |
564 | if D::normalization() == NormalizationStrategy::Lazy => | |
565 | { | |
566 | Ok(self.relate_projection_ty(projection_ty, b)) | |
567 | } | |
568 | ||
569 | (_, &ty::Projection(projection_ty)) | |
570 | if D::normalization() == NormalizationStrategy::Lazy => | |
571 | { | |
572 | Ok(self.relate_projection_ty(projection_ty, a)) | |
0bf4aa26 XL |
573 | } |
574 | ||
575 | _ => { | |
c295e0f8 | 576 | debug!(?a, ?b, ?self.ambient_variance); |
0bf4aa26 | 577 | |
a1dfa0c6 XL |
578 | // Will also handle unification of `IntVar` and `FloatVar`. |
579 | self.infcx.super_combine_tys(self, a, b) | |
0bf4aa26 XL |
580 | } |
581 | } | |
582 | } | |
583 | ||
c295e0f8 | 584 | #[instrument(skip(self), level = "trace")] |
0bf4aa26 XL |
585 | fn regions( |
586 | &mut self, | |
587 | a: ty::Region<'tcx>, | |
588 | b: ty::Region<'tcx>, | |
589 | ) -> RelateResult<'tcx, ty::Region<'tcx>> { | |
c295e0f8 | 590 | debug!(?self.ambient_variance); |
0bf4aa26 XL |
591 | |
592 | let v_a = self.replace_bound_region(a, ty::INNERMOST, &self.a_scopes); | |
593 | let v_b = self.replace_bound_region(b, ty::INNERMOST, &self.b_scopes); | |
594 | ||
c295e0f8 XL |
595 | debug!(?v_a); |
596 | debug!(?v_b); | |
0bf4aa26 XL |
597 | |
598 | if self.ambient_covariance() { | |
599 | // Covariance: a <= b. Hence, `b: a`. | |
c295e0f8 | 600 | self.push_outlives(v_b, v_a, self.ambient_variance_info); |
0bf4aa26 XL |
601 | } |
602 | ||
603 | if self.ambient_contravariance() { | |
604 | // Contravariant: b <= a. Hence, `a: b`. | |
c295e0f8 | 605 | self.push_outlives(v_a, v_b, self.ambient_variance_info); |
0bf4aa26 XL |
606 | } |
607 | ||
608 | Ok(a) | |
609 | } | |
610 | ||
48663c56 XL |
611 | fn consts( |
612 | &mut self, | |
613 | a: &'tcx ty::Const<'tcx>, | |
e74abb32 | 614 | mut b: &'tcx ty::Const<'tcx>, |
48663c56 | 615 | ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> { |
e74abb32 XL |
616 | let a = self.infcx.shallow_resolve(a); |
617 | ||
618 | if !D::forbid_inference_vars() { | |
619 | b = self.infcx.shallow_resolve(b); | |
620 | } | |
621 | ||
622 | match b.val { | |
60c5eb7d | 623 | ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => { |
e74abb32 XL |
624 | // Forbid inference variables in the RHS. |
625 | bug!("unexpected inference var {:?}", b) | |
626 | } | |
627 | // FIXME(invariance): see the related FIXME above. | |
dfeec247 | 628 | _ => self.infcx.super_combine_consts(self, a, b), |
48663c56 XL |
629 | } |
630 | } | |
631 | ||
c295e0f8 | 632 | #[instrument(skip(self), level = "trace")] |
0bf4aa26 XL |
633 | fn binders<T>( |
634 | &mut self, | |
cdc7bbd5 XL |
635 | a: ty::Binder<'tcx, T>, |
636 | b: ty::Binder<'tcx, T>, | |
637 | ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> | |
0bf4aa26 XL |
638 | where |
639 | T: Relate<'tcx>, | |
640 | { | |
641 | // We want that | |
642 | // | |
643 | // ``` | |
644 | // for<'a> fn(&'a u32) -> &'a u32 <: | |
645 | // fn(&'b u32) -> &'b u32 | |
646 | // ``` | |
647 | // | |
648 | // but not | |
649 | // | |
650 | // ``` | |
651 | // fn(&'a u32) -> &'a u32 <: | |
652 | // for<'b> fn(&'b u32) -> &'b u32 | |
653 | // ``` | |
654 | // | |
655 | // We therefore proceed as follows: | |
656 | // | |
657 | // - Instantiate binders on `b` universally, yielding a universe U1. | |
658 | // - Instantiate binders on `a` existentially in U1. | |
659 | ||
c295e0f8 | 660 | debug!(?self.ambient_variance); |
0bf4aa26 | 661 | |
f035d41b | 662 | if let (Some(a), Some(b)) = (a.no_bound_vars(), b.no_bound_vars()) { |
74b04a01 | 663 | // Fast path for the common case. |
f035d41b | 664 | self.relate(a, b)?; |
29967ef6 | 665 | return Ok(ty::Binder::dummy(a)); |
74b04a01 XL |
666 | } |
667 | ||
0bf4aa26 XL |
668 | if self.ambient_covariance() { |
669 | // Covariance, so we want `for<..> A <: for<..> B` -- | |
670 | // therefore we compare any instantiation of A (i.e., A | |
671 | // instantiated with existentials) against every | |
672 | // instantiation of B (i.e., B instantiated with | |
673 | // universals). | |
674 | ||
675 | let b_scope = self.create_scope(b, UniversallyQuantified(true)); | |
676 | let a_scope = self.create_scope(a, UniversallyQuantified(false)); | |
677 | ||
c295e0f8 XL |
678 | debug!(?a_scope, "(existential)"); |
679 | debug!(?b_scope, "(universal)"); | |
0bf4aa26 XL |
680 | |
681 | self.b_scopes.push(b_scope); | |
682 | self.a_scopes.push(a_scope); | |
683 | ||
684 | // Reset the ambient variance to covariant. This is needed | |
685 | // to correctly handle cases like | |
686 | // | |
f9f354fc | 687 | // for<'a> fn(&'a u32, &'a u32) == for<'b, 'c> fn(&'b u32, &'c u32) |
0bf4aa26 XL |
688 | // |
689 | // Somewhat surprisingly, these two types are actually | |
690 | // **equal**, even though the one on the right looks more | |
691 | // polymorphic. The reason is due to subtyping. To see it, | |
692 | // consider that each function can call the other: | |
693 | // | |
694 | // - The left function can call the right with `'b` and | |
695 | // `'c` both equal to `'a` | |
696 | // | |
697 | // - The right function can call the left with `'a` set to | |
698 | // `{P}`, where P is the point in the CFG where the call | |
699 | // itself occurs. Note that `'b` and `'c` must both | |
700 | // include P. At the point, the call works because of | |
701 | // subtyping (i.e., `&'b u32 <: &{P} u32`). | |
29967ef6 | 702 | let variance = std::mem::replace(&mut self.ambient_variance, ty::Variance::Covariant); |
0bf4aa26 XL |
703 | |
704 | self.relate(a.skip_binder(), b.skip_binder())?; | |
705 | ||
706 | self.ambient_variance = variance; | |
707 | ||
708 | self.b_scopes.pop().unwrap(); | |
709 | self.a_scopes.pop().unwrap(); | |
710 | } | |
711 | ||
712 | if self.ambient_contravariance() { | |
713 | // Contravariance, so we want `for<..> A :> for<..> B` | |
714 | // -- therefore we compare every instantiation of A (i.e., | |
715 | // A instantiated with universals) against any | |
716 | // instantiation of B (i.e., B instantiated with | |
717 | // existentials). Opposite of above. | |
718 | ||
719 | let a_scope = self.create_scope(a, UniversallyQuantified(true)); | |
720 | let b_scope = self.create_scope(b, UniversallyQuantified(false)); | |
721 | ||
c295e0f8 XL |
722 | debug!(?a_scope, "(universal)"); |
723 | debug!(?b_scope, "(existential)"); | |
0bf4aa26 XL |
724 | |
725 | self.a_scopes.push(a_scope); | |
726 | self.b_scopes.push(b_scope); | |
727 | ||
728 | // Reset ambient variance to contravariance. See the | |
729 | // covariant case above for an explanation. | |
730 | let variance = | |
29967ef6 | 731 | std::mem::replace(&mut self.ambient_variance, ty::Variance::Contravariant); |
0bf4aa26 XL |
732 | |
733 | self.relate(a.skip_binder(), b.skip_binder())?; | |
734 | ||
735 | self.ambient_variance = variance; | |
736 | ||
737 | self.b_scopes.pop().unwrap(); | |
738 | self.a_scopes.pop().unwrap(); | |
739 | } | |
740 | ||
3dfed10e | 741 | Ok(a) |
0bf4aa26 XL |
742 | } |
743 | } | |
744 | ||
f9f354fc XL |
745 | impl<'tcx, D> ConstEquateRelation<'tcx> for TypeRelating<'_, 'tcx, D> |
746 | where | |
747 | D: TypeRelatingDelegate<'tcx>, | |
748 | { | |
749 | fn const_equate_obligation(&mut self, a: &'tcx ty::Const<'tcx>, b: &'tcx ty::Const<'tcx>) { | |
750 | self.delegate.const_equate(a, b); | |
751 | } | |
752 | } | |
753 | ||
0bf4aa26 XL |
754 | /// When we encounter a binder like `for<..> fn(..)`, we actually have |
755 | /// to walk the `fn` value to find all the values bound by the `for` | |
756 | /// (these are not explicitly present in the ty representation right | |
757 | /// now). This visitor handles that: it descends the type, tracking | |
758 | /// binder depth, and finds late-bound regions targeting the | |
759 | /// `for<..`>. For each of those, it creates an entry in | |
760 | /// `bound_region_scope`. | |
dc9dc135 | 761 | struct ScopeInstantiator<'me, 'tcx> { |
94222f64 | 762 | tcx: TyCtxt<'tcx>, |
0bf4aa26 XL |
763 | next_region: &'me mut dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx>, |
764 | // The debruijn index of the scope we are instantiating. | |
765 | target_index: ty::DebruijnIndex, | |
766 | bound_region_scope: &'me mut BoundRegionScope<'tcx>, | |
767 | } | |
768 | ||
769 | impl<'me, 'tcx> TypeVisitor<'tcx> for ScopeInstantiator<'me, 'tcx> { | |
94222f64 XL |
770 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> { |
771 | Some(self.tcx) | |
772 | } | |
773 | ||
fc512014 XL |
774 | fn visit_binder<T: TypeFoldable<'tcx>>( |
775 | &mut self, | |
cdc7bbd5 | 776 | t: &ty::Binder<'tcx, T>, |
fc512014 | 777 | ) -> ControlFlow<Self::BreakTy> { |
0bf4aa26 XL |
778 | self.target_index.shift_in(1); |
779 | t.super_visit_with(self); | |
780 | self.target_index.shift_out(1); | |
781 | ||
29967ef6 | 782 | ControlFlow::CONTINUE |
0bf4aa26 XL |
783 | } |
784 | ||
fc512014 | 785 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
dfeec247 | 786 | let ScopeInstantiator { bound_region_scope, next_region, .. } = self; |
0bf4aa26 XL |
787 | |
788 | match r { | |
789 | ty::ReLateBound(debruijn, br) if *debruijn == self.target_index => { | |
dfeec247 | 790 | bound_region_scope.map.entry(*br).or_insert_with(|| next_region(*br)); |
0bf4aa26 XL |
791 | } |
792 | ||
793 | _ => {} | |
794 | } | |
795 | ||
29967ef6 | 796 | ControlFlow::CONTINUE |
0bf4aa26 XL |
797 | } |
798 | } | |
799 | ||
6a06907d | 800 | /// The "type generalizer" is used when handling inference variables. |
0bf4aa26 XL |
801 | /// |
802 | /// The basic strategy for handling a constraint like `?A <: B` is to | |
803 | /// apply a "generalization strategy" to the type `B` -- this replaces | |
804 | /// all the lifetimes in the type `B` with fresh inference | |
805 | /// variables. (You can read more about the strategy in this [blog | |
806 | /// post].) | |
807 | /// | |
808 | /// As an example, if we had `?A <: &'x u32`, we would generalize `&'x | |
809 | /// u32` to `&'0 u32` where `'0` is a fresh variable. This becomes the | |
810 | /// value of `A`. Finally, we relate `&'0 u32 <: &'x u32`, which | |
811 | /// establishes `'0: 'x` as a constraint. | |
812 | /// | |
813 | /// As a side-effect of this generalization procedure, we also replace | |
814 | /// all the bound regions that we have traversed with concrete values, | |
815 | /// so that the resulting generalized type is independent from the | |
816 | /// scopes. | |
817 | /// | |
818 | /// [blog post]: https://is.gd/0hKvIr | |
dc9dc135 | 819 | struct TypeGeneralizer<'me, 'tcx, D> |
0bf4aa26 | 820 | where |
dc9dc135 | 821 | D: TypeRelatingDelegate<'tcx>, |
0bf4aa26 | 822 | { |
dc9dc135 | 823 | infcx: &'me InferCtxt<'me, 'tcx>, |
0bf4aa26 XL |
824 | |
825 | delegate: &'me mut D, | |
826 | ||
827 | /// After we generalize this type, we are going to relative it to | |
828 | /// some other type. What will be the variance at this point? | |
829 | ambient_variance: ty::Variance, | |
830 | ||
831 | first_free_index: ty::DebruijnIndex, | |
832 | ||
a1dfa0c6 XL |
833 | /// The vid of the type variable that is in the process of being |
834 | /// instantiated. If we find this within the value we are folding, | |
835 | /// that means we would have created a cyclic value. | |
836 | for_vid_sub_root: ty::TyVid, | |
837 | ||
838 | /// The universe of the type variable that is in the process of being | |
839 | /// instantiated. If we find anything that this universe cannot name, | |
840 | /// we reject the relation. | |
0bf4aa26 XL |
841 | universe: ty::UniverseIndex, |
842 | } | |
843 | ||
dc9dc135 | 844 | impl<D> TypeRelation<'tcx> for TypeGeneralizer<'me, 'tcx, D> |
0bf4aa26 XL |
845 | where |
846 | D: TypeRelatingDelegate<'tcx>, | |
847 | { | |
dc9dc135 | 848 | fn tcx(&self) -> TyCtxt<'tcx> { |
a1dfa0c6 | 849 | self.infcx.tcx |
0bf4aa26 XL |
850 | } |
851 | ||
dfeec247 | 852 | fn param_env(&self) -> ty::ParamEnv<'tcx> { |
6a06907d | 853 | self.delegate.param_env() |
dfeec247 | 854 | } |
416331ca | 855 | |
0bf4aa26 XL |
856 | fn tag(&self) -> &'static str { |
857 | "nll::generalizer" | |
858 | } | |
859 | ||
860 | fn a_is_expected(&self) -> bool { | |
861 | true | |
862 | } | |
863 | ||
864 | fn relate_with_variance<T: Relate<'tcx>>( | |
865 | &mut self, | |
866 | variance: ty::Variance, | |
17df50a5 | 867 | _info: ty::VarianceDiagInfo<'tcx>, |
f035d41b XL |
868 | a: T, |
869 | b: T, | |
0bf4aa26 XL |
870 | ) -> RelateResult<'tcx, T> { |
871 | debug!( | |
872 | "TypeGeneralizer::relate_with_variance(variance={:?}, a={:?}, b={:?})", | |
873 | variance, a, b | |
874 | ); | |
875 | ||
876 | let old_ambient_variance = self.ambient_variance; | |
877 | self.ambient_variance = self.ambient_variance.xform(variance); | |
878 | ||
879 | debug!( | |
880 | "TypeGeneralizer::relate_with_variance: ambient_variance = {:?}", | |
881 | self.ambient_variance | |
882 | ); | |
883 | ||
884 | let r = self.relate(a, b)?; | |
885 | ||
886 | self.ambient_variance = old_ambient_variance; | |
887 | ||
888 | debug!("TypeGeneralizer::relate_with_variance: r={:?}", r); | |
889 | ||
890 | Ok(r) | |
891 | } | |
892 | ||
893 | fn tys(&mut self, a: Ty<'tcx>, _: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { | |
a1dfa0c6 XL |
894 | use crate::infer::type_variable::TypeVariableValue; |
895 | ||
48663c56 | 896 | debug!("TypeGeneralizer::tys(a={:?})", a); |
0bf4aa26 | 897 | |
1b1a35ee | 898 | match *a.kind() { |
a1dfa0c6 XL |
899 | ty::Infer(ty::TyVar(_)) | ty::Infer(ty::IntVar(_)) | ty::Infer(ty::FloatVar(_)) |
900 | if D::forbid_inference_vars() => | |
901 | { | |
dfeec247 | 902 | bug!("unexpected inference variable encountered in NLL generalization: {:?}", a); |
0bf4aa26 XL |
903 | } |
904 | ||
a1dfa0c6 | 905 | ty::Infer(ty::TyVar(vid)) => { |
f9f354fc XL |
906 | let mut inner = self.infcx.inner.borrow_mut(); |
907 | let variables = &mut inner.type_variables(); | |
a1dfa0c6 XL |
908 | let vid = variables.root_var(vid); |
909 | let sub_vid = variables.sub_root_var(vid); | |
910 | if sub_vid == self.for_vid_sub_root { | |
911 | // If sub-roots are equal, then `for_vid` and | |
912 | // `vid` are related via subtyping. | |
913 | debug!("TypeGeneralizer::tys: occurs check failed"); | |
ba9703b0 | 914 | Err(TypeError::Mismatch) |
a1dfa0c6 XL |
915 | } else { |
916 | match variables.probe(vid) { | |
917 | TypeVariableValue::Known { value: u } => { | |
918 | drop(variables); | |
f035d41b | 919 | self.relate(u, u) |
a1dfa0c6 | 920 | } |
dfeec247 | 921 | TypeVariableValue::Unknown { universe: _universe } => { |
a1dfa0c6 XL |
922 | if self.ambient_variance == ty::Bivariant { |
923 | // FIXME: we may need a WF predicate (related to #54105). | |
924 | } | |
925 | ||
926 | let origin = *variables.var_origin(vid); | |
927 | ||
928 | // Replacing with a new variable in the universe `self.universe`, | |
929 | // it will be unified later with the original type variable in | |
930 | // the universe `_universe`. | |
c295e0f8 | 931 | let new_var_id = variables.new_var(self.universe, origin); |
a1dfa0c6 | 932 | |
532ac7d7 | 933 | let u = self.tcx().mk_ty_var(new_var_id); |
dfeec247 | 934 | debug!("generalize: replacing original vid={:?} with new={:?}", vid, u); |
ba9703b0 | 935 | Ok(u) |
a1dfa0c6 XL |
936 | } |
937 | } | |
938 | } | |
939 | } | |
940 | ||
ba9703b0 | 941 | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => { |
a1dfa0c6 XL |
942 | // No matter what mode we are in, |
943 | // integer/floating-point types must be equal to be | |
944 | // relatable. | |
945 | Ok(a) | |
946 | } | |
947 | ||
948 | ty::Placeholder(placeholder) => { | |
949 | if self.universe.cannot_name(placeholder.universe) { | |
950 | debug!( | |
951 | "TypeGeneralizer::tys: root universe {:?} cannot name\ | |
532ac7d7 XL |
952 | placeholder in universe {:?}", |
953 | self.universe, placeholder.universe | |
a1dfa0c6 XL |
954 | ); |
955 | Err(TypeError::Mismatch) | |
956 | } else { | |
957 | Ok(a) | |
958 | } | |
959 | } | |
960 | ||
532ac7d7 | 961 | _ => relate::super_relate_tys(self, a, a), |
0bf4aa26 XL |
962 | } |
963 | } | |
964 | ||
965 | fn regions( | |
966 | &mut self, | |
967 | a: ty::Region<'tcx>, | |
968 | _: ty::Region<'tcx>, | |
969 | ) -> RelateResult<'tcx, ty::Region<'tcx>> { | |
48663c56 | 970 | debug!("TypeGeneralizer::regions(a={:?})", a); |
0bf4aa26 XL |
971 | |
972 | if let ty::ReLateBound(debruijn, _) = a { | |
973 | if *debruijn < self.first_free_index { | |
974 | return Ok(a); | |
975 | } | |
976 | } | |
977 | ||
978 | // For now, we just always create a fresh region variable to | |
979 | // replace all the regions in the source type. In the main | |
980 | // type checker, we special case the case where the ambient | |
981 | // variance is `Invariant` and try to avoid creating a fresh | |
982 | // region variable, but since this comes up so much less in | |
983 | // NLL (only when users use `_` etc) it is much less | |
984 | // important. | |
985 | // | |
986 | // As an aside, since these new variables are created in | |
987 | // `self.universe` universe, this also serves to enforce the | |
988 | // universe scoping rules. | |
989 | // | |
990 | // FIXME(#54105) -- if the ambient variance is bivariant, | |
991 | // though, we may however need to check well-formedness or | |
992 | // risk a problem like #41677 again. | |
993 | ||
994 | let replacement_region_vid = self.delegate.generalize_existential(self.universe); | |
995 | ||
996 | Ok(replacement_region_vid) | |
997 | } | |
998 | ||
48663c56 XL |
999 | fn consts( |
1000 | &mut self, | |
1001 | a: &'tcx ty::Const<'tcx>, | |
1002 | _: &'tcx ty::Const<'tcx>, | |
1003 | ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> { | |
e74abb32 | 1004 | match a.val { |
60c5eb7d | 1005 | ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => { |
dfeec247 | 1006 | bug!("unexpected inference variable encountered in NLL generalization: {:?}", a); |
e74abb32 | 1007 | } |
60c5eb7d | 1008 | ty::ConstKind::Infer(InferConst::Var(vid)) => { |
f9f354fc XL |
1009 | let mut inner = self.infcx.inner.borrow_mut(); |
1010 | let variable_table = &mut inner.const_unification_table(); | |
e74abb32 XL |
1011 | let var_value = variable_table.probe_value(vid); |
1012 | match var_value.val.known() { | |
f035d41b | 1013 | Some(u) => self.relate(u, u), |
e74abb32 XL |
1014 | None => { |
1015 | let new_var_id = variable_table.new_key(ConstVarValue { | |
1016 | origin: var_value.origin, | |
1017 | val: ConstVariableValue::Unknown { universe: self.universe }, | |
1018 | }); | |
1019 | Ok(self.tcx().mk_const_var(new_var_id, a.ty)) | |
1020 | } | |
1021 | } | |
1022 | } | |
f9f354fc | 1023 | ty::ConstKind::Unevaluated(..) if self.tcx().lazy_normalization() => Ok(a), |
e74abb32 | 1024 | _ => relate::super_relate_consts(self, a, a), |
48663c56 XL |
1025 | } |
1026 | } | |
1027 | ||
0bf4aa26 XL |
1028 | fn binders<T>( |
1029 | &mut self, | |
cdc7bbd5 XL |
1030 | a: ty::Binder<'tcx, T>, |
1031 | _: ty::Binder<'tcx, T>, | |
1032 | ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> | |
0bf4aa26 XL |
1033 | where |
1034 | T: Relate<'tcx>, | |
1035 | { | |
48663c56 | 1036 | debug!("TypeGeneralizer::binders(a={:?})", a); |
0bf4aa26 XL |
1037 | |
1038 | self.first_free_index.shift_in(1); | |
1039 | let result = self.relate(a.skip_binder(), a.skip_binder())?; | |
1040 | self.first_free_index.shift_out(1); | |
fc512014 | 1041 | Ok(a.rebind(result)) |
0bf4aa26 XL |
1042 | } |
1043 | } |