compiler/rustc_middle/src/ty/relate.rs

   1 //! Generalized type relating mechanism.
   2 //!
   3 //! A type relation `R` relates a pair of values `(A, B)`. `A and B` are usually
   4 //! types or regions but can be other things. Examples of type relations are
   5 //! subtyping, type equality, etc.
   6
   7 use crate::ty::error::{ExpectedFound, TypeError};
   8 use crate::ty::{self, ImplSubject, Term, TermKind, Ty, TyCtxt, TypeFoldable};
   9 use crate::ty::{GenericArg, GenericArgKind, SubstsRef};
  10 use rustc_hir as ast;
  11 use rustc_hir::def_id::DefId;
  12 use rustc_span::DUMMY_SP;
  13 use rustc_target::spec::abi;
  14 use std::iter;
  15
  16 pub type RelateResult<'tcx, T> = Result<T, TypeError<'tcx>>;
  17
  18 #[derive(Clone, Debug)]
  19 pub enum Cause {
  20     ExistentialRegionBound, // relating an existential region bound
  21 }
  22
  23 pub trait TypeRelation<'tcx>: Sized {
  24     fn tcx(&self) -> TyCtxt<'tcx>;
  25
  26     fn intercrate(&self) -> bool;
  27
  28     fn param_env(&self) -> ty::ParamEnv<'tcx>;
  29
  30     /// Returns a static string we can use for printouts.
  31     fn tag(&self) -> &'static str;
  32
  33     /// Returns `true` if the value `a` is the "expected" type in the
  34     /// relation. Just affects error messages.
  35     fn a_is_expected(&self) -> bool;
  36
  37     fn with_cause<F, R>(&mut self, _cause: Cause, f: F) -> R
  38     where
  39         F: FnOnce(&mut Self) -> R,
  40     {
  41         f(self)
  42     }
  43
  44     /// Generic relation routine suitable for most anything.
  45     fn relate<T: Relate<'tcx>>(&mut self, a: T, b: T) -> RelateResult<'tcx, T> {
  46         Relate::relate(self, a, b)
  47     }
  48
  49     /// Relate the two substitutions for the given item. The default
  50     /// is to look up the variance for the item and proceed
  51     /// accordingly.
  52     fn relate_item_substs(
  53         &mut self,
  54         item_def_id: DefId,
  55         a_subst: SubstsRef<'tcx>,
  56         b_subst: SubstsRef<'tcx>,
  57     ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
  58         debug!(
  59             "relate_item_substs(item_def_id={:?}, a_subst={:?}, b_subst={:?})",
  60             item_def_id, a_subst, b_subst
  61         );
  62
  63         let tcx = self.tcx();
  64         let opt_variances = tcx.variances_of(item_def_id);
  65         relate_substs_with_variances(self, item_def_id, opt_variances, a_subst, b_subst, true)
  66     }
  67
  68     /// Switch variance for the purpose of relating `a` and `b`.
  69     fn relate_with_variance<T: Relate<'tcx>>(
  70         &mut self,
  71         variance: ty::Variance,
  72         info: ty::VarianceDiagInfo<'tcx>,
  73         a: T,
  74         b: T,
  75     ) -> RelateResult<'tcx, T>;
  76
  77     // Overridable relations. You shouldn't typically call these
  78     // directly, instead call `relate()`, which in turn calls
  79     // these. This is both more uniform but also allows us to add
  80     // additional hooks for other types in the future if needed
  81     // without making older code, which called `relate`, obsolete.
  82
  83     fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>>;
  84
  85     fn regions(
  86         &mut self,
  87         a: ty::Region<'tcx>,
  88         b: ty::Region<'tcx>,
  89     ) -> RelateResult<'tcx, ty::Region<'tcx>>;
  90
  91     fn consts(
  92         &mut self,
  93         a: ty::Const<'tcx>,
  94         b: ty::Const<'tcx>,
  95     ) -> RelateResult<'tcx, ty::Const<'tcx>>;
  96
  97     fn binders<T>(
  98         &mut self,
  99         a: ty::Binder<'tcx, T>,
 100         b: ty::Binder<'tcx, T>,
 101     ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
 102     where
 103         T: Relate<'tcx>;
 104 }
 105
 106 pub trait Relate<'tcx>: TypeFoldable<'tcx> + Copy {
 107     fn relate<R: TypeRelation<'tcx>>(
 108         relation: &mut R,
 109         a: Self,
 110         b: Self,
 111     ) -> RelateResult<'tcx, Self>;
 112 }
 113
 114 ///////////////////////////////////////////////////////////////////////////
 115 // Relate impls
 116
 117 pub fn relate_type_and_mut<'tcx, R: TypeRelation<'tcx>>(
 118     relation: &mut R,
 119     a: ty::TypeAndMut<'tcx>,
 120     b: ty::TypeAndMut<'tcx>,
 121     base_ty: Ty<'tcx>,
 122 ) -> RelateResult<'tcx, ty::TypeAndMut<'tcx>> {
 123     debug!("{}.mts({:?}, {:?})", relation.tag(), a, b);
 124     if a.mutbl != b.mutbl {
 125         Err(TypeError::Mutability)
 126     } else {
 127         let mutbl = a.mutbl;
 128         let (variance, info) = match mutbl {
 129             ast::Mutability::Not => (ty::Covariant, ty::VarianceDiagInfo::None),
 130             ast::Mutability::Mut => {
 131                 (ty::Invariant, ty::VarianceDiagInfo::Invariant { ty: base_ty, param_index: 0 })
 132             }
 133         };
 134         let ty = relation.relate_with_variance(variance, info, a.ty, b.ty)?;
 135         Ok(ty::TypeAndMut { ty, mutbl })
 136     }
 137 }
 138
 139 #[inline]
 140 pub fn relate_substs<'tcx, R: TypeRelation<'tcx>>(
 141     relation: &mut R,
 142     a_subst: SubstsRef<'tcx>,
 143     b_subst: SubstsRef<'tcx>,
 144 ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
 145     relation.tcx().mk_substs(iter::zip(a_subst, b_subst).map(|(a, b)| {
 146         relation.relate_with_variance(ty::Invariant, ty::VarianceDiagInfo::default(), a, b)
 147     }))
 148 }
 149
 150 pub fn relate_substs_with_variances<'tcx, R: TypeRelation<'tcx>>(
 151     relation: &mut R,
 152     ty_def_id: DefId,
 153     variances: &[ty::Variance],
 154     a_subst: SubstsRef<'tcx>,
 155     b_subst: SubstsRef<'tcx>,
 156     fetch_ty_for_diag: bool,
 157 ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
 158     let tcx = relation.tcx();
 159
 160     let mut cached_ty = None;
 161     let params = iter::zip(a_subst, b_subst).enumerate().map(|(i, (a, b))| {
 162         let variance = variances[i];
 163         let variance_info = if variance == ty::Invariant && fetch_ty_for_diag {
 164             let ty =
 165                 *cached_ty.get_or_insert_with(|| tcx.bound_type_of(ty_def_id).subst(tcx, a_subst));
 166             ty::VarianceDiagInfo::Invariant { ty, param_index: i.try_into().unwrap() }
 167         } else {
 168             ty::VarianceDiagInfo::default()
 169         };
 170         relation.relate_with_variance(variance, variance_info, a, b)
 171     });
 172
 173     tcx.mk_substs(params)
 174 }
 175
 176 impl<'tcx> Relate<'tcx> for ty::FnSig<'tcx> {
 177     fn relate<R: TypeRelation<'tcx>>(
 178         relation: &mut R,
 179         a: ty::FnSig<'tcx>,
 180         b: ty::FnSig<'tcx>,
 181     ) -> RelateResult<'tcx, ty::FnSig<'tcx>> {
 182         let tcx = relation.tcx();
 183
 184         if a.c_variadic != b.c_variadic {
 185             return Err(TypeError::VariadicMismatch(expected_found(
 186                 relation,
 187                 a.c_variadic,
 188                 b.c_variadic,
 189             )));
 190         }
 191         let unsafety = relation.relate(a.unsafety, b.unsafety)?;
 192         let abi = relation.relate(a.abi, b.abi)?;
 193
 194         if a.inputs().len() != b.inputs().len() {
 195             return Err(TypeError::ArgCount);
 196         }
 197
 198         let inputs_and_output = iter::zip(a.inputs(), b.inputs())
 199             .map(|(&a, &b)| ((a, b), false))
 200             .chain(iter::once(((a.output(), b.output()), true)))
 201             .map(|((a, b), is_output)| {
 202                 if is_output {
 203                     relation.relate(a, b)
 204                 } else {
 205                     relation.relate_with_variance(
 206                         ty::Contravariant,
 207                         ty::VarianceDiagInfo::default(),
 208                         a,
 209                         b,
 210                     )
 211                 }
 212             })
 213             .enumerate()
 214             .map(|(i, r)| match r {
 215                 Err(TypeError::Sorts(exp_found) | TypeError::ArgumentSorts(exp_found, _)) => {
 216                     Err(TypeError::ArgumentSorts(exp_found, i))
 217                 }
 218                 Err(TypeError::Mutability | TypeError::ArgumentMutability(_)) => {
 219                     Err(TypeError::ArgumentMutability(i))
 220                 }
 221                 r => r,
 222             });
 223         Ok(ty::FnSig {
 224             inputs_and_output: tcx.mk_type_list(inputs_and_output)?,
 225             c_variadic: a.c_variadic,
 226             unsafety,
 227             abi,
 228         })
 229     }
 230 }
 231
 232 impl<'tcx> Relate<'tcx> for ty::BoundConstness {
 233     fn relate<R: TypeRelation<'tcx>>(
 234         relation: &mut R,
 235         a: ty::BoundConstness,
 236         b: ty::BoundConstness,
 237     ) -> RelateResult<'tcx, ty::BoundConstness> {
 238         if a != b {
 239             Err(TypeError::ConstnessMismatch(expected_found(relation, a, b)))
 240         } else {
 241             Ok(a)
 242         }
 243     }
 244 }
 245
 246 impl<'tcx> Relate<'tcx> for ast::Unsafety {
 247     fn relate<R: TypeRelation<'tcx>>(
 248         relation: &mut R,
 249         a: ast::Unsafety,
 250         b: ast::Unsafety,
 251     ) -> RelateResult<'tcx, ast::Unsafety> {
 252         if a != b {
 253             Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
 254         } else {
 255             Ok(a)
 256         }
 257     }
 258 }
 259
 260 impl<'tcx> Relate<'tcx> for abi::Abi {
 261     fn relate<R: TypeRelation<'tcx>>(
 262         relation: &mut R,
 263         a: abi::Abi,
 264         b: abi::Abi,
 265     ) -> RelateResult<'tcx, abi::Abi> {
 266         if a == b { Ok(a) } else { Err(TypeError::AbiMismatch(expected_found(relation, a, b))) }
 267     }
 268 }
 269
 270 impl<'tcx> Relate<'tcx> for ty::ProjectionTy<'tcx> {
 271     fn relate<R: TypeRelation<'tcx>>(
 272         relation: &mut R,
 273         a: ty::ProjectionTy<'tcx>,
 274         b: ty::ProjectionTy<'tcx>,
 275     ) -> RelateResult<'tcx, ty::ProjectionTy<'tcx>> {
 276         if a.item_def_id != b.item_def_id {
 277             Err(TypeError::ProjectionMismatched(expected_found(
 278                 relation,
 279                 a.item_def_id,
 280                 b.item_def_id,
 281             )))
 282         } else {
 283             let substs = relation.relate(a.substs, b.substs)?;
 284             Ok(ty::ProjectionTy { item_def_id: a.item_def_id, substs: &substs })
 285         }
 286     }
 287 }
 288
 289 impl<'tcx> Relate<'tcx> for ty::ExistentialProjection<'tcx> {
 290     fn relate<R: TypeRelation<'tcx>>(
 291         relation: &mut R,
 292         a: ty::ExistentialProjection<'tcx>,
 293         b: ty::ExistentialProjection<'tcx>,
 294     ) -> RelateResult<'tcx, ty::ExistentialProjection<'tcx>> {
 295         if a.item_def_id != b.item_def_id {
 296             Err(TypeError::ProjectionMismatched(expected_found(
 297                 relation,
 298                 a.item_def_id,
 299                 b.item_def_id,
 300             )))
 301         } else {
 302             let term = relation.relate_with_variance(
 303                 ty::Invariant,
 304                 ty::VarianceDiagInfo::default(),
 305                 a.term,
 306                 b.term,
 307             )?;
 308             let substs = relation.relate_with_variance(
 309                 ty::Invariant,
 310                 ty::VarianceDiagInfo::default(),
 311                 a.substs,
 312                 b.substs,
 313             )?;
 314             Ok(ty::ExistentialProjection { item_def_id: a.item_def_id, substs, term })
 315         }
 316     }
 317 }
 318
 319 impl<'tcx> Relate<'tcx> for ty::TraitRef<'tcx> {
 320     fn relate<R: TypeRelation<'tcx>>(
 321         relation: &mut R,
 322         a: ty::TraitRef<'tcx>,
 323         b: ty::TraitRef<'tcx>,
 324     ) -> RelateResult<'tcx, ty::TraitRef<'tcx>> {
 325         // Different traits cannot be related.
 326         if a.def_id != b.def_id {
 327             Err(TypeError::Traits(expected_found(relation, a.def_id, b.def_id)))
 328         } else {
 329             let substs = relate_substs(relation, a.substs, b.substs)?;
 330             Ok(ty::TraitRef { def_id: a.def_id, substs })
 331         }
 332     }
 333 }
 334
 335 impl<'tcx> Relate<'tcx> for ty::ExistentialTraitRef<'tcx> {
 336     fn relate<R: TypeRelation<'tcx>>(
 337         relation: &mut R,
 338         a: ty::ExistentialTraitRef<'tcx>,
 339         b: ty::ExistentialTraitRef<'tcx>,
 340     ) -> RelateResult<'tcx, ty::ExistentialTraitRef<'tcx>> {
 341         // Different traits cannot be related.
 342         if a.def_id != b.def_id {
 343             Err(TypeError::Traits(expected_found(relation, a.def_id, b.def_id)))
 344         } else {
 345             let substs = relate_substs(relation, a.substs, b.substs)?;
 346             Ok(ty::ExistentialTraitRef { def_id: a.def_id, substs })
 347         }
 348     }
 349 }
 350
 351 #[derive(Copy, Debug, Clone, TypeFoldable, TypeVisitable)]
 352 struct GeneratorWitness<'tcx>(&'tcx ty::List<Ty<'tcx>>);
 353
 354 impl<'tcx> Relate<'tcx> for GeneratorWitness<'tcx> {
 355     fn relate<R: TypeRelation<'tcx>>(
 356         relation: &mut R,
 357         a: GeneratorWitness<'tcx>,
 358         b: GeneratorWitness<'tcx>,
 359     ) -> RelateResult<'tcx, GeneratorWitness<'tcx>> {
 360         assert_eq!(a.0.len(), b.0.len());
 361         let tcx = relation.tcx();
 362         let types = tcx.mk_type_list(iter::zip(a.0, b.0).map(|(a, b)| relation.relate(a, b)))?;
 363         Ok(GeneratorWitness(types))
 364     }
 365 }
 366
 367 impl<'tcx> Relate<'tcx> for ImplSubject<'tcx> {
 368     #[inline]
 369     fn relate<R: TypeRelation<'tcx>>(
 370         relation: &mut R,
 371         a: ImplSubject<'tcx>,
 372         b: ImplSubject<'tcx>,
 373     ) -> RelateResult<'tcx, ImplSubject<'tcx>> {
 374         match (a, b) {
 375             (ImplSubject::Trait(trait_ref_a), ImplSubject::Trait(trait_ref_b)) => {
 376                 let trait_ref = ty::TraitRef::relate(relation, trait_ref_a, trait_ref_b)?;
 377                 Ok(ImplSubject::Trait(trait_ref))
 378             }
 379             (ImplSubject::Inherent(ty_a), ImplSubject::Inherent(ty_b)) => {
 380                 let ty = Ty::relate(relation, ty_a, ty_b)?;
 381                 Ok(ImplSubject::Inherent(ty))
 382             }
 383             (ImplSubject::Trait(_), ImplSubject::Inherent(_))
 384             | (ImplSubject::Inherent(_), ImplSubject::Trait(_)) => {
 385                 bug!("can not relate TraitRef and Ty");
 386             }
 387         }
 388     }
 389 }
 390
 391 impl<'tcx> Relate<'tcx> for Ty<'tcx> {
 392     #[inline]
 393     fn relate<R: TypeRelation<'tcx>>(
 394         relation: &mut R,
 395         a: Ty<'tcx>,
 396         b: Ty<'tcx>,
 397     ) -> RelateResult<'tcx, Ty<'tcx>> {
 398         relation.tys(a, b)
 399     }
 400 }
 401
 402 /// The main "type relation" routine. Note that this does not handle
 403 /// inference artifacts, so you should filter those out before calling
 404 /// it.
 405 pub fn super_relate_tys<'tcx, R: TypeRelation<'tcx>>(
 406     relation: &mut R,
 407     a: Ty<'tcx>,
 408     b: Ty<'tcx>,
 409 ) -> RelateResult<'tcx, Ty<'tcx>> {
 410     let tcx = relation.tcx();
 411     debug!("super_relate_tys: a={:?} b={:?}", a, b);
 412     match (a.kind(), b.kind()) {
 413         (&ty::Infer(_), _) | (_, &ty::Infer(_)) => {
 414             // The caller should handle these cases!
 415             bug!("var types encountered in super_relate_tys")
 416         }
 417
 418         (ty::Bound(..), _) | (_, ty::Bound(..)) => {
 419             bug!("bound types encountered in super_relate_tys")
 420         }
 421
 422         (&ty::Error(_), _) | (_, &ty::Error(_)) => Ok(tcx.ty_error()),
 423
 424         (&ty::Never, _)
 425         | (&ty::Char, _)
 426         | (&ty::Bool, _)
 427         | (&ty::Int(_), _)
 428         | (&ty::Uint(_), _)
 429         | (&ty::Float(_), _)
 430         | (&ty::Str, _)
 431             if a == b =>
 432         {
 433             Ok(a)
 434         }
 435
 436         (&ty::Param(ref a_p), &ty::Param(ref b_p)) if a_p.index == b_p.index => Ok(a),
 437
 438         (ty::Placeholder(p1), ty::Placeholder(p2)) if p1 == p2 => Ok(a),
 439
 440         (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs)) if a_def == b_def => {
 441             let substs = relation.relate_item_substs(a_def.did(), a_substs, b_substs)?;
 442             Ok(tcx.mk_adt(a_def, substs))
 443         }
 444
 445         (&ty::Foreign(a_id), &ty::Foreign(b_id)) if a_id == b_id => Ok(tcx.mk_foreign(a_id)),
 446
 447         (&ty::Dynamic(a_obj, a_region, a_repr), &ty::Dynamic(b_obj, b_region, b_repr))
 448             if a_repr == b_repr =>
 449         {
 450             let region_bound = relation.with_cause(Cause::ExistentialRegionBound, |relation| {
 451                 relation.relate_with_variance(
 452                     ty::Contravariant,
 453                     ty::VarianceDiagInfo::default(),
 454                     a_region,
 455                     b_region,
 456                 )
 457             })?;
 458             Ok(tcx.mk_dynamic(relation.relate(a_obj, b_obj)?, region_bound, a_repr))
 459         }
 460
 461         (&ty::Generator(a_id, a_substs, movability), &ty::Generator(b_id, b_substs, _))
 462             if a_id == b_id =>
 463         {
 464             // All Generator types with the same id represent
 465             // the (anonymous) type of the same generator expression. So
 466             // all of their regions should be equated.
 467             let substs = relation.relate(a_substs, b_substs)?;
 468             Ok(tcx.mk_generator(a_id, substs, movability))
 469         }
 470
 471         (&ty::GeneratorWitness(a_types), &ty::GeneratorWitness(b_types)) => {
 472             // Wrap our types with a temporary GeneratorWitness struct
 473             // inside the binder so we can related them
 474             let a_types = a_types.map_bound(GeneratorWitness);
 475             let b_types = b_types.map_bound(GeneratorWitness);
 476             // Then remove the GeneratorWitness for the result
 477             let types = relation.relate(a_types, b_types)?.map_bound(|witness| witness.0);
 478             Ok(tcx.mk_generator_witness(types))
 479         }
 480
 481         (&ty::Closure(a_id, a_substs), &ty::Closure(b_id, b_substs)) if a_id == b_id => {
 482             // All Closure types with the same id represent
 483             // the (anonymous) type of the same closure expression. So
 484             // all of their regions should be equated.
 485             let substs = relation.relate(a_substs, b_substs)?;
 486             Ok(tcx.mk_closure(a_id, &substs))
 487         }
 488
 489         (&ty::RawPtr(a_mt), &ty::RawPtr(b_mt)) => {
 490             let mt = relate_type_and_mut(relation, a_mt, b_mt, a)?;
 491             Ok(tcx.mk_ptr(mt))
 492         }
 493
 494         (&ty::Ref(a_r, a_ty, a_mutbl), &ty::Ref(b_r, b_ty, b_mutbl)) => {
 495             let r = relation.relate_with_variance(
 496                 ty::Contravariant,
 497                 ty::VarianceDiagInfo::default(),
 498                 a_r,
 499                 b_r,
 500             )?;
 501             let a_mt = ty::TypeAndMut { ty: a_ty, mutbl: a_mutbl };
 502             let b_mt = ty::TypeAndMut { ty: b_ty, mutbl: b_mutbl };
 503             let mt = relate_type_and_mut(relation, a_mt, b_mt, a)?;
 504             Ok(tcx.mk_ref(r, mt))
 505         }
 506
 507         (&ty::Array(a_t, sz_a), &ty::Array(b_t, sz_b)) => {
 508             let t = relation.relate(a_t, b_t)?;
 509             match relation.relate(sz_a, sz_b) {
 510                 Ok(sz) => Ok(tcx.mk_ty(ty::Array(t, sz))),
 511                 Err(err) => {
 512                     // Check whether the lengths are both concrete/known values,
 513                     // but are unequal, for better diagnostics.
 514                     //
 515                     // It might seem dubious to eagerly evaluate these constants here,
 516                     // we however cannot end up with errors in `Relate` during both
 517                     // `type_of` and `predicates_of`. This means that evaluating the
 518                     // constants should not cause cycle errors here.
 519                     let sz_a = sz_a.try_eval_usize(tcx, relation.param_env());
 520                     let sz_b = sz_b.try_eval_usize(tcx, relation.param_env());
 521                     match (sz_a, sz_b) {
 522                         (Some(sz_a_val), Some(sz_b_val)) if sz_a_val != sz_b_val => Err(
 523                             TypeError::FixedArraySize(expected_found(relation, sz_a_val, sz_b_val)),
 524                         ),
 525                         _ => Err(err),
 526                     }
 527                 }
 528             }
 529         }
 530
 531         (&ty::Slice(a_t), &ty::Slice(b_t)) => {
 532             let t = relation.relate(a_t, b_t)?;
 533             Ok(tcx.mk_slice(t))
 534         }
 535
 536         (&ty::Tuple(as_), &ty::Tuple(bs)) => {
 537             if as_.len() == bs.len() {
 538                 Ok(tcx.mk_tup(iter::zip(as_, bs).map(|(a, b)| relation.relate(a, b)))?)
 539             } else if !(as_.is_empty() || bs.is_empty()) {
 540                 Err(TypeError::TupleSize(expected_found(relation, as_.len(), bs.len())))
 541             } else {
 542                 Err(TypeError::Sorts(expected_found(relation, a, b)))
 543             }
 544         }
 545
 546         (&ty::FnDef(a_def_id, a_substs), &ty::FnDef(b_def_id, b_substs))
 547             if a_def_id == b_def_id =>
 548         {
 549             let substs = relation.relate_item_substs(a_def_id, a_substs, b_substs)?;
 550             Ok(tcx.mk_fn_def(a_def_id, substs))
 551         }
 552
 553         (&ty::FnPtr(a_fty), &ty::FnPtr(b_fty)) => {
 554             let fty = relation.relate(a_fty, b_fty)?;
 555             Ok(tcx.mk_fn_ptr(fty))
 556         }
 557
 558         // these two are already handled downstream in case of lazy normalization
 559         (&ty::Projection(a_data), &ty::Projection(b_data)) => {
 560             let projection_ty = relation.relate(a_data, b_data)?;
 561             Ok(tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs))
 562         }
 563
 564         (&ty::Opaque(a_def_id, a_substs), &ty::Opaque(b_def_id, b_substs))
 565             if a_def_id == b_def_id =>
 566         {
 567             if relation.intercrate() {
 568                 // During coherence, opaque types should be treated as equal to each other, even if their generic params
 569                 // differ, as they could resolve to the same hidden type, even for different generic params.
 570                 Ok(a)
 571             } else {
 572                 let opt_variances = tcx.variances_of(a_def_id);
 573                 let substs = relate_substs_with_variances(
 574                     relation,
 575                     a_def_id,
 576                     opt_variances,
 577                     a_substs,
 578                     b_substs,
 579                     false, // do not fetch `type_of(a_def_id)`, as it will cause a cycle
 580                 )?;
 581                 Ok(tcx.mk_opaque(a_def_id, substs))
 582             }
 583         }
 584
 585         _ => Err(TypeError::Sorts(expected_found(relation, a, b))),
 586     }
 587 }
 588
 589 /// The main "const relation" routine. Note that this does not handle
 590 /// inference artifacts, so you should filter those out before calling
 591 /// it.
 592 pub fn super_relate_consts<'tcx, R: TypeRelation<'tcx>>(
 593     relation: &mut R,
 594     mut a: ty::Const<'tcx>,
 595     mut b: ty::Const<'tcx>,
 596 ) -> RelateResult<'tcx, ty::Const<'tcx>> {
 597     debug!("{}.super_relate_consts(a = {:?}, b = {:?})", relation.tag(), a, b);
 598     let tcx = relation.tcx();
 599
 600     let a_ty;
 601     let b_ty;
 602     if relation.tcx().features().adt_const_params {
 603         a_ty = tcx.normalize_erasing_regions(relation.param_env(), a.ty());
 604         b_ty = tcx.normalize_erasing_regions(relation.param_env(), b.ty());
 605     } else {
 606         a_ty = tcx.erase_regions(a.ty());
 607         b_ty = tcx.erase_regions(b.ty());
 608     }
 609     if a_ty != b_ty {
 610         relation.tcx().sess.delay_span_bug(
 611             DUMMY_SP,
 612             &format!("cannot relate constants of different types: {} != {}", a_ty, b_ty),
 613         );
 614     }
 615
 616     // HACK(const_generics): We still need to eagerly evaluate consts when
 617     // relating them because during `normalize_param_env_or_error`,
 618     // we may relate an evaluated constant in a obligation against
 619     // an unnormalized (i.e. unevaluated) const in the param-env.
 620     // FIXME(generic_const_exprs): Once we always lazily unify unevaluated constants
 621     // these `eval` calls can be removed.
 622     if !relation.tcx().features().generic_const_exprs {
 623         a = a.eval(tcx, relation.param_env());
 624         b = b.eval(tcx, relation.param_env());
 625     }
 626
 627     // Currently, the values that can be unified are primitive types,
 628     // and those that derive both `PartialEq` and `Eq`, corresponding
 629     // to structural-match types.
 630     let is_match = match (a.kind(), b.kind()) {
 631         (ty::ConstKind::Infer(_), _) | (_, ty::ConstKind::Infer(_)) => {
 632             // The caller should handle these cases!
 633             bug!("var types encountered in super_relate_consts: {:?} {:?}", a, b)
 634         }
 635
 636         (ty::ConstKind::Error(_), _) => return Ok(a),
 637         (_, ty::ConstKind::Error(_)) => return Ok(b),
 638
 639         (ty::ConstKind::Param(a_p), ty::ConstKind::Param(b_p)) => a_p.index == b_p.index,
 640         (ty::ConstKind::Placeholder(p1), ty::ConstKind::Placeholder(p2)) => p1 == p2,
 641         (ty::ConstKind::Value(a_val), ty::ConstKind::Value(b_val)) => a_val == b_val,
 642
 643         (ty::ConstKind::Unevaluated(au), ty::ConstKind::Unevaluated(bu))
 644             if tcx.features().generic_const_exprs =>
 645         {
 646             tcx.try_unify_abstract_consts(relation.param_env().and((au, bu)))
 647         }
 648
 649         // While this is slightly incorrect, it shouldn't matter for `min_const_generics`
 650         // and is the better alternative to waiting until `generic_const_exprs` can
 651         // be stabilized.
 652         (ty::ConstKind::Unevaluated(au), ty::ConstKind::Unevaluated(bu)) if au.def == bu.def => {
 653             let substs = relation.relate_with_variance(
 654                 ty::Variance::Invariant,
 655                 ty::VarianceDiagInfo::default(),
 656                 au.substs,
 657                 bu.substs,
 658             )?;
 659             return Ok(tcx.mk_const(
 660                 ty::ConstKind::Unevaluated(ty::UnevaluatedConst { def: au.def, substs }),
 661                 a.ty(),
 662             ));
 663         }
 664         _ => false,
 665     };
 666     if is_match { Ok(a) } else { Err(TypeError::ConstMismatch(expected_found(relation, a, b))) }
 667 }
 668
 669 impl<'tcx> Relate<'tcx> for &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>> {
 670     fn relate<R: TypeRelation<'tcx>>(
 671         relation: &mut R,
 672         a: Self,
 673         b: Self,
 674     ) -> RelateResult<'tcx, Self> {
 675         let tcx = relation.tcx();
 676
 677         // FIXME: this is wasteful, but want to do a perf run to see how slow it is.
 678         // We need to perform this deduplication as we sometimes generate duplicate projections
 679         // in `a`.
 680         let mut a_v: Vec<_> = a.into_iter().collect();
 681         let mut b_v: Vec<_> = b.into_iter().collect();
 682         // `skip_binder` here is okay because `stable_cmp` doesn't look at binders
 683         a_v.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder()));
 684         a_v.dedup();
 685         b_v.sort_by(|a, b| a.skip_binder().stable_cmp(tcx, &b.skip_binder()));
 686         b_v.dedup();
 687         if a_v.len() != b_v.len() {
 688             return Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)));
 689         }
 690
 691         let v = iter::zip(a_v, b_v).map(|(ep_a, ep_b)| {
 692             use crate::ty::ExistentialPredicate::*;
 693             match (ep_a.skip_binder(), ep_b.skip_binder()) {
 694                 (Trait(a), Trait(b)) => Ok(ep_a
 695                     .rebind(Trait(relation.relate(ep_a.rebind(a), ep_b.rebind(b))?.skip_binder()))),
 696                 (Projection(a), Projection(b)) => Ok(ep_a.rebind(Projection(
 697                     relation.relate(ep_a.rebind(a), ep_b.rebind(b))?.skip_binder(),
 698                 ))),
 699                 (AutoTrait(a), AutoTrait(b)) if a == b => Ok(ep_a.rebind(AutoTrait(a))),
 700                 _ => Err(TypeError::ExistentialMismatch(expected_found(relation, a, b))),
 701             }
 702         });
 703         tcx.mk_poly_existential_predicates(v)
 704     }
 705 }
 706
 707 impl<'tcx> Relate<'tcx> for ty::ClosureSubsts<'tcx> {
 708     fn relate<R: TypeRelation<'tcx>>(
 709         relation: &mut R,
 710         a: ty::ClosureSubsts<'tcx>,
 711         b: ty::ClosureSubsts<'tcx>,
 712     ) -> RelateResult<'tcx, ty::ClosureSubsts<'tcx>> {
 713         let substs = relate_substs(relation, a.substs, b.substs)?;
 714         Ok(ty::ClosureSubsts { substs })
 715     }
 716 }
 717
 718 impl<'tcx> Relate<'tcx> for ty::GeneratorSubsts<'tcx> {
 719     fn relate<R: TypeRelation<'tcx>>(
 720         relation: &mut R,
 721         a: ty::GeneratorSubsts<'tcx>,
 722         b: ty::GeneratorSubsts<'tcx>,
 723     ) -> RelateResult<'tcx, ty::GeneratorSubsts<'tcx>> {
 724         let substs = relate_substs(relation, a.substs, b.substs)?;
 725         Ok(ty::GeneratorSubsts { substs })
 726     }
 727 }
 728
 729 impl<'tcx> Relate<'tcx> for SubstsRef<'tcx> {
 730     fn relate<R: TypeRelation<'tcx>>(
 731         relation: &mut R,
 732         a: SubstsRef<'tcx>,
 733         b: SubstsRef<'tcx>,
 734     ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
 735         relate_substs(relation, a, b)
 736     }
 737 }
 738
 739 impl<'tcx> Relate<'tcx> for ty::Region<'tcx> {
 740     fn relate<R: TypeRelation<'tcx>>(
 741         relation: &mut R,
 742         a: ty::Region<'tcx>,
 743         b: ty::Region<'tcx>,
 744     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 745         relation.regions(a, b)
 746     }
 747 }
 748
 749 impl<'tcx> Relate<'tcx> for ty::Const<'tcx> {
 750     fn relate<R: TypeRelation<'tcx>>(
 751         relation: &mut R,
 752         a: ty::Const<'tcx>,
 753         b: ty::Const<'tcx>,
 754     ) -> RelateResult<'tcx, ty::Const<'tcx>> {
 755         relation.consts(a, b)
 756     }
 757 }
 758
 759 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for ty::Binder<'tcx, T> {
 760     fn relate<R: TypeRelation<'tcx>>(
 761         relation: &mut R,
 762         a: ty::Binder<'tcx, T>,
 763         b: ty::Binder<'tcx, T>,
 764     ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> {
 765         relation.binders(a, b)
 766     }
 767 }
 768
 769 impl<'tcx> Relate<'tcx> for GenericArg<'tcx> {
 770     fn relate<R: TypeRelation<'tcx>>(
 771         relation: &mut R,
 772         a: GenericArg<'tcx>,
 773         b: GenericArg<'tcx>,
 774     ) -> RelateResult<'tcx, GenericArg<'tcx>> {
 775         match (a.unpack(), b.unpack()) {
 776             (GenericArgKind::Lifetime(a_lt), GenericArgKind::Lifetime(b_lt)) => {
 777                 Ok(relation.relate(a_lt, b_lt)?.into())
 778             }
 779             (GenericArgKind::Type(a_ty), GenericArgKind::Type(b_ty)) => {
 780                 Ok(relation.relate(a_ty, b_ty)?.into())
 781             }
 782             (GenericArgKind::Const(a_ct), GenericArgKind::Const(b_ct)) => {
 783                 Ok(relation.relate(a_ct, b_ct)?.into())
 784             }
 785             (GenericArgKind::Lifetime(unpacked), x) => {
 786                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 787             }
 788             (GenericArgKind::Type(unpacked), x) => {
 789                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 790             }
 791             (GenericArgKind::Const(unpacked), x) => {
 792                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 793             }
 794         }
 795     }
 796 }
 797
 798 impl<'tcx> Relate<'tcx> for ty::ImplPolarity {
 799     fn relate<R: TypeRelation<'tcx>>(
 800         relation: &mut R,
 801         a: ty::ImplPolarity,
 802         b: ty::ImplPolarity,
 803     ) -> RelateResult<'tcx, ty::ImplPolarity> {
 804         if a != b {
 805             Err(TypeError::PolarityMismatch(expected_found(relation, a, b)))
 806         } else {
 807             Ok(a)
 808         }
 809     }
 810 }
 811
 812 impl<'tcx> Relate<'tcx> for ty::TraitPredicate<'tcx> {
 813     fn relate<R: TypeRelation<'tcx>>(
 814         relation: &mut R,
 815         a: ty::TraitPredicate<'tcx>,
 816         b: ty::TraitPredicate<'tcx>,
 817     ) -> RelateResult<'tcx, ty::TraitPredicate<'tcx>> {
 818         Ok(ty::TraitPredicate {
 819             trait_ref: relation.relate(a.trait_ref, b.trait_ref)?,
 820             constness: relation.relate(a.constness, b.constness)?,
 821             polarity: relation.relate(a.polarity, b.polarity)?,
 822         })
 823     }
 824 }
 825
 826 impl<'tcx> Relate<'tcx> for Term<'tcx> {
 827     fn relate<R: TypeRelation<'tcx>>(
 828         relation: &mut R,
 829         a: Self,
 830         b: Self,
 831     ) -> RelateResult<'tcx, Self> {
 832         Ok(match (a.unpack(), b.unpack()) {
 833             (TermKind::Ty(a), TermKind::Ty(b)) => relation.relate(a, b)?.into(),
 834             (TermKind::Const(a), TermKind::Const(b)) => relation.relate(a, b)?.into(),
 835             _ => return Err(TypeError::Mismatch),
 836         })
 837     }
 838 }
 839
 840 impl<'tcx> Relate<'tcx> for ty::ProjectionPredicate<'tcx> {
 841     fn relate<R: TypeRelation<'tcx>>(
 842         relation: &mut R,
 843         a: ty::ProjectionPredicate<'tcx>,
 844         b: ty::ProjectionPredicate<'tcx>,
 845     ) -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>> {
 846         Ok(ty::ProjectionPredicate {
 847             projection_ty: relation.relate(a.projection_ty, b.projection_ty)?,
 848             term: relation.relate(a.term, b.term)?,
 849         })
 850     }
 851 }
 852
 853 ///////////////////////////////////////////////////////////////////////////
 854 // Error handling
 855
 856 pub fn expected_found<'tcx, R, T>(relation: &mut R, a: T, b: T) -> ExpectedFound<T>
 857 where
 858     R: TypeRelation<'tcx>,
 859 {
 860     ExpectedFound::new(relation.a_is_expected(), a, b)
 861 }