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