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