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 three type combiners: sub, lub, and glb. Each implements
15 // the trait `Combine` and contains methods for combining two
16 // instances of various things and yielding a new instance. These
17 // combiner methods always yield a `result<T>`---failure is propagated
18 // upward using `and_then()` methods. There is a lot of common code for
19 // these operations, implemented as default methods on the `Combine`
22 // In reality, the sub operation is rather different from lub/glb, but
23 // they are combined into one trait to avoid duplication (they used to
24 // be separate but there were many bugs because there were two copies
27 // The differences are:
29 // - when making two things have a sub relationship, the order of the
30 // arguments is significant (a <: b) and the return value of the
31 // combine functions is largely irrelevant. The important thing is
32 // whether the action succeeds or fails. If it succeeds, then side
33 // effects have been committed into the type variables.
35 // - for GLB/LUB, the order of arguments is not significant (GLB(a,b) ==
36 // GLB(b,a)) and the return value is important (it is the GLB). Of
37 // course GLB/LUB may also have side effects.
41 // When you are relating two things which have a contravariant
42 // relationship, you should use `contratys()` or `contraregions()`,
43 // rather than inversing the order of arguments! This is necessary
44 // because the order of arguments is not relevant for LUB and GLB. It
45 // is also useful to track which value is the "expected" value in
46 // terms of error reporting, although we do not do that properly right
51 use middle::subst::Substs;
52 use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
53 use middle::ty::{IntType, UintType};
54 use middle::ty::{BuiltinBounds};
56 use middle::typeck::infer::{ToUres};
57 use middle::typeck::infer::glb::Glb;
58 use middle::typeck::infer::lub::Lub;
59 use middle::typeck::infer::sub::Sub;
60 use middle::typeck::infer::to_str::InferStr;
61 use middle::typeck::infer::unify::InferCtxtMethods;
62 use middle::typeck::infer::{InferCtxt, cres, ures};
63 use middle::typeck::infer::{TypeTrace};
64 use util::common::indent;
65 use util::ppaux::Repr;
69 use syntax::ast::{Onceness, FnStyle};
74 fn infcx<'a>(&'a self) -> &'a InferCtxt<'a>;
75 fn tag(&self) -> String;
76 fn a_is_expected(&self) -> bool;
77 fn trace(&self) -> TypeTrace;
79 fn sub<'a>(&'a self) -> Sub<'a>;
80 fn lub<'a>(&'a self) -> Lub<'a>;
81 fn glb<'a>(&'a self) -> Glb<'a>;
83 fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt>;
84 fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t>;
85 fn tys(&self, a: ty::t, b: ty::t) -> cres<ty::t>;
88 space: subst::ParamSpace,
93 // FIXME(#5781) -- In general, we treat variance a bit wrong
94 // here. For historical reasons, we treat Self as
95 // contravariant and other tps as invariant. Both are wrong:
96 // Self may or may not be contravariant, and other tps do not
97 // need to be invariant.
99 if as_.len() != bs.len() {
100 return Err(ty::terr_ty_param_size(expected_found(self,
106 subst::SelfSpace => {
110 .map(|(a, b)| self.contratys(*a, *b)),
112 |mut v, a| { v.push(a); v })
115 subst::TypeSpace | subst::FnSpace => {
116 try!(result::fold_(as_
119 .map(|(a, b)| eq_tys(self, *a, *b))));
120 Ok(Vec::from_slice(as_))
126 item_def_id: ast::DefId,
127 a_subst: &subst::Substs,
128 b_subst: &subst::Substs)
129 -> cres<subst::Substs>
131 let variances = ty::item_variances(self.infcx().tcx, item_def_id);
132 let mut substs = subst::Substs::empty();
134 for &space in subst::ParamSpace::all().iter() {
135 let a_tps = a_subst.types.get_vec(space);
136 let b_tps = b_subst.types.get_vec(space);
137 let tps = if_ok!(self.tps(space,
141 let a_regions = a_subst.regions().get_vec(space);
142 let b_regions = b_subst.regions().get_vec(space);
143 let r_variances = variances.regions.get_vec(space);
144 let regions = if_ok!(relate_region_params(self,
150 *substs.types.get_mut_vec(space) = tps;
151 *substs.mut_regions().get_mut_vec(space) = regions;
156 fn relate_region_params<C:Combine>(this: &C,
157 item_def_id: ast::DefId,
158 variances: &Vec<ty::Variance>,
159 a_rs: &Vec<ty::Region>,
160 b_rs: &Vec<ty::Region>)
161 -> cres<Vec<ty::Region>>
163 let tcx = this.infcx().tcx;
164 let num_region_params = variances.len();
166 debug!("relate_region_params(\
171 item_def_id.repr(tcx),
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) {
180 let a_r = *a_rs.get(i);
181 let b_r = *b_rs.get(i);
182 let variance = *variances.get(i);
183 let r = match variance {
185 eq_regions(this, a_r, b_r)
186 .and_then(|()| Ok(a_r))
188 ty::Covariant => this.regions(a_r, b_r),
189 ty::Contravariant => this.contraregions(a_r, b_r),
190 ty::Bivariant => Ok(a_r),
198 fn bare_fn_tys(&self, a: &ty::BareFnTy,
199 b: &ty::BareFnTy) -> cres<ty::BareFnTy> {
200 let fn_style = if_ok!(self.fn_styles(a.fn_style, b.fn_style));
201 let abi = if_ok!(self.abi(a.abi, b.abi));
202 let sig = if_ok!(self.fn_sigs(&a.sig, &b.sig));
203 Ok(ty::BareFnTy {fn_style: fn_style,
208 fn closure_tys(&self, a: &ty::ClosureTy,
209 b: &ty::ClosureTy) -> cres<ty::ClosureTy> {
211 let store = match (a.store, b.store) {
212 (ty::RegionTraitStore(a_r, a_m),
213 ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
214 let r = if_ok!(self.contraregions(a_r, b_r));
215 ty::RegionTraitStore(r, a_m)
218 _ if a.store == b.store => {
223 return Err(ty::terr_sigil_mismatch(expected_found(self, a.store, b.store)))
226 let fn_style = if_ok!(self.fn_styles(a.fn_style, b.fn_style));
227 let onceness = if_ok!(self.oncenesses(a.onceness, b.onceness));
228 let bounds = if_ok!(self.bounds(a.bounds, b.bounds));
229 let sig = if_ok!(self.fn_sigs(&a.sig, &b.sig));
239 fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig>;
241 fn args(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
242 self.contratys(a, b).and_then(|t| Ok(t))
245 fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<FnStyle>;
247 fn abi(&self, a: abi::Abi, b: abi::Abi) -> cres<abi::Abi> {
251 Err(ty::terr_abi_mismatch(expected_found(self, a, b)))
255 fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<Onceness>;
256 fn bounds(&self, a: BuiltinBounds, b: BuiltinBounds) -> cres<BuiltinBounds>;
257 fn contraregions(&self, a: ty::Region, b: ty::Region)
259 fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region>;
261 fn trait_stores(&self,
262 vk: ty::terr_vstore_kind,
265 -> cres<ty::TraitStore> {
266 debug!("{}.trait_stores(a={:?}, b={:?})", self.tag(), a, b);
269 (ty::RegionTraitStore(a_r, a_m),
270 ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => {
271 self.contraregions(a_r, b_r).and_then(|r| {
272 Ok(ty::RegionTraitStore(r, a_m))
281 Err(ty::terr_trait_stores_differ(vk, expected_found(self, a, b)))
290 -> cres<ty::TraitRef> {
291 // Different traits cannot be related
293 // - NOTE in the future, expand out subtraits!
295 if a.def_id != b.def_id {
297 expected_found(self, a.def_id, b.def_id)))
299 let substs = if_ok!(self.substs(a.def_id, &a.substs, &b.substs));
300 Ok(ty::TraitRef { def_id: a.def_id,
307 pub struct CombineFields<'a> {
308 pub infcx: &'a InferCtxt<'a>,
309 pub a_is_expected: bool,
310 pub trace: TypeTrace,
313 pub fn expected_found<C:Combine,T>(
314 this: &C, a: T, b: T) -> ty::expected_found<T> {
315 if this.a_is_expected() {
316 ty::expected_found {expected: a, found: b}
318 ty::expected_found {expected: b, found: a}
322 pub fn eq_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> ures {
323 let suber = this.sub();
324 this.infcx().try(|| {
325 suber.tys(a, b).and_then(|_ok| suber.contratys(a, b)).to_ures()
329 pub fn eq_regions<C:Combine>(this: &C, a: ty::Region, b: ty::Region)
331 debug!("eq_regions({}, {})",
332 a.repr(this.infcx().tcx),
333 b.repr(this.infcx().tcx));
334 let sub = this.sub();
336 this.infcx().try(|| {
337 sub.regions(a, b).and_then(|_r| sub.contraregions(a, b))
339 // substitute a better error, but use the regions
340 // found in the original error
342 ty::terr_regions_does_not_outlive(a1, b1) =>
343 Err(ty::terr_regions_not_same(a1, b1)),
350 pub fn super_fn_sigs<C:Combine>(this: &C, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
352 fn argvecs<C:Combine>(this: &C, a_args: &[ty::t], b_args: &[ty::t]) -> cres<Vec<ty::t> > {
353 if a_args.len() == b_args.len() {
354 result::collect(a_args.iter().zip(b_args.iter())
355 .map(|(a, b)| this.args(*a, *b)))
357 Err(ty::terr_arg_count)
361 if a.variadic != b.variadic {
362 return Err(ty::terr_variadic_mismatch(expected_found(this, a.variadic, b.variadic)));
365 let inputs = if_ok!(argvecs(this,
367 b.inputs.as_slice()));
368 let output = if_ok!(this.tys(a.output, b.output));
369 Ok(FnSig {binder_id: a.binder_id,
372 variadic: a.variadic})
375 pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
377 // This is a horrible hack - historically, [T] was not treated as a type,
378 // so, for example, &T and &[U] should not unify. In fact the only thing
379 // &[U] should unify with is &[T]. We preserve that behaviour with this
381 fn check_ptr_to_unsized<C:Combine>(this: &C,
386 result: ty::t) -> cres<ty::t> {
387 match (&ty::get(a_inner).sty, &ty::get(b_inner).sty) {
388 (&ty::ty_vec(_, None), &ty::ty_vec(_, None)) |
389 (&ty::ty_str, &ty::ty_str) |
390 (&ty::ty_trait(..), &ty::ty_trait(..)) => Ok(result),
391 (&ty::ty_vec(_, None), _) | (_, &ty::ty_vec(_, None)) |
392 (&ty::ty_str, _) | (_, &ty::ty_str) |
393 (&ty::ty_trait(..), _) | (_, &ty::ty_trait(..))
394 => Err(ty::terr_sorts(expected_found(this, a, b))),
399 let tcx = this.infcx().tcx;
400 let a_sty = &ty::get(a).sty;
401 let b_sty = &ty::get(b).sty;
402 debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
403 return match (a_sty, b_sty) {
404 // The "subtype" ought to be handling cases involving bot or var:
407 (&ty::ty_infer(TyVar(_)), _) |
408 (_, &ty::ty_infer(TyVar(_))) => {
410 format!("{}: bot and var types should have been handled ({},{})",
412 a.inf_str(this.infcx()),
413 b.inf_str(this.infcx())).as_slice());
416 // Relate integral variables to other types
417 (&ty::ty_infer(IntVar(a_id)), &ty::ty_infer(IntVar(b_id))) => {
418 if_ok!(this.infcx().simple_vars(this.a_is_expected(),
422 (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => {
423 unify_integral_variable(this, this.a_is_expected(),
426 (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => {
427 unify_integral_variable(this, !this.a_is_expected(),
430 (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => {
431 unify_integral_variable(this, this.a_is_expected(),
434 (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => {
435 unify_integral_variable(this, !this.a_is_expected(),
439 // Relate floating-point variables to other types
440 (&ty::ty_infer(FloatVar(a_id)), &ty::ty_infer(FloatVar(b_id))) => {
441 if_ok!(this.infcx().simple_vars(this.a_is_expected(),
445 (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => {
446 unify_float_variable(this, this.a_is_expected(), v_id, v)
448 (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => {
449 unify_float_variable(this, !this.a_is_expected(), v_id, v)
455 (&ty::ty_int(_), _) |
456 (&ty::ty_uint(_), _) |
457 (&ty::ty_float(_), _) => {
458 if ty::get(a).sty == ty::get(b).sty {
461 Err(ty::terr_sorts(expected_found(this, a, b)))
465 (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if a_p.idx == b_p.idx => {
469 (&ty::ty_enum(a_id, ref a_substs),
470 &ty::ty_enum(b_id, ref b_substs))
472 let substs = if_ok!(this.substs(a_id,
475 Ok(ty::mk_enum(tcx, a_id, substs))
478 (&ty::ty_trait(ref a_),
479 &ty::ty_trait(ref b_))
480 if a_.def_id == b_.def_id => {
481 debug!("Trying to match traits {:?} and {:?}", a, b);
482 let substs = if_ok!(this.substs(a_.def_id, &a_.substs, &b_.substs));
483 let bounds = if_ok!(this.bounds(a_.bounds, b_.bounds));
490 (&ty::ty_struct(a_id, ref a_substs), &ty::ty_struct(b_id, ref b_substs))
492 let substs = if_ok!(this.substs(a_id, a_substs, b_substs));
493 Ok(ty::mk_struct(tcx, a_id, substs))
496 (&ty::ty_box(a_inner), &ty::ty_box(b_inner)) => {
497 this.tys(a_inner, b_inner).and_then(|typ| Ok(ty::mk_box(tcx, typ)))
500 (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) => {
501 let typ = if_ok!(this.tys(a_inner, b_inner));
502 check_ptr_to_unsized(this, a, b, a_inner, b_inner, ty::mk_uniq(tcx, typ))
505 (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) => {
506 let mt = if_ok!(this.mts(a_mt, b_mt));
507 check_ptr_to_unsized(this, a, b, a_mt.ty, b_mt.ty, ty::mk_ptr(tcx, mt))
510 (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) => {
511 let r = if_ok!(this.contraregions(a_r, b_r));
512 // FIXME(14985) If we have mutable references to trait objects, we
513 // used to use covariant subtyping. I have preserved this behaviour,
514 // even though it is probably incorrect. So don't go down the usual
515 // path which would require invariance.
516 let mt = match (&ty::get(a_mt.ty).sty, &ty::get(b_mt.ty).sty) {
517 (&ty::ty_trait(..), &ty::ty_trait(..)) if a_mt.mutbl == b_mt.mutbl => {
518 let ty = if_ok!(this.tys(a_mt.ty, b_mt.ty));
519 ty::mt { ty: ty, mutbl: a_mt.mutbl }
521 _ => if_ok!(this.mts(a_mt, b_mt))
523 check_ptr_to_unsized(this, a, b, a_mt.ty, b_mt.ty, ty::mk_rptr(tcx, r, mt))
526 (&ty::ty_vec(ref a_mt, sz_a), &ty::ty_vec(ref b_mt, sz_b)) => {
527 this.mts(a_mt, b_mt).and_then(|mt| {
529 Ok(ty::mk_vec(tcx, mt, sz_a))
531 Err(ty::terr_sorts(expected_found(this, a, b)))
536 (&ty::ty_str, &ty::ty_str) => {
540 (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => {
541 if as_.len() == bs.len() {
542 result::collect(as_.iter().zip(bs.iter())
543 .map(|(a, b)| this.tys(*a, *b)))
544 .and_then(|ts| Ok(ty::mk_tup(tcx, ts)) )
546 Err(ty::terr_tuple_size(
547 expected_found(this, as_.len(), bs.len())))
551 (&ty::ty_bare_fn(ref a_fty), &ty::ty_bare_fn(ref b_fty)) => {
552 this.bare_fn_tys(a_fty, b_fty).and_then(|fty| {
553 Ok(ty::mk_bare_fn(tcx, fty))
557 (&ty::ty_closure(ref a_fty), &ty::ty_closure(ref b_fty)) => {
558 this.closure_tys(*a_fty, *b_fty).and_then(|fty| {
559 Ok(ty::mk_closure(tcx, fty))
563 _ => Err(ty::terr_sorts(expected_found(this, a, b)))
566 fn unify_integral_variable<C:Combine>(
568 vid_is_expected: bool,
570 val: ty::IntVarValue) -> cres<ty::t>
572 if_ok!(this.infcx().simple_var_t(vid_is_expected, vid, val));
574 IntType(v) => Ok(ty::mk_mach_int(v)),
575 UintType(v) => Ok(ty::mk_mach_uint(v))
579 fn unify_float_variable<C:Combine>(
581 vid_is_expected: bool,
583 val: ast::FloatTy) -> cres<ty::t>
585 if_ok!(this.infcx().simple_var_t(vid_is_expected, vid, val));
586 Ok(ty::mk_mach_float(val))