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
50 use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
51 use middle::ty::{IntType, UintType, substs};
52 use middle::ty::{BuiltinBounds};
54 use middle::typeck::infer::{then, ToUres};
55 use middle::typeck::infer::glb::Glb;
56 use middle::typeck::infer::lub::Lub;
57 use middle::typeck::infer::sub::Sub;
58 use middle::typeck::infer::to_str::InferStr;
59 use middle::typeck::infer::unify::InferCtxtMethods;
60 use middle::typeck::infer::{InferCtxt, cres, ures};
61 use middle::typeck::infer::{TypeTrace};
62 use util::common::indent;
63 use util::ppaux::Repr;
66 use syntax::ast::{Onceness, Purity};
69 use syntax::abi::AbiSet;
72 fn infcx<'a>(&'a self) -> &'a InferCtxt;
73 fn tag(&self) -> ~str;
74 fn a_is_expected(&self) -> bool;
75 fn trace(&self) -> TypeTrace;
77 fn sub<'a>(&'a self) -> Sub<'a>;
78 fn lub<'a>(&'a self) -> Lub<'a>;
79 fn glb<'a>(&'a self) -> Glb<'a>;
81 fn mts(&self, a: &ty::mt, b: &ty::mt) -> cres<ty::mt>;
82 fn contratys(&self, a: ty::t, b: ty::t) -> cres<ty::t>;
83 fn tys(&self, a: ty::t, b: ty::t) -> cres<ty::t>;
85 fn tps(&self, as_: &[ty::t], bs: &[ty::t]) -> cres<Vec<ty::t> > {
87 // Note: type parameters are always treated as *invariant*
88 // (otherwise the type system would be unsound). In the
89 // future we could allow type parameters to declare a
92 if as_.len() == bs.len() {
93 result::fold_(as_.iter().zip(bs.iter())
94 .map(|(a, b)| eq_tys(self, *a, *b)))
95 .then(|| Ok(as_.to_owned()))
97 Err(ty::terr_ty_param_size(expected_found(self,
103 fn self_tys(&self, a: Option<ty::t>, b: Option<ty::t>)
104 -> cres<Option<ty::t>> {
110 (Some(a), Some(b)) => {
111 // FIXME(#5781) this should be eq_tys
112 // eq_tys(self, a, b).then(|| Ok(Some(a)) )
113 self.contratys(a, b).and_then(|t| Ok(Some(t)))
117 // I think it should never happen that we unify two
118 // substs and one of them has a self_ty and one
119 // doesn't...? I could be wrong about this.
120 self.infcx().tcx.sess.bug(
121 format!("substitution a had a self_ty \
122 and substitution b didn't, \
129 item_def_id: ast::DefId,
131 bs: &ty::substs) -> cres<ty::substs> {
133 fn relate_region_params<C:Combine>(this: &C,
134 item_def_id: ast::DefId,
135 a: &ty::RegionSubsts,
136 b: &ty::RegionSubsts)
137 -> cres<ty::RegionSubsts> {
138 let tcx = this.infcx().tcx;
140 (&ty::ErasedRegions, _) | (_, &ty::ErasedRegions) => {
141 Ok(ty::ErasedRegions)
144 (&ty::NonerasedRegions(ref a_rs),
145 &ty::NonerasedRegions(ref b_rs)) => {
146 let variances = ty::item_variances(tcx, item_def_id);
147 let region_params = &variances.region_params;
148 let num_region_params = region_params.len();
150 debug!("relate_region_params(\
155 item_def_id.repr(tcx),
158 region_params.repr(tcx));
160 assert_eq!(num_region_params, a_rs.len());
161 assert_eq!(num_region_params, b_rs.len());
162 let mut rs = opt_vec::Empty;
163 for i in range(0, num_region_params) {
164 let a_r = *a_rs.get(i);
165 let b_r = *b_rs.get(i);
166 let variance = *region_params.get(i);
167 let r = match variance {
169 eq_regions(this, a_r, b_r)
170 .and_then(|()| Ok(a_r))
172 ty::Covariant => this.regions(a_r, b_r),
173 ty::Contravariant => this.contraregions(a_r, b_r),
174 ty::Bivariant => Ok(a_r),
178 Ok(ty::NonerasedRegions(rs))
183 let tps = if_ok!(self.tps(as_.tps, bs.tps));
184 let self_ty = if_ok!(self.self_tys(as_.self_ty, bs.self_ty));
185 let regions = if_ok!(relate_region_params(self,
189 Ok(substs { regions: regions,
194 fn bare_fn_tys(&self, a: &ty::BareFnTy,
195 b: &ty::BareFnTy) -> cres<ty::BareFnTy> {
196 let purity = if_ok!(self.purities(a.purity, b.purity));
197 let abi = if_ok!(self.abis(a.abis, b.abis));
198 let sig = if_ok!(self.fn_sigs(&a.sig, &b.sig));
199 Ok(ty::BareFnTy {purity: purity,
204 fn closure_tys(&self, a: &ty::ClosureTy,
205 b: &ty::ClosureTy) -> cres<ty::ClosureTy> {
207 let p = if_ok!(self.sigils(a.sigil, b.sigil));
208 let r = if_ok!(self.contraregions(a.region, b.region));
209 let purity = if_ok!(self.purities(a.purity, b.purity));
210 let onceness = if_ok!(self.oncenesses(a.onceness, b.onceness));
211 let bounds = if_ok!(self.bounds(a.bounds, b.bounds));
212 let sig = if_ok!(self.fn_sigs(&a.sig, &b.sig));
213 Ok(ty::ClosureTy {purity: purity,
221 fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig>;
223 fn flds(&self, a: ty::field, b: ty::field) -> cres<ty::field> {
224 if a.ident == b.ident {
225 self.mts(&a.mt, &b.mt)
226 .and_then(|mt| Ok(ty::field {ident: a.ident, mt: mt}) )
227 .or_else(|e| Err(ty::terr_in_field(@e, a.ident)) )
229 Err(ty::terr_record_fields(
236 fn args(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
237 self.contratys(a, b).and_then(|t| Ok(t))
240 fn sigils(&self, p1: ast::Sigil, p2: ast::Sigil) -> cres<ast::Sigil> {
244 Err(ty::terr_sigil_mismatch(expected_found(self, p1, p2)))
248 fn purities(&self, a: Purity, b: Purity) -> cres<Purity>;
250 fn abis(&self, a: AbiSet, b: AbiSet) -> cres<AbiSet> {
254 Err(ty::terr_abi_mismatch(expected_found(self, a, b)))
258 fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<Onceness>;
259 fn bounds(&self, a: BuiltinBounds, b: BuiltinBounds) -> cres<BuiltinBounds>;
260 fn contraregions(&self, a: ty::Region, b: ty::Region)
262 fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region>;
265 vk: ty::terr_vstore_kind,
268 -> cres<ty::vstore> {
269 debug!("{}.vstores(a={:?}, b={:?})", self.tag(), a, b);
272 (ty::vstore_slice(a_r), ty::vstore_slice(b_r)) => {
273 self.contraregions(a_r, b_r).and_then(|r| {
274 Ok(ty::vstore_slice(r))
283 Err(ty::terr_vstores_differ(vk, expected_found(self, a, b)))
288 fn trait_stores(&self,
289 vk: ty::terr_vstore_kind,
292 -> cres<ty::TraitStore> {
293 debug!("{}.trait_stores(a={:?}, b={:?})", self.tag(), a, b);
296 (ty::RegionTraitStore(a_r), ty::RegionTraitStore(b_r)) => {
297 self.contraregions(a_r, b_r).and_then(|r| {
298 Ok(ty::RegionTraitStore(r))
307 Err(ty::terr_trait_stores_differ(vk, expected_found(self, a, b)))
316 -> cres<ty::TraitRef> {
317 // Different traits cannot be related
319 // - NOTE in the future, expand out subtraits!
321 if a.def_id != b.def_id {
323 expected_found(self, a.def_id, b.def_id)))
325 let substs = if_ok!(self.substs(a.def_id, &a.substs, &b.substs));
326 Ok(ty::TraitRef { def_id: a.def_id,
332 pub struct CombineFields<'a> {
333 infcx: &'a InferCtxt,
338 pub fn expected_found<C:Combine,T>(
339 this: &C, a: T, b: T) -> ty::expected_found<T> {
340 if this.a_is_expected() {
341 ty::expected_found {expected: a, found: b}
343 ty::expected_found {expected: b, found: a}
347 pub fn eq_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> ures {
348 let suber = this.sub();
349 this.infcx().try(|| {
350 suber.tys(a, b).and_then(|_ok| suber.contratys(a, b)).to_ures()
354 pub fn eq_regions<C:Combine>(this: &C, a: ty::Region, b: ty::Region)
356 debug!("eq_regions({}, {})",
357 a.repr(this.infcx().tcx),
358 b.repr(this.infcx().tcx));
359 let sub = this.sub();
361 this.infcx().try(|| {
362 sub.regions(a, b).and_then(|_r| sub.contraregions(a, b))
364 // substitute a better error, but use the regions
365 // found in the original error
367 ty::terr_regions_does_not_outlive(a1, b1) =>
368 Err(ty::terr_regions_not_same(a1, b1)),
375 pub fn eq_opt_regions<C:Combine>(
377 a: Option<ty::Region>,
378 b: Option<ty::Region>) -> cres<Option<ty::Region>> {
381 (None, None) => Ok(None),
382 (Some(a), Some(b)) => eq_regions(this, a, b).then(|| Ok(Some(a))),
384 // If these two substitutions are for the same type (and
385 // they should be), then the type should either
386 // consistently have a region parameter or not have a
388 this.infcx().tcx.sess.bug(
389 format!("substitution a had opt_region {} and \
390 b had opt_region {}",
391 a.inf_str(this.infcx()),
392 b.inf_str(this.infcx())));
397 pub fn super_fn_sigs<C:Combine>(this: &C, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
399 fn argvecs<C:Combine>(this: &C, a_args: &[ty::t], b_args: &[ty::t]) -> cres<Vec<ty::t> > {
400 if a_args.len() == b_args.len() {
401 result::collect(a_args.iter().zip(b_args.iter())
402 .map(|(a, b)| this.args(*a, *b)))
404 Err(ty::terr_arg_count)
408 if a.variadic != b.variadic {
409 return Err(ty::terr_variadic_mismatch(expected_found(this, a.variadic, b.variadic)));
412 let inputs = if_ok!(argvecs(this, a.inputs, b.inputs));
413 let output = if_ok!(this.tys(a.output, b.output));
414 Ok(FnSig {binder_id: a.binder_id,
417 variadic: a.variadic})
420 pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
421 let tcx = this.infcx().tcx;
422 let a_sty = &ty::get(a).sty;
423 let b_sty = &ty::get(b).sty;
424 debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty);
425 return match (a_sty, b_sty) {
426 // The "subtype" ought to be handling cases involving bot or var:
429 (&ty::ty_infer(TyVar(_)), _) |
430 (_, &ty::ty_infer(TyVar(_))) => {
432 format!("{}: bot and var types should have been handled ({},{})",
434 a.inf_str(this.infcx()),
435 b.inf_str(this.infcx())));
438 // Relate integral variables to other types
439 (&ty::ty_infer(IntVar(a_id)), &ty::ty_infer(IntVar(b_id))) => {
440 if_ok!(this.infcx().simple_vars(this.a_is_expected(),
444 (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => {
445 unify_integral_variable(this, this.a_is_expected(),
448 (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => {
449 unify_integral_variable(this, !this.a_is_expected(),
452 (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => {
453 unify_integral_variable(this, this.a_is_expected(),
456 (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => {
457 unify_integral_variable(this, !this.a_is_expected(),
461 // Relate floating-point variables to other types
462 (&ty::ty_infer(FloatVar(a_id)), &ty::ty_infer(FloatVar(b_id))) => {
463 if_ok!(this.infcx().simple_vars(this.a_is_expected(),
467 (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => {
468 unify_float_variable(this, this.a_is_expected(), v_id, v)
470 (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => {
471 unify_float_variable(this, !this.a_is_expected(), v_id, v)
477 (&ty::ty_int(_), _) |
478 (&ty::ty_uint(_), _) |
479 (&ty::ty_float(_), _) => {
480 if ty::get(a).sty == ty::get(b).sty {
483 Err(ty::terr_sorts(expected_found(this, a, b)))
487 (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if a_p.idx == b_p.idx => {
491 (&ty::ty_enum(a_id, ref a_substs),
492 &ty::ty_enum(b_id, ref b_substs))
494 let substs = if_ok!(this.substs(a_id,
497 Ok(ty::mk_enum(tcx, a_id, substs))
500 (&ty::ty_trait(a_id, ref a_substs, a_store, a_mutbl, a_bounds),
501 &ty::ty_trait(b_id, ref b_substs, b_store, b_mutbl, b_bounds))
502 if a_id == b_id && a_mutbl == b_mutbl => {
503 debug!("Trying to match traits {:?} and {:?}", a, b);
504 let substs = if_ok!(this.substs(a_id, a_substs, b_substs));
505 let s = if_ok!(this.trait_stores(ty::terr_trait, a_store, b_store));
506 let bounds = if_ok!(this.bounds(a_bounds, b_bounds));
515 (&ty::ty_struct(a_id, ref a_substs), &ty::ty_struct(b_id, ref b_substs))
517 let substs = if_ok!(this.substs(a_id, a_substs, b_substs));
518 Ok(ty::mk_struct(tcx, a_id, substs))
521 (&ty::ty_box(a_inner), &ty::ty_box(b_inner)) => {
522 this.tys(a_inner, b_inner).and_then(|typ| Ok(ty::mk_box(tcx, typ)))
525 (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) => {
526 this.tys(a_inner, b_inner).and_then(|typ| Ok(ty::mk_uniq(tcx, typ)))
529 (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) => {
530 this.mts(a_mt, b_mt).and_then(|mt| Ok(ty::mk_ptr(tcx, mt)))
533 (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) => {
534 let r = if_ok!(this.contraregions(a_r, b_r));
535 let mt = if_ok!(this.mts(a_mt, b_mt));
536 Ok(ty::mk_rptr(tcx, r, mt))
539 (&ty::ty_vec(ref a_mt, vs_a), &ty::ty_vec(ref b_mt, vs_b)) => {
540 this.mts(a_mt, b_mt).and_then(|mt| {
541 this.vstores(ty::terr_vec, vs_a, vs_b).and_then(|vs| {
542 Ok(ty::mk_vec(tcx, mt, vs))
547 (&ty::ty_str(vs_a), &ty::ty_str(vs_b)) => {
548 let vs = if_ok!(this.vstores(ty::terr_str, vs_a, vs_b));
549 Ok(ty::mk_str(tcx,vs))
552 (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => {
553 if as_.len() == bs.len() {
554 result::collect(as_.iter().zip(bs.iter())
555 .map(|(a, b)| this.tys(*a, *b)))
556 .and_then(|ts| Ok(ty::mk_tup(tcx, ts)) )
558 Err(ty::terr_tuple_size(
559 expected_found(this, as_.len(), bs.len())))
563 (&ty::ty_bare_fn(ref a_fty), &ty::ty_bare_fn(ref b_fty)) => {
564 this.bare_fn_tys(a_fty, b_fty).and_then(|fty| {
565 Ok(ty::mk_bare_fn(tcx, fty))
569 (&ty::ty_closure(ref a_fty), &ty::ty_closure(ref b_fty)) => {
570 this.closure_tys(a_fty, b_fty).and_then(|fty| {
571 Ok(ty::mk_closure(tcx, fty))
575 _ => Err(ty::terr_sorts(expected_found(this, a, b)))
578 fn unify_integral_variable<C:Combine>(
580 vid_is_expected: bool,
582 val: ty::IntVarValue) -> cres<ty::t>
584 if_ok!(this.infcx().simple_var_t(vid_is_expected, vid, val));
586 IntType(v) => Ok(ty::mk_mach_int(v)),
587 UintType(v) => Ok(ty::mk_mach_uint(v))
591 fn unify_float_variable<C:Combine>(
593 vid_is_expected: bool,
595 val: ast::FloatTy) -> cres<ty::t>
597 if_ok!(this.infcx().simple_var_t(vid_is_expected, vid, val));
598 Ok(ty::mk_mach_float(val))