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