src/librustc/middle/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 middle::def_id::DefId;
  17 use middle::subst::{ErasedRegions, NonerasedRegions, ParamSpace, Substs};
  18 use middle::ty::{self, Ty, TypeFoldable};
  19 use middle::ty::error::{ExpectedFound, TypeError};
  20 use std::rc::Rc;
  21 use syntax::abi;
  22 use rustc_front::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 ty::ctxt<'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 = try!(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 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 = try!(relate_type_params(relation, t_variances, a_tps, b_tps));
 156         substs.types.replace(space, tps);
 157     }
 158
 159     match (&a_subst.regions, &b_subst.regions) {
 160         (&ErasedRegions, _) | (_, &ErasedRegions) => {
 161             substs.regions = ErasedRegions;
 162         }
 163
 164         (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => {
 165             for &space in &ParamSpace::all() {
 166                 let a_regions = a.get_slice(space);
 167                 let b_regions = b.get_slice(space);
 168                 let r_variances = variances.map(|v| v.regions.get_slice(space));
 169                 let regions = try!(relate_region_params(relation,
 170                                                         r_variances,
 171                                                         a_regions,
 172                                                         b_regions));
 173                 substs.mut_regions().replace(space, regions);
 174             }
 175         }
 176     }
 177
 178     Ok(substs)
 179 }
 180
 181 fn relate_type_params<'a,'tcx:'a,R>(relation: &mut R,
 182                                     variances: Option<&[ty::Variance]>,
 183                                     a_tys: &[Ty<'tcx>],
 184                                     b_tys: &[Ty<'tcx>])
 185                                     -> RelateResult<'tcx, Vec<Ty<'tcx>>>
 186     where R: TypeRelation<'a,'tcx>
 187 {
 188     if a_tys.len() != b_tys.len() {
 189         return Err(TypeError::TyParamSize(expected_found(relation,
 190                                                          &a_tys.len(),
 191                                                          &b_tys.len())));
 192     }
 193
 194     (0 .. a_tys.len())
 195         .map(|i| {
 196             let a_ty = a_tys[i];
 197             let b_ty = b_tys[i];
 198             let v = variances.map_or(ty::Invariant, |v| v[i]);
 199             relation.relate_with_variance(v, &a_ty, &b_ty)
 200         })
 201         .collect()
 202 }
 203
 204 fn relate_region_params<'a,'tcx:'a,R>(relation: &mut R,
 205                                       variances: Option<&[ty::Variance]>,
 206                                       a_rs: &[ty::Region],
 207                                       b_rs: &[ty::Region])
 208                                       -> RelateResult<'tcx, Vec<ty::Region>>
 209     where R: TypeRelation<'a,'tcx>
 210 {
 211     let num_region_params = a_rs.len();
 212
 213     debug!("relate_region_params(a_rs={:?}, \
 214             b_rs={:?}, variances={:?})",
 215            a_rs,
 216            b_rs,
 217            variances);
 218
 219     assert_eq!(num_region_params,
 220                variances.map_or(num_region_params,
 221                                 |v| v.len()));
 222
 223     assert_eq!(num_region_params, b_rs.len());
 224
 225     (0..a_rs.len())
 226         .map(|i| {
 227             let a_r = a_rs[i];
 228             let b_r = b_rs[i];
 229             let variance = variances.map_or(ty::Invariant, |v| v[i]);
 230             relation.relate_with_variance(variance, &a_r, &b_r)
 231         })
 232         .collect()
 233 }
 234
 235 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BareFnTy<'tcx> {
 236     fn relate<R>(relation: &mut R,
 237                  a: &ty::BareFnTy<'tcx>,
 238                  b: &ty::BareFnTy<'tcx>)
 239                  -> RelateResult<'tcx, ty::BareFnTy<'tcx>>
 240         where R: TypeRelation<'a,'tcx>
 241     {
 242         let unsafety = try!(relation.relate(&a.unsafety, &b.unsafety));
 243         let abi = try!(relation.relate(&a.abi, &b.abi));
 244         let sig = try!(relation.relate(&a.sig, &b.sig));
 245         Ok(ty::BareFnTy {unsafety: unsafety,
 246                          abi: abi,
 247                          sig: sig})
 248     }
 249 }
 250
 251 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::FnSig<'tcx> {
 252     fn relate<R>(relation: &mut R,
 253                  a: &ty::FnSig<'tcx>,
 254                  b: &ty::FnSig<'tcx>)
 255                  -> RelateResult<'tcx, ty::FnSig<'tcx>>
 256         where R: TypeRelation<'a,'tcx>
 257     {
 258         if a.variadic != b.variadic {
 259             return Err(TypeError::VariadicMismatch(
 260                 expected_found(relation, &a.variadic, &b.variadic)));
 261         }
 262
 263         let inputs = try!(relate_arg_vecs(relation,
 264                                           &a.inputs,
 265                                           &b.inputs));
 266
 267         let output = try!(match (a.output, b.output) {
 268             (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) =>
 269                 Ok(ty::FnConverging(try!(relation.relate(&a_ty, &b_ty)))),
 270             (ty::FnDiverging, ty::FnDiverging) =>
 271                 Ok(ty::FnDiverging),
 272             (a, b) =>
 273                 Err(TypeError::ConvergenceMismatch(
 274                     expected_found(relation, &(a != ty::FnDiverging), &(b != ty::FnDiverging)))),
 275         });
 276
 277         return Ok(ty::FnSig {inputs: inputs,
 278                              output: output,
 279                              variadic: a.variadic});
 280     }
 281 }
 282
 283 fn relate_arg_vecs<'a,'tcx:'a,R>(relation: &mut R,
 284                                  a_args: &[Ty<'tcx>],
 285                                  b_args: &[Ty<'tcx>])
 286                                  -> RelateResult<'tcx, Vec<Ty<'tcx>>>
 287     where R: TypeRelation<'a,'tcx>
 288 {
 289     if a_args.len() != b_args.len() {
 290         return Err(TypeError::ArgCount);
 291     }
 292
 293     a_args.iter().zip(b_args)
 294           .map(|(a, b)| relation.relate_with_variance(ty::Contravariant, a, b))
 295           .collect()
 296 }
 297
 298 impl<'a,'tcx:'a> Relate<'a,'tcx> for ast::Unsafety {
 299     fn relate<R>(relation: &mut R,
 300                  a: &ast::Unsafety,
 301                  b: &ast::Unsafety)
 302                  -> RelateResult<'tcx, ast::Unsafety>
 303         where R: TypeRelation<'a,'tcx>
 304     {
 305         if a != b {
 306             Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
 307         } else {
 308             Ok(*a)
 309         }
 310     }
 311 }
 312
 313 impl<'a,'tcx:'a> Relate<'a,'tcx> for abi::Abi {
 314     fn relate<R>(relation: &mut R,
 315                  a: &abi::Abi,
 316                  b: &abi::Abi)
 317                  -> RelateResult<'tcx, abi::Abi>
 318         where R: TypeRelation<'a,'tcx>
 319     {
 320         if a == b {
 321             Ok(*a)
 322         } else {
 323             Err(TypeError::AbiMismatch(expected_found(relation, a, b)))
 324         }
 325     }
 326 }
 327
 328 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionTy<'tcx> {
 329     fn relate<R>(relation: &mut R,
 330                  a: &ty::ProjectionTy<'tcx>,
 331                  b: &ty::ProjectionTy<'tcx>)
 332                  -> RelateResult<'tcx, ty::ProjectionTy<'tcx>>
 333         where R: TypeRelation<'a,'tcx>
 334     {
 335         if a.item_name != b.item_name {
 336             Err(TypeError::ProjectionNameMismatched(
 337                 expected_found(relation, &a.item_name, &b.item_name)))
 338         } else {
 339             let trait_ref = try!(relation.relate(&a.trait_ref, &b.trait_ref));
 340             Ok(ty::ProjectionTy { trait_ref: trait_ref, item_name: a.item_name })
 341         }
 342     }
 343 }
 344
 345 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionPredicate<'tcx> {
 346     fn relate<R>(relation: &mut R,
 347                  a: &ty::ProjectionPredicate<'tcx>,
 348                  b: &ty::ProjectionPredicate<'tcx>)
 349                  -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>>
 350         where R: TypeRelation<'a,'tcx>
 351     {
 352         let projection_ty = try!(relation.relate(&a.projection_ty, &b.projection_ty));
 353         let ty = try!(relation.relate(&a.ty, &b.ty));
 354         Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty })
 355     }
 356 }
 357
 358 impl<'a,'tcx:'a> Relate<'a,'tcx> for Vec<ty::PolyProjectionPredicate<'tcx>> {
 359     fn relate<R>(relation: &mut R,
 360                  a: &Vec<ty::PolyProjectionPredicate<'tcx>>,
 361                  b: &Vec<ty::PolyProjectionPredicate<'tcx>>)
 362                  -> RelateResult<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>>
 363         where R: TypeRelation<'a,'tcx>
 364     {
 365         // To be compatible, `a` and `b` must be for precisely the
 366         // same set of traits and item names. We always require that
 367         // projection bounds lists are sorted by trait-def-id and item-name,
 368         // so we can just iterate through the lists pairwise, so long as they are the
 369         // same length.
 370         if a.len() != b.len() {
 371             Err(TypeError::ProjectionBoundsLength(expected_found(relation, &a.len(), &b.len())))
 372         } else {
 373             a.iter().zip(b)
 374                 .map(|(a, b)| relation.relate(a, b))
 375                 .collect()
 376         }
 377     }
 378 }
 379
 380 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ExistentialBounds<'tcx> {
 381     fn relate<R>(relation: &mut R,
 382                  a: &ty::ExistentialBounds<'tcx>,
 383                  b: &ty::ExistentialBounds<'tcx>)
 384                  -> RelateResult<'tcx, ty::ExistentialBounds<'tcx>>
 385         where R: TypeRelation<'a,'tcx>
 386     {
 387         let r =
 388             try!(relation.with_cause(
 389                 Cause::ExistentialRegionBound,
 390                 |relation| relation.relate_with_variance(ty::Contravariant,
 391                                                          &a.region_bound,
 392                                                          &b.region_bound)));
 393         let nb = try!(relation.relate(&a.builtin_bounds, &b.builtin_bounds));
 394         let pb = try!(relation.relate(&a.projection_bounds, &b.projection_bounds));
 395         Ok(ty::ExistentialBounds { region_bound: r,
 396                                    builtin_bounds: nb,
 397                                    projection_bounds: pb })
 398     }
 399 }
 400
 401 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BuiltinBounds {
 402     fn relate<R>(relation: &mut R,
 403                  a: &ty::BuiltinBounds,
 404                  b: &ty::BuiltinBounds)
 405                  -> RelateResult<'tcx, ty::BuiltinBounds>
 406         where R: TypeRelation<'a,'tcx>
 407     {
 408         // Two sets of builtin bounds are only relatable if they are
 409         // precisely the same (but see the coercion code).
 410         if a != b {
 411             Err(TypeError::BuiltinBoundsMismatch(expected_found(relation, a, b)))
 412         } else {
 413             Ok(*a)
 414         }
 415     }
 416 }
 417
 418 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::TraitRef<'tcx> {
 419     fn relate<R>(relation: &mut R,
 420                  a: &ty::TraitRef<'tcx>,
 421                  b: &ty::TraitRef<'tcx>)
 422                  -> RelateResult<'tcx, ty::TraitRef<'tcx>>
 423         where R: TypeRelation<'a,'tcx>
 424     {
 425         // Different traits cannot be related
 426         if a.def_id != b.def_id {
 427             Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
 428         } else {
 429             let substs = try!(relate_item_substs(relation, a.def_id, a.substs, b.substs));
 430             Ok(ty::TraitRef { def_id: a.def_id, substs: relation.tcx().mk_substs(substs) })
 431         }
 432     }
 433 }
 434
 435 impl<'a,'tcx:'a> Relate<'a,'tcx> for Ty<'tcx> {
 436     fn relate<R>(relation: &mut R,
 437                  a: &Ty<'tcx>,
 438                  b: &Ty<'tcx>)
 439                  -> RelateResult<'tcx, Ty<'tcx>>
 440         where R: TypeRelation<'a,'tcx>
 441     {
 442         relation.tys(a, b)
 443     }
 444 }
 445
 446 /// The main "type relation" routine. Note that this does not handle
 447 /// inference artifacts, so you should filter those out before calling
 448 /// it.
 449 pub fn super_relate_tys<'a,'tcx:'a,R>(relation: &mut R,
 450                                       a: Ty<'tcx>,
 451                                       b: Ty<'tcx>)
 452                                       -> RelateResult<'tcx, Ty<'tcx>>
 453     where R: TypeRelation<'a,'tcx>
 454 {
 455     let tcx = relation.tcx();
 456     let a_sty = &a.sty;
 457     let b_sty = &b.sty;
 458     debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
 459     match (a_sty, b_sty) {
 460         (&ty::TyInfer(_), _) |
 461         (_, &ty::TyInfer(_)) =>
 462         {
 463             // The caller should handle these cases!
 464             tcx.sess.bug("var types encountered in super_relate_tys")
 465         }
 466
 467         (&ty::TyError, _) | (_, &ty::TyError) =>
 468         {
 469             Ok(tcx.types.err)
 470         }
 471
 472         (&ty::TyChar, _) |
 473         (&ty::TyBool, _) |
 474         (&ty::TyInt(_), _) |
 475         (&ty::TyUint(_), _) |
 476         (&ty::TyFloat(_), _) |
 477         (&ty::TyStr, _)
 478             if a == b =>
 479         {
 480             Ok(a)
 481         }
 482
 483         (&ty::TyParam(ref a_p), &ty::TyParam(ref b_p))
 484             if a_p.idx == b_p.idx && a_p.space == b_p.space =>
 485         {
 486             Ok(a)
 487         }
 488
 489         (&ty::TyEnum(a_def, a_substs), &ty::TyEnum(b_def, b_substs))
 490             if a_def == b_def =>
 491         {
 492             let substs = try!(relate_item_substs(relation, a_def.did, a_substs, b_substs));
 493             Ok(tcx.mk_enum(a_def, tcx.mk_substs(substs)))
 494         }
 495
 496         (&ty::TyTrait(ref a_), &ty::TyTrait(ref b_)) =>
 497         {
 498             let principal = try!(relation.relate(&a_.principal, &b_.principal));
 499             let bounds = try!(relation.relate(&a_.bounds, &b_.bounds));
 500             Ok(tcx.mk_trait(principal, bounds))
 501         }
 502
 503         (&ty::TyStruct(a_def, a_substs), &ty::TyStruct(b_def, b_substs))
 504             if a_def == b_def =>
 505         {
 506             let substs = try!(relate_item_substs(relation, a_def.did, a_substs, b_substs));
 507             Ok(tcx.mk_struct(a_def, tcx.mk_substs(substs)))
 508         }
 509
 510         (&ty::TyClosure(a_id, ref a_substs),
 511          &ty::TyClosure(b_id, ref b_substs))
 512             if a_id == b_id =>
 513         {
 514             // All TyClosure types with the same id represent
 515             // the (anonymous) type of the same closure expression. So
 516             // all of their regions should be equated.
 517             let substs = try!(relation.relate(a_substs, b_substs));
 518             Ok(tcx.mk_closure_from_closure_substs(a_id, substs))
 519         }
 520
 521         (&ty::TyBox(a_inner), &ty::TyBox(b_inner)) =>
 522         {
 523             let typ = try!(relation.relate(&a_inner, &b_inner));
 524             Ok(tcx.mk_box(typ))
 525         }
 526
 527         (&ty::TyRawPtr(ref a_mt), &ty::TyRawPtr(ref b_mt)) =>
 528         {
 529             let mt = try!(relation.relate(a_mt, b_mt));
 530             Ok(tcx.mk_ptr(mt))
 531         }
 532
 533         (&ty::TyRef(a_r, ref a_mt), &ty::TyRef(b_r, ref b_mt)) =>
 534         {
 535             let r = try!(relation.relate_with_variance(ty::Contravariant, a_r, b_r));
 536             let mt = try!(relation.relate(a_mt, b_mt));
 537             Ok(tcx.mk_ref(tcx.mk_region(r), mt))
 538         }
 539
 540         (&ty::TyArray(a_t, sz_a), &ty::TyArray(b_t, sz_b)) =>
 541         {
 542             let t = try!(relation.relate(&a_t, &b_t));
 543             if sz_a == sz_b {
 544                 Ok(tcx.mk_array(t, sz_a))
 545             } else {
 546                 Err(TypeError::FixedArraySize(expected_found(relation, &sz_a, &sz_b)))
 547             }
 548         }
 549
 550         (&ty::TySlice(a_t), &ty::TySlice(b_t)) =>
 551         {
 552             let t = try!(relation.relate(&a_t, &b_t));
 553             Ok(tcx.mk_slice(t))
 554         }
 555
 556         (&ty::TyTuple(ref as_), &ty::TyTuple(ref bs)) =>
 557         {
 558             if as_.len() == bs.len() {
 559                 let ts = try!(as_.iter().zip(bs)
 560                                  .map(|(a, b)| relation.relate(a, b))
 561                                  .collect::<Result<_, _>>());
 562                 Ok(tcx.mk_tup(ts))
 563             } else if !(as_.is_empty() || bs.is_empty()) {
 564                 Err(TypeError::TupleSize(
 565                     expected_found(relation, &as_.len(), &bs.len())))
 566             } else {
 567                 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 568             }
 569         }
 570
 571         (&ty::TyBareFn(a_opt_def_id, a_fty), &ty::TyBareFn(b_opt_def_id, b_fty))
 572             if a_opt_def_id == b_opt_def_id =>
 573         {
 574             let fty = try!(relation.relate(a_fty, b_fty));
 575             Ok(tcx.mk_fn(a_opt_def_id, tcx.mk_bare_fn(fty)))
 576         }
 577
 578         (&ty::TyProjection(ref a_data), &ty::TyProjection(ref b_data)) =>
 579         {
 580             let projection_ty = try!(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 = try!(relate_substs(relation, None, a.func_substs, b.func_substs));
 599         let upvar_tys = try!(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 ty::Region {
 606     fn relate<R>(relation: &mut R,
 607                  a: &ty::Region,
 608                  b: &ty::Region)
 609                  -> RelateResult<'tcx, ty::Region>
 610         where R: TypeRelation<'a,'tcx>
 611     {
 612         relation.regions(*a, *b)
 613     }
 614 }
 615
 616 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for ty::Binder<T>
 617     where T: Relate<'a,'tcx>
 618 {
 619     fn relate<R>(relation: &mut R,
 620                  a: &ty::Binder<T>,
 621                  b: &ty::Binder<T>)
 622                  -> RelateResult<'tcx, ty::Binder<T>>
 623         where R: TypeRelation<'a,'tcx>
 624     {
 625         relation.binders(a, b)
 626     }
 627 }
 628
 629 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Rc<T>
 630     where T: Relate<'a,'tcx>
 631 {
 632     fn relate<R>(relation: &mut R,
 633                  a: &Rc<T>,
 634                  b: &Rc<T>)
 635                  -> RelateResult<'tcx, Rc<T>>
 636         where R: TypeRelation<'a,'tcx>
 637     {
 638         let a: &T = a;
 639         let b: &T = b;
 640         Ok(Rc::new(try!(relation.relate(a, b))))
 641     }
 642 }
 643
 644 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Box<T>
 645     where T: Relate<'a,'tcx>
 646 {
 647     fn relate<R>(relation: &mut R,
 648                  a: &Box<T>,
 649                  b: &Box<T>)
 650                  -> RelateResult<'tcx, Box<T>>
 651         where R: TypeRelation<'a,'tcx>
 652     {
 653         let a: &T = a;
 654         let b: &T = b;
 655         Ok(Box::new(try!(relation.relate(a, b))))
 656     }
 657 }
 658
 659 ///////////////////////////////////////////////////////////////////////////
 660 // Error handling
 661
 662 pub fn expected_found<'a,'tcx:'a,R,T>(relation: &mut R,
 663                                       a: &T,
 664                                       b: &T)
 665                                       -> ExpectedFound<T>
 666     where R: TypeRelation<'a,'tcx>, T: Clone
 667 {
 668     expected_found_bool(relation.a_is_expected(), a, b)
 669 }
 670
 671 pub fn expected_found_bool<T>(a_is_expected: bool,
 672                               a: &T,
 673                               b: &T)
 674                               -> ExpectedFound<T>
 675     where T: Clone
 676 {
 677     let a = a.clone();
 678     let b = b.clone();
 679     if a_is_expected {
 680         ExpectedFound {expected: a, found: b}
 681     } else {
 682         ExpectedFound {expected: b, found: a}
 683     }
 684 }