]>
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 | ||
3157f602 XL |
14 | use super::{CombinedSnapshot, |
15 | InferCtxt, | |
16 | LateBoundRegion, | |
17 | HigherRankedType, | |
18 | SubregionOrigin, | |
19 | SkolemizationMap}; | |
c34b1796 | 20 | use super::combine::CombineFields; |
3157f602 | 21 | use super::region_inference::{TaintDirections}; |
1a4d82fc | 22 | |
54a0048b SL |
23 | use ty::{self, TyCtxt, Binder, TypeFoldable}; |
24 | use ty::error::TypeError; | |
25 | use ty::relate::{Relate, RelateResult, TypeRelation}; | |
3157f602 | 26 | use syntax_pos::Span; |
1a4d82fc | 27 | use util::nodemap::{FnvHashMap, FnvHashSet}; |
1a4d82fc | 28 | |
3157f602 XL |
29 | pub struct HrMatchResult<U> { |
30 | pub value: U, | |
31 | ||
32 | /// Normally, when we do a higher-ranked match operation, we | |
33 | /// expect all higher-ranked regions to be constrained as part of | |
34 | /// the match operation. However, in the transition period for | |
35 | /// #32330, it can happen that we sometimes have unconstrained | |
36 | /// regions that get instantiated with fresh variables. In that | |
37 | /// case, we collect the set of unconstrained bound regions here | |
38 | /// and replace them with fresh variables. | |
39 | pub unconstrained_regions: Vec<ty::BoundRegion>, | |
40 | } | |
41 | ||
a7813a04 | 42 | impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> { |
5bcae85e | 43 | pub fn higher_ranked_sub<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool) |
a7813a04 XL |
44 | -> RelateResult<'tcx, Binder<T>> |
45 | where T: Relate<'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| { |
3157f602 XL |
61 | let span = self.trace.origin.span(); |
62 | ||
1a4d82fc JJ |
63 | // First, we instantiate each bound region in the subtype with a fresh |
64 | // region variable. | |
65 | let (a_prime, _) = | |
c34b1796 | 66 | self.infcx.replace_late_bound_regions_with_fresh_var( |
3157f602 | 67 | span, |
1a4d82fc JJ |
68 | HigherRankedType, |
69 | a); | |
70 | ||
71 | // Second, we instantiate each bound region in the supertype with a | |
72 | // fresh concrete region. | |
73 | let (b_prime, skol_map) = | |
c34b1796 | 74 | self.infcx.skolemize_late_bound_regions(b, snapshot); |
1a4d82fc | 75 | |
62682a34 SL |
76 | debug!("a_prime={:?}", a_prime); |
77 | debug!("b_prime={:?}", b_prime); | |
1a4d82fc JJ |
78 | |
79 | // Compare types now that bound regions have been replaced. | |
5bcae85e | 80 | let result = self.sub(a_is_expected).relate(&a_prime, &b_prime)?; |
1a4d82fc JJ |
81 | |
82 | // Presuming type comparison succeeds, we need to check | |
83 | // that the skolemized regions do not "leak". | |
5bcae85e | 84 | self.infcx.leak_check(!a_is_expected, span, &skol_map, snapshot)?; |
3157f602 XL |
85 | |
86 | // We are finished with the skolemized regions now so pop | |
87 | // them off. | |
88 | self.infcx.pop_skolemized(skol_map, snapshot); | |
1a4d82fc | 89 | |
a7813a04 | 90 | debug!("higher_ranked_sub: OK result={:?}", result); |
1a4d82fc JJ |
91 | |
92 | Ok(ty::Binder(result)) | |
93 | }); | |
94 | } | |
95 | ||
3157f602 XL |
96 | /// The value consists of a pair `(t, u)` where `t` is the |
97 | /// *matcher* and `u` is a *value*. The idea is to find a | |
98 | /// substitution `S` such that `S(t) == b`, and then return | |
99 | /// `S(u)`. In other words, find values for the late-bound regions | |
100 | /// in `a` that can make `t == b` and then replace the LBR in `u` | |
101 | /// with those values. | |
102 | /// | |
103 | /// This routine is (as of this writing) used in trait matching, | |
104 | /// particularly projection. | |
105 | /// | |
106 | /// NB. It should not happen that there are LBR appearing in `U` | |
107 | /// that do not appear in `T`. If that happens, those regions are | |
108 | /// unconstrained, and this routine replaces them with `'static`. | |
5bcae85e | 109 | pub fn higher_ranked_match<T, U>(&mut self, |
3157f602 XL |
110 | span: Span, |
111 | a_pair: &Binder<(T, U)>, | |
5bcae85e SL |
112 | b_match: &T, |
113 | a_is_expected: bool) | |
3157f602 XL |
114 | -> RelateResult<'tcx, HrMatchResult<U>> |
115 | where T: Relate<'tcx>, | |
116 | U: TypeFoldable<'tcx> | |
117 | { | |
118 | debug!("higher_ranked_match(a={:?}, b={:?})", | |
119 | a_pair, b_match); | |
120 | ||
121 | // Start a snapshot so we can examine "all bindings that were | |
122 | // created as part of this type comparison". | |
123 | return self.infcx.commit_if_ok(|snapshot| { | |
124 | // First, we instantiate each bound region in the matcher | |
125 | // with a skolemized region. | |
126 | let ((a_match, a_value), skol_map) = | |
127 | self.infcx.skolemize_late_bound_regions(a_pair, snapshot); | |
128 | ||
129 | debug!("higher_ranked_match: a_match={:?}", a_match); | |
130 | debug!("higher_ranked_match: skol_map={:?}", skol_map); | |
131 | ||
132 | // Equate types now that bound regions have been replaced. | |
9e0c209e | 133 | self.equate(a_is_expected).relate(&a_match, &b_match)?; |
3157f602 XL |
134 | |
135 | // Map each skolemized region to a vector of other regions that it | |
136 | // must be equated with. (Note that this vector may include other | |
137 | // skolemized regions from `skol_map`.) | |
138 | let skol_resolution_map: FnvHashMap<_, _> = | |
139 | skol_map | |
140 | .iter() | |
141 | .map(|(&br, &skol)| { | |
142 | let tainted_regions = | |
143 | self.infcx.tainted_regions(snapshot, | |
144 | skol, | |
145 | TaintDirections::incoming()); // [1] | |
146 | ||
147 | // [1] this routine executes after the skolemized | |
148 | // regions have been *equated* with something | |
149 | // else, so examining the incoming edges ought to | |
150 | // be enough to collect all constraints | |
151 | ||
152 | (skol, (br, tainted_regions)) | |
153 | }) | |
154 | .collect(); | |
155 | ||
156 | // For each skolemized region, pick a representative -- which can | |
157 | // be any region from the sets above, except for other members of | |
158 | // `skol_map`. There should always be a representative if things | |
159 | // are properly well-formed. | |
160 | let mut unconstrained_regions = vec![]; | |
161 | let skol_representatives: FnvHashMap<_, _> = | |
162 | skol_resolution_map | |
163 | .iter() | |
164 | .map(|(&skol, &(br, ref regions))| { | |
165 | let representative = | |
166 | regions.iter() | |
9e0c209e | 167 | .filter(|&&r| !skol_resolution_map.contains_key(r)) |
3157f602 XL |
168 | .cloned() |
169 | .next() | |
170 | .unwrap_or_else(|| { // [1] | |
171 | unconstrained_regions.push(br); | |
172 | self.infcx.next_region_var( | |
173 | LateBoundRegion(span, br, HigherRankedType)) | |
174 | }); | |
175 | ||
176 | // [1] There should always be a representative, | |
177 | // unless the higher-ranked region did not appear | |
178 | // in the values being matched. We should reject | |
179 | // as ill-formed cases that can lead to this, but | |
180 | // right now we sometimes issue warnings (see | |
181 | // #32330). | |
182 | ||
183 | (skol, representative) | |
184 | }) | |
185 | .collect(); | |
186 | ||
187 | // Equate all the members of each skolemization set with the | |
188 | // representative. | |
189 | for (skol, &(_br, ref regions)) in &skol_resolution_map { | |
190 | let representative = &skol_representatives[skol]; | |
191 | debug!("higher_ranked_match: \ | |
192 | skol={:?} representative={:?} regions={:?}", | |
193 | skol, representative, regions); | |
194 | for region in regions.iter() | |
195 | .filter(|&r| !skol_resolution_map.contains_key(r)) | |
196 | .filter(|&r| r != representative) | |
197 | { | |
198 | let origin = SubregionOrigin::Subtype(self.trace.clone()); | |
199 | self.infcx.region_vars.make_eqregion(origin, | |
200 | *representative, | |
201 | *region); | |
202 | } | |
203 | } | |
204 | ||
205 | // Replace the skolemized regions appearing in value with | |
206 | // their representatives | |
207 | let a_value = | |
208 | fold_regions_in( | |
209 | self.tcx(), | |
210 | &a_value, | |
211 | |r, _| skol_representatives.get(&r).cloned().unwrap_or(r)); | |
212 | ||
213 | debug!("higher_ranked_match: value={:?}", a_value); | |
214 | ||
215 | // We are now done with these skolemized variables. | |
216 | self.infcx.pop_skolemized(skol_map, snapshot); | |
217 | ||
218 | Ok(HrMatchResult { | |
219 | value: a_value, | |
220 | unconstrained_regions: unconstrained_regions, | |
221 | }) | |
222 | }); | |
223 | } | |
224 | ||
5bcae85e | 225 | pub fn higher_ranked_lub<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool) |
a7813a04 XL |
226 | -> RelateResult<'tcx, Binder<T>> |
227 | where T: Relate<'tcx> | |
1a4d82fc JJ |
228 | { |
229 | // Start a snapshot so we can examine "all bindings that were | |
230 | // created as part of this type comparison". | |
c34b1796 | 231 | return self.infcx.commit_if_ok(|snapshot| { |
1a4d82fc | 232 | // Instantiate each bound region with a fresh region variable. |
c34b1796 | 233 | let span = self.trace.origin.span(); |
1a4d82fc | 234 | let (a_with_fresh, a_map) = |
c34b1796 | 235 | self.infcx.replace_late_bound_regions_with_fresh_var( |
1a4d82fc JJ |
236 | span, HigherRankedType, a); |
237 | let (b_with_fresh, _) = | |
c34b1796 | 238 | self.infcx.replace_late_bound_regions_with_fresh_var( |
1a4d82fc JJ |
239 | span, HigherRankedType, b); |
240 | ||
241 | // Collect constraints. | |
242 | let result0 = | |
5bcae85e | 243 | self.lub(a_is_expected).relate(&a_with_fresh, &b_with_fresh)?; |
1a4d82fc | 244 | let result0 = |
c34b1796 | 245 | self.infcx.resolve_type_vars_if_possible(&result0); |
62682a34 | 246 | debug!("lub result0 = {:?}", result0); |
1a4d82fc JJ |
247 | |
248 | // Generalize the regions appearing in result0 if possible | |
c34b1796 AL |
249 | let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot); |
250 | let span = self.trace.origin.span(); | |
1a4d82fc JJ |
251 | let result1 = |
252 | fold_regions_in( | |
253 | self.tcx(), | |
254 | &result0, | |
c34b1796 | 255 | |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn, |
85aaf69f | 256 | &new_vars, &a_map, r)); |
1a4d82fc | 257 | |
62682a34 SL |
258 | debug!("lub({:?},{:?}) = {:?}", |
259 | a, | |
260 | b, | |
261 | result1); | |
1a4d82fc JJ |
262 | |
263 | Ok(ty::Binder(result1)) | |
264 | }); | |
265 | ||
a7813a04 XL |
266 | fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, |
267 | span: Span, | |
268 | snapshot: &CombinedSnapshot, | |
269 | debruijn: ty::DebruijnIndex, | |
270 | new_vars: &[ty::RegionVid], | |
9e0c209e SL |
271 | a_map: &FnvHashMap<ty::BoundRegion, &'tcx ty::Region>, |
272 | r0: &'tcx ty::Region) | |
273 | -> &'tcx ty::Region { | |
1a4d82fc JJ |
274 | // Regions that pre-dated the LUB computation stay as they are. |
275 | if !is_var_in_set(new_vars, r0) { | |
276 | assert!(!r0.is_bound()); | |
277 | debug!("generalize_region(r0={:?}): not new variable", r0); | |
278 | return r0; | |
279 | } | |
280 | ||
3157f602 | 281 | let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both()); |
1a4d82fc JJ |
282 | |
283 | // Variables created during LUB computation which are | |
284 | // *related* to regions that pre-date the LUB computation | |
285 | // stay as they are. | |
286 | if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) { | |
287 | debug!("generalize_region(r0={:?}): \ | |
288 | non-new-variables found in {:?}", | |
289 | r0, tainted); | |
290 | assert!(!r0.is_bound()); | |
291 | return r0; | |
292 | } | |
293 | ||
294 | // Otherwise, the variable must be associated with at | |
295 | // least one of the variables representing bound regions | |
296 | // in both A and B. Replace the variable with the "first" | |
297 | // bound region from A that we find it to be associated | |
298 | // with. | |
85aaf69f | 299 | for (a_br, a_r) in a_map { |
1a4d82fc JJ |
300 | if tainted.iter().any(|x| x == a_r) { |
301 | debug!("generalize_region(r0={:?}): \ | |
302 | replacing with {:?}, tainted={:?}", | |
303 | r0, *a_br, tainted); | |
9e0c209e | 304 | return infcx.tcx.mk_region(ty::ReLateBound(debruijn, *a_br)); |
1a4d82fc JJ |
305 | } |
306 | } | |
307 | ||
54a0048b | 308 | span_bug!( |
1a4d82fc | 309 | span, |
54a0048b SL |
310 | "region {:?} is not associated with any bound region from A!", |
311 | r0) | |
1a4d82fc JJ |
312 | } |
313 | } | |
314 | ||
5bcae85e | 315 | pub fn higher_ranked_glb<T>(&mut self, a: &Binder<T>, b: &Binder<T>, a_is_expected: bool) |
a7813a04 XL |
316 | -> RelateResult<'tcx, Binder<T>> |
317 | where T: Relate<'tcx> | |
1a4d82fc | 318 | { |
62682a34 SL |
319 | debug!("higher_ranked_glb({:?}, {:?})", |
320 | a, b); | |
1a4d82fc JJ |
321 | |
322 | // Make a snapshot so we can examine "all bindings that were | |
323 | // created as part of this type comparison". | |
c34b1796 | 324 | return self.infcx.commit_if_ok(|snapshot| { |
1a4d82fc JJ |
325 | // Instantiate each bound region with a fresh region variable. |
326 | let (a_with_fresh, a_map) = | |
c34b1796 AL |
327 | self.infcx.replace_late_bound_regions_with_fresh_var( |
328 | self.trace.origin.span(), HigherRankedType, a); | |
1a4d82fc | 329 | let (b_with_fresh, b_map) = |
c34b1796 AL |
330 | self.infcx.replace_late_bound_regions_with_fresh_var( |
331 | self.trace.origin.span(), HigherRankedType, b); | |
1a4d82fc JJ |
332 | let a_vars = var_ids(self, &a_map); |
333 | let b_vars = var_ids(self, &b_map); | |
334 | ||
335 | // Collect constraints. | |
336 | let result0 = | |
5bcae85e | 337 | self.glb(a_is_expected).relate(&a_with_fresh, &b_with_fresh)?; |
1a4d82fc | 338 | let result0 = |
c34b1796 | 339 | self.infcx.resolve_type_vars_if_possible(&result0); |
62682a34 | 340 | debug!("glb result0 = {:?}", result0); |
1a4d82fc JJ |
341 | |
342 | // Generalize the regions appearing in result0 if possible | |
c34b1796 AL |
343 | let new_vars = self.infcx.region_vars_confined_to_snapshot(snapshot); |
344 | let span = self.trace.origin.span(); | |
1a4d82fc JJ |
345 | let result1 = |
346 | fold_regions_in( | |
347 | self.tcx(), | |
348 | &result0, | |
c34b1796 | 349 | |r, debruijn| generalize_region(self.infcx, span, snapshot, debruijn, |
85aaf69f SL |
350 | &new_vars, |
351 | &a_map, &a_vars, &b_vars, | |
1a4d82fc JJ |
352 | r)); |
353 | ||
62682a34 SL |
354 | debug!("glb({:?},{:?}) = {:?}", |
355 | a, | |
356 | b, | |
357 | result1); | |
1a4d82fc JJ |
358 | |
359 | Ok(ty::Binder(result1)) | |
360 | }); | |
361 | ||
a7813a04 XL |
362 | fn generalize_region<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, |
363 | span: Span, | |
364 | snapshot: &CombinedSnapshot, | |
365 | debruijn: ty::DebruijnIndex, | |
366 | new_vars: &[ty::RegionVid], | |
9e0c209e SL |
367 | a_map: &FnvHashMap<ty::BoundRegion, |
368 | &'tcx ty::Region>, | |
a7813a04 XL |
369 | a_vars: &[ty::RegionVid], |
370 | b_vars: &[ty::RegionVid], | |
9e0c209e SL |
371 | r0: &'tcx ty::Region) |
372 | -> &'tcx ty::Region { | |
1a4d82fc JJ |
373 | if !is_var_in_set(new_vars, r0) { |
374 | assert!(!r0.is_bound()); | |
375 | return r0; | |
376 | } | |
377 | ||
3157f602 | 378 | let tainted = infcx.tainted_regions(snapshot, r0, TaintDirections::both()); |
1a4d82fc JJ |
379 | |
380 | let mut a_r = None; | |
381 | let mut b_r = None; | |
382 | let mut only_new_vars = true; | |
85aaf69f | 383 | for r in &tainted { |
1a4d82fc JJ |
384 | if is_var_in_set(a_vars, *r) { |
385 | if a_r.is_some() { | |
386 | return fresh_bound_variable(infcx, debruijn); | |
387 | } else { | |
388 | a_r = Some(*r); | |
389 | } | |
390 | } else if is_var_in_set(b_vars, *r) { | |
391 | if b_r.is_some() { | |
392 | return fresh_bound_variable(infcx, debruijn); | |
393 | } else { | |
394 | b_r = Some(*r); | |
395 | } | |
396 | } else if !is_var_in_set(new_vars, *r) { | |
397 | only_new_vars = false; | |
398 | } | |
399 | } | |
400 | ||
401 | // NB---I do not believe this algorithm computes | |
402 | // (necessarily) the GLB. As written it can | |
403 | // spuriously fail. In particular, if there is a case | |
404 | // like: |fn(&a)| and fn(fn(&b)), where a and b are | |
405 | // free, it will return fn(&c) where c = GLB(a,b). If | |
406 | // however this GLB is not defined, then the result is | |
407 | // an error, even though something like | |
408 | // "fn<X>(fn(&X))" where X is bound would be a | |
409 | // subtype of both of those. | |
410 | // | |
411 | // The problem is that if we were to return a bound | |
412 | // variable, we'd be computing a lower-bound, but not | |
413 | // necessarily the *greatest* lower-bound. | |
414 | // | |
415 | // Unfortunately, this problem is non-trivial to solve, | |
416 | // because we do not know at the time of computing the GLB | |
417 | // whether a GLB(a,b) exists or not, because we haven't | |
418 | // run region inference (or indeed, even fully computed | |
419 | // the region hierarchy!). The current algorithm seems to | |
420 | // works ok in practice. | |
421 | ||
422 | if a_r.is_some() && b_r.is_some() && only_new_vars { | |
423 | // Related to exactly one bound variable from each fn: | |
9e0c209e | 424 | return rev_lookup(infcx, span, a_map, a_r.unwrap()); |
1a4d82fc JJ |
425 | } else if a_r.is_none() && b_r.is_none() { |
426 | // Not related to bound variables from either fn: | |
427 | assert!(!r0.is_bound()); | |
428 | return r0; | |
429 | } else { | |
430 | // Other: | |
431 | return fresh_bound_variable(infcx, debruijn); | |
432 | } | |
433 | } | |
434 | ||
9e0c209e SL |
435 | fn rev_lookup<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, |
436 | span: Span, | |
437 | a_map: &FnvHashMap<ty::BoundRegion, &'tcx ty::Region>, | |
438 | r: &'tcx ty::Region) -> &'tcx ty::Region | |
1a4d82fc | 439 | { |
85aaf69f | 440 | for (a_br, a_r) in a_map { |
1a4d82fc | 441 | if *a_r == r { |
9e0c209e | 442 | return infcx.tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br)); |
1a4d82fc JJ |
443 | } |
444 | } | |
54a0048b | 445 | span_bug!( |
1a4d82fc | 446 | span, |
54a0048b SL |
447 | "could not find original bound region for {:?}", |
448 | r); | |
1a4d82fc JJ |
449 | } |
450 | ||
9e0c209e SL |
451 | fn fresh_bound_variable<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>, |
452 | debruijn: ty::DebruijnIndex) | |
453 | -> &'tcx ty::Region { | |
1a4d82fc JJ |
454 | infcx.region_vars.new_bound(debruijn) |
455 | } | |
456 | } | |
457 | } | |
458 | ||
a7813a04 | 459 | fn var_ids<'a, 'gcx, 'tcx>(fields: &CombineFields<'a, 'gcx, 'tcx>, |
9e0c209e | 460 | map: &FnvHashMap<ty::BoundRegion, &'tcx ty::Region>) |
a7813a04 | 461 | -> Vec<ty::RegionVid> { |
c34b1796 | 462 | map.iter() |
9e0c209e | 463 | .map(|(_, &r)| match *r { |
e9174d1e | 464 | ty::ReVar(r) => { r } |
9e0c209e | 465 | _ => { |
54a0048b | 466 | span_bug!( |
c34b1796 | 467 | fields.trace.origin.span(), |
54a0048b SL |
468 | "found non-region-vid: {:?}", |
469 | r); | |
c34b1796 AL |
470 | } |
471 | }) | |
472 | .collect() | |
1a4d82fc JJ |
473 | } |
474 | ||
9e0c209e SL |
475 | fn is_var_in_set(new_vars: &[ty::RegionVid], r: &ty::Region) -> bool { |
476 | match *r { | |
e9174d1e | 477 | ty::ReVar(ref v) => new_vars.iter().any(|x| x == v), |
1a4d82fc JJ |
478 | _ => false |
479 | } | |
480 | } | |
481 | ||
a7813a04 XL |
482 | fn fold_regions_in<'a, 'gcx, 'tcx, T, F>(tcx: TyCtxt<'a, 'gcx, 'tcx>, |
483 | unbound_value: &T, | |
484 | mut fldr: F) | |
485 | -> T | |
c34b1796 | 486 | where T: TypeFoldable<'tcx>, |
9e0c209e | 487 | F: FnMut(&'tcx ty::Region, ty::DebruijnIndex) -> &'tcx ty::Region, |
1a4d82fc | 488 | { |
e9174d1e | 489 | tcx.fold_regions(unbound_value, &mut false, |region, current_depth| { |
1a4d82fc JJ |
490 | // we should only be encountering "escaping" late-bound regions here, |
491 | // because the ones at the current level should have been replaced | |
492 | // with fresh variables | |
9e0c209e | 493 | assert!(match *region { |
1a4d82fc JJ |
494 | ty::ReLateBound(..) => false, |
495 | _ => true | |
496 | }); | |
497 | ||
498 | fldr(region, ty::DebruijnIndex::new(current_depth)) | |
c1a9b12d | 499 | }) |
1a4d82fc JJ |
500 | } |
501 | ||
a7813a04 | 502 | impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> { |
3157f602 XL |
503 | fn tainted_regions(&self, |
504 | snapshot: &CombinedSnapshot, | |
9e0c209e | 505 | r: &'tcx ty::Region, |
3157f602 | 506 | directions: TaintDirections) |
9e0c209e | 507 | -> FnvHashSet<&'tcx ty::Region> { |
3157f602 | 508 | self.region_vars.tainted(&snapshot.region_vars_snapshot, r, directions) |
1a4d82fc JJ |
509 | } |
510 | ||
511 | fn region_vars_confined_to_snapshot(&self, | |
512 | snapshot: &CombinedSnapshot) | |
513 | -> Vec<ty::RegionVid> | |
514 | { | |
515 | /*! | |
516 | * Returns the set of region variables that do not affect any | |
517 | * types/regions which existed before `snapshot` was | |
518 | * started. This is used in the sub/lub/glb computations. The | |
519 | * idea here is that when we are computing lub/glb of two | |
520 | * regions, we sometimes create intermediate region variables. | |
521 | * Those region variables may touch some of the skolemized or | |
522 | * other "forbidden" regions we created to replace bound | |
523 | * regions, but they don't really represent an "external" | |
524 | * constraint. | |
525 | * | |
526 | * However, sometimes fresh variables are created for other | |
527 | * purposes too, and those *may* represent an external | |
528 | * constraint. In particular, when a type variable is | |
529 | * instantiated, we create region variables for all the | |
530 | * regions that appear within, and if that type variable | |
531 | * pre-existed the snapshot, then those region variables | |
532 | * represent external constraints. | |
533 | * | |
534 | * An example appears in the unit test | |
535 | * `sub_free_bound_false_infer`. In this test, we want to | |
536 | * know whether | |
537 | * | |
538 | * ```rust | |
539 | * fn(_#0t) <: for<'a> fn(&'a int) | |
540 | * ``` | |
541 | * | |
542 | * Note that the subtype has a type variable. Because the type | |
543 | * variable can't be instantiated with a region that is bound | |
544 | * in the fn signature, this comparison ought to fail. But if | |
545 | * we're not careful, it will succeed. | |
546 | * | |
547 | * The reason is that when we walk through the subtyping | |
548 | * algorith, we begin by replacing `'a` with a skolemized | |
549 | * variable `'1`. We then have `fn(_#0t) <: fn(&'1 int)`. This | |
550 | * can be made true by unifying `_#0t` with `&'1 int`. In the | |
551 | * process, we create a fresh variable for the skolemized | |
552 | * region, `'$2`, and hence we have that `_#0t == &'$2 | |
553 | * int`. However, because `'$2` was created during the sub | |
554 | * computation, if we're not careful we will erroneously | |
555 | * assume it is one of the transient region variables | |
556 | * representing a lub/glb internally. Not good. | |
557 | * | |
558 | * To prevent this, we check for type variables which were | |
559 | * unified during the snapshot, and say that any region | |
560 | * variable created during the snapshot but which finds its | |
561 | * way into a type variable is considered to "escape" the | |
562 | * snapshot. | |
563 | */ | |
564 | ||
565 | let mut region_vars = | |
566 | self.region_vars.vars_created_since_snapshot(&snapshot.region_vars_snapshot); | |
567 | ||
568 | let escaping_types = | |
54a0048b | 569 | self.type_variables.borrow_mut().types_escaping_snapshot(&snapshot.type_snapshot); |
1a4d82fc | 570 | |
c1a9b12d SL |
571 | let mut escaping_region_vars = FnvHashSet(); |
572 | for ty in &escaping_types { | |
e9174d1e | 573 | self.tcx.collect_regions(ty, &mut escaping_region_vars); |
c1a9b12d | 574 | } |
1a4d82fc JJ |
575 | |
576 | region_vars.retain(|®ion_vid| { | |
e9174d1e | 577 | let r = ty::ReVar(region_vid); |
1a4d82fc JJ |
578 | !escaping_region_vars.contains(&r) |
579 | }); | |
580 | ||
62682a34 SL |
581 | debug!("region_vars_confined_to_snapshot: region_vars={:?} escaping_types={:?}", |
582 | region_vars, | |
583 | escaping_types); | |
1a4d82fc JJ |
584 | |
585 | region_vars | |
586 | } | |
1a4d82fc | 587 | |
3157f602 XL |
588 | /// Replace all regions bound by `binder` with skolemized regions and |
589 | /// return a map indicating which bound-region was replaced with what | |
590 | /// skolemized region. This is the first step of checking subtyping | |
591 | /// when higher-ranked things are involved. | |
592 | /// | |
593 | /// **Important:** you must call this function from within a snapshot. | |
594 | /// Moreover, before committing the snapshot, you must eventually call | |
595 | /// either `plug_leaks` or `pop_skolemized` to remove the skolemized | |
596 | /// regions. If you rollback the snapshot (or are using a probe), then | |
597 | /// the pop occurs as part of the rollback, so an explicit call is not | |
598 | /// needed (but is also permitted). | |
599 | /// | |
600 | /// See `README.md` for more details. | |
a7813a04 XL |
601 | pub fn skolemize_late_bound_regions<T>(&self, |
602 | binder: &ty::Binder<T>, | |
603 | snapshot: &CombinedSnapshot) | |
9e0c209e | 604 | -> (T, SkolemizationMap<'tcx>) |
a7813a04 XL |
605 | where T : TypeFoldable<'tcx> |
606 | { | |
a7813a04 | 607 | let (result, map) = self.tcx.replace_late_bound_regions(binder, |br| { |
3157f602 | 608 | self.region_vars.push_skolemized(br, &snapshot.region_vars_snapshot) |
a7813a04 | 609 | }); |
1a4d82fc | 610 | |
a7813a04 XL |
611 | debug!("skolemize_bound_regions(binder={:?}, result={:?}, map={:?})", |
612 | binder, | |
613 | result, | |
614 | map); | |
1a4d82fc | 615 | |
a7813a04 | 616 | (result, map) |
1a4d82fc | 617 | } |
1a4d82fc | 618 | |
3157f602 XL |
619 | /// Searches the region constriants created since `snapshot` was started |
620 | /// and checks to determine whether any of the skolemized regions created | |
621 | /// in `skol_map` would "escape" -- meaning that they are related to | |
622 | /// other regions in some way. If so, the higher-ranked subtyping doesn't | |
623 | /// hold. See `README.md` for more details. | |
a7813a04 XL |
624 | pub fn leak_check(&self, |
625 | overly_polymorphic: bool, | |
3157f602 | 626 | span: Span, |
9e0c209e | 627 | skol_map: &SkolemizationMap<'tcx>, |
a7813a04 XL |
628 | snapshot: &CombinedSnapshot) |
629 | -> RelateResult<'tcx, ()> | |
630 | { | |
a7813a04 XL |
631 | debug!("leak_check: skol_map={:?}", |
632 | skol_map); | |
633 | ||
3157f602 XL |
634 | // ## Issue #32330 warnings |
635 | // | |
636 | // When Issue #32330 is fixed, a certain number of late-bound | |
637 | // regions (LBR) will become early-bound. We wish to issue | |
638 | // warnings when the result of `leak_check` relies on such LBR, as | |
639 | // that means that compilation will likely start to fail. | |
640 | // | |
641 | // Recall that when we do a "HR subtype" check, we replace all | |
642 | // late-bound regions (LBR) in the subtype with fresh variables, | |
643 | // and skolemize the late-bound regions in the supertype. If those | |
644 | // skolemized regions from the supertype wind up being | |
645 | // super-regions (directly or indirectly) of either | |
646 | // | |
647 | // - another skolemized region; or, | |
648 | // - some region that pre-exists the HR subtype check | |
649 | // - e.g., a region variable that is not one of those created | |
650 | // to represent bound regions in the subtype | |
651 | // | |
652 | // then leak-check (and hence the subtype check) fails. | |
653 | // | |
654 | // What will change when we fix #32330 is that some of the LBR in the | |
655 | // subtype may become early-bound. In that case, they would no longer be in | |
656 | // the "permitted set" of variables that can be related to a skolemized | |
657 | // type. | |
658 | // | |
659 | // So the foundation for this warning is to collect variables that we found | |
660 | // to be related to a skolemized type. For each of them, we have a | |
661 | // `BoundRegion` which carries a `Issue32330` flag. We check whether any of | |
662 | // those flags indicate that this variable was created from a lifetime | |
663 | // that will change from late- to early-bound. If so, we issue a warning | |
664 | // indicating that the results of compilation may change. | |
665 | // | |
666 | // This is imperfect, since there are other kinds of code that will not | |
667 | // compile once #32330 is fixed. However, it fixes the errors observed in | |
668 | // practice on crater runs. | |
669 | let mut warnings = vec![]; | |
670 | ||
a7813a04 XL |
671 | let new_vars = self.region_vars_confined_to_snapshot(snapshot); |
672 | for (&skol_br, &skol) in skol_map { | |
3157f602 XL |
673 | // The inputs to a skolemized variable can only |
674 | // be itself or other new variables. | |
675 | let incoming_taints = self.tainted_regions(snapshot, | |
676 | skol, | |
677 | TaintDirections::both()); | |
678 | for &tainted_region in &incoming_taints { | |
a7813a04 XL |
679 | // Each skolemized should only be relatable to itself |
680 | // or new variables: | |
9e0c209e | 681 | match *tainted_region { |
a7813a04 | 682 | ty::ReVar(vid) => { |
3157f602 XL |
683 | if new_vars.contains(&vid) { |
684 | warnings.extend( | |
685 | match self.region_vars.var_origin(vid) { | |
686 | LateBoundRegion(_, | |
9e0c209e | 687 | ty::BrNamed(.., wc), |
3157f602 XL |
688 | _) => Some(wc), |
689 | _ => None, | |
690 | }); | |
691 | continue; | |
692 | } | |
a7813a04 XL |
693 | } |
694 | _ => { | |
695 | if tainted_region == skol { continue; } | |
696 | } | |
697 | }; | |
698 | ||
699 | debug!("{:?} (which replaced {:?}) is tainted by {:?}", | |
700 | skol, | |
701 | skol_br, | |
702 | tainted_region); | |
703 | ||
704 | if overly_polymorphic { | |
705 | debug!("Overly polymorphic!"); | |
706 | return Err(TypeError::RegionsOverlyPolymorphic(skol_br, | |
707 | tainted_region)); | |
708 | } else { | |
709 | debug!("Not as polymorphic!"); | |
710 | return Err(TypeError::RegionsInsufficientlyPolymorphic(skol_br, | |
711 | tainted_region)); | |
712 | } | |
1a4d82fc JJ |
713 | } |
714 | } | |
3157f602 XL |
715 | |
716 | self.issue_32330_warnings(span, &warnings); | |
717 | ||
a7813a04 XL |
718 | Ok(()) |
719 | } | |
720 | ||
721 | /// This code converts from skolemized regions back to late-bound | |
722 | /// regions. It works by replacing each region in the taint set of a | |
723 | /// skolemized region with a bound-region. The bound region will be bound | |
724 | /// by the outer-most binder in `value`; the caller must ensure that there is | |
725 | /// such a binder and it is the right place. | |
726 | /// | |
727 | /// This routine is only intended to be used when the leak-check has | |
728 | /// passed; currently, it's used in the trait matching code to create | |
729 | /// a set of nested obligations frmo an impl that matches against | |
730 | /// something higher-ranked. More details can be found in | |
731 | /// `librustc/middle/traits/README.md`. | |
732 | /// | |
733 | /// As a brief example, consider the obligation `for<'a> Fn(&'a int) | |
734 | /// -> &'a int`, and the impl: | |
735 | /// | |
736 | /// impl<A,R> Fn<A,R> for SomethingOrOther | |
737 | /// where A : Clone | |
738 | /// { ... } | |
739 | /// | |
740 | /// Here we will have replaced `'a` with a skolemized region | |
741 | /// `'0`. This means that our substitution will be `{A=>&'0 | |
742 | /// int, R=>&'0 int}`. | |
743 | /// | |
744 | /// When we apply the substitution to the bounds, we will wind up with | |
745 | /// `&'0 int : Clone` as a predicate. As a last step, we then go and | |
746 | /// replace `'0` with a late-bound region `'a`. The depth is matched | |
747 | /// to the depth of the predicate, in this case 1, so that the final | |
748 | /// predicate is `for<'a> &'a int : Clone`. | |
749 | pub fn plug_leaks<T>(&self, | |
9e0c209e | 750 | skol_map: SkolemizationMap<'tcx>, |
a7813a04 XL |
751 | snapshot: &CombinedSnapshot, |
752 | value: &T) -> T | |
753 | where T : TypeFoldable<'tcx> | |
754 | { | |
a7813a04 XL |
755 | debug!("plug_leaks(skol_map={:?}, value={:?})", |
756 | skol_map, | |
757 | value); | |
758 | ||
759 | // Compute a mapping from the "taint set" of each skolemized | |
760 | // region back to the `ty::BoundRegion` that it originally | |
761 | // represented. Because `leak_check` passed, we know that | |
762 | // these taint sets are mutually disjoint. | |
9e0c209e | 763 | let inv_skol_map: FnvHashMap<&'tcx ty::Region, ty::BoundRegion> = |
a7813a04 | 764 | skol_map |
3157f602 XL |
765 | .iter() |
766 | .flat_map(|(&skol_br, &skol)| { | |
767 | self.tainted_regions(snapshot, skol, TaintDirections::both()) | |
a7813a04 XL |
768 | .into_iter() |
769 | .map(move |tainted_region| (tainted_region, skol_br)) | |
770 | }) | |
771 | .collect(); | |
772 | ||
773 | debug!("plug_leaks: inv_skol_map={:?}", | |
774 | inv_skol_map); | |
775 | ||
776 | // Remove any instantiated type variables from `value`; those can hide | |
777 | // references to regions from the `fold_regions` code below. | |
778 | let value = self.resolve_type_vars_if_possible(value); | |
779 | ||
780 | // Map any skolemization byproducts back to a late-bound | |
781 | // region. Put that late-bound region at whatever the outermost | |
782 | // binder is that we encountered in `value`. The caller is | |
783 | // responsible for ensuring that (a) `value` contains at least one | |
784 | // binder and (b) that binder is the one we want to use. | |
785 | let result = self.tcx.fold_regions(&value, &mut false, |r, current_depth| { | |
786 | match inv_skol_map.get(&r) { | |
787 | None => r, | |
788 | Some(br) => { | |
789 | // It is the responsibility of the caller to ensure | |
790 | // that each skolemized region appears within a | |
791 | // binder. In practice, this routine is only used by | |
792 | // trait checking, and all of the skolemized regions | |
793 | // appear inside predicates, which always have | |
794 | // binders, so this assert is satisfied. | |
795 | assert!(current_depth > 1); | |
796 | ||
3157f602 XL |
797 | // since leak-check passed, this skolemized region |
798 | // should only have incoming edges from variables | |
799 | // (which ought not to escape the snapshot, but we | |
800 | // don't check that) or itself | |
801 | assert!( | |
9e0c209e | 802 | match *r { |
3157f602 XL |
803 | ty::ReVar(_) => true, |
804 | ty::ReSkolemized(_, ref br1) => br == br1, | |
805 | _ => false, | |
806 | }, | |
807 | "leak-check would have us replace {:?} with {:?}", | |
808 | r, br); | |
809 | ||
9e0c209e SL |
810 | self.tcx.mk_region(ty::ReLateBound( |
811 | ty::DebruijnIndex::new(current_depth - 1), br.clone())) | |
a7813a04 XL |
812 | } |
813 | } | |
814 | }); | |
1a4d82fc | 815 | |
a7813a04 XL |
816 | debug!("plug_leaks: result={:?}", |
817 | result); | |
1a4d82fc | 818 | |
3157f602 XL |
819 | self.pop_skolemized(skol_map, snapshot); |
820 | ||
821 | debug!("plug_leaks: result={:?}", result); | |
822 | ||
a7813a04 XL |
823 | result |
824 | } | |
3157f602 XL |
825 | |
826 | /// Pops the skolemized regions found in `skol_map` from the region | |
827 | /// inference context. Whenever you create skolemized regions via | |
828 | /// `skolemize_late_bound_regions`, they must be popped before you | |
829 | /// commit the enclosing snapshot (if you do not commit, e.g. within a | |
830 | /// probe or as a result of an error, then this is not necessary, as | |
831 | /// popping happens as part of the rollback). | |
832 | /// | |
833 | /// Note: popping also occurs implicitly as part of `leak_check`. | |
834 | pub fn pop_skolemized(&self, | |
9e0c209e | 835 | skol_map: SkolemizationMap<'tcx>, |
3157f602 XL |
836 | snapshot: &CombinedSnapshot) |
837 | { | |
838 | debug!("pop_skolemized({:?})", skol_map); | |
839 | let skol_regions: FnvHashSet<_> = skol_map.values().cloned().collect(); | |
840 | self.region_vars.pop_skolemized(&skol_regions, &snapshot.region_vars_snapshot); | |
841 | } | |
1a4d82fc | 842 | } |