]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 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. | |
20 | // | |
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. | |
25 | // | |
26 | // ## Contravariance | |
27 | // | |
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. | |
34 | ||
85aaf69f | 35 | use super::bivariate::Bivariate; |
1a4d82fc JJ |
36 | use super::equate::Equate; |
37 | use super::glb::Glb; | |
38 | use super::lub::Lub; | |
39 | use super::sub::Sub; | |
54a0048b | 40 | use super::InferCtxt; |
1a4d82fc | 41 | use super::{MiscVariable, TypeTrace}; |
85aaf69f | 42 | use super::type_variable::{RelationDir, BiTo, EqTo, SubtypeOf, SupertypeOf}; |
1a4d82fc | 43 | |
54a0048b SL |
44 | use ty::{IntType, UintType}; |
45 | use ty::{self, Ty, TyCtxt}; | |
46 | use ty::error::TypeError; | |
a7813a04 XL |
47 | use ty::fold::TypeFoldable; |
48 | use ty::relate::{RelateResult, TypeRelation}; | |
54a0048b | 49 | use traits::PredicateObligations; |
1a4d82fc | 50 | |
b039eaaf | 51 | use syntax::ast; |
3157f602 | 52 | use syntax_pos::Span; |
1a4d82fc | 53 | |
1a4d82fc | 54 | #[derive(Clone)] |
5bcae85e SL |
55 | pub struct CombineFields<'infcx, 'gcx: 'infcx+'tcx, 'tcx: 'infcx> { |
56 | pub infcx: &'infcx InferCtxt<'infcx, 'gcx, 'tcx>, | |
1a4d82fc | 57 | pub trace: TypeTrace<'tcx>, |
e9174d1e | 58 | pub cause: Option<ty::relate::Cause>, |
54a0048b | 59 | pub obligations: PredicateObligations<'tcx>, |
1a4d82fc JJ |
60 | } |
61 | ||
5bcae85e | 62 | impl<'infcx, 'gcx, 'tcx> InferCtxt<'infcx, 'gcx, 'tcx> { |
a7813a04 XL |
63 | pub fn super_combine_tys<R>(&self, |
64 | relation: &mut R, | |
65 | a: Ty<'tcx>, | |
66 | b: Ty<'tcx>) | |
67 | -> RelateResult<'tcx, Ty<'tcx>> | |
5bcae85e | 68 | where R: TypeRelation<'infcx, 'gcx, 'tcx> |
a7813a04 XL |
69 | { |
70 | let a_is_expected = relation.a_is_expected(); | |
1a4d82fc | 71 | |
a7813a04 XL |
72 | match (&a.sty, &b.sty) { |
73 | // Relate integral variables to other types | |
74 | (&ty::TyInfer(ty::IntVar(a_id)), &ty::TyInfer(ty::IntVar(b_id))) => { | |
75 | self.int_unification_table | |
76 | .borrow_mut() | |
77 | .unify_var_var(a_id, b_id) | |
78 | .map_err(|e| int_unification_error(a_is_expected, e))?; | |
79 | Ok(a) | |
80 | } | |
81 | (&ty::TyInfer(ty::IntVar(v_id)), &ty::TyInt(v)) => { | |
82 | self.unify_integral_variable(a_is_expected, v_id, IntType(v)) | |
83 | } | |
84 | (&ty::TyInt(v), &ty::TyInfer(ty::IntVar(v_id))) => { | |
85 | self.unify_integral_variable(!a_is_expected, v_id, IntType(v)) | |
86 | } | |
87 | (&ty::TyInfer(ty::IntVar(v_id)), &ty::TyUint(v)) => { | |
88 | self.unify_integral_variable(a_is_expected, v_id, UintType(v)) | |
89 | } | |
90 | (&ty::TyUint(v), &ty::TyInfer(ty::IntVar(v_id))) => { | |
91 | self.unify_integral_variable(!a_is_expected, v_id, UintType(v)) | |
92 | } | |
1a4d82fc | 93 | |
a7813a04 XL |
94 | // Relate floating-point variables to other types |
95 | (&ty::TyInfer(ty::FloatVar(a_id)), &ty::TyInfer(ty::FloatVar(b_id))) => { | |
96 | self.float_unification_table | |
97 | .borrow_mut() | |
98 | .unify_var_var(a_id, b_id) | |
99 | .map_err(|e| float_unification_error(relation.a_is_expected(), e))?; | |
100 | Ok(a) | |
101 | } | |
102 | (&ty::TyInfer(ty::FloatVar(v_id)), &ty::TyFloat(v)) => { | |
103 | self.unify_float_variable(a_is_expected, v_id, v) | |
104 | } | |
105 | (&ty::TyFloat(v), &ty::TyInfer(ty::FloatVar(v_id))) => { | |
106 | self.unify_float_variable(!a_is_expected, v_id, v) | |
107 | } | |
1a4d82fc | 108 | |
a7813a04 XL |
109 | // All other cases of inference are errors |
110 | (&ty::TyInfer(_), _) | | |
111 | (_, &ty::TyInfer(_)) => { | |
112 | Err(TypeError::Sorts(ty::relate::expected_found(relation, &a, &b))) | |
113 | } | |
1a4d82fc | 114 | |
1a4d82fc | 115 | |
a7813a04 XL |
116 | _ => { |
117 | ty::relate::super_relate_tys(relation, a, b) | |
118 | } | |
1a4d82fc JJ |
119 | } |
120 | } | |
121 | ||
a7813a04 XL |
122 | fn unify_integral_variable(&self, |
123 | vid_is_expected: bool, | |
124 | vid: ty::IntVid, | |
125 | val: ty::IntVarValue) | |
126 | -> RelateResult<'tcx, Ty<'tcx>> | |
127 | { | |
128 | self.int_unification_table | |
129 | .borrow_mut() | |
130 | .unify_var_value(vid, val) | |
131 | .map_err(|e| int_unification_error(vid_is_expected, e))?; | |
132 | match val { | |
133 | IntType(v) => Ok(self.tcx.mk_mach_int(v)), | |
134 | UintType(v) => Ok(self.tcx.mk_mach_uint(v)), | |
135 | } | |
1a4d82fc | 136 | } |
1a4d82fc | 137 | |
a7813a04 XL |
138 | fn unify_float_variable(&self, |
139 | vid_is_expected: bool, | |
140 | vid: ty::FloatVid, | |
141 | val: ast::FloatTy) | |
142 | -> RelateResult<'tcx, Ty<'tcx>> | |
143 | { | |
144 | self.float_unification_table | |
145 | .borrow_mut() | |
146 | .unify_var_value(vid, val) | |
147 | .map_err(|e| float_unification_error(vid_is_expected, e))?; | |
148 | Ok(self.tcx.mk_mach_float(val)) | |
149 | } | |
c34b1796 AL |
150 | } |
151 | ||
5bcae85e SL |
152 | impl<'infcx, 'gcx, 'tcx> CombineFields<'infcx, 'gcx, 'tcx> { |
153 | pub fn tcx(&self) -> TyCtxt<'infcx, 'gcx, 'tcx> { | |
c34b1796 AL |
154 | self.infcx.tcx |
155 | } | |
156 | ||
5bcae85e SL |
157 | pub fn equate<'a>(&'a mut self, a_is_expected: bool) -> Equate<'a, 'infcx, 'gcx, 'tcx> { |
158 | Equate::new(self, a_is_expected) | |
1a4d82fc JJ |
159 | } |
160 | ||
5bcae85e SL |
161 | pub fn bivariate<'a>(&'a mut self, a_is_expected: bool) -> Bivariate<'a, 'infcx, 'gcx, 'tcx> { |
162 | Bivariate::new(self, a_is_expected) | |
85aaf69f SL |
163 | } |
164 | ||
5bcae85e SL |
165 | pub fn sub<'a>(&'a mut self, a_is_expected: bool) -> Sub<'a, 'infcx, 'gcx, 'tcx> { |
166 | Sub::new(self, a_is_expected) | |
c34b1796 AL |
167 | } |
168 | ||
5bcae85e SL |
169 | pub fn lub<'a>(&'a mut self, a_is_expected: bool) -> Lub<'a, 'infcx, 'gcx, 'tcx> { |
170 | Lub::new(self, a_is_expected) | |
c34b1796 AL |
171 | } |
172 | ||
5bcae85e SL |
173 | pub fn glb<'a>(&'a mut self, a_is_expected: bool) -> Glb<'a, 'infcx, 'gcx, 'tcx> { |
174 | Glb::new(self, a_is_expected) | |
1a4d82fc JJ |
175 | } |
176 | ||
5bcae85e | 177 | pub fn instantiate(&mut self, |
1a4d82fc JJ |
178 | a_ty: Ty<'tcx>, |
179 | dir: RelationDir, | |
5bcae85e SL |
180 | b_vid: ty::TyVid, |
181 | a_is_expected: bool) | |
c34b1796 | 182 | -> RelateResult<'tcx, ()> |
1a4d82fc | 183 | { |
1a4d82fc JJ |
184 | let mut stack = Vec::new(); |
185 | stack.push((a_ty, dir, b_vid)); | |
186 | loop { | |
187 | // For each turn of the loop, we extract a tuple | |
188 | // | |
189 | // (a_ty, dir, b_vid) | |
190 | // | |
191 | // to relate. Here dir is either SubtypeOf or | |
192 | // SupertypeOf. The idea is that we should ensure that | |
193 | // the type `a_ty` is a subtype or supertype (respectively) of the | |
194 | // type to which `b_vid` is bound. | |
195 | // | |
196 | // If `b_vid` has not yet been instantiated with a type | |
197 | // (which is always true on the first iteration, but not | |
198 | // necessarily true on later iterations), we will first | |
199 | // instantiate `b_vid` with a *generalized* version of | |
200 | // `a_ty`. Generalization introduces other inference | |
201 | // variables wherever subtyping could occur (at time of | |
202 | // this writing, this means replacing free regions with | |
203 | // region variables). | |
204 | let (a_ty, dir, b_vid) = match stack.pop() { | |
205 | None => break, | |
206 | Some(e) => e, | |
207 | }; | |
54a0048b SL |
208 | // Get the actual variable that b_vid has been inferred to |
209 | let (b_vid, b_ty) = { | |
210 | let mut variables = self.infcx.type_variables.borrow_mut(); | |
211 | let b_vid = variables.root_var(b_vid); | |
212 | (b_vid, variables.probe_root(b_vid)) | |
213 | }; | |
1a4d82fc | 214 | |
62682a34 SL |
215 | debug!("instantiate(a_ty={:?} dir={:?} b_vid={:?})", |
216 | a_ty, | |
1a4d82fc | 217 | dir, |
62682a34 | 218 | b_vid); |
1a4d82fc JJ |
219 | |
220 | // Check whether `vid` has been instantiated yet. If not, | |
221 | // make a generalized form of `ty` and instantiate with | |
222 | // that. | |
1a4d82fc JJ |
223 | let b_ty = match b_ty { |
224 | Some(t) => t, // ...already instantiated. | |
225 | None => { // ...not yet instantiated: | |
226 | // Generalize type if necessary. | |
54a0048b | 227 | let generalized_ty = match dir { |
c34b1796 AL |
228 | EqTo => self.generalize(a_ty, b_vid, false), |
229 | BiTo | SupertypeOf | SubtypeOf => self.generalize(a_ty, b_vid, true), | |
54a0048b | 230 | }?; |
62682a34 SL |
231 | debug!("instantiate(a_ty={:?}, dir={:?}, \ |
232 | b_vid={:?}, generalized_ty={:?})", | |
233 | a_ty, dir, b_vid, | |
234 | generalized_ty); | |
1a4d82fc JJ |
235 | self.infcx.type_variables |
236 | .borrow_mut() | |
237 | .instantiate_and_push( | |
238 | b_vid, generalized_ty, &mut stack); | |
239 | generalized_ty | |
240 | } | |
241 | }; | |
242 | ||
243 | // The original triple was `(a_ty, dir, b_vid)` -- now we have | |
244 | // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`: | |
245 | // | |
246 | // FIXME(#16847): This code is non-ideal because all these subtype | |
247 | // relations wind up attributed to the same spans. We need | |
248 | // to associate causes/spans with each of the relations in | |
249 | // the stack to get this right. | |
54a0048b | 250 | match dir { |
5bcae85e SL |
251 | BiTo => self.bivariate(a_is_expected).relate(&a_ty, &b_ty), |
252 | EqTo => self.equate(a_is_expected).relate(&a_ty, &b_ty), | |
253 | SubtypeOf => self.sub(a_is_expected).relate(&a_ty, &b_ty), | |
254 | SupertypeOf => self.sub(a_is_expected).relate_with_variance( | |
255 | ty::Contravariant, &a_ty, &b_ty), | |
54a0048b | 256 | }?; |
1a4d82fc JJ |
257 | } |
258 | ||
259 | Ok(()) | |
260 | } | |
261 | ||
262 | /// Attempts to generalize `ty` for the type variable `for_vid`. This checks for cycle -- that | |
263 | /// is, whether the type `ty` references `for_vid`. If `make_region_vars` is true, it will also | |
62682a34 | 264 | /// replace all regions with fresh variables. Returns `TyError` in the case of a cycle, `Ok` |
1a4d82fc JJ |
265 | /// otherwise. |
266 | fn generalize(&self, | |
267 | ty: Ty<'tcx>, | |
268 | for_vid: ty::TyVid, | |
269 | make_region_vars: bool) | |
c34b1796 | 270 | -> RelateResult<'tcx, Ty<'tcx>> |
1a4d82fc | 271 | { |
c34b1796 AL |
272 | let mut generalize = Generalizer { |
273 | infcx: self.infcx, | |
274 | span: self.trace.origin.span(), | |
275 | for_vid: for_vid, | |
276 | make_region_vars: make_region_vars, | |
277 | cycle_detected: false | |
278 | }; | |
1a4d82fc JJ |
279 | let u = ty.fold_with(&mut generalize); |
280 | if generalize.cycle_detected { | |
c1a9b12d | 281 | Err(TypeError::CyclicTy) |
1a4d82fc JJ |
282 | } else { |
283 | Ok(u) | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
a7813a04 XL |
288 | struct Generalizer<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> { |
289 | infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, | |
1a4d82fc JJ |
290 | span: Span, |
291 | for_vid: ty::TyVid, | |
292 | make_region_vars: bool, | |
293 | cycle_detected: bool, | |
294 | } | |
295 | ||
a7813a04 XL |
296 | impl<'cx, 'gcx, 'tcx> ty::fold::TypeFolder<'gcx, 'tcx> for Generalizer<'cx, 'gcx, 'tcx> { |
297 | fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx> { | |
1a4d82fc JJ |
298 | self.infcx.tcx |
299 | } | |
300 | ||
301 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
302 | // Check to see whether the type we are genealizing references | |
303 | // `vid`. At the same time, also update any type variables to | |
304 | // the values that they are bound to. This is needed to truly | |
305 | // check for cycles, but also just makes things readable. | |
306 | // | |
307 | // (In particular, you could have something like `$0 = Box<$1>` | |
308 | // where `$1` has already been instantiated with `Box<$0>`) | |
309 | match t.sty { | |
62682a34 | 310 | ty::TyInfer(ty::TyVar(vid)) => { |
54a0048b SL |
311 | let mut variables = self.infcx.type_variables.borrow_mut(); |
312 | let vid = variables.root_var(vid); | |
1a4d82fc JJ |
313 | if vid == self.for_vid { |
314 | self.cycle_detected = true; | |
315 | self.tcx().types.err | |
316 | } else { | |
54a0048b SL |
317 | match variables.probe_root(vid) { |
318 | Some(u) => { | |
319 | drop(variables); | |
320 | self.fold_ty(u) | |
321 | } | |
1a4d82fc JJ |
322 | None => t, |
323 | } | |
324 | } | |
325 | } | |
326 | _ => { | |
9cc50fc6 | 327 | t.super_fold_with(self) |
1a4d82fc JJ |
328 | } |
329 | } | |
330 | } | |
331 | ||
332 | fn fold_region(&mut self, r: ty::Region) -> ty::Region { | |
333 | match r { | |
3157f602 XL |
334 | // Never make variables for regions bound within the type itself, |
335 | // nor for erased regions. | |
336 | ty::ReLateBound(..) | | |
337 | ty::ReErased => { return r; } | |
1a4d82fc JJ |
338 | |
339 | // Early-bound regions should really have been substituted away before | |
340 | // we get to this point. | |
341 | ty::ReEarlyBound(..) => { | |
54a0048b | 342 | span_bug!( |
1a4d82fc | 343 | self.span, |
54a0048b SL |
344 | "Encountered early bound region when generalizing: {:?}", |
345 | r); | |
1a4d82fc JJ |
346 | } |
347 | ||
348 | // Always make a fresh region variable for skolemized regions; | |
349 | // the higher-ranked decision procedures rely on this. | |
e9174d1e | 350 | ty::ReSkolemized(..) => { } |
1a4d82fc JJ |
351 | |
352 | // For anything else, we make a region variable, unless we | |
353 | // are *equating*, in which case it's just wasteful. | |
354 | ty::ReEmpty | | |
355 | ty::ReStatic | | |
356 | ty::ReScope(..) | | |
e9174d1e | 357 | ty::ReVar(..) | |
1a4d82fc JJ |
358 | ty::ReFree(..) => { |
359 | if !self.make_region_vars { | |
360 | return r; | |
361 | } | |
362 | } | |
363 | } | |
364 | ||
365 | // FIXME: This is non-ideal because we don't give a | |
366 | // very descriptive origin for this region variable. | |
367 | self.infcx.next_region_var(MiscVariable(self.span)) | |
368 | } | |
369 | } | |
c34b1796 AL |
370 | |
371 | pub trait RelateResultCompare<'tcx, T> { | |
372 | fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> where | |
e9174d1e | 373 | F: FnOnce() -> TypeError<'tcx>; |
c34b1796 AL |
374 | } |
375 | ||
376 | impl<'tcx, T:Clone + PartialEq> RelateResultCompare<'tcx, T> for RelateResult<'tcx, T> { | |
377 | fn compare<F>(&self, t: T, f: F) -> RelateResult<'tcx, T> where | |
e9174d1e | 378 | F: FnOnce() -> TypeError<'tcx>, |
c34b1796 AL |
379 | { |
380 | self.clone().and_then(|s| { | |
381 | if s == t { | |
382 | self.clone() | |
383 | } else { | |
384 | Err(f()) | |
385 | } | |
386 | }) | |
387 | } | |
388 | } | |
389 | ||
390 | fn int_unification_error<'tcx>(a_is_expected: bool, v: (ty::IntVarValue, ty::IntVarValue)) | |
e9174d1e | 391 | -> TypeError<'tcx> |
c34b1796 AL |
392 | { |
393 | let (a, b) = v; | |
e9174d1e | 394 | TypeError::IntMismatch(ty::relate::expected_found_bool(a_is_expected, &a, &b)) |
c34b1796 AL |
395 | } |
396 | ||
397 | fn float_unification_error<'tcx>(a_is_expected: bool, | |
b039eaaf | 398 | v: (ast::FloatTy, ast::FloatTy)) |
e9174d1e | 399 | -> TypeError<'tcx> |
c34b1796 AL |
400 | { |
401 | let (a, b) = v; | |
e9174d1e | 402 | TypeError::FloatMismatch(ty::relate::expected_found_bool(a_is_expected, &a, &b)) |
c34b1796 | 403 | } |