]>
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 | ||
35 | use super::equate::Equate; | |
36 | use super::glb::Glb; | |
37 | use super::lub::Lub; | |
38 | use super::sub::Sub; | |
39 | use super::unify::InferCtxtMethodsForSimplyUnifiableTypes; | |
40 | use super::{InferCtxt, cres}; | |
41 | use super::{MiscVariable, TypeTrace}; | |
42 | use super::type_variable::{RelationDir, EqTo, SubtypeOf, SupertypeOf}; | |
43 | ||
44 | use middle::subst; | |
45 | use middle::subst::{ErasedRegions, NonerasedRegions, Substs}; | |
46 | use middle::ty::{FloatVar, FnSig, IntVar, TyVar}; | |
47 | use middle::ty::{IntType, UintType}; | |
48 | use middle::ty::{BuiltinBounds}; | |
49 | use middle::ty::{self, Ty}; | |
50 | use middle::ty_fold; | |
51 | use middle::ty_fold::{TypeFoldable}; | |
52 | use util::ppaux::Repr; | |
53 | ||
54 | use std::rc::Rc; | |
55 | use syntax::ast::{Onceness, Unsafety}; | |
56 | use syntax::ast; | |
57 | use syntax::abi; | |
58 | use syntax::codemap::Span; | |
59 | ||
60 | pub trait Combine<'tcx> : Sized { | |
61 | fn infcx<'a>(&'a self) -> &'a InferCtxt<'a, 'tcx>; | |
62 | fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> { self.infcx().tcx } | |
63 | fn tag(&self) -> String; | |
64 | fn a_is_expected(&self) -> bool; | |
65 | fn trace(&self) -> TypeTrace<'tcx>; | |
66 | ||
67 | fn equate<'a>(&'a self) -> Equate<'a, 'tcx>; | |
68 | fn sub<'a>(&'a self) -> Sub<'a, 'tcx>; | |
69 | fn lub<'a>(&'a self) -> Lub<'a, 'tcx>; | |
70 | fn glb<'a>(&'a self) -> Glb<'a, 'tcx>; | |
71 | ||
72 | fn mts(&self, a: &ty::mt<'tcx>, b: &ty::mt<'tcx>) -> cres<'tcx, ty::mt<'tcx>>; | |
73 | fn contratys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>>; | |
74 | fn tys(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>>; | |
75 | ||
76 | fn tps(&self, | |
77 | _: subst::ParamSpace, | |
78 | as_: &[Ty<'tcx>], | |
79 | bs: &[Ty<'tcx>]) | |
80 | -> cres<'tcx, Vec<Ty<'tcx>>> { | |
81 | // FIXME -- In general, we treat variance a bit wrong | |
82 | // here. For historical reasons, we treat tps and Self | |
83 | // as invariant. This is overly conservative. | |
84 | ||
85 | if as_.len() != bs.len() { | |
86 | return Err(ty::terr_ty_param_size(expected_found(self, | |
87 | as_.len(), | |
88 | bs.len()))); | |
89 | } | |
90 | ||
91 | try!(as_.iter().zip(bs.iter()) | |
92 | .map(|(a, b)| self.equate().tys(*a, *b)) | |
93 | .collect::<cres<Vec<Ty>>>()); | |
94 | Ok(as_.to_vec()) | |
95 | } | |
96 | ||
97 | fn substs(&self, | |
98 | item_def_id: ast::DefId, | |
99 | a_subst: &subst::Substs<'tcx>, | |
100 | b_subst: &subst::Substs<'tcx>) | |
101 | -> cres<'tcx, subst::Substs<'tcx>> | |
102 | { | |
103 | let variances = if self.infcx().tcx.variance_computed.get() { | |
104 | Some(ty::item_variances(self.infcx().tcx, item_def_id)) | |
105 | } else { | |
106 | None | |
107 | }; | |
108 | self.substs_variances(variances.as_ref().map(|v| &**v), a_subst, b_subst) | |
109 | } | |
110 | ||
111 | fn substs_variances(&self, | |
112 | variances: Option<&ty::ItemVariances>, | |
113 | a_subst: &subst::Substs<'tcx>, | |
114 | b_subst: &subst::Substs<'tcx>) | |
115 | -> cres<'tcx, subst::Substs<'tcx>> | |
116 | { | |
117 | let mut substs = subst::Substs::empty(); | |
118 | ||
119 | for &space in subst::ParamSpace::all().iter() { | |
120 | let a_tps = a_subst.types.get_slice(space); | |
121 | let b_tps = b_subst.types.get_slice(space); | |
122 | let tps = try!(self.tps(space, a_tps, b_tps)); | |
123 | substs.types.replace(space, tps); | |
124 | } | |
125 | ||
126 | match (&a_subst.regions, &b_subst.regions) { | |
127 | (&ErasedRegions, _) | (_, &ErasedRegions) => { | |
128 | substs.regions = ErasedRegions; | |
129 | } | |
130 | ||
131 | (&NonerasedRegions(ref a), &NonerasedRegions(ref b)) => { | |
132 | for &space in subst::ParamSpace::all().iter() { | |
133 | let a_regions = a.get_slice(space); | |
134 | let b_regions = b.get_slice(space); | |
135 | ||
136 | let mut invariance = Vec::new(); | |
137 | let r_variances = match variances { | |
138 | Some(variances) => { | |
139 | variances.regions.get_slice(space) | |
140 | } | |
141 | None => { | |
142 | for _ in a_regions.iter() { | |
143 | invariance.push(ty::Invariant); | |
144 | } | |
145 | &invariance[] | |
146 | } | |
147 | }; | |
148 | ||
149 | let regions = try!(relate_region_params(self, | |
150 | r_variances, | |
151 | a_regions, | |
152 | b_regions)); | |
153 | substs.mut_regions().replace(space, regions); | |
154 | } | |
155 | } | |
156 | } | |
157 | ||
158 | return Ok(substs); | |
159 | ||
160 | fn relate_region_params<'tcx, C: Combine<'tcx>>(this: &C, | |
161 | variances: &[ty::Variance], | |
162 | a_rs: &[ty::Region], | |
163 | b_rs: &[ty::Region]) | |
164 | -> cres<'tcx, Vec<ty::Region>> { | |
165 | let tcx = this.infcx().tcx; | |
166 | let num_region_params = variances.len(); | |
167 | ||
168 | debug!("relate_region_params(\ | |
169 | a_rs={}, \ | |
170 | b_rs={}, | |
171 | variances={})", | |
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[i]; | |
181 | let b_r = b_rs[i]; | |
182 | let variance = variances[i]; | |
183 | let r = match variance { | |
184 | ty::Invariant => this.equate().regions(a_r, b_r), | |
185 | ty::Covariant => this.regions(a_r, b_r), | |
186 | ty::Contravariant => this.contraregions(a_r, b_r), | |
187 | ty::Bivariant => Ok(a_r), | |
188 | }; | |
189 | rs.push(try!(r)); | |
190 | } | |
191 | Ok(rs) | |
192 | } | |
193 | } | |
194 | ||
195 | fn bare_fn_tys(&self, a: &ty::BareFnTy<'tcx>, | |
196 | b: &ty::BareFnTy<'tcx>) -> cres<'tcx, ty::BareFnTy<'tcx>> { | |
197 | let unsafety = try!(self.unsafeties(a.unsafety, b.unsafety)); | |
198 | let abi = try!(self.abi(a.abi, b.abi)); | |
199 | let sig = try!(self.binders(&a.sig, &b.sig)); | |
200 | Ok(ty::BareFnTy {unsafety: unsafety, | |
201 | abi: abi, | |
202 | sig: sig}) | |
203 | } | |
204 | ||
205 | fn closure_tys(&self, a: &ty::ClosureTy<'tcx>, | |
206 | b: &ty::ClosureTy<'tcx>) -> cres<'tcx, ty::ClosureTy<'tcx>> { | |
207 | ||
208 | let store = match (a.store, b.store) { | |
209 | (ty::RegionTraitStore(a_r, a_m), | |
210 | ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => { | |
211 | let r = try!(self.contraregions(a_r, b_r)); | |
212 | ty::RegionTraitStore(r, a_m) | |
213 | } | |
214 | ||
215 | _ if a.store == b.store => { | |
216 | a.store | |
217 | } | |
218 | ||
219 | _ => { | |
220 | return Err(ty::terr_sigil_mismatch(expected_found(self, a.store, b.store))) | |
221 | } | |
222 | }; | |
223 | let unsafety = try!(self.unsafeties(a.unsafety, b.unsafety)); | |
224 | let onceness = try!(self.oncenesses(a.onceness, b.onceness)); | |
225 | let bounds = try!(self.existential_bounds(&a.bounds, &b.bounds)); | |
226 | let sig = try!(self.binders(&a.sig, &b.sig)); | |
227 | let abi = try!(self.abi(a.abi, b.abi)); | |
228 | Ok(ty::ClosureTy { | |
229 | unsafety: unsafety, | |
230 | onceness: onceness, | |
231 | store: store, | |
232 | bounds: bounds, | |
233 | sig: sig, | |
234 | abi: abi, | |
235 | }) | |
236 | } | |
237 | ||
238 | fn fn_sigs(&self, a: &ty::FnSig<'tcx>, b: &ty::FnSig<'tcx>) -> cres<'tcx, ty::FnSig<'tcx>> { | |
239 | if a.variadic != b.variadic { | |
240 | return Err(ty::terr_variadic_mismatch(expected_found(self, a.variadic, b.variadic))); | |
241 | } | |
242 | ||
243 | let inputs = try!(argvecs(self, | |
244 | a.inputs.as_slice(), | |
245 | b.inputs.as_slice())); | |
246 | ||
247 | let output = try!(match (a.output, b.output) { | |
248 | (ty::FnConverging(a_ty), ty::FnConverging(b_ty)) => | |
249 | Ok(ty::FnConverging(try!(self.tys(a_ty, b_ty)))), | |
250 | (ty::FnDiverging, ty::FnDiverging) => | |
251 | Ok(ty::FnDiverging), | |
252 | (a, b) => | |
253 | Err(ty::terr_convergence_mismatch( | |
254 | expected_found(self, a != ty::FnDiverging, b != ty::FnDiverging))), | |
255 | }); | |
256 | ||
257 | return Ok(ty::FnSig {inputs: inputs, | |
258 | output: output, | |
259 | variadic: a.variadic}); | |
260 | ||
261 | ||
262 | fn argvecs<'tcx, C: Combine<'tcx>>(combiner: &C, | |
263 | a_args: &[Ty<'tcx>], | |
264 | b_args: &[Ty<'tcx>]) | |
265 | -> cres<'tcx, Vec<Ty<'tcx>>> | |
266 | { | |
267 | if a_args.len() == b_args.len() { | |
268 | a_args.iter().zip(b_args.iter()) | |
269 | .map(|(a, b)| combiner.args(*a, *b)).collect() | |
270 | } else { | |
271 | Err(ty::terr_arg_count) | |
272 | } | |
273 | } | |
274 | } | |
275 | ||
276 | fn args(&self, a: Ty<'tcx>, b: Ty<'tcx>) -> cres<'tcx, Ty<'tcx>> { | |
277 | self.contratys(a, b).and_then(|t| Ok(t)) | |
278 | } | |
279 | ||
280 | fn unsafeties(&self, a: Unsafety, b: Unsafety) -> cres<'tcx, Unsafety>; | |
281 | ||
282 | fn abi(&self, a: abi::Abi, b: abi::Abi) -> cres<'tcx, abi::Abi> { | |
283 | if a == b { | |
284 | Ok(a) | |
285 | } else { | |
286 | Err(ty::terr_abi_mismatch(expected_found(self, a, b))) | |
287 | } | |
288 | } | |
289 | ||
290 | fn oncenesses(&self, a: Onceness, b: Onceness) -> cres<'tcx, Onceness>; | |
291 | ||
292 | fn projection_tys(&self, | |
293 | a: &ty::ProjectionTy<'tcx>, | |
294 | b: &ty::ProjectionTy<'tcx>) | |
295 | -> cres<'tcx, ty::ProjectionTy<'tcx>> | |
296 | { | |
297 | if a.item_name != b.item_name { | |
298 | Err(ty::terr_projection_name_mismatched( | |
299 | expected_found(self, a.item_name, b.item_name))) | |
300 | } else { | |
301 | let trait_ref = try!(self.trait_refs(&*a.trait_ref, &*b.trait_ref)); | |
302 | Ok(ty::ProjectionTy { trait_ref: Rc::new(trait_ref), item_name: a.item_name }) | |
303 | } | |
304 | } | |
305 | ||
306 | fn projection_predicates(&self, | |
307 | a: &ty::ProjectionPredicate<'tcx>, | |
308 | b: &ty::ProjectionPredicate<'tcx>) | |
309 | -> cres<'tcx, ty::ProjectionPredicate<'tcx>> | |
310 | { | |
311 | let projection_ty = try!(self.projection_tys(&a.projection_ty, &b.projection_ty)); | |
312 | let ty = try!(self.tys(a.ty, b.ty)); | |
313 | Ok(ty::ProjectionPredicate { projection_ty: projection_ty, ty: ty }) | |
314 | } | |
315 | ||
316 | fn projection_bounds(&self, | |
317 | a: &Vec<ty::PolyProjectionPredicate<'tcx>>, | |
318 | b: &Vec<ty::PolyProjectionPredicate<'tcx>>) | |
319 | -> cres<'tcx, Vec<ty::PolyProjectionPredicate<'tcx>>> | |
320 | { | |
321 | // To be compatible, `a` and `b` must be for precisely the | |
322 | // same set of traits and item names. We always require that | |
323 | // projection bounds lists are sorted by trait-def-id and item-name, | |
324 | // so we can just iterate through the lists pairwise, so long as they are the | |
325 | // same length. | |
326 | if a.len() != b.len() { | |
327 | Err(ty::terr_projection_bounds_length(expected_found(self, a.len(), b.len()))) | |
328 | } else { | |
329 | a.iter() | |
330 | .zip(b.iter()) | |
331 | .map(|(a, b)| self.binders(a, b)) | |
332 | .collect() | |
333 | } | |
334 | } | |
335 | ||
336 | fn existential_bounds(&self, | |
337 | a: &ty::ExistentialBounds<'tcx>, | |
338 | b: &ty::ExistentialBounds<'tcx>) | |
339 | -> cres<'tcx, ty::ExistentialBounds<'tcx>> | |
340 | { | |
341 | let r = try!(self.contraregions(a.region_bound, b.region_bound)); | |
342 | let nb = try!(self.builtin_bounds(a.builtin_bounds, b.builtin_bounds)); | |
343 | let pb = try!(self.projection_bounds(&a.projection_bounds, &b.projection_bounds)); | |
344 | Ok(ty::ExistentialBounds { region_bound: r, | |
345 | builtin_bounds: nb, | |
346 | projection_bounds: pb }) | |
347 | } | |
348 | ||
349 | fn builtin_bounds(&self, | |
350 | a: ty::BuiltinBounds, | |
351 | b: ty::BuiltinBounds) | |
352 | -> cres<'tcx, ty::BuiltinBounds>; | |
353 | ||
354 | fn contraregions(&self, a: ty::Region, b: ty::Region) | |
355 | -> cres<'tcx, ty::Region>; | |
356 | ||
357 | fn regions(&self, a: ty::Region, b: ty::Region) -> cres<'tcx, ty::Region>; | |
358 | ||
359 | fn trait_stores(&self, | |
360 | vk: ty::terr_vstore_kind, | |
361 | a: ty::TraitStore, | |
362 | b: ty::TraitStore) | |
363 | -> cres<'tcx, ty::TraitStore> { | |
364 | debug!("{}.trait_stores(a={:?}, b={:?})", self.tag(), a, b); | |
365 | ||
366 | match (a, b) { | |
367 | (ty::RegionTraitStore(a_r, a_m), | |
368 | ty::RegionTraitStore(b_r, b_m)) if a_m == b_m => { | |
369 | self.contraregions(a_r, b_r).and_then(|r| { | |
370 | Ok(ty::RegionTraitStore(r, a_m)) | |
371 | }) | |
372 | } | |
373 | ||
374 | _ if a == b => { | |
375 | Ok(a) | |
376 | } | |
377 | ||
378 | _ => { | |
379 | Err(ty::terr_trait_stores_differ(vk, expected_found(self, a, b))) | |
380 | } | |
381 | } | |
382 | } | |
383 | ||
384 | fn trait_refs(&self, | |
385 | a: &ty::TraitRef<'tcx>, | |
386 | b: &ty::TraitRef<'tcx>) | |
387 | -> cres<'tcx, ty::TraitRef<'tcx>> | |
388 | { | |
389 | // Different traits cannot be related | |
390 | if a.def_id != b.def_id { | |
391 | Err(ty::terr_traits(expected_found(self, a.def_id, b.def_id))) | |
392 | } else { | |
393 | let substs = try!(self.substs(a.def_id, a.substs, b.substs)); | |
394 | Ok(ty::TraitRef { def_id: a.def_id, substs: self.tcx().mk_substs(substs) }) | |
395 | } | |
396 | } | |
397 | ||
398 | fn binders<T>(&self, a: &ty::Binder<T>, b: &ty::Binder<T>) -> cres<'tcx, ty::Binder<T>> | |
399 | where T : Combineable<'tcx>; | |
400 | // this must be overridden to do correctly, so as to account for higher-ranked | |
401 | // behavior | |
402 | } | |
403 | ||
404 | pub trait Combineable<'tcx> : Repr<'tcx> + TypeFoldable<'tcx> { | |
405 | fn combine<C:Combine<'tcx>>(combiner: &C, a: &Self, b: &Self) -> cres<'tcx, Self>; | |
406 | } | |
407 | ||
408 | impl<'tcx,T> Combineable<'tcx> for Rc<T> | |
409 | where T : Combineable<'tcx> | |
410 | { | |
411 | fn combine<C:Combine<'tcx>>(combiner: &C, | |
412 | a: &Rc<T>, | |
413 | b: &Rc<T>) | |
414 | -> cres<'tcx, Rc<T>> | |
415 | { | |
416 | Ok(Rc::new(try!(Combineable::combine(combiner, &**a, &**b)))) | |
417 | } | |
418 | } | |
419 | ||
420 | impl<'tcx> Combineable<'tcx> for ty::TraitRef<'tcx> { | |
421 | fn combine<C:Combine<'tcx>>(combiner: &C, | |
422 | a: &ty::TraitRef<'tcx>, | |
423 | b: &ty::TraitRef<'tcx>) | |
424 | -> cres<'tcx, ty::TraitRef<'tcx>> | |
425 | { | |
426 | combiner.trait_refs(a, b) | |
427 | } | |
428 | } | |
429 | ||
430 | impl<'tcx> Combineable<'tcx> for Ty<'tcx> { | |
431 | fn combine<C:Combine<'tcx>>(combiner: &C, | |
432 | a: &Ty<'tcx>, | |
433 | b: &Ty<'tcx>) | |
434 | -> cres<'tcx, Ty<'tcx>> | |
435 | { | |
436 | combiner.tys(*a, *b) | |
437 | } | |
438 | } | |
439 | ||
440 | impl<'tcx> Combineable<'tcx> for ty::ProjectionPredicate<'tcx> { | |
441 | fn combine<C:Combine<'tcx>>(combiner: &C, | |
442 | a: &ty::ProjectionPredicate<'tcx>, | |
443 | b: &ty::ProjectionPredicate<'tcx>) | |
444 | -> cres<'tcx, ty::ProjectionPredicate<'tcx>> | |
445 | { | |
446 | combiner.projection_predicates(a, b) | |
447 | } | |
448 | } | |
449 | ||
450 | impl<'tcx> Combineable<'tcx> for ty::FnSig<'tcx> { | |
451 | fn combine<C:Combine<'tcx>>(combiner: &C, | |
452 | a: &ty::FnSig<'tcx>, | |
453 | b: &ty::FnSig<'tcx>) | |
454 | -> cres<'tcx, ty::FnSig<'tcx>> | |
455 | { | |
456 | combiner.fn_sigs(a, b) | |
457 | } | |
458 | } | |
459 | ||
460 | #[derive(Clone)] | |
461 | pub struct CombineFields<'a, 'tcx: 'a> { | |
462 | pub infcx: &'a InferCtxt<'a, 'tcx>, | |
463 | pub a_is_expected: bool, | |
464 | pub trace: TypeTrace<'tcx>, | |
465 | } | |
466 | ||
467 | pub fn expected_found<'tcx, C: Combine<'tcx>, T>( | |
468 | this: &C, a: T, b: T) -> ty::expected_found<T> { | |
469 | if this.a_is_expected() { | |
470 | ty::expected_found {expected: a, found: b} | |
471 | } else { | |
472 | ty::expected_found {expected: b, found: a} | |
473 | } | |
474 | } | |
475 | ||
476 | pub fn super_tys<'tcx, C: Combine<'tcx>>(this: &C, | |
477 | a: Ty<'tcx>, | |
478 | b: Ty<'tcx>) | |
479 | -> cres<'tcx, Ty<'tcx>> | |
480 | { | |
481 | let tcx = this.infcx().tcx; | |
482 | let a_sty = &a.sty; | |
483 | let b_sty = &b.sty; | |
484 | debug!("super_tys: a_sty={:?} b_sty={:?}", a_sty, b_sty); | |
485 | return match (a_sty, b_sty) { | |
486 | // The "subtype" ought to be handling cases involving var: | |
487 | (&ty::ty_infer(TyVar(_)), _) | | |
488 | (_, &ty::ty_infer(TyVar(_))) => { | |
489 | tcx.sess.bug( | |
490 | &format!("{}: bot and var types should have been handled ({},{})", | |
491 | this.tag(), | |
492 | a.repr(this.infcx().tcx), | |
493 | b.repr(this.infcx().tcx))[]); | |
494 | } | |
495 | ||
496 | (&ty::ty_err, _) | (_, &ty::ty_err) => { | |
497 | Ok(tcx.types.err) | |
498 | } | |
499 | ||
500 | // Relate integral variables to other types | |
501 | (&ty::ty_infer(IntVar(a_id)), &ty::ty_infer(IntVar(b_id))) => { | |
502 | try!(this.infcx().simple_vars(this.a_is_expected(), | |
503 | a_id, b_id)); | |
504 | Ok(a) | |
505 | } | |
506 | (&ty::ty_infer(IntVar(v_id)), &ty::ty_int(v)) => { | |
507 | unify_integral_variable(this, this.a_is_expected(), | |
508 | v_id, IntType(v)) | |
509 | } | |
510 | (&ty::ty_int(v), &ty::ty_infer(IntVar(v_id))) => { | |
511 | unify_integral_variable(this, !this.a_is_expected(), | |
512 | v_id, IntType(v)) | |
513 | } | |
514 | (&ty::ty_infer(IntVar(v_id)), &ty::ty_uint(v)) => { | |
515 | unify_integral_variable(this, this.a_is_expected(), | |
516 | v_id, UintType(v)) | |
517 | } | |
518 | (&ty::ty_uint(v), &ty::ty_infer(IntVar(v_id))) => { | |
519 | unify_integral_variable(this, !this.a_is_expected(), | |
520 | v_id, UintType(v)) | |
521 | } | |
522 | ||
523 | // Relate floating-point variables to other types | |
524 | (&ty::ty_infer(FloatVar(a_id)), &ty::ty_infer(FloatVar(b_id))) => { | |
525 | try!(this.infcx().simple_vars(this.a_is_expected(), a_id, b_id)); | |
526 | Ok(a) | |
527 | } | |
528 | (&ty::ty_infer(FloatVar(v_id)), &ty::ty_float(v)) => { | |
529 | unify_float_variable(this, this.a_is_expected(), v_id, v) | |
530 | } | |
531 | (&ty::ty_float(v), &ty::ty_infer(FloatVar(v_id))) => { | |
532 | unify_float_variable(this, !this.a_is_expected(), v_id, v) | |
533 | } | |
534 | ||
535 | (&ty::ty_char, _) | | |
536 | (&ty::ty_bool, _) | | |
537 | (&ty::ty_int(_), _) | | |
538 | (&ty::ty_uint(_), _) | | |
539 | (&ty::ty_float(_), _) => { | |
540 | if a == b { | |
541 | Ok(a) | |
542 | } else { | |
543 | Err(ty::terr_sorts(expected_found(this, a, b))) | |
544 | } | |
545 | } | |
546 | ||
547 | (&ty::ty_param(ref a_p), &ty::ty_param(ref b_p)) if | |
548 | a_p.idx == b_p.idx && a_p.space == b_p.space => { | |
549 | Ok(a) | |
550 | } | |
551 | ||
552 | (&ty::ty_enum(a_id, a_substs), | |
553 | &ty::ty_enum(b_id, b_substs)) | |
554 | if a_id == b_id => { | |
555 | let substs = try!(this.substs(a_id, | |
556 | a_substs, | |
557 | b_substs)); | |
558 | Ok(ty::mk_enum(tcx, a_id, tcx.mk_substs(substs))) | |
559 | } | |
560 | ||
561 | (&ty::ty_trait(ref a_), | |
562 | &ty::ty_trait(ref b_)) => { | |
563 | debug!("Trying to match traits {:?} and {:?}", a, b); | |
564 | let principal = try!(this.binders(&a_.principal, &b_.principal)); | |
565 | let bounds = try!(this.existential_bounds(&a_.bounds, &b_.bounds)); | |
566 | Ok(ty::mk_trait(tcx, principal, bounds)) | |
567 | } | |
568 | ||
569 | (&ty::ty_struct(a_id, a_substs), &ty::ty_struct(b_id, b_substs)) | |
570 | if a_id == b_id => { | |
571 | let substs = try!(this.substs(a_id, a_substs, b_substs)); | |
572 | Ok(ty::mk_struct(tcx, a_id, tcx.mk_substs(substs))) | |
573 | } | |
574 | ||
575 | (&ty::ty_unboxed_closure(a_id, a_region, a_substs), | |
576 | &ty::ty_unboxed_closure(b_id, b_region, b_substs)) | |
577 | if a_id == b_id => { | |
578 | // All ty_unboxed_closure types with the same id represent | |
579 | // the (anonymous) type of the same closure expression. So | |
580 | // all of their regions should be equated. | |
581 | let region = try!(this.equate().regions(*a_region, *b_region)); | |
582 | let substs = try!(this.substs_variances(None, a_substs, b_substs)); | |
583 | Ok(ty::mk_unboxed_closure(tcx, a_id, tcx.mk_region(region), tcx.mk_substs(substs))) | |
584 | } | |
585 | ||
586 | (&ty::ty_uniq(a_inner), &ty::ty_uniq(b_inner)) => { | |
587 | let typ = try!(this.tys(a_inner, b_inner)); | |
588 | Ok(ty::mk_uniq(tcx, typ)) | |
589 | } | |
590 | ||
591 | (&ty::ty_ptr(ref a_mt), &ty::ty_ptr(ref b_mt)) => { | |
592 | let mt = try!(this.mts(a_mt, b_mt)); | |
593 | Ok(ty::mk_ptr(tcx, mt)) | |
594 | } | |
595 | ||
596 | (&ty::ty_rptr(a_r, ref a_mt), &ty::ty_rptr(b_r, ref b_mt)) => { | |
597 | let r = try!(this.contraregions(*a_r, *b_r)); | |
598 | // FIXME(14985) If we have mutable references to trait objects, we | |
599 | // used to use covariant subtyping. I have preserved this behaviour, | |
600 | // even though it is probably incorrect. So don't go down the usual | |
601 | // path which would require invariance. | |
602 | let mt = match (&a_mt.ty.sty, &b_mt.ty.sty) { | |
603 | (&ty::ty_trait(..), &ty::ty_trait(..)) if a_mt.mutbl == b_mt.mutbl => { | |
604 | let ty = try!(this.tys(a_mt.ty, b_mt.ty)); | |
605 | ty::mt { ty: ty, mutbl: a_mt.mutbl } | |
606 | } | |
607 | _ => try!(this.mts(a_mt, b_mt)) | |
608 | }; | |
609 | Ok(ty::mk_rptr(tcx, tcx.mk_region(r), mt)) | |
610 | } | |
611 | ||
612 | (&ty::ty_vec(a_t, Some(sz_a)), &ty::ty_vec(b_t, Some(sz_b))) => { | |
613 | this.tys(a_t, b_t).and_then(|t| { | |
614 | if sz_a == sz_b { | |
615 | Ok(ty::mk_vec(tcx, t, Some(sz_a))) | |
616 | } else { | |
617 | Err(ty::terr_fixed_array_size(expected_found(this, sz_a, sz_b))) | |
618 | } | |
619 | }) | |
620 | } | |
621 | ||
622 | (&ty::ty_vec(a_t, sz_a), &ty::ty_vec(b_t, sz_b)) => { | |
623 | this.tys(a_t, b_t).and_then(|t| { | |
624 | if sz_a == sz_b { | |
625 | Ok(ty::mk_vec(tcx, t, sz_a)) | |
626 | } else { | |
627 | Err(ty::terr_sorts(expected_found(this, a, b))) | |
628 | } | |
629 | }) | |
630 | } | |
631 | ||
632 | (&ty::ty_str, &ty::ty_str) => { | |
633 | Ok(ty::mk_str(tcx)) | |
634 | } | |
635 | ||
636 | (&ty::ty_tup(ref as_), &ty::ty_tup(ref bs)) => { | |
637 | if as_.len() == bs.len() { | |
638 | as_.iter().zip(bs.iter()) | |
639 | .map(|(a, b)| this.tys(*a, *b)) | |
640 | .collect::<Result<_, _>>() | |
641 | .map(|ts| ty::mk_tup(tcx, ts)) | |
642 | } else if as_.len() != 0 && bs.len() != 0 { | |
643 | Err(ty::terr_tuple_size( | |
644 | expected_found(this, as_.len(), bs.len()))) | |
645 | } else { | |
646 | Err(ty::terr_sorts(expected_found(this, a, b))) | |
647 | } | |
648 | } | |
649 | ||
650 | (&ty::ty_bare_fn(a_opt_def_id, a_fty), &ty::ty_bare_fn(b_opt_def_id, b_fty)) | |
651 | if a_opt_def_id == b_opt_def_id => | |
652 | { | |
653 | let fty = try!(this.bare_fn_tys(a_fty, b_fty)); | |
654 | Ok(ty::mk_bare_fn(tcx, a_opt_def_id, tcx.mk_bare_fn(fty))) | |
655 | } | |
656 | ||
657 | (&ty::ty_projection(ref a_data), &ty::ty_projection(ref b_data)) => { | |
658 | let projection_ty = try!(this.projection_tys(a_data, b_data)); | |
659 | Ok(ty::mk_projection(tcx, projection_ty.trait_ref, projection_ty.item_name)) | |
660 | } | |
661 | ||
662 | _ => Err(ty::terr_sorts(expected_found(this, a, b))) | |
663 | }; | |
664 | ||
665 | fn unify_integral_variable<'tcx, C: Combine<'tcx>>( | |
666 | this: &C, | |
667 | vid_is_expected: bool, | |
668 | vid: ty::IntVid, | |
669 | val: ty::IntVarValue) -> cres<'tcx, Ty<'tcx>> | |
670 | { | |
671 | try!(this.infcx().simple_var_t(vid_is_expected, vid, val)); | |
672 | match val { | |
673 | IntType(v) => Ok(ty::mk_mach_int(this.tcx(), v)), | |
674 | UintType(v) => Ok(ty::mk_mach_uint(this.tcx(), v)) | |
675 | } | |
676 | } | |
677 | ||
678 | fn unify_float_variable<'tcx, C: Combine<'tcx>>( | |
679 | this: &C, | |
680 | vid_is_expected: bool, | |
681 | vid: ty::FloatVid, | |
682 | val: ast::FloatTy) -> cres<'tcx, Ty<'tcx>> | |
683 | { | |
684 | try!(this.infcx().simple_var_t(vid_is_expected, vid, val)); | |
685 | Ok(ty::mk_mach_float(this.tcx(), val)) | |
686 | } | |
687 | } | |
688 | ||
689 | impl<'f, 'tcx> CombineFields<'f, 'tcx> { | |
690 | pub fn switch_expected(&self) -> CombineFields<'f, 'tcx> { | |
691 | CombineFields { | |
692 | a_is_expected: !self.a_is_expected, | |
693 | ..(*self).clone() | |
694 | } | |
695 | } | |
696 | ||
697 | fn equate(&self) -> Equate<'f, 'tcx> { | |
698 | Equate((*self).clone()) | |
699 | } | |
700 | ||
701 | fn sub(&self) -> Sub<'f, 'tcx> { | |
702 | Sub((*self).clone()) | |
703 | } | |
704 | ||
705 | pub fn instantiate(&self, | |
706 | a_ty: Ty<'tcx>, | |
707 | dir: RelationDir, | |
708 | b_vid: ty::TyVid) | |
709 | -> cres<'tcx, ()> | |
710 | { | |
711 | let tcx = self.infcx.tcx; | |
712 | let mut stack = Vec::new(); | |
713 | stack.push((a_ty, dir, b_vid)); | |
714 | loop { | |
715 | // For each turn of the loop, we extract a tuple | |
716 | // | |
717 | // (a_ty, dir, b_vid) | |
718 | // | |
719 | // to relate. Here dir is either SubtypeOf or | |
720 | // SupertypeOf. The idea is that we should ensure that | |
721 | // the type `a_ty` is a subtype or supertype (respectively) of the | |
722 | // type to which `b_vid` is bound. | |
723 | // | |
724 | // If `b_vid` has not yet been instantiated with a type | |
725 | // (which is always true on the first iteration, but not | |
726 | // necessarily true on later iterations), we will first | |
727 | // instantiate `b_vid` with a *generalized* version of | |
728 | // `a_ty`. Generalization introduces other inference | |
729 | // variables wherever subtyping could occur (at time of | |
730 | // this writing, this means replacing free regions with | |
731 | // region variables). | |
732 | let (a_ty, dir, b_vid) = match stack.pop() { | |
733 | None => break, | |
734 | Some(e) => e, | |
735 | }; | |
736 | ||
737 | debug!("instantiate(a_ty={} dir={:?} b_vid={})", | |
738 | a_ty.repr(tcx), | |
739 | dir, | |
740 | b_vid.repr(tcx)); | |
741 | ||
742 | // Check whether `vid` has been instantiated yet. If not, | |
743 | // make a generalized form of `ty` and instantiate with | |
744 | // that. | |
745 | let b_ty = self.infcx.type_variables.borrow().probe(b_vid); | |
746 | let b_ty = match b_ty { | |
747 | Some(t) => t, // ...already instantiated. | |
748 | None => { // ...not yet instantiated: | |
749 | // Generalize type if necessary. | |
750 | let generalized_ty = try!(match dir { | |
751 | EqTo => { | |
752 | self.generalize(a_ty, b_vid, false) | |
753 | } | |
754 | SupertypeOf | SubtypeOf => { | |
755 | self.generalize(a_ty, b_vid, true) | |
756 | } | |
757 | }); | |
758 | debug!("instantiate(a_ty={}, dir={:?}, \ | |
759 | b_vid={}, generalized_ty={})", | |
760 | a_ty.repr(tcx), dir, b_vid.repr(tcx), | |
761 | generalized_ty.repr(tcx)); | |
762 | self.infcx.type_variables | |
763 | .borrow_mut() | |
764 | .instantiate_and_push( | |
765 | b_vid, generalized_ty, &mut stack); | |
766 | generalized_ty | |
767 | } | |
768 | }; | |
769 | ||
770 | // The original triple was `(a_ty, dir, b_vid)` -- now we have | |
771 | // resolved `b_vid` to `b_ty`, so apply `(a_ty, dir, b_ty)`: | |
772 | // | |
773 | // FIXME(#16847): This code is non-ideal because all these subtype | |
774 | // relations wind up attributed to the same spans. We need | |
775 | // to associate causes/spans with each of the relations in | |
776 | // the stack to get this right. | |
777 | match dir { | |
778 | EqTo => { | |
779 | try!(self.equate().tys(a_ty, b_ty)); | |
780 | } | |
781 | ||
782 | SubtypeOf => { | |
783 | try!(self.sub().tys(a_ty, b_ty)); | |
784 | } | |
785 | ||
786 | SupertypeOf => { | |
787 | try!(self.sub().contratys(a_ty, b_ty)); | |
788 | } | |
789 | } | |
790 | } | |
791 | ||
792 | Ok(()) | |
793 | } | |
794 | ||
795 | /// Attempts to generalize `ty` for the type variable `for_vid`. This checks for cycle -- that | |
796 | /// is, whether the type `ty` references `for_vid`. If `make_region_vars` is true, it will also | |
797 | /// replace all regions with fresh variables. Returns `ty_err` in the case of a cycle, `Ok` | |
798 | /// otherwise. | |
799 | fn generalize(&self, | |
800 | ty: Ty<'tcx>, | |
801 | for_vid: ty::TyVid, | |
802 | make_region_vars: bool) | |
803 | -> cres<'tcx, Ty<'tcx>> | |
804 | { | |
805 | let mut generalize = Generalizer { infcx: self.infcx, | |
806 | span: self.trace.origin.span(), | |
807 | for_vid: for_vid, | |
808 | make_region_vars: make_region_vars, | |
809 | cycle_detected: false }; | |
810 | let u = ty.fold_with(&mut generalize); | |
811 | if generalize.cycle_detected { | |
812 | Err(ty::terr_cyclic_ty) | |
813 | } else { | |
814 | Ok(u) | |
815 | } | |
816 | } | |
817 | } | |
818 | ||
819 | struct Generalizer<'cx, 'tcx:'cx> { | |
820 | infcx: &'cx InferCtxt<'cx, 'tcx>, | |
821 | span: Span, | |
822 | for_vid: ty::TyVid, | |
823 | make_region_vars: bool, | |
824 | cycle_detected: bool, | |
825 | } | |
826 | ||
827 | impl<'cx, 'tcx> ty_fold::TypeFolder<'tcx> for Generalizer<'cx, 'tcx> { | |
828 | fn tcx(&self) -> &ty::ctxt<'tcx> { | |
829 | self.infcx.tcx | |
830 | } | |
831 | ||
832 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
833 | // Check to see whether the type we are genealizing references | |
834 | // `vid`. At the same time, also update any type variables to | |
835 | // the values that they are bound to. This is needed to truly | |
836 | // check for cycles, but also just makes things readable. | |
837 | // | |
838 | // (In particular, you could have something like `$0 = Box<$1>` | |
839 | // where `$1` has already been instantiated with `Box<$0>`) | |
840 | match t.sty { | |
841 | ty::ty_infer(ty::TyVar(vid)) => { | |
842 | if vid == self.for_vid { | |
843 | self.cycle_detected = true; | |
844 | self.tcx().types.err | |
845 | } else { | |
846 | match self.infcx.type_variables.borrow().probe(vid) { | |
847 | Some(u) => self.fold_ty(u), | |
848 | None => t, | |
849 | } | |
850 | } | |
851 | } | |
852 | _ => { | |
853 | ty_fold::super_fold_ty(self, t) | |
854 | } | |
855 | } | |
856 | } | |
857 | ||
858 | fn fold_region(&mut self, r: ty::Region) -> ty::Region { | |
859 | match r { | |
860 | // Never make variables for regions bound within the type itself. | |
861 | ty::ReLateBound(..) => { return r; } | |
862 | ||
863 | // Early-bound regions should really have been substituted away before | |
864 | // we get to this point. | |
865 | ty::ReEarlyBound(..) => { | |
866 | self.tcx().sess.span_bug( | |
867 | self.span, | |
868 | &format!("Encountered early bound region when generalizing: {}", | |
869 | r.repr(self.tcx()))[]); | |
870 | } | |
871 | ||
872 | // Always make a fresh region variable for skolemized regions; | |
873 | // the higher-ranked decision procedures rely on this. | |
874 | ty::ReInfer(ty::ReSkolemized(..)) => { } | |
875 | ||
876 | // For anything else, we make a region variable, unless we | |
877 | // are *equating*, in which case it's just wasteful. | |
878 | ty::ReEmpty | | |
879 | ty::ReStatic | | |
880 | ty::ReScope(..) | | |
881 | ty::ReInfer(ty::ReVar(..)) | | |
882 | ty::ReFree(..) => { | |
883 | if !self.make_region_vars { | |
884 | return r; | |
885 | } | |
886 | } | |
887 | } | |
888 | ||
889 | // FIXME: This is non-ideal because we don't give a | |
890 | // very descriptive origin for this region variable. | |
891 | self.infcx.next_region_var(MiscVariable(self.span)) | |
892 | } | |
893 | } |