]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2014 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 | //! Helper routines for higher-ranked things. See the `doc` module at | |
12 | //! the end of the file for details. | |
13 | ||
c34b1796 AL |
14 | use super::{CombinedSnapshot, InferCtxt, HigherRankedType, SkolemizationMap}; |
15 | use super::combine::CombineFields; | |
1a4d82fc | 16 | |
9cc50fc6 | 17 | use middle::ty::{self, Binder, TypeFoldable}; |
e9174d1e | 18 | use middle::ty::error::TypeError; |
e9174d1e | 19 | use middle::ty::relate::{Relate, RelateResult, TypeRelation}; |
1a4d82fc JJ |
20 | use syntax::codemap::Span; |
21 | use util::nodemap::{FnvHashMap, FnvHashSet}; | |
1a4d82fc | 22 | |
c34b1796 AL |
23 | pub trait HigherRankedRelations<'a,'tcx> { |
24 | fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>> | |
25 | where T: Relate<'a,'tcx>; | |
1a4d82fc | 26 | |
c34b1796 AL |
27 | fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>> |
28 | where T: Relate<'a,'tcx>; | |
1a4d82fc | 29 | |
c34b1796 AL |
30 | fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>> |
31 | where T: Relate<'a,'tcx>; | |
1a4d82fc JJ |
32 | } |
33 | ||
85aaf69f | 34 | trait InferCtxtExt { |
1a4d82fc JJ |
35 | fn tainted_regions(&self, snapshot: &CombinedSnapshot, r: ty::Region) -> Vec<ty::Region>; |
36 | ||
37 | fn region_vars_confined_to_snapshot(&self, | |
38 | snapshot: &CombinedSnapshot) | |
39 | -> Vec<ty::RegionVid>; | |
40 | } | |
41 | ||
c34b1796 | 42 | impl<'a,'tcx> HigherRankedRelations<'a,'tcx> for CombineFields<'a,'tcx> { |
1a4d82fc | 43 | fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>) |
c34b1796 AL |
44 | -> RelateResult<'tcx, Binder<T>> |
45 | where T: Relate<'a,'tcx> | |
1a4d82fc | 46 | { |
62682a34 SL |
47 | debug!("higher_ranked_sub(a={:?}, b={:?})", |
48 | a, b); | |
1a4d82fc JJ |
49 | |
50 | // Rather than checking the subtype relationship between `a` and `b` | |
51 | // as-is, we need to do some extra work here in order to make sure | |
52 | // that function subtyping works correctly with respect to regions | |
53 | // | |
54 | // Note: this is a subtle algorithm. For a full explanation, | |
55 | // please see the large comment at the end of the file in the (inlined) module | |
56 | // `doc`. | |
57 | ||
58 | // Start a snapshot so we can examine "all bindings that were | |
59 | // created as part of this type comparison". | |
c34b1796 | 60 | return self.infcx.commit_if_ok(|snapshot| { |
1a4d82fc JJ |
61 | // First, we instantiate each bound region in the subtype with a fresh |
62 | // region variable. | |
63 | let (a_prime, _) = | |
c34b1796 AL |
64 | self.infcx.replace_late_bound_regions_with_fresh_var( |
65 | self.trace.origin.span(), | |
1a4d82fc JJ |
66 | HigherRankedType, |
67 | a); | |
68 | ||
69 | // Second, we instantiate each bound region in the supertype with a | |
70 | // fresh concrete region. | |
71 | let (b_prime, skol_map) = | |
c34b1796 | 72 | self.infcx.skolemize_late_bound_regions(b, snapshot); |
1a4d82fc | 73 | |
62682a34 SL |
74 | debug!("a_prime={:?}", a_prime); |
75 | debug!("b_prime={:?}", b_prime); | |
1a4d82fc JJ |
76 | |
77 | // Compare types now that bound regions have been replaced. | |
c34b1796 | 78 | let result = try!(self.sub().relate(&a_prime, &b_prime)); |
1a4d82fc JJ |
79 | |
80 | // Presuming type comparison succeeds, we need to check | |
81 | // that the skolemized regions do not "leak". | |
c34b1796 | 82 | match leak_check(self.infcx, &skol_map, snapshot) { |
1a4d82fc JJ |
83 | Ok(()) => { } |
84 | Err((skol_br, tainted_region)) => { | |
c34b1796 | 85 | if self.a_is_expected { |
1a4d82fc | 86 | debug!("Not as polymorphic!"); |
c1a9b12d | 87 | return Err(TypeError::RegionsInsufficientlyPolymorphic(skol_br, |
1a4d82fc JJ |
88 | tainted_region)); |
89 | } else { | |
90 | debug!("Overly polymorphic!"); | |
c1a9b12d | 91 | return Err(TypeError::RegionsOverlyPolymorphic(skol_br, |
1a4d82fc JJ |
92 | tainted_region)); |
93 | } | |
94 | } | |
95 | } | |
96 | ||
62682a34 SL |
97 | debug!("higher_ranked_sub: OK result={:?}", |
98 | result); | |
1a4d82fc JJ |
99 | |
100 | Ok(ty::Binder(result)) | |
101 | }); | |
102 | } | |
103 | ||
c34b1796 AL |
104 | fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>> |
105 | where T: Relate<'a,'tcx> | |
1a4d82fc JJ |
106 | { |
107 | // Start a snapshot so we can examine "all bindings that were | |
108 | // created as part of this type comparison". | |
c34b1796 | 109 | return self.infcx.commit_if_ok(|snapshot| { |
1a4d82fc | 110 | // Instantiate each bound region with a fresh region variable. |
c34b1796 | 111 | let span = self.trace.origin.span(); |
1a4d82fc | 112 | let (a_with_fresh, a_map) = |
c34b1796 | 113 | self.infcx.replace_late_bound_regions_with_fresh_var( |
1a4d82fc JJ |
114 | span, HigherRankedType, a); |
115 | let (b_with_fresh, _) = | |
c34b1796 | 116 | self.infcx.replace_late_bound_regions_with_fresh_var( |
1a4d82fc JJ |
117 | span, HigherRankedType, b); |
118 | ||
119 | // Collect constraints. | |
120 | let result0 = | |
c34b1796 | 121 | try!(self.lub().relate(&a_with_fresh, &b_with_fresh)); |
1a4d82fc | 122 | let result0 = |
c34b1796 | 123 | self.infcx.resolve_type_vars_if_possible(&result0); |
62682a34 | 124 | debug!("lub result0 = {:?}", result0); |
1a4d82fc JJ |
125 | |
126 | // Generalize the regions appearing in result0 if possible | |
c34b1796 AL |
127 | let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot); |
128 | let span = self.trace.origin.span(); | |
1a4d82fc JJ |
129 | let result1 = |
130 | fold_regions_in( | |
131 | self.tcx(), | |
132 | &result0, | |
c34b1796 | 133 | |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn, |
85aaf69f | 134 | &new_vars, &a_map, r)); |
1a4d82fc | 135 | |
62682a34 SL |
136 | debug!("lub({:?},{:?}) = {:?}", |
137 | a, | |
138 | b, | |
139 | result1); | |
1a4d82fc JJ |
140 | |
141 | Ok(ty::Binder(result1)) | |
142 | }); | |
143 | ||
144 | fn generalize_region(infcx: &InferCtxt, | |
145 | span: Span, | |
146 | snapshot: &CombinedSnapshot, | |
147 | debruijn: ty::DebruijnIndex, | |
148 | new_vars: &[ty::RegionVid], | |
149 | a_map: &FnvHashMap<ty::BoundRegion, ty::Region>, | |
150 | r0: ty::Region) | |
151 | -> ty::Region { | |
152 | // Regions that pre-dated the LUB computation stay as they are. | |
153 | if !is_var_in_set(new_vars, r0) { | |
154 | assert!(!r0.is_bound()); | |
155 | debug!("generalize_region(r0={:?}): not new variable", r0); | |
156 | return r0; | |
157 | } | |
158 | ||
159 | let tainted = infcx.tainted_regions(snapshot, r0); | |
160 | ||
161 | // Variables created during LUB computation which are | |
162 | // *related* to regions that pre-date the LUB computation | |
163 | // stay as they are. | |
164 | if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) { | |
165 | debug!("generalize_region(r0={:?}): \ | |
166 | non-new-variables found in {:?}", | |
167 | r0, tainted); | |
168 | assert!(!r0.is_bound()); | |
169 | return r0; | |
170 | } | |
171 | ||
172 | // Otherwise, the variable must be associated with at | |
173 | // least one of the variables representing bound regions | |
174 | // in both A and B. Replace the variable with the "first" | |
175 | // bound region from A that we find it to be associated | |
176 | // with. | |
85aaf69f | 177 | for (a_br, a_r) in a_map { |
1a4d82fc JJ |
178 | if tainted.iter().any(|x| x == a_r) { |
179 | debug!("generalize_region(r0={:?}): \ | |
180 | replacing with {:?}, tainted={:?}", | |
181 | r0, *a_br, tainted); | |
182 | return ty::ReLateBound(debruijn, *a_br); | |
183 | } | |
184 | } | |
185 | ||
186 | infcx.tcx.sess.span_bug( | |
187 | span, | |
188 | &format!("region {:?} is not associated with \ | |
189 | any bound region from A!", | |
c34b1796 | 190 | r0)) |
1a4d82fc JJ |
191 | } |
192 | } | |
193 | ||
c34b1796 AL |
194 | fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> RelateResult<'tcx, Binder<T>> |
195 | where T: Relate<'a,'tcx> | |
1a4d82fc | 196 | { |
62682a34 SL |
197 | debug!("higher_ranked_glb({:?}, {:?})", |
198 | a, b); | |
1a4d82fc JJ |
199 | |
200 | // Make a snapshot so we can examine "all bindings that were | |
201 | // created as part of this type comparison". | |
c34b1796 | 202 | return self.infcx.commit_if_ok(|snapshot| { |
1a4d82fc JJ |
203 | // Instantiate each bound region with a fresh region variable. |
204 | let (a_with_fresh, a_map) = | |
c34b1796 AL |
205 | self.infcx.replace_late_bound_regions_with_fresh_var( |
206 | self.trace.origin.span(), HigherRankedType, a); | |
1a4d82fc | 207 | let (b_with_fresh, b_map) = |
c34b1796 AL |
208 | self.infcx.replace_late_bound_regions_with_fresh_var( |
209 | self.trace.origin.span(), HigherRankedType, b); | |
1a4d82fc JJ |
210 | let a_vars = var_ids(self, &a_map); |
211 | let b_vars = var_ids(self, &b_map); | |
212 | ||
213 | // Collect constraints. | |
214 | let result0 = | |
c34b1796 | 215 | try!(self.glb().relate(&a_with_fresh, &b_with_fresh)); |
1a4d82fc | 216 | let result0 = |
c34b1796 | 217 | self.infcx.resolve_type_vars_if_possible(&result0); |
62682a34 | 218 | debug!("glb result0 = {:?}", result0); |
1a4d82fc JJ |
219 | |
220 | // Generalize the regions appearing in result0 if possible | |
c34b1796 AL |
221 | let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot); |
222 | let span = self.trace.origin.span(); | |
1a4d82fc JJ |
223 | let result1 = |
224 | fold_regions_in( | |
225 | self.tcx(), | |
226 | &result0, | |
c34b1796 | 227 | |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn, |
85aaf69f SL |
228 | &new_vars, |
229 | &a_map, &a_vars, &b_vars, | |
1a4d82fc JJ |
230 | r)); |
231 | ||
62682a34 SL |
232 | debug!("glb({:?},{:?}) = {:?}", |
233 | a, | |
234 | b, | |
235 | result1); | |
1a4d82fc JJ |
236 | |
237 | Ok(ty::Binder(result1)) | |
238 | }); | |
239 | ||
240 | fn generalize_region(infcx: &InferCtxt, | |
241 | span: Span, | |
242 | snapshot: &CombinedSnapshot, | |
243 | debruijn: ty::DebruijnIndex, | |
244 | new_vars: &[ty::RegionVid], | |
245 | a_map: &FnvHashMap<ty::BoundRegion, ty::Region>, | |
246 | a_vars: &[ty::RegionVid], | |
247 | b_vars: &[ty::RegionVid], | |
248 | r0: ty::Region) -> ty::Region { | |
249 | if !is_var_in_set(new_vars, r0) { | |
250 | assert!(!r0.is_bound()); | |
251 | return r0; | |
252 | } | |
253 | ||
254 | let tainted = infcx.tainted_regions(snapshot, r0); | |
255 | ||
256 | let mut a_r = None; | |
257 | let mut b_r = None; | |
258 | let mut only_new_vars = true; | |
85aaf69f | 259 | for r in &tainted { |
1a4d82fc JJ |
260 | if is_var_in_set(a_vars, *r) { |
261 | if a_r.is_some() { | |
262 | return fresh_bound_variable(infcx, debruijn); | |
263 | } else { | |
264 | a_r = Some(*r); | |
265 | } | |
266 | } else if is_var_in_set(b_vars, *r) { | |
267 | if b_r.is_some() { | |
268 | return fresh_bound_variable(infcx, debruijn); | |
269 | } else { | |
270 | b_r = Some(*r); | |
271 | } | |
272 | } else if !is_var_in_set(new_vars, *r) { | |
273 | only_new_vars = false; | |
274 | } | |
275 | } | |
276 | ||
277 | // NB---I do not believe this algorithm computes | |
278 | // (necessarily) the GLB. As written it can | |
279 | // spuriously fail. In particular, if there is a case | |
280 | // like: |fn(&a)| and fn(fn(&b)), where a and b are | |
281 | // free, it will return fn(&c) where c = GLB(a,b). If | |
282 | // however this GLB is not defined, then the result is | |
283 | // an error, even though something like | |
284 | // "fn<X>(fn(&X))" where X is bound would be a | |
285 | // subtype of both of those. | |
286 | // | |
287 | // The problem is that if we were to return a bound | |
288 | // variable, we'd be computing a lower-bound, but not | |
289 | // necessarily the *greatest* lower-bound. | |
290 | // | |
291 | // Unfortunately, this problem is non-trivial to solve, | |
292 | // because we do not know at the time of computing the GLB | |
293 | // whether a GLB(a,b) exists or not, because we haven't | |
294 | // run region inference (or indeed, even fully computed | |
295 | // the region hierarchy!). The current algorithm seems to | |
296 | // works ok in practice. | |
297 | ||
298 | if a_r.is_some() && b_r.is_some() && only_new_vars { | |
299 | // Related to exactly one bound variable from each fn: | |
300 | return rev_lookup(infcx, span, a_map, a_r.unwrap()); | |
301 | } else if a_r.is_none() && b_r.is_none() { | |
302 | // Not related to bound variables from either fn: | |
303 | assert!(!r0.is_bound()); | |
304 | return r0; | |
305 | } else { | |
306 | // Other: | |
307 | return fresh_bound_variable(infcx, debruijn); | |
308 | } | |
309 | } | |
310 | ||
311 | fn rev_lookup(infcx: &InferCtxt, | |
312 | span: Span, | |
313 | a_map: &FnvHashMap<ty::BoundRegion, ty::Region>, | |
314 | r: ty::Region) -> ty::Region | |
315 | { | |
85aaf69f | 316 | for (a_br, a_r) in a_map { |
1a4d82fc JJ |
317 | if *a_r == r { |
318 | return ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br); | |
319 | } | |
320 | } | |
321 | infcx.tcx.sess.span_bug( | |
322 | span, | |
c34b1796 | 323 | &format!("could not find original bound region for {:?}", r)); |
1a4d82fc JJ |
324 | } |
325 | ||
326 | fn fresh_bound_variable(infcx: &InferCtxt, debruijn: ty::DebruijnIndex) -> ty::Region { | |
327 | infcx.region_vars.new_bound(debruijn) | |
328 | } | |
329 | } | |
330 | } | |
331 | ||
c34b1796 AL |
332 | fn var_ids<'a, 'tcx>(fields: &CombineFields<'a, 'tcx>, |
333 | map: &FnvHashMap<ty::BoundRegion, ty::Region>) | |
334 | -> Vec<ty::RegionVid> { | |
335 | map.iter() | |
336 | .map(|(_, r)| match *r { | |
e9174d1e | 337 | ty::ReVar(r) => { r } |
c34b1796 AL |
338 | r => { |
339 | fields.tcx().sess.span_bug( | |
340 | fields.trace.origin.span(), | |
341 | &format!("found non-region-vid: {:?}", r)); | |
342 | } | |
343 | }) | |
344 | .collect() | |
1a4d82fc JJ |
345 | } |
346 | ||
347 | fn is_var_in_set(new_vars: &[ty::RegionVid], r: ty::Region) -> bool { | |
348 | match r { | |
e9174d1e | 349 | ty::ReVar(ref v) => new_vars.iter().any(|x| x == v), |
1a4d82fc JJ |
350 | _ => false |
351 | } | |
352 | } | |
353 | ||
354 | fn fold_regions_in<'tcx, T, F>(tcx: &ty::ctxt<'tcx>, | |
355 | unbound_value: &T, | |
356 | mut fldr: F) | |
357 | -> T | |
c34b1796 AL |
358 | where T: TypeFoldable<'tcx>, |
359 | F: FnMut(ty::Region, ty::DebruijnIndex) -> ty::Region, | |
1a4d82fc | 360 | { |
e9174d1e | 361 | tcx.fold_regions(unbound_value, &mut false, |region, current_depth| { |
1a4d82fc JJ |
362 | // we should only be encountering "escaping" late-bound regions here, |
363 | // because the ones at the current level should have been replaced | |
364 | // with fresh variables | |
365 | assert!(match region { | |
366 | ty::ReLateBound(..) => false, | |
367 | _ => true | |
368 | }); | |
369 | ||
370 | fldr(region, ty::DebruijnIndex::new(current_depth)) | |
c1a9b12d | 371 | }) |
1a4d82fc JJ |
372 | } |
373 | ||
85aaf69f | 374 | impl<'a,'tcx> InferCtxtExt for InferCtxt<'a,'tcx> { |
1a4d82fc JJ |
375 | fn tainted_regions(&self, snapshot: &CombinedSnapshot, r: ty::Region) -> Vec<ty::Region> { |
376 | self.region_vars.tainted(&snapshot.region_vars_snapshot, r) | |
377 | } | |
378 | ||
379 | fn region_vars_confined_to_snapshot(&self, | |
380 | snapshot: &CombinedSnapshot) | |
381 | -> Vec<ty::RegionVid> | |
382 | { | |
383 | /*! | |
384 | * Returns the set of region variables that do not affect any | |
385 | * types/regions which existed before `snapshot` was | |
386 | * started. This is used in the sub/lub/glb computations. The | |
387 | * idea here is that when we are computing lub/glb of two | |
388 | * regions, we sometimes create intermediate region variables. | |
389 | * Those region variables may touch some of the skolemized or | |
390 | * other "forbidden" regions we created to replace bound | |
391 | * regions, but they don't really represent an "external" | |
392 | * constraint. | |
393 | * | |
394 | * However, sometimes fresh variables are created for other | |
395 | * purposes too, and those *may* represent an external | |
396 | * constraint. In particular, when a type variable is | |
397 | * instantiated, we create region variables for all the | |
398 | * regions that appear within, and if that type variable | |
399 | * pre-existed the snapshot, then those region variables | |
400 | * represent external constraints. | |
401 | * | |
402 | * An example appears in the unit test | |
403 | * `sub_free_bound_false_infer`. In this test, we want to | |
404 | * know whether | |
405 | * | |
406 | * ```rust | |
407 | * fn(_#0t) <: for<'a> fn(&'a int) | |
408 | * ``` | |
409 | * | |
410 | * Note that the subtype has a type variable. Because the type | |
411 | * variable can't be instantiated with a region that is bound | |
412 | * in the fn signature, this comparison ought to fail. But if | |
413 | * we're not careful, it will succeed. | |
414 | * | |
415 | * The reason is that when we walk through the subtyping | |
416 | * algorith, we begin by replacing `'a` with a skolemized | |
417 | * variable `'1`. We then have `fn(_#0t) <: fn(&'1 int)`. This | |
418 | * can be made true by unifying `_#0t` with `&'1 int`. In the | |
419 | * process, we create a fresh variable for the skolemized | |
420 | * region, `'$2`, and hence we have that `_#0t == &'$2 | |
421 | * int`. However, because `'$2` was created during the sub | |
422 | * computation, if we're not careful we will erroneously | |
423 | * assume it is one of the transient region variables | |
424 | * representing a lub/glb internally. Not good. | |
425 | * | |
426 | * To prevent this, we check for type variables which were | |
427 | * unified during the snapshot, and say that any region | |
428 | * variable created during the snapshot but which finds its | |
429 | * way into a type variable is considered to "escape" the | |
430 | * snapshot. | |
431 | */ | |
432 | ||
433 | let mut region_vars = | |
434 | self.region_vars.vars_created_since_snapshot(&snapshot.region_vars_snapshot); | |
435 | ||
436 | let escaping_types = | |
437 | self.type_variables.borrow().types_escaping_snapshot(&snapshot.type_snapshot); | |
438 | ||
c1a9b12d SL |
439 | let mut escaping_region_vars = FnvHashSet(); |
440 | for ty in &escaping_types { | |
e9174d1e | 441 | self.tcx.collect_regions(ty, &mut escaping_region_vars); |
c1a9b12d | 442 | } |
1a4d82fc JJ |
443 | |
444 | region_vars.retain(|®ion_vid| { | |
e9174d1e | 445 | let r = ty::ReVar(region_vid); |
1a4d82fc JJ |
446 | !escaping_region_vars.contains(&r) |
447 | }); | |
448 | ||
62682a34 SL |
449 | debug!("region_vars_confined_to_snapshot: region_vars={:?} escaping_types={:?}", |
450 | region_vars, | |
451 | escaping_types); | |
1a4d82fc JJ |
452 | |
453 | region_vars | |
454 | } | |
455 | } | |
456 | ||
457 | pub fn skolemize_late_bound_regions<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>, | |
458 | binder: &ty::Binder<T>, | |
459 | snapshot: &CombinedSnapshot) | |
460 | -> (T, SkolemizationMap) | |
62682a34 | 461 | where T : TypeFoldable<'tcx> |
1a4d82fc JJ |
462 | { |
463 | /*! | |
464 | * Replace all regions bound by `binder` with skolemized regions and | |
465 | * return a map indicating which bound-region was replaced with what | |
466 | * skolemized region. This is the first step of checking subtyping | |
c34b1796 AL |
467 | * when higher-ranked things are involved. See `README.md` for more |
468 | * details. | |
1a4d82fc JJ |
469 | */ |
470 | ||
e9174d1e | 471 | let (result, map) = infcx.tcx.replace_late_bound_regions(binder, |br| { |
1a4d82fc JJ |
472 | infcx.region_vars.new_skolemized(br, &snapshot.region_vars_snapshot) |
473 | }); | |
474 | ||
62682a34 SL |
475 | debug!("skolemize_bound_regions(binder={:?}, result={:?}, map={:?})", |
476 | binder, | |
477 | result, | |
478 | map); | |
1a4d82fc JJ |
479 | |
480 | (result, map) | |
481 | } | |
482 | ||
483 | pub fn leak_check<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>, | |
484 | skol_map: &SkolemizationMap, | |
485 | snapshot: &CombinedSnapshot) | |
486 | -> Result<(),(ty::BoundRegion,ty::Region)> | |
487 | { | |
488 | /*! | |
489 | * Searches the region constriants created since `snapshot` was started | |
490 | * and checks to determine whether any of the skolemized regions created | |
491 | * in `skol_map` would "escape" -- meaning that they are related to | |
492 | * other regions in some way. If so, the higher-ranked subtyping doesn't | |
c34b1796 | 493 | * hold. See `README.md` for more details. |
1a4d82fc JJ |
494 | */ |
495 | ||
62682a34 SL |
496 | debug!("leak_check: skol_map={:?}", |
497 | skol_map); | |
1a4d82fc JJ |
498 | |
499 | let new_vars = infcx.region_vars_confined_to_snapshot(snapshot); | |
85aaf69f | 500 | for (&skol_br, &skol) in skol_map { |
1a4d82fc | 501 | let tainted = infcx.tainted_regions(snapshot, skol); |
85aaf69f | 502 | for &tainted_region in &tainted { |
1a4d82fc JJ |
503 | // Each skolemized should only be relatable to itself |
504 | // or new variables: | |
505 | match tainted_region { | |
e9174d1e | 506 | ty::ReVar(vid) => { |
1a4d82fc JJ |
507 | if new_vars.iter().any(|&x| x == vid) { continue; } |
508 | } | |
509 | _ => { | |
510 | if tainted_region == skol { continue; } | |
511 | } | |
512 | }; | |
513 | ||
62682a34 SL |
514 | debug!("{:?} (which replaced {:?}) is tainted by {:?}", |
515 | skol, | |
516 | skol_br, | |
517 | tainted_region); | |
1a4d82fc JJ |
518 | |
519 | // A is not as polymorphic as B: | |
520 | return Err((skol_br, tainted_region)); | |
521 | } | |
522 | } | |
523 | Ok(()) | |
524 | } | |
525 | ||
526 | /// This code converts from skolemized regions back to late-bound | |
527 | /// regions. It works by replacing each region in the taint set of a | |
528 | /// skolemized region with a bound-region. The bound region will be bound | |
529 | /// by the outer-most binder in `value`; the caller must ensure that there is | |
530 | /// such a binder and it is the right place. | |
531 | /// | |
532 | /// This routine is only intended to be used when the leak-check has | |
533 | /// passed; currently, it's used in the trait matching code to create | |
534 | /// a set of nested obligations frmo an impl that matches against | |
535 | /// something higher-ranked. More details can be found in | |
c34b1796 | 536 | /// `librustc/middle/traits/README.md`. |
1a4d82fc JJ |
537 | /// |
538 | /// As a brief example, consider the obligation `for<'a> Fn(&'a int) | |
539 | /// -> &'a int`, and the impl: | |
540 | /// | |
541 | /// impl<A,R> Fn<A,R> for SomethingOrOther | |
542 | /// where A : Clone | |
543 | /// { ... } | |
544 | /// | |
545 | /// Here we will have replaced `'a` with a skolemized region | |
546 | /// `'0`. This means that our substitution will be `{A=>&'0 | |
547 | /// int, R=>&'0 int}`. | |
548 | /// | |
549 | /// When we apply the substitution to the bounds, we will wind up with | |
550 | /// `&'0 int : Clone` as a predicate. As a last step, we then go and | |
551 | /// replace `'0` with a late-bound region `'a`. The depth is matched | |
552 | /// to the depth of the predicate, in this case 1, so that the final | |
553 | /// predicate is `for<'a> &'a int : Clone`. | |
554 | pub fn plug_leaks<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>, | |
555 | skol_map: SkolemizationMap, | |
556 | snapshot: &CombinedSnapshot, | |
557 | value: &T) | |
558 | -> T | |
9cc50fc6 | 559 | where T : TypeFoldable<'tcx> |
1a4d82fc JJ |
560 | { |
561 | debug_assert!(leak_check(infcx, &skol_map, snapshot).is_ok()); | |
562 | ||
62682a34 SL |
563 | debug!("plug_leaks(skol_map={:?}, value={:?})", |
564 | skol_map, | |
565 | value); | |
1a4d82fc JJ |
566 | |
567 | // Compute a mapping from the "taint set" of each skolemized | |
568 | // region back to the `ty::BoundRegion` that it originally | |
b039eaaf | 569 | // represented. Because `leak_check` passed, we know that |
1a4d82fc JJ |
570 | // these taint sets are mutually disjoint. |
571 | let inv_skol_map: FnvHashMap<ty::Region, ty::BoundRegion> = | |
572 | skol_map | |
573 | .into_iter() | |
574 | .flat_map(|(skol_br, skol)| { | |
575 | infcx.tainted_regions(snapshot, skol) | |
576 | .into_iter() | |
577 | .map(move |tainted_region| (tainted_region, skol_br)) | |
578 | }) | |
579 | .collect(); | |
580 | ||
62682a34 SL |
581 | debug!("plug_leaks: inv_skol_map={:?}", |
582 | inv_skol_map); | |
1a4d82fc JJ |
583 | |
584 | // Remove any instantiated type variables from `value`; those can hide | |
585 | // references to regions from the `fold_regions` code below. | |
586 | let value = infcx.resolve_type_vars_if_possible(value); | |
587 | ||
588 | // Map any skolemization byproducts back to a late-bound | |
589 | // region. Put that late-bound region at whatever the outermost | |
590 | // binder is that we encountered in `value`. The caller is | |
591 | // responsible for ensuring that (a) `value` contains at least one | |
592 | // binder and (b) that binder is the one we want to use. | |
e9174d1e | 593 | let result = infcx.tcx.fold_regions(&value, &mut false, |r, current_depth| { |
1a4d82fc JJ |
594 | match inv_skol_map.get(&r) { |
595 | None => r, | |
596 | Some(br) => { | |
597 | // It is the responsibility of the caller to ensure | |
598 | // that each skolemized region appears within a | |
599 | // binder. In practice, this routine is only used by | |
600 | // trait checking, and all of the skolemized regions | |
601 | // appear inside predicates, which always have | |
602 | // binders, so this assert is satisfied. | |
603 | assert!(current_depth > 1); | |
604 | ||
605 | ty::ReLateBound(ty::DebruijnIndex::new(current_depth - 1), br.clone()) | |
606 | } | |
607 | } | |
608 | }); | |
609 | ||
62682a34 SL |
610 | debug!("plug_leaks: result={:?}", |
611 | result); | |
1a4d82fc JJ |
612 | |
613 | result | |
614 | } |