src/librustc/ty/relate.rs

   1 // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Generalized type relating mechanism. A type relation R relates a
  12 //! pair of values (A, B). A and B are usually types or regions but
  13 //! can be other things. Examples of type relations are subtyping,
  14 //! type equality, etc.
  15
  16 use hir::def_id::DefId;
  17 use ty::subst::{ParamSpace, Substs};
  18 use ty::{self, Ty, TyCtxt, TypeFoldable};
  19 use ty::error::{ExpectedFound, TypeError};
  20 use std::rc::Rc;
  21 use syntax::abi;
  22 use hir as ast;
  23
  24 pub type RelateResult<'tcx, T> = Result<T, TypeError<'tcx>>;
  25
  26 #[derive(Clone, Debug)]
  27 pub enum Cause {
  28     ExistentialRegionBound, // relating an existential region bound
  29 }
  30
  31 pub trait TypeRelation<'a,'tcx> : Sized {
  32     fn tcx(&self) -> &'a TyCtxt<'tcx>;
  33
  34     /// Returns a static string we can use for printouts.
  35     fn tag(&self) -> &'static str;
  36
  37     /// Returns true if the value `a` is the "expected" type in the
  38     /// relation. Just affects error messages.
  39     fn a_is_expected(&self) -> bool;
  40
  41     fn with_cause<F,R>(&mut self, _cause: Cause, f: F) -> R
  42         where F: FnOnce(&mut Self) -> R
  43     {
  44         f(self)
  45     }
  46
  47     /// Generic relation routine suitable for most anything.
  48     fn relate<T:Relate<'a,'tcx>>(&mut self, a: &T, b: &T) -> RelateResult<'tcx, T> {
  49         Relate::relate(self, a, b)
  50     }
  51
  52     /// Relete elements of two slices pairwise.
  53     fn relate_zip<T:Relate<'a,'tcx>>(&mut self, a: &[T], b: &[T]) -> RelateResult<'tcx, Vec<T>> {
  54         assert_eq!(a.len(), b.len());
  55         a.iter().zip(b).map(|(a, b)| self.relate(a, b)).collect()
  56     }
  57
  58     /// Switch variance for the purpose of relating `a` and `b`.
  59     fn relate_with_variance<T:Relate<'a,'tcx>>(&mut self,
  60                                                variance: ty::Variance,
  61                                                a: &T,
  62                                                b: &T)
  63                                                -> RelateResult<'tcx, T>;
  64
  65     // Overrideable relations. You shouldn't typically call these
  66     // directly, instead call `relate()`, which in turn calls
  67     // these. This is both more uniform but also allows us to add
  68     // additional hooks for other types in the future if needed
  69     // without making older code, which called `relate`, obsolete.
  70
  71     fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>)
  72            -> RelateResult<'tcx, Ty<'tcx>>;
  73
  74     fn regions(&mut self, a: ty::Region, b: ty::Region)
  75                -> RelateResult<'tcx, ty::Region>;
  76
  77     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
  78                   -> RelateResult<'tcx, ty::Binder<T>>
  79         where T: Relate<'a,'tcx>;
  80 }
  81
  82 pub trait Relate<'a,'tcx>: TypeFoldable<'tcx> {
  83     fn relate<R:TypeRelation<'a,'tcx>>(relation: &mut R,
  84                                        a: &Self,
  85                                        b: &Self)
  86                                        -> RelateResult<'tcx, Self>;
  87 }
  88
  89 ///////////////////////////////////////////////////////////////////////////
  90 // Relate impls
  91
  92 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::TypeAndMut<'tcx> {
  93     fn relate<R>(relation: &mut R,
  94                  a: &ty::TypeAndMut<'tcx>,
  95                  b: &ty::TypeAndMut<'tcx>)
  96                  -> RelateResult<'tcx, ty::TypeAndMut<'tcx>>
  97         where R: TypeRelation<'a,'tcx>
  98     {
  99         debug!("{}.mts({:?}, {:?})",
 100                relation.tag(),
 101                a,
 102                b);
 103         if a.mutbl != b.mutbl {
 104             Err(TypeError::Mutability)
 105         } else {
 106             let mutbl = a.mutbl;
 107             let variance = match mutbl {
 108                 ast::Mutability::MutImmutable => ty::Covariant,
 109                 ast::Mutability::MutMutable => ty::Invariant,
 110             };
 111             let ty = relation.relate_with_variance(variance, &a.ty, &b.ty)?;
 112             Ok(ty::TypeAndMut {ty: ty, mutbl: mutbl})
 113         }
 114     }
 115 }
 116
 117 // substitutions are not themselves relatable without more context,
 118 // but they is an important subroutine for things that ARE relatable,
 119 // like traits etc.
 120 fn relate_item_substs<'a,'tcx:'a,R>(relation: &mut R,
 121                                     item_def_id: DefId,
 122                                     a_subst: &Substs<'tcx>,
 123                                     b_subst: &Substs<'tcx>)
 124                                     -> RelateResult<'tcx, Substs<'tcx>>
 125     where R: TypeRelation<'a,'tcx>
 126 {
 127     debug!("substs: item_def_id={:?} a_subst={:?} b_subst={:?}",
 128            item_def_id,
 129            a_subst,
 130            b_subst);
 131
 132     let variances;
 133     let opt_variances = if relation.tcx().variance_computed.get() {
 134         variances = relation.tcx().item_variances(item_def_id);
 135         Some(&*variances)
 136     } else {
 137         None
 138     };
 139     relate_substs(relation, opt_variances, a_subst, b_subst)
 140 }
 141
 142 pub fn relate_substs<'a,'tcx:'a,R>(relation: &mut R,
 143                                    variances: Option<&ty::ItemVariances>,
 144                                    a_subst: &Substs<'tcx>,
 145                                    b_subst: &Substs<'tcx>)
 146                                    -> RelateResult<'tcx, Substs<'tcx>>
 147     where R: TypeRelation<'a,'tcx>
 148 {
 149     let mut substs = Substs::empty();
 150
 151     for &space in &ParamSpace::all() {
 152         let a_tps = a_subst.types.get_slice(space);
 153         let b_tps = b_subst.types.get_slice(space);
 154         let t_variances = variances.map(|v| v.types.get_slice(space));
 155         let tps = relate_type_params(relation, t_variances, a_tps, b_tps)?;
 156         substs.types.replace(space, tps);
 157     }
 158
 159     for &space in &ParamSpace::all() {
 160         let a_regions = a_subst.regions.get_slice(space);
 161         let b_regions = b_subst.regions.get_slice(space);
 162         let r_variances = variances.map(|v| v.regions.get_slice(space));
 163         let regions = relate_region_params(relation,
 164                                            r_variances,
 165                                            a_regions,
 166                                            b_regions)?;
 167         substs.regions.replace(space, regions);
 168     }
 169
 170     Ok(substs)
 171 }
 172
 173 fn relate_type_params<'a,'tcx:'a,R>(relation: &mut R,
 174                                     variances: Option<&[ty::Variance]>,
 175                                     a_tys: &[Ty<'tcx>],
 176                                     b_tys: &[Ty<'tcx>])
 177                                     -> RelateResult<'tcx, Vec<Ty<'tcx>>>
 178     where R: TypeRelation<'a,'tcx>
 179 {
 180     if a_tys.len() != b_tys.len() {
 181         return Err(TypeError::TyParamSize(expected_found(relation,
 182                                                          &a_tys.len(),
 183                                                          &b_tys.len())));
 184     }
 185
 186     (0 .. a_tys.len())
 187         .map(|i| {
 188             let a_ty = a_tys[i];
 189             let b_ty = b_tys[i];
 190             let v = variances.map_or(ty::Invariant, |v| v[i]);
 191             relation.relate_with_variance(v, &a_ty, &b_ty)
 192         })
 193         .collect()
 194 }
 195
 196 fn relate_region_params<'a,'tcx:'a,R>(relation: &mut R,
 197                                       variances: Option<&[ty::Variance]>,
 198                                       a_rs: &[ty::Region],
 199                                       b_rs: &[ty::Region])
 200                                       -> RelateResult<'tcx, Vec<ty::Region>>
 201     where R: TypeRelation<'a,'tcx>
 202 {
 203     let num_region_params = a_rs.len();
 204
 205     debug!("relate_region_params(a_rs={:?}, \
 206             b_rs={:?}, variances={:?})",
 207            a_rs,
 208            b_rs,
 209            variances);
 210
 211     assert_eq!(num_region_params,
 212                variances.map_or(num_region_params,
 213                                 |v| v.len()));
 214
 215     assert_eq!(num_region_params, b_rs.len());
 216
 217     (0..a_rs.len())
 218         .map(|i| {
 219             let a_r = a_rs[i];
 220             let b_r = b_rs[i];
 221             let variance = variances.map_or(ty::Invariant, |v| v[i]);
 222             relation.relate_with_variance(variance, &a_r, &b_r)
 223         })
 224         .collect()
 225 }
 226
 227 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BareFnTy<'tcx> {
 228     fn relate<R>(relation: &mut R,
 229                  a: &ty::BareFnTy<'tcx>,
 230                  b: &ty::BareFnTy<'tcx>)
 231                  -> RelateResult<'tcx, ty::BareFnTy<'tcx>>
 232         where R: TypeRelation<'a,'tcx>
 233     {
 234         let unsafety = relation.relate(&a.unsafety, &b.unsafety)?;
 235         let abi = relation.relate(&a.abi, &b.abi)?;
 236         let sig = relation.relate(&a.sig, &b.sig)?;
 237         Ok(ty::BareFnTy {unsafety: unsafety,
 238                          abi: abi,
 239                          sig: sig})
 240     }
 241 }
 242
 243 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::FnSig<'tcx> {
 244     fn relate<R>(relation: &mut R,
 245                  a: &ty::FnSig<'tcx>,
 246                  b: &ty::FnSig<'tcx>)
 247                  -> RelateResult<'tcx, ty::FnSig<'tcx>>
 248         where R: TypeRelation<'a,'tcx>
 249     {
 250         if a.variadic != b.variadic {
 251             return Err(TypeError::VariadicMismatch(
 252                 expected_found(relation, &a.variadic, &b.variadic)));
 253         }
 254
 255         let inputs = relate_arg_vecs(relation,
 256                                      &a.inputs,
 257                                      &b.inputs)?;
 258
 259         let output = match (a.output, b.output) {
 260             (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) =>
 261                 Ok(ty::FnConverging(relation.relate(&a_ty, &b_ty)?)),
 262             (ty::FnDiverging, ty::FnDiverging) =>
 263                 Ok(ty::FnDiverging),
 264             (a, b) =>
 265                 Err(TypeError::ConvergenceMismatch(
 266                     expected_found(relation, &(a != ty::FnDiverging), &(b != ty::FnDiverging)))),
 267         }?;
 268
 269         return Ok(ty::FnSig {inputs: inputs,
 270                              output: output,
 271                              variadic: a.variadic});
 272     }
 273 }
 274
 275 fn relate_arg_vecs<'a,'tcx:'a,R>(relation: &mut R,
 276                                  a_args: &[Ty<'tcx>],
 277                                  b_args: &[Ty<'tcx>])
 278                                  -> RelateResult<'tcx, Vec<Ty<'tcx>>>
 279     where R: TypeRelation<'a,'tcx>
 280 {
 281     if a_args.len() != b_args.len() {
 282         return Err(TypeError::ArgCount);
 283     }
 284
 285     a_args.iter().zip(b_args)
 286           .map(|(a, b)| relation.relate_with_variance(ty::Contravariant, a, b))
 287           .collect()
 288 }
 289
 290 impl<'a,'tcx:'a> Relate<'a,'tcx> for ast::Unsafety {
 291     fn relate<R>(relation: &mut R,
 292                  a: &ast::Unsafety,
 293                  b: &ast::Unsafety)
 294                  -> RelateResult<'tcx, ast::Unsafety>
 295         where R: TypeRelation<'a,'tcx>
 296     {
 297         if a != b {
 298             Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
 299         } else {
 300             Ok(*a)
 301         }
 302     }
 303 }
 304
 305 impl<'a,'tcx:'a> Relate<'a,'tcx> for abi::Abi {
 306     fn relate<R>(relation: &mut R,
 307                  a: &abi::Abi,
 308                  b: &abi::Abi)
 309                  -> RelateResult<'tcx, abi::Abi>
 310         where R: TypeRelation<'a,'tcx>
 311     {
 312         if a == b {
 313             Ok(*a)
 314         } else {
 315             Err(TypeError::AbiMismatch(expected_found(relation, a, b)))
 316         }
 317     }
 318 }
 319
 320 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionTy<'tcx> {
 321     fn relate<R>(relation: &mut R,
 322                  a: &ty::ProjectionTy<'tcx>,
 323                  b: &ty::ProjectionTy<'tcx>)
 324                  -> RelateResult<'tcx, ty::ProjectionTy<'tcx>>
 325         where R: TypeRelation<'a,'tcx>
 326     {
 327         if a.item_name != b.item_name {
 328             Err(TypeError::ProjectionNameMismatched(
 329                 expected_found(relation, &a.item_name, &b.item_name)))
 330         } else {
 331             let trait_ref = relation.relate(&a.trait_ref, &b.trait_ref)?;
 332             Ok(ty::ProjectionTy { trait_ref: trait_ref, item_name: a.item_name })
 333         }
 334     }
 335 }
 336
 337 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionPredicate<'tcx> {
 338     fn relate<R>(relation: &mut R,
 339                  a: &ty::ProjectionPredicate<'tcx>,
 340                  b: &ty::ProjectionPredicate<'tcx>)
 341                  -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>>
 342         where R: TypeRelation<'a,'tcx>
 343     {
 344         let projection_ty = relation.relate(&a.projection_ty, &b.projection_ty)?;
 345         let ty = relation.relate(&a.ty, &b.ty)?;
 346         Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty })
 347     }
 348 }
 349
 350 impl<'a,'tcx:'a> Relate<'a,'tcx> for Vec<ty::PolyProjectionPredicate<'tcx>> {
 351     fn relate<R>(relation: &mut R,
 352                  a: &Vec<ty::PolyProjectionPredicate<'tcx>>,
 353                  b: &Vec<ty::PolyProjectionPredicate<'tcx>>)
 354                  -> RelateResult<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>>
 355         where R: TypeRelation<'a,'tcx>
 356     {
 357         // To be compatible, `a` and `b` must be for precisely the
 358         // same set of traits and item names. We always require that
 359         // projection bounds lists are sorted by trait-def-id and item-name,
 360         // so we can just iterate through the lists pairwise, so long as they are the
 361         // same length.
 362         if a.len() != b.len() {
 363             Err(TypeError::ProjectionBoundsLength(expected_found(relation, &a.len(), &b.len())))
 364         } else {
 365             a.iter().zip(b)
 366                 .map(|(a, b)| relation.relate(a, b))
 367                 .collect()
 368         }
 369     }
 370 }
 371
 372 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ExistentialBounds<'tcx> {
 373     fn relate<R>(relation: &mut R,
 374                  a: &ty::ExistentialBounds<'tcx>,
 375                  b: &ty::ExistentialBounds<'tcx>)
 376                  -> RelateResult<'tcx, ty::ExistentialBounds<'tcx>>
 377         where R: TypeRelation<'a,'tcx>
 378     {
 379         let r =
 380             relation.with_cause(
 381                 Cause::ExistentialRegionBound,
 382                 |relation| relation.relate_with_variance(ty::Contravariant,
 383                                                          &a.region_bound,
 384                                                          &b.region_bound))?;
 385         let nb = relation.relate(&a.builtin_bounds, &b.builtin_bounds)?;
 386         let pb = relation.relate(&a.projection_bounds, &b.projection_bounds)?;
 387         Ok(ty::ExistentialBounds { region_bound: r,
 388                                    builtin_bounds: nb,
 389                                    projection_bounds: pb })
 390     }
 391 }
 392
 393 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BuiltinBounds {
 394     fn relate<R>(relation: &mut R,
 395                  a: &ty::BuiltinBounds,
 396                  b: &ty::BuiltinBounds)
 397                  -> RelateResult<'tcx, ty::BuiltinBounds>
 398         where R: TypeRelation<'a,'tcx>
 399     {
 400         // Two sets of builtin bounds are only relatable if they are
 401         // precisely the same (but see the coercion code).
 402         if a != b {
 403             Err(TypeError::BuiltinBoundsMismatch(expected_found(relation, a, b)))
 404         } else {
 405             Ok(*a)
 406         }
 407     }
 408 }
 409
 410 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::TraitRef<'tcx> {
 411     fn relate<R>(relation: &mut R,
 412                  a: &ty::TraitRef<'tcx>,
 413                  b: &ty::TraitRef<'tcx>)
 414                  -> RelateResult<'tcx, ty::TraitRef<'tcx>>
 415         where R: TypeRelation<'a,'tcx>
 416     {
 417         // Different traits cannot be related
 418         if a.def_id != b.def_id {
 419             Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
 420         } else {
 421             let substs = relate_item_substs(relation, a.def_id, a.substs, b.substs)?;
 422             Ok(ty::TraitRef { def_id: a.def_id, substs: relation.tcx().mk_substs(substs) })
 423         }
 424     }
 425 }
 426
 427 impl<'a,'tcx:'a> Relate<'a,'tcx> for Ty<'tcx> {
 428     fn relate<R>(relation: &mut R,
 429                  a: &Ty<'tcx>,
 430                  b: &Ty<'tcx>)
 431                  -> RelateResult<'tcx, Ty<'tcx>>
 432         where R: TypeRelation<'a,'tcx>
 433     {
 434         relation.tys(a, b)
 435     }
 436 }
 437
 438 /// The main "type relation" routine. Note that this does not handle
 439 /// inference artifacts, so you should filter those out before calling
 440 /// it.
 441 pub fn super_relate_tys<'a,'tcx:'a,R>(relation: &mut R,
 442                                       a: Ty<'tcx>,
 443                                       b: Ty<'tcx>)
 444                                       -> RelateResult<'tcx, Ty<'tcx>>
 445     where R: TypeRelation<'a,'tcx>
 446 {
 447     let tcx = relation.tcx();
 448     let a_sty = &a.sty;
 449     let b_sty = &b.sty;
 450     debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
 451     match (a_sty, b_sty) {
 452         (&ty::TyInfer(_), _) |
 453         (_, &ty::TyInfer(_)) =>
 454         {
 455             // The caller should handle these cases!
 456             bug!("var types encountered in super_relate_tys")
 457         }
 458
 459         (&ty::TyError, _) | (_, &ty::TyError) =>
 460         {
 461             Ok(tcx.types.err)
 462         }
 463
 464         (&ty::TyChar, _) |
 465         (&ty::TyBool, _) |
 466         (&ty::TyInt(_), _) |
 467         (&ty::TyUint(_), _) |
 468         (&ty::TyFloat(_), _) |
 469         (&ty::TyStr, _)
 470             if a == b =>
 471         {
 472             Ok(a)
 473         }
 474
 475         (&ty::TyParam(ref a_p), &ty::TyParam(ref b_p))
 476             if a_p.idx == b_p.idx && a_p.space == b_p.space =>
 477         {
 478             Ok(a)
 479         }
 480
 481         (&ty::TyEnum(a_def, a_substs), &ty::TyEnum(b_def, b_substs))
 482             if a_def == b_def =>
 483         {
 484             let substs = relate_item_substs(relation, a_def.did, a_substs, b_substs)?;
 485             Ok(tcx.mk_enum(a_def, tcx.mk_substs(substs)))
 486         }
 487
 488         (&ty::TyTrait(ref a_), &ty::TyTrait(ref b_)) =>
 489         {
 490             let principal = relation.relate(&a_.principal, &b_.principal)?;
 491             let bounds = relation.relate(&a_.bounds, &b_.bounds)?;
 492             Ok(tcx.mk_trait(principal, bounds))
 493         }
 494
 495         (&ty::TyStruct(a_def, a_substs), &ty::TyStruct(b_def, b_substs))
 496             if a_def == b_def =>
 497         {
 498             let substs = relate_item_substs(relation, a_def.did, a_substs, b_substs)?;
 499             Ok(tcx.mk_struct(a_def, tcx.mk_substs(substs)))
 500         }
 501
 502         (&ty::TyClosure(a_id, ref a_substs),
 503          &ty::TyClosure(b_id, ref b_substs))
 504             if a_id == b_id =>
 505         {
 506             // All TyClosure types with the same id represent
 507             // the (anonymous) type of the same closure expression. So
 508             // all of their regions should be equated.
 509             let substs = relation.relate(a_substs, b_substs)?;
 510             Ok(tcx.mk_closure_from_closure_substs(a_id, substs))
 511         }
 512
 513         (&ty::TyBox(a_inner), &ty::TyBox(b_inner)) =>
 514         {
 515             let typ = relation.relate(&a_inner, &b_inner)?;
 516             Ok(tcx.mk_box(typ))
 517         }
 518
 519         (&ty::TyRawPtr(ref a_mt), &ty::TyRawPtr(ref b_mt)) =>
 520         {
 521             let mt = relation.relate(a_mt, b_mt)?;
 522             Ok(tcx.mk_ptr(mt))
 523         }
 524
 525         (&ty::TyRef(a_r, ref a_mt), &ty::TyRef(b_r, ref b_mt)) =>
 526         {
 527             let r = relation.relate_with_variance(ty::Contravariant, a_r, b_r)?;
 528             let mt = relation.relate(a_mt, b_mt)?;
 529             Ok(tcx.mk_ref(tcx.mk_region(r), mt))
 530         }
 531
 532         (&ty::TyArray(a_t, sz_a), &ty::TyArray(b_t, sz_b)) =>
 533         {
 534             let t = relation.relate(&a_t, &b_t)?;
 535             if sz_a == sz_b {
 536                 Ok(tcx.mk_array(t, sz_a))
 537             } else {
 538                 Err(TypeError::FixedArraySize(expected_found(relation, &sz_a, &sz_b)))
 539             }
 540         }
 541
 542         (&ty::TySlice(a_t), &ty::TySlice(b_t)) =>
 543         {
 544             let t = relation.relate(&a_t, &b_t)?;
 545             Ok(tcx.mk_slice(t))
 546         }
 547
 548         (&ty::TyTuple(ref as_), &ty::TyTuple(ref bs)) =>
 549         {
 550             if as_.len() == bs.len() {
 551                 let ts = as_.iter().zip(bs)
 552                             .map(|(a, b)| relation.relate(a, b))
 553                             .collect::<Result<_, _>>()?;
 554                 Ok(tcx.mk_tup(ts))
 555             } else if !(as_.is_empty() || bs.is_empty()) {
 556                 Err(TypeError::TupleSize(
 557                     expected_found(relation, &as_.len(), &bs.len())))
 558             } else {
 559                 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 560             }
 561         }
 562
 563         (&ty::TyFnDef(a_def_id, a_substs, a_fty),
 564          &ty::TyFnDef(b_def_id, b_substs, b_fty))
 565             if a_def_id == b_def_id =>
 566         {
 567             let substs = relate_substs(relation, None, a_substs, b_substs)?;
 568             let fty = relation.relate(a_fty, b_fty)?;
 569             Ok(tcx.mk_fn_def(a_def_id, tcx.mk_substs(substs), fty))
 570         }
 571
 572         (&ty::TyFnPtr(a_fty), &ty::TyFnPtr(b_fty)) =>
 573         {
 574             let fty = relation.relate(a_fty, b_fty)?;
 575             Ok(tcx.mk_fn_ptr(fty))
 576         }
 577
 578         (&ty::TyProjection(ref a_data), &ty::TyProjection(ref b_data)) =>
 579         {
 580             let projection_ty = relation.relate(a_data, b_data)?;
 581             Ok(tcx.mk_projection(projection_ty.trait_ref, projection_ty.item_name))
 582         }
 583
 584         _ =>
 585         {
 586             Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 587         }
 588     }
 589 }
 590
 591 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ClosureSubsts<'tcx> {
 592     fn relate<R>(relation: &mut R,
 593                  a: &ty::ClosureSubsts<'tcx>,
 594                  b: &ty::ClosureSubsts<'tcx>)
 595                  -> RelateResult<'tcx, ty::ClosureSubsts<'tcx>>
 596         where R: TypeRelation<'a,'tcx>
 597     {
 598         let func_substs = relate_substs(relation, None, a.func_substs, b.func_substs)?;
 599         let upvar_tys = relation.relate_zip(&a.upvar_tys, &b.upvar_tys)?;
 600         Ok(ty::ClosureSubsts { func_substs: relation.tcx().mk_substs(func_substs),
 601                                upvar_tys: upvar_tys })
 602     }
 603 }
 604
 605 impl<'a,'tcx:'a> Relate<'a,'tcx> for Substs<'tcx> {
 606     fn relate<R>(relation: &mut R,
 607                  a: &Substs<'tcx>,
 608                  b: &Substs<'tcx>)
 609                  -> RelateResult<'tcx, Substs<'tcx>>
 610         where R: TypeRelation<'a,'tcx>
 611     {
 612         relate_substs(relation, None, a, b)
 613     }
 614 }
 615
 616 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::Region {
 617     fn relate<R>(relation: &mut R,
 618                  a: &ty::Region,
 619                  b: &ty::Region)
 620                  -> RelateResult<'tcx, ty::Region>
 621         where R: TypeRelation<'a,'tcx>
 622     {
 623         relation.regions(*a, *b)
 624     }
 625 }
 626
 627 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for ty::Binder<T>
 628     where T: Relate<'a,'tcx>
 629 {
 630     fn relate<R>(relation: &mut R,
 631                  a: &ty::Binder<T>,
 632                  b: &ty::Binder<T>)
 633                  -> RelateResult<'tcx, ty::Binder<T>>
 634         where R: TypeRelation<'a,'tcx>
 635     {
 636         relation.binders(a, b)
 637     }
 638 }
 639
 640 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Rc<T>
 641     where T: Relate<'a,'tcx>
 642 {
 643     fn relate<R>(relation: &mut R,
 644                  a: &Rc<T>,
 645                  b: &Rc<T>)
 646                  -> RelateResult<'tcx, Rc<T>>
 647         where R: TypeRelation<'a,'tcx>
 648     {
 649         let a: &T = a;
 650         let b: &T = b;
 651         Ok(Rc::new(relation.relate(a, b)?))
 652     }
 653 }
 654
 655 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Box<T>
 656     where T: Relate<'a,'tcx>
 657 {
 658     fn relate<R>(relation: &mut R,
 659                  a: &Box<T>,
 660                  b: &Box<T>)
 661                  -> RelateResult<'tcx, Box<T>>
 662         where R: TypeRelation<'a,'tcx>
 663     {
 664         let a: &T = a;
 665         let b: &T = b;
 666         Ok(Box::new(relation.relate(a, b)?))
 667     }
 668 }
 669
 670 ///////////////////////////////////////////////////////////////////////////
 671 // Error handling
 672
 673 pub fn expected_found<'a,'tcx:'a,R,T>(relation: &mut R,
 674                                       a: &T,
 675                                       b: &T)
 676                                       -> ExpectedFound<T>
 677     where R: TypeRelation<'a,'tcx>, T: Clone
 678 {
 679     expected_found_bool(relation.a_is_expected(), a, b)
 680 }
 681
 682 pub fn expected_found_bool<T>(a_is_expected: bool,
 683                               a: &T,
 684                               b: &T)
 685                               -> ExpectedFound<T>
 686     where T: Clone
 687 {
 688     let a = a.clone();
 689     let b = b.clone();
 690     if a_is_expected {
 691         ExpectedFound {expected: a, found: b}
 692     } else {
 693         ExpectedFound {expected: b, found: a}
 694     }
 695 }