compiler/rustc_infer/src/infer/combine.rs

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