1 // Copyright 2012 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 ///////////////////////////////////////////////////////////////////////////
14 // There are four type combiners: equate, sub, lub, and glb. Each
15 // implements the trait `Combine` and contains methods for combining
16 // two instances of various things and yielding a new instance. These
17 // combiner methods always yield a `Result<T>`. There is a lot of
18 // common code for these operations, implemented as default methods on
19 // the `Combine` trait.
21 // Each operation may have side-effects on the inference context,
22 // though these can be unrolled using snapshots. On success, the
23 // LUB/GLB operations return the appropriate bound. The Eq and Sub
24 // operations generally return the first operand.
28 // When you are relating two things which have a contravariant
29 // relationship, you should use `contratys()` or `contraregions()`,
30 // rather than inversing the order of arguments! This is necessary
31 // because the order of arguments is not relevant for LUB and GLB. It
32 // is also useful to track which value is the "expected" value in
33 // terms of error reporting.
37 use middle::subst::{ErasedRegions, NonerasedRegions, Substs};
38 use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
39 use middle::ty::{IntType, UintType};
40 use middle::ty::{BuiltinBounds};
41 use middle::ty::{mod, Ty};
43 use middle::typeck::infer::equate::Equate;
44 use middle::typeck::infer::glb::Glb;
45 use middle::typeck::infer::lub::Lub;
46 use middle::typeck::infer::sub::Sub;
47 use middle::typeck::infer::unify::InferCtxtMethodsForSimplyUnifiableTypes;
48 use middle::typeck::infer::{InferCtxt, cres};
49 use middle::typeck::infer::{MiscVariable, TypeTrace};
50 use middle::typeck::infer::type_variable::{RelationDir, EqTo,
51 SubtypeOf, SupertypeOf};
52 use middle::ty_fold::{TypeFoldable};
53 use util::ppaux::Repr;
55 use syntax::ast::{Onceness, FnStyle};
58 use syntax::codemap::Span;
60 pub trait Combine<'tcx> {
61 fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx>;
62 fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.infcx().tcx }
63 fn tag(&self) -> String;
64 fn a_is_expected(&self) -> bool;
65 fn trace(&self) -> TypeTrace<'tcx>;
67 fn equate<'a>(&'a self) -> Equate<'a, 'tcx>;
68 fn sub<'a>(&'a self) -> Sub<'a, 'tcx>;
69 fn lub<'a>(&'a self) -> Lub<'a, 'tcx>;
70 fn glb<'a>(&'a self) -> Glb<'a, 'tcx>;
72 fn mts(&self, a: &ty::mt<'tcx>, b: &ty::mt<'tcx>) -> cres<'tcx, ty::mt<'tcx>>;
73 fn contratys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>>;
74 fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>>;
80 -> cres<'tcx, Vec<Ty<'tcx>>> {
81 // FIXME -- In general, we treat variance a bit wrong
82 // here. For historical reasons, we treat tps and Self
83 // as invariant. This is overly conservative.
85 if as_.len() != bs.len() {
86 return Err(ty::terr_ty_param_size(expected_found(self,
91 try!(as_.iter().zip(bs.iter())
92 .map(|(a, b)| self.equate().tys(*a, *b))
93 .collect::<cres<Vec<Ty>>>());
98 item_def_id: ast::DefId,
99 a_subst: &subst::Substs<'tcx>,
100 b_subst: &subst::Substs<'tcx>)
101 -> cres<'tcx, subst::Substs<'tcx>>
103 let variances = if self.infcx().tcx.variance_computed.get() {
104 Some(ty::item_variances(self.infcx().tcx, item_def_id))
108 self.substs_variances(variances.as_ref().map(|v| &**v), a_subst, b_subst)
111 fn substs_variances(&self,
112 variances: Option<&ty::ItemVariances>,
113 a_subst: &subst::Substs<'tcx>,
114 b_subst: &subst::Substs<'tcx>)
115 -> cres<'tcx, subst::Substs<'tcx>>
117 let mut substs = subst::Substs::empty();
119 for &space in subst::ParamSpace::all().iter() {
120 let a_tps = a_subst.types.get_slice(space);
121 let b_tps = b_subst.types.get_slice(space);
122 let tps = try!(self.tps(space, a_tps, b_tps));
123 substs.types.replace(space, tps);
126 match (&a_subst.regions, &b_subst.regions) {
127 (&ErasedRegions, _) | (_, &ErasedRegions) => {
128 substs.regions = ErasedRegions;
131 (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => {
132 for &space in subst::ParamSpace::all().iter() {
133 let a_regions = a.get_slice(space);
134 let b_regions = b.get_slice(space);
136 let mut invariance = Vec::new();
137 let r_variances = match variances {
139 variances.regions.get_slice(space)
142 for _ in a_regions.iter() {
143 invariance.push(ty::Invariant);
145 invariance.as_slice()
149 let regions = try!(relate_region_params(self,
153 substs.mut_regions().replace(space, regions);
160 fn relate_region_params<'tcx, C: Combine<'tcx>>(this: &C,
161 variances: &[ty::Variance],
164 -> cres<'tcx, Vec<ty::Region>> {
165 let tcx = this.infcx().tcx;
166 let num_region_params = variances.len();
168 debug!("relate_region_params(\
174 variances.repr(tcx));
176 assert_eq!(num_region_params, a_rs.len());
177 assert_eq!(num_region_params, b_rs.len());
179 for i in range(0, num_region_params) {
182 let variance = variances[i];
183 let r = match variance {
184 ty::Invariant => this.equate().regions(a_r, b_r),
185 ty::Covariant => this.regions(a_r, b_r),
186 ty::Contravariant => this.contraregions(a_r, b_r),
187 ty::Bivariant => Ok(a_r),
195 fn bare_fn_tys(&self, a: &ty::BareFnTy<'tcx>,
196 b: &ty::BareFnTy<'tcx>) -> cres<'tcx, ty::BareFnTy<'tcx>> {
197 let fn_style = try!(self.fn_styles(a.fn_style, b.fn_style));
198 let abi = try!(self.abi(a.abi, b.abi));
199 let sig = try!(self.fn_sigs(&a.sig, &b.sig));
200 Ok(ty::BareFnTy {fn_style: fn_style,
205 fn closure_tys(&self, a: &ty::ClosureTy<'tcx>,
206 b: &ty::ClosureTy<'tcx>) -> cres<'tcx, ty::ClosureTy<'tcx>> {
208 let store = match (a.store, b.store) {
209 (ty::RegionTraitStore(a_r, a_m),
210 ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
211 let r = try!(self.contraregions(a_r, b_r));
212 ty::RegionTraitStore(r, a_m)
215 _ if a.store == b.store => {
220 return Err(ty::terr_sigil_mismatch(expected_found(self, a.store, b.store)))
223 let fn_style = try!(self.fn_styles(a.fn_style, b.fn_style));
224 let onceness = try!(self.oncenesses(a.onceness, b.onceness));
225 let bounds = try!(self.existential_bounds(a.bounds, b.bounds));
226 let sig = try!(self.fn_sigs(&a.sig, &b.sig));
227 let abi = try!(self.abi(a.abi, b.abi));
238 fn fn_sigs(&self, a: &ty::FnSig<'tcx>, b: &ty::FnSig<'tcx>) -> cres<'tcx, ty::FnSig<'tcx>>;
240 fn args(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>> {
241 self.contratys(a, b).and_then(|t| Ok(t))
244 fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<'tcx, FnStyle>;
246 fn abi(&self, a: abi::Abi, b: abi::Abi) -> cres<'tcx, abi::Abi> {
250 Err(ty::terr_abi_mismatch(expected_found(self, a, b)))
254 fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<'tcx, Onceness>;
256 fn existential_bounds(&self,
257 a: ty::ExistentialBounds,
258 b: ty::ExistentialBounds)
259 -> cres<'tcx, ty::ExistentialBounds>
261 let r = try!(self.contraregions(a.region_bound, b.region_bound));
262 let nb = try!(self.builtin_bounds(a.builtin_bounds, b.builtin_bounds));
263 Ok(ty::ExistentialBounds { region_bound: r,
264 builtin_bounds: nb })
267 fn builtin_bounds(&self,
268 a: ty::BuiltinBounds,
269 b: ty::BuiltinBounds)
270 -> cres<'tcx, ty::BuiltinBounds>;
272 fn contraregions(&self, a: ty::Region, b: ty::Region)
273 -> cres<'tcx, ty::Region>;
275 fn regions(&self, a: ty::Region, b: ty::Region) -> cres<'tcx, ty::Region>;
277 fn trait_stores(&self,
278 vk: ty::terr_vstore_kind,
281 -> cres<'tcx, ty::TraitStore> {
282 debug!("{}.trait_stores(a={}, b={})", self.tag(), a, b);
285 (ty::RegionTraitStore(a_r, a_m),
286 ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
287 self.contraregions(a_r, b_r).and_then(|r| {
288 Ok(ty::RegionTraitStore(r, a_m))
297 Err(ty::terr_trait_stores_differ(vk, expected_found(self, a, b)))
303 a: &ty::TraitRef<'tcx>,
304 b: &ty::TraitRef<'tcx>)
305 -> cres<'tcx, ty::TraitRef<'tcx>>;
306 // this must be overridden to do correctly, so as to account for higher-ranked
311 pub struct CombineFields<'a, 'tcx: 'a> {
312 pub infcx: &'a InferCtxt<'a, 'tcx>,
313 pub a_is_expected: bool,
314 pub trace: TypeTrace<'tcx>,
317 pub fn expected_found<'tcx, C: Combine<'tcx>, T>(
318 this: &C, a: T, b: T) -> ty::expected_found<T> {
319 if this.a_is_expected() {
320 ty::expected_found {expected: a, found: b}
322 ty::expected_found {expected: b, found: a}
326 pub fn super_tys<'tcx, C: Combine<'tcx>>(this: &C,
329 -> cres<'tcx, Ty<'tcx>> {
331 let tcx = this.infcx().tcx;
334 debug!("super_tys: a_sty={} b_sty={}", a_sty, b_sty);
335 return match (a_sty, b_sty) {
336 // The "subtype" ought to be handling cases involving var:
337 (&ty::ty_infer(TyVar(_)), _) |
338 (_, &ty::ty_infer(TyVar(_))) => {
340 format!("{}: bot and var types should have been handled ({},{})",
342 a.repr(this.infcx().tcx),
343 b.repr(this.infcx().tcx)).as_slice());
346 (&ty::ty_err, _) | (_, &ty::ty_err) => {
350 // Relate integral variables to other types
351 (&ty::ty_infer(IntVar(a_id)), &ty::ty_infer(IntVar(b_id))) => {
352 try!(this.infcx().simple_vars(this.a_is_expected(),
356 (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => {
357 unify_integral_variable(this, this.a_is_expected(),
360 (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => {
361 unify_integral_variable(this, !this.a_is_expected(),
364 (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => {
365 unify_integral_variable(this, this.a_is_expected(),
368 (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => {
369 unify_integral_variable(this, !this.a_is_expected(),
373 // Relate floating-point variables to other types
374 (&ty::ty_infer(FloatVar(a_id)), &ty::ty_infer(FloatVar(b_id))) => {
375 try!(this.infcx().simple_vars(this.a_is_expected(), a_id, b_id));
378 (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => {
379 unify_float_variable(this, this.a_is_expected(), v_id, v)
381 (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => {
382 unify_float_variable(this, !this.a_is_expected(), v_id, v)
387 (&ty::ty_int(_), _) |
388 (&ty::ty_uint(_), _) |
389 (&ty::ty_float(_), _) => {
393 Err(ty::terr_sorts(expected_found(this, a, b)))
397 (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if
398 a_p.idx == b_p.idx && a_p.space == b_p.space => {
402 (&ty::ty_enum(a_id, ref a_substs),
403 &ty::ty_enum(b_id, ref b_substs))
405 let substs = try!(this.substs(a_id,
408 Ok(ty::mk_enum(tcx, a_id, substs))
411 (&ty::ty_trait(ref a_),
412 &ty::ty_trait(ref b_)) => {
413 debug!("Trying to match traits {} and {}", a, b);
414 let principal = try!(this.trait_refs(&a_.principal, &b_.principal));
415 let bounds = try!(this.existential_bounds(a_.bounds, b_.bounds));
416 Ok(ty::mk_trait(tcx, principal, bounds))
419 (&ty::ty_struct(a_id, ref a_substs), &ty::ty_struct(b_id, ref b_substs))
421 let substs = try!(this.substs(a_id, a_substs, b_substs));
422 Ok(ty::mk_struct(tcx, a_id, substs))
425 (&ty::ty_unboxed_closure(a_id, a_region, ref a_substs),
426 &ty::ty_unboxed_closure(b_id, b_region, ref b_substs))
428 // All ty_unboxed_closure types with the same id represent
429 // the (anonymous) type of the same closure expression. So
430 // all of their regions should be equated.
431 let region = try!(this.equate().regions(a_region, b_region));
432 let substs = try!(this.substs_variances(None, a_substs, b_substs));
433 Ok(ty::mk_unboxed_closure(tcx, a_id, region, substs))
436 (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) => {
437 let typ = try!(this.tys(a_inner, b_inner));
438 Ok(ty::mk_uniq(tcx, typ))
441 (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) => {
442 let mt = try!(this.mts(a_mt, b_mt));
443 Ok(ty::mk_ptr(tcx, mt))
446 (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) => {
447 let r = try!(this.contraregions(a_r, b_r));
448 // FIXME(14985) If we have mutable references to trait objects, we
449 // used to use covariant subtyping. I have preserved this behaviour,
450 // even though it is probably incorrect. So don't go down the usual
451 // path which would require invariance.
452 let mt = match (&a_mt.ty.sty, &b_mt.ty.sty) {
453 (&ty::ty_trait(..), &ty::ty_trait(..)) if a_mt.mutbl == b_mt.mutbl => {
454 let ty = try!(this.tys(a_mt.ty, b_mt.ty));
455 ty::mt { ty: ty, mutbl: a_mt.mutbl }
457 _ => try!(this.mts(a_mt, b_mt))
459 Ok(ty::mk_rptr(tcx, r, mt))
462 (&ty::ty_vec(a_t, Some(sz_a)), &ty::ty_vec(b_t, Some(sz_b))) => {
463 this.tys(a_t, b_t).and_then(|t| {
465 Ok(ty::mk_vec(tcx, t, Some(sz_a)))
467 Err(ty::terr_fixed_array_size(expected_found(this, sz_a, sz_b)))
472 (&ty::ty_vec(a_t, sz_a), &ty::ty_vec(b_t, sz_b)) => {
473 this.tys(a_t, b_t).and_then(|t| {
475 Ok(ty::mk_vec(tcx, t, sz_a))
477 Err(ty::terr_sorts(expected_found(this, a, b)))
482 (&ty::ty_str, &ty::ty_str) => {
486 (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => {
487 if as_.len() == bs.len() {
488 as_.iter().zip(bs.iter())
489 .map(|(a, b)| this.tys(*a, *b))
490 .collect::<Result<_, _>>()
491 .map(|ts| ty::mk_tup(tcx, ts))
492 } else if as_.len() != 0 && bs.len() != 0 {
493 Err(ty::terr_tuple_size(
494 expected_found(this, as_.len(), bs.len())))
496 Err(ty::terr_sorts(expected_found(this, a, b)))
500 (&ty::ty_bare_fn(ref a_fty), &ty::ty_bare_fn(ref b_fty)) => {
501 this.bare_fn_tys(a_fty, b_fty).and_then(|fty| {
502 Ok(ty::mk_bare_fn(tcx, fty))
506 (&ty::ty_closure(ref a_fty), &ty::ty_closure(ref b_fty)) => {
507 this.closure_tys(&**a_fty, &**b_fty).and_then(|fty| {
508 Ok(ty::mk_closure(tcx, fty))
512 _ => Err(ty::terr_sorts(expected_found(this, a, b)))
515 fn unify_integral_variable<'tcx, C: Combine<'tcx>>(
517 vid_is_expected: bool,
519 val: ty::IntVarValue) -> cres<'tcx, Ty<'tcx>>
521 try!(this.infcx().simple_var_t(vid_is_expected, vid, val));
523 IntType(v) => Ok(ty::mk_mach_int(v)),
524 UintType(v) => Ok(ty::mk_mach_uint(v))
528 fn unify_float_variable<'tcx, C: Combine<'tcx>>(
530 vid_is_expected: bool,
532 val: ast::FloatTy) -> cres<'tcx, Ty<'tcx>>
534 try!(this.infcx().simple_var_t(vid_is_expected, vid, val));
535 Ok(ty::mk_mach_float(val))
539 impl<'f, 'tcx> CombineFields<'f, 'tcx> {
540 pub fn switch_expected(&self) -> CombineFields<'f, 'tcx> {
542 a_is_expected: !self.a_is_expected,
547 fn equate(&self) -> Equate<'f, 'tcx> {
548 Equate((*self).clone())
551 fn sub(&self) -> Sub<'f, 'tcx> {
555 pub fn instantiate(&self,
561 let tcx = self.infcx.tcx;
562 let mut stack = Vec::new();
563 stack.push((a_ty, dir, b_vid));
565 // For each turn of the loop, we extract a tuple
567 // (a_ty, dir, b_vid)
569 // to relate. Here dir is either SubtypeOf or
570 // SupertypeOf. The idea is that we should ensure that
571 // the type `a_ty` is a subtype or supertype (respectively) of the
572 // type to which `b_vid` is bound.
574 // If `b_vid` has not yet been instantiated with a type
575 // (which is always true on the first iteration, but not
576 // necessarily true on later iterations), we will first
577 // instantiate `b_vid` with a *generalized* version of
578 // `a_ty`. Generalization introduces other inference
579 // variables wherever subtyping could occur (at time of
580 // this writing, this means replacing free regions with
581 // region variables).
582 let (a_ty, dir, b_vid) = match stack.pop() {
587 debug!("instantiate(a_ty={} dir={} b_vid={})",
592 // Check whether `vid` has been instantiated yet. If not,
593 // make a generalized form of `ty` and instantiate with
595 let b_ty = self.infcx.type_variables.borrow().probe(b_vid);
596 let b_ty = match b_ty {
597 Some(t) => t, // ...already instantiated.
598 None => { // ...not yet instantiated:
599 // Generalize type if necessary.
600 let generalized_ty = try!(match dir {
602 self.generalize(a_ty, b_vid, false)
604 SupertypeOf | SubtypeOf => {
605 self.generalize(a_ty, b_vid, true)
608 debug!("instantiate(a_ty={}, dir={}, \
609 b_vid={}, generalized_ty={})",
610 a_ty.repr(tcx), dir, b_vid.repr(tcx),
611 generalized_ty.repr(tcx));
612 self.infcx.type_variables
614 .instantiate_and_push(
615 b_vid, generalized_ty, &mut stack);
620 // The original triple was `(a_ty, dir, b_vid)` -- now we have
621 // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`:
623 // FIXME(#16847): This code is non-ideal because all these subtype
624 // relations wind up attributed to the same spans. We need
625 // to associate causes/spans with each of the relations in
626 // the stack to get this right.
629 try!(self.equate().tys(a_ty, b_ty));
633 try!(self.sub().tys(a_ty, b_ty));
637 try!(self.sub().contratys(a_ty, b_ty));
645 /// Attempts to generalize `ty` for the type variable `for_vid`. This checks for cycle -- that
646 /// is, whether the type `ty` references `for_vid`. If `make_region_vars` is true, it will also
647 /// replace all regions with fresh variables. Returns `ty_err` in the case of a cycle, `Ok`
652 make_region_vars: bool)
653 -> cres<'tcx, Ty<'tcx>>
655 let mut generalize = Generalizer { infcx: self.infcx,
656 span: self.trace.origin.span(),
658 make_region_vars: make_region_vars,
659 cycle_detected: false };
660 let u = ty.fold_with(&mut generalize);
661 if generalize.cycle_detected {
662 Err(ty::terr_cyclic_ty)
669 struct Generalizer<'cx, 'tcx:'cx> {
670 infcx: &'cx InferCtxt<'cx, 'tcx>,
673 make_region_vars: bool,
674 cycle_detected: bool,
677 impl<'cx, 'tcx> ty_fold::TypeFolder<'tcx> for Generalizer<'cx, 'tcx> {
678 fn tcx(&self) -> &ty::ctxt<'tcx> {
682 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
683 // Check to see whether the type we are genealizing references
684 // `vid`. At the same time, also update any type variables to
685 // the values that they are bound to. This is needed to truly
686 // check for cycles, but also just makes things readable.
688 // (In particular, you could have something like `$0 = Box<$1>`
689 // where `$1` has already been instantiated with `Box<$0>`)
691 ty::ty_infer(ty::TyVar(vid)) => {
692 if vid == self.for_vid {
693 self.cycle_detected = true;
696 match self.infcx.type_variables.borrow().probe(vid) {
697 Some(u) => self.fold_ty(u),
703 ty_fold::super_fold_ty(self, t)
708 fn fold_region(&mut self, r: ty::Region) -> ty::Region {
710 ty::ReLateBound(..) | ty::ReEarlyBound(..) => r,
711 _ if self.make_region_vars => {
712 // FIXME: This is non-ideal because we don't give a
713 // very descriptive origin for this region variable.
714 self.infcx.next_region_var(MiscVariable(self.span))