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