]> git.proxmox.com Git - rustc.git/blame - src/librustc_infer/infer/combine.rs
New upstream version 1.44.1+dfsg1
[rustc.git] / src / librustc_infer / infer / combine.rs
CommitLineData
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
25use super::equate::Equate;
26use super::glb::Glb;
27use super::lub::Lub;
28use super::sub::Sub;
0531ce1d 29use super::type_variable::TypeVariableValue;
dfeec247 30use super::unify_key::replace_if_possible;
dc9dc135
XL
31use super::unify_key::{ConstVarValue, ConstVariableValue};
32use super::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
dfeec247 33use super::{InferCtxt, MiscVariable, TypeTrace};
1a4d82fc 34
dfeec247 35use crate::traits::{Obligation, PredicateObligations};
1a4d82fc 36
74b04a01 37use rustc_ast::ast;
dfeec247 38use rustc_hir::def_id::DefId;
ba9703b0
XL
39use rustc_middle::ty::error::TypeError;
40use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation};
41use rustc_middle::ty::subst::SubstsRef;
42use rustc_middle::ty::{self, InferConst, Ty, TyCtxt};
43use rustc_middle::ty::{IntType, UintType};
dfeec247 44use rustc_span::{Span, DUMMY_SP};
1a4d82fc 45
1a4d82fc 46#[derive(Clone)]
dc9dc135
XL
47pub 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 56pub enum RelationDir {
dfeec247
XL
57 SubtypeOf,
58 SupertypeOf,
59 EqTo,
cc61c64b
XL
60}
61
dc9dc135
XL
62impl<'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
229impl<'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
380struct 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
411struct 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
442impl 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
643pub 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
649impl<'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
658pub 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
665fn 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
673fn 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}