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 hir::def_id::DefId;
17 use ty::subst::{Kind, Substs};
18 use ty::{self, Ty, TyCtxt, TypeFoldable};
19 use ty::error::{ExpectedFound, TypeError};
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, 'gcx: 'a+'tcx, 'tcx: 'a> : Sized {
32 fn tcx(&self) -> TyCtxt<'a, 'gcx, '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<'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<'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<'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: &'tcx ty::Region, b: &'tcx ty::Region)
75 -> RelateResult<'tcx, &'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<'tcx>;
82 pub trait Relate<'tcx>: TypeFoldable<'tcx> {
83 fn relate<'a, 'gcx, R>(relation: &mut R, a: &Self, b: &Self)
84 -> RelateResult<'tcx, Self>
85 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a;
88 ///////////////////////////////////////////////////////////////////////////
91 impl<'tcx> Relate<'tcx> for ty::TypeAndMut<'tcx> {
92 fn relate<'a, 'gcx, R>(relation: &mut R,
93 a: &ty::TypeAndMut<'tcx>,
94 b: &ty::TypeAndMut<'tcx>)
95 -> RelateResult<'tcx, ty::TypeAndMut<'tcx>>
96 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
98 debug!("{}.mts({:?}, {:?})",
102 if a.mutbl != b.mutbl {
103 Err(TypeError::Mutability)
106 let variance = match mutbl {
107 ast::Mutability::MutImmutable => ty::Covariant,
108 ast::Mutability::MutMutable => ty::Invariant,
110 let ty = relation.relate_with_variance(variance, &a.ty, &b.ty)?;
111 Ok(ty::TypeAndMut {ty: ty, mutbl: mutbl})
116 // substitutions are not themselves relatable without more context,
117 // but they is an important subroutine for things that ARE relatable,
119 fn relate_item_substs<'a, 'gcx, 'tcx, R>(relation: &mut R,
121 a_subst: &'tcx Substs<'tcx>,
122 b_subst: &'tcx Substs<'tcx>)
123 -> RelateResult<'tcx, &'tcx Substs<'tcx>>
124 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
126 debug!("substs: item_def_id={:?} a_subst={:?} b_subst={:?}",
132 let opt_variances = if relation.tcx().variance_computed.get() {
133 variances = relation.tcx().item_variances(item_def_id);
138 relate_substs(relation, opt_variances, a_subst, b_subst)
141 pub fn relate_substs<'a, 'gcx, 'tcx, R>(relation: &mut R,
142 variances: Option<&Vec<ty::Variance>>,
143 a_subst: &'tcx Substs<'tcx>,
144 b_subst: &'tcx Substs<'tcx>)
145 -> RelateResult<'tcx, &'tcx Substs<'tcx>>
146 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
148 let tcx = relation.tcx();
150 let params = a_subst.params().iter().zip(b_subst.params()).enumerate().map(|(i, (a, b))| {
151 let variance = variances.map_or(ty::Invariant, |v| v[i]);
152 if let (Some(a_ty), Some(b_ty)) = (a.as_type(), b.as_type()) {
153 Ok(Kind::from(relation.relate_with_variance(variance, &a_ty, &b_ty)?))
154 } else if let (Some(a_r), Some(b_r)) = (a.as_region(), b.as_region()) {
155 Ok(Kind::from(relation.relate_with_variance(variance, &a_r, &b_r)?))
161 Substs::maybe_new(tcx, params)
164 impl<'tcx> Relate<'tcx> for &'tcx ty::BareFnTy<'tcx> {
165 fn relate<'a, 'gcx, R>(relation: &mut R,
166 a: &&'tcx ty::BareFnTy<'tcx>,
167 b: &&'tcx ty::BareFnTy<'tcx>)
168 -> RelateResult<'tcx, &'tcx ty::BareFnTy<'tcx>>
169 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
171 let unsafety = relation.relate(&a.unsafety, &b.unsafety)?;
172 let abi = relation.relate(&a.abi, &b.abi)?;
173 let sig = relation.relate(&a.sig, &b.sig)?;
174 Ok(relation.tcx().mk_bare_fn(ty::BareFnTy {
182 impl<'tcx> Relate<'tcx> for ty::FnSig<'tcx> {
183 fn relate<'a, 'gcx, R>(relation: &mut R,
186 -> RelateResult<'tcx, ty::FnSig<'tcx>>
187 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
189 if a.variadic != b.variadic {
190 return Err(TypeError::VariadicMismatch(
191 expected_found(relation, &a.variadic, &b.variadic)));
194 let inputs = relate_arg_vecs(relation,
197 let output = relation.relate(&a.output, &b.output)?;
199 Ok(ty::FnSig {inputs: inputs,
201 variadic: a.variadic})
205 fn relate_arg_vecs<'a, 'gcx, 'tcx, R>(relation: &mut R,
208 -> RelateResult<'tcx, Vec<Ty<'tcx>>>
209 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
211 if a_args.len() != b_args.len() {
212 return Err(TypeError::ArgCount);
215 a_args.iter().zip(b_args)
216 .map(|(a, b)| relation.relate_with_variance(ty::Contravariant, a, b))
220 impl<'tcx> Relate<'tcx> for ast::Unsafety {
221 fn relate<'a, 'gcx, R>(relation: &mut R,
224 -> RelateResult<'tcx, ast::Unsafety>
225 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
228 Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
235 impl<'tcx> Relate<'tcx> for abi::Abi {
236 fn relate<'a, 'gcx, R>(relation: &mut R,
239 -> RelateResult<'tcx, abi::Abi>
240 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
245 Err(TypeError::AbiMismatch(expected_found(relation, a, b)))
250 impl<'tcx> Relate<'tcx> for ty::ProjectionTy<'tcx> {
251 fn relate<'a, 'gcx, R>(relation: &mut R,
252 a: &ty::ProjectionTy<'tcx>,
253 b: &ty::ProjectionTy<'tcx>)
254 -> RelateResult<'tcx, ty::ProjectionTy<'tcx>>
255 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
257 if a.item_name != b.item_name {
258 Err(TypeError::ProjectionNameMismatched(
259 expected_found(relation, &a.item_name, &b.item_name)))
261 let trait_ref = relation.relate(&a.trait_ref, &b.trait_ref)?;
262 Ok(ty::ProjectionTy { trait_ref: trait_ref, item_name: a.item_name })
267 impl<'tcx> Relate<'tcx> for ty::ExistentialProjection<'tcx> {
268 fn relate<'a, 'gcx, R>(relation: &mut R,
269 a: &ty::ExistentialProjection<'tcx>,
270 b: &ty::ExistentialProjection<'tcx>)
271 -> RelateResult<'tcx, ty::ExistentialProjection<'tcx>>
272 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
274 if a.item_name != b.item_name {
275 Err(TypeError::ProjectionNameMismatched(
276 expected_found(relation, &a.item_name, &b.item_name)))
278 let trait_ref = relation.relate(&a.trait_ref, &b.trait_ref)?;
279 let ty = relation.relate(&a.ty, &b.ty)?;
280 Ok(ty::ExistentialProjection {
281 trait_ref: trait_ref,
282 item_name: a.item_name,
289 impl<'tcx> Relate<'tcx> for Vec<ty::PolyExistentialProjection<'tcx>> {
290 fn relate<'a, 'gcx, R>(relation: &mut R,
291 a: &Vec<ty::PolyExistentialProjection<'tcx>>,
292 b: &Vec<ty::PolyExistentialProjection<'tcx>>)
293 -> RelateResult<'tcx, Vec<ty::PolyExistentialProjection<'tcx>>>
294 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
296 // To be compatible, `a` and `b` must be for precisely the
297 // same set of traits and item names. We always require that
298 // projection bounds lists are sorted by trait-def-id and item-name,
299 // so we can just iterate through the lists pairwise, so long as they are the
301 if a.len() != b.len() {
302 Err(TypeError::ProjectionBoundsLength(expected_found(relation, &a.len(), &b.len())))
305 .map(|(a, b)| relation.relate(a, b))
311 impl<'tcx> Relate<'tcx> for ty::BuiltinBounds {
312 fn relate<'a, 'gcx, R>(relation: &mut R,
313 a: &ty::BuiltinBounds,
314 b: &ty::BuiltinBounds)
315 -> RelateResult<'tcx, ty::BuiltinBounds>
316 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
318 // Two sets of builtin bounds are only relatable if they are
319 // precisely the same (but see the coercion code).
321 Err(TypeError::BuiltinBoundsMismatch(expected_found(relation, a, b)))
328 impl<'tcx> Relate<'tcx> for ty::TraitRef<'tcx> {
329 fn relate<'a, 'gcx, R>(relation: &mut R,
330 a: &ty::TraitRef<'tcx>,
331 b: &ty::TraitRef<'tcx>)
332 -> RelateResult<'tcx, ty::TraitRef<'tcx>>
333 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
335 // Different traits cannot be related
336 if a.def_id != b.def_id {
337 Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
339 let substs = relate_item_substs(relation, a.def_id, a.substs, b.substs)?;
340 Ok(ty::TraitRef { def_id: a.def_id, substs: substs })
345 impl<'tcx> Relate<'tcx> for ty::ExistentialTraitRef<'tcx> {
346 fn relate<'a, 'gcx, R>(relation: &mut R,
347 a: &ty::ExistentialTraitRef<'tcx>,
348 b: &ty::ExistentialTraitRef<'tcx>)
349 -> RelateResult<'tcx, ty::ExistentialTraitRef<'tcx>>
350 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
352 // Different traits cannot be related
353 if a.def_id != b.def_id {
354 Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id)))
356 let substs = relate_item_substs(relation, a.def_id, a.substs, b.substs)?;
357 Ok(ty::ExistentialTraitRef { def_id: a.def_id, substs: substs })
362 impl<'tcx> Relate<'tcx> for Ty<'tcx> {
363 fn relate<'a, 'gcx, R>(relation: &mut R,
366 -> RelateResult<'tcx, Ty<'tcx>>
367 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
373 /// The main "type relation" routine. Note that this does not handle
374 /// inference artifacts, so you should filter those out before calling
376 pub fn super_relate_tys<'a, 'gcx, 'tcx, R>(relation: &mut R,
379 -> RelateResult<'tcx, Ty<'tcx>>
380 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
382 let tcx = relation.tcx();
385 debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
386 match (a_sty, b_sty) {
387 (&ty::TyInfer(_), _) |
388 (_, &ty::TyInfer(_)) =>
390 // The caller should handle these cases!
391 bug!("var types encountered in super_relate_tys")
394 (&ty::TyError, _) | (_, &ty::TyError) =>
403 (&ty::TyUint(_), _) |
404 (&ty::TyFloat(_), _) |
411 (&ty::TyParam(ref a_p), &ty::TyParam(ref b_p))
412 if a_p.idx == b_p.idx =>
417 (&ty::TyEnum(a_def, a_substs), &ty::TyEnum(b_def, b_substs))
420 let substs = relate_item_substs(relation, a_def.did, a_substs, b_substs)?;
421 Ok(tcx.mk_enum(a_def, substs))
424 (&ty::TyTrait(ref a_obj), &ty::TyTrait(ref b_obj)) =>
426 let principal = relation.relate(&a_obj.principal, &b_obj.principal)?;
429 Cause::ExistentialRegionBound,
430 |relation| relation.relate_with_variance(ty::Contravariant,
432 &b_obj.region_bound))?;
433 let nb = relation.relate(&a_obj.builtin_bounds, &b_obj.builtin_bounds)?;
434 let pb = relation.relate(&a_obj.projection_bounds, &b_obj.projection_bounds)?;
435 Ok(tcx.mk_trait(ty::TraitObject {
436 principal: principal,
439 projection_bounds: pb
443 (&ty::TyStruct(a_def, a_substs), &ty::TyStruct(b_def, b_substs))
446 let substs = relate_item_substs(relation, a_def.did, a_substs, b_substs)?;
447 Ok(tcx.mk_struct(a_def, substs))
450 (&ty::TyClosure(a_id, a_substs),
451 &ty::TyClosure(b_id, b_substs))
454 // All TyClosure types with the same id represent
455 // the (anonymous) type of the same closure expression. So
456 // all of their regions should be equated.
457 let substs = relation.relate(&a_substs, &b_substs)?;
458 Ok(tcx.mk_closure_from_closure_substs(a_id, substs))
461 (&ty::TyBox(a_inner), &ty::TyBox(b_inner)) =>
463 let typ = relation.relate(&a_inner, &b_inner)?;
467 (&ty::TyRawPtr(ref a_mt), &ty::TyRawPtr(ref b_mt)) =>
469 let mt = relation.relate(a_mt, b_mt)?;
473 (&ty::TyRef(a_r, ref a_mt), &ty::TyRef(b_r, ref b_mt)) =>
475 let r = relation.relate_with_variance(ty::Contravariant, &a_r, &b_r)?;
476 let mt = relation.relate(a_mt, b_mt)?;
477 Ok(tcx.mk_ref(r, mt))
480 (&ty::TyArray(a_t, sz_a), &ty::TyArray(b_t, sz_b)) =>
482 let t = relation.relate(&a_t, &b_t)?;
484 Ok(tcx.mk_array(t, sz_a))
486 Err(TypeError::FixedArraySize(expected_found(relation, &sz_a, &sz_b)))
490 (&ty::TySlice(a_t), &ty::TySlice(b_t)) =>
492 let t = relation.relate(&a_t, &b_t)?;
496 (&ty::TyTuple(as_), &ty::TyTuple(bs)) =>
498 if as_.len() == bs.len() {
499 let ts = as_.iter().zip(bs)
500 .map(|(a, b)| relation.relate(a, b))
501 .collect::<Result<_, _>>()?;
503 } else if !(as_.is_empty() || bs.is_empty()) {
504 Err(TypeError::TupleSize(
505 expected_found(relation, &as_.len(), &bs.len())))
507 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
511 (&ty::TyFnDef(a_def_id, a_substs, a_fty),
512 &ty::TyFnDef(b_def_id, b_substs, b_fty))
513 if a_def_id == b_def_id =>
515 let substs = relate_substs(relation, None, a_substs, b_substs)?;
516 let fty = relation.relate(&a_fty, &b_fty)?;
517 Ok(tcx.mk_fn_def(a_def_id, substs, fty))
520 (&ty::TyFnPtr(a_fty), &ty::TyFnPtr(b_fty)) =>
522 let fty = relation.relate(&a_fty, &b_fty)?;
523 Ok(tcx.mk_fn_ptr(fty))
526 (&ty::TyProjection(ref a_data), &ty::TyProjection(ref b_data)) =>
528 let projection_ty = relation.relate(a_data, b_data)?;
529 Ok(tcx.mk_projection(projection_ty.trait_ref, projection_ty.item_name))
532 (&ty::TyAnon(a_def_id, a_substs), &ty::TyAnon(b_def_id, b_substs))
533 if a_def_id == b_def_id =>
535 let substs = relate_substs(relation, None, a_substs, b_substs)?;
536 Ok(tcx.mk_anon(a_def_id, substs))
541 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
546 impl<'tcx> Relate<'tcx> for ty::ClosureSubsts<'tcx> {
547 fn relate<'a, 'gcx, R>(relation: &mut R,
548 a: &ty::ClosureSubsts<'tcx>,
549 b: &ty::ClosureSubsts<'tcx>)
550 -> RelateResult<'tcx, ty::ClosureSubsts<'tcx>>
551 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
553 let substs = relate_substs(relation, None, a.func_substs, b.func_substs)?;
554 let upvar_tys = relation.relate_zip(&a.upvar_tys, &b.upvar_tys)?;
555 Ok(ty::ClosureSubsts {
557 upvar_tys: relation.tcx().mk_type_list(upvar_tys)
562 impl<'tcx> Relate<'tcx> for &'tcx Substs<'tcx> {
563 fn relate<'a, 'gcx, R>(relation: &mut R,
564 a: &&'tcx Substs<'tcx>,
565 b: &&'tcx Substs<'tcx>)
566 -> RelateResult<'tcx, &'tcx Substs<'tcx>>
567 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
569 relate_substs(relation, None, a, b)
573 impl<'tcx> Relate<'tcx> for &'tcx ty::Region {
574 fn relate<'a, 'gcx, R>(relation: &mut R,
575 a: &&'tcx ty::Region,
576 b: &&'tcx ty::Region)
577 -> RelateResult<'tcx, &'tcx ty::Region>
578 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
580 relation.regions(*a, *b)
584 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for ty::Binder<T> {
585 fn relate<'a, 'gcx, R>(relation: &mut R,
588 -> RelateResult<'tcx, ty::Binder<T>>
589 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
591 relation.binders(a, b)
595 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Rc<T> {
596 fn relate<'a, 'gcx, R>(relation: &mut R,
599 -> RelateResult<'tcx, Rc<T>>
600 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
604 Ok(Rc::new(relation.relate(a, b)?))
608 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Box<T> {
609 fn relate<'a, 'gcx, R>(relation: &mut R,
612 -> RelateResult<'tcx, Box<T>>
613 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
617 Ok(Box::new(relation.relate(a, b)?))
621 ///////////////////////////////////////////////////////////////////////////
624 pub fn expected_found<'a, 'gcx, 'tcx, R, T>(relation: &mut R,
628 where R: TypeRelation<'a, 'gcx, 'tcx>, T: Clone, 'gcx: 'a+'tcx, 'tcx: 'a
630 expected_found_bool(relation.a_is_expected(), a, b)
633 pub fn expected_found_bool<T>(a_is_expected: bool,
642 ExpectedFound {expected: a, found: b}
644 ExpectedFound {expected: b, found: a}