]> git.lizzy.rs Git - rust.git/blob - src/librustc/middle/typeck/infer/combine.rs
cc898ab9c66926fef84d69a6e4ac594c2b45d666
[rust.git] / src / librustc / middle / typeck / infer / combine.rs
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.
4 //
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.
10
11 // ______________________________________________________________________
12 // Type combining
13 //
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`
20 // trait.
21 //
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
25 // of most routines).
26 //
27 // The differences are:
28 //
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.
34 //
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.
38 //
39 // Contravariance
40 //
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
47 // now.
48
49
50 use middle::subst;
51 use middle::subst::Substs;
52 use middle::ty::{FloatVar, FnSig, IntVar, TyVar};
53 use middle::ty::{IntType, UintType};
54 use middle::ty::{BuiltinBounds};
55 use middle::ty;
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;
66
67 use std::result;
68
69 use syntax::ast::{Onceness, FnStyle};
70 use syntax::ast;
71 use syntax::abi;
72
73 pub trait Combine {
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;
78
79     fn sub<'a>(&'a self) -> Sub<'a>;
80     fn lub<'a>(&'a self) -> Lub<'a>;
81     fn glb<'a>(&'a self) -> Glb<'a>;
82
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>;
86
87     fn tps(&self,
88            space: subst::ParamSpace,
89            as_: &[ty::t],
90            bs: &[ty::t])
91            -> cres<Vec<ty::t>>
92     {
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.
98
99         if as_.len() != bs.len() {
100             return Err(ty::terr_ty_param_size(expected_found(self,
101                                                              as_.len(),
102                                                              bs.len())));
103         }
104
105         match space {
106             subst::SelfSpace => {
107                 result::fold(as_
108                              .iter()
109                              .zip(bs.iter())
110                              .map(|(a, b)| self.contratys(*a, *b)),
111                              Vec::new(),
112                              |mut v, a| { v.push(a); v })
113             }
114
115             subst::TypeSpace | subst::FnSpace => {
116                 try!(result::fold_(as_
117                                   .iter()
118                                   .zip(bs.iter())
119                                   .map(|(a, b)| eq_tys(self, *a, *b))));
120                 Ok(Vec::from_slice(as_))
121             }
122         }
123     }
124
125     fn substs(&self,
126               item_def_id: ast::DefId,
127               a_subst: &subst::Substs,
128               b_subst: &subst::Substs)
129               -> cres<subst::Substs>
130     {
131         let variances = ty::item_variances(self.infcx().tcx, item_def_id);
132         let mut substs = subst::Substs::empty();
133
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,
138                                       a_tps.as_slice(),
139                                       b_tps.as_slice()));
140
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,
145                                                       item_def_id,
146                                                       r_variances,
147                                                       a_regions,
148                                                       b_regions));
149
150             *substs.types.get_mut_vec(space) = tps;
151             *substs.mut_regions().get_mut_vec(space) = regions;
152         }
153
154         return Ok(substs);
155
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>>
162         {
163             let tcx = this.infcx().tcx;
164             let num_region_params = variances.len();
165
166             debug!("relate_region_params(\
167                    item_def_id={}, \
168                    a_rs={}, \
169                    b_rs={},
170                    variances={})",
171                    item_def_id.repr(tcx),
172                    a_rs.repr(tcx),
173                    b_rs.repr(tcx),
174                    variances.repr(tcx));
175
176             assert_eq!(num_region_params, a_rs.len());
177             assert_eq!(num_region_params, b_rs.len());
178             let mut rs = vec!();
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 {
184                     ty::Invariant => {
185                         eq_regions(this, a_r, b_r)
186                             .and_then(|()| Ok(a_r))
187                     }
188                     ty::Covariant => this.regions(a_r, b_r),
189                     ty::Contravariant => this.contraregions(a_r, b_r),
190                     ty::Bivariant => Ok(a_r),
191                 };
192                 rs.push(if_ok!(r));
193             }
194             Ok(rs)
195         }
196     }
197
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,
204                 abi: abi,
205                 sig: sig})
206     }
207
208     fn closure_tys(&self, a: &ty::ClosureTy,
209                    b: &ty::ClosureTy) -> cres<ty::ClosureTy> {
210
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)
216             }
217
218             _ if a.store == b.store => {
219                 a.store
220             }
221
222             _ => {
223                 return Err(ty::terr_sigil_mismatch(expected_found(self, a.store, b.store)))
224             }
225         };
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));
230         Ok(ty::ClosureTy {
231             fn_style: fn_style,
232             onceness: onceness,
233             store: store,
234             bounds: bounds,
235             sig: sig
236         })
237     }
238
239     fn fn_sigs(&self, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig>;
240
241     fn args(&self, a: ty::t, b: ty::t) -> cres<ty::t> {
242         self.contratys(a, b).and_then(|t| Ok(t))
243     }
244
245     fn fn_styles(&self, a: FnStyle, b: FnStyle) -> cres<FnStyle>;
246
247     fn abi(&self, a: abi::Abi, b: abi::Abi) -> cres<abi::Abi> {
248         if a == b {
249             Ok(a)
250         } else {
251             Err(ty::terr_abi_mismatch(expected_found(self, a, b)))
252         }
253     }
254
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)
258                   -> cres<ty::Region>;
259     fn regions(&self, a: ty::Region, b: ty::Region) -> cres<ty::Region>;
260
261     fn trait_stores(&self,
262                     vk: ty::terr_vstore_kind,
263                     a: ty::TraitStore,
264                     b: ty::TraitStore)
265                     -> cres<ty::TraitStore> {
266         debug!("{}.trait_stores(a={:?}, b={:?})", self.tag(), a, b);
267
268         match (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))
273                 })
274             }
275
276             _ if a == b => {
277                 Ok(a)
278             }
279
280             _ => {
281                 Err(ty::terr_trait_stores_differ(vk, expected_found(self, a, b)))
282             }
283         }
284
285     }
286
287     fn trait_refs(&self,
288                   a: &ty::TraitRef,
289                   b: &ty::TraitRef)
290                   -> cres<ty::TraitRef> {
291         // Different traits cannot be related
292
293         // - NOTE in the future, expand out subtraits!
294
295         if a.def_id != b.def_id {
296             Err(ty::terr_traits(
297                                 expected_found(self, a.def_id, b.def_id)))
298         } else {
299             let substs = if_ok!(self.substs(a.def_id, &a.substs, &b.substs));
300             Ok(ty::TraitRef { def_id: a.def_id,
301                               substs: substs })
302         }
303     }
304 }
305
306 #[deriving(Clone)]
307 pub struct CombineFields<'a> {
308     pub infcx: &'a InferCtxt<'a>,
309     pub a_is_expected: bool,
310     pub trace: TypeTrace,
311 }
312
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}
317     } else {
318         ty::expected_found {expected: b, found: a}
319     }
320 }
321
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()
326     })
327 }
328
329 pub fn eq_regions<C:Combine>(this: &C, a: ty::Region, b: ty::Region)
330                           -> ures {
331     debug!("eq_regions({}, {})",
332             a.repr(this.infcx().tcx),
333             b.repr(this.infcx().tcx));
334     let sub = this.sub();
335     indent(|| {
336         this.infcx().try(|| {
337             sub.regions(a, b).and_then(|_r| sub.contraregions(a, b))
338         }).or_else(|e| {
339             // substitute a better error, but use the regions
340             // found in the original error
341             match e {
342               ty::terr_regions_does_not_outlive(a1, b1) =>
343                 Err(ty::terr_regions_not_same(a1, b1)),
344               _ => Err(e)
345             }
346         }).to_ures()
347     })
348 }
349
350 pub fn super_fn_sigs<C:Combine>(this: &C, a: &ty::FnSig, b: &ty::FnSig) -> cres<ty::FnSig> {
351
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)))
356         } else {
357             Err(ty::terr_arg_count)
358         }
359     }
360
361     if a.variadic != b.variadic {
362         return Err(ty::terr_variadic_mismatch(expected_found(this, a.variadic, b.variadic)));
363     }
364
365     let inputs = if_ok!(argvecs(this,
366                                 a.inputs.as_slice(),
367                                 b.inputs.as_slice()));
368     let output = if_ok!(this.tys(a.output, b.output));
369     Ok(FnSig {binder_id: a.binder_id,
370               inputs: inputs,
371               output: output,
372               variadic: a.variadic})
373 }
374
375 pub fn super_tys<C:Combine>(this: &C, a: ty::t, b: ty::t) -> cres<ty::t> {
376
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
380     // check.
381     fn check_ptr_to_unsized<C:Combine>(this: &C,
382                                        a: ty::t,
383                                        b: ty::t,
384                                        a_inner: ty::t,
385                                        b_inner: ty::t,
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))),
395             _ => Ok(result),
396         }
397     }
398
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:
405       (&ty::ty_bot, _) |
406       (_, &ty::ty_bot) |
407       (&ty::ty_infer(TyVar(_)), _) |
408       (_, &ty::ty_infer(TyVar(_))) => {
409         tcx.sess.bug(
410             format!("{}: bot and var types should have been handled ({},{})",
411                     this.tag(),
412                     a.inf_str(this.infcx()),
413                     b.inf_str(this.infcx())).as_slice());
414       }
415
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(),
419                                             a_id, b_id));
420             Ok(a)
421         }
422         (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => {
423             unify_integral_variable(this, this.a_is_expected(),
424                                     v_id, IntType(v))
425         }
426         (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => {
427             unify_integral_variable(this, !this.a_is_expected(),
428                                     v_id, IntType(v))
429         }
430         (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => {
431             unify_integral_variable(this, this.a_is_expected(),
432                                     v_id, UintType(v))
433         }
434         (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => {
435             unify_integral_variable(this, !this.a_is_expected(),
436                                     v_id, UintType(v))
437         }
438
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(),
442                                             a_id, b_id));
443             Ok(a)
444         }
445         (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => {
446             unify_float_variable(this, this.a_is_expected(), v_id, v)
447         }
448         (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => {
449             unify_float_variable(this, !this.a_is_expected(), v_id, v)
450         }
451
452       (&ty::ty_char, _) |
453       (&ty::ty_nil, _) |
454       (&ty::ty_bool, _) |
455       (&ty::ty_int(_), _) |
456       (&ty::ty_uint(_), _) |
457       (&ty::ty_float(_), _) => {
458         if ty::get(a).sty == ty::get(b).sty {
459             Ok(a)
460         } else {
461             Err(ty::terr_sorts(expected_found(this, a, b)))
462         }
463       }
464
465       (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if a_p.idx == b_p.idx => {
466         Ok(a)
467       }
468
469       (&ty::ty_enum(a_id, ref a_substs),
470        &ty::ty_enum(b_id, ref b_substs))
471       if a_id == b_id => {
472           let substs = if_ok!(this.substs(a_id,
473                                           a_substs,
474                                           b_substs));
475           Ok(ty::mk_enum(tcx, a_id, substs))
476       }
477
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));
484           Ok(ty::mk_trait(tcx,
485                           a_.def_id,
486                           substs.clone(),
487                           bounds))
488       }
489
490       (&ty::ty_struct(a_id, ref a_substs), &ty::ty_struct(b_id, ref b_substs))
491       if a_id == b_id => {
492             let substs = if_ok!(this.substs(a_id, a_substs, b_substs));
493             Ok(ty::mk_struct(tcx, a_id, substs))
494       }
495
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)))
498       }
499
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))
503       }
504
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))
508       }
509
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 }
520                 }
521                 _ => if_ok!(this.mts(a_mt, b_mt))
522             };
523             check_ptr_to_unsized(this, a, b, a_mt.ty, b_mt.ty, ty::mk_rptr(tcx, r, mt))
524       }
525
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| {
528             if sz_a == sz_b {
529                 Ok(ty::mk_vec(tcx, mt, sz_a))
530             } else {
531                 Err(ty::terr_sorts(expected_found(this, a, b)))
532             }
533         })
534       }
535
536       (&ty::ty_str, &ty::ty_str) => {
537             Ok(ty::mk_str(tcx))
538       }
539
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)) )
545         } else {
546             Err(ty::terr_tuple_size(
547                 expected_found(this, as_.len(), bs.len())))
548         }
549       }
550
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))
554         })
555       }
556
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))
560         })
561       }
562
563       _ => Err(ty::terr_sorts(expected_found(this, a, b)))
564     };
565
566     fn unify_integral_variable<C:Combine>(
567         this: &C,
568         vid_is_expected: bool,
569         vid: ty::IntVid,
570         val: ty::IntVarValue) -> cres<ty::t>
571     {
572         if_ok!(this.infcx().simple_var_t(vid_is_expected, vid, val));
573         match val {
574             IntType(v) => Ok(ty::mk_mach_int(v)),
575             UintType(v) => Ok(ty::mk_mach_uint(v))
576         }
577     }
578
579     fn unify_float_variable<C:Combine>(
580         this: &C,
581         vid_is_expected: bool,
582         vid: ty::FloatVid,
583         val: ast::FloatTy) -> cres<ty::t>
584     {
585         if_ok!(this.infcx().simple_var_t(vid_is_expected, vid, val));
586         Ok(ty::mk_mach_float(val))
587     }
588 }