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
  35 use crate::traits::{Obligation, PredicateObligations};
  36
  37 use rustc_data_structures::sso::SsoHashMap;
  38 use rustc_hir::def_id::DefId;
  39 use rustc_middle::traits::ObligationCause;
  40 use rustc_middle::ty::error::{ExpectedFound, TypeError};
  41 use rustc_middle::ty::relate::{self, Relate, RelateResult, TypeRelation};
  42 use rustc_middle::ty::subst::SubstsRef;
  43 use rustc_middle::ty::{self, InferConst, ToPredicate, Ty, TyCtxt, TypeFoldable};
  44 use rustc_middle::ty::{IntType, UintType};
  45 use rustc_span::{Span, DUMMY_SP};
  46
  47 #[derive(Clone)]
  48 pub struct CombineFields<'infcx, 'tcx> {
  49     pub infcx: &'infcx InferCtxt<'infcx, 'tcx>,
  50     pub trace: TypeTrace<'tcx>,
  51     pub cause: Option<ty::relate::Cause>,
  52     pub param_env: ty::ParamEnv<'tcx>,
  53     pub obligations: PredicateObligations<'tcx>,
  54 }
  55
  56 #[derive(Copy, Clone, Debug)]
  57 pub enum RelationDir {
  58     SubtypeOf,
  59     SupertypeOf,
  60     EqTo,
  61 }
  62
  63 impl<'infcx, 'tcx> InferCtxt<'infcx, 'tcx> {
  64     pub fn super_combine_tys<R>(
  65         &self,
  66         relation: &mut R,
  67         a: Ty<'tcx>,
  68         b: Ty<'tcx>,
  69     ) -> RelateResult<'tcx, Ty<'tcx>>
  70     where
  71         R: TypeRelation<'tcx>,
  72     {
  73         let a_is_expected = relation.a_is_expected();
  74
  75         match (a.kind(), b.kind()) {
  76             // Relate integral variables to other types
  77             (&ty::Infer(ty::IntVar(a_id)), &ty::Infer(ty::IntVar(b_id))) => {
  78                 self.inner
  79                     .borrow_mut()
  80                     .int_unification_table()
  81                     .unify_var_var(a_id, b_id)
  82                     .map_err(|e| int_unification_error(a_is_expected, e))?;
  83                 Ok(a)
  84             }
  85             (&ty::Infer(ty::IntVar(v_id)), &ty::Int(v)) => {
  86                 self.unify_integral_variable(a_is_expected, v_id, IntType(v))
  87             }
  88             (&ty::Int(v), &ty::Infer(ty::IntVar(v_id))) => {
  89                 self.unify_integral_variable(!a_is_expected, v_id, IntType(v))
  90             }
  91             (&ty::Infer(ty::IntVar(v_id)), &ty::Uint(v)) => {
  92                 self.unify_integral_variable(a_is_expected, v_id, UintType(v))
  93             }
  94             (&ty::Uint(v), &ty::Infer(ty::IntVar(v_id))) => {
  95                 self.unify_integral_variable(!a_is_expected, v_id, UintType(v))
  96             }
  97
  98             // Relate floating-point variables to other types
  99             (&ty::Infer(ty::FloatVar(a_id)), &ty::Infer(ty::FloatVar(b_id))) => {
 100                 self.inner
 101                     .borrow_mut()
 102                     .float_unification_table()
 103                     .unify_var_var(a_id, b_id)
 104                     .map_err(|e| float_unification_error(relation.a_is_expected(), e))?;
 105                 Ok(a)
 106             }
 107             (&ty::Infer(ty::FloatVar(v_id)), &ty::Float(v)) => {
 108                 self.unify_float_variable(a_is_expected, v_id, v)
 109             }
 110             (&ty::Float(v), &ty::Infer(ty::FloatVar(v_id))) => {
 111                 self.unify_float_variable(!a_is_expected, v_id, v)
 112             }
 113
 114             // All other cases of inference are errors
 115             (&ty::Infer(_), _) | (_, &ty::Infer(_)) => {
 116                 Err(TypeError::Sorts(ty::relate::expected_found(relation, a, b)))
 117             }
 118
 119             _ => ty::relate::super_relate_tys(relation, a, b),
 120         }
 121     }
 122
 123     pub fn super_combine_consts<R>(
 124         &self,
 125         relation: &mut R,
 126         a: ty::Const<'tcx>,
 127         b: ty::Const<'tcx>,
 128     ) -> RelateResult<'tcx, ty::Const<'tcx>>
 129     where
 130         R: ConstEquateRelation<'tcx>,
 131     {
 132         debug!("{}.consts({:?}, {:?})", relation.tag(), a, b);
 133         if a == b {
 134             return Ok(a);
 135         }
 136
 137         let a = replace_if_possible(&mut self.inner.borrow_mut().const_unification_table(), a);
 138         let b = replace_if_possible(&mut self.inner.borrow_mut().const_unification_table(), b);
 139
 140         let a_is_expected = relation.a_is_expected();
 141
 142         match (a.val(), b.val()) {
 143             (
 144                 ty::ConstKind::Infer(InferConst::Var(a_vid)),
 145                 ty::ConstKind::Infer(InferConst::Var(b_vid)),
 146             ) => {
 147                 self.inner
 148                     .borrow_mut()
 149                     .const_unification_table()
 150                     .unify_var_var(a_vid, b_vid)
 151                     .map_err(|e| const_unification_error(a_is_expected, e))?;
 152                 return Ok(a);
 153             }
 154
 155             // All other cases of inference with other variables are errors.
 156             (ty::ConstKind::Infer(InferConst::Var(_)), ty::ConstKind::Infer(_))
 157             | (ty::ConstKind::Infer(_), ty::ConstKind::Infer(InferConst::Var(_))) => {
 158                 bug!("tried to combine ConstKind::Infer/ConstKind::Infer(InferConst::Var)")
 159             }
 160
 161             (ty::ConstKind::Infer(InferConst::Var(vid)), _) => {
 162                 return self.unify_const_variable(relation.param_env(), vid, b, a_is_expected);
 163             }
 164
 165             (_, ty::ConstKind::Infer(InferConst::Var(vid))) => {
 166                 return self.unify_const_variable(relation.param_env(), vid, a, !a_is_expected);
 167             }
 168             (ty::ConstKind::Unevaluated(..), _) if self.tcx.lazy_normalization() => {
 169                 // FIXME(#59490): Need to remove the leak check to accommodate
 170                 // escaping bound variables here.
 171                 if !a.has_escaping_bound_vars() && !b.has_escaping_bound_vars() {
 172                     relation.const_equate_obligation(a, b);
 173                 }
 174                 return Ok(b);
 175             }
 176             (_, ty::ConstKind::Unevaluated(..)) if self.tcx.lazy_normalization() => {
 177                 // FIXME(#59490): Need to remove the leak check to accommodate
 178                 // escaping bound variables here.
 179                 if !a.has_escaping_bound_vars() && !b.has_escaping_bound_vars() {
 180                     relation.const_equate_obligation(a, b);
 181                 }
 182                 return Ok(a);
 183             }
 184             _ => {}
 185         }
 186
 187         ty::relate::super_relate_consts(relation, a, b)
 188     }
 189
 190     /// Unifies the const variable `target_vid` with the given constant.
 191     ///
 192     /// This also tests if the given const `ct` contains an inference variable which was previously
 193     /// unioned with `target_vid`. If this is the case, inferring `target_vid` to `ct`
 194     /// would result in an infinite type as we continuously replace an inference variable
 195     /// in `ct` with `ct` itself.
 196     ///
 197     /// This is especially important as unevaluated consts use their parents generics.
 198     /// They therefore often contain unused substs, making these errors far more likely.
 199     ///
 200     /// A good example of this is the following:
 201     ///
 202     /// ```rust
 203     /// #![feature(generic_const_exprs)]
 204     ///
 205     /// fn bind<const N: usize>(value: [u8; N]) -> [u8; 3 + 4] {
 206     ///     todo!()
 207     /// }
 208     ///
 209     /// fn main() {
 210     ///     let mut arr = Default::default();
 211     ///     arr = bind(arr);
 212     /// }
 213     /// ```
 214     ///
 215     /// Here `3 + 4` ends up as `ConstKind::Unevaluated` which uses the generics
 216     /// of `fn bind` (meaning that its substs contain `N`).
 217     ///
 218     /// `bind(arr)` now infers that the type of `arr` must be `[u8; N]`.
 219     /// The assignment `arr = bind(arr)` now tries to equate `N` with `3 + 4`.
 220     ///
 221     /// As `3 + 4` contains `N` in its substs, this must not succeed.
 222     ///
 223     /// See `src/test/ui/const-generics/occurs-check/` for more examples where this is relevant.
 224     #[instrument(level = "debug", skip(self))]
 225     fn unify_const_variable(
 226         &self,
 227         param_env: ty::ParamEnv<'tcx>,
 228         target_vid: ty::ConstVid<'tcx>,
 229         ct: ty::Const<'tcx>,
 230         vid_is_expected: bool,
 231     ) -> RelateResult<'tcx, ty::Const<'tcx>> {
 232         let (for_universe, span) = {
 233             let mut inner = self.inner.borrow_mut();
 234             let variable_table = &mut inner.const_unification_table();
 235             let var_value = variable_table.probe_value(target_vid);
 236             match var_value.val {
 237                 ConstVariableValue::Known { value } => {
 238                     bug!("instantiating {:?} which has a known value {:?}", target_vid, value)
 239                 }
 240                 ConstVariableValue::Unknown { universe } => (universe, var_value.origin.span),
 241             }
 242         };
 243         let value = ConstInferUnifier { infcx: self, span, param_env, for_universe, target_vid }
 244             .relate(ct, ct)?;
 245
 246         self.inner
 247             .borrow_mut()
 248             .const_unification_table()
 249             .unify_var_value(
 250                 target_vid,
 251                 ConstVarValue {
 252                     origin: ConstVariableOrigin {
 253                         kind: ConstVariableOriginKind::ConstInference,
 254                         span: DUMMY_SP,
 255                     },
 256                     val: ConstVariableValue::Known { value },
 257                 },
 258             )
 259             .map(|()| value)
 260             .map_err(|e| const_unification_error(vid_is_expected, e))
 261     }
 262
 263     fn unify_integral_variable(
 264         &self,
 265         vid_is_expected: bool,
 266         vid: ty::IntVid,
 267         val: ty::IntVarValue,
 268     ) -> RelateResult<'tcx, Ty<'tcx>> {
 269         self.inner
 270             .borrow_mut()
 271             .int_unification_table()
 272             .unify_var_value(vid, Some(val))
 273             .map_err(|e| int_unification_error(vid_is_expected, e))?;
 274         match val {
 275             IntType(v) => Ok(self.tcx.mk_mach_int(v)),
 276             UintType(v) => Ok(self.tcx.mk_mach_uint(v)),
 277         }
 278     }
 279
 280     fn unify_float_variable(
 281         &self,
 282         vid_is_expected: bool,
 283         vid: ty::FloatVid,
 284         val: ty::FloatTy,
 285     ) -> RelateResult<'tcx, Ty<'tcx>> {
 286         self.inner
 287             .borrow_mut()
 288             .float_unification_table()
 289             .unify_var_value(vid, Some(ty::FloatVarValue(val)))
 290             .map_err(|e| float_unification_error(vid_is_expected, e))?;
 291         Ok(self.tcx.mk_mach_float(val))
 292     }
 293 }
 294
 295 impl<'infcx, 'tcx> CombineFields<'infcx, 'tcx> {
 296     pub fn tcx(&self) -> TyCtxt<'tcx> {
 297         self.infcx.tcx
 298     }
 299
 300     pub fn equate<'a>(&'a mut self, a_is_expected: bool) -> Equate<'a, 'infcx, 'tcx> {
 301         Equate::new(self, a_is_expected)
 302     }
 303
 304     pub fn sub<'a>(&'a mut self, a_is_expected: bool) -> Sub<'a, 'infcx, 'tcx> {
 305         Sub::new(self, a_is_expected)
 306     }
 307
 308     pub fn lub<'a>(&'a mut self, a_is_expected: bool) -> Lub<'a, 'infcx, 'tcx> {
 309         Lub::new(self, a_is_expected)
 310     }
 311
 312     pub fn glb<'a>(&'a mut self, a_is_expected: bool) -> Glb<'a, 'infcx, 'tcx> {
 313         Glb::new(self, a_is_expected)
 314     }
 315
 316     /// Here, `dir` is either `EqTo`, `SubtypeOf`, or `SupertypeOf`.
 317     /// The idea is that we should ensure that the type `a_ty` is equal
 318     /// to, a subtype of, or a supertype of (respectively) the type
 319     /// to which `b_vid` is bound.
 320     ///
 321     /// Since `b_vid` has not yet been instantiated with a type, we
 322     /// will first instantiate `b_vid` with a *generalized* version
 323     /// of `a_ty`. Generalization introduces other inference
 324     /// variables wherever subtyping could occur.
 325     pub fn instantiate(
 326         &mut self,
 327         a_ty: Ty<'tcx>,
 328         dir: RelationDir,
 329         b_vid: ty::TyVid,
 330         a_is_expected: bool,
 331     ) -> RelateResult<'tcx, ()> {
 332         use self::RelationDir::*;
 333
 334         // Get the actual variable that b_vid has been inferred to
 335         debug_assert!(self.infcx.inner.borrow_mut().type_variables().probe(b_vid).is_unknown());
 336
 337         debug!("instantiate(a_ty={:?} dir={:?} b_vid={:?})", a_ty, dir, b_vid);
 338
 339         // Generalize type of `a_ty` appropriately depending on the
 340         // direction.  As an example, assume:
 341         //
 342         // - `a_ty == &'x ?1`, where `'x` is some free region and `?1` is an
 343         //   inference variable,
 344         // - and `dir` == `SubtypeOf`.
 345         //
 346         // Then the generalized form `b_ty` would be `&'?2 ?3`, where
 347         // `'?2` and `?3` are fresh region/type inference
 348         // variables. (Down below, we will relate `a_ty <: b_ty`,
 349         // adding constraints like `'x: '?2` and `?1 <: ?3`.)
 350         let Generalization { ty: b_ty, needs_wf } = self.generalize(a_ty, b_vid, dir)?;
 351         debug!(
 352             "instantiate(a_ty={:?}, dir={:?}, b_vid={:?}, generalized b_ty={:?})",
 353             a_ty, dir, b_vid, b_ty
 354         );
 355         self.infcx.inner.borrow_mut().type_variables().instantiate(b_vid, b_ty);
 356
 357         if needs_wf {
 358             self.obligations.push(Obligation::new(
 359                 self.trace.cause.clone(),
 360                 self.param_env,
 361                 ty::Binder::dummy(ty::PredicateKind::WellFormed(b_ty.into()))
 362                     .to_predicate(self.infcx.tcx),
 363             ));
 364         }
 365
 366         // Finally, relate `b_ty` to `a_ty`, as described in previous comment.
 367         //
 368         // FIXME(#16847): This code is non-ideal because all these subtype
 369         // relations wind up attributed to the same spans. We need
 370         // to associate causes/spans with each of the relations in
 371         // the stack to get this right.
 372         match dir {
 373             EqTo => self.equate(a_is_expected).relate(a_ty, b_ty),
 374             SubtypeOf => self.sub(a_is_expected).relate(a_ty, b_ty),
 375             SupertypeOf => self.sub(a_is_expected).relate_with_variance(
 376                 ty::Contravariant,
 377                 ty::VarianceDiagInfo::default(),
 378                 a_ty,
 379                 b_ty,
 380             ),
 381         }?;
 382
 383         Ok(())
 384     }
 385
 386     /// Attempts to generalize `ty` for the type variable `for_vid`.
 387     /// This checks for cycle -- that is, whether the type `ty`
 388     /// references `for_vid`. The `dir` is the "direction" for which we
 389     /// a performing the generalization (i.e., are we producing a type
 390     /// that can be used as a supertype etc).
 391     ///
 392     /// Preconditions:
 393     ///
 394     /// - `for_vid` is a "root vid"
 395     fn generalize(
 396         &self,
 397         ty: Ty<'tcx>,
 398         for_vid: ty::TyVid,
 399         dir: RelationDir,
 400     ) -> RelateResult<'tcx, Generalization<'tcx>> {
 401         debug!("generalize(ty={:?}, for_vid={:?}, dir={:?}", ty, for_vid, dir);
 402         // Determine the ambient variance within which `ty` appears.
 403         // The surrounding equation is:
 404         //
 405         //     ty [op] ty2
 406         //
 407         // where `op` is either `==`, `<:`, or `:>`. This maps quite
 408         // naturally.
 409         let ambient_variance = match dir {
 410             RelationDir::EqTo => ty::Invariant,
 411             RelationDir::SubtypeOf => ty::Covariant,
 412             RelationDir::SupertypeOf => ty::Contravariant,
 413         };
 414
 415         debug!("generalize: ambient_variance = {:?}", ambient_variance);
 416
 417         let for_universe = match self.infcx.inner.borrow_mut().type_variables().probe(for_vid) {
 418             v @ TypeVariableValue::Known { .. } => {
 419                 bug!("instantiating {:?} which has a known value {:?}", for_vid, v,)
 420             }
 421             TypeVariableValue::Unknown { universe } => universe,
 422         };
 423
 424         debug!("generalize: for_universe = {:?}", for_universe);
 425         debug!("generalize: trace = {:?}", self.trace);
 426
 427         let mut generalize = Generalizer {
 428             infcx: self.infcx,
 429             cause: &self.trace.cause,
 430             for_vid_sub_root: self.infcx.inner.borrow_mut().type_variables().sub_root_var(for_vid),
 431             for_universe,
 432             ambient_variance,
 433             needs_wf: false,
 434             root_ty: ty,
 435             param_env: self.param_env,
 436             cache: SsoHashMap::new(),
 437         };
 438
 439         let ty = match generalize.relate(ty, ty) {
 440             Ok(ty) => ty,
 441             Err(e) => {
 442                 debug!("generalize: failure {:?}", e);
 443                 return Err(e);
 444             }
 445         };
 446         let needs_wf = generalize.needs_wf;
 447         debug!("generalize: success {{ {:?}, {:?} }}", ty, needs_wf);
 448         Ok(Generalization { ty, needs_wf })
 449     }
 450
 451     pub fn add_const_equate_obligation(
 452         &mut self,
 453         a_is_expected: bool,
 454         a: ty::Const<'tcx>,
 455         b: ty::Const<'tcx>,
 456     ) {
 457         let predicate = if a_is_expected {
 458             ty::PredicateKind::ConstEquate(a, b)
 459         } else {
 460             ty::PredicateKind::ConstEquate(b, a)
 461         };
 462         self.obligations.push(Obligation::new(
 463             self.trace.cause.clone(),
 464             self.param_env,
 465             ty::Binder::dummy(predicate).to_predicate(self.tcx()),
 466         ));
 467     }
 468 }
 469
 470 struct Generalizer<'cx, 'tcx> {
 471     infcx: &'cx InferCtxt<'cx, 'tcx>,
 472
 473     /// The span, used when creating new type variables and things.
 474     cause: &'cx ObligationCause<'tcx>,
 475
 476     /// The vid of the type variable that is in the process of being
 477     /// instantiated; if we find this within the type we are folding,
 478     /// that means we would have created a cyclic type.
 479     for_vid_sub_root: ty::TyVid,
 480
 481     /// The universe of the type variable that is in the process of
 482     /// being instantiated. Any fresh variables that we create in this
 483     /// process should be in that same universe.
 484     for_universe: ty::UniverseIndex,
 485
 486     /// Track the variance as we descend into the type.
 487     ambient_variance: ty::Variance,
 488
 489     /// See the field `needs_wf` in `Generalization`.
 490     needs_wf: bool,
 491
 492     /// The root type that we are generalizing. Used when reporting cycles.
 493     root_ty: Ty<'tcx>,
 494
 495     param_env: ty::ParamEnv<'tcx>,
 496
 497     cache: SsoHashMap<Ty<'tcx>, RelateResult<'tcx, Ty<'tcx>>>,
 498 }
 499
 500 /// Result from a generalization operation. This includes
 501 /// not only the generalized type, but also a bool flag
 502 /// indicating whether further WF checks are needed.
 503 struct Generalization<'tcx> {
 504     ty: Ty<'tcx>,
 505
 506     /// If true, then the generalized type may not be well-formed,
 507     /// even if the source type is well-formed, so we should add an
 508     /// additional check to enforce that it is. This arises in
 509     /// particular around 'bivariant' type parameters that are only
 510     /// constrained by a where-clause. As an example, imagine a type:
 511     ///
 512     ///     struct Foo<A, B> where A: Iterator<Item = B> {
 513     ///         data: A
 514     ///     }
 515     ///
 516     /// here, `A` will be covariant, but `B` is
 517     /// unconstrained. However, whatever it is, for `Foo` to be WF, it
 518     /// must be equal to `A::Item`. If we have an input `Foo<?A, ?B>`,
 519     /// then after generalization we will wind up with a type like
 520     /// `Foo<?C, ?D>`. When we enforce that `Foo<?A, ?B> <: Foo<?C,
 521     /// ?D>` (or `>:`), we will wind up with the requirement that `?A
 522     /// <: ?C`, but no particular relationship between `?B` and `?D`
 523     /// (after all, we do not know the variance of the normalized form
 524     /// of `A::Item` with respect to `A`). If we do nothing else, this
 525     /// may mean that `?D` goes unconstrained (as in #41677). So, in
 526     /// this scenario where we create a new type variable in a
 527     /// bivariant context, we set the `needs_wf` flag to true. This
 528     /// will force the calling code to check that `WF(Foo<?C, ?D>)`
 529     /// holds, which in turn implies that `?C::Item == ?D`. So once
 530     /// `?C` is constrained, that should suffice to restrict `?D`.
 531     needs_wf: bool,
 532 }
 533
 534 impl<'tcx> TypeRelation<'tcx> for Generalizer<'_, 'tcx> {
 535     fn tcx(&self) -> TyCtxt<'tcx> {
 536         self.infcx.tcx
 537     }
 538     fn param_env(&self) -> ty::ParamEnv<'tcx> {
 539         self.param_env
 540     }
 541
 542     fn tag(&self) -> &'static str {
 543         "Generalizer"
 544     }
 545
 546     fn a_is_expected(&self) -> bool {
 547         true
 548     }
 549
 550     fn binders<T>(
 551         &mut self,
 552         a: ty::Binder<'tcx, T>,
 553         b: ty::Binder<'tcx, T>,
 554     ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
 555     where
 556         T: Relate<'tcx>,
 557     {
 558         Ok(a.rebind(self.relate(a.skip_binder(), b.skip_binder())?))
 559     }
 560
 561     fn relate_item_substs(
 562         &mut self,
 563         item_def_id: DefId,
 564         a_subst: SubstsRef<'tcx>,
 565         b_subst: SubstsRef<'tcx>,
 566     ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
 567         if self.ambient_variance == ty::Variance::Invariant {
 568             // Avoid fetching the variance if we are in an invariant
 569             // context; no need, and it can induce dependency cycles
 570             // (e.g., #41849).
 571             relate::relate_substs(self, None, a_subst, b_subst)
 572         } else {
 573             let tcx = self.tcx();
 574             let opt_variances = tcx.variances_of(item_def_id);
 575             relate::relate_substs(self, Some((item_def_id, &opt_variances)), a_subst, b_subst)
 576         }
 577     }
 578
 579     fn relate_with_variance<T: Relate<'tcx>>(
 580         &mut self,
 581         variance: ty::Variance,
 582         _info: ty::VarianceDiagInfo<'tcx>,
 583         a: T,
 584         b: T,
 585     ) -> RelateResult<'tcx, T> {
 586         let old_ambient_variance = self.ambient_variance;
 587         self.ambient_variance = self.ambient_variance.xform(variance);
 588
 589         let result = self.relate(a, b);
 590         self.ambient_variance = old_ambient_variance;
 591         result
 592     }
 593
 594     fn tys(&mut self, t: Ty<'tcx>, t2: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
 595         assert_eq!(t, t2); // we are abusing TypeRelation here; both LHS and RHS ought to be ==
 596
 597         if let Some(result) = self.cache.get(&t) {
 598             return result.clone();
 599         }
 600         debug!("generalize: t={:?}", t);
 601
 602         // Check to see whether the type we are generalizing references
 603         // any other type variable related to `vid` via
 604         // subtyping. This is basically our "occurs check", preventing
 605         // us from creating infinitely sized types.
 606         let result = match *t.kind() {
 607             ty::Infer(ty::TyVar(vid)) => {
 608                 let vid = self.infcx.inner.borrow_mut().type_variables().root_var(vid);
 609                 let sub_vid = self.infcx.inner.borrow_mut().type_variables().sub_root_var(vid);
 610                 if sub_vid == self.for_vid_sub_root {
 611                     // If sub-roots are equal, then `for_vid` and
 612                     // `vid` are related via subtyping.
 613                     Err(TypeError::CyclicTy(self.root_ty))
 614                 } else {
 615                     let probe = self.infcx.inner.borrow_mut().type_variables().probe(vid);
 616                     match probe {
 617                         TypeVariableValue::Known { value: u } => {
 618                             debug!("generalize: known value {:?}", u);
 619                             self.relate(u, u)
 620                         }
 621                         TypeVariableValue::Unknown { universe } => {
 622                             match self.ambient_variance {
 623                                 // Invariant: no need to make a fresh type variable.
 624                                 ty::Invariant => {
 625                                     if self.for_universe.can_name(universe) {
 626                                         return Ok(t);
 627                                     }
 628                                 }
 629
 630                                 // Bivariant: make a fresh var, but we
 631                                 // may need a WF predicate. See
 632                                 // comment on `needs_wf` field for
 633                                 // more info.
 634                                 ty::Bivariant => self.needs_wf = true,
 635
 636                                 // Co/contravariant: this will be
 637                                 // sufficiently constrained later on.
 638                                 ty::Covariant | ty::Contravariant => (),
 639                             }
 640
 641                             let origin =
 642                                 *self.infcx.inner.borrow_mut().type_variables().var_origin(vid);
 643                             let new_var_id = self
 644                                 .infcx
 645                                 .inner
 646                                 .borrow_mut()
 647                                 .type_variables()
 648                                 .new_var(self.for_universe, origin);
 649                             let u = self.tcx().mk_ty_var(new_var_id);
 650
 651                             // Record that we replaced `vid` with `new_var_id` as part of a generalization
 652                             // operation. This is needed to detect cyclic types. To see why, see the
 653                             // docs in the `type_variables` module.
 654                             self.infcx.inner.borrow_mut().type_variables().sub(vid, new_var_id);
 655                             debug!("generalize: replacing original vid={:?} with new={:?}", vid, u);
 656                             Ok(u)
 657                         }
 658                     }
 659                 }
 660             }
 661             ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => {
 662                 // No matter what mode we are in,
 663                 // integer/floating-point types must be equal to be
 664                 // relatable.
 665                 Ok(t)
 666             }
 667             _ => relate::super_relate_tys(self, t, t),
 668         };
 669
 670         self.cache.insert(t, result.clone());
 671         return result;
 672     }
 673
 674     fn regions(
 675         &mut self,
 676         r: ty::Region<'tcx>,
 677         r2: ty::Region<'tcx>,
 678     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 679         assert_eq!(r, r2); // we are abusing TypeRelation here; both LHS and RHS ought to be ==
 680
 681         debug!("generalize: regions r={:?}", r);
 682
 683         match *r {
 684             // Never make variables for regions bound within the type itself,
 685             // nor for erased regions.
 686             ty::ReLateBound(..) | ty::ReErased => {
 687                 return Ok(r);
 688             }
 689
 690             ty::RePlaceholder(..)
 691             | ty::ReVar(..)
 692             | ty::ReEmpty(_)
 693             | ty::ReStatic
 694             | ty::ReEarlyBound(..)
 695             | ty::ReFree(..) => {
 696                 // see common code below
 697             }
 698         }
 699
 700         // If we are in an invariant context, we can re-use the region
 701         // as is, unless it happens to be in some universe that we
 702         // can't name. (In the case of a region *variable*, we could
 703         // use it if we promoted it into our universe, but we don't
 704         // bother.)
 705         if let ty::Invariant = self.ambient_variance {
 706             let r_universe = self.infcx.universe_of_region(r);
 707             if self.for_universe.can_name(r_universe) {
 708                 return Ok(r);
 709             }
 710         }
 711
 712         // FIXME: This is non-ideal because we don't give a
 713         // very descriptive origin for this region variable.
 714         Ok(self.infcx.next_region_var_in_universe(MiscVariable(self.cause.span), self.for_universe))
 715     }
 716
 717     fn consts(
 718         &mut self,
 719         c: ty::Const<'tcx>,
 720         c2: ty::Const<'tcx>,
 721     ) -> RelateResult<'tcx, ty::Const<'tcx>> {
 722         assert_eq!(c, c2); // we are abusing TypeRelation here; both LHS and RHS ought to be ==
 723
 724         match c.val() {
 725             ty::ConstKind::Infer(InferConst::Var(vid)) => {
 726                 let mut inner = self.infcx.inner.borrow_mut();
 727                 let variable_table = &mut inner.const_unification_table();
 728                 let var_value = variable_table.probe_value(vid);
 729                 match var_value.val {
 730                     ConstVariableValue::Known { value: u } => {
 731                         drop(inner);
 732                         self.relate(u, u)
 733                     }
 734                     ConstVariableValue::Unknown { universe } => {
 735                         if self.for_universe.can_name(universe) {
 736                             Ok(c)
 737                         } else {
 738                             let new_var_id = variable_table.new_key(ConstVarValue {
 739                                 origin: var_value.origin,
 740                                 val: ConstVariableValue::Unknown { universe: self.for_universe },
 741                             });
 742                             Ok(self.tcx().mk_const_var(new_var_id, c.ty()))
 743                         }
 744                     }
 745                 }
 746             }
 747             ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs, promoted })
 748                 if self.tcx().lazy_normalization() =>
 749             {
 750                 assert_eq!(promoted, None);
 751                 let substs = self.relate_with_variance(
 752                     ty::Variance::Invariant,
 753                     ty::VarianceDiagInfo::default(),
 754                     substs,
 755                     substs,
 756                 )?;
 757                 Ok(self.tcx().mk_const(ty::ConstS {
 758                     ty: c.ty(),
 759                     val: ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs, promoted }),
 760                 }))
 761             }
 762             _ => relate::super_relate_consts(self, c, c),
 763         }
 764     }
 765 }
 766
 767 pub trait ConstEquateRelation<'tcx>: TypeRelation<'tcx> {
 768     /// Register an obligation that both constants must be equal to each other.
 769     ///
 770     /// If they aren't equal then the relation doesn't hold.
 771     fn const_equate_obligation(&mut self, a: ty::Const<'tcx>, b: ty::Const<'tcx>);
 772 }
 773
 774 pub trait RelateResultCompare<'tcx, T> {
 775     fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T>
 776     where
 777         F: FnOnce() -> TypeError<'tcx>;
 778 }
 779
 780 impl<'tcx, T: Clone + PartialEq> RelateResultCompare<'tcx, T> for RelateResult<'tcx, T> {
 781     fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T>
 782     where
 783         F: FnOnce() -> TypeError<'tcx>,
 784     {
 785         self.clone().and_then(|s| if s == t { self.clone() } else { Err(f()) })
 786     }
 787 }
 788
 789 pub fn const_unification_error<'tcx>(
 790     a_is_expected: bool,
 791     (a, b): (ty::Const<'tcx>, ty::Const<'tcx>),
 792 ) -> TypeError<'tcx> {
 793     TypeError::ConstMismatch(ExpectedFound::new(a_is_expected, a, b))
 794 }
 795
 796 fn int_unification_error<'tcx>(
 797     a_is_expected: bool,
 798     v: (ty::IntVarValue, ty::IntVarValue),
 799 ) -> TypeError<'tcx> {
 800     let (a, b) = v;
 801     TypeError::IntMismatch(ExpectedFound::new(a_is_expected, a, b))
 802 }
 803
 804 fn float_unification_error<'tcx>(
 805     a_is_expected: bool,
 806     v: (ty::FloatVarValue, ty::FloatVarValue),
 807 ) -> TypeError<'tcx> {
 808     let (ty::FloatVarValue(a), ty::FloatVarValue(b)) = v;
 809     TypeError::FloatMismatch(ExpectedFound::new(a_is_expected, a, b))
 810 }
 811
 812 struct ConstInferUnifier<'cx, 'tcx> {
 813     infcx: &'cx InferCtxt<'cx, 'tcx>,
 814
 815     span: Span,
 816
 817     param_env: ty::ParamEnv<'tcx>,
 818
 819     for_universe: ty::UniverseIndex,
 820
 821     /// The vid of the const variable that is in the process of being
 822     /// instantiated; if we find this within the const we are folding,
 823     /// that means we would have created a cyclic const.
 824     target_vid: ty::ConstVid<'tcx>,
 825 }
 826
 827 // We use `TypeRelation` here to propagate `RelateResult` upwards.
 828 //
 829 // Both inputs are expected to be the same.
 830 impl<'tcx> TypeRelation<'tcx> for ConstInferUnifier<'_, 'tcx> {
 831     fn tcx(&self) -> TyCtxt<'tcx> {
 832         self.infcx.tcx
 833     }
 834
 835     fn param_env(&self) -> ty::ParamEnv<'tcx> {
 836         self.param_env
 837     }
 838
 839     fn tag(&self) -> &'static str {
 840         "ConstInferUnifier"
 841     }
 842
 843     fn a_is_expected(&self) -> bool {
 844         true
 845     }
 846
 847     fn relate_with_variance<T: Relate<'tcx>>(
 848         &mut self,
 849         _variance: ty::Variance,
 850         _info: ty::VarianceDiagInfo<'tcx>,
 851         a: T,
 852         b: T,
 853     ) -> RelateResult<'tcx, T> {
 854         // We don't care about variance here.
 855         self.relate(a, b)
 856     }
 857
 858     fn binders<T>(
 859         &mut self,
 860         a: ty::Binder<'tcx, T>,
 861         b: ty::Binder<'tcx, T>,
 862     ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
 863     where
 864         T: Relate<'tcx>,
 865     {
 866         Ok(a.rebind(self.relate(a.skip_binder(), b.skip_binder())?))
 867     }
 868
 869     #[tracing::instrument(level = "debug", skip(self))]
 870     fn tys(&mut self, t: Ty<'tcx>, _t: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
 871         debug_assert_eq!(t, _t);
 872         debug!("ConstInferUnifier: t={:?}", t);
 873
 874         match t.kind() {
 875             &ty::Infer(ty::TyVar(vid)) => {
 876                 let vid = self.infcx.inner.borrow_mut().type_variables().root_var(vid);
 877                 let probe = self.infcx.inner.borrow_mut().type_variables().probe(vid);
 878                 match probe {
 879                     TypeVariableValue::Known { value: u } => {
 880                         debug!("ConstOccursChecker: known value {:?}", u);
 881                         self.tys(u, u)
 882                     }
 883                     TypeVariableValue::Unknown { universe } => {
 884                         if self.for_universe.can_name(universe) {
 885                             return Ok(t);
 886                         }
 887
 888                         let origin =
 889                             *self.infcx.inner.borrow_mut().type_variables().var_origin(vid);
 890                         let new_var_id = self
 891                             .infcx
 892                             .inner
 893                             .borrow_mut()
 894                             .type_variables()
 895                             .new_var(self.for_universe, origin);
 896                         let u = self.tcx().mk_ty_var(new_var_id);
 897                         debug!(
 898                             "ConstInferUnifier: replacing original vid={:?} with new={:?}",
 899                             vid, u
 900                         );
 901                         Ok(u)
 902                     }
 903                 }
 904             }
 905             ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => Ok(t),
 906             _ => relate::super_relate_tys(self, t, t),
 907         }
 908     }
 909
 910     fn regions(
 911         &mut self,
 912         r: ty::Region<'tcx>,
 913         _r: ty::Region<'tcx>,
 914     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 915         debug_assert_eq!(r, _r);
 916         debug!("ConstInferUnifier: r={:?}", r);
 917
 918         match *r {
 919             // Never make variables for regions bound within the type itself,
 920             // nor for erased regions.
 921             ty::ReLateBound(..) | ty::ReErased => {
 922                 return Ok(r);
 923             }
 924
 925             ty::RePlaceholder(..)
 926             | ty::ReVar(..)
 927             | ty::ReEmpty(_)
 928             | ty::ReStatic
 929             | ty::ReEarlyBound(..)
 930             | ty::ReFree(..) => {
 931                 // see common code below
 932             }
 933         }
 934
 935         let r_universe = self.infcx.universe_of_region(r);
 936         if self.for_universe.can_name(r_universe) {
 937             return Ok(r);
 938         } else {
 939             // FIXME: This is non-ideal because we don't give a
 940             // very descriptive origin for this region variable.
 941             Ok(self.infcx.next_region_var_in_universe(MiscVariable(self.span), self.for_universe))
 942         }
 943     }
 944
 945     #[tracing::instrument(level = "debug", skip(self))]
 946     fn consts(
 947         &mut self,
 948         c: ty::Const<'tcx>,
 949         _c: ty::Const<'tcx>,
 950     ) -> RelateResult<'tcx, ty::Const<'tcx>> {
 951         debug_assert_eq!(c, _c);
 952         debug!("ConstInferUnifier: c={:?}", c);
 953
 954         match c.val() {
 955             ty::ConstKind::Infer(InferConst::Var(vid)) => {
 956                 // Check if the current unification would end up
 957                 // unifying `target_vid` with a const which contains
 958                 // an inference variable which is unioned with `target_vid`.
 959                 //
 960                 // Not doing so can easily result in stack overflows.
 961                 if self
 962                     .infcx
 963                     .inner
 964                     .borrow_mut()
 965                     .const_unification_table()
 966                     .unioned(self.target_vid, vid)
 967                 {
 968                     return Err(TypeError::CyclicConst(c));
 969                 }
 970
 971                 let var_value =
 972                     self.infcx.inner.borrow_mut().const_unification_table().probe_value(vid);
 973                 match var_value.val {
 974                     ConstVariableValue::Known { value: u } => self.consts(u, u),
 975                     ConstVariableValue::Unknown { universe } => {
 976                         if self.for_universe.can_name(universe) {
 977                             Ok(c)
 978                         } else {
 979                             let new_var_id =
 980                                 self.infcx.inner.borrow_mut().const_unification_table().new_key(
 981                                     ConstVarValue {
 982                                         origin: var_value.origin,
 983                                         val: ConstVariableValue::Unknown {
 984                                             universe: self.for_universe,
 985                                         },
 986                                     },
 987                                 );
 988                             Ok(self.tcx().mk_const_var(new_var_id, c.ty()))
 989                         }
 990                     }
 991                 }
 992             }
 993             ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs, promoted })
 994                 if self.tcx().lazy_normalization() =>
 995             {
 996                 assert_eq!(promoted, None);
 997                 let substs = self.relate_with_variance(
 998                     ty::Variance::Invariant,
 999                     ty::VarianceDiagInfo::default(),
1000                     substs,
1001                     substs,
1002                 )?;
1003                 Ok(self.tcx().mk_const(ty::ConstS {
1004                     ty: c.ty(),
1005                     val: ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs, promoted }),
1006                 }))
1007             }
1008             _ => relate::super_relate_consts(self, c, c),
1009         }
1010     }
1011 }