]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | /////////////////////////////////////////////////////////////////////////// |
2 | // # Type combining | |
3 | // | |
4 | // There are four type combiners: equate, sub, lub, and glb. Each | |
5 | // implements the trait `Combine` and contains methods for combining | |
6 | // two instances of various things and yielding a new instance. These | |
7 | // combiner methods always yield a `Result<T>`. There is a lot of | |
8 | // common code for these operations, implemented as default methods on | |
9 | // the `Combine` trait. | |
10 | // | |
11 | // Each operation may have side-effects on the inference context, | |
12 | // though these can be unrolled using snapshots. On success, the | |
13 | // LUB/GLB operations return the appropriate bound. The Eq and Sub | |
14 | // operations generally return the first operand. | |
15 | // | |
16 | // ## Contravariance | |
17 | // | |
18 | // When you are relating two things which have a contravariant | |
19 | // relationship, you should use `contratys()` or `contraregions()`, | |
20 | // rather than inversing the order of arguments! This is necessary | |
21 | // because the order of arguments is not relevant for LUB and GLB. It | |
22 | // is also useful to track which value is the "expected" value in | |
23 | // terms of error reporting. | |
24 | ||
25 | use super::equate::Equate; | |
26 | use super::glb::Glb; | |
27 | use super::lub::Lub; | |
28 | use super::sub::Sub; | |
0531ce1d | 29 | use super::type_variable::TypeVariableValue; |
dfeec247 | 30 | use super::unify_key::replace_if_possible; |
dc9dc135 XL |
31 | use super::unify_key::{ConstVarValue, ConstVariableValue}; |
32 | use super::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; | |
dfeec247 | 33 | use super::{InferCtxt, MiscVariable, TypeTrace}; |
1a4d82fc | 34 | |
dfeec247 | 35 | use crate::traits::{Obligation, PredicateObligations}; |
1a4d82fc | 36 | |
74b04a01 | 37 | use rustc_ast::ast; |
dfeec247 | 38 | use rustc_hir::def_id::DefId; |
ba9703b0 XL |
39 | use rustc_middle::ty::error::TypeError; |
40 | use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation}; | |
41 | use rustc_middle::ty::subst::SubstsRef; | |
42 | use rustc_middle::ty::{self, InferConst, Ty, TyCtxt}; | |
43 | use rustc_middle::ty::{IntType, UintType}; | |
dfeec247 | 44 | use rustc_span::{Span, DUMMY_SP}; |
1a4d82fc | 45 | |
1a4d82fc | 46 | #[derive(Clone)] |
dc9dc135 XL |
47 | pub struct CombineFields<'infcx, 'tcx> { |
48 | pub infcx: &'infcx InferCtxt<'infcx, 'tcx>, | |
1a4d82fc | 49 | pub trace: TypeTrace<'tcx>, |
e9174d1e | 50 | pub cause: Option<ty::relate::Cause>, |
7cac9316 | 51 | pub param_env: ty::ParamEnv<'tcx>, |
54a0048b | 52 | pub obligations: PredicateObligations<'tcx>, |
1a4d82fc JJ |
53 | } |
54 | ||
e74abb32 | 55 | #[derive(Copy, Clone, Debug)] |
cc61c64b | 56 | pub enum RelationDir { |
dfeec247 XL |
57 | SubtypeOf, |
58 | SupertypeOf, | |
59 | EqTo, | |
cc61c64b XL |
60 | } |
61 | ||
dc9dc135 XL |
62 | impl<'infcx, 'tcx> InferCtxt<'infcx, 'tcx> { |
63 | pub fn super_combine_tys<R>( | |
64 | &self, | |
65 | relation: &mut R, | |
66 | a: Ty<'tcx>, | |
67 | b: Ty<'tcx>, | |
68 | ) -> RelateResult<'tcx, Ty<'tcx>> | |
69 | where | |
70 | R: TypeRelation<'tcx>, | |
a7813a04 XL |
71 | { |
72 | let a_is_expected = relation.a_is_expected(); | |
1a4d82fc | 73 | |
e74abb32 | 74 | match (&a.kind, &b.kind) { |
a7813a04 | 75 | // Relate integral variables to other types |
b7449926 | 76 | (&ty::Infer(ty::IntVar(a_id)), &ty::Infer(ty::IntVar(b_id))) => { |
74b04a01 | 77 | self.inner |
a7813a04 | 78 | .borrow_mut() |
74b04a01 | 79 | .int_unification_table |
a7813a04 XL |
80 | .unify_var_var(a_id, b_id) |
81 | .map_err(|e| int_unification_error(a_is_expected, e))?; | |
82 | Ok(a) | |
83 | } | |
b7449926 | 84 | (&ty::Infer(ty::IntVar(v_id)), &ty::Int(v)) => { |
a7813a04 XL |
85 | self.unify_integral_variable(a_is_expected, v_id, IntType(v)) |
86 | } | |
b7449926 | 87 | (&ty::Int(v), &ty::Infer(ty::IntVar(v_id))) => { |
a7813a04 XL |
88 | self.unify_integral_variable(!a_is_expected, v_id, IntType(v)) |
89 | } | |
b7449926 | 90 | (&ty::Infer(ty::IntVar(v_id)), &ty::Uint(v)) => { |
a7813a04 XL |
91 | self.unify_integral_variable(a_is_expected, v_id, UintType(v)) |
92 | } | |
b7449926 | 93 | (&ty::Uint(v), &ty::Infer(ty::IntVar(v_id))) => { |
a7813a04 XL |
94 | self.unify_integral_variable(!a_is_expected, v_id, UintType(v)) |
95 | } | |
1a4d82fc | 96 | |
a7813a04 | 97 | // Relate floating-point variables to other types |
b7449926 | 98 | (&ty::Infer(ty::FloatVar(a_id)), &ty::Infer(ty::FloatVar(b_id))) => { |
74b04a01 | 99 | self.inner |
a7813a04 | 100 | .borrow_mut() |
74b04a01 | 101 | .float_unification_table |
a7813a04 XL |
102 | .unify_var_var(a_id, b_id) |
103 | .map_err(|e| float_unification_error(relation.a_is_expected(), e))?; | |
104 | Ok(a) | |
105 | } | |
b7449926 | 106 | (&ty::Infer(ty::FloatVar(v_id)), &ty::Float(v)) => { |
a7813a04 XL |
107 | self.unify_float_variable(a_is_expected, v_id, v) |
108 | } | |
b7449926 | 109 | (&ty::Float(v), &ty::Infer(ty::FloatVar(v_id))) => { |
a7813a04 XL |
110 | self.unify_float_variable(!a_is_expected, v_id, v) |
111 | } | |
1a4d82fc | 112 | |
a7813a04 | 113 | // All other cases of inference are errors |
dfeec247 | 114 | (&ty::Infer(_), _) | (_, &ty::Infer(_)) => { |
a7813a04 XL |
115 | Err(TypeError::Sorts(ty::relate::expected_found(relation, &a, &b))) |
116 | } | |
1a4d82fc | 117 | |
dfeec247 | 118 | _ => ty::relate::super_relate_tys(relation, a, b), |
1a4d82fc JJ |
119 | } |
120 | } | |
121 | ||
48663c56 XL |
122 | pub fn super_combine_consts<R>( |
123 | &self, | |
124 | relation: &mut R, | |
125 | a: &'tcx ty::Const<'tcx>, | |
126 | b: &'tcx ty::Const<'tcx>, | |
127 | ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> | |
128 | where | |
dc9dc135 | 129 | R: TypeRelation<'tcx>, |
48663c56 | 130 | { |
e1599b0c | 131 | debug!("{}.consts({:?}, {:?})", relation.tag(), a, b); |
dfeec247 XL |
132 | if a == b { |
133 | return Ok(a); | |
134 | } | |
e1599b0c | 135 | |
74b04a01 XL |
136 | let a = replace_if_possible(&mut self.inner.borrow_mut().const_unification_table, a); |
137 | let b = replace_if_possible(&mut self.inner.borrow_mut().const_unification_table, b); | |
e1599b0c | 138 | |
48663c56 XL |
139 | let a_is_expected = relation.a_is_expected(); |
140 | ||
141 | match (a.val, b.val) { | |
dfeec247 XL |
142 | ( |
143 | ty::ConstKind::Infer(InferConst::Var(a_vid)), | |
144 | ty::ConstKind::Infer(InferConst::Var(b_vid)), | |
145 | ) => { | |
74b04a01 | 146 | self.inner |
48663c56 | 147 | .borrow_mut() |
74b04a01 | 148 | .const_unification_table |
48663c56 XL |
149 | .unify_var_var(a_vid, b_vid) |
150 | .map_err(|e| const_unification_error(a_is_expected, e))?; | |
151 | return Ok(a); | |
152 | } | |
153 | ||
154 | // All other cases of inference with other variables are errors. | |
dfeec247 XL |
155 | (ty::ConstKind::Infer(InferConst::Var(_)), ty::ConstKind::Infer(_)) |
156 | | (ty::ConstKind::Infer(_), ty::ConstKind::Infer(InferConst::Var(_))) => { | |
60c5eb7d | 157 | bug!("tried to combine ConstKind::Infer/ConstKind::Infer(InferConst::Var)") |
48663c56 XL |
158 | } |
159 | ||
60c5eb7d | 160 | (ty::ConstKind::Infer(InferConst::Var(vid)), _) => { |
48663c56 XL |
161 | return self.unify_const_variable(a_is_expected, vid, b); |
162 | } | |
163 | ||
60c5eb7d | 164 | (_, ty::ConstKind::Infer(InferConst::Var(vid))) => { |
48663c56 XL |
165 | return self.unify_const_variable(!a_is_expected, vid, a); |
166 | } | |
167 | ||
168 | _ => {} | |
169 | } | |
170 | ||
171 | ty::relate::super_relate_consts(relation, a, b) | |
172 | } | |
173 | ||
174 | pub fn unify_const_variable( | |
175 | &self, | |
176 | vid_is_expected: bool, | |
177 | vid: ty::ConstVid<'tcx>, | |
178 | value: &'tcx ty::Const<'tcx>, | |
179 | ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> { | |
74b04a01 | 180 | self.inner |
48663c56 | 181 | .borrow_mut() |
74b04a01 | 182 | .const_unification_table |
dfeec247 XL |
183 | .unify_var_value( |
184 | vid, | |
185 | ConstVarValue { | |
186 | origin: ConstVariableOrigin { | |
187 | kind: ConstVariableOriginKind::ConstInference, | |
188 | span: DUMMY_SP, | |
189 | }, | |
190 | val: ConstVariableValue::Known { value }, | |
dc9dc135 | 191 | }, |
dfeec247 | 192 | ) |
48663c56 XL |
193 | .map_err(|e| const_unification_error(vid_is_expected, e))?; |
194 | Ok(value) | |
195 | } | |
196 | ||
dfeec247 XL |
197 | fn unify_integral_variable( |
198 | &self, | |
199 | vid_is_expected: bool, | |
200 | vid: ty::IntVid, | |
201 | val: ty::IntVarValue, | |
202 | ) -> RelateResult<'tcx, Ty<'tcx>> { | |
74b04a01 | 203 | self.inner |
a7813a04 | 204 | .borrow_mut() |
74b04a01 | 205 | .int_unification_table |
0531ce1d | 206 | .unify_var_value(vid, Some(val)) |
a7813a04 XL |
207 | .map_err(|e| int_unification_error(vid_is_expected, e))?; |
208 | match val { | |
209 | IntType(v) => Ok(self.tcx.mk_mach_int(v)), | |
210 | UintType(v) => Ok(self.tcx.mk_mach_uint(v)), | |
211 | } | |
1a4d82fc | 212 | } |
1a4d82fc | 213 | |
dfeec247 XL |
214 | fn unify_float_variable( |
215 | &self, | |
216 | vid_is_expected: bool, | |
217 | vid: ty::FloatVid, | |
218 | val: ast::FloatTy, | |
219 | ) -> RelateResult<'tcx, Ty<'tcx>> { | |
74b04a01 | 220 | self.inner |
a7813a04 | 221 | .borrow_mut() |
74b04a01 | 222 | .float_unification_table |
0531ce1d | 223 | .unify_var_value(vid, Some(ty::FloatVarValue(val))) |
a7813a04 XL |
224 | .map_err(|e| float_unification_error(vid_is_expected, e))?; |
225 | Ok(self.tcx.mk_mach_float(val)) | |
226 | } | |
c34b1796 AL |
227 | } |
228 | ||
dc9dc135 XL |
229 | impl<'infcx, 'tcx> CombineFields<'infcx, 'tcx> { |
230 | pub fn tcx(&self) -> TyCtxt<'tcx> { | |
c34b1796 AL |
231 | self.infcx.tcx |
232 | } | |
233 | ||
dc9dc135 | 234 | pub fn equate<'a>(&'a mut self, a_is_expected: bool) -> Equate<'a, 'infcx, 'tcx> { |
5bcae85e | 235 | Equate::new(self, a_is_expected) |
1a4d82fc JJ |
236 | } |
237 | ||
dc9dc135 | 238 | pub fn sub<'a>(&'a mut self, a_is_expected: bool) -> Sub<'a, 'infcx, 'tcx> { |
5bcae85e | 239 | Sub::new(self, a_is_expected) |
c34b1796 AL |
240 | } |
241 | ||
dc9dc135 | 242 | pub fn lub<'a>(&'a mut self, a_is_expected: bool) -> Lub<'a, 'infcx, 'tcx> { |
5bcae85e | 243 | Lub::new(self, a_is_expected) |
c34b1796 AL |
244 | } |
245 | ||
dc9dc135 | 246 | pub fn glb<'a>(&'a mut self, a_is_expected: bool) -> Glb<'a, 'infcx, 'tcx> { |
5bcae85e | 247 | Glb::new(self, a_is_expected) |
1a4d82fc JJ |
248 | } |
249 | ||
9fa01778 XL |
250 | /// Here, `dir` is either `EqTo`, `SubtypeOf`, or `SupertypeOf`. |
251 | /// The idea is that we should ensure that the type `a_ty` is equal | |
cc61c64b XL |
252 | /// to, a subtype of, or a supertype of (respectively) the type |
253 | /// to which `b_vid` is bound. | |
254 | /// | |
255 | /// Since `b_vid` has not yet been instantiated with a type, we | |
256 | /// will first instantiate `b_vid` with a *generalized* version | |
257 | /// of `a_ty`. Generalization introduces other inference | |
258 | /// variables wherever subtyping could occur. | |
dfeec247 XL |
259 | pub fn instantiate( |
260 | &mut self, | |
261 | a_ty: Ty<'tcx>, | |
262 | dir: RelationDir, | |
263 | b_vid: ty::TyVid, | |
264 | a_is_expected: bool, | |
265 | ) -> RelateResult<'tcx, ()> { | |
cc61c64b | 266 | use self::RelationDir::*; |
1a4d82fc | 267 | |
cc61c64b | 268 | // Get the actual variable that b_vid has been inferred to |
74b04a01 | 269 | debug_assert!(self.infcx.inner.borrow_mut().type_variables.probe(b_vid).is_unknown()); |
1a4d82fc | 270 | |
cc61c64b XL |
271 | debug!("instantiate(a_ty={:?} dir={:?} b_vid={:?})", a_ty, dir, b_vid); |
272 | ||
273 | // Generalize type of `a_ty` appropriately depending on the | |
274 | // direction. As an example, assume: | |
275 | // | |
276 | // - `a_ty == &'x ?1`, where `'x` is some free region and `?1` is an | |
277 | // inference variable, | |
278 | // - and `dir` == `SubtypeOf`. | |
279 | // | |
280 | // Then the generalized form `b_ty` would be `&'?2 ?3`, where | |
281 | // `'?2` and `?3` are fresh region/type inference | |
282 | // variables. (Down below, we will relate `a_ty <: b_ty`, | |
283 | // adding constraints like `'x: '?2` and `?1 <: ?3`.) | |
284 | let Generalization { ty: b_ty, needs_wf } = self.generalize(a_ty, b_vid, dir)?; | |
dfeec247 XL |
285 | debug!( |
286 | "instantiate(a_ty={:?}, dir={:?}, b_vid={:?}, generalized b_ty={:?})", | |
287 | a_ty, dir, b_vid, b_ty | |
288 | ); | |
74b04a01 | 289 | self.infcx.inner.borrow_mut().type_variables.instantiate(b_vid, b_ty); |
cc61c64b XL |
290 | |
291 | if needs_wf { | |
dfeec247 XL |
292 | self.obligations.push(Obligation::new( |
293 | self.trace.cause.clone(), | |
294 | self.param_env, | |
295 | ty::Predicate::WellFormed(b_ty), | |
296 | )); | |
1a4d82fc JJ |
297 | } |
298 | ||
cc61c64b XL |
299 | // Finally, relate `b_ty` to `a_ty`, as described in previous comment. |
300 | // | |
301 | // FIXME(#16847): This code is non-ideal because all these subtype | |
302 | // relations wind up attributed to the same spans. We need | |
303 | // to associate causes/spans with each of the relations in | |
304 | // the stack to get this right. | |
305 | match dir { | |
306 | EqTo => self.equate(a_is_expected).relate(&a_ty, &b_ty), | |
307 | SubtypeOf => self.sub(a_is_expected).relate(&a_ty, &b_ty), | |
dfeec247 XL |
308 | SupertypeOf => { |
309 | self.sub(a_is_expected).relate_with_variance(ty::Contravariant, &a_ty, &b_ty) | |
310 | } | |
cc61c64b XL |
311 | }?; |
312 | ||
1a4d82fc JJ |
313 | Ok(()) |
314 | } | |
315 | ||
cc61c64b XL |
316 | /// Attempts to generalize `ty` for the type variable `for_vid`. |
317 | /// This checks for cycle -- that is, whether the type `ty` | |
318 | /// references `for_vid`. The `dir` is the "direction" for which we | |
319 | /// a performing the generalization (i.e., are we producing a type | |
320 | /// that can be used as a supertype etc). | |
321 | /// | |
322 | /// Preconditions: | |
323 | /// | |
324 | /// - `for_vid` is a "root vid" | |
dfeec247 XL |
325 | fn generalize( |
326 | &self, | |
327 | ty: Ty<'tcx>, | |
328 | for_vid: ty::TyVid, | |
329 | dir: RelationDir, | |
330 | ) -> RelateResult<'tcx, Generalization<'tcx>> { | |
13cf67c4 | 331 | debug!("generalize(ty={:?}, for_vid={:?}, dir={:?}", ty, for_vid, dir); |
cc61c64b XL |
332 | // Determine the ambient variance within which `ty` appears. |
333 | // The surrounding equation is: | |
334 | // | |
335 | // ty [op] ty2 | |
336 | // | |
337 | // where `op` is either `==`, `<:`, or `:>`. This maps quite | |
338 | // naturally. | |
339 | let ambient_variance = match dir { | |
340 | RelationDir::EqTo => ty::Invariant, | |
341 | RelationDir::SubtypeOf => ty::Covariant, | |
342 | RelationDir::SupertypeOf => ty::Contravariant, | |
343 | }; | |
344 | ||
0731742a XL |
345 | debug!("generalize: ambient_variance = {:?}", ambient_variance); |
346 | ||
74b04a01 | 347 | let for_universe = match self.infcx.inner.borrow_mut().type_variables.probe(for_vid) { |
dfeec247 XL |
348 | v @ TypeVariableValue::Known { .. } => { |
349 | panic!("instantiating {:?} which has a known value {:?}", for_vid, v,) | |
350 | } | |
0731742a XL |
351 | TypeVariableValue::Unknown { universe } => universe, |
352 | }; | |
353 | ||
354 | debug!("generalize: for_universe = {:?}", for_universe); | |
355 | ||
c34b1796 AL |
356 | let mut generalize = Generalizer { |
357 | infcx: self.infcx, | |
476ff2be | 358 | span: self.trace.cause.span, |
74b04a01 | 359 | for_vid_sub_root: self.infcx.inner.borrow_mut().type_variables.sub_root_var(for_vid), |
0731742a | 360 | for_universe, |
041b39d2 | 361 | ambient_variance, |
cc61c64b | 362 | needs_wf: false, |
ff7c6d11 | 363 | root_ty: ty, |
416331ca | 364 | param_env: self.param_env, |
c34b1796 | 365 | }; |
cc61c64b | 366 | |
13cf67c4 XL |
367 | let ty = match generalize.relate(&ty, &ty) { |
368 | Ok(ty) => ty, | |
369 | Err(e) => { | |
370 | debug!("generalize: failure {:?}", e); | |
371 | return Err(e); | |
372 | } | |
373 | }; | |
cc61c64b | 374 | let needs_wf = generalize.needs_wf; |
13cf67c4 | 375 | debug!("generalize: success {{ {:?}, {:?} }}", ty, needs_wf); |
cc61c64b | 376 | Ok(Generalization { ty, needs_wf }) |
1a4d82fc JJ |
377 | } |
378 | } | |
379 | ||
dc9dc135 XL |
380 | struct Generalizer<'cx, 'tcx> { |
381 | infcx: &'cx InferCtxt<'cx, 'tcx>, | |
ff7c6d11 | 382 | |
9fa01778 | 383 | /// The span, used when creating new type variables and things. |
1a4d82fc | 384 | span: Span, |
ff7c6d11 XL |
385 | |
386 | /// The vid of the type variable that is in the process of being | |
387 | /// instantiated; if we find this within the type we are folding, | |
388 | /// that means we would have created a cyclic type. | |
cc61c64b | 389 | for_vid_sub_root: ty::TyVid, |
ff7c6d11 | 390 | |
0731742a XL |
391 | /// The universe of the type variable that is in the process of |
392 | /// being instantiated. Any fresh variables that we create in this | |
393 | /// process should be in that same universe. | |
394 | for_universe: ty::UniverseIndex, | |
395 | ||
ff7c6d11 | 396 | /// Track the variance as we descend into the type. |
cc61c64b | 397 | ambient_variance: ty::Variance, |
ff7c6d11 XL |
398 | |
399 | /// See the field `needs_wf` in `Generalization`. | |
400 | needs_wf: bool, | |
401 | ||
402 | /// The root type that we are generalizing. Used when reporting cycles. | |
403 | root_ty: Ty<'tcx>, | |
416331ca XL |
404 | |
405 | param_env: ty::ParamEnv<'tcx>, | |
cc61c64b XL |
406 | } |
407 | ||
408 | /// Result from a generalization operation. This includes | |
409 | /// not only the generalized type, but also a bool flag | |
83c7162d | 410 | /// indicating whether further WF checks are needed. |
cc61c64b XL |
411 | struct Generalization<'tcx> { |
412 | ty: Ty<'tcx>, | |
413 | ||
414 | /// If true, then the generalized type may not be well-formed, | |
415 | /// even if the source type is well-formed, so we should add an | |
416 | /// additional check to enforce that it is. This arises in | |
417 | /// particular around 'bivariant' type parameters that are only | |
418 | /// constrained by a where-clause. As an example, imagine a type: | |
419 | /// | |
9fa01778 | 420 | /// struct Foo<A, B> where A: Iterator<Item = B> { |
cc61c64b XL |
421 | /// data: A |
422 | /// } | |
423 | /// | |
424 | /// here, `A` will be covariant, but `B` is | |
425 | /// unconstrained. However, whatever it is, for `Foo` to be WF, it | |
426 | /// must be equal to `A::Item`. If we have an input `Foo<?A, ?B>`, | |
427 | /// then after generalization we will wind up with a type like | |
428 | /// `Foo<?C, ?D>`. When we enforce that `Foo<?A, ?B> <: Foo<?C, | |
429 | /// ?D>` (or `>:`), we will wind up with the requirement that `?A | |
430 | /// <: ?C`, but no particular relationship between `?B` and `?D` | |
431 | /// (after all, we do not know the variance of the normalized form | |
432 | /// of `A::Item` with respect to `A`). If we do nothing else, this | |
9fa01778 | 433 | /// may mean that `?D` goes unconstrained (as in #41677). So, in |
cc61c64b XL |
434 | /// this scenario where we create a new type variable in a |
435 | /// bivariant context, we set the `needs_wf` flag to true. This | |
436 | /// will force the calling code to check that `WF(Foo<?C, ?D>)` | |
437 | /// holds, which in turn implies that `?C::Item == ?D`. So once | |
438 | /// `?C` is constrained, that should suffice to restrict `?D`. | |
439 | needs_wf: bool, | |
1a4d82fc JJ |
440 | } |
441 | ||
dc9dc135 XL |
442 | impl TypeRelation<'tcx> for Generalizer<'_, 'tcx> { |
443 | fn tcx(&self) -> TyCtxt<'tcx> { | |
1a4d82fc JJ |
444 | self.infcx.tcx |
445 | } | |
dfeec247 XL |
446 | fn param_env(&self) -> ty::ParamEnv<'tcx> { |
447 | self.param_env | |
448 | } | |
1a4d82fc | 449 | |
cc61c64b XL |
450 | fn tag(&self) -> &'static str { |
451 | "Generalizer" | |
452 | } | |
453 | ||
454 | fn a_is_expected(&self) -> bool { | |
455 | true | |
456 | } | |
457 | ||
dfeec247 XL |
458 | fn binders<T>( |
459 | &mut self, | |
460 | a: &ty::Binder<T>, | |
461 | b: &ty::Binder<T>, | |
462 | ) -> RelateResult<'tcx, ty::Binder<T>> | |
463 | where | |
464 | T: Relate<'tcx>, | |
cc61c64b | 465 | { |
83c7162d | 466 | Ok(ty::Binder::bind(self.relate(a.skip_binder(), b.skip_binder())?)) |
cc61c64b XL |
467 | } |
468 | ||
dfeec247 XL |
469 | fn relate_item_substs( |
470 | &mut self, | |
471 | item_def_id: DefId, | |
472 | a_subst: SubstsRef<'tcx>, | |
473 | b_subst: SubstsRef<'tcx>, | |
474 | ) -> RelateResult<'tcx, SubstsRef<'tcx>> { | |
cc61c64b XL |
475 | if self.ambient_variance == ty::Variance::Invariant { |
476 | // Avoid fetching the variance if we are in an invariant | |
477 | // context; no need, and it can induce dependency cycles | |
0731742a | 478 | // (e.g., #41849). |
cc61c64b XL |
479 | relate::relate_substs(self, None, a_subst, b_subst) |
480 | } else { | |
7cac9316 XL |
481 | let opt_variances = self.tcx().variances_of(item_def_id); |
482 | relate::relate_substs(self, Some(&opt_variances), a_subst, b_subst) | |
cc61c64b XL |
483 | } |
484 | } | |
485 | ||
dfeec247 XL |
486 | fn relate_with_variance<T: Relate<'tcx>>( |
487 | &mut self, | |
488 | variance: ty::Variance, | |
489 | a: &T, | |
490 | b: &T, | |
491 | ) -> RelateResult<'tcx, T> { | |
cc61c64b XL |
492 | let old_ambient_variance = self.ambient_variance; |
493 | self.ambient_variance = self.ambient_variance.xform(variance); | |
494 | ||
495 | let result = self.relate(a, b); | |
496 | self.ambient_variance = old_ambient_variance; | |
497 | result | |
498 | } | |
499 | ||
500 | fn tys(&mut self, t: Ty<'tcx>, t2: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { | |
501 | assert_eq!(t, t2); // we are abusing TypeRelation here; both LHS and RHS ought to be == | |
502 | ||
0731742a XL |
503 | debug!("generalize: t={:?}", t); |
504 | ||
48663c56 | 505 | // Check to see whether the type we are generalizing references |
cc61c64b XL |
506 | // any other type variable related to `vid` via |
507 | // subtyping. This is basically our "occurs check", preventing | |
508 | // us from creating infinitely sized types. | |
e74abb32 | 509 | match t.kind { |
b7449926 | 510 | ty::Infer(ty::TyVar(vid)) => { |
74b04a01 XL |
511 | let vid = self.infcx.inner.borrow_mut().type_variables.root_var(vid); |
512 | let sub_vid = self.infcx.inner.borrow_mut().type_variables.sub_root_var(vid); | |
cc61c64b XL |
513 | if sub_vid == self.for_vid_sub_root { |
514 | // If sub-roots are equal, then `for_vid` and | |
515 | // `vid` are related via subtyping. | |
e74abb32 | 516 | Err(TypeError::CyclicTy(self.root_ty)) |
1a4d82fc | 517 | } else { |
74b04a01 XL |
518 | let probe = self.infcx.inner.borrow_mut().type_variables.probe(vid); |
519 | match probe { | |
0531ce1d | 520 | TypeVariableValue::Known { value: u } => { |
0731742a | 521 | debug!("generalize: known value {:?}", u); |
cc61c64b XL |
522 | self.relate(&u, &u) |
523 | } | |
83c7162d | 524 | TypeVariableValue::Unknown { universe } => { |
cc61c64b XL |
525 | match self.ambient_variance { |
526 | // Invariant: no need to make a fresh type variable. | |
0731742a XL |
527 | ty::Invariant => { |
528 | if self.for_universe.can_name(universe) { | |
529 | return Ok(t); | |
530 | } | |
531 | } | |
cc61c64b XL |
532 | |
533 | // Bivariant: make a fresh var, but we | |
534 | // may need a WF predicate. See | |
535 | // comment on `needs_wf` field for | |
536 | // more info. | |
537 | ty::Bivariant => self.needs_wf = true, | |
538 | ||
539 | // Co/contravariant: this will be | |
540 | // sufficiently constrained later on. | |
541 | ty::Covariant | ty::Contravariant => (), | |
542 | } | |
543 | ||
74b04a01 XL |
544 | let origin = |
545 | *self.infcx.inner.borrow_mut().type_variables.var_origin(vid); | |
546 | let new_var_id = self.infcx.inner.borrow_mut().type_variables.new_var( | |
547 | self.for_universe, | |
548 | false, | |
549 | origin, | |
550 | ); | |
532ac7d7 | 551 | let u = self.tcx().mk_ty_var(new_var_id); |
dfeec247 | 552 | debug!("generalize: replacing original vid={:?} with new={:?}", vid, u); |
e74abb32 | 553 | Ok(u) |
54a0048b | 554 | } |
1a4d82fc JJ |
555 | } |
556 | } | |
557 | } | |
ba9703b0 | 558 | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => { |
cc61c64b XL |
559 | // No matter what mode we are in, |
560 | // integer/floating-point types must be equal to be | |
561 | // relatable. | |
562 | Ok(t) | |
563 | } | |
dfeec247 | 564 | _ => relate::super_relate_tys(self, t, t), |
1a4d82fc JJ |
565 | } |
566 | } | |
567 | ||
dfeec247 XL |
568 | fn regions( |
569 | &mut self, | |
570 | r: ty::Region<'tcx>, | |
571 | r2: ty::Region<'tcx>, | |
572 | ) -> RelateResult<'tcx, ty::Region<'tcx>> { | |
cc61c64b XL |
573 | assert_eq!(r, r2); // we are abusing TypeRelation here; both LHS and RHS ought to be == |
574 | ||
0731742a XL |
575 | debug!("generalize: regions r={:?}", r); |
576 | ||
9e0c209e | 577 | match *r { |
3157f602 XL |
578 | // Never make variables for regions bound within the type itself, |
579 | // nor for erased regions. | |
dfeec247 | 580 | ty::ReLateBound(..) | ty::ReErased => { |
cc61c64b XL |
581 | return Ok(r); |
582 | } | |
1a4d82fc | 583 | |
dfeec247 XL |
584 | ty::RePlaceholder(..) |
585 | | ty::ReVar(..) | |
74b04a01 | 586 | | ty::ReEmpty(_) |
dfeec247 XL |
587 | | ty::ReStatic |
588 | | ty::ReScope(..) | |
589 | | ty::ReEarlyBound(..) | |
590 | | ty::ReFree(..) => { | |
0731742a | 591 | // see common code below |
1a4d82fc | 592 | } |
0731742a | 593 | } |
ff7c6d11 | 594 | |
0731742a XL |
595 | // If we are in an invariant context, we can re-use the region |
596 | // as is, unless it happens to be in some universe that we | |
597 | // can't name. (In the case of a region *variable*, we could | |
598 | // use it if we promoted it into our universe, but we don't | |
599 | // bother.) | |
600 | if let ty::Invariant = self.ambient_variance { | |
601 | let r_universe = self.infcx.universe_of_region(r); | |
602 | if self.for_universe.can_name(r_universe) { | |
603 | return Ok(r); | |
ff7c6d11 | 604 | } |
1a4d82fc JJ |
605 | } |
606 | ||
607 | // FIXME: This is non-ideal because we don't give a | |
608 | // very descriptive origin for this region variable. | |
0731742a | 609 | Ok(self.infcx.next_region_var_in_universe(MiscVariable(self.span), self.for_universe)) |
1a4d82fc | 610 | } |
48663c56 XL |
611 | |
612 | fn consts( | |
613 | &mut self, | |
614 | c: &'tcx ty::Const<'tcx>, | |
dfeec247 | 615 | c2: &'tcx ty::Const<'tcx>, |
48663c56 XL |
616 | ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> { |
617 | assert_eq!(c, c2); // we are abusing TypeRelation here; both LHS and RHS ought to be == | |
618 | ||
e74abb32 | 619 | match c.val { |
60c5eb7d | 620 | ty::ConstKind::Infer(InferConst::Var(vid)) => { |
74b04a01 | 621 | let variable_table = &mut self.infcx.inner.borrow_mut().const_unification_table; |
e74abb32 XL |
622 | let var_value = variable_table.probe_value(vid); |
623 | match var_value.val { | |
624 | ConstVariableValue::Known { value: u } => self.relate(&u, &u), | |
625 | ConstVariableValue::Unknown { universe } => { | |
626 | if self.for_universe.can_name(universe) { | |
627 | Ok(c) | |
628 | } else { | |
629 | let new_var_id = variable_table.new_key(ConstVarValue { | |
630 | origin: var_value.origin, | |
631 | val: ConstVariableValue::Unknown { universe: self.for_universe }, | |
632 | }); | |
633 | Ok(self.tcx().mk_const_var(new_var_id, c.ty)) | |
634 | } | |
48663c56 | 635 | } |
48663c56 XL |
636 | } |
637 | } | |
e74abb32 | 638 | _ => relate::super_relate_consts(self, c, c), |
48663c56 XL |
639 | } |
640 | } | |
1a4d82fc | 641 | } |
c34b1796 AL |
642 | |
643 | pub trait RelateResultCompare<'tcx, T> { | |
dfeec247 XL |
644 | fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> |
645 | where | |
e9174d1e | 646 | F: FnOnce() -> TypeError<'tcx>; |
c34b1796 AL |
647 | } |
648 | ||
dfeec247 XL |
649 | impl<'tcx, T: Clone + PartialEq> RelateResultCompare<'tcx, T> for RelateResult<'tcx, T> { |
650 | fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> | |
651 | where | |
e9174d1e | 652 | F: FnOnce() -> TypeError<'tcx>, |
c34b1796 | 653 | { |
dfeec247 | 654 | self.clone().and_then(|s| if s == t { self.clone() } else { Err(f()) }) |
c34b1796 AL |
655 | } |
656 | } | |
657 | ||
48663c56 XL |
658 | pub fn const_unification_error<'tcx>( |
659 | a_is_expected: bool, | |
660 | (a, b): (&'tcx ty::Const<'tcx>, &'tcx ty::Const<'tcx>), | |
661 | ) -> TypeError<'tcx> { | |
662 | TypeError::ConstMismatch(ty::relate::expected_found_bool(a_is_expected, &a, &b)) | |
663 | } | |
664 | ||
dfeec247 XL |
665 | fn int_unification_error<'tcx>( |
666 | a_is_expected: bool, | |
667 | v: (ty::IntVarValue, ty::IntVarValue), | |
668 | ) -> TypeError<'tcx> { | |
c34b1796 | 669 | let (a, b) = v; |
e9174d1e | 670 | TypeError::IntMismatch(ty::relate::expected_found_bool(a_is_expected, &a, &b)) |
c34b1796 AL |
671 | } |
672 | ||
dfeec247 XL |
673 | fn float_unification_error<'tcx>( |
674 | a_is_expected: bool, | |
675 | v: (ty::FloatVarValue, ty::FloatVarValue), | |
676 | ) -> TypeError<'tcx> { | |
0531ce1d | 677 | let (ty::FloatVarValue(a), ty::FloatVarValue(b)) = v; |
e9174d1e | 678 | TypeError::FloatMismatch(ty::relate::expected_found_bool(a_is_expected, &a, &b)) |
c34b1796 | 679 | } |