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