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