src/librustc/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::hir::def_id::DefId;
   8 use crate::ty::subst::{Kind, UnpackedKind, SubstsRef};
   9 use crate::ty::{self, Ty, TyCtxt, TypeFoldable};
  10 use crate::ty::error::{ExpectedFound, TypeError};
  11 use crate::mir::interpret::{ConstValue, Scalar, GlobalId};
  12 use std::rc::Rc;
  13 use std::iter;
  14 use rustc_target::spec::abi;
  15 use crate::hir as ast;
  16 use crate::traits;
  17
  18 pub type RelateResult<'tcx, T> = Result<T, TypeError<'tcx>>;
  19
  20 #[derive(Clone, Debug)]
  21 pub enum Cause {
  22     ExistentialRegionBound, // relating an existential region bound
  23 }
  24
  25 pub trait TypeRelation<'tcx>: Sized {
  26     fn tcx(&self) -> TyCtxt<'tcx>;
  27
  28     /// Returns a static string we can use for printouts.
  29     fn tag(&self) -> &'static str;
  30
  31     /// Returns `true` if the value `a` is the "expected" type in the
  32     /// relation. Just affects error messages.
  33     fn a_is_expected(&self) -> bool;
  34
  35     fn with_cause<F,R>(&mut self, _cause: Cause, f: F) -> R
  36         where F: FnOnce(&mut Self) -> R
  37     {
  38         f(self)
  39     }
  40
  41     /// Generic relation routine suitable for most anything.
  42     fn relate<T: Relate<'tcx>>(&mut self, a: &T, b: &T) -> RelateResult<'tcx, T> {
  43         Relate::relate(self, a, b)
  44     }
  45
  46     /// Relate the two substitutions for the given item. The default
  47     /// is to look up the variance for the item and proceed
  48     /// accordingly.
  49     fn relate_item_substs(&mut self,
  50                           item_def_id: DefId,
  51                           a_subst: SubstsRef<'tcx>,
  52                           b_subst: SubstsRef<'tcx>)
  53                           -> RelateResult<'tcx, SubstsRef<'tcx>>
  54     {
  55         debug!("relate_item_substs(item_def_id={:?}, a_subst={:?}, b_subst={:?})",
  56                item_def_id,
  57                a_subst,
  58                b_subst);
  59
  60         let opt_variances = self.tcx().variances_of(item_def_id);
  61         relate_substs(self, Some(opt_variances), a_subst, b_subst)
  62     }
  63
  64     /// Switch variance for the purpose of relating `a` and `b`.
  65     fn relate_with_variance<T: Relate<'tcx>>(&mut self,
  66                                              variance: ty::Variance,
  67                                              a: &T,
  68                                              b: &T)
  69                                              -> RelateResult<'tcx, T>;
  70
  71     // Overrideable relations. You shouldn't typically call these
  72     // directly, instead call `relate()`, which in turn calls
  73     // these. This is both more uniform but also allows us to add
  74     // additional hooks for other types in the future if needed
  75     // without making older code, which called `relate`, obsolete.
  76
  77     fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>>;
  78
  79     fn regions(
  80         &mut self,
  81         a: ty::Region<'tcx>,
  82         b: ty::Region<'tcx>
  83     ) -> RelateResult<'tcx, ty::Region<'tcx>>;
  84
  85     fn consts(
  86         &mut self,
  87         a: &'tcx ty::Const<'tcx>,
  88         b: &'tcx ty::Const<'tcx>
  89     ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>>;
  90
  91     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
  92                   -> RelateResult<'tcx, ty::Binder<T>>
  93         where T: Relate<'tcx>;
  94 }
  95
  96 pub trait Relate<'tcx>: TypeFoldable<'tcx> {
  97     fn relate<R: TypeRelation<'tcx>>(
  98         relation: &mut R,
  99         a: &Self,
 100         b: &Self,
 101     ) -> RelateResult<'tcx, Self>;
 102 }
 103
 104 ///////////////////////////////////////////////////////////////////////////
 105 // Relate impls
 106
 107 impl<'tcx> Relate<'tcx> for ty::TypeAndMut<'tcx> {
 108     fn relate<R: TypeRelation<'tcx>>(
 109         relation: &mut R,
 110         a: &ty::TypeAndMut<'tcx>,
 111         b: &ty::TypeAndMut<'tcx>,
 112     ) -> RelateResult<'tcx, ty::TypeAndMut<'tcx>> {
 113         debug!("{}.mts({:?}, {:?})",
 114                relation.tag(),
 115                a,
 116                b);
 117         if a.mutbl != b.mutbl {
 118             Err(TypeError::Mutability)
 119         } else {
 120             let mutbl = a.mutbl;
 121             let variance = match mutbl {
 122                 ast::Mutability::MutImmutable => ty::Covariant,
 123                 ast::Mutability::MutMutable => ty::Invariant,
 124             };
 125             let ty = relation.relate_with_variance(variance, &a.ty, &b.ty)?;
 126             Ok(ty::TypeAndMut { ty, mutbl })
 127         }
 128     }
 129 }
 130
 131 pub fn relate_substs<R: TypeRelation<'tcx>>(
 132     relation: &mut R,
 133     variances: Option<&[ty::Variance]>,
 134     a_subst: SubstsRef<'tcx>,
 135     b_subst: SubstsRef<'tcx>,
 136 ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
 137     let tcx = relation.tcx();
 138
 139     let params = a_subst.iter().zip(b_subst).enumerate().map(|(i, (a, b))| {
 140         let variance = variances.map_or(ty::Invariant, |v| v[i]);
 141         relation.relate_with_variance(variance, a, b)
 142     });
 143
 144     Ok(tcx.mk_substs(params)?)
 145 }
 146
 147 impl<'tcx> Relate<'tcx> for ty::FnSig<'tcx> {
 148     fn relate<R: TypeRelation<'tcx>>(
 149         relation: &mut R,
 150         a: &ty::FnSig<'tcx>,
 151         b: &ty::FnSig<'tcx>,
 152     ) -> RelateResult<'tcx, ty::FnSig<'tcx>> {
 153         let tcx = relation.tcx();
 154
 155         if a.c_variadic != b.c_variadic {
 156             return Err(TypeError::VariadicMismatch(
 157                 expected_found(relation, &a.c_variadic, &b.c_variadic)));
 158         }
 159         let unsafety = relation.relate(&a.unsafety, &b.unsafety)?;
 160         let abi = relation.relate(&a.abi, &b.abi)?;
 161
 162         if a.inputs().len() != b.inputs().len() {
 163             return Err(TypeError::ArgCount);
 164         }
 165
 166         let inputs_and_output = a.inputs().iter().cloned()
 167             .zip(b.inputs().iter().cloned())
 168             .map(|x| (x, false))
 169             .chain(iter::once(((a.output(), b.output()), true)))
 170             .map(|((a, b), is_output)| {
 171                 if is_output {
 172                     relation.relate(&a, &b)
 173                 } else {
 174                     relation.relate_with_variance(ty::Contravariant, &a, &b)
 175                 }
 176             });
 177         Ok(ty::FnSig {
 178             inputs_and_output: tcx.mk_type_list(inputs_and_output)?,
 179             c_variadic: a.c_variadic,
 180             unsafety,
 181             abi,
 182         })
 183     }
 184 }
 185
 186 impl<'tcx> Relate<'tcx> for ast::Unsafety {
 187     fn relate<R: TypeRelation<'tcx>>(
 188         relation: &mut R,
 189         a: &ast::Unsafety,
 190         b: &ast::Unsafety,
 191     ) -> RelateResult<'tcx, ast::Unsafety> {
 192         if a != b {
 193             Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
 194         } else {
 195             Ok(*a)
 196         }
 197     }
 198 }
 199
 200 impl<'tcx> Relate<'tcx> for abi::Abi {
 201     fn relate<R: TypeRelation<'tcx>>(
 202         relation: &mut R,
 203         a: &abi::Abi,
 204         b: &abi::Abi,
 205     ) -> RelateResult<'tcx, abi::Abi> {
 206         if a == b {
 207             Ok(*a)
 208         } else {
 209             Err(TypeError::AbiMismatch(expected_found(relation, a, b)))
 210         }
 211     }
 212 }
 213
 214 impl<'tcx> Relate<'tcx> for ty::ProjectionTy<'tcx> {
 215     fn relate<R: TypeRelation<'tcx>>(
 216         relation: &mut R,
 217         a: &ty::ProjectionTy<'tcx>,
 218         b: &ty::ProjectionTy<'tcx>,
 219     ) -> RelateResult<'tcx, ty::ProjectionTy<'tcx>> {
 220         if a.item_def_id != b.item_def_id {
 221             Err(TypeError::ProjectionMismatched(
 222                 expected_found(relation, &a.item_def_id, &b.item_def_id)))
 223         } else {
 224             let substs = relation.relate(&a.substs, &b.substs)?;
 225             Ok(ty::ProjectionTy {
 226                 item_def_id: a.item_def_id,
 227                 substs: &substs,
 228             })
 229         }
 230     }
 231 }
 232
 233 impl<'tcx> Relate<'tcx> for ty::ExistentialProjection<'tcx> {
 234     fn relate<R: TypeRelation<'tcx>>(
 235         relation: &mut R,
 236         a: &ty::ExistentialProjection<'tcx>,
 237         b: &ty::ExistentialProjection<'tcx>,
 238     ) -> RelateResult<'tcx, ty::ExistentialProjection<'tcx>> {
 239         if a.item_def_id != b.item_def_id {
 240             Err(TypeError::ProjectionMismatched(
 241                 expected_found(relation, &a.item_def_id, &b.item_def_id)))
 242         } else {
 243             let ty = relation.relate(&a.ty, &b.ty)?;
 244             let substs = relation.relate(&a.substs, &b.substs)?;
 245             Ok(ty::ExistentialProjection {
 246                 item_def_id: a.item_def_id,
 247                 substs,
 248                 ty,
 249             })
 250         }
 251     }
 252 }
 253
 254 impl<'tcx> Relate<'tcx> for Vec<ty::PolyExistentialProjection<'tcx>> {
 255     fn relate<R: TypeRelation<'tcx>>(
 256         relation: &mut R,
 257         a: &Vec<ty::PolyExistentialProjection<'tcx>>,
 258         b: &Vec<ty::PolyExistentialProjection<'tcx>>,
 259     ) -> RelateResult<'tcx, Vec<ty::PolyExistentialProjection<'tcx>>> {
 260         // To be compatible, `a` and `b` must be for precisely the
 261         // same set of traits and item names. We always require that
 262         // projection bounds lists are sorted by trait-def-id and item-name,
 263         // so we can just iterate through the lists pairwise, so long as they are the
 264         // same length.
 265         if a.len() != b.len() {
 266             Err(TypeError::ProjectionBoundsLength(expected_found(relation, &a.len(), &b.len())))
 267         } else {
 268             a.iter()
 269              .zip(b)
 270              .map(|(a, b)| relation.relate(a, b))
 271              .collect()
 272         }
 273     }
 274 }
 275
 276 impl<'tcx> Relate<'tcx> for ty::TraitRef<'tcx> {
 277     fn relate<R: TypeRelation<'tcx>>(
 278         relation: &mut R,
 279         a: &ty::TraitRef<'tcx>,
 280         b: &ty::TraitRef<'tcx>,
 281     ) -> RelateResult<'tcx, ty::TraitRef<'tcx>> {
 282         // Different traits cannot be related
 283         if a.def_id != b.def_id {
 284             Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
 285         } else {
 286             let substs = relate_substs(relation, None, a.substs, b.substs)?;
 287             Ok(ty::TraitRef { def_id: a.def_id, substs: substs })
 288         }
 289     }
 290 }
 291
 292 impl<'tcx> Relate<'tcx> for ty::ExistentialTraitRef<'tcx> {
 293     fn relate<R: TypeRelation<'tcx>>(
 294         relation: &mut R,
 295         a: &ty::ExistentialTraitRef<'tcx>,
 296         b: &ty::ExistentialTraitRef<'tcx>,
 297     ) -> RelateResult<'tcx, ty::ExistentialTraitRef<'tcx>> {
 298         // Different traits cannot be related
 299         if a.def_id != b.def_id {
 300             Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
 301         } else {
 302             let substs = relate_substs(relation, None, a.substs, b.substs)?;
 303             Ok(ty::ExistentialTraitRef { def_id: a.def_id, substs: substs })
 304         }
 305     }
 306 }
 307
 308 #[derive(Debug, Clone)]
 309 struct GeneratorWitness<'tcx>(&'tcx ty::List<Ty<'tcx>>);
 310
 311 TupleStructTypeFoldableImpl! {
 312     impl<'tcx> TypeFoldable<'tcx> for GeneratorWitness<'tcx> {
 313         a
 314     }
 315 }
 316
 317 impl<'tcx> Relate<'tcx> for GeneratorWitness<'tcx> {
 318     fn relate<R: TypeRelation<'tcx>>(
 319         relation: &mut R,
 320         a: &GeneratorWitness<'tcx>,
 321         b: &GeneratorWitness<'tcx>,
 322     ) -> RelateResult<'tcx, GeneratorWitness<'tcx>> {
 323         assert_eq!(a.0.len(), b.0.len());
 324         let tcx = relation.tcx();
 325         let types = tcx.mk_type_list(a.0.iter().zip(b.0).map(|(a, b)| relation.relate(a, b)))?;
 326         Ok(GeneratorWitness(types))
 327     }
 328 }
 329
 330 impl<'tcx> Relate<'tcx> for Ty<'tcx> {
 331     fn relate<R: TypeRelation<'tcx>>(
 332         relation: &mut R,
 333         a: &Ty<'tcx>,
 334         b: &Ty<'tcx>,
 335     ) -> RelateResult<'tcx, Ty<'tcx>> {
 336         relation.tys(a, b)
 337     }
 338 }
 339
 340 /// The main "type relation" routine. Note that this does not handle
 341 /// inference artifacts, so you should filter those out before calling
 342 /// it.
 343 pub fn super_relate_tys<R: TypeRelation<'tcx>>(
 344     relation: &mut R,
 345     a: Ty<'tcx>,
 346     b: Ty<'tcx>,
 347 ) -> RelateResult<'tcx, Ty<'tcx>> {
 348     let tcx = relation.tcx();
 349     debug!("super_relate_tys: a={:?} b={:?}", a, b);
 350     match (&a.sty, &b.sty) {
 351         (&ty::Infer(_), _) |
 352         (_, &ty::Infer(_)) =>
 353         {
 354             // The caller should handle these cases!
 355             bug!("var types encountered in super_relate_tys")
 356         }
 357
 358         (ty::Bound(..), _) | (_, ty::Bound(..)) => {
 359             bug!("bound types encountered in super_relate_tys")
 360         }
 361
 362         (&ty::Error, _) | (_, &ty::Error) =>
 363         {
 364             Ok(tcx.types.err)
 365         }
 366
 367         (&ty::Never, _) |
 368         (&ty::Char, _) |
 369         (&ty::Bool, _) |
 370         (&ty::Int(_), _) |
 371         (&ty::Uint(_), _) |
 372         (&ty::Float(_), _) |
 373         (&ty::Str, _)
 374             if a == b =>
 375         {
 376             Ok(a)
 377         }
 378
 379         (&ty::Param(ref a_p), &ty::Param(ref b_p))
 380             if a_p.index == b_p.index =>
 381         {
 382             Ok(a)
 383         }
 384
 385         (ty::Placeholder(p1), ty::Placeholder(p2)) if p1 == p2 => {
 386             Ok(a)
 387         }
 388
 389         (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs))
 390             if a_def == b_def =>
 391         {
 392             let substs = relation.relate_item_substs(a_def.did, a_substs, b_substs)?;
 393             Ok(tcx.mk_adt(a_def, substs))
 394         }
 395
 396         (&ty::Foreign(a_id), &ty::Foreign(b_id))
 397             if a_id == b_id =>
 398         {
 399             Ok(tcx.mk_foreign(a_id))
 400         }
 401
 402         (&ty::Dynamic(ref a_obj, ref a_region), &ty::Dynamic(ref b_obj, ref b_region)) => {
 403             let region_bound = relation.with_cause(Cause::ExistentialRegionBound,
 404                                                        |relation| {
 405                                                            relation.relate_with_variance(
 406                                                                ty::Contravariant,
 407                                                                a_region,
 408                                                                b_region)
 409                                                        })?;
 410             Ok(tcx.mk_dynamic(relation.relate(a_obj, b_obj)?, region_bound))
 411         }
 412
 413         (&ty::Generator(a_id, a_substs, movability),
 414          &ty::Generator(b_id, b_substs, _))
 415             if a_id == b_id =>
 416         {
 417             // All Generator types with the same id represent
 418             // the (anonymous) type of the same generator expression. So
 419             // all of their regions should be equated.
 420             let substs = relation.relate(&a_substs, &b_substs)?;
 421             Ok(tcx.mk_generator(a_id, substs, movability))
 422         }
 423
 424         (&ty::GeneratorWitness(a_types), &ty::GeneratorWitness(b_types)) =>
 425         {
 426             // Wrap our types with a temporary GeneratorWitness struct
 427             // inside the binder so we can related them
 428             let a_types = a_types.map_bound(GeneratorWitness);
 429             let b_types = b_types.map_bound(GeneratorWitness);
 430             // Then remove the GeneratorWitness for the result
 431             let types = relation.relate(&a_types, &b_types)?.map_bound(|witness| witness.0);
 432             Ok(tcx.mk_generator_witness(types))
 433         }
 434
 435         (&ty::Closure(a_id, a_substs),
 436          &ty::Closure(b_id, b_substs))
 437             if a_id == b_id =>
 438         {
 439             // All Closure types with the same id represent
 440             // the (anonymous) type of the same closure expression. So
 441             // all of their regions should be equated.
 442             let substs = relation.relate(&a_substs, &b_substs)?;
 443             Ok(tcx.mk_closure(a_id, substs))
 444         }
 445
 446         (&ty::RawPtr(ref a_mt), &ty::RawPtr(ref b_mt)) =>
 447         {
 448             let mt = relation.relate(a_mt, b_mt)?;
 449             Ok(tcx.mk_ptr(mt))
 450         }
 451
 452         (&ty::Ref(a_r, a_ty, a_mutbl), &ty::Ref(b_r, b_ty, b_mutbl)) =>
 453         {
 454             let r = relation.relate_with_variance(ty::Contravariant, &a_r, &b_r)?;
 455             let a_mt = ty::TypeAndMut { ty: a_ty, mutbl: a_mutbl };
 456             let b_mt = ty::TypeAndMut { ty: b_ty, mutbl: b_mutbl };
 457             let mt = relation.relate(&a_mt, &b_mt)?;
 458             Ok(tcx.mk_ref(r, mt))
 459         }
 460
 461         (&ty::Array(a_t, sz_a), &ty::Array(b_t, sz_b)) =>
 462         {
 463             let t = relation.relate(&a_t, &b_t)?;
 464             match relation.relate(&sz_a, &sz_b) {
 465                 Ok(sz) => Ok(tcx.mk_ty(ty::Array(t, sz))),
 466                 Err(err) => {
 467                     // Check whether the lengths are both concrete/known values,
 468                     // but are unequal, for better diagnostics.
 469                     match (sz_a.assert_usize(tcx), sz_b.assert_usize(tcx)) {
 470                         (Some(sz_a_val), Some(sz_b_val)) => {
 471                             Err(TypeError::FixedArraySize(
 472                                 expected_found(relation, &sz_a_val, &sz_b_val)
 473                             ))
 474                         }
 475                         _ => return Err(err),
 476                     }
 477                 }
 478             }
 479         }
 480
 481         (&ty::Slice(a_t), &ty::Slice(b_t)) =>
 482         {
 483             let t = relation.relate(&a_t, &b_t)?;
 484             Ok(tcx.mk_slice(t))
 485         }
 486
 487         (&ty::Tuple(as_), &ty::Tuple(bs)) =>
 488         {
 489             if as_.len() == bs.len() {
 490                 Ok(tcx.mk_tup(as_.iter().zip(bs).map(|(a, b)| {
 491                     relation.relate(&a.expect_ty(), &b.expect_ty())
 492                 }))?)
 493             } else if !(as_.is_empty() || bs.is_empty()) {
 494                 Err(TypeError::TupleSize(
 495                     expected_found(relation, &as_.len(), &bs.len())))
 496             } else {
 497                 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 498             }
 499         }
 500
 501         (&ty::FnDef(a_def_id, a_substs), &ty::FnDef(b_def_id, b_substs))
 502             if a_def_id == b_def_id =>
 503         {
 504             let substs = relation.relate_item_substs(a_def_id, a_substs, b_substs)?;
 505             Ok(tcx.mk_fn_def(a_def_id, substs))
 506         }
 507
 508         (&ty::FnPtr(a_fty), &ty::FnPtr(b_fty)) =>
 509         {
 510             let fty = relation.relate(&a_fty, &b_fty)?;
 511             Ok(tcx.mk_fn_ptr(fty))
 512         }
 513
 514         (ty::UnnormalizedProjection(a_data), ty::UnnormalizedProjection(b_data)) => {
 515             let projection_ty = relation.relate(a_data, b_data)?;
 516             Ok(tcx.mk_ty(ty::UnnormalizedProjection(projection_ty)))
 517         }
 518
 519         // these two are already handled downstream in case of lazy normalization
 520         (ty::Projection(a_data), ty::Projection(b_data)) => {
 521             let projection_ty = relation.relate(a_data, b_data)?;
 522             Ok(tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs))
 523         }
 524
 525         (&ty::Opaque(a_def_id, a_substs), &ty::Opaque(b_def_id, b_substs))
 526             if a_def_id == b_def_id =>
 527         {
 528             let substs = relate_substs(relation, None, a_substs, b_substs)?;
 529             Ok(tcx.mk_opaque(a_def_id, substs))
 530         }
 531
 532         _ =>
 533         {
 534             Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 535         }
 536     }
 537 }
 538
 539 /// The main "const relation" routine. Note that this does not handle
 540 /// inference artifacts, so you should filter those out before calling
 541 /// it.
 542 pub fn super_relate_consts<R: TypeRelation<'tcx>>(
 543     relation: &mut R,
 544     a: &'tcx ty::Const<'tcx>,
 545     b: &'tcx ty::Const<'tcx>,
 546 ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
 547     let tcx = relation.tcx();
 548
 549     let eagerly_eval = |x: &'tcx ty::Const<'tcx>| {
 550         if let ConstValue::Unevaluated(def_id, substs) = x.val {
 551             // FIXME(eddyb) get the right param_env.
 552             let param_env = ty::ParamEnv::empty();
 553             if !substs.has_local_value() {
 554                 let instance = ty::Instance::resolve(
 555                     tcx.global_tcx(),
 556                     param_env,
 557                     def_id,
 558                     substs,
 559                 );
 560                 if let Some(instance) = instance {
 561                     let cid = GlobalId {
 562                         instance,
 563                         promoted: None,
 564                     };
 565                     if let Ok(ct) = tcx.const_eval(param_env.and(cid)) {
 566                         return ct.val;
 567                     }
 568                 }
 569             }
 570         }
 571         x.val
 572     };
 573
 574     // Currently, the values that can be unified are those that
 575     // implement both `PartialEq` and `Eq`, corresponding to
 576     // `structural_match` types.
 577     // FIXME(const_generics): check for `structural_match` synthetic attribute.
 578     match (eagerly_eval(a), eagerly_eval(b)) {
 579         (ConstValue::Infer(_), _) | (_, ConstValue::Infer(_)) => {
 580             // The caller should handle these cases!
 581             bug!("var types encountered in super_relate_consts: {:?} {:?}", a, b)
 582         }
 583         (ConstValue::Param(a_p), ConstValue::Param(b_p)) if a_p.index == b_p.index => {
 584             Ok(a)
 585         }
 586         (ConstValue::Placeholder(p1), ConstValue::Placeholder(p2)) if p1 == p2 => {
 587             Ok(a)
 588         }
 589         (a_val @ ConstValue::Scalar(Scalar::Raw { .. }), b_val @ _)
 590             if a.ty == b.ty && a_val == b_val =>
 591         {
 592             Ok(tcx.mk_const(ty::Const {
 593                 val: a_val,
 594                 ty: a.ty,
 595             }))
 596         }
 597
 598         // FIXME(const_generics): we should either handle `Scalar::Ptr` or add a comment
 599         // saying that we're not handling it intentionally.
 600
 601         // FIXME(const_generics): handle `ConstValue::ByRef` and `ConstValue::Slice`.
 602
 603         // FIXME(const_generics): this is wrong, as it is a projection
 604         (ConstValue::Unevaluated(a_def_id, a_substs),
 605             ConstValue::Unevaluated(b_def_id, b_substs)) if a_def_id == b_def_id => {
 606                 let substs =
 607                     relation.relate_with_variance(ty::Variance::Invariant, &a_substs, &b_substs)?;
 608                 Ok(tcx.mk_const(ty::Const {
 609                     val: ConstValue::Unevaluated(a_def_id, &substs),
 610                     ty: a.ty,
 611                 }))
 612             }
 613
 614         _ => Err(TypeError::ConstMismatch(expected_found(relation, &a, &b))),
 615     }
 616 }
 617
 618 impl<'tcx> Relate<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
 619     fn relate<R: TypeRelation<'tcx>>(
 620         relation: &mut R,
 621         a: &Self,
 622         b: &Self,
 623     ) -> RelateResult<'tcx, Self> {
 624         if a.len() != b.len() {
 625             return Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)));
 626         }
 627
 628         let tcx = relation.tcx();
 629         let v = a.iter().zip(b.iter()).map(|(ep_a, ep_b)| {
 630             use crate::ty::ExistentialPredicate::*;
 631             match (*ep_a, *ep_b) {
 632                 (Trait(ref a), Trait(ref b)) => Ok(Trait(relation.relate(a, b)?)),
 633                 (Projection(ref a), Projection(ref b)) => Ok(Projection(relation.relate(a, b)?)),
 634                 (AutoTrait(ref a), AutoTrait(ref b)) if a == b => Ok(AutoTrait(*a)),
 635                 _ => Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)))
 636             }
 637         });
 638         Ok(tcx.mk_existential_predicates(v)?)
 639     }
 640 }
 641
 642 impl<'tcx> Relate<'tcx> for ty::ClosureSubsts<'tcx> {
 643     fn relate<R: TypeRelation<'tcx>>(
 644         relation: &mut R,
 645         a: &ty::ClosureSubsts<'tcx>,
 646         b: &ty::ClosureSubsts<'tcx>,
 647     ) -> RelateResult<'tcx, ty::ClosureSubsts<'tcx>> {
 648         let substs = relate_substs(relation, None, a.substs, b.substs)?;
 649         Ok(ty::ClosureSubsts { substs })
 650     }
 651 }
 652
 653 impl<'tcx> Relate<'tcx> for ty::GeneratorSubsts<'tcx> {
 654     fn relate<R: TypeRelation<'tcx>>(
 655         relation: &mut R,
 656         a: &ty::GeneratorSubsts<'tcx>,
 657         b: &ty::GeneratorSubsts<'tcx>,
 658     ) -> RelateResult<'tcx, ty::GeneratorSubsts<'tcx>> {
 659         let substs = relate_substs(relation, None, a.substs, b.substs)?;
 660         Ok(ty::GeneratorSubsts { substs })
 661     }
 662 }
 663
 664 impl<'tcx> Relate<'tcx> for SubstsRef<'tcx> {
 665     fn relate<R: TypeRelation<'tcx>>(
 666         relation: &mut R,
 667         a: &SubstsRef<'tcx>,
 668         b: &SubstsRef<'tcx>,
 669     ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
 670         relate_substs(relation, None, a, b)
 671     }
 672 }
 673
 674 impl<'tcx> Relate<'tcx> for ty::Region<'tcx> {
 675     fn relate<R: TypeRelation<'tcx>>(
 676         relation: &mut R,
 677         a: &ty::Region<'tcx>,
 678         b: &ty::Region<'tcx>,
 679     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 680         relation.regions(*a, *b)
 681     }
 682 }
 683
 684 impl<'tcx> Relate<'tcx> for &'tcx ty::Const<'tcx> {
 685     fn relate<R: TypeRelation<'tcx>>(
 686         relation: &mut R,
 687         a: &&'tcx ty::Const<'tcx>,
 688         b: &&'tcx ty::Const<'tcx>,
 689     ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
 690         relation.consts(*a, *b)
 691     }
 692 }
 693
 694 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for ty::Binder<T> {
 695     fn relate<R: TypeRelation<'tcx>>(
 696         relation: &mut R,
 697         a: &ty::Binder<T>,
 698         b: &ty::Binder<T>,
 699     ) -> RelateResult<'tcx, ty::Binder<T>> {
 700         relation.binders(a, b)
 701     }
 702 }
 703
 704 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Rc<T> {
 705     fn relate<R: TypeRelation<'tcx>>(
 706         relation: &mut R,
 707         a: &Rc<T>,
 708         b: &Rc<T>,
 709     ) -> RelateResult<'tcx, Rc<T>> {
 710         let a: &T = a;
 711         let b: &T = b;
 712         Ok(Rc::new(relation.relate(a, b)?))
 713     }
 714 }
 715
 716 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Box<T> {
 717     fn relate<R: TypeRelation<'tcx>>(
 718         relation: &mut R,
 719         a: &Box<T>,
 720         b: &Box<T>,
 721     ) -> RelateResult<'tcx, Box<T>> {
 722         let a: &T = a;
 723         let b: &T = b;
 724         Ok(Box::new(relation.relate(a, b)?))
 725     }
 726 }
 727
 728 impl<'tcx> Relate<'tcx> for Kind<'tcx> {
 729     fn relate<R: TypeRelation<'tcx>>(
 730         relation: &mut R,
 731         a: &Kind<'tcx>,
 732         b: &Kind<'tcx>,
 733     ) -> RelateResult<'tcx, Kind<'tcx>> {
 734         match (a.unpack(), b.unpack()) {
 735             (UnpackedKind::Lifetime(a_lt), UnpackedKind::Lifetime(b_lt)) => {
 736                 Ok(relation.relate(&a_lt, &b_lt)?.into())
 737             }
 738             (UnpackedKind::Type(a_ty), UnpackedKind::Type(b_ty)) => {
 739                 Ok(relation.relate(&a_ty, &b_ty)?.into())
 740             }
 741             (UnpackedKind::Const(a_ct), UnpackedKind::Const(b_ct)) => {
 742                 Ok(relation.relate(&a_ct, &b_ct)?.into())
 743             }
 744             (UnpackedKind::Lifetime(unpacked), x) => {
 745                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 746             }
 747             (UnpackedKind::Type(unpacked), x) => {
 748                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 749             }
 750             (UnpackedKind::Const(unpacked), x) => {
 751                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 752             }
 753         }
 754     }
 755 }
 756
 757 impl<'tcx> Relate<'tcx> for ty::TraitPredicate<'tcx> {
 758     fn relate<R: TypeRelation<'tcx>>(
 759         relation: &mut R,
 760         a: &ty::TraitPredicate<'tcx>,
 761         b: &ty::TraitPredicate<'tcx>,
 762     ) -> RelateResult<'tcx, ty::TraitPredicate<'tcx>> {
 763         Ok(ty::TraitPredicate {
 764             trait_ref: relation.relate(&a.trait_ref, &b.trait_ref)?,
 765         })
 766     }
 767 }
 768
 769 impl<'tcx> Relate<'tcx> for ty::ProjectionPredicate<'tcx> {
 770     fn relate<R: TypeRelation<'tcx>>(
 771         relation: &mut R,
 772         a: &ty::ProjectionPredicate<'tcx>,
 773         b: &ty::ProjectionPredicate<'tcx>,
 774     ) -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>> {
 775         Ok(ty::ProjectionPredicate {
 776             projection_ty: relation.relate(&a.projection_ty, &b.projection_ty)?,
 777             ty: relation.relate(&a.ty, &b.ty)?,
 778         })
 779     }
 780 }
 781
 782 impl<'tcx> Relate<'tcx> for traits::WhereClause<'tcx> {
 783     fn relate<R: TypeRelation<'tcx>>(
 784         relation: &mut R,
 785         a: &traits::WhereClause<'tcx>,
 786         b: &traits::WhereClause<'tcx>,
 787     ) -> RelateResult<'tcx, traits::WhereClause<'tcx>> {
 788         use crate::traits::WhereClause::*;
 789         match (a, b) {
 790             (Implemented(a_pred), Implemented(b_pred)) => {
 791                 Ok(Implemented(relation.relate(a_pred, b_pred)?))
 792             }
 793
 794             (ProjectionEq(a_pred), ProjectionEq(b_pred)) => {
 795                 Ok(ProjectionEq(relation.relate(a_pred, b_pred)?))
 796             }
 797
 798             (RegionOutlives(a_pred), RegionOutlives(b_pred)) => {
 799                 Ok(RegionOutlives(ty::OutlivesPredicate(
 800                     relation.relate(&a_pred.0, &b_pred.0)?,
 801                     relation.relate(&a_pred.1, &b_pred.1)?,
 802                 )))
 803             }
 804
 805             (TypeOutlives(a_pred), TypeOutlives(b_pred)) => {
 806                 Ok(TypeOutlives(ty::OutlivesPredicate(
 807                     relation.relate(&a_pred.0, &b_pred.0)?,
 808                     relation.relate(&a_pred.1, &b_pred.1)?,
 809                 )))
 810             }
 811
 812             _ =>  Err(TypeError::Mismatch),
 813         }
 814     }
 815 }
 816
 817 impl<'tcx> Relate<'tcx> for traits::WellFormed<'tcx> {
 818     fn relate<R: TypeRelation<'tcx>>(
 819         relation: &mut R,
 820         a: &traits::WellFormed<'tcx>,
 821         b: &traits::WellFormed<'tcx>,
 822     ) -> RelateResult<'tcx, traits::WellFormed<'tcx>> {
 823         use crate::traits::WellFormed::*;
 824         match (a, b) {
 825             (Trait(a_pred), Trait(b_pred)) => Ok(Trait(relation.relate(a_pred, b_pred)?)),
 826             (Ty(a_ty), Ty(b_ty)) => Ok(Ty(relation.relate(a_ty, b_ty)?)),
 827             _ =>  Err(TypeError::Mismatch),
 828         }
 829     }
 830 }
 831
 832 impl<'tcx> Relate<'tcx> for traits::FromEnv<'tcx> {
 833     fn relate<R: TypeRelation<'tcx>>(
 834         relation: &mut R,
 835         a: &traits::FromEnv<'tcx>,
 836         b: &traits::FromEnv<'tcx>,
 837     ) -> RelateResult<'tcx, traits::FromEnv<'tcx>> {
 838         use crate::traits::FromEnv::*;
 839         match (a, b) {
 840             (Trait(a_pred), Trait(b_pred)) => Ok(Trait(relation.relate(a_pred, b_pred)?)),
 841             (Ty(a_ty), Ty(b_ty)) => Ok(Ty(relation.relate(a_ty, b_ty)?)),
 842             _ =>  Err(TypeError::Mismatch),
 843         }
 844     }
 845 }
 846
 847 impl<'tcx> Relate<'tcx> for traits::DomainGoal<'tcx> {
 848     fn relate<R: TypeRelation<'tcx>>(
 849         relation: &mut R,
 850         a: &traits::DomainGoal<'tcx>,
 851         b: &traits::DomainGoal<'tcx>,
 852     ) -> RelateResult<'tcx, traits::DomainGoal<'tcx>> {
 853         use crate::traits::DomainGoal::*;
 854         match (a, b) {
 855             (Holds(a_wc), Holds(b_wc)) => Ok(Holds(relation.relate(a_wc, b_wc)?)),
 856             (WellFormed(a_wf), WellFormed(b_wf)) => Ok(WellFormed(relation.relate(a_wf, b_wf)?)),
 857             (FromEnv(a_fe), FromEnv(b_fe)) => Ok(FromEnv(relation.relate(a_fe, b_fe)?)),
 858
 859             (Normalize(a_pred), Normalize(b_pred)) => {
 860                 Ok(Normalize(relation.relate(a_pred, b_pred)?))
 861             }
 862
 863             _ =>  Err(TypeError::Mismatch),
 864         }
 865     }
 866 }
 867
 868 impl<'tcx> Relate<'tcx> for traits::Goal<'tcx> {
 869     fn relate<R: TypeRelation<'tcx>>(
 870         relation: &mut R,
 871         a: &traits::Goal<'tcx>,
 872         b: &traits::Goal<'tcx>,
 873     ) -> RelateResult<'tcx, traits::Goal<'tcx>> {
 874         use crate::traits::GoalKind::*;
 875         match (a, b) {
 876             (Implies(a_clauses, a_goal), Implies(b_clauses, b_goal)) => {
 877                 let clauses = relation.relate(a_clauses, b_clauses)?;
 878                 let goal = relation.relate(a_goal, b_goal)?;
 879                 Ok(relation.tcx().mk_goal(Implies(clauses, goal)))
 880             }
 881
 882             (And(a_left, a_right), And(b_left, b_right)) => {
 883                 let left = relation.relate(a_left, b_left)?;
 884                 let right = relation.relate(a_right, b_right)?;
 885                 Ok(relation.tcx().mk_goal(And(left, right)))
 886             }
 887
 888             (Not(a_goal), Not(b_goal)) => {
 889                 let goal = relation.relate(a_goal, b_goal)?;
 890                 Ok(relation.tcx().mk_goal(Not(goal)))
 891             }
 892
 893             (DomainGoal(a_goal), DomainGoal(b_goal)) => {
 894                 let goal = relation.relate(a_goal, b_goal)?;
 895                 Ok(relation.tcx().mk_goal(DomainGoal(goal)))
 896             }
 897
 898             (Quantified(a_qkind, a_goal), Quantified(b_qkind, b_goal))
 899                 if a_qkind == b_qkind =>
 900             {
 901                 let goal = relation.relate(a_goal, b_goal)?;
 902                 Ok(relation.tcx().mk_goal(Quantified(*a_qkind, goal)))
 903             }
 904
 905             (CannotProve, CannotProve) => Ok(*a),
 906
 907             _ => Err(TypeError::Mismatch),
 908         }
 909     }
 910 }
 911
 912 impl<'tcx> Relate<'tcx> for traits::Goals<'tcx> {
 913     fn relate<R: TypeRelation<'tcx>>(
 914         relation: &mut R,
 915         a: &traits::Goals<'tcx>,
 916         b: &traits::Goals<'tcx>,
 917     ) -> RelateResult<'tcx, traits::Goals<'tcx>> {
 918         if a.len() != b.len() {
 919             return Err(TypeError::Mismatch);
 920         }
 921
 922         let tcx = relation.tcx();
 923         let goals = a.iter().zip(b.iter()).map(|(a, b)| relation.relate(a, b));
 924         Ok(tcx.mk_goals(goals)?)
 925     }
 926 }
 927
 928 impl<'tcx> Relate<'tcx> for traits::Clause<'tcx> {
 929     fn relate<R: TypeRelation<'tcx>>(
 930         relation: &mut R,
 931         a: &traits::Clause<'tcx>,
 932         b: &traits::Clause<'tcx>,
 933     ) -> RelateResult<'tcx, traits::Clause<'tcx>> {
 934         use crate::traits::Clause::*;
 935         match (a, b) {
 936             (Implies(a_clause), Implies(b_clause)) => {
 937                 let clause = relation.relate(a_clause, b_clause)?;
 938                 Ok(Implies(clause))
 939             }
 940
 941             (ForAll(a_clause), ForAll(b_clause)) => {
 942                 let clause = relation.relate(a_clause, b_clause)?;
 943                 Ok(ForAll(clause))
 944             }
 945
 946             _ => Err(TypeError::Mismatch),
 947         }
 948     }
 949 }
 950
 951 impl<'tcx> Relate<'tcx> for traits::Clauses<'tcx> {
 952     fn relate<R: TypeRelation<'tcx>>(
 953         relation: &mut R,
 954         a: &traits::Clauses<'tcx>,
 955         b: &traits::Clauses<'tcx>,
 956     ) -> RelateResult<'tcx, traits::Clauses<'tcx>> {
 957         if a.len() != b.len() {
 958             return Err(TypeError::Mismatch);
 959         }
 960
 961         let tcx = relation.tcx();
 962         let clauses = a.iter().zip(b.iter()).map(|(a, b)| relation.relate(a, b));
 963         Ok(tcx.mk_clauses(clauses)?)
 964     }
 965 }
 966
 967 impl<'tcx> Relate<'tcx> for traits::ProgramClause<'tcx> {
 968     fn relate<R: TypeRelation<'tcx>>(
 969         relation: &mut R,
 970         a: &traits::ProgramClause<'tcx>,
 971         b: &traits::ProgramClause<'tcx>,
 972     ) -> RelateResult<'tcx, traits::ProgramClause<'tcx>> {
 973         Ok(traits::ProgramClause {
 974             goal: relation.relate(&a.goal, &b.goal)?,
 975             hypotheses: relation.relate(&a.hypotheses, &b.hypotheses)?,
 976             category: traits::ProgramClauseCategory::Other,
 977         })
 978     }
 979 }
 980
 981 impl<'tcx> Relate<'tcx> for traits::Environment<'tcx> {
 982     fn relate<R: TypeRelation<'tcx>>(
 983         relation: &mut R,
 984         a: &traits::Environment<'tcx>,
 985         b: &traits::Environment<'tcx>,
 986     ) -> RelateResult<'tcx, traits::Environment<'tcx>> {
 987         Ok(traits::Environment {
 988             clauses: relation.relate(&a.clauses, &b.clauses)?,
 989         })
 990     }
 991 }
 992
 993 impl<'tcx, G> Relate<'tcx> for traits::InEnvironment<'tcx, G>
 994 where
 995     G: Relate<'tcx>,
 996 {
 997     fn relate<R: TypeRelation<'tcx>>(
 998         relation: &mut R,
 999         a: &traits::InEnvironment<'tcx, G>,
1000         b: &traits::InEnvironment<'tcx, G>,
1001     ) -> RelateResult<'tcx, traits::InEnvironment<'tcx, G>> {
1002         Ok(traits::InEnvironment {
1003             environment: relation.relate(&a.environment, &b.environment)?,
1004             goal: relation.relate(&a.goal, &b.goal)?,
1005         })
1006     }
1007 }
1008
1009 ///////////////////////////////////////////////////////////////////////////
1010 // Error handling
1011
1012 pub fn expected_found<R, T>(relation: &mut R, a: &T, b: &T) -> ExpectedFound<T>
1013 where
1014     R: TypeRelation<'tcx>,
1015     T: Clone,
1016 {
1017     expected_found_bool(relation.a_is_expected(), a, b)
1018 }
1019
1020 pub fn expected_found_bool<T>(a_is_expected: bool,
1021                               a: &T,
1022                               b: &T)
1023                               -> ExpectedFound<T>
1024     where T: Clone
1025 {
1026     let a = a.clone();
1027     let b = b.clone();
1028     if a_is_expected {
1029         ExpectedFound {expected: a, found: b}
1030     } else {
1031         ExpectedFound {expected: b, found: a}
1032     }
1033 }