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