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 std::iter;
  22 use syntax::abi;
  23 use hir as ast;
  24 use rustc_data_structures::accumulate_vec::AccumulateVec;
  25
  26 pub type RelateResult<'tcx, T> = Result<T, TypeError<'tcx>>;
  27
  28 #[derive(Clone, Debug)]
  29 pub enum Cause {
  30     ExistentialRegionBound, // relating an existential region bound
  31 }
  32
  33 pub trait TypeRelation<'a, 'gcx: 'a+'tcx, 'tcx: 'a> : Sized {
  34     fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx>;
  35
  36     /// Returns a static string we can use for printouts.
  37     fn tag(&self) -> &'static str;
  38
  39     /// Returns true if the value `a` is the "expected" type in the
  40     /// relation. Just affects error messages.
  41     fn a_is_expected(&self) -> bool;
  42
  43     fn with_cause<F,R>(&mut self, _cause: Cause, f: F) -> R
  44         where F: FnOnce(&mut Self) -> R
  45     {
  46         f(self)
  47     }
  48
  49     /// Generic relation routine suitable for most anything.
  50     fn relate<T: Relate<'tcx>>(&mut self, a: &T, b: &T) -> RelateResult<'tcx, T> {
  51         Relate::relate(self, a, b)
  52     }
  53
  54     /// Relate the two substitutions for the given item. The default
  55     /// is to look up the variance for the item and proceed
  56     /// accordingly.
  57     fn relate_item_substs(&mut self,
  58                           item_def_id: DefId,
  59                           a_subst: &'tcx Substs<'tcx>,
  60                           b_subst: &'tcx Substs<'tcx>)
  61                           -> RelateResult<'tcx, &'tcx Substs<'tcx>>
  62     {
  63         debug!("relate_item_substs(item_def_id={:?}, a_subst={:?}, b_subst={:?})",
  64                item_def_id,
  65                a_subst,
  66                b_subst);
  67
  68         let opt_variances = self.tcx().variances_of(item_def_id);
  69         relate_substs(self, Some(&opt_variances), a_subst, b_subst)
  70     }
  71
  72     /// Switch variance for the purpose of relating `a` and `b`.
  73     fn relate_with_variance<T: Relate<'tcx>>(&mut self,
  74                                              variance: ty::Variance,
  75                                              a: &T,
  76                                              b: &T)
  77                                              -> RelateResult<'tcx, T>;
  78
  79     // Overrideable relations. You shouldn't typically call these
  80     // directly, instead call `relate()`, which in turn calls
  81     // these. This is both more uniform but also allows us to add
  82     // additional hooks for other types in the future if needed
  83     // without making older code, which called `relate`, obsolete.
  84
  85     fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>)
  86            -> RelateResult<'tcx, Ty<'tcx>>;
  87
  88     fn regions(&mut self, a: ty::Region<'tcx>, b: ty::Region<'tcx>)
  89                -> RelateResult<'tcx, ty::Region<'tcx>>;
  90
  91     fn binders<T>(&mut self, a: &ty::Binder<T>, b: &ty::Binder<T>)
  92                   -> RelateResult<'tcx, ty::Binder<T>>
  93         where T: Relate<'tcx>;
  94 }
  95
  96 pub trait Relate<'tcx>: TypeFoldable<'tcx> {
  97     fn relate<'a, 'gcx, R>(relation: &mut R, a: &Self, b: &Self)
  98                            -> RelateResult<'tcx, Self>
  99         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a;
 100 }
 101
 102 ///////////////////////////////////////////////////////////////////////////
 103 // Relate impls
 104
 105 impl<'tcx> Relate<'tcx> for ty::TypeAndMut<'tcx> {
 106     fn relate<'a, 'gcx, R>(relation: &mut R,
 107                            a: &ty::TypeAndMut<'tcx>,
 108                            b: &ty::TypeAndMut<'tcx>)
 109                            -> RelateResult<'tcx, ty::TypeAndMut<'tcx>>
 110         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 111     {
 112         debug!("{}.mts({:?}, {:?})",
 113                relation.tag(),
 114                a,
 115                b);
 116         if a.mutbl != b.mutbl {
 117             Err(TypeError::Mutability)
 118         } else {
 119             let mutbl = a.mutbl;
 120             let variance = match mutbl {
 121                 ast::Mutability::MutImmutable => ty::Covariant,
 122                 ast::Mutability::MutMutable => ty::Invariant,
 123             };
 124             let ty = relation.relate_with_variance(variance, &a.ty, &b.ty)?;
 125             Ok(ty::TypeAndMut {ty: ty, mutbl: mutbl})
 126         }
 127     }
 128 }
 129
 130 pub fn relate_substs<'a, 'gcx, 'tcx, R>(relation: &mut R,
 131                                         variances: Option<&Vec<ty::Variance>>,
 132                                         a_subst: &'tcx Substs<'tcx>,
 133                                         b_subst: &'tcx Substs<'tcx>)
 134                                         -> RelateResult<'tcx, &'tcx Substs<'tcx>>
 135     where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 136 {
 137     let tcx = relation.tcx();
 138
 139     let params = a_subst.iter().zip(b_subst).enumerate().map(|(i, (a, b))| {
 140         let variance = variances.map_or(ty::Invariant, |v| v[i]);
 141         if let (Some(a_ty), Some(b_ty)) = (a.as_type(), b.as_type()) {
 142             Ok(Kind::from(relation.relate_with_variance(variance, &a_ty, &b_ty)?))
 143         } else if let (Some(a_r), Some(b_r)) = (a.as_region(), b.as_region()) {
 144             Ok(Kind::from(relation.relate_with_variance(variance, &a_r, &b_r)?))
 145         } else {
 146             bug!()
 147         }
 148     });
 149
 150     Ok(tcx.mk_substs(params)?)
 151 }
 152
 153 impl<'tcx> Relate<'tcx> for ty::FnSig<'tcx> {
 154     fn relate<'a, 'gcx, R>(relation: &mut R,
 155                            a: &ty::FnSig<'tcx>,
 156                            b: &ty::FnSig<'tcx>)
 157                            -> RelateResult<'tcx, ty::FnSig<'tcx>>
 158         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 159     {
 160         if a.variadic != b.variadic {
 161             return Err(TypeError::VariadicMismatch(
 162                 expected_found(relation, &a.variadic, &b.variadic)));
 163         }
 164         let unsafety = relation.relate(&a.unsafety, &b.unsafety)?;
 165         let abi = relation.relate(&a.abi, &b.abi)?;
 166
 167         if a.inputs().len() != b.inputs().len() {
 168             return Err(TypeError::ArgCount);
 169         }
 170
 171         let inputs_and_output = a.inputs().iter().cloned()
 172             .zip(b.inputs().iter().cloned())
 173             .map(|x| (x, false))
 174             .chain(iter::once(((a.output(), b.output()), true)))
 175             .map(|((a, b), is_output)| {
 176                 if is_output {
 177                     relation.relate(&a, &b)
 178                 } else {
 179                     relation.relate_with_variance(ty::Contravariant, &a, &b)
 180                 }
 181             }).collect::<Result<AccumulateVec<[_; 8]>, _>>()?;
 182         Ok(ty::FnSig {
 183             inputs_and_output: relation.tcx().intern_type_list(&inputs_and_output),
 184             variadic: a.variadic,
 185             unsafety: unsafety,
 186             abi: abi
 187         })
 188     }
 189 }
 190
 191 impl<'tcx> Relate<'tcx> for ast::Unsafety {
 192     fn relate<'a, 'gcx, R>(relation: &mut R,
 193                            a: &ast::Unsafety,
 194                            b: &ast::Unsafety)
 195                            -> RelateResult<'tcx, ast::Unsafety>
 196         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 197     {
 198         if a != b {
 199             Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
 200         } else {
 201             Ok(*a)
 202         }
 203     }
 204 }
 205
 206 impl<'tcx> Relate<'tcx> for abi::Abi {
 207     fn relate<'a, 'gcx, R>(relation: &mut R,
 208                            a: &abi::Abi,
 209                            b: &abi::Abi)
 210                            -> RelateResult<'tcx, abi::Abi>
 211         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 212     {
 213         if a == b {
 214             Ok(*a)
 215         } else {
 216             Err(TypeError::AbiMismatch(expected_found(relation, a, b)))
 217         }
 218     }
 219 }
 220
 221 impl<'tcx> Relate<'tcx> for ty::ProjectionTy<'tcx> {
 222     fn relate<'a, 'gcx, R>(relation: &mut R,
 223                            a: &ty::ProjectionTy<'tcx>,
 224                            b: &ty::ProjectionTy<'tcx>)
 225                            -> RelateResult<'tcx, ty::ProjectionTy<'tcx>>
 226         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 227     {
 228         if a.item_name != b.item_name {
 229             Err(TypeError::ProjectionNameMismatched(
 230                 expected_found(relation, &a.item_name, &b.item_name)))
 231         } else {
 232             let trait_ref = relation.relate(&a.trait_ref, &b.trait_ref)?;
 233             Ok(ty::ProjectionTy { trait_ref: trait_ref, item_name: a.item_name })
 234         }
 235     }
 236 }
 237
 238 impl<'tcx> Relate<'tcx> for ty::ExistentialProjection<'tcx> {
 239     fn relate<'a, 'gcx, R>(relation: &mut R,
 240                            a: &ty::ExistentialProjection<'tcx>,
 241                            b: &ty::ExistentialProjection<'tcx>)
 242                            -> RelateResult<'tcx, ty::ExistentialProjection<'tcx>>
 243         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 244     {
 245         if a.item_name != b.item_name {
 246             Err(TypeError::ProjectionNameMismatched(
 247                 expected_found(relation, &a.item_name, &b.item_name)))
 248         } else {
 249             let trait_ref = relation.relate(&a.trait_ref, &b.trait_ref)?;
 250             let ty = relation.relate(&a.ty, &b.ty)?;
 251             Ok(ty::ExistentialProjection {
 252                 trait_ref: trait_ref,
 253                 item_name: a.item_name,
 254                 ty: ty
 255             })
 256         }
 257     }
 258 }
 259
 260 impl<'tcx> Relate<'tcx> for Vec<ty::PolyExistentialProjection<'tcx>> {
 261     fn relate<'a, 'gcx, R>(relation: &mut R,
 262                            a: &Vec<ty::PolyExistentialProjection<'tcx>>,
 263                            b: &Vec<ty::PolyExistentialProjection<'tcx>>)
 264                            -> RelateResult<'tcx, Vec<ty::PolyExistentialProjection<'tcx>>>
 265         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 266     {
 267         // To be compatible, `a` and `b` must be for precisely the
 268         // same set of traits and item names. We always require that
 269         // projection bounds lists are sorted by trait-def-id and item-name,
 270         // so we can just iterate through the lists pairwise, so long as they are the
 271         // same length.
 272         if a.len() != b.len() {
 273             Err(TypeError::ProjectionBoundsLength(expected_found(relation, &a.len(), &b.len())))
 274         } else {
 275             a.iter().zip(b)
 276                 .map(|(a, b)| relation.relate(a, b))
 277                 .collect()
 278         }
 279     }
 280 }
 281
 282 impl<'tcx> Relate<'tcx> for ty::TraitRef<'tcx> {
 283     fn relate<'a, 'gcx, R>(relation: &mut R,
 284                            a: &ty::TraitRef<'tcx>,
 285                            b: &ty::TraitRef<'tcx>)
 286                            -> RelateResult<'tcx, ty::TraitRef<'tcx>>
 287         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 288     {
 289         // Different traits cannot be related
 290         if a.def_id != b.def_id {
 291             Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
 292         } else {
 293             let substs = relation.relate_item_substs(a.def_id, a.substs, b.substs)?;
 294             Ok(ty::TraitRef { def_id: a.def_id, substs: substs })
 295         }
 296     }
 297 }
 298
 299 impl<'tcx> Relate<'tcx> for ty::ExistentialTraitRef<'tcx> {
 300     fn relate<'a, 'gcx, R>(relation: &mut R,
 301                            a: &ty::ExistentialTraitRef<'tcx>,
 302                            b: &ty::ExistentialTraitRef<'tcx>)
 303                            -> RelateResult<'tcx, ty::ExistentialTraitRef<'tcx>>
 304         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 305     {
 306         // Different traits cannot be related
 307         if a.def_id != b.def_id {
 308             Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
 309         } else {
 310             let substs = relation.relate_item_substs(a.def_id, a.substs, b.substs)?;
 311             Ok(ty::ExistentialTraitRef { def_id: a.def_id, substs: substs })
 312         }
 313     }
 314 }
 315
 316 impl<'tcx> Relate<'tcx> for Ty<'tcx> {
 317     fn relate<'a, 'gcx, R>(relation: &mut R,
 318                            a: &Ty<'tcx>,
 319                            b: &Ty<'tcx>)
 320                            -> RelateResult<'tcx, Ty<'tcx>>
 321         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 322     {
 323         relation.tys(a, b)
 324     }
 325 }
 326
 327 /// The main "type relation" routine. Note that this does not handle
 328 /// inference artifacts, so you should filter those out before calling
 329 /// it.
 330 pub fn super_relate_tys<'a, 'gcx, 'tcx, R>(relation: &mut R,
 331                                            a: Ty<'tcx>,
 332                                            b: Ty<'tcx>)
 333                                            -> RelateResult<'tcx, Ty<'tcx>>
 334     where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 335 {
 336     let tcx = relation.tcx();
 337     let a_sty = &a.sty;
 338     let b_sty = &b.sty;
 339     debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
 340     match (a_sty, b_sty) {
 341         (&ty::TyInfer(_), _) |
 342         (_, &ty::TyInfer(_)) =>
 343         {
 344             // The caller should handle these cases!
 345             bug!("var types encountered in super_relate_tys")
 346         }
 347
 348         (&ty::TyError, _) | (_, &ty::TyError) =>
 349         {
 350             Ok(tcx.types.err)
 351         }
 352
 353         (&ty::TyNever, _) |
 354         (&ty::TyChar, _) |
 355         (&ty::TyBool, _) |
 356         (&ty::TyInt(_), _) |
 357         (&ty::TyUint(_), _) |
 358         (&ty::TyFloat(_), _) |
 359         (&ty::TyStr, _)
 360             if a == b =>
 361         {
 362             Ok(a)
 363         }
 364
 365         (&ty::TyParam(ref a_p), &ty::TyParam(ref b_p))
 366             if a_p.idx == b_p.idx =>
 367         {
 368             Ok(a)
 369         }
 370
 371         (&ty::TyAdt(a_def, a_substs), &ty::TyAdt(b_def, b_substs))
 372             if a_def == b_def =>
 373         {
 374             let substs = relation.relate_item_substs(a_def.did, a_substs, b_substs)?;
 375             Ok(tcx.mk_adt(a_def, substs))
 376         }
 377
 378         (&ty::TyDynamic(ref a_obj, ref a_region), &ty::TyDynamic(ref b_obj, ref b_region)) => {
 379             let region_bound = relation.with_cause(Cause::ExistentialRegionBound,
 380                                                        |relation| {
 381                                                            relation.relate_with_variance(
 382                                                                ty::Contravariant,
 383                                                                a_region,
 384                                                                b_region)
 385                                                        })?;
 386             Ok(tcx.mk_dynamic(relation.relate(a_obj, b_obj)?, region_bound))
 387         }
 388
 389         (&ty::TyClosure(a_id, a_substs),
 390          &ty::TyClosure(b_id, b_substs))
 391             if a_id == b_id =>
 392         {
 393             // All TyClosure types with the same id represent
 394             // the (anonymous) type of the same closure expression. So
 395             // all of their regions should be equated.
 396             let substs = relation.relate(&a_substs, &b_substs)?;
 397             Ok(tcx.mk_closure_from_closure_substs(a_id, substs))
 398         }
 399
 400         (&ty::TyRawPtr(ref a_mt), &ty::TyRawPtr(ref b_mt)) =>
 401         {
 402             let mt = relation.relate(a_mt, b_mt)?;
 403             Ok(tcx.mk_ptr(mt))
 404         }
 405
 406         (&ty::TyRef(a_r, ref a_mt), &ty::TyRef(b_r, ref b_mt)) =>
 407         {
 408             let r = relation.relate_with_variance(ty::Contravariant, &a_r, &b_r)?;
 409             let mt = relation.relate(a_mt, b_mt)?;
 410             Ok(tcx.mk_ref(r, mt))
 411         }
 412
 413         (&ty::TyArray(a_t, sz_a), &ty::TyArray(b_t, sz_b)) =>
 414         {
 415             let t = relation.relate(&a_t, &b_t)?;
 416             if sz_a == sz_b {
 417                 Ok(tcx.mk_array(t, sz_a))
 418             } else {
 419                 Err(TypeError::FixedArraySize(expected_found(relation, &sz_a, &sz_b)))
 420             }
 421         }
 422
 423         (&ty::TySlice(a_t), &ty::TySlice(b_t)) =>
 424         {
 425             let t = relation.relate(&a_t, &b_t)?;
 426             Ok(tcx.mk_slice(t))
 427         }
 428
 429         (&ty::TyTuple(as_, a_defaulted), &ty::TyTuple(bs, b_defaulted)) =>
 430         {
 431             if as_.len() == bs.len() {
 432                 let defaulted = a_defaulted || b_defaulted;
 433                 Ok(tcx.mk_tup(as_.iter().zip(bs).map(|(a, b)| relation.relate(a, b)), defaulted)?)
 434             } else if !(as_.is_empty() || bs.is_empty()) {
 435                 Err(TypeError::TupleSize(
 436                     expected_found(relation, &as_.len(), &bs.len())))
 437             } else {
 438                 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 439             }
 440         }
 441
 442         (&ty::TyFnDef(a_def_id, a_substs, a_fty),
 443          &ty::TyFnDef(b_def_id, b_substs, b_fty))
 444             if a_def_id == b_def_id =>
 445         {
 446             let substs = relate_substs(relation, None, a_substs, b_substs)?;
 447             let fty = relation.relate(&a_fty, &b_fty)?;
 448             Ok(tcx.mk_fn_def(a_def_id, substs, fty))
 449         }
 450
 451         (&ty::TyFnPtr(a_fty), &ty::TyFnPtr(b_fty)) =>
 452         {
 453             let fty = relation.relate(&a_fty, &b_fty)?;
 454             Ok(tcx.mk_fn_ptr(fty))
 455         }
 456
 457         (&ty::TyProjection(ref a_data), &ty::TyProjection(ref b_data)) =>
 458         {
 459             let projection_ty = relation.relate(a_data, b_data)?;
 460             Ok(tcx.mk_projection(projection_ty.trait_ref, projection_ty.item_name))
 461         }
 462
 463         (&ty::TyAnon(a_def_id, a_substs), &ty::TyAnon(b_def_id, b_substs))
 464             if a_def_id == b_def_id =>
 465         {
 466             let substs = relate_substs(relation, None, a_substs, b_substs)?;
 467             Ok(tcx.mk_anon(a_def_id, substs))
 468         }
 469
 470         _ =>
 471         {
 472             Err(TypeError::Sorts(expected_found(relation, &a, &b)))
 473         }
 474     }
 475 }
 476
 477 impl<'tcx> Relate<'tcx> for &'tcx ty::Slice<ty::ExistentialPredicate<'tcx>> {
 478     fn relate<'a, 'gcx, R>(relation: &mut R,
 479                            a: &Self,
 480                            b: &Self)
 481         -> RelateResult<'tcx, Self>
 482             where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a {
 483
 484         if a.len() != b.len() {
 485             return Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)));
 486         }
 487
 488         let tcx = relation.tcx();
 489         let v = a.iter().zip(b.iter()).map(|(ep_a, ep_b)| {
 490             use ty::ExistentialPredicate::*;
 491             match (*ep_a, *ep_b) {
 492                 (Trait(ref a), Trait(ref b)) => Ok(Trait(relation.relate(a, b)?)),
 493                 (Projection(ref a), Projection(ref b)) => Ok(Projection(relation.relate(a, b)?)),
 494                 (AutoTrait(ref a), AutoTrait(ref b)) if a == b => Ok(AutoTrait(*a)),
 495                 _ => Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)))
 496             }
 497         });
 498         Ok(tcx.mk_existential_predicates(v)?)
 499     }
 500 }
 501
 502 impl<'tcx> Relate<'tcx> for ty::ClosureSubsts<'tcx> {
 503     fn relate<'a, 'gcx, R>(relation: &mut R,
 504                            a: &ty::ClosureSubsts<'tcx>,
 505                            b: &ty::ClosureSubsts<'tcx>)
 506                            -> RelateResult<'tcx, ty::ClosureSubsts<'tcx>>
 507         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 508     {
 509         let substs = relate_substs(relation, None, a.substs, b.substs)?;
 510         Ok(ty::ClosureSubsts { substs: substs })
 511     }
 512 }
 513
 514 impl<'tcx> Relate<'tcx> for &'tcx Substs<'tcx> {
 515     fn relate<'a, 'gcx, R>(relation: &mut R,
 516                            a: &&'tcx Substs<'tcx>,
 517                            b: &&'tcx Substs<'tcx>)
 518                            -> RelateResult<'tcx, &'tcx Substs<'tcx>>
 519         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 520     {
 521         relate_substs(relation, None, a, b)
 522     }
 523 }
 524
 525 impl<'tcx> Relate<'tcx> for ty::Region<'tcx> {
 526     fn relate<'a, 'gcx, R>(relation: &mut R,
 527                            a: &ty::Region<'tcx>,
 528                            b: &ty::Region<'tcx>)
 529                            -> RelateResult<'tcx, ty::Region<'tcx>>
 530         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 531     {
 532         relation.regions(*a, *b)
 533     }
 534 }
 535
 536 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for ty::Binder<T> {
 537     fn relate<'a, 'gcx, R>(relation: &mut R,
 538                            a: &ty::Binder<T>,
 539                            b: &ty::Binder<T>)
 540                            -> RelateResult<'tcx, ty::Binder<T>>
 541         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 542     {
 543         relation.binders(a, b)
 544     }
 545 }
 546
 547 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Rc<T> {
 548     fn relate<'a, 'gcx, R>(relation: &mut R,
 549                            a: &Rc<T>,
 550                            b: &Rc<T>)
 551                            -> RelateResult<'tcx, Rc<T>>
 552         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 553     {
 554         let a: &T = a;
 555         let b: &T = b;
 556         Ok(Rc::new(relation.relate(a, b)?))
 557     }
 558 }
 559
 560 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Box<T> {
 561     fn relate<'a, 'gcx, R>(relation: &mut R,
 562                            a: &Box<T>,
 563                            b: &Box<T>)
 564                            -> RelateResult<'tcx, Box<T>>
 565         where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
 566     {
 567         let a: &T = a;
 568         let b: &T = b;
 569         Ok(Box::new(relation.relate(a, b)?))
 570     }
 571 }
 572
 573 ///////////////////////////////////////////////////////////////////////////
 574 // Error handling
 575
 576 pub fn expected_found<'a, 'gcx, 'tcx, R, T>(relation: &mut R,
 577                                             a: &T,
 578                                             b: &T)
 579                                             -> ExpectedFound<T>
 580     where R: TypeRelation<'a, 'gcx, 'tcx>, T: Clone, 'gcx: 'a+'tcx, 'tcx: 'a
 581 {
 582     expected_found_bool(relation.a_is_expected(), a, b)
 583 }
 584
 585 pub fn expected_found_bool<T>(a_is_expected: bool,
 586                               a: &T,
 587                               b: &T)
 588                               -> ExpectedFound<T>
 589     where T: Clone
 590 {
 591     let a = a.clone();
 592     let b = b.clone();
 593     if a_is_expected {
 594         ExpectedFound {expected: a, found: b}
 595     } else {
 596         ExpectedFound {expected: b, found: a}
 597     }
 598 }