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