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