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