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, Scalar};
  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::MutImmutable => ty::Covariant,
 125                 ast::Mutability::MutMutable => 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)]
 311 struct GeneratorWitness<'tcx>(&'tcx ty::List<Ty<'tcx>>);
 312
 313 TupleStructTypeFoldableImpl! {
 314     impl<'tcx> TypeFoldable<'tcx> for GeneratorWitness<'tcx> {
 315         a
 316     }
 317 }
 318
 319 impl<'tcx> Relate<'tcx> for GeneratorWitness<'tcx> {
 320     fn relate<R: TypeRelation<'tcx>>(
 321         relation: &mut R,
 322         a: &GeneratorWitness<'tcx>,
 323         b: &GeneratorWitness<'tcx>,
 324     ) -> RelateResult<'tcx, GeneratorWitness<'tcx>> {
 325         assert_eq!(a.0.len(), b.0.len());
 326         let tcx = relation.tcx();
 327         let types = tcx.mk_type_list(a.0.iter().zip(b.0).map(|(a, b)| relation.relate(a, b)))?;
 328         Ok(GeneratorWitness(types))
 329     }
 330 }
 331
 332 impl<'tcx> Relate<'tcx> for Ty<'tcx> {
 333     fn relate<R: TypeRelation<'tcx>>(
 334         relation: &mut R,
 335         a: &Ty<'tcx>,
 336         b: &Ty<'tcx>,
 337     ) -> RelateResult<'tcx, Ty<'tcx>> {
 338         relation.tys(a, b)
 339     }
 340 }
 341
 342 /// The main "type relation" routine. Note that this does not handle
 343 /// inference artifacts, so you should filter those out before calling
 344 /// it.
 345 pub fn super_relate_tys<R: TypeRelation<'tcx>>(
 346     relation: &mut R,
 347     a: Ty<'tcx>,
 348     b: Ty<'tcx>,
 349 ) -> RelateResult<'tcx, Ty<'tcx>> {
 350     let tcx = relation.tcx();
 351     debug!("super_relate_tys: a={:?} b={:?}", a, b);
 352     match (&a.kind, &b.kind) {
 353         (&ty::Infer(_), _) |
 354         (_, &ty::Infer(_)) =>
 355         {
 356             // The caller should handle these cases!
 357             bug!("var types encountered in super_relate_tys")
 358         }
 359
 360         (ty::Bound(..), _) | (_, ty::Bound(..)) => {
 361             bug!("bound types encountered in super_relate_tys")
 362         }
 363
 364         (&ty::Error, _) | (_, &ty::Error) =>
 365         {
 366             Ok(tcx.types.err)
 367         }
 368
 369         (&ty::Never, _) |
 370         (&ty::Char, _) |
 371         (&ty::Bool, _) |
 372         (&ty::Int(_), _) |
 373         (&ty::Uint(_), _) |
 374         (&ty::Float(_), _) |
 375         (&ty::Str, _)
 376             if a == b =>
 377         {
 378             Ok(a)
 379         }
 380
 381         (&ty::Param(ref a_p), &ty::Param(ref b_p))
 382             if a_p.index == b_p.index =>
 383         {
 384             Ok(a)
 385         }
 386
 387         (ty::Placeholder(p1), ty::Placeholder(p2)) if p1 == p2 => {
 388             Ok(a)
 389         }
 390
 391         (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs))
 392             if a_def == b_def =>
 393         {
 394             let substs = relation.relate_item_substs(a_def.did, a_substs, b_substs)?;
 395             Ok(tcx.mk_adt(a_def, substs))
 396         }
 397
 398         (&ty::Foreign(a_id), &ty::Foreign(b_id))
 399             if a_id == b_id =>
 400         {
 401             Ok(tcx.mk_foreign(a_id))
 402         }
 403
 404         (&ty::Dynamic(ref a_obj, ref a_region), &ty::Dynamic(ref b_obj, ref b_region)) => {
 405             let region_bound = relation.with_cause(Cause::ExistentialRegionBound,
 406                                                        |relation| {
 407                                                            relation.relate_with_variance(
 408                                                                ty::Contravariant,
 409                                                                a_region,
 410                                                                b_region)
 411                                                        })?;
 412             Ok(tcx.mk_dynamic(relation.relate(a_obj, b_obj)?, region_bound))
 413         }
 414
 415         (&ty::Generator(a_id, a_substs, movability),
 416          &ty::Generator(b_id, b_substs, _))
 417             if a_id == b_id =>
 418         {
 419             // All Generator types with the same id represent
 420             // the (anonymous) type of the same generator expression. So
 421             // all of their regions should be equated.
 422             let substs = relation.relate(&a_substs, &b_substs)?;
 423             Ok(tcx.mk_generator(a_id, substs, movability))
 424         }
 425
 426         (&ty::GeneratorWitness(a_types), &ty::GeneratorWitness(b_types)) =>
 427         {
 428             // Wrap our types with a temporary GeneratorWitness struct
 429             // inside the binder so we can related them
 430             let a_types = a_types.map_bound(GeneratorWitness);
 431             let b_types = b_types.map_bound(GeneratorWitness);
 432             // Then remove the GeneratorWitness for the result
 433             let types = relation.relate(&a_types, &b_types)?.map_bound(|witness| witness.0);
 434             Ok(tcx.mk_generator_witness(types))
 435         }
 436
 437         (&ty::Closure(a_id, a_substs),
 438          &ty::Closure(b_id, b_substs))
 439             if a_id == b_id =>
 440         {
 441             // All Closure types with the same id represent
 442             // the (anonymous) type of the same closure expression. So
 443             // all of their regions should be equated.
 444             let substs = relation.relate(&a_substs, &b_substs)?;
 445             Ok(tcx.mk_closure(a_id, substs))
 446         }
 447
 448         (&ty::RawPtr(ref a_mt), &ty::RawPtr(ref b_mt)) =>
 449         {
 450             let mt = relation.relate(a_mt, b_mt)?;
 451             Ok(tcx.mk_ptr(mt))
 452         }
 453
 454         (&ty::Ref(a_r, a_ty, a_mutbl), &ty::Ref(b_r, b_ty, b_mutbl)) =>
 455         {
 456             let r = relation.relate_with_variance(ty::Contravariant, &a_r, &b_r)?;
 457             let a_mt = ty::TypeAndMut { ty: a_ty, mutbl: a_mutbl };
 458             let b_mt = ty::TypeAndMut { ty: b_ty, mutbl: b_mutbl };
 459             let mt = relation.relate(&a_mt, &b_mt)?;
 460             Ok(tcx.mk_ref(r, mt))
 461         }
 462
 463         (&ty::Array(a_t, sz_a), &ty::Array(b_t, sz_b)) =>
 464         {
 465             let t = relation.relate(&a_t, &b_t)?;
 466             match relation.relate(&sz_a, &sz_b) {
 467                 Ok(sz) => Ok(tcx.mk_ty(ty::Array(t, sz))),
 468                 Err(err) => {
 469                     // Check whether the lengths are both concrete/known values,
 470                     // but are unequal, for better diagnostics.
 471                     let sz_a = sz_a.try_eval_usize(tcx, relation.param_env());
 472                     let sz_b = sz_b.try_eval_usize(tcx, relation.param_env());
 473                     match (sz_a, sz_b) {
 474                         (Some(sz_a_val), Some(sz_b_val)) => {
 475                             Err(TypeError::FixedArraySize(
 476                                 expected_found(relation, &sz_a_val, &sz_b_val)
 477                             ))
 478                         }
 479                         _ => return Err(err),
 480                     }
 481                 }
 482             }
 483         }
 484
 485         (&ty::Slice(a_t), &ty::Slice(b_t)) =>
 486         {
 487             let t = relation.relate(&a_t, &b_t)?;
 488             Ok(tcx.mk_slice(t))
 489         }
 490
 491         (&ty::Tuple(as_), &ty::Tuple(bs)) =>
 492         {
 493             if as_.len() == bs.len() {
 494                 Ok(tcx.mk_tup(as_.iter().zip(bs).map(|(a, b)| {
 495                     relation.relate(&a.expect_ty(), &b.expect_ty())
 496                 }))?)
 497             } else if !(as_.is_empty() || bs.is_empty()) {
 498                 Err(TypeError::TupleSize(
 499                     expected_found(relation, &as_.len(), &bs.len())))
 500             } else {
 501                 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 502             }
 503         }
 504
 505         (&ty::FnDef(a_def_id, a_substs), &ty::FnDef(b_def_id, b_substs))
 506             if a_def_id == b_def_id =>
 507         {
 508             let substs = relation.relate_item_substs(a_def_id, a_substs, b_substs)?;
 509             Ok(tcx.mk_fn_def(a_def_id, substs))
 510         }
 511
 512         (&ty::FnPtr(a_fty), &ty::FnPtr(b_fty)) =>
 513         {
 514             let fty = relation.relate(&a_fty, &b_fty)?;
 515             Ok(tcx.mk_fn_ptr(fty))
 516         }
 517
 518         (ty::UnnormalizedProjection(a_data), ty::UnnormalizedProjection(b_data)) => {
 519             let projection_ty = relation.relate(a_data, b_data)?;
 520             Ok(tcx.mk_ty(ty::UnnormalizedProjection(projection_ty)))
 521         }
 522
 523         // these two are already handled downstream in case of lazy normalization
 524         (ty::Projection(a_data), ty::Projection(b_data)) => {
 525             let projection_ty = relation.relate(a_data, b_data)?;
 526             Ok(tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs))
 527         }
 528
 529         (&ty::Opaque(a_def_id, a_substs), &ty::Opaque(b_def_id, b_substs))
 530             if a_def_id == b_def_id =>
 531         {
 532             let substs = relate_substs(relation, None, a_substs, b_substs)?;
 533             Ok(tcx.mk_opaque(a_def_id, substs))
 534         }
 535
 536         _ =>
 537         {
 538             Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 539         }
 540     }
 541 }
 542
 543 /// The main "const relation" routine. Note that this does not handle
 544 /// inference artifacts, so you should filter those out before calling
 545 /// it.
 546 pub fn super_relate_consts<R: TypeRelation<'tcx>>(
 547     relation: &mut R,
 548     a: &'tcx ty::Const<'tcx>,
 549     b: &'tcx ty::Const<'tcx>,
 550 ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
 551     let tcx = relation.tcx();
 552
 553     let eagerly_eval = |x: &'tcx ty::Const<'tcx>| {
 554         if !x.val.has_local_value() {
 555             return x.eval(tcx, relation.param_env()).val;
 556         }
 557         x.val
 558     };
 559
 560     // Currently, the values that can be unified are those that
 561     // implement both `PartialEq` and `Eq`, corresponding to
 562     // `structural_match` types.
 563     // FIXME(const_generics): check for `structural_match` synthetic attribute.
 564     match (eagerly_eval(a), eagerly_eval(b)) {
 565         (ConstValue::Infer(_), _) | (_, ConstValue::Infer(_)) => {
 566             // The caller should handle these cases!
 567             bug!("var types encountered in super_relate_consts: {:?} {:?}", a, b)
 568         }
 569         (ConstValue::Param(a_p), ConstValue::Param(b_p)) if a_p.index == b_p.index => {
 570             Ok(a)
 571         }
 572         (ConstValue::Placeholder(p1), ConstValue::Placeholder(p2)) if p1 == p2 => {
 573             Ok(a)
 574         }
 575         (a_val @ ConstValue::Scalar(Scalar::Raw { .. }), b_val @ _)
 576             if a.ty == b.ty && a_val == b_val =>
 577         {
 578             Ok(tcx.mk_const(ty::Const {
 579                 val: a_val,
 580                 ty: a.ty,
 581             }))
 582         }
 583
 584         // FIXME(const_generics): we should either handle `Scalar::Ptr` or add a comment
 585         // saying that we're not handling it intentionally.
 586
 587         // FIXME(const_generics): handle `ConstValue::ByRef` and `ConstValue::Slice`.
 588
 589         // FIXME(const_generics): this is wrong, as it is a projection
 590         (ConstValue::Unevaluated(a_def_id, a_substs),
 591             ConstValue::Unevaluated(b_def_id, b_substs)) if a_def_id == b_def_id => {
 592                 let substs =
 593                     relation.relate_with_variance(ty::Variance::Invariant, &a_substs, &b_substs)?;
 594                 Ok(tcx.mk_const(ty::Const {
 595                     val: ConstValue::Unevaluated(a_def_id, &substs),
 596                     ty: a.ty,
 597                 }))
 598             }
 599
 600         _ => Err(TypeError::ConstMismatch(expected_found(relation, &a, &b))),
 601     }
 602 }
 603
 604 impl<'tcx> Relate<'tcx> for &'tcx ty::List<ty::ExistentialPredicate<'tcx>> {
 605     fn relate<R: TypeRelation<'tcx>>(
 606         relation: &mut R,
 607         a: &Self,
 608         b: &Self,
 609     ) -> RelateResult<'tcx, Self> {
 610         if a.len() != b.len() {
 611             return Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)));
 612         }
 613
 614         let tcx = relation.tcx();
 615         let v = a.iter().zip(b.iter()).map(|(ep_a, ep_b)| {
 616             use crate::ty::ExistentialPredicate::*;
 617             match (*ep_a, *ep_b) {
 618                 (Trait(ref a), Trait(ref b)) => Ok(Trait(relation.relate(a, b)?)),
 619                 (Projection(ref a), Projection(ref b)) => Ok(Projection(relation.relate(a, b)?)),
 620                 (AutoTrait(ref a), AutoTrait(ref b)) if a == b => Ok(AutoTrait(*a)),
 621                 _ => Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)))
 622             }
 623         });
 624         Ok(tcx.mk_existential_predicates(v)?)
 625     }
 626 }
 627
 628 impl<'tcx> Relate<'tcx> for ty::ClosureSubsts<'tcx> {
 629     fn relate<R: TypeRelation<'tcx>>(
 630         relation: &mut R,
 631         a: &ty::ClosureSubsts<'tcx>,
 632         b: &ty::ClosureSubsts<'tcx>,
 633     ) -> RelateResult<'tcx, ty::ClosureSubsts<'tcx>> {
 634         let substs = relate_substs(relation, None, a.substs, b.substs)?;
 635         Ok(ty::ClosureSubsts { substs })
 636     }
 637 }
 638
 639 impl<'tcx> Relate<'tcx> for ty::GeneratorSubsts<'tcx> {
 640     fn relate<R: TypeRelation<'tcx>>(
 641         relation: &mut R,
 642         a: &ty::GeneratorSubsts<'tcx>,
 643         b: &ty::GeneratorSubsts<'tcx>,
 644     ) -> RelateResult<'tcx, ty::GeneratorSubsts<'tcx>> {
 645         let substs = relate_substs(relation, None, a.substs, b.substs)?;
 646         Ok(ty::GeneratorSubsts { substs })
 647     }
 648 }
 649
 650 impl<'tcx> Relate<'tcx> for SubstsRef<'tcx> {
 651     fn relate<R: TypeRelation<'tcx>>(
 652         relation: &mut R,
 653         a: &SubstsRef<'tcx>,
 654         b: &SubstsRef<'tcx>,
 655     ) -> RelateResult<'tcx, SubstsRef<'tcx>> {
 656         relate_substs(relation, None, a, b)
 657     }
 658 }
 659
 660 impl<'tcx> Relate<'tcx> for ty::Region<'tcx> {
 661     fn relate<R: TypeRelation<'tcx>>(
 662         relation: &mut R,
 663         a: &ty::Region<'tcx>,
 664         b: &ty::Region<'tcx>,
 665     ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 666         relation.regions(*a, *b)
 667     }
 668 }
 669
 670 impl<'tcx> Relate<'tcx> for &'tcx ty::Const<'tcx> {
 671     fn relate<R: TypeRelation<'tcx>>(
 672         relation: &mut R,
 673         a: &&'tcx ty::Const<'tcx>,
 674         b: &&'tcx ty::Const<'tcx>,
 675     ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
 676         relation.consts(*a, *b)
 677     }
 678 }
 679
 680 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for ty::Binder<T> {
 681     fn relate<R: TypeRelation<'tcx>>(
 682         relation: &mut R,
 683         a: &ty::Binder<T>,
 684         b: &ty::Binder<T>,
 685     ) -> RelateResult<'tcx, ty::Binder<T>> {
 686         relation.binders(a, b)
 687     }
 688 }
 689
 690 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Rc<T> {
 691     fn relate<R: TypeRelation<'tcx>>(
 692         relation: &mut R,
 693         a: &Rc<T>,
 694         b: &Rc<T>,
 695     ) -> RelateResult<'tcx, Rc<T>> {
 696         let a: &T = a;
 697         let b: &T = b;
 698         Ok(Rc::new(relation.relate(a, b)?))
 699     }
 700 }
 701
 702 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Box<T> {
 703     fn relate<R: TypeRelation<'tcx>>(
 704         relation: &mut R,
 705         a: &Box<T>,
 706         b: &Box<T>,
 707     ) -> RelateResult<'tcx, Box<T>> {
 708         let a: &T = a;
 709         let b: &T = b;
 710         Ok(Box::new(relation.relate(a, b)?))
 711     }
 712 }
 713
 714 impl<'tcx> Relate<'tcx> for GenericArg<'tcx> {
 715     fn relate<R: TypeRelation<'tcx>>(
 716         relation: &mut R,
 717         a: &GenericArg<'tcx>,
 718         b: &GenericArg<'tcx>,
 719     ) -> RelateResult<'tcx, GenericArg<'tcx>> {
 720         match (a.unpack(), b.unpack()) {
 721             (GenericArgKind::Lifetime(a_lt), GenericArgKind::Lifetime(b_lt)) => {
 722                 Ok(relation.relate(&a_lt, &b_lt)?.into())
 723             }
 724             (GenericArgKind::Type(a_ty), GenericArgKind::Type(b_ty)) => {
 725                 Ok(relation.relate(&a_ty, &b_ty)?.into())
 726             }
 727             (GenericArgKind::Const(a_ct), GenericArgKind::Const(b_ct)) => {
 728                 Ok(relation.relate(&a_ct, &b_ct)?.into())
 729             }
 730             (GenericArgKind::Lifetime(unpacked), x) => {
 731                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 732             }
 733             (GenericArgKind::Type(unpacked), x) => {
 734                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 735             }
 736             (GenericArgKind::Const(unpacked), x) => {
 737                 bug!("impossible case reached: can't relate: {:?} with {:?}", unpacked, x)
 738             }
 739         }
 740     }
 741 }
 742
 743 impl<'tcx> Relate<'tcx> for ty::TraitPredicate<'tcx> {
 744     fn relate<R: TypeRelation<'tcx>>(
 745         relation: &mut R,
 746         a: &ty::TraitPredicate<'tcx>,
 747         b: &ty::TraitPredicate<'tcx>,
 748     ) -> RelateResult<'tcx, ty::TraitPredicate<'tcx>> {
 749         Ok(ty::TraitPredicate {
 750             trait_ref: relation.relate(&a.trait_ref, &b.trait_ref)?,
 751         })
 752     }
 753 }
 754
 755 impl<'tcx> Relate<'tcx> for ty::ProjectionPredicate<'tcx> {
 756     fn relate<R: TypeRelation<'tcx>>(
 757         relation: &mut R,
 758         a: &ty::ProjectionPredicate<'tcx>,
 759         b: &ty::ProjectionPredicate<'tcx>,
 760     ) -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>> {
 761         Ok(ty::ProjectionPredicate {
 762             projection_ty: relation.relate(&a.projection_ty, &b.projection_ty)?,
 763             ty: relation.relate(&a.ty, &b.ty)?,
 764         })
 765     }
 766 }
 767
 768 impl<'tcx> Relate<'tcx> for traits::WhereClause<'tcx> {
 769     fn relate<R: TypeRelation<'tcx>>(
 770         relation: &mut R,
 771         a: &traits::WhereClause<'tcx>,
 772         b: &traits::WhereClause<'tcx>,
 773     ) -> RelateResult<'tcx, traits::WhereClause<'tcx>> {
 774         use crate::traits::WhereClause::*;
 775         match (a, b) {
 776             (Implemented(a_pred), Implemented(b_pred)) => {
 777                 Ok(Implemented(relation.relate(a_pred, b_pred)?))
 778             }
 779
 780             (ProjectionEq(a_pred), ProjectionEq(b_pred)) => {
 781                 Ok(ProjectionEq(relation.relate(a_pred, b_pred)?))
 782             }
 783
 784             (RegionOutlives(a_pred), RegionOutlives(b_pred)) => {
 785                 Ok(RegionOutlives(ty::OutlivesPredicate(
 786                     relation.relate(&a_pred.0, &b_pred.0)?,
 787                     relation.relate(&a_pred.1, &b_pred.1)?,
 788                 )))
 789             }
 790
 791             (TypeOutlives(a_pred), TypeOutlives(b_pred)) => {
 792                 Ok(TypeOutlives(ty::OutlivesPredicate(
 793                     relation.relate(&a_pred.0, &b_pred.0)?,
 794                     relation.relate(&a_pred.1, &b_pred.1)?,
 795                 )))
 796             }
 797
 798             _ =>  Err(TypeError::Mismatch),
 799         }
 800     }
 801 }
 802
 803 impl<'tcx> Relate<'tcx> for traits::WellFormed<'tcx> {
 804     fn relate<R: TypeRelation<'tcx>>(
 805         relation: &mut R,
 806         a: &traits::WellFormed<'tcx>,
 807         b: &traits::WellFormed<'tcx>,
 808     ) -> RelateResult<'tcx, traits::WellFormed<'tcx>> {
 809         use crate::traits::WellFormed::*;
 810         match (a, b) {
 811             (Trait(a_pred), Trait(b_pred)) => Ok(Trait(relation.relate(a_pred, b_pred)?)),
 812             (Ty(a_ty), Ty(b_ty)) => Ok(Ty(relation.relate(a_ty, b_ty)?)),
 813             _ =>  Err(TypeError::Mismatch),
 814         }
 815     }
 816 }
 817
 818 impl<'tcx> Relate<'tcx> for traits::FromEnv<'tcx> {
 819     fn relate<R: TypeRelation<'tcx>>(
 820         relation: &mut R,
 821         a: &traits::FromEnv<'tcx>,
 822         b: &traits::FromEnv<'tcx>,
 823     ) -> RelateResult<'tcx, traits::FromEnv<'tcx>> {
 824         use crate::traits::FromEnv::*;
 825         match (a, b) {
 826             (Trait(a_pred), Trait(b_pred)) => Ok(Trait(relation.relate(a_pred, b_pred)?)),
 827             (Ty(a_ty), Ty(b_ty)) => Ok(Ty(relation.relate(a_ty, b_ty)?)),
 828             _ =>  Err(TypeError::Mismatch),
 829         }
 830     }
 831 }
 832
 833 impl<'tcx> Relate<'tcx> for traits::DomainGoal<'tcx> {
 834     fn relate<R: TypeRelation<'tcx>>(
 835         relation: &mut R,
 836         a: &traits::DomainGoal<'tcx>,
 837         b: &traits::DomainGoal<'tcx>,
 838     ) -> RelateResult<'tcx, traits::DomainGoal<'tcx>> {
 839         use crate::traits::DomainGoal::*;
 840         match (a, b) {
 841             (Holds(a_wc), Holds(b_wc)) => Ok(Holds(relation.relate(a_wc, b_wc)?)),
 842             (WellFormed(a_wf), WellFormed(b_wf)) => Ok(WellFormed(relation.relate(a_wf, b_wf)?)),
 843             (FromEnv(a_fe), FromEnv(b_fe)) => Ok(FromEnv(relation.relate(a_fe, b_fe)?)),
 844
 845             (Normalize(a_pred), Normalize(b_pred)) => {
 846                 Ok(Normalize(relation.relate(a_pred, b_pred)?))
 847             }
 848
 849             _ =>  Err(TypeError::Mismatch),
 850         }
 851     }
 852 }
 853
 854 impl<'tcx> Relate<'tcx> for traits::Goal<'tcx> {
 855     fn relate<R: TypeRelation<'tcx>>(
 856         relation: &mut R,
 857         a: &traits::Goal<'tcx>,
 858         b: &traits::Goal<'tcx>,
 859     ) -> RelateResult<'tcx, traits::Goal<'tcx>> {
 860         use crate::traits::GoalKind::*;
 861         match (a, b) {
 862             (Implies(a_clauses, a_goal), Implies(b_clauses, b_goal)) => {
 863                 let clauses = relation.relate(a_clauses, b_clauses)?;
 864                 let goal = relation.relate(a_goal, b_goal)?;
 865                 Ok(relation.tcx().mk_goal(Implies(clauses, goal)))
 866             }
 867
 868             (And(a_left, a_right), And(b_left, b_right)) => {
 869                 let left = relation.relate(a_left, b_left)?;
 870                 let right = relation.relate(a_right, b_right)?;
 871                 Ok(relation.tcx().mk_goal(And(left, right)))
 872             }
 873
 874             (Not(a_goal), Not(b_goal)) => {
 875                 let goal = relation.relate(a_goal, b_goal)?;
 876                 Ok(relation.tcx().mk_goal(Not(goal)))
 877             }
 878
 879             (DomainGoal(a_goal), DomainGoal(b_goal)) => {
 880                 let goal = relation.relate(a_goal, b_goal)?;
 881                 Ok(relation.tcx().mk_goal(DomainGoal(goal)))
 882             }
 883
 884             (Quantified(a_qkind, a_goal), Quantified(b_qkind, b_goal))
 885                 if a_qkind == b_qkind =>
 886             {
 887                 let goal = relation.relate(a_goal, b_goal)?;
 888                 Ok(relation.tcx().mk_goal(Quantified(*a_qkind, goal)))
 889             }
 890
 891             (CannotProve, CannotProve) => Ok(*a),
 892
 893             _ => Err(TypeError::Mismatch),
 894         }
 895     }
 896 }
 897
 898 impl<'tcx> Relate<'tcx> for traits::Goals<'tcx> {
 899     fn relate<R: TypeRelation<'tcx>>(
 900         relation: &mut R,
 901         a: &traits::Goals<'tcx>,
 902         b: &traits::Goals<'tcx>,
 903     ) -> RelateResult<'tcx, traits::Goals<'tcx>> {
 904         if a.len() != b.len() {
 905             return Err(TypeError::Mismatch);
 906         }
 907
 908         let tcx = relation.tcx();
 909         let goals = a.iter().zip(b.iter()).map(|(a, b)| relation.relate(a, b));
 910         Ok(tcx.mk_goals(goals)?)
 911     }
 912 }
 913
 914 impl<'tcx> Relate<'tcx> for traits::Clause<'tcx> {
 915     fn relate<R: TypeRelation<'tcx>>(
 916         relation: &mut R,
 917         a: &traits::Clause<'tcx>,
 918         b: &traits::Clause<'tcx>,
 919     ) -> RelateResult<'tcx, traits::Clause<'tcx>> {
 920         use crate::traits::Clause::*;
 921         match (a, b) {
 922             (Implies(a_clause), Implies(b_clause)) => {
 923                 let clause = relation.relate(a_clause, b_clause)?;
 924                 Ok(Implies(clause))
 925             }
 926
 927             (ForAll(a_clause), ForAll(b_clause)) => {
 928                 let clause = relation.relate(a_clause, b_clause)?;
 929                 Ok(ForAll(clause))
 930             }
 931
 932             _ => Err(TypeError::Mismatch),
 933         }
 934     }
 935 }
 936
 937 impl<'tcx> Relate<'tcx> for traits::Clauses<'tcx> {
 938     fn relate<R: TypeRelation<'tcx>>(
 939         relation: &mut R,
 940         a: &traits::Clauses<'tcx>,
 941         b: &traits::Clauses<'tcx>,
 942     ) -> RelateResult<'tcx, traits::Clauses<'tcx>> {
 943         if a.len() != b.len() {
 944             return Err(TypeError::Mismatch);
 945         }
 946
 947         let tcx = relation.tcx();
 948         let clauses = a.iter().zip(b.iter()).map(|(a, b)| relation.relate(a, b));
 949         Ok(tcx.mk_clauses(clauses)?)
 950     }
 951 }
 952
 953 impl<'tcx> Relate<'tcx> for traits::ProgramClause<'tcx> {
 954     fn relate<R: TypeRelation<'tcx>>(
 955         relation: &mut R,
 956         a: &traits::ProgramClause<'tcx>,
 957         b: &traits::ProgramClause<'tcx>,
 958     ) -> RelateResult<'tcx, traits::ProgramClause<'tcx>> {
 959         Ok(traits::ProgramClause {
 960             goal: relation.relate(&a.goal, &b.goal)?,
 961             hypotheses: relation.relate(&a.hypotheses, &b.hypotheses)?,
 962             category: traits::ProgramClauseCategory::Other,
 963         })
 964     }
 965 }
 966
 967 impl<'tcx> Relate<'tcx> for traits::Environment<'tcx> {
 968     fn relate<R: TypeRelation<'tcx>>(
 969         relation: &mut R,
 970         a: &traits::Environment<'tcx>,
 971         b: &traits::Environment<'tcx>,
 972     ) -> RelateResult<'tcx, traits::Environment<'tcx>> {
 973         Ok(traits::Environment {
 974             clauses: relation.relate(&a.clauses, &b.clauses)?,
 975         })
 976     }
 977 }
 978
 979 impl<'tcx, G> Relate<'tcx> for traits::InEnvironment<'tcx, G>
 980 where
 981     G: Relate<'tcx>,
 982 {
 983     fn relate<R: TypeRelation<'tcx>>(
 984         relation: &mut R,
 985         a: &traits::InEnvironment<'tcx, G>,
 986         b: &traits::InEnvironment<'tcx, G>,
 987     ) -> RelateResult<'tcx, traits::InEnvironment<'tcx, G>> {
 988         Ok(traits::InEnvironment {
 989             environment: relation.relate(&a.environment, &b.environment)?,
 990             goal: relation.relate(&a.goal, &b.goal)?,
 991         })
 992     }
 993 }
 994
 995 ///////////////////////////////////////////////////////////////////////////
 996 // Error handling
 997
 998 pub fn expected_found<R, T>(relation: &mut R, a: &T, b: &T) -> ExpectedFound<T>
 999 where
1000     R: TypeRelation<'tcx>,
1001     T: Clone,
1002 {
1003     expected_found_bool(relation.a_is_expected(), a, b)
1004 }
1005
1006 pub fn expected_found_bool<T>(a_is_expected: bool,
1007                               a: &T,
1008                               b: &T)
1009                               -> ExpectedFound<T>
1010     where T: Clone
1011 {
1012     let a = a.clone();
1013     let b = b.clone();
1014     if a_is_expected {
1015         ExpectedFound {expected: a, found: b}
1016     } else {
1017         ExpectedFound {expected: b, found: a}
1018     }
1019 }