1 //! This code is kind of an alternate way of doing subtyping, 2 //! supertyping, and type equating, distinct from the `combine.rs` 3 //! code but very similar in its effect and design. Eventually the two 4 //! ought to be merged. This code is intended for use in NLL and chalk. 5 //! 6 //! Here are the key differences: 7 //! 8 //! - This code may choose to bypass some checks (e.g., the occurs check) 9 //! in the case where we know that there are no unbound type inference 10 //! variables. This is the case for NLL, because at NLL time types are fully 11 //! inferred up-to regions. 12 //! - This code uses "universes" to handle higher-ranked regions and 13 //! not the leak-check. This is "more correct" than what rustc does 14 //! and we are generally migrating in this direction, but NLL had to 15 //! get there first. 16 //! 17 //! Also, this code assumes that there are no bound types at all, not even 18 //! free ones. This is ok because: 19 //! - we are not relating anything quantified over some type variable 20 //! - we will have instantiated all the bound type vars already (the one 21 //! thing we relate in chalk are basically domain goals and their 22 //! constituents) 23 24 use rustc_data_structures::fx::FxHashMap; 25 use rustc_middle::traits::ObligationCause; 26 use rustc_middle::ty::fold::FnMutDelegate; 27 use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation}; 28 use rustc_middle::ty::visit::TypeVisitableExt; 29 use rustc_middle::ty::{self, InferConst, Ty, TyCtxt}; 30 use rustc_span::{Span, Symbol}; 31 use std::fmt::Debug; 32 33 use crate::infer::combine::ObligationEmittingRelation; 34 use crate::infer::generalize::{self, Generalization}; 35 use crate::infer::InferCtxt; 36 use crate::infer::{TypeVariableOrigin, TypeVariableOriginKind}; 37 use crate::traits::{Obligation, PredicateObligations}; 38 39 pub struct TypeRelating<'me, 'tcx, D> 40 where 41 D: TypeRelatingDelegate<'tcx>, 42 { 43 infcx: &'me InferCtxt<'tcx>, 44 45 /// Callback to use when we deduce an outlives relationship. 46 delegate: D, 47 48 /// How are we relating `a` and `b`? 49 /// 50 /// - Covariant means `a <: b`. 51 /// - Contravariant means `b <: a`. 52 /// - Invariant means `a == b`. 53 /// - Bivariant means that it doesn't matter. 54 ambient_variance: ty::Variance, 55 56 ambient_variance_info: ty::VarianceDiagInfo<'tcx>, 57 } 58 59 pub trait TypeRelatingDelegate<'tcx> { param_env(&self) -> ty::ParamEnv<'tcx>60 fn param_env(&self) -> ty::ParamEnv<'tcx>; span(&self) -> Span61 fn span(&self) -> Span; 62 63 /// Push a constraint `sup: sub` -- this constraint must be 64 /// satisfied for the two types to be related. `sub` and `sup` may 65 /// be regions from the type or new variables created through the 66 /// delegate. push_outlives( &mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>, info: ty::VarianceDiagInfo<'tcx>, )67 fn push_outlives( 68 &mut self, 69 sup: ty::Region<'tcx>, 70 sub: ty::Region<'tcx>, 71 info: ty::VarianceDiagInfo<'tcx>, 72 ); 73 register_obligations(&mut self, obligations: PredicateObligations<'tcx>)74 fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>); 75 76 /// Creates a new universe index. Used when instantiating placeholders. create_next_universe(&mut self) -> ty::UniverseIndex77 fn create_next_universe(&mut self) -> ty::UniverseIndex; 78 79 /// Creates a new region variable representing a higher-ranked 80 /// region that is instantiated existentially. This creates an 81 /// inference variable, typically. 82 /// 83 /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then 84 /// we will invoke this method to instantiate `'a` with an 85 /// inference variable (though `'b` would be instantiated first, 86 /// as a placeholder). next_existential_region_var( &mut self, was_placeholder: bool, name: Option<Symbol>, ) -> ty::Region<'tcx>87 fn next_existential_region_var( 88 &mut self, 89 was_placeholder: bool, 90 name: Option<Symbol>, 91 ) -> ty::Region<'tcx>; 92 93 /// Creates a new region variable representing a 94 /// higher-ranked region that is instantiated universally. 95 /// This creates a new region placeholder, typically. 96 /// 97 /// So e.g., if you have `for<'a> fn(..) <: for<'b> fn(..)`, then 98 /// we will invoke this method to instantiate `'b` with a 99 /// placeholder region. next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>100 fn next_placeholder_region(&mut self, placeholder: ty::PlaceholderRegion) -> ty::Region<'tcx>; 101 102 /// Creates a new existential region in the given universe. This 103 /// is used when handling subtyping and type variables -- if we 104 /// have that `?X <: Foo<'a>`, for example, we would instantiate 105 /// `?X` with a type like `Foo<'?0>` where `'?0` is a fresh 106 /// existential variable created by this function. We would then 107 /// relate `Foo<'?0>` with `Foo<'a>` (and probably add an outlives 108 /// relation stating that `'?0: 'a`). generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>109 fn generalize_existential(&mut self, universe: ty::UniverseIndex) -> ty::Region<'tcx>; 110 111 /// Enables some optimizations if we do not expect inference variables 112 /// in the RHS of the relation. forbid_inference_vars() -> bool113 fn forbid_inference_vars() -> bool; 114 } 115 116 #[derive(Copy, Clone)] 117 struct UniversallyQuantified(bool); 118 119 impl<'me, 'tcx, D> TypeRelating<'me, 'tcx, D> 120 where 121 D: TypeRelatingDelegate<'tcx>, 122 { new(infcx: &'me InferCtxt<'tcx>, delegate: D, ambient_variance: ty::Variance) -> Self123 pub fn new(infcx: &'me InferCtxt<'tcx>, delegate: D, ambient_variance: ty::Variance) -> Self { 124 Self { 125 infcx, 126 delegate, 127 ambient_variance, 128 ambient_variance_info: ty::VarianceDiagInfo::default(), 129 } 130 } 131 ambient_covariance(&self) -> bool132 fn ambient_covariance(&self) -> bool { 133 match self.ambient_variance { 134 ty::Variance::Covariant | ty::Variance::Invariant => true, 135 ty::Variance::Contravariant | ty::Variance::Bivariant => false, 136 } 137 } 138 ambient_contravariance(&self) -> bool139 fn ambient_contravariance(&self) -> bool { 140 match self.ambient_variance { 141 ty::Variance::Contravariant | ty::Variance::Invariant => true, 142 ty::Variance::Covariant | ty::Variance::Bivariant => false, 143 } 144 } 145 146 /// Push a new outlives requirement into our output set of 147 /// constraints. push_outlives( &mut self, sup: ty::Region<'tcx>, sub: ty::Region<'tcx>, info: ty::VarianceDiagInfo<'tcx>, )148 fn push_outlives( 149 &mut self, 150 sup: ty::Region<'tcx>, 151 sub: ty::Region<'tcx>, 152 info: ty::VarianceDiagInfo<'tcx>, 153 ) { 154 debug!("push_outlives({:?}: {:?})", sup, sub); 155 156 self.delegate.push_outlives(sup, sub, info); 157 } 158 159 /// Relate a type inference variable with a value type. This works 160 /// by creating a "generalization" G of the value where all the 161 /// lifetimes are replaced with fresh inference values. This 162 /// generalization G becomes the value of the inference variable, 163 /// and is then related in turn to the value. So e.g. if you had 164 /// `vid = ?0` and `value = &'a u32`, we might first instantiate 165 /// `?0` to a type like `&'0 u32` where `'0` is a fresh variable, 166 /// and then relate `&'0 u32` with `&'a u32` (resulting in 167 /// relations between `'0` and `'a`). 168 /// 169 /// The variable `pair` can be either a `(vid, ty)` or `(ty, vid)` 170 /// -- in other words, it is always an (unresolved) inference 171 /// variable `vid` and a type `ty` that are being related, but the 172 /// vid may appear either as the "a" type or the "b" type, 173 /// depending on where it appears in the tuple. The trait 174 /// `VidValuePair` lets us work with the vid/type while preserving 175 /// the "sidedness" when necessary -- the sidedness is relevant in 176 /// particular for the variance and set of in-scope things. relate_ty_var<PAIR: VidValuePair<'tcx>>( &mut self, pair: PAIR, ) -> RelateResult<'tcx, Ty<'tcx>>177 fn relate_ty_var<PAIR: VidValuePair<'tcx>>( 178 &mut self, 179 pair: PAIR, 180 ) -> RelateResult<'tcx, Ty<'tcx>> { 181 debug!("relate_ty_var({:?})", pair); 182 183 let vid = pair.vid(); 184 let value_ty = pair.value_ty(); 185 186 // FIXME(invariance) -- this logic assumes invariance, but that is wrong. 187 // This only presently applies to chalk integration, as NLL 188 // doesn't permit type variables to appear on both sides (and 189 // doesn't use lazy norm). 190 match *value_ty.kind() { 191 ty::Infer(ty::TyVar(value_vid)) => { 192 // Two type variables: just equate them. 193 self.infcx.inner.borrow_mut().type_variables().equate(vid, value_vid); 194 return Ok(value_ty); 195 } 196 197 _ => (), 198 } 199 200 let generalized_ty = self.generalize(value_ty, vid)?; 201 debug!("relate_ty_var: generalized_ty = {:?}", generalized_ty); 202 203 if D::forbid_inference_vars() { 204 // In NLL, we don't have type inference variables 205 // floating around, so we can do this rather imprecise 206 // variant of the occurs-check. 207 assert!(!generalized_ty.has_non_region_infer()); 208 } 209 210 self.infcx.inner.borrow_mut().type_variables().instantiate(vid, generalized_ty); 211 212 // Relate the generalized kind to the original one. 213 let result = pair.relate_generalized_ty(self, generalized_ty); 214 215 debug!("relate_ty_var: complete, result = {:?}", result); 216 result 217 } 218 generalize(&mut self, ty: Ty<'tcx>, for_vid: ty::TyVid) -> RelateResult<'tcx, Ty<'tcx>>219 fn generalize(&mut self, ty: Ty<'tcx>, for_vid: ty::TyVid) -> RelateResult<'tcx, Ty<'tcx>> { 220 let Generalization { value: ty, needs_wf: _ } = generalize::generalize( 221 self.infcx, 222 &mut self.delegate, 223 ty, 224 for_vid, 225 self.ambient_variance, 226 )?; 227 Ok(ty) 228 } 229 relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>>230 fn relate_opaques(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { 231 let (a, b) = if self.a_is_expected() { (a, b) } else { (b, a) }; 232 let mut generalize = |ty, ty_is_expected| { 233 let var = self.infcx.next_ty_var_id_in_universe( 234 TypeVariableOrigin { 235 kind: TypeVariableOriginKind::MiscVariable, 236 span: self.delegate.span(), 237 }, 238 ty::UniverseIndex::ROOT, 239 ); 240 if ty_is_expected { 241 self.relate_ty_var((ty, var)) 242 } else { 243 self.relate_ty_var((var, ty)) 244 } 245 }; 246 let (a, b) = match (a.kind(), b.kind()) { 247 (&ty::Alias(ty::Opaque, ..), _) => (a, generalize(b, false)?), 248 (_, &ty::Alias(ty::Opaque, ..)) => (generalize(a, true)?, b), 249 _ => unreachable!(), 250 }; 251 let cause = ObligationCause::dummy_with_span(self.delegate.span()); 252 let obligations = self 253 .infcx 254 .handle_opaque_type(a, b, true, &cause, self.delegate.param_env())? 255 .obligations; 256 self.delegate.register_obligations(obligations); 257 trace!(a = ?a.kind(), b = ?b.kind(), "opaque type instantiated"); 258 Ok(a) 259 } 260 261 #[instrument(skip(self), level = "debug")] instantiate_binder_with_placeholders<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T where T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,262 fn instantiate_binder_with_placeholders<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T 263 where 264 T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy, 265 { 266 if let Some(inner) = binder.no_bound_vars() { 267 return inner; 268 } 269 270 let mut next_region = { 271 let nll_delegate = &mut self.delegate; 272 let mut lazy_universe = None; 273 274 move |br: ty::BoundRegion| { 275 // The first time this closure is called, create a 276 // new universe for the placeholders we will make 277 // from here out. 278 let universe = lazy_universe.unwrap_or_else(|| { 279 let universe = nll_delegate.create_next_universe(); 280 lazy_universe = Some(universe); 281 universe 282 }); 283 284 let placeholder = ty::PlaceholderRegion { universe, bound: br }; 285 debug!(?placeholder); 286 let placeholder_reg = nll_delegate.next_placeholder_region(placeholder); 287 debug!(?placeholder_reg); 288 289 placeholder_reg 290 } 291 }; 292 293 let delegate = FnMutDelegate { 294 regions: &mut next_region, 295 types: &mut |_bound_ty: ty::BoundTy| { 296 unreachable!("we only replace regions in nll_relate, not types") 297 }, 298 consts: &mut |_bound_var: ty::BoundVar, _ty| { 299 unreachable!("we only replace regions in nll_relate, not consts") 300 }, 301 }; 302 303 let replaced = self.infcx.tcx.replace_bound_vars_uncached(binder, delegate); 304 debug!(?replaced); 305 306 replaced 307 } 308 309 #[instrument(skip(self), level = "debug")] instantiate_binder_with_existentials<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T where T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy,310 fn instantiate_binder_with_existentials<T>(&mut self, binder: ty::Binder<'tcx, T>) -> T 311 where 312 T: ty::TypeFoldable<TyCtxt<'tcx>> + Copy, 313 { 314 if let Some(inner) = binder.no_bound_vars() { 315 return inner; 316 } 317 318 let mut next_region = { 319 let nll_delegate = &mut self.delegate; 320 let mut reg_map = FxHashMap::default(); 321 322 move |br: ty::BoundRegion| { 323 if let Some(ex_reg_var) = reg_map.get(&br) { 324 return *ex_reg_var; 325 } else { 326 let ex_reg_var = 327 nll_delegate.next_existential_region_var(true, br.kind.get_name()); 328 debug!(?ex_reg_var); 329 reg_map.insert(br, ex_reg_var); 330 331 ex_reg_var 332 } 333 } 334 }; 335 336 let delegate = FnMutDelegate { 337 regions: &mut next_region, 338 types: &mut |_bound_ty: ty::BoundTy| { 339 unreachable!("we only replace regions in nll_relate, not types") 340 }, 341 consts: &mut |_bound_var: ty::BoundVar, _ty| { 342 unreachable!("we only replace regions in nll_relate, not consts") 343 }, 344 }; 345 346 let replaced = self.infcx.tcx.replace_bound_vars_uncached(binder, delegate); 347 debug!(?replaced); 348 349 replaced 350 } 351 } 352 353 /// When we instantiate an inference variable with a value in 354 /// `relate_ty_var`, we always have the pair of a `TyVid` and a `Ty`, 355 /// but the ordering may vary (depending on whether the inference 356 /// variable was found on the `a` or `b` sides). Therefore, this trait 357 /// allows us to factor out common code, while preserving the order 358 /// when needed. 359 trait VidValuePair<'tcx>: Debug { 360 /// Extract the inference variable (which could be either the 361 /// first or second part of the tuple). vid(&self) -> ty::TyVid362 fn vid(&self) -> ty::TyVid; 363 364 /// Extract the value it is being related to (which will be the 365 /// opposite part of the tuple from the vid). value_ty(&self) -> Ty<'tcx>366 fn value_ty(&self) -> Ty<'tcx>; 367 368 /// Given a generalized type G that should replace the vid, relate 369 /// G to the value, putting G on whichever side the vid would have 370 /// appeared. relate_generalized_ty<D>( &self, relate: &mut TypeRelating<'_, 'tcx, D>, generalized_ty: Ty<'tcx>, ) -> RelateResult<'tcx, Ty<'tcx>> where D: TypeRelatingDelegate<'tcx>371 fn relate_generalized_ty<D>( 372 &self, 373 relate: &mut TypeRelating<'_, 'tcx, D>, 374 generalized_ty: Ty<'tcx>, 375 ) -> RelateResult<'tcx, Ty<'tcx>> 376 where 377 D: TypeRelatingDelegate<'tcx>; 378 } 379 380 impl<'tcx> VidValuePair<'tcx> for (ty::TyVid, Ty<'tcx>) { vid(&self) -> ty::TyVid381 fn vid(&self) -> ty::TyVid { 382 self.0 383 } 384 value_ty(&self) -> Ty<'tcx>385 fn value_ty(&self) -> Ty<'tcx> { 386 self.1 387 } 388 relate_generalized_ty<D>( &self, relate: &mut TypeRelating<'_, 'tcx, D>, generalized_ty: Ty<'tcx>, ) -> RelateResult<'tcx, Ty<'tcx>> where D: TypeRelatingDelegate<'tcx>,389 fn relate_generalized_ty<D>( 390 &self, 391 relate: &mut TypeRelating<'_, 'tcx, D>, 392 generalized_ty: Ty<'tcx>, 393 ) -> RelateResult<'tcx, Ty<'tcx>> 394 where 395 D: TypeRelatingDelegate<'tcx>, 396 { 397 relate.relate(generalized_ty, self.value_ty()) 398 } 399 } 400 401 // In this case, the "vid" is the "b" type. 402 impl<'tcx> VidValuePair<'tcx> for (Ty<'tcx>, ty::TyVid) { vid(&self) -> ty::TyVid403 fn vid(&self) -> ty::TyVid { 404 self.1 405 } 406 value_ty(&self) -> Ty<'tcx>407 fn value_ty(&self) -> Ty<'tcx> { 408 self.0 409 } 410 relate_generalized_ty<D>( &self, relate: &mut TypeRelating<'_, 'tcx, D>, generalized_ty: Ty<'tcx>, ) -> RelateResult<'tcx, Ty<'tcx>> where D: TypeRelatingDelegate<'tcx>,411 fn relate_generalized_ty<D>( 412 &self, 413 relate: &mut TypeRelating<'_, 'tcx, D>, 414 generalized_ty: Ty<'tcx>, 415 ) -> RelateResult<'tcx, Ty<'tcx>> 416 where 417 D: TypeRelatingDelegate<'tcx>, 418 { 419 relate.relate(self.value_ty(), generalized_ty) 420 } 421 } 422 423 impl<'tcx, D> TypeRelation<'tcx> for TypeRelating<'_, 'tcx, D> 424 where 425 D: TypeRelatingDelegate<'tcx>, 426 { tcx(&self) -> TyCtxt<'tcx>427 fn tcx(&self) -> TyCtxt<'tcx> { 428 self.infcx.tcx 429 } 430 param_env(&self) -> ty::ParamEnv<'tcx>431 fn param_env(&self) -> ty::ParamEnv<'tcx> { 432 self.delegate.param_env() 433 } 434 tag(&self) -> &'static str435 fn tag(&self) -> &'static str { 436 "nll::subtype" 437 } 438 a_is_expected(&self) -> bool439 fn a_is_expected(&self) -> bool { 440 true 441 } 442 443 #[instrument(skip(self, info), level = "trace", ret)] relate_with_variance<T: Relate<'tcx>>( &mut self, variance: ty::Variance, info: ty::VarianceDiagInfo<'tcx>, a: T, b: T, ) -> RelateResult<'tcx, T>444 fn relate_with_variance<T: Relate<'tcx>>( 445 &mut self, 446 variance: ty::Variance, 447 info: ty::VarianceDiagInfo<'tcx>, 448 a: T, 449 b: T, 450 ) -> RelateResult<'tcx, T> { 451 let old_ambient_variance = self.ambient_variance; 452 self.ambient_variance = self.ambient_variance.xform(variance); 453 self.ambient_variance_info = self.ambient_variance_info.xform(info); 454 455 debug!(?self.ambient_variance); 456 // In a bivariant context this always succeeds. 457 let r = 458 if self.ambient_variance == ty::Variance::Bivariant { a } else { self.relate(a, b)? }; 459 460 self.ambient_variance = old_ambient_variance; 461 462 Ok(r) 463 } 464 465 #[instrument(skip(self), level = "debug")] tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>>466 fn tys(&mut self, a: Ty<'tcx>, mut b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { 467 let infcx = self.infcx; 468 469 let a = self.infcx.shallow_resolve(a); 470 471 if !D::forbid_inference_vars() { 472 b = self.infcx.shallow_resolve(b); 473 } 474 475 if a == b { 476 return Ok(a); 477 } 478 479 match (a.kind(), b.kind()) { 480 (_, &ty::Infer(ty::TyVar(vid))) => { 481 if D::forbid_inference_vars() { 482 // Forbid inference variables in the RHS. 483 bug!("unexpected inference var {:?}", b) 484 } else { 485 self.relate_ty_var((a, vid)) 486 } 487 } 488 489 (&ty::Infer(ty::TyVar(vid)), _) => self.relate_ty_var((vid, b)), 490 491 ( 492 &ty::Alias(ty::Opaque, ty::AliasTy { def_id: a_def_id, .. }), 493 &ty::Alias(ty::Opaque, ty::AliasTy { def_id: b_def_id, .. }), 494 ) if a_def_id == b_def_id || infcx.next_trait_solver() => { 495 infcx.super_combine_tys(self, a, b).or_else(|err| { 496 // This behavior is only there for the old solver, the new solver 497 // shouldn't ever fail. Instead, it unconditionally emits an 498 // alias-relate goal. 499 assert!(!self.infcx.next_trait_solver()); 500 self.tcx().sess.delay_span_bug( 501 self.delegate.span(), 502 "failure to relate an opaque to itself should result in an error later on", 503 ); 504 if a_def_id.is_local() { self.relate_opaques(a, b) } else { Err(err) } 505 }) 506 } 507 (&ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }), _) 508 | (_, &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. })) 509 if def_id.is_local() && !self.infcx.next_trait_solver() => 510 { 511 self.relate_opaques(a, b) 512 } 513 514 _ => { 515 debug!(?a, ?b, ?self.ambient_variance); 516 517 // Will also handle unification of `IntVar` and `FloatVar`. 518 self.infcx.super_combine_tys(self, a, b) 519 } 520 } 521 } 522 523 #[instrument(skip(self), level = "trace")] regions( &mut self, a: ty::Region<'tcx>, b: ty::Region<'tcx>, ) -> RelateResult<'tcx, ty::Region<'tcx>>524 fn regions( 525 &mut self, 526 a: ty::Region<'tcx>, 527 b: ty::Region<'tcx>, 528 ) -> RelateResult<'tcx, ty::Region<'tcx>> { 529 debug!(?self.ambient_variance); 530 531 if self.ambient_covariance() { 532 // Covariant: &'a u8 <: &'b u8. Hence, `'a: 'b`. 533 self.push_outlives(a, b, self.ambient_variance_info); 534 } 535 536 if self.ambient_contravariance() { 537 // Contravariant: &'b u8 <: &'a u8. Hence, `'b: 'a`. 538 self.push_outlives(b, a, self.ambient_variance_info); 539 } 540 541 Ok(a) 542 } 543 consts( &mut self, a: ty::Const<'tcx>, mut b: ty::Const<'tcx>, ) -> RelateResult<'tcx, ty::Const<'tcx>>544 fn consts( 545 &mut self, 546 a: ty::Const<'tcx>, 547 mut b: ty::Const<'tcx>, 548 ) -> RelateResult<'tcx, ty::Const<'tcx>> { 549 let a = self.infcx.shallow_resolve(a); 550 551 if !D::forbid_inference_vars() { 552 b = self.infcx.shallow_resolve(b); 553 } 554 555 match b.kind() { 556 ty::ConstKind::Infer(InferConst::Var(_)) if D::forbid_inference_vars() => { 557 // Forbid inference variables in the RHS. 558 self.infcx.tcx.sess.delay_span_bug( 559 self.delegate.span(), 560 format!("unexpected inference var {:?}", b,), 561 ); 562 Ok(a) 563 } 564 // FIXME(invariance): see the related FIXME above. 565 _ => self.infcx.super_combine_consts(self, a, b), 566 } 567 } 568 569 #[instrument(skip(self), level = "trace")] binders<T>( &mut self, a: ty::Binder<'tcx, T>, b: ty::Binder<'tcx, T>, ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> where T: Relate<'tcx>,570 fn binders<T>( 571 &mut self, 572 a: ty::Binder<'tcx, T>, 573 b: ty::Binder<'tcx, T>, 574 ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> 575 where 576 T: Relate<'tcx>, 577 { 578 // We want that 579 // 580 // ``` 581 // for<'a> fn(&'a u32) -> &'a u32 <: 582 // fn(&'b u32) -> &'b u32 583 // ``` 584 // 585 // but not 586 // 587 // ``` 588 // fn(&'a u32) -> &'a u32 <: 589 // for<'b> fn(&'b u32) -> &'b u32 590 // ``` 591 // 592 // We therefore proceed as follows: 593 // 594 // - Instantiate binders on `b` universally, yielding a universe U1. 595 // - Instantiate binders on `a` existentially in U1. 596 597 debug!(?self.ambient_variance); 598 599 if let (Some(a), Some(b)) = (a.no_bound_vars(), b.no_bound_vars()) { 600 // Fast path for the common case. 601 self.relate(a, b)?; 602 return Ok(ty::Binder::dummy(a)); 603 } 604 605 if self.ambient_covariance() { 606 // Covariance, so we want `for<..> A <: for<..> B` -- 607 // therefore we compare any instantiation of A (i.e., A 608 // instantiated with existentials) against every 609 // instantiation of B (i.e., B instantiated with 610 // universals). 611 612 // Reset the ambient variance to covariant. This is needed 613 // to correctly handle cases like 614 // 615 // for<'a> fn(&'a u32, &'a u32) == for<'b, 'c> fn(&'b u32, &'c u32) 616 // 617 // Somewhat surprisingly, these two types are actually 618 // **equal**, even though the one on the right looks more 619 // polymorphic. The reason is due to subtyping. To see it, 620 // consider that each function can call the other: 621 // 622 // - The left function can call the right with `'b` and 623 // `'c` both equal to `'a` 624 // 625 // - The right function can call the left with `'a` set to 626 // `{P}`, where P is the point in the CFG where the call 627 // itself occurs. Note that `'b` and `'c` must both 628 // include P. At the point, the call works because of 629 // subtyping (i.e., `&'b u32 <: &{P} u32`). 630 let variance = std::mem::replace(&mut self.ambient_variance, ty::Variance::Covariant); 631 632 // Note: the order here is important. Create the placeholders first, otherwise 633 // we assign the wrong universe to the existential! 634 let b_replaced = self.instantiate_binder_with_placeholders(b); 635 let a_replaced = self.instantiate_binder_with_existentials(a); 636 637 self.relate(a_replaced, b_replaced)?; 638 639 self.ambient_variance = variance; 640 } 641 642 if self.ambient_contravariance() { 643 // Contravariance, so we want `for<..> A :> for<..> B` 644 // -- therefore we compare every instantiation of A (i.e., 645 // A instantiated with universals) against any 646 // instantiation of B (i.e., B instantiated with 647 // existentials). Opposite of above. 648 649 // Reset ambient variance to contravariance. See the 650 // covariant case above for an explanation. 651 let variance = 652 std::mem::replace(&mut self.ambient_variance, ty::Variance::Contravariant); 653 654 let a_replaced = self.instantiate_binder_with_placeholders(a); 655 let b_replaced = self.instantiate_binder_with_existentials(b); 656 657 self.relate(a_replaced, b_replaced)?; 658 659 self.ambient_variance = variance; 660 } 661 662 Ok(a) 663 } 664 } 665 666 impl<'tcx, D> ObligationEmittingRelation<'tcx> for TypeRelating<'_, 'tcx, D> 667 where 668 D: TypeRelatingDelegate<'tcx>, 669 { register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>)670 fn register_predicates(&mut self, obligations: impl IntoIterator<Item: ty::ToPredicate<'tcx>>) { 671 self.delegate.register_obligations( 672 obligations 673 .into_iter() 674 .map(|to_pred| { 675 Obligation::new(self.tcx(), ObligationCause::dummy(), self.param_env(), to_pred) 676 }) 677 .collect(), 678 ); 679 } 680 register_obligations(&mut self, obligations: PredicateObligations<'tcx>)681 fn register_obligations(&mut self, obligations: PredicateObligations<'tcx>) { 682 self.delegate.register_obligations(obligations); 683 } 684 alias_relate_direction(&self) -> ty::AliasRelationDirection685 fn alias_relate_direction(&self) -> ty::AliasRelationDirection { 686 unreachable!("manually overridden to handle ty::Variance::Contravariant ambient variance") 687 } 688 register_type_relate_obligation(&mut self, a: Ty<'tcx>, b: Ty<'tcx>)689 fn register_type_relate_obligation(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) { 690 self.register_predicates([ty::Binder::dummy(match self.ambient_variance { 691 ty::Variance::Covariant => ty::PredicateKind::AliasRelate( 692 a.into(), 693 b.into(), 694 ty::AliasRelationDirection::Subtype, 695 ), 696 // a :> b is b <: a 697 ty::Variance::Contravariant => ty::PredicateKind::AliasRelate( 698 b.into(), 699 a.into(), 700 ty::AliasRelationDirection::Subtype, 701 ), 702 ty::Variance::Invariant => ty::PredicateKind::AliasRelate( 703 a.into(), 704 b.into(), 705 ty::AliasRelationDirection::Equate, 706 ), 707 // FIXME(deferred_projection_equality): Implement this when we trigger it. 708 // Probably just need to do nothing here. 709 ty::Variance::Bivariant => unreachable!(), 710 })]); 711 } 712 } 713