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