src/librustc/middle/infer/higher_ranked/mod.rs

   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
  14 use super::{CombinedSnapshot, cres, InferCtxt, HigherRankedType, SkolemizationMap};
  15 use super::combine::{Combine, Combineable};
  16
  17 use middle::ty::{self, Binder};
  18 use middle::ty_fold::{self, TypeFoldable};
  19 use syntax::codemap::Span;
  20 use util::nodemap::{FnvHashMap, FnvHashSet};
  21 use util::ppaux::Repr;
  22
  23 pub trait HigherRankedRelations<'tcx> {
  24     fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> cres<'tcx, Binder<T>>
  25         where T : Combineable<'tcx>;
  26
  27     fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> cres<'tcx, Binder<T>>
  28         where T : Combineable<'tcx>;
  29
  30     fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> cres<'tcx, Binder<T>>
  31         where T : Combineable<'tcx>;
  32 }
  33
  34 trait InferCtxtExt<'tcx> {
  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
  42 impl<'tcx,C> HigherRankedRelations<'tcx> for C
  43     where C : Combine<'tcx>
  44 {
  45     fn higher_ranked_sub<T>(&self, a: &Binder<T>, b: &Binder<T>)
  46                             -> cres<'tcx, Binder<T>>
  47         where T : Combineable<'tcx>
  48     {
  49         debug!("higher_ranked_sub(a={}, b={})",
  50                a.repr(self.tcx()), b.repr(self.tcx()));
  51
  52         // Rather than checking the subtype relationship between `a` and `b`
  53         // as-is, we need to do some extra work here in order to make sure
  54         // that function subtyping works correctly with respect to regions
  55         //
  56         // Note: this is a subtle algorithm.  For a full explanation,
  57         // please see the large comment at the end of the file in the (inlined) module
  58         // `doc`.
  59
  60         // Start a snapshot so we can examine "all bindings that were
  61         // created as part of this type comparison".
  62         return self.infcx().try(|snapshot| {
  63             // First, we instantiate each bound region in the subtype with a fresh
  64             // region variable.
  65             let (a_prime, _) =
  66                 self.infcx().replace_late_bound_regions_with_fresh_var(
  67                     self.trace().origin.span(),
  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) =
  74                 self.infcx().skolemize_late_bound_regions(b, snapshot);
  75
  76             debug!("a_prime={}", a_prime.repr(self.tcx()));
  77             debug!("b_prime={}", b_prime.repr(self.tcx()));
  78
  79             // Compare types now that bound regions have been replaced.
  80             let result = try!(Combineable::combine(self, &a_prime, &b_prime));
  81
  82             // Presuming type comparison succeeds, we need to check
  83             // that the skolemized regions do not "leak".
  84             match leak_check(self.infcx(), &skol_map, snapshot) {
  85                 Ok(()) => { }
  86                 Err((skol_br, tainted_region)) => {
  87                     if self.a_is_expected() {
  88                         debug!("Not as polymorphic!");
  89                         return Err(ty::terr_regions_insufficiently_polymorphic(skol_br,
  90                                                                                tainted_region));
  91                     } else {
  92                         debug!("Overly polymorphic!");
  93                         return Err(ty::terr_regions_overly_polymorphic(skol_br,
  94                                                                        tainted_region));
  95                     }
  96                 }
  97             }
  98
  99             debug!("higher_ranked_sub: OK result={}",
 100                    result.repr(self.tcx()));
 101
 102             Ok(ty::Binder(result))
 103         });
 104     }
 105
 106     fn higher_ranked_lub<T>(&self, a: &Binder<T>, b: &Binder<T>) -> cres<'tcx, Binder<T>>
 107         where T : Combineable<'tcx>
 108     {
 109         // Start a snapshot so we can examine "all bindings that were
 110         // created as part of this type comparison".
 111         return self.infcx().try(|snapshot| {
 112             // Instantiate each bound region with a fresh region variable.
 113             let span = self.trace().origin.span();
 114             let (a_with_fresh, a_map) =
 115                 self.infcx().replace_late_bound_regions_with_fresh_var(
 116                     span, HigherRankedType, a);
 117             let (b_with_fresh, _) =
 118                 self.infcx().replace_late_bound_regions_with_fresh_var(
 119                     span, HigherRankedType, b);
 120
 121             // Collect constraints.
 122             let result0 =
 123                 try!(Combineable::combine(self, &a_with_fresh, &b_with_fresh));
 124             let result0 =
 125                 self.infcx().resolve_type_vars_if_possible(&result0);
 126             debug!("lub result0 = {}", result0.repr(self.tcx()));
 127
 128             // Generalize the regions appearing in result0 if possible
 129             let new_vars = self.infcx().region_vars_confined_to_snapshot(snapshot);
 130             let span = self.trace().origin.span();
 131             let result1 =
 132                 fold_regions_in(
 133                     self.tcx(),
 134                     &result0,
 135                     |r, debruijn| generalize_region(self.infcx(), span, snapshot, debruijn,
 136                                                     new_vars.as_slice(), &a_map, r));
 137
 138             debug!("lub({},{}) = {}",
 139                    a.repr(self.tcx()),
 140                    b.repr(self.tcx()),
 141                    result1.repr(self.tcx()));
 142
 143             Ok(ty::Binder(result1))
 144         });
 145
 146         fn generalize_region(infcx: &InferCtxt,
 147                              span: Span,
 148                              snapshot: &CombinedSnapshot,
 149                              debruijn: ty::DebruijnIndex,
 150                              new_vars: &[ty::RegionVid],
 151                              a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
 152                              r0: ty::Region)
 153                              -> ty::Region {
 154             // Regions that pre-dated the LUB computation stay as they are.
 155             if !is_var_in_set(new_vars, r0) {
 156                 assert!(!r0.is_bound());
 157                 debug!("generalize_region(r0={:?}): not new variable", r0);
 158                 return r0;
 159             }
 160
 161             let tainted = infcx.tainted_regions(snapshot, r0);
 162
 163             // Variables created during LUB computation which are
 164             // *related* to regions that pre-date the LUB computation
 165             // stay as they are.
 166             if !tainted.iter().all(|r| is_var_in_set(new_vars, *r)) {
 167                 debug!("generalize_region(r0={:?}): \
 168                         non-new-variables found in {:?}",
 169                        r0, tainted);
 170                 assert!(!r0.is_bound());
 171                 return r0;
 172             }
 173
 174             // Otherwise, the variable must be associated with at
 175             // least one of the variables representing bound regions
 176             // in both A and B.  Replace the variable with the "first"
 177             // bound region from A that we find it to be associated
 178             // with.
 179             for (a_br, a_r) in a_map.iter() {
 180                 if tainted.iter().any(|x| x == a_r) {
 181                     debug!("generalize_region(r0={:?}): \
 182                             replacing with {:?}, tainted={:?}",
 183                            r0, *a_br, tainted);
 184                     return ty::ReLateBound(debruijn, *a_br);
 185                 }
 186             }
 187
 188             infcx.tcx.sess.span_bug(
 189                 span,
 190                 &format!("region {:?} is not associated with \
 191                          any bound region from A!",
 192                         r0)[])
 193         }
 194     }
 195
 196     fn higher_ranked_glb<T>(&self, a: &Binder<T>, b: &Binder<T>) -> cres<'tcx, Binder<T>>
 197         where T : Combineable<'tcx>
 198     {
 199         debug!("{}.higher_ranked_glb({}, {})",
 200                self.tag(), a.repr(self.tcx()), b.repr(self.tcx()));
 201
 202         // Make a snapshot so we can examine "all bindings that were
 203         // created as part of this type comparison".
 204         return self.infcx().try(|snapshot| {
 205             // Instantiate each bound region with a fresh region variable.
 206             let (a_with_fresh, a_map) =
 207                 self.infcx().replace_late_bound_regions_with_fresh_var(
 208                     self.trace().origin.span(), HigherRankedType, a);
 209             let (b_with_fresh, b_map) =
 210                 self.infcx().replace_late_bound_regions_with_fresh_var(
 211                     self.trace().origin.span(), HigherRankedType, b);
 212             let a_vars = var_ids(self, &a_map);
 213             let b_vars = var_ids(self, &b_map);
 214
 215             // Collect constraints.
 216             let result0 =
 217                 try!(Combineable::combine(self, &a_with_fresh, &b_with_fresh));
 218             let result0 =
 219                 self.infcx().resolve_type_vars_if_possible(&result0);
 220             debug!("glb result0 = {}", result0.repr(self.tcx()));
 221
 222             // Generalize the regions appearing in result0 if possible
 223             let new_vars = self.infcx().region_vars_confined_to_snapshot(snapshot);
 224             let span = self.trace().origin.span();
 225             let result1 =
 226                 fold_regions_in(
 227                     self.tcx(),
 228                     &result0,
 229                     |r, debruijn| generalize_region(self.infcx(), span, snapshot, debruijn,
 230                                                     new_vars.as_slice(),
 231                                                     &a_map, a_vars.as_slice(), b_vars.as_slice(),
 232                                                     r));
 233
 234             debug!("glb({},{}) = {}",
 235                    a.repr(self.tcx()),
 236                    b.repr(self.tcx()),
 237                    result1.repr(self.tcx()));
 238
 239             Ok(ty::Binder(result1))
 240         });
 241
 242         fn generalize_region(infcx: &InferCtxt,
 243                              span: Span,
 244                              snapshot: &CombinedSnapshot,
 245                              debruijn: ty::DebruijnIndex,
 246                              new_vars: &[ty::RegionVid],
 247                              a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
 248                              a_vars: &[ty::RegionVid],
 249                              b_vars: &[ty::RegionVid],
 250                              r0: ty::Region) -> ty::Region {
 251             if !is_var_in_set(new_vars, r0) {
 252                 assert!(!r0.is_bound());
 253                 return r0;
 254             }
 255
 256             let tainted = infcx.tainted_regions(snapshot, r0);
 257
 258             let mut a_r = None;
 259             let mut b_r = None;
 260             let mut only_new_vars = true;
 261             for r in tainted.iter() {
 262                 if is_var_in_set(a_vars, *r) {
 263                     if a_r.is_some() {
 264                         return fresh_bound_variable(infcx, debruijn);
 265                     } else {
 266                         a_r = Some(*r);
 267                     }
 268                 } else if is_var_in_set(b_vars, *r) {
 269                     if b_r.is_some() {
 270                         return fresh_bound_variable(infcx, debruijn);
 271                     } else {
 272                         b_r = Some(*r);
 273                     }
 274                 } else if !is_var_in_set(new_vars, *r) {
 275                     only_new_vars = false;
 276                 }
 277             }
 278
 279             // NB---I do not believe this algorithm computes
 280             // (necessarily) the GLB.  As written it can
 281             // spuriously fail. In particular, if there is a case
 282             // like: |fn(&a)| and fn(fn(&b)), where a and b are
 283             // free, it will return fn(&c) where c = GLB(a,b).  If
 284             // however this GLB is not defined, then the result is
 285             // an error, even though something like
 286             // "fn<X>(fn(&X))" where X is bound would be a
 287             // subtype of both of those.
 288             //
 289             // The problem is that if we were to return a bound
 290             // variable, we'd be computing a lower-bound, but not
 291             // necessarily the *greatest* lower-bound.
 292             //
 293             // Unfortunately, this problem is non-trivial to solve,
 294             // because we do not know at the time of computing the GLB
 295             // whether a GLB(a,b) exists or not, because we haven't
 296             // run region inference (or indeed, even fully computed
 297             // the region hierarchy!). The current algorithm seems to
 298             // works ok in practice.
 299
 300             if a_r.is_some() && b_r.is_some() && only_new_vars {
 301                 // Related to exactly one bound variable from each fn:
 302                 return rev_lookup(infcx, span, a_map, a_r.unwrap());
 303             } else if a_r.is_none() && b_r.is_none() {
 304                 // Not related to bound variables from either fn:
 305                 assert!(!r0.is_bound());
 306                 return r0;
 307             } else {
 308                 // Other:
 309                 return fresh_bound_variable(infcx, debruijn);
 310             }
 311         }
 312
 313         fn rev_lookup(infcx: &InferCtxt,
 314                       span: Span,
 315                       a_map: &FnvHashMap<ty::BoundRegion, ty::Region>,
 316                       r: ty::Region) -> ty::Region
 317         {
 318             for (a_br, a_r) in a_map.iter() {
 319                 if *a_r == r {
 320                     return ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br);
 321                 }
 322             }
 323             infcx.tcx.sess.span_bug(
 324                 span,
 325                 &format!("could not find original bound region for {:?}", r)[]);
 326         }
 327
 328         fn fresh_bound_variable(infcx: &InferCtxt, debruijn: ty::DebruijnIndex) -> ty::Region {
 329             infcx.region_vars.new_bound(debruijn)
 330         }
 331     }
 332 }
 333
 334 fn var_ids<'tcx, T: Combine<'tcx>>(combiner: &T,
 335                                    map: &FnvHashMap<ty::BoundRegion, ty::Region>)
 336                                    -> Vec<ty::RegionVid> {
 337     map.iter().map(|(_, r)| match *r {
 338             ty::ReInfer(ty::ReVar(r)) => { r }
 339             r => {
 340                 combiner.infcx().tcx.sess.span_bug(
 341                     combiner.trace().origin.span(),
 342                     &format!("found non-region-vid: {:?}", r)[]);
 343             }
 344         }).collect()
 345 }
 346
 347 fn is_var_in_set(new_vars: &[ty::RegionVid], r: ty::Region) -> bool {
 348     match r {
 349         ty::ReInfer(ty::ReVar(ref v)) => new_vars.iter().any(|x| x == v),
 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
 358     where T : Combineable<'tcx>,
 359           F : FnMut(ty::Region, ty::DebruijnIndex) -> ty::Region,
 360 {
 361     unbound_value.fold_with(&mut ty_fold::RegionFolder::new(tcx, &mut |region, current_depth| {
 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))
 371     }))
 372 }
 373
 374 impl<'a,'tcx> InferCtxtExt<'tcx> for InferCtxt<'a,'tcx> {
 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
 439         let escaping_region_vars: FnvHashSet<_> =
 440             escaping_types
 441             .iter()
 442             .flat_map(|&t| ty_fold::collect_regions(self.tcx, &t).into_iter())
 443             .collect();
 444
 445         region_vars.retain(|&region_vid| {
 446             let r = ty::ReInfer(ty::ReVar(region_vid));
 447             !escaping_region_vars.contains(&r)
 448         });
 449
 450         debug!("region_vars_confined_to_snapshot: region_vars={} escaping_types={}",
 451                region_vars.repr(self.tcx),
 452                escaping_types.repr(self.tcx));
 453
 454         region_vars
 455     }
 456 }
 457
 458 pub fn skolemize_late_bound_regions<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>,
 459                                                binder: &ty::Binder<T>,
 460                                                snapshot: &CombinedSnapshot)
 461                                                -> (T, SkolemizationMap)
 462     where T : TypeFoldable<'tcx> + Repr<'tcx>
 463 {
 464     /*!
 465      * Replace all regions bound by `binder` with skolemized regions and
 466      * return a map indicating which bound-region was replaced with what
 467      * skolemized region. This is the first step of checking subtyping
 468      * when higher-ranked things are involved. See `doc.rs` for more details.
 469      */
 470
 471     let (result, map) = ty::replace_late_bound_regions(infcx.tcx, binder, |br| {
 472         infcx.region_vars.new_skolemized(br, &snapshot.region_vars_snapshot)
 473     });
 474
 475     debug!("skolemize_bound_regions(binder={}, result={}, map={})",
 476            binder.repr(infcx.tcx),
 477            result.repr(infcx.tcx),
 478            map.repr(infcx.tcx));
 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
 493      * hold. See `doc.rs` for more details.
 494      */
 495
 496     debug!("leak_check: skol_map={}",
 497            skol_map.repr(infcx.tcx));
 498
 499     let new_vars = infcx.region_vars_confined_to_snapshot(snapshot);
 500     for (&skol_br, &skol) in skol_map.iter() {
 501         let tainted = infcx.tainted_regions(snapshot, skol);
 502         for &tainted_region in tainted.iter() {
 503             // Each skolemized should only be relatable to itself
 504             // or new variables:
 505             match tainted_region {
 506                 ty::ReInfer(ty::ReVar(vid)) => {
 507                     if new_vars.iter().any(|&x| x == vid) { continue; }
 508                 }
 509                 _ => {
 510                     if tainted_region == skol { continue; }
 511                 }
 512             };
 513
 514             debug!("{} (which replaced {}) is tainted by {}",
 515                    skol.repr(infcx.tcx),
 516                    skol_br.repr(infcx.tcx),
 517                    tainted_region.repr(infcx.tcx));
 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
 536 /// `middle::traits::doc.rs`.
 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
 559     where T : TypeFoldable<'tcx> + Repr<'tcx>
 560 {
 561     debug_assert!(leak_check(infcx, &skol_map, snapshot).is_ok());
 562
 563     debug!("plug_leaks(skol_map={}, value={})",
 564            skol_map.repr(infcx.tcx),
 565            value.repr(infcx.tcx));
 566
 567     // Compute a mapping from the "taint set" of each skolemized
 568     // region back to the `ty::BoundRegion` that it originally
 569     // represented. Because `leak_check` passed, we know that that
 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
 581     debug!("plug_leaks: inv_skol_map={}",
 582            inv_skol_map.repr(infcx.tcx));
 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.
 593     let result = ty_fold::fold_regions(infcx.tcx, &value, |r, current_depth| {
 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
 610     debug!("plug_leaks: result={}",
 611            result.repr(infcx.tcx));
 612
 613     result
 614 }