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.
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.
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.
16 use middle::def_id::DefId;
17 use middle::subst::{ErasedRegions, NonerasedRegions, ParamSpace, Substs};
18 use middle::ty::{self, Ty, TyCtxt, TypeFoldable};
19 use middle::ty::error::{ExpectedFound, TypeError};
22 use rustc_front::hir as ast;
24 pub type RelateResult<'tcx, T> = Result<T, TypeError<'tcx>>;
26 #[derive(Clone, Debug)]
28 ExistentialRegionBound, // relating an existential region bound
31 pub trait TypeRelation<'a,'tcx> : Sized {
32 fn tcx(&self) -> &'a TyCtxt<'tcx>;
34 /// Returns a static string we can use for printouts.
35 fn tag(&self) -> &'static str;
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;
41 fn with_cause<F,R>(&mut self, _cause: Cause, f: F) -> R
42 where F: FnOnce(&mut Self) -> R
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)
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()
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,
63 -> RelateResult<'tcx, T>;
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.
71 fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>)
72 -> RelateResult<'tcx, Ty<'tcx>>;
74 fn regions(&mut self, a: ty::Region, b: ty::Region)
75 -> RelateResult<'tcx, ty::Region>;
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>;
82 pub trait Relate<'a,'tcx>: TypeFoldable<'tcx> {
83 fn relate<R:TypeRelation<'a,'tcx>>(relation: &mut R,
86 -> RelateResult<'tcx, Self>;
89 ///////////////////////////////////////////////////////////////////////////
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>
99 debug!("{}.mts({:?}, {:?})",
103 if a.mutbl != b.mutbl {
104 Err(TypeError::Mutability)
107 let variance = match mutbl {
108 ast::Mutability::MutImmutable => ty::Covariant,
109 ast::Mutability::MutMutable => ty::Invariant,
111 let ty = relation.relate_with_variance(variance, &a.ty, &b.ty)?;
112 Ok(ty::TypeAndMut {ty: ty, mutbl: mutbl})
117 // substitutions are not themselves relatable without more context,
118 // but they is an important subroutine for things that ARE relatable,
120 fn relate_item_substs<'a,'tcx:'a,R>(relation: &mut R,
122 a_subst: &Substs<'tcx>,
123 b_subst: &Substs<'tcx>)
124 -> RelateResult<'tcx, Substs<'tcx>>
125 where R: TypeRelation<'a,'tcx>
127 debug!("substs: item_def_id={:?} a_subst={:?} b_subst={:?}",
133 let opt_variances = if relation.tcx().variance_computed.get() {
134 variances = relation.tcx().item_variances(item_def_id);
139 relate_substs(relation, opt_variances, a_subst, b_subst)
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>
149 let mut substs = Substs::empty();
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);
159 match (&a_subst.regions, &b_subst.regions) {
160 (&ErasedRegions, _) | (_, &ErasedRegions) => {
161 substs.regions = ErasedRegions;
164 (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => {
165 for &space in &ParamSpace::all() {
166 let a_regions = a.get_slice(space);
167 let b_regions = b.get_slice(space);
168 let r_variances = variances.map(|v| v.regions.get_slice(space));
169 let regions = relate_region_params(relation,
173 substs.mut_regions().replace(space, regions);
181 fn relate_type_params<'a,'tcx:'a,R>(relation: &mut R,
182 variances: Option<&[ty::Variance]>,
185 -> RelateResult<'tcx, Vec<Ty<'tcx>>>
186 where R: TypeRelation<'a,'tcx>
188 if a_tys.len() != b_tys.len() {
189 return Err(TypeError::TyParamSize(expected_found(relation,
198 let v = variances.map_or(ty::Invariant, |v| v[i]);
199 relation.relate_with_variance(v, &a_ty, &b_ty)
204 fn relate_region_params<'a,'tcx:'a,R>(relation: &mut R,
205 variances: Option<&[ty::Variance]>,
208 -> RelateResult<'tcx, Vec<ty::Region>>
209 where R: TypeRelation<'a,'tcx>
211 let num_region_params = a_rs.len();
213 debug!("relate_region_params(a_rs={:?}, \
214 b_rs={:?}, variances={:?})",
219 assert_eq!(num_region_params,
220 variances.map_or(num_region_params,
223 assert_eq!(num_region_params, b_rs.len());
229 let variance = variances.map_or(ty::Invariant, |v| v[i]);
230 relation.relate_with_variance(variance, &a_r, &b_r)
235 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BareFnTy<'tcx> {
236 fn relate<R>(relation: &mut R,
237 a: &ty::BareFnTy<'tcx>,
238 b: &ty::BareFnTy<'tcx>)
239 -> RelateResult<'tcx, ty::BareFnTy<'tcx>>
240 where R: TypeRelation<'a,'tcx>
242 let unsafety = relation.relate(&a.unsafety, &b.unsafety)?;
243 let abi = relation.relate(&a.abi, &b.abi)?;
244 let sig = relation.relate(&a.sig, &b.sig)?;
245 Ok(ty::BareFnTy {unsafety: unsafety,
251 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::FnSig<'tcx> {
252 fn relate<R>(relation: &mut R,
255 -> RelateResult<'tcx, ty::FnSig<'tcx>>
256 where R: TypeRelation<'a,'tcx>
258 if a.variadic != b.variadic {
259 return Err(TypeError::VariadicMismatch(
260 expected_found(relation, &a.variadic, &b.variadic)));
263 let inputs = relate_arg_vecs(relation,
267 let output = match (a.output, b.output) {
268 (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) =>
269 Ok(ty::FnConverging(relation.relate(&a_ty, &b_ty)?)),
270 (ty::FnDiverging, ty::FnDiverging) =>
273 Err(TypeError::ConvergenceMismatch(
274 expected_found(relation, &(a != ty::FnDiverging), &(b != ty::FnDiverging)))),
277 return Ok(ty::FnSig {inputs: inputs,
279 variadic: a.variadic});
283 fn relate_arg_vecs<'a,'tcx:'a,R>(relation: &mut R,
286 -> RelateResult<'tcx, Vec<Ty<'tcx>>>
287 where R: TypeRelation<'a,'tcx>
289 if a_args.len() != b_args.len() {
290 return Err(TypeError::ArgCount);
293 a_args.iter().zip(b_args)
294 .map(|(a, b)| relation.relate_with_variance(ty::Contravariant, a, b))
298 impl<'a,'tcx:'a> Relate<'a,'tcx> for ast::Unsafety {
299 fn relate<R>(relation: &mut R,
302 -> RelateResult<'tcx, ast::Unsafety>
303 where R: TypeRelation<'a,'tcx>
306 Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
313 impl<'a,'tcx:'a> Relate<'a,'tcx> for abi::Abi {
314 fn relate<R>(relation: &mut R,
317 -> RelateResult<'tcx, abi::Abi>
318 where R: TypeRelation<'a,'tcx>
323 Err(TypeError::AbiMismatch(expected_found(relation, a, b)))
328 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionTy<'tcx> {
329 fn relate<R>(relation: &mut R,
330 a: &ty::ProjectionTy<'tcx>,
331 b: &ty::ProjectionTy<'tcx>)
332 -> RelateResult<'tcx, ty::ProjectionTy<'tcx>>
333 where R: TypeRelation<'a,'tcx>
335 if a.item_name != b.item_name {
336 Err(TypeError::ProjectionNameMismatched(
337 expected_found(relation, &a.item_name, &b.item_name)))
339 let trait_ref = relation.relate(&a.trait_ref, &b.trait_ref)?;
340 Ok(ty::ProjectionTy { trait_ref: trait_ref, item_name: a.item_name })
345 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionPredicate<'tcx> {
346 fn relate<R>(relation: &mut R,
347 a: &ty::ProjectionPredicate<'tcx>,
348 b: &ty::ProjectionPredicate<'tcx>)
349 -> RelateResult<'tcx, ty::ProjectionPredicate<'tcx>>
350 where R: TypeRelation<'a,'tcx>
352 let projection_ty = relation.relate(&a.projection_ty, &b.projection_ty)?;
353 let ty = relation.relate(&a.ty, &b.ty)?;
354 Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty })
358 impl<'a,'tcx:'a> Relate<'a,'tcx> for Vec<ty::PolyProjectionPredicate<'tcx>> {
359 fn relate<R>(relation: &mut R,
360 a: &Vec<ty::PolyProjectionPredicate<'tcx>>,
361 b: &Vec<ty::PolyProjectionPredicate<'tcx>>)
362 -> RelateResult<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>>
363 where R: TypeRelation<'a,'tcx>
365 // To be compatible, `a` and `b` must be for precisely the
366 // same set of traits and item names. We always require that
367 // projection bounds lists are sorted by trait-def-id and item-name,
368 // so we can just iterate through the lists pairwise, so long as they are the
370 if a.len() != b.len() {
371 Err(TypeError::ProjectionBoundsLength(expected_found(relation, &a.len(), &b.len())))
374 .map(|(a, b)| relation.relate(a, b))
380 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ExistentialBounds<'tcx> {
381 fn relate<R>(relation: &mut R,
382 a: &ty::ExistentialBounds<'tcx>,
383 b: &ty::ExistentialBounds<'tcx>)
384 -> RelateResult<'tcx, ty::ExistentialBounds<'tcx>>
385 where R: TypeRelation<'a,'tcx>
389 Cause::ExistentialRegionBound,
390 |relation| relation.relate_with_variance(ty::Contravariant,
393 let nb = relation.relate(&a.builtin_bounds, &b.builtin_bounds)?;
394 let pb = relation.relate(&a.projection_bounds, &b.projection_bounds)?;
395 Ok(ty::ExistentialBounds { region_bound: r,
397 projection_bounds: pb })
401 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::BuiltinBounds {
402 fn relate<R>(relation: &mut R,
403 a: &ty::BuiltinBounds,
404 b: &ty::BuiltinBounds)
405 -> RelateResult<'tcx, ty::BuiltinBounds>
406 where R: TypeRelation<'a,'tcx>
408 // Two sets of builtin bounds are only relatable if they are
409 // precisely the same (but see the coercion code).
411 Err(TypeError::BuiltinBoundsMismatch(expected_found(relation, a, b)))
418 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::TraitRef<'tcx> {
419 fn relate<R>(relation: &mut R,
420 a: &ty::TraitRef<'tcx>,
421 b: &ty::TraitRef<'tcx>)
422 -> RelateResult<'tcx, ty::TraitRef<'tcx>>
423 where R: TypeRelation<'a,'tcx>
425 // Different traits cannot be related
426 if a.def_id != b.def_id {
427 Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
429 let substs = relate_item_substs(relation, a.def_id, a.substs, b.substs)?;
430 Ok(ty::TraitRef { def_id: a.def_id, substs: relation.tcx().mk_substs(substs) })
435 impl<'a,'tcx:'a> Relate<'a,'tcx> for Ty<'tcx> {
436 fn relate<R>(relation: &mut R,
439 -> RelateResult<'tcx, Ty<'tcx>>
440 where R: TypeRelation<'a,'tcx>
446 /// The main "type relation" routine. Note that this does not handle
447 /// inference artifacts, so you should filter those out before calling
449 pub fn super_relate_tys<'a,'tcx:'a,R>(relation: &mut R,
452 -> RelateResult<'tcx, Ty<'tcx>>
453 where R: TypeRelation<'a,'tcx>
455 let tcx = relation.tcx();
458 debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
459 match (a_sty, b_sty) {
460 (&ty::TyInfer(_), _) |
461 (_, &ty::TyInfer(_)) =>
463 // The caller should handle these cases!
464 tcx.sess.bug("var types encountered in super_relate_tys")
467 (&ty::TyError, _) | (_, &ty::TyError) =>
475 (&ty::TyUint(_), _) |
476 (&ty::TyFloat(_), _) |
483 (&ty::TyParam(ref a_p), &ty::TyParam(ref b_p))
484 if a_p.idx == b_p.idx && a_p.space == b_p.space =>
489 (&ty::TyEnum(a_def, a_substs), &ty::TyEnum(b_def, b_substs))
492 let substs = relate_item_substs(relation, a_def.did, a_substs, b_substs)?;
493 Ok(tcx.mk_enum(a_def, tcx.mk_substs(substs)))
496 (&ty::TyTrait(ref a_), &ty::TyTrait(ref b_)) =>
498 let principal = relation.relate(&a_.principal, &b_.principal)?;
499 let bounds = relation.relate(&a_.bounds, &b_.bounds)?;
500 Ok(tcx.mk_trait(principal, bounds))
503 (&ty::TyStruct(a_def, a_substs), &ty::TyStruct(b_def, b_substs))
506 let substs = relate_item_substs(relation, a_def.did, a_substs, b_substs)?;
507 Ok(tcx.mk_struct(a_def, tcx.mk_substs(substs)))
510 (&ty::TyClosure(a_id, ref a_substs),
511 &ty::TyClosure(b_id, ref b_substs))
514 // All TyClosure types with the same id represent
515 // the (anonymous) type of the same closure expression. So
516 // all of their regions should be equated.
517 let substs = relation.relate(a_substs, b_substs)?;
518 Ok(tcx.mk_closure_from_closure_substs(a_id, substs))
521 (&ty::TyBox(a_inner), &ty::TyBox(b_inner)) =>
523 let typ = relation.relate(&a_inner, &b_inner)?;
527 (&ty::TyRawPtr(ref a_mt), &ty::TyRawPtr(ref b_mt)) =>
529 let mt = relation.relate(a_mt, b_mt)?;
533 (&ty::TyRef(a_r, ref a_mt), &ty::TyRef(b_r, ref b_mt)) =>
535 let r = relation.relate_with_variance(ty::Contravariant, a_r, b_r)?;
536 let mt = relation.relate(a_mt, b_mt)?;
537 Ok(tcx.mk_ref(tcx.mk_region(r), mt))
540 (&ty::TyArray(a_t, sz_a), &ty::TyArray(b_t, sz_b)) =>
542 let t = relation.relate(&a_t, &b_t)?;
544 Ok(tcx.mk_array(t, sz_a))
546 Err(TypeError::FixedArraySize(expected_found(relation, &sz_a, &sz_b)))
550 (&ty::TySlice(a_t), &ty::TySlice(b_t)) =>
552 let t = relation.relate(&a_t, &b_t)?;
556 (&ty::TyTuple(ref as_), &ty::TyTuple(ref bs)) =>
558 if as_.len() == bs.len() {
559 let ts = as_.iter().zip(bs)
560 .map(|(a, b)| relation.relate(a, b))
561 .collect::<Result<_, _>>()?;
563 } else if !(as_.is_empty() || bs.is_empty()) {
564 Err(TypeError::TupleSize(
565 expected_found(relation, &as_.len(), &bs.len())))
567 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
571 (&ty::TyFnDef(a_def_id, a_substs, a_fty),
572 &ty::TyFnDef(b_def_id, b_substs, b_fty))
573 if a_def_id == b_def_id =>
575 let substs = relate_substs(relation, None, a_substs, b_substs)?;
576 let fty = relation.relate(a_fty, b_fty)?;
577 Ok(tcx.mk_fn_def(a_def_id, tcx.mk_substs(substs), fty))
580 (&ty::TyFnPtr(a_fty), &ty::TyFnPtr(b_fty)) =>
582 let fty = relation.relate(a_fty, b_fty)?;
583 Ok(tcx.mk_fn_ptr(fty))
586 (&ty::TyProjection(ref a_data), &ty::TyProjection(ref b_data)) =>
588 let projection_ty = relation.relate(a_data, b_data)?;
589 Ok(tcx.mk_projection(projection_ty.trait_ref, projection_ty.item_name))
594 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
599 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ClosureSubsts<'tcx> {
600 fn relate<R>(relation: &mut R,
601 a: &ty::ClosureSubsts<'tcx>,
602 b: &ty::ClosureSubsts<'tcx>)
603 -> RelateResult<'tcx, ty::ClosureSubsts<'tcx>>
604 where R: TypeRelation<'a,'tcx>
606 let func_substs = relate_substs(relation, None, a.func_substs, b.func_substs)?;
607 let upvar_tys = relation.relate_zip(&a.upvar_tys, &b.upvar_tys)?;
608 Ok(ty::ClosureSubsts { func_substs: relation.tcx().mk_substs(func_substs),
609 upvar_tys: upvar_tys })
613 impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::Region {
614 fn relate<R>(relation: &mut R,
617 -> RelateResult<'tcx, ty::Region>
618 where R: TypeRelation<'a,'tcx>
620 relation.regions(*a, *b)
624 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for ty::Binder<T>
625 where T: Relate<'a,'tcx>
627 fn relate<R>(relation: &mut R,
630 -> RelateResult<'tcx, ty::Binder<T>>
631 where R: TypeRelation<'a,'tcx>
633 relation.binders(a, b)
637 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Rc<T>
638 where T: Relate<'a,'tcx>
640 fn relate<R>(relation: &mut R,
643 -> RelateResult<'tcx, Rc<T>>
644 where R: TypeRelation<'a,'tcx>
648 Ok(Rc::new(relation.relate(a, b)?))
652 impl<'a,'tcx:'a,T> Relate<'a,'tcx> for Box<T>
653 where T: Relate<'a,'tcx>
655 fn relate<R>(relation: &mut R,
658 -> RelateResult<'tcx, Box<T>>
659 where R: TypeRelation<'a,'tcx>
663 Ok(Box::new(relation.relate(a, b)?))
667 ///////////////////////////////////////////////////////////////////////////
670 pub fn expected_found<'a,'tcx:'a,R,T>(relation: &mut R,
674 where R: TypeRelation<'a,'tcx>, T: Clone
676 expected_found_bool(relation.a_is_expected(), a, b)
679 pub fn expected_found_bool<T>(a_is_expected: bool,
688 ExpectedFound {expected: a, found: b}
690 ExpectedFound {expected: b, found: a}