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