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.
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.
11 //! Helper routines for higher-ranked things. See the `doc` module at
12 //! the end of the file for details.
14 use super::{CombinedSnapshot
,
20 use super::combine
::CombineFields
;
21 use super::region_inference
::{TaintDirections}
;
23 use ty
::{self, TyCtxt, Binder, TypeFoldable}
;
24 use ty
::error
::TypeError
;
25 use ty
::relate
::{Relate, RelateResult, TypeRelation}
;
27 use util
::nodemap
::{FnvHashMap, FnvHashSet}
;
29 pub struct HrMatchResult
<U
> {
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
>,
42 impl<'a
, 'gcx
, 'tcx
> CombineFields
<'a
, 'gcx
, 'tcx
> {
43 pub fn higher_ranked_sub
<T
>(&mut self, a
: &Binder
<T
>, b
: &Binder
<T
>, a_is_expected
: bool
)
44 -> RelateResult
<'tcx
, Binder
<T
>>
47 debug
!("higher_ranked_sub(a={:?}, b={:?})",
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
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
58 // Start a snapshot so we can examine "all bindings that were
59 // created as part of this type comparison".
60 return self.infcx
.commit_if_ok(|snapshot
| {
61 let span
= self.trace
.origin
.span();
63 // First, we instantiate each bound region in the subtype with a fresh
66 self.infcx
.replace_late_bound_regions_with_fresh_var(
71 // Second, we instantiate each bound region in the supertype with a
72 // fresh concrete region.
73 let (b_prime
, skol_map
) =
74 self.infcx
.skolemize_late_bound_regions(b
, snapshot
);
76 debug
!("a_prime={:?}", a_prime
);
77 debug
!("b_prime={:?}", b_prime
);
79 // Compare types now that bound regions have been replaced.
80 let result
= self.sub(a_is_expected
).relate(&a_prime
, &b_prime
)?
;
82 // Presuming type comparison succeeds, we need to check
83 // that the skolemized regions do not "leak".
84 self.infcx
.leak_check(!a_is_expected
, span
, &skol_map
, snapshot
)?
;
86 // We are finished with the skolemized regions now so pop
88 self.infcx
.pop_skolemized(skol_map
, snapshot
);
90 debug
!("higher_ranked_sub: OK result={:?}", result
);
92 Ok(ty
::Binder(result
))
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.
103 /// This routine is (as of this writing) used in trait matching,
104 /// particularly projection.
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`.
109 pub fn higher_ranked_match
<T
, U
>(&mut self,
111 a_pair
: &Binder
<(T
, U
)>,
114 -> RelateResult
<'tcx
, HrMatchResult
<U
>>
115 where T
: Relate
<'tcx
>,
116 U
: TypeFoldable
<'tcx
>
118 debug
!("higher_ranked_match(a={:?}, b={:?})",
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
);
129 debug
!("higher_ranked_match: a_match={:?}", a_match
);
130 debug
!("higher_ranked_match: skol_map={:?}", skol_map
);
132 // Equate types now that bound regions have been replaced.
133 self.equate(a_is_expected
).relate(&a_match
, &b_match
)?
;
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
<_
, _
> =
141 .map(|(&br
, &skol
)| {
142 let tainted_regions
=
143 self.infcx
.tainted_regions(snapshot
,
145 TaintDirections
::incoming()); // [1]
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
152 (skol
, (br
, tainted_regions
))
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
<_
, _
> =
164 .map(|(&skol
, &(br
, ref regions
))| {
167 .filter(|&&r
| !skol_resolution_map
.contains_key(r
))
170 .unwrap_or_else(|| { // [1]
171 unconstrained_regions
.push(br
);
172 self.infcx
.next_region_var(
173 LateBoundRegion(span
, br
, HigherRankedType
))
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
183 (skol
, representative
)
187 // Equate all the members of each skolemization set with the
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
)
198 let origin
= SubregionOrigin
::Subtype(self.trace
.clone());
199 self.infcx
.region_vars
.make_eqregion(origin
,
205 // Replace the skolemized regions appearing in value with
206 // their representatives
211 |r
, _
| skol_representatives
.get(&r
).cloned().unwrap_or(r
));
213 debug
!("higher_ranked_match: value={:?}", a_value
);
215 // We are now done with these skolemized variables.
216 self.infcx
.pop_skolemized(skol_map
, snapshot
);
220 unconstrained_regions
: unconstrained_regions
,
225 pub fn higher_ranked_lub
<T
>(&mut self, a
: &Binder
<T
>, b
: &Binder
<T
>, a_is_expected
: bool
)
226 -> RelateResult
<'tcx
, Binder
<T
>>
227 where T
: Relate
<'tcx
>
229 // Start a snapshot so we can examine "all bindings that were
230 // created as part of this type comparison".
231 return self.infcx
.commit_if_ok(|snapshot
| {
232 // Instantiate each bound region with a fresh region variable.
233 let span
= self.trace
.origin
.span();
234 let (a_with_fresh
, a_map
) =
235 self.infcx
.replace_late_bound_regions_with_fresh_var(
236 span
, HigherRankedType
, a
);
237 let (b_with_fresh
, _
) =
238 self.infcx
.replace_late_bound_regions_with_fresh_var(
239 span
, HigherRankedType
, b
);
241 // Collect constraints.
243 self.lub(a_is_expected
).relate(&a_with_fresh
, &b_with_fresh
)?
;
245 self.infcx
.resolve_type_vars_if_possible(&result0
);
246 debug
!("lub result0 = {:?}", result0
);
248 // Generalize the regions appearing in result0 if possible
249 let new_vars
= self.infcx
.region_vars_confined_to_snapshot(snapshot
);
250 let span
= self.trace
.origin
.span();
255 |r
, debruijn
| generalize_region(self.infcx
, span
, snapshot
, debruijn
,
256 &new_vars
, &a_map
, r
));
258 debug
!("lub({:?},{:?}) = {:?}",
263 Ok(ty
::Binder(result1
))
266 fn generalize_region
<'a
, 'gcx
, 'tcx
>(infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
268 snapshot
: &CombinedSnapshot
,
269 debruijn
: ty
::DebruijnIndex
,
270 new_vars
: &[ty
::RegionVid
],
271 a_map
: &FnvHashMap
<ty
::BoundRegion
, &'tcx ty
::Region
>,
272 r0
: &'tcx ty
::Region
)
273 -> &'tcx ty
::Region
{
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
);
281 let tainted
= infcx
.tainted_regions(snapshot
, r0
, TaintDirections
::both());
283 // Variables created during LUB computation which are
284 // *related* to regions that pre-date the LUB computation
286 if !tainted
.iter().all(|r
| is_var_in_set(new_vars
, *r
)) {
287 debug
!("generalize_region(r0={:?}): \
288 non-new-variables found in {:?}",
290 assert
!(!r0
.is_bound());
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
299 for (a_br
, a_r
) in a_map
{
300 if tainted
.iter().any(|x
| x
== a_r
) {
301 debug
!("generalize_region(r0={:?}): \
302 replacing with {:?}, tainted={:?}",
304 return infcx
.tcx
.mk_region(ty
::ReLateBound(debruijn
, *a_br
));
310 "region {:?} is not associated with any bound region from A!",
315 pub fn higher_ranked_glb
<T
>(&mut self, a
: &Binder
<T
>, b
: &Binder
<T
>, a_is_expected
: bool
)
316 -> RelateResult
<'tcx
, Binder
<T
>>
317 where T
: Relate
<'tcx
>
319 debug
!("higher_ranked_glb({:?}, {:?})",
322 // Make a snapshot so we can examine "all bindings that were
323 // created as part of this type comparison".
324 return self.infcx
.commit_if_ok(|snapshot
| {
325 // Instantiate each bound region with a fresh region variable.
326 let (a_with_fresh
, a_map
) =
327 self.infcx
.replace_late_bound_regions_with_fresh_var(
328 self.trace
.origin
.span(), HigherRankedType
, a
);
329 let (b_with_fresh
, b_map
) =
330 self.infcx
.replace_late_bound_regions_with_fresh_var(
331 self.trace
.origin
.span(), HigherRankedType
, b
);
332 let a_vars
= var_ids(self, &a_map
);
333 let b_vars
= var_ids(self, &b_map
);
335 // Collect constraints.
337 self.glb(a_is_expected
).relate(&a_with_fresh
, &b_with_fresh
)?
;
339 self.infcx
.resolve_type_vars_if_possible(&result0
);
340 debug
!("glb result0 = {:?}", result0
);
342 // Generalize the regions appearing in result0 if possible
343 let new_vars
= self.infcx
.region_vars_confined_to_snapshot(snapshot
);
344 let span
= self.trace
.origin
.span();
349 |r
, debruijn
| generalize_region(self.infcx
, span
, snapshot
, debruijn
,
351 &a_map
, &a_vars
, &b_vars
,
354 debug
!("glb({:?},{:?}) = {:?}",
359 Ok(ty
::Binder(result1
))
362 fn generalize_region
<'a
, 'gcx
, 'tcx
>(infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
364 snapshot
: &CombinedSnapshot
,
365 debruijn
: ty
::DebruijnIndex
,
366 new_vars
: &[ty
::RegionVid
],
367 a_map
: &FnvHashMap
<ty
::BoundRegion
,
369 a_vars
: &[ty
::RegionVid
],
370 b_vars
: &[ty
::RegionVid
],
371 r0
: &'tcx ty
::Region
)
372 -> &'tcx ty
::Region
{
373 if !is_var_in_set(new_vars
, r0
) {
374 assert
!(!r0
.is_bound());
378 let tainted
= infcx
.tainted_regions(snapshot
, r0
, TaintDirections
::both());
382 let mut only_new_vars
= true;
384 if is_var_in_set(a_vars
, *r
) {
386 return fresh_bound_variable(infcx
, debruijn
);
390 } else if is_var_in_set(b_vars
, *r
) {
392 return fresh_bound_variable(infcx
, debruijn
);
396 } else if !is_var_in_set(new_vars
, *r
) {
397 only_new_vars
= false;
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.
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.
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.
422 if a_r
.is_some() && b_r
.is_some() && only_new_vars
{
423 // Related to exactly one bound variable from each fn:
424 return rev_lookup(infcx
, span
, a_map
, a_r
.unwrap());
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());
431 return fresh_bound_variable(infcx
, debruijn
);
435 fn rev_lookup
<'a
, 'gcx
, 'tcx
>(infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
437 a_map
: &FnvHashMap
<ty
::BoundRegion
, &'tcx ty
::Region
>,
438 r
: &'tcx ty
::Region
) -> &'tcx ty
::Region
440 for (a_br
, a_r
) in a_map
{
442 return infcx
.tcx
.mk_region(ty
::ReLateBound(ty
::DebruijnIndex
::new(1), *a_br
));
447 "could not find original bound region for {:?}",
451 fn fresh_bound_variable
<'a
, 'gcx
, 'tcx
>(infcx
: &InferCtxt
<'a
, 'gcx
, 'tcx
>,
452 debruijn
: ty
::DebruijnIndex
)
453 -> &'tcx ty
::Region
{
454 infcx
.region_vars
.new_bound(debruijn
)
459 fn var_ids
<'a
, 'gcx
, 'tcx
>(fields
: &CombineFields
<'a
, 'gcx
, 'tcx
>,
460 map
: &FnvHashMap
<ty
::BoundRegion
, &'tcx ty
::Region
>)
461 -> Vec
<ty
::RegionVid
> {
463 .map(|(_
, &r
)| match *r
{
464 ty
::ReVar(r
) => { r }
467 fields
.trace
.origin
.span(),
468 "found non-region-vid: {:?}",
475 fn is_var_in_set(new_vars
: &[ty
::RegionVid
], r
: &ty
::Region
) -> bool
{
477 ty
::ReVar(ref v
) => new_vars
.iter().any(|x
| x
== v
),
482 fn fold_regions_in
<'a
, 'gcx
, 'tcx
, T
, F
>(tcx
: TyCtxt
<'a
, 'gcx
, 'tcx
>,
486 where T
: TypeFoldable
<'tcx
>,
487 F
: FnMut(&'tcx ty
::Region
, ty
::DebruijnIndex
) -> &'tcx ty
::Region
,
489 tcx
.fold_regions(unbound_value
, &mut false, |region
, current_depth
| {
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
493 assert
!(match *region
{
494 ty
::ReLateBound(..) => false,
498 fldr(region
, ty
::DebruijnIndex
::new(current_depth
))
502 impl<'a
, 'gcx
, 'tcx
> InferCtxt
<'a
, 'gcx
, 'tcx
> {
503 fn tainted_regions(&self,
504 snapshot
: &CombinedSnapshot
,
506 directions
: TaintDirections
)
507 -> FnvHashSet
<&'tcx ty
::Region
> {
508 self.region_vars
.tainted(&snapshot
.region_vars_snapshot
, r
, directions
)
511 fn region_vars_confined_to_snapshot(&self,
512 snapshot
: &CombinedSnapshot
)
513 -> Vec
<ty
::RegionVid
>
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"
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.
534 * An example appears in the unit test
535 * `sub_free_bound_false_infer`. In this test, we want to
539 * fn(_#0t) <: for<'a> fn(&'a int)
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.
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.
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
565 let mut region_vars
=
566 self.region_vars
.vars_created_since_snapshot(&snapshot
.region_vars_snapshot
);
569 self.type_variables
.borrow_mut().types_escaping_snapshot(&snapshot
.type_snapshot
);
571 let mut escaping_region_vars
= FnvHashSet();
572 for ty
in &escaping_types
{
573 self.tcx
.collect_regions(ty
, &mut escaping_region_vars
);
576 region_vars
.retain(|®ion_vid
| {
577 let r
= ty
::ReVar(region_vid
);
578 !escaping_region_vars
.contains(&r
)
581 debug
!("region_vars_confined_to_snapshot: region_vars={:?} escaping_types={:?}",
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.
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).
600 /// See `README.md` for more details.
601 pub fn skolemize_late_bound_regions
<T
>(&self,
602 binder
: &ty
::Binder
<T
>,
603 snapshot
: &CombinedSnapshot
)
604 -> (T
, SkolemizationMap
<'tcx
>)
605 where T
: TypeFoldable
<'tcx
>
607 let (result
, map
) = self.tcx
.replace_late_bound_regions(binder
, |br
| {
608 self.region_vars
.push_skolemized(br
, &snapshot
.region_vars_snapshot
)
611 debug
!("skolemize_bound_regions(binder={:?}, result={:?}, map={:?})",
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.
624 pub fn leak_check(&self,
625 overly_polymorphic
: bool
,
627 skol_map
: &SkolemizationMap
<'tcx
>,
628 snapshot
: &CombinedSnapshot
)
629 -> RelateResult
<'tcx
, ()>
631 debug
!("leak_check: skol_map={:?}",
634 // ## Issue #32330 warnings
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.
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
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
652 // then leak-check (and hence the subtype check) fails.
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
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.
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
![];
671 let new_vars
= self.region_vars_confined_to_snapshot(snapshot
);
672 for (&skol_br
, &skol
) in skol_map
{
673 // The inputs to a skolemized variable can only
674 // be itself or other new variables.
675 let incoming_taints
= self.tainted_regions(snapshot
,
677 TaintDirections
::both());
678 for &tainted_region
in &incoming_taints
{
679 // Each skolemized should only be relatable to itself
681 match *tainted_region
{
683 if new_vars
.contains(&vid
) {
685 match self.region_vars
.var_origin(vid
) {
695 if tainted_region
== skol { continue; }
699 debug
!("{:?} (which replaced {:?}) is tainted by {:?}",
704 if overly_polymorphic
{
705 debug
!("Overly polymorphic!");
706 return Err(TypeError
::RegionsOverlyPolymorphic(skol_br
,
709 debug
!("Not as polymorphic!");
710 return Err(TypeError
::RegionsInsufficientlyPolymorphic(skol_br
,
716 self.issue_32330_warnings(span
, &warnings
);
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.
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`.
733 /// As a brief example, consider the obligation `for<'a> Fn(&'a int)
734 /// -> &'a int`, and the impl:
736 /// impl<A,R> Fn<A,R> for SomethingOrOther
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}`.
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,
750 skol_map
: SkolemizationMap
<'tcx
>,
751 snapshot
: &CombinedSnapshot
,
753 where T
: TypeFoldable
<'tcx
>
755 debug
!("plug_leaks(skol_map={:?}, value={:?})",
759 if skol_map
.is_empty() {
763 // Compute a mapping from the "taint set" of each skolemized
764 // region back to the `ty::BoundRegion` that it originally
765 // represented. Because `leak_check` passed, we know that
766 // these taint sets are mutually disjoint.
767 let inv_skol_map
: FnvHashMap
<&'tcx ty
::Region
, ty
::BoundRegion
> =
770 .flat_map(|(&skol_br
, &skol
)| {
771 self.tainted_regions(snapshot
, skol
, TaintDirections
::both())
773 .map(move |tainted_region
| (tainted_region
, skol_br
))
777 debug
!("plug_leaks: inv_skol_map={:?}",
780 // Remove any instantiated type variables from `value`; those can hide
781 // references to regions from the `fold_regions` code below.
782 let value
= self.resolve_type_vars_if_possible(&value
);
784 // Map any skolemization byproducts back to a late-bound
785 // region. Put that late-bound region at whatever the outermost
786 // binder is that we encountered in `value`. The caller is
787 // responsible for ensuring that (a) `value` contains at least one
788 // binder and (b) that binder is the one we want to use.
789 let result
= self.tcx
.fold_regions(&value
, &mut false, |r
, current_depth
| {
790 match inv_skol_map
.get(&r
) {
793 // It is the responsibility of the caller to ensure
794 // that each skolemized region appears within a
795 // binder. In practice, this routine is only used by
796 // trait checking, and all of the skolemized regions
797 // appear inside predicates, which always have
798 // binders, so this assert is satisfied.
799 assert
!(current_depth
> 1);
801 // since leak-check passed, this skolemized region
802 // should only have incoming edges from variables
803 // (which ought not to escape the snapshot, but we
804 // don't check that) or itself
807 ty
::ReVar(_
) => true,
808 ty
::ReSkolemized(_
, ref br1
) => br
== br1
,
811 "leak-check would have us replace {:?} with {:?}",
814 self.tcx
.mk_region(ty
::ReLateBound(
815 ty
::DebruijnIndex
::new(current_depth
- 1), br
.clone()))
820 self.pop_skolemized(skol_map
, snapshot
);
822 debug
!("plug_leaks: result={:?}", result
);
827 /// Pops the skolemized regions found in `skol_map` from the region
828 /// inference context. Whenever you create skolemized regions via
829 /// `skolemize_late_bound_regions`, they must be popped before you
830 /// commit the enclosing snapshot (if you do not commit, e.g. within a
831 /// probe or as a result of an error, then this is not necessary, as
832 /// popping happens as part of the rollback).
834 /// Note: popping also occurs implicitly as part of `leak_check`.
835 pub fn pop_skolemized(&self,
836 skol_map
: SkolemizationMap
<'tcx
>,
837 snapshot
: &CombinedSnapshot
)
839 debug
!("pop_skolemized({:?})", skol_map
);
840 let skol_regions
: FnvHashSet
<_
> = skol_map
.values().cloned().collect();
841 self.region_vars
.pop_skolemized(&skol_regions
, &snapshot
.region_vars_snapshot
);
842 if !skol_map
.is_empty() {
843 self.projection_cache
.borrow_mut().rollback_skolemized(
844 &snapshot
.projection_cache_snapshot
);