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 // Resolution is the process of removing type variables and replacing
12 // them with their inferred values. Unfortunately our inference has
13 // become fairly complex and so there are a number of options to
14 // control *just how much* you want to resolve and how you want to do
15 // it.
16 //
17 // # Controlling the scope of resolution
18 //
19 // The options resolve_* determine what kinds of variables get
20 // resolved. Generally resolution starts with a top-level type
21 // variable; we will always resolve this. However, once we have
22 // resolved that variable, we may end up with a type that still
23 // contains type variables. For example, if we resolve `<T0>` we may
24 // end up with something like `[<T1>]`. If the option
25 // `resolve_nested_tvar` is passed, we will then go and recursively
26 // resolve `<T1>`.
27 //
28 // The options `resolve_rvar` controls whether we resolve region
29 // variables. The options `resolve_fvar` and `resolve_ivar` control
30 // whether we resolve floating point and integral variables,
31 // respectively.
32 //
33 // # What do if things are unconstrained
34 //
35 // Sometimes we will encounter a variable that has no constraints, and
36 // therefore cannot sensibly be mapped to any particular result. By
37 // default, we will leave such variables as is (so you will get back a
38 // variable in your result). The options force_* will cause the
39 // resolution to fail in this case instead, except for the case of
40 // integral variables, which resolve to `int` if forced.
41 //
42 // # resolve_all and force_all
43 //
44 // The options are a bit set, so you can use the *_all to resolve or
45 // force all kinds of variables (including those we may add in the
46 // future). If you want to resolve everything but one type, you are
47 // probably better off writing `resolve_all - resolve_ivar`.
48
49
50 use middle::ty::{FloatVar, FloatVid, IntVar, IntVid, RegionVid, TyVar, TyVid};
51 use middle::ty::{type_is_bot, IntType, UintType};
52 use middle::ty;
53 use middle::ty_fold;
54 use middle::typeck::infer::{Bounds, cyclic_ty, fixup_err, fres, InferCtxt};
55 use middle::typeck::infer::unresolved_ty;
56 use middle::typeck::infer::to_str::InferStr;
57 use middle::typeck::infer::unify::{Root, UnifyInferCtxtMethods};
58 use util::common::{indent, indenter};
59 use util::ppaux::ty_to_str;
60
61 use syntax::ast;
62
63 pub static resolve_nested_tvar: uint = 0b0000000001;
64 pub static resolve_rvar: uint = 0b0000000010;
65 pub static resolve_ivar: uint = 0b0000000100;
66 pub static resolve_fvar: uint = 0b0000001000;
67 pub static resolve_all: uint = 0b0000001111;
68 pub static force_tvar: uint = 0b0000100000;
69 pub static force_rvar: uint = 0b0001000000;
70 pub static force_ivar: uint = 0b0010000000;
71 pub static force_fvar: uint = 0b0100000000;
72 pub static force_all: uint = 0b0111100000;
73
74 pub static not_regions: uint = !(force_rvar | resolve_rvar);
75
76 pub static try_resolve_tvar_shallow: uint = 0;
77 pub static resolve_and_force_all_but_regions: uint =
78 (resolve_all | force_all) & not_regions;
79
80 pub struct ResolveState<'a> {
81 infcx: &'a InferCtxt<'a>,
82 modes: uint,
83 err: Option<fixup_err>,
84 v_seen: Vec<TyVid> ,
85 type_depth: uint
86 }
87
88 pub fn resolver<'a>(infcx: &'a InferCtxt, modes: uint) -> ResolveState<'a> {
89 ResolveState {
90 infcx: infcx,
91 modes: modes,
92 err: None,
93 v_seen: Vec::new(),
94 type_depth: 0
95 }
96 }
97
98 impl<'a> ty_fold::TypeFolder for ResolveState<'a> {
99 fn tcx<'a>(&'a self) -> &'a ty::ctxt {
100 self.infcx.tcx
101 }
102
103 fn fold_ty(&mut self, t: ty::t) -> ty::t {
104 self.resolve_type(t)
105 }
106
107 fn fold_region(&mut self, r: ty::Region) -> ty::Region {
108 self.resolve_region(r)
109 }
110 }
111
112 impl<'a> ResolveState<'a> {
113 pub fn should(&mut self, mode: uint) -> bool {
114 (self.modes & mode) == mode
115 }
116
117 pub fn resolve_type_chk(&mut self, typ: ty::t) -> fres<ty::t> {
118 self.err = None;
119
120 debug!("Resolving {} (modes={:x})",
121 ty_to_str(self.infcx.tcx, typ),
122 self.modes);
123
124 // n.b. This is a hokey mess because the current fold doesn't
125 // allow us to pass back errors in any useful way.
126
127 assert!(self.v_seen.is_empty());
128 let rty = indent(|| self.resolve_type(typ) );
129 assert!(self.v_seen.is_empty());
130 match self.err {
131 None => {
132 debug!("Resolved to {} + {} (modes={:x})",
133 ty_to_str(self.infcx.tcx, rty),
134 ty_to_str(self.infcx.tcx, rty),
135 self.modes);
136 return Ok(rty);
137 }
138 Some(e) => return Err(e)
139 }
140 }
141
142 pub fn resolve_region_chk(&mut self, orig: ty::Region)
143 -> fres<ty::Region> {
144 self.err = None;
145 let resolved = indent(|| self.resolve_region(orig) );
146 match self.err {
147 None => Ok(resolved),
148 Some(e) => Err(e)
149 }
150 }
151
152 pub fn resolve_type(&mut self, typ: ty::t) -> ty::t {
153 debug!("resolve_type({})", typ.inf_str(self.infcx));
154 let _i = indenter();
155
156 if !ty::type_needs_infer(typ) {
157 return typ;
158 }
159
160 if self.type_depth > 0 && !self.should(resolve_nested_tvar) {
161 return typ;
162 }
163
164 match ty::get(typ).sty {
165 ty::ty_infer(TyVar(vid)) => {
166 self.resolve_ty_var(vid)
167 }
168 ty::ty_infer(IntVar(vid)) => {
169 self.resolve_int_var(vid)
170 }
171 ty::ty_infer(FloatVar(vid)) => {
172 self.resolve_float_var(vid)
173 }
174 _ => {
175 if self.modes & resolve_all == 0 {
176 // if we are only resolving top-level type
177 // variables, and this is not a top-level type
178 // variable, then shortcircuit for efficiency
179 typ
180 } else {
181 self.type_depth += 1;
182 let result = ty_fold::super_fold_ty(self, typ);
183 self.type_depth -= 1;
184 result
185 }
186 }
187 }
188 }
189
190 pub fn resolve_region(&mut self, orig: ty::Region) -> ty::Region {
191 debug!("Resolve_region({})", orig.inf_str(self.infcx));
192 match orig {
193 ty::ReInfer(ty::ReVar(rid)) => self.resolve_region_var(rid),
194 _ => orig
195 }
196 }
197
198 pub fn resolve_region_var(&mut self, rid: RegionVid) -> ty::Region {
199 if !self.should(resolve_rvar) {
200 return ty::ReInfer(ty::ReVar(rid));
201 }
202 self.infcx.region_vars.resolve_var(rid)
203 }
204
205 pub fn resolve_ty_var(&mut self, vid: TyVid) -> ty::t {
206 if self.v_seen.contains(&vid) {
207 self.err = Some(cyclic_ty(vid));
208 return ty::mk_var(self.infcx.tcx, vid);
209 } else {
210 self.v_seen.push(vid);
211 let tcx = self.infcx.tcx;
212
213 // Nonobvious: prefer the most specific type
214 // (i.e., the lower bound) to the more general
215 // one. More general types in Rust (e.g., fn())
216 // tend to carry more restrictions or higher
217 // perf. penalties, so it pays to know more.
218
219 let nde = self.infcx.get(vid);
220 let bounds = nde.possible_types;
221
222 let t1 = match bounds {
223 Bounds { ub:_, lb:Some(t) } if !type_is_bot(t)
224 => self.resolve_type(t),
225 Bounds { ub:Some(t), lb:_ } => self.resolve_type(t),
226 Bounds { ub:_, lb:Some(t) } => self.resolve_type(t),
227 Bounds { ub:None, lb:None } => {
228 if self.should(force_tvar) {
229 self.err = Some(unresolved_ty(vid));
230 }
231 ty::mk_var(tcx, vid)
232 }
233 };
234 self.v_seen.pop().unwrap();
235 return t1;
236 }
237 }
238
239 pub fn resolve_int_var(&mut self, vid: IntVid) -> ty::t {
240 if !self.should(resolve_ivar) {
241 return ty::mk_int_var(self.infcx.tcx, vid);
242 }
243
244 let node = self.infcx.get(vid);
245 match node.possible_types {
246 Some(IntType(t)) => ty::mk_mach_int(t),
247 Some(UintType(t)) => ty::mk_mach_uint(t),
248 None => {
249 if self.should(force_ivar) {
250 // As a last resort, default to int.
251 let ty = ty::mk_int();
252 self.infcx.set(vid, Root(Some(IntType(ast::TyI)), node.rank));
253 ty
254 } else {
255 ty::mk_int_var(self.infcx.tcx, vid)
256 }
257 }
258 }
259 }
260
261 pub fn resolve_float_var(&mut self, vid: FloatVid) -> ty::t {
262 if !self.should(resolve_fvar) {
263 return ty::mk_float_var(self.infcx.tcx, vid);
264 }
265
266 let node = self.infcx.get(vid);
267 match node.possible_types {
268 Some(t) => ty::mk_mach_float(t),
269 None => {
270 if self.should(force_fvar) {
271 // As a last resort, default to f64.
272 let ty = ty::mk_f64();
273 self.infcx.set(vid, Root(Some(ast::TyF64), node.rank));
274 ty
275 } else {
276 ty::mk_float_var(self.infcx.tcx, vid)
277 }
278 }
279 }
280 }
281 }