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 use rustc_data_structures::accumulate_vec::AccumulateVec;
26 pub type RelateResult<'tcx, T> = Result<T, TypeError<'tcx>>;
28 #[derive(Clone, Debug)]
30 ExistentialRegionBound, // relating an existential region bound
33 pub trait TypeRelation<'a, 'gcx: 'a+'tcx, 'tcx: 'a> : Sized {
34 fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx>;
36 /// Returns a static string we can use for printouts.
37 fn tag(&self) -> &'static str;
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;
43 fn with_cause<F,R>(&mut self, _cause: Cause, f: F) -> R
44 where F: FnOnce(&mut Self) -> R
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)
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,
59 -> RelateResult<'tcx, T>;
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.
67 fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>)
68 -> RelateResult<'tcx, Ty<'tcx>>;
70 fn regions(&mut self, a: &'tcx ty::Region, b: &'tcx ty::Region)
71 -> RelateResult<'tcx, &'tcx ty::Region>;
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>;
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;
84 ///////////////////////////////////////////////////////////////////////////
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
94 debug!("{}.mts({:?}, {:?})",
98 if a.mutbl != b.mutbl {
99 Err(TypeError::Mutability)
102 let variance = match mutbl {
103 ast::Mutability::MutImmutable => ty::Covariant,
104 ast::Mutability::MutMutable => ty::Invariant,
106 let ty = relation.relate_with_variance(variance, &a.ty, &b.ty)?;
107 Ok(ty::TypeAndMut {ty: ty, mutbl: mutbl})
112 // substitutions are not themselves relatable without more context,
113 // but they is an important subroutine for things that ARE relatable,
115 fn relate_item_substs<'a, 'gcx, 'tcx, R>(relation: &mut R,
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
122 debug!("substs: item_def_id={:?} a_subst={:?} b_subst={:?}",
128 let opt_variances = if relation.tcx().variance_computed.get() {
129 variances = relation.tcx().item_variances(item_def_id);
134 relate_substs(relation, opt_variances, a_subst, b_subst)
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
144 let tcx = relation.tcx();
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)?))
157 Ok(tcx.mk_substs(params)?)
160 impl<'tcx> Relate<'tcx> for ty::FnSig<'tcx> {
161 fn relate<'a, 'gcx, R>(relation: &mut R,
164 -> RelateResult<'tcx, ty::FnSig<'tcx>>
165 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
167 if a.variadic != b.variadic {
168 return Err(TypeError::VariadicMismatch(
169 expected_found(relation, &a.variadic, &b.variadic)));
171 let unsafety = relation.relate(&a.unsafety, &b.unsafety)?;
172 let abi = relation.relate(&a.abi, &b.abi)?;
174 if a.inputs().len() != b.inputs().len() {
175 return Err(TypeError::ArgCount);
178 let inputs_and_output = a.inputs().iter().cloned()
179 .zip(b.inputs().iter().cloned())
181 .chain(iter::once(((a.output(), b.output()), true)))
182 .map(|((a, b), is_output)| {
184 relation.relate(&a, &b)
186 relation.relate_with_variance(ty::Contravariant, &a, &b)
188 }).collect::<Result<AccumulateVec<[_; 8]>, _>>()?;
190 inputs_and_output: relation.tcx().intern_type_list(&inputs_and_output),
191 variadic: a.variadic,
198 impl<'tcx> Relate<'tcx> for ast::Unsafety {
199 fn relate<'a, 'gcx, R>(relation: &mut R,
202 -> RelateResult<'tcx, ast::Unsafety>
203 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
206 Err(TypeError::UnsafetyMismatch(expected_found(relation, a, b)))
213 impl<'tcx> Relate<'tcx> for abi::Abi {
214 fn relate<'a, 'gcx, R>(relation: &mut R,
217 -> RelateResult<'tcx, abi::Abi>
218 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
223 Err(TypeError::AbiMismatch(expected_found(relation, a, b)))
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
235 if a.item_name != b.item_name {
236 Err(TypeError::ProjectionNameMismatched(
237 expected_found(relation, &a.item_name, &b.item_name)))
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 })
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
252 if a.item_name != b.item_name {
253 Err(TypeError::ProjectionNameMismatched(
254 expected_found(relation, &a.item_name, &b.item_name)))
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,
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
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
279 if a.len() != b.len() {
280 Err(TypeError::ProjectionBoundsLength(expected_found(relation, &a.len(), &b.len())))
283 .map(|(a, b)| relation.relate(a, b))
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
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)))
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 })
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
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)))
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 })
323 impl<'tcx> Relate<'tcx> for Ty<'tcx> {
324 fn relate<'a, 'gcx, R>(relation: &mut R,
327 -> RelateResult<'tcx, Ty<'tcx>>
328 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
334 /// The main "type relation" routine. Note that this does not handle
335 /// inference artifacts, so you should filter those out before calling
337 pub fn super_relate_tys<'a, 'gcx, 'tcx, R>(relation: &mut R,
340 -> RelateResult<'tcx, Ty<'tcx>>
341 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
343 let tcx = relation.tcx();
346 debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
347 match (a_sty, b_sty) {
348 (&ty::TyInfer(_), _) |
349 (_, &ty::TyInfer(_)) =>
351 // The caller should handle these cases!
352 bug!("var types encountered in super_relate_tys")
355 (&ty::TyError, _) | (_, &ty::TyError) =>
364 (&ty::TyUint(_), _) |
365 (&ty::TyFloat(_), _) |
372 (&ty::TyParam(ref a_p), &ty::TyParam(ref b_p))
373 if a_p.idx == b_p.idx =>
378 (&ty::TyAdt(a_def, a_substs), &ty::TyAdt(b_def, b_substs))
381 let substs = relate_item_substs(relation, a_def.did, a_substs, b_substs)?;
382 Ok(tcx.mk_adt(a_def, substs))
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,
388 relation.relate_with_variance(
393 Ok(tcx.mk_dynamic(relation.relate(a_obj, b_obj)?, region_bound))
396 (&ty::TyClosure(a_id, a_substs),
397 &ty::TyClosure(b_id, b_substs))
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))
407 (&ty::TyRawPtr(ref a_mt), &ty::TyRawPtr(ref b_mt)) =>
409 let mt = relation.relate(a_mt, b_mt)?;
413 (&ty::TyRef(a_r, ref a_mt), &ty::TyRef(b_r, ref b_mt)) =>
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))
420 (&ty::TyArray(a_t, sz_a), &ty::TyArray(b_t, sz_b)) =>
422 let t = relation.relate(&a_t, &b_t)?;
424 Ok(tcx.mk_array(t, sz_a))
426 Err(TypeError::FixedArraySize(expected_found(relation, &sz_a, &sz_b)))
430 (&ty::TySlice(a_t), &ty::TySlice(b_t)) =>
432 let t = relation.relate(&a_t, &b_t)?;
436 (&ty::TyTuple(as_, a_defaulted), &ty::TyTuple(bs, b_defaulted)) =>
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())))
445 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
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 =>
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))
458 (&ty::TyFnPtr(a_fty), &ty::TyFnPtr(b_fty)) =>
460 let fty = relation.relate(&a_fty, &b_fty)?;
461 Ok(tcx.mk_fn_ptr(fty))
464 (&ty::TyProjection(ref a_data), &ty::TyProjection(ref b_data)) =>
466 let projection_ty = relation.relate(a_data, b_data)?;
467 Ok(tcx.mk_projection(projection_ty.trait_ref, projection_ty.item_name))
470 (&ty::TyAnon(a_def_id, a_substs), &ty::TyAnon(b_def_id, b_substs))
471 if a_def_id == b_def_id =>
473 let substs = relate_substs(relation, None, a_substs, b_substs)?;
474 Ok(tcx.mk_anon(a_def_id, substs))
479 Err(TypeError::Sorts(expected_found(relation, &a, &b)))
484 impl<'tcx> Relate<'tcx> for &'tcx ty::Slice<ty::ExistentialPredicate<'tcx>> {
485 fn relate<'a, 'gcx, R>(relation: &mut R,
488 -> RelateResult<'tcx, Self>
489 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a {
491 if a.len() != b.len() {
492 return Err(TypeError::ExistentialMismatch(expected_found(relation, a, b)));
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)))
505 Ok(tcx.mk_existential_predicates(v)?)
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
516 let substs = relate_substs(relation, None, a.substs, b.substs)?;
517 Ok(ty::ClosureSubsts { substs: substs })
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
528 relate_substs(relation, None, a, b)
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
539 relation.regions(*a, *b)
543 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for ty::Binder<T> {
544 fn relate<'a, 'gcx, R>(relation: &mut R,
547 -> RelateResult<'tcx, ty::Binder<T>>
548 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
550 relation.binders(a, b)
554 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Rc<T> {
555 fn relate<'a, 'gcx, R>(relation: &mut R,
558 -> RelateResult<'tcx, Rc<T>>
559 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
563 Ok(Rc::new(relation.relate(a, b)?))
567 impl<'tcx, T: Relate<'tcx>> Relate<'tcx> for Box<T> {
568 fn relate<'a, 'gcx, R>(relation: &mut R,
571 -> RelateResult<'tcx, Box<T>>
572 where R: TypeRelation<'a, 'gcx, 'tcx>, 'gcx: 'a+'tcx, 'tcx: 'a
576 Ok(Box::new(relation.relate(a, b)?))
580 ///////////////////////////////////////////////////////////////////////////
583 pub fn expected_found<'a, 'gcx, 'tcx, R, T>(relation: &mut R,
587 where R: TypeRelation<'a, 'gcx, 'tcx>, T: Clone, 'gcx: 'a+'tcx, 'tcx: 'a
589 expected_found_bool(relation.a_is_expected(), a, b)
592 pub fn expected_found_bool<T>(a_is_expected: bool,
601 ExpectedFound {expected: a, found: b}
603 ExpectedFound {expected: b, found: a}