Auto merge of #50475 - csmoe:debr, r=nikomatsakis

Refactor DebruijnIndex to be 0-based

Fixes #49813

31 files changed, 360 insertions, 184 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 0f8926c6f44..04e57883c77 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -104,16 +104,16 @@ for ty::RegionKind {
                 c.hash_stable(hcx, hasher);
             }
             ty::ReLateBound(db, ty::BrAnon(i)) => {
-                db.depth.hash_stable(hcx, hasher);
+                db.hash_stable(hcx, hasher);
                 i.hash_stable(hcx, hasher);
             }
             ty::ReLateBound(db, ty::BrNamed(def_id, name)) => {
-                db.depth.hash_stable(hcx, hasher);
+                db.hash_stable(hcx, hasher);
                 def_id.hash_stable(hcx, hasher);
                 name.hash_stable(hcx, hasher);
             }
             ty::ReLateBound(db, ty::BrEnv) => {
-                db.depth.hash_stable(hcx, hasher);
+                db.hash_stable(hcx, hasher);
             }
             ty::ReEarlyBound(ty::EarlyBoundRegion { def_id, index, name }) => {
                 def_id.hash_stable(hcx, hasher);
@@ -821,10 +821,6 @@ impl_stable_hash_for!(enum ::middle::resolve_lifetime::Region {
     Free(call_site_scope_data, decl)
 });
 
-impl_stable_hash_for!(struct ty::DebruijnIndex {
-    depth
-});
-
 impl_stable_hash_for!(enum ty::cast::CastKind {
     CoercionCast,
     PtrPtrCast,
diff --git a/src/librustc/infer/error_reporting/nice_region_error/find_anon_type.rs b/src/librustc/infer/error_reporting/nice_region_error/find_anon_type.rs
index dc53c1db06f..13c849ec0b7 100644
--- a/src/librustc/infer/error_reporting/nice_region_error/find_anon_type.rs
+++ b/src/librustc/infer/error_reporting/nice_region_error/find_anon_type.rs
@@ -77,7 +77,7 @@ impl<'a, 'gcx, 'tcx> NiceRegionError<'a, 'gcx, 'tcx> {
             tcx: self.tcx,
             bound_region: *br,
             found_type: None,
-            depth: 1,
+            current_index: ty::DebruijnIndex::INNERMOST,
         };
         nested_visitor.visit_ty(arg);
         nested_visitor.found_type
@@ -99,7 +99,7 @@ struct FindNestedTypeVisitor<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
     // The type where the anonymous lifetime appears
     // for e.g. Vec<`&u8`> and <`&u8`>
     found_type: Option<&'gcx hir::Ty>,
-    depth: u32,
+    current_index: ty::DebruijnIndex,
 }
 
 impl<'a, 'gcx, 'tcx> Visitor<'gcx> for FindNestedTypeVisitor<'a, 'gcx, 'tcx> {
@@ -110,16 +110,16 @@ impl<'a, 'gcx, 'tcx> Visitor<'gcx> for FindNestedTypeVisitor<'a, 'gcx, 'tcx> {
     fn visit_ty(&mut self, arg: &'gcx hir::Ty) {
         match arg.node {
             hir::TyBareFn(_) => {
-                self.depth += 1;
+                self.current_index.shift_in(1);
                 intravisit::walk_ty(self, arg);
-                self.depth -= 1;
+                self.current_index.shift_out(1);
                 return;
             }
 
             hir::TyTraitObject(ref bounds, _) => for bound in bounds {
-                self.depth += 1;
+                self.current_index.shift_in(1);
                 self.visit_poly_trait_ref(bound, hir::TraitBoundModifier::None);
-                self.depth -= 1;
+                self.current_index.shift_out(1);
             },
 
             hir::TyRptr(ref lifetime, _) => {
@@ -135,11 +135,11 @@ impl<'a, 'gcx, 'tcx> Visitor<'gcx> for FindNestedTypeVisitor<'a, 'gcx, 'tcx> {
                     ) => {
                         debug!(
                             "LateBoundAnon depth = {:?} anon_index = {:?} br_index={:?}",
-                            debruijn_index.depth,
+                            debruijn_index,
                             anon_index,
                             br_index
                         );
-                        if debruijn_index.depth == self.depth && anon_index == br_index {
+                        if debruijn_index == self.current_index && anon_index == br_index {
                             self.found_type = Some(arg);
                             return; // we can stop visiting now
                         }
@@ -170,11 +170,11 @@ impl<'a, 'gcx, 'tcx> Visitor<'gcx> for FindNestedTypeVisitor<'a, 'gcx, 'tcx> {
                     ) => {
                         debug!(
                             "FindNestedTypeVisitor::visit_ty: LateBound depth = {:?}",
-                            debruijn_index.depth
+                            debruijn_index
                         );
                         debug!("self.infcx.tcx.hir.local_def_id(id)={:?}", id);
                         debug!("def_id={:?}", def_id);
-                        if debruijn_index.depth == self.depth && id == def_id {
+                        if debruijn_index == self.current_index && id == def_id {
                             self.found_type = Some(arg);
                             return; // we can stop visiting now
                         }
@@ -196,7 +196,7 @@ impl<'a, 'gcx, 'tcx> Visitor<'gcx> for FindNestedTypeVisitor<'a, 'gcx, 'tcx> {
                     tcx: self.tcx,
                     found_it: false,
                     bound_region: self.bound_region,
-                    depth: self.depth,
+                    current_index: self.current_index,
                 };
                 intravisit::walk_ty(subvisitor, arg); // call walk_ty; as visit_ty is empty,
                                                       // this will visit only outermost type
@@ -222,7 +222,7 @@ struct TyPathVisitor<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'gcx, 'tcx>,
     found_it: bool,
     bound_region: ty::BoundRegion,
-    depth: u32,
+    current_index: ty::DebruijnIndex,
 }
 
 impl<'a, 'gcx, 'tcx> Visitor<'gcx> for TyPathVisitor<'a, 'gcx, 'tcx> {
@@ -235,7 +235,7 @@ impl<'a, 'gcx, 'tcx> Visitor<'gcx> for TyPathVisitor<'a, 'gcx, 'tcx> {
         match (self.tcx.named_region(hir_id), self.bound_region) {
             // the lifetime of the TyPath!
             (Some(rl::Region::LateBoundAnon(debruijn_index, anon_index)), ty::BrAnon(br_index)) => {
-                if debruijn_index.depth == self.depth && anon_index == br_index {
+                if debruijn_index == self.current_index && anon_index == br_index {
                     self.found_it = true;
                     return;
                 }
@@ -257,11 +257,11 @@ impl<'a, 'gcx, 'tcx> Visitor<'gcx> for TyPathVisitor<'a, 'gcx, 'tcx> {
             (Some(rl::Region::LateBound(debruijn_index, id, _)), ty::BrNamed(def_id, _)) => {
                 debug!(
                     "FindNestedTypeVisitor::visit_ty: LateBound depth = {:?}",
-                    debruijn_index.depth
+                    debruijn_index,
                 );
                 debug!("id={:?}", id);
                 debug!("def_id={:?}", def_id);
-                if debruijn_index.depth == self.depth && id == def_id {
+                if debruijn_index == self.current_index && id == def_id {
                     self.found_it = true;
                     return; // we can stop visiting now
                 }
diff --git a/src/librustc/infer/higher_ranked/mod.rs b/src/librustc/infer/higher_ranked/mod.rs
index acd5c44c1a4..cd73da9adc8 100644
--- a/src/librustc/infer/higher_ranked/mod.rs
+++ b/src/librustc/infer/higher_ranked/mod.rs
@@ -417,7 +417,8 @@ impl<'a, 'gcx, 'tcx> CombineFields<'a, 'gcx, 'tcx> {
         {
             for (a_br, a_r) in a_map {
                 if *a_r == r {
-                    return infcx.tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1), *a_br));
+                    return infcx.tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::INNERMOST,
+                                                               *a_br));
                 }
             }
             span_bug!(
@@ -473,7 +474,7 @@ fn fold_regions_in<'a, 'gcx, 'tcx, T, F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
             _ => true
         });
 
-        fldr(region, ty::DebruijnIndex::new(current_depth))
+        fldr(region, current_depth)
     })
 }
 
@@ -734,7 +735,7 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                     // trait checking, and all of the skolemized regions
                     // appear inside predicates, which always have
                     // binders, so this assert is satisfied.
-                    assert!(current_depth > 1);
+                    assert!(current_depth > ty::DebruijnIndex::INNERMOST);
 
                     // since leak-check passed, this skolemized region
                     // should only have incoming edges from variables
@@ -750,7 +751,9 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                         r, br);
 
                     self.tcx.mk_region(ty::ReLateBound(
-                        ty::DebruijnIndex::new(current_depth - 1), br.clone()))
+                        current_depth.shifted_out(1),
+                        br.clone(),
+                    ))
                 }
             }
         });
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index 783d4a472a5..da6340b5f61 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -71,6 +71,7 @@
 #![feature(test)]
 #![feature(in_band_lifetimes)]
 #![feature(macro_at_most_once_rep)]
+#![feature(inclusive_range_methods)]
 
 #![recursion_limit="512"]
 
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index 966000ccd90..53d51d9429f 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -98,7 +98,7 @@ impl Region {
     }
 
     fn late(hir_map: &Map, def: &hir::LifetimeDef) -> (hir::LifetimeName, Region) {
-        let depth = ty::DebruijnIndex::new(1);
+        let depth = ty::DebruijnIndex::INNERMOST;
         let def_id = hir_map.local_def_id(def.lifetime.id);
         let origin = LifetimeDefOrigin::from_is_in_band(def.in_band);
         (def.lifetime.name, Region::LateBound(depth, def_id, origin))
@@ -107,7 +107,7 @@ impl Region {
     fn late_anon(index: &Cell<u32>) -> Region {
         let i = index.get();
         index.set(i + 1);
-        let depth = ty::DebruijnIndex::new(1);
+        let depth = ty::DebruijnIndex::INNERMOST;
         Region::LateBoundAnon(depth, i)
     }
 
@@ -123,29 +123,25 @@ impl Region {
 
     fn shifted(self, amount: u32) -> Region {
         match self {
-            Region::LateBound(depth, id, origin) => {
-                Region::LateBound(depth.shifted(amount), id, origin)
+            Region::LateBound(debruijn, id, origin) => {
+                Region::LateBound(debruijn.shifted_in(amount), id, origin)
             }
-            Region::LateBoundAnon(depth, index) => {
-                Region::LateBoundAnon(depth.shifted(amount), index)
+            Region::LateBoundAnon(debruijn, index) => {
+                Region::LateBoundAnon(debruijn.shifted_in(amount), index)
             }
             _ => self,
         }
     }
 
-    fn from_depth(self, depth: u32) -> Region {
+    fn shifted_out_to_binder(self, binder: ty::DebruijnIndex) -> Region {
         match self {
             Region::LateBound(debruijn, id, origin) => Region::LateBound(
-                ty::DebruijnIndex {
-                    depth: debruijn.depth - (depth - 1),
-                },
+                debruijn.shifted_out_to_binder(binder),
                 id,
                 origin,
             ),
             Region::LateBoundAnon(debruijn, index) => Region::LateBoundAnon(
-                ty::DebruijnIndex {
-                    depth: debruijn.depth - (depth - 1),
-                },
+                debruijn.shifted_out_to_binder(binder),
                 index,
             ),
             _ => self,
@@ -1858,7 +1854,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
             .map(|(i, input)| {
                 let mut gather = GatherLifetimes {
                     map: self.map,
-                    binder_depth: 1,
+                    outer_index: ty::DebruijnIndex::INNERMOST,
                     have_bound_regions: false,
                     lifetimes: FxHashSet(),
                 };
@@ -1899,7 +1895,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 
         struct GatherLifetimes<'a> {
             map: &'a NamedRegionMap,
-            binder_depth: u32,
+            outer_index: ty::DebruijnIndex,
             have_bound_regions: bool,
             lifetimes: FxHashSet<Region>,
         }
@@ -1911,7 +1907,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 
             fn visit_ty(&mut self, ty: &hir::Ty) {
                 if let hir::TyBareFn(_) = ty.node {
-                    self.binder_depth += 1;
+                    self.outer_index.shift_in(1);
                 }
                 if let hir::TyTraitObject(ref bounds, ref lifetime) = ty.node {
                     for bound in bounds {
@@ -1927,7 +1923,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     intravisit::walk_ty(self, ty);
                 }
                 if let hir::TyBareFn(_) = ty.node {
-                    self.binder_depth -= 1;
+                    self.outer_index.shift_out(1);
                 }
             }
 
@@ -1946,22 +1942,22 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                 trait_ref: &hir::PolyTraitRef,
                 modifier: hir::TraitBoundModifier,
             ) {
-                self.binder_depth += 1;
+                self.outer_index.shift_in(1);
                 intravisit::walk_poly_trait_ref(self, trait_ref, modifier);
-                self.binder_depth -= 1;
+                self.outer_index.shift_out(1);
             }
 
             fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
                 if let Some(&lifetime) = self.map.defs.get(&lifetime_ref.id) {
                     match lifetime {
                         Region::LateBound(debruijn, _, _) | Region::LateBoundAnon(debruijn, _)
-                            if debruijn.depth < self.binder_depth =>
+                            if debruijn < self.outer_index =>
                         {
                             self.have_bound_regions = true;
                         }
                         _ => {
                             self.lifetimes
-                                .insert(lifetime.from_depth(self.binder_depth));
+                                .insert(lifetime.shifted_out_to_binder(self.outer_index));
                         }
                     }
                 }
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 9d3dda46dad..a533e1a5b9b 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -181,7 +181,7 @@ impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
             let ty_struct = TyS {
                 sty: st,
                 flags: flags.flags,
-                region_depth: flags.depth,
+                outer_exclusive_binder: flags.outer_exclusive_binder,
             };
 
             // Make sure we don't end up with inference
@@ -205,7 +205,7 @@ impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
             let ty_struct = TyS {
                 sty: st,
                 flags: flags.flags,
-                region_depth: flags.depth,
+                outer_exclusive_binder: flags.outer_exclusive_binder,
             };
 
             // This is safe because all the types the ty_struct can point to
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index e913f8f568a..ebbdc928b5d 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -16,13 +16,16 @@ use ty::{self, Ty, TypeFlags, TypeFoldable};
 pub struct FlagComputation {
     pub flags: TypeFlags,
 
-    // maximum depth of any bound region that we have seen thus far
-    pub depth: u32,
+    // see `TyS::outer_exclusive_binder` for details
+    pub outer_exclusive_binder: ty::DebruijnIndex,
 }
 
 impl FlagComputation {
     fn new() -> FlagComputation {
-        FlagComputation { flags: TypeFlags::empty(), depth: 0 }
+        FlagComputation {
+            flags: TypeFlags::empty(),
+            outer_exclusive_binder: ty::DebruijnIndex::INNERMOST,
+        }
     }
 
     pub fn for_sty(st: &ty::TypeVariants) -> FlagComputation {
@@ -35,10 +38,17 @@ impl FlagComputation {
         self.flags = self.flags | (flags & TypeFlags::NOMINAL_FLAGS);
     }
 
-    fn add_depth(&mut self, depth: u32) {
-        if depth > self.depth {
-            self.depth = depth;
-        }
+    /// indicates that `self` refers to something at binding level `binder`
+    fn add_binder(&mut self, binder: ty::DebruijnIndex) {
+        let exclusive_binder = binder.shifted_in(1);
+        self.add_exclusive_binder(exclusive_binder);
+    }
+
+    /// indicates that `self` refers to something *inside* binding
+    /// level `binder` -- not bound by `binder`, but bound by the next
+    /// binder internal to it
+    fn add_exclusive_binder(&mut self, exclusive_binder: ty::DebruijnIndex) {
+        self.outer_exclusive_binder = self.outer_exclusive_binder.max(exclusive_binder);
     }
 
     /// Adds the flags/depth from a set of types that appear within the current type, but within a
@@ -49,9 +59,11 @@ impl FlagComputation {
         // The types that contributed to `computation` occurred within
         // a region binder, so subtract one from the region depth
         // within when adding the depth to `self`.
-        let depth = computation.depth;
-        if depth > 0 {
-            self.add_depth(depth - 1);
+        let outer_exclusive_binder = computation.outer_exclusive_binder;
+        if outer_exclusive_binder > ty::DebruijnIndex::INNERMOST {
+            self.add_exclusive_binder(outer_exclusive_binder.shifted_out(1));
+        } else {
+            // otherwise, this binder captures nothing
         }
     }
 
@@ -194,7 +206,7 @@ impl FlagComputation {
 
     fn add_ty(&mut self, ty: Ty) {
         self.add_flags(ty.flags);
-        self.add_depth(ty.region_depth);
+        self.add_exclusive_binder(ty.outer_exclusive_binder);
     }
 
     fn add_tys(&mut self, tys: &[Ty]) {
@@ -215,7 +227,7 @@ impl FlagComputation {
     fn add_region(&mut self, r: ty::Region) {
         self.add_flags(r.type_flags());
         if let ty::ReLateBound(debruijn, _) = *r {
-            self.add_depth(debruijn.depth);
+            self.add_binder(debruijn);
         }
     }
 
diff --git a/src/librustc/ty/fold.rs b/src/librustc/ty/fold.rs
index 8aca7177d55..dea33ca6947 100644
--- a/src/librustc/ty/fold.rs
+++ b/src/librustc/ty/fold.rs
@@ -63,11 +63,22 @@ pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
         self.super_visit_with(visitor)
     }
 
-    fn has_regions_escaping_depth(&self, depth: u32) -> bool {
-        self.visit_with(&mut HasEscapingRegionsVisitor { depth: depth })
+    /// True if `self` has any late-bound regions that are either
+    /// bound by `binder` or bound by some binder outside of `binder`.
+    /// If `binder` is `ty::DebruijnIndex::INNERMOST`, this indicates whether
+    /// there are any late-bound regions that appear free.
+    fn has_regions_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
+        self.visit_with(&mut HasEscapingRegionsVisitor { outer_index: binder })
     }
+
+    /// True if this `self` has any regions that escape `binder` (and
+    /// hence are not bound by it).
+    fn has_regions_bound_above(&self, binder: ty::DebruijnIndex) -> bool {
+        self.has_regions_bound_at_or_above(binder.shifted_in(1))
+    }
+
     fn has_escaping_regions(&self) -> bool {
-        self.has_regions_escaping_depth(0)
+        self.has_regions_bound_at_or_above(ty::DebruijnIndex::INNERMOST)
     }
 
     fn has_type_flags(&self, flags: TypeFlags) -> bool {
@@ -207,7 +218,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     {
         let mut have_bound_regions = false;
         self.fold_regions(value, &mut have_bound_regions, |r, d| {
-            region_set.insert(self.mk_region(r.from_depth(d)));
+            region_set.insert(self.mk_region(r.shifted_out_to_binder(d)));
             r
         });
         have_bound_regions
@@ -216,13 +227,14 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
     /// Folds the escaping and free regions in `value` using `f`, and
     /// sets `skipped_regions` to true if any late-bound region was found
     /// and skipped.
-    pub fn fold_regions<T,F>(self,
+    pub fn fold_regions<T>(
+        self,
         value: &T,
         skipped_regions: &mut bool,
-        mut f: F)
-        -> T
-        where F : FnMut(ty::Region<'tcx>, u32) -> ty::Region<'tcx>,
-              T : TypeFoldable<'tcx>,
+        mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
+    ) -> T
+    where
+        T : TypeFoldable<'tcx>,
     {
         value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f))
     }
@@ -233,10 +245,30 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         where F: FnMut(ty::Region<'tcx>),
               T: TypeFoldable<'tcx>,
     {
-        value.visit_with(&mut RegionVisitor { current_depth: 0, callback });
+        value.visit_with(&mut RegionVisitor {
+            outer_index: ty::DebruijnIndex::INNERMOST,
+            callback
+        });
 
         struct RegionVisitor<F> {
-            current_depth: u32,
+            /// The index of a binder *just outside* the things we have
+            /// traversed. If we encounter a bound region bound by this
+            /// binder or one outer to it, it appears free. Example:
+            ///
+            /// ```
+            ///    for<'a> fn(for<'b> fn(), T)
+            /// ^          ^          ^     ^
+            /// |          |          |     | here, would be shifted in 1
+            /// |          |          | here, would be shifted in 2
+            /// |          | here, would be INNTERMOST shifted in by 1
+            /// | here, initially, binder would be INNERMOST
+            /// ```
+            ///
+            /// You see that, initially, *any* bound value is free,
+            /// because we've not traversed any binders. As we pass
+            /// through a binder, we shift the `outer_index` by 1 to
+            /// account for the new binder that encloses us.
+            outer_index: ty::DebruijnIndex,
             callback: F,
         }
 
@@ -244,16 +276,16 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
             where F : FnMut(ty::Region<'tcx>)
         {
             fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
-                self.current_depth += 1;
+                self.outer_index.shift_in(1);
                 t.skip_binder().visit_with(self);
-                self.current_depth -= 1;
+                self.outer_index.shift_out(1);
 
                 false // keep visiting
             }
 
             fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
                 match *r {
-                    ty::ReLateBound(debruijn, _) if debruijn.depth <= self.current_depth => {
+                    ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => {
                         /* ignore bound regions */
                     }
                     _ => (self.callback)(r),
@@ -277,21 +309,32 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 pub struct RegionFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'gcx, 'tcx>,
     skipped_regions: &'a mut bool,
-    current_depth: u32,
-    fld_r: &'a mut (dyn FnMut(ty::Region<'tcx>, u32) -> ty::Region<'tcx> + 'a),
+
+    /// Stores the index of a binder *just outside* the stuff we have
+    /// visited.  So this begins as INNERMOST; when we pass through a
+    /// binder, it is incremented (via `shift_in`).
+    current_index: ty::DebruijnIndex,
+
+    /// Callback invokes for each free region. The `DebruijnIndex`
+    /// points to the binder *just outside* the ones we have passed
+    /// through.
+    fold_region_fn: &'a mut (dyn FnMut(
+        ty::Region<'tcx>,
+        ty::DebruijnIndex,
+    ) -> ty::Region<'tcx> + 'a),
 }
 
 impl<'a, 'gcx, 'tcx> RegionFolder<'a, 'gcx, 'tcx> {
-    pub fn new<F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                  skipped_regions: &'a mut bool,
-                  fld_r: &'a mut F) -> RegionFolder<'a, 'gcx, 'tcx>
-        where F : FnMut(ty::Region<'tcx>, u32) -> ty::Region<'tcx>
-    {
+    pub fn new(
+        tcx: TyCtxt<'a, 'gcx, 'tcx>,
+        skipped_regions: &'a mut bool,
+        fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
+    ) -> RegionFolder<'a, 'gcx, 'tcx> {
         RegionFolder {
             tcx,
             skipped_regions,
-            current_depth: 1,
-            fld_r,
+            current_index: ty::DebruijnIndex::INNERMOST,
+            fold_region_fn,
         }
     }
 }
@@ -300,24 +343,24 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionFolder<'a, 'gcx, 'tcx> {
     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 
     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
-        self.current_depth += 1;
+        self.current_index.shift_in(1);
         let t = t.super_fold_with(self);
-        self.current_depth -= 1;
+        self.current_index.shift_out(1);
         t
     }
 
     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
         match *r {
-            ty::ReLateBound(debruijn, _) if debruijn.depth < self.current_depth => {
-                debug!("RegionFolder.fold_region({:?}) skipped bound region (current depth={})",
-                       r, self.current_depth);
+            ty::ReLateBound(debruijn, _) if debruijn < self.current_index => {
+                debug!("RegionFolder.fold_region({:?}) skipped bound region (current index={:?})",
+                       r, self.current_index);
                 *self.skipped_regions = true;
                 r
             }
             _ => {
-                debug!("RegionFolder.fold_region({:?}) folding free region (current_depth={})",
-                       r, self.current_depth);
-                (self.fld_r)(r, self.current_depth)
+                debug!("RegionFolder.fold_region({:?}) folding free region (current_index={:?})",
+                       r, self.current_index);
+                (self.fold_region_fn)(r, self.current_index)
             }
         }
     }
@@ -330,7 +373,11 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionFolder<'a, 'gcx, 'tcx> {
 
 struct RegionReplacer<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
     tcx: TyCtxt<'a, 'gcx, 'tcx>,
-    current_depth: u32,
+
+    /// As with `RegionFolder`, represents the index of a binder *just outside*
+    /// the ones we have visited.
+    current_index: ty::DebruijnIndex,
+
     fld_r: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a),
     map: BTreeMap<ty::BoundRegion, ty::Region<'tcx>>
 }
@@ -372,20 +419,22 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         }).0
     }
 
-    /// Flattens two binding levels into one. So `for<'a> for<'b> Foo`
+    /// Flattens multiple binding levels into one. So `for<'a> for<'b> Foo`
     /// becomes `for<'a,'b> Foo`.
     pub fn flatten_late_bound_regions<T>(self, bound2_value: &Binder<Binder<T>>)
                                          -> Binder<T>
         where T: TypeFoldable<'tcx>
     {
         let bound0_value = bound2_value.skip_binder().skip_binder();
-        let value = self.fold_regions(bound0_value, &mut false,
-                                      |region, current_depth| {
+        let value = self.fold_regions(bound0_value, &mut false, |region, current_depth| {
             match *region {
-                ty::ReLateBound(debruijn, br) if debruijn.depth >= current_depth => {
-                    // should be true if no escaping regions from bound2_value
-                    assert!(debruijn.depth - current_depth <= 1);
-                    self.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(current_depth), br))
+                ty::ReLateBound(debruijn, br) => {
+                    // We assume no regions bound *outside* of the
+                    // binders in `bound2_value` (nmatsakis added in
+                    // the course of this PR; seems like a reasonable
+                    // sanity check though).
+                    assert!(debruijn == current_depth);
+                    self.mk_region(ty::ReLateBound(current_depth, br))
                 }
                 _ => {
                     region
@@ -446,7 +495,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         let mut counter = 0;
         Binder::bind(self.replace_late_bound_regions(sig, |_| {
             counter += 1;
-            self.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrAnon(counter)))
+            self.mk_region(ty::ReLateBound(ty::DebruijnIndex::INNERMOST, ty::BrAnon(counter)))
         }).0)
     }
 }
@@ -458,7 +507,7 @@ impl<'a, 'gcx, 'tcx> RegionReplacer<'a, 'gcx, 'tcx> {
     {
         RegionReplacer {
             tcx,
-            current_depth: 1,
+            current_index: ty::DebruijnIndex::INNERMOST,
             fld_r,
             map: BTreeMap::default()
         }
@@ -469,14 +518,14 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> {
     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 
     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
-        self.current_depth += 1;
+        self.current_index.shift_in(1);
         let t = t.super_fold_with(self);
-        self.current_depth -= 1;
+        self.current_index.shift_out(1);
         t
     }
 
     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
-        if !t.has_regions_escaping_depth(self.current_depth-1) {
+        if !t.has_regions_bound_at_or_above(self.current_index) {
             return t;
         }
 
@@ -485,14 +534,15 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> {
 
     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
         match *r {
-            ty::ReLateBound(debruijn, br) if debruijn.depth == self.current_depth => {
+            ty::ReLateBound(debruijn, br) if debruijn == self.current_index => {
                 let fld_r = &mut self.fld_r;
                 let region = *self.map.entry(br).or_insert_with(|| fld_r(br));
                 if let ty::ReLateBound(debruijn1, br) = *region {
                     // If the callback returns a late-bound region,
-                    // that region should always use depth 1. Then we
-                    // adjust it to the correct depth.
-                    assert_eq!(debruijn1.depth, 1);
+                    // that region should always use the INNERMOST
+                    // debruijn index. Then we adjust it to the
+                    // correct depth.
+                    assert_eq!(debruijn1, ty::DebruijnIndex::INNERMOST);
                     self.tcx.mk_region(ty::ReLateBound(debruijn, br))
                 } else {
                     region
@@ -515,7 +565,7 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> {
 pub fn shift_region(region: ty::RegionKind, amount: u32) -> ty::RegionKind {
     match region {
         ty::ReLateBound(debruijn, br) => {
-            ty::ReLateBound(debruijn.shifted(amount), br)
+            ty::ReLateBound(debruijn.shifted_in(amount), br)
         }
         _ => {
             region
@@ -531,7 +581,7 @@ pub fn shift_region_ref<'a, 'gcx, 'tcx>(
 {
     match region {
         &ty::ReLateBound(debruijn, br) if amount > 0 => {
-            tcx.mk_region(ty::ReLateBound(debruijn.shifted(amount), br))
+            tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), br))
         }
         _ => {
             region
@@ -575,23 +625,32 @@ pub fn shift_regions<'a, 'gcx, 'tcx, T>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 /// represent the scope to which it is attached, etc. An escaping region represents a bound region
 /// for which this processing has not yet been done.
 struct HasEscapingRegionsVisitor {
-    depth: u32,
+    /// Anything bound by `outer_index` or "above" is escaping
+    outer_index: ty::DebruijnIndex,
 }
 
 impl<'tcx> TypeVisitor<'tcx> for HasEscapingRegionsVisitor {
     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
-        self.depth += 1;
+        self.outer_index.shift_in(1);
         let result = t.super_visit_with(self);
-        self.depth -= 1;
+        self.outer_index.shift_out(1);
         result
     }
 
     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
-        t.region_depth > self.depth
+        // If the outer-exclusive-binder is *strictly greater* than
+        // `outer_index`, that means that `t` contains some content
+        // bound at `outer_index` or above (because
+        // `outer_exclusive_binder` is always 1 higher than the
+        // content in `t`). Therefore, `t` has some escaping regions.
+        t.outer_exclusive_binder > self.outer_index
     }
 
     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
-        r.escapes_depth(self.depth)
+        // If the region is bound by `outer_index` or anything outside
+        // of outer index, then it escapes the binders we have
+        // visited.
+        r.bound_at_or_above_binder(self.outer_index)
     }
 }
 
@@ -623,17 +682,26 @@ impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor {
     }
 }
 
-/// Collects all the late-bound regions it finds into a hash set.
+/// Collects all the late-bound regions at the innermost binding level
+/// into a hash set.
 struct LateBoundRegionsCollector {
-    current_depth: u32,
+    current_index: ty::DebruijnIndex,
     regions: FxHashSet<ty::BoundRegion>,
+
+    /// If true, we only want regions that are known to be
+    /// "constrained" when you equate this type with another type. In
+    /// partcular, if you have e.g. `&'a u32` and `&'b u32`, equating
+    /// them constraints `'a == 'b`.  But if you have `<&'a u32 as
+    /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
+    /// types may mean that `'a` and `'b` don't appear in the results,
+    /// so they are not considered *constrained*.
     just_constrained: bool,
 }
 
 impl LateBoundRegionsCollector {
     fn new(just_constrained: bool) -> Self {
         LateBoundRegionsCollector {
-            current_depth: 1,
+            current_index: ty::DebruijnIndex::INNERMOST,
             regions: FxHashSet(),
             just_constrained,
         }
@@ -642,9 +710,9 @@ impl LateBoundRegionsCollector {
 
 impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
-        self.current_depth += 1;
+        self.current_index.shift_in(1);
         let result = t.super_visit_with(self);
-        self.current_depth -= 1;
+        self.current_index.shift_out(1);
         result
     }
 
@@ -664,7 +732,7 @@ impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
 
     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
         match *r {
-            ty::ReLateBound(debruijn, br) if debruijn.depth == self.current_depth => {
+            ty::ReLateBound(debruijn, br) if debruijn == self.current_index => {
                 self.regions.insert(br);
             }
             _ => { }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 775c7c234fd..646c60c139c 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -488,8 +488,24 @@ pub struct TyS<'tcx> {
     pub sty: TypeVariants<'tcx>,
     pub flags: TypeFlags,
 
-    // the maximal depth of any bound regions appearing in this type.
-    region_depth: u32,
+    /// This is a kind of confusing thing: it stores the smallest
+    /// binder such that
+    ///
+    /// (a) the binder itself captures nothing but
+    /// (b) all the late-bound things within the type are captured
+    ///     by some sub-binder.
+    ///
+    /// So, for a type without any late-bound things, like `u32`, this
+    /// will be INNERMOST, because that is the innermost binder that
+    /// captures nothing. But for a type `&'D u32`, where `'D` is a
+    /// late-bound region with debruijn index D, this would be D+1 --
+    /// the binder itself does not capture D, but D is captured by an
+    /// inner binder.
+    ///
+    /// We call this concept an "exclusive" binder D (because all
+    /// debruijn indices within the type are contained within `0..D`
+    /// (exclusive)).
+    outer_exclusive_binder: ty::DebruijnIndex,
 }
 
 impl<'tcx> Ord for TyS<'tcx> {
@@ -560,7 +576,8 @@ impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for ty::TyS<'gcx> {
             // The other fields just provide fast access to information that is
             // also contained in `sty`, so no need to hash them.
             flags: _,
-            region_depth: _,
+
+            outer_exclusive_binder: _,
         } = *self;
 
         sty.hash_stable(hcx, hasher);
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 6fda152f9a1..f484fda2ae1 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -989,11 +989,11 @@ impl<'a, 'gcx, 'tcx> ParamTy {
 ///     for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
 ///     ^          ^            |        |         |
 ///     |          |            |        |         |
-///     |          +------------+ 1      |         |
+///     |          +------------+ 0      |         |
 ///     |                                |         |
-///     +--------------------------------+ 2       |
+///     +--------------------------------+ 1       |
 ///     |                                          |
-///     +------------------------------------------+ 1
+///     +------------------------------------------+ 0
 ///
 /// In this type, there are two binders (the outer fn and the inner
 /// fn). We need to be able to determine, for any given region, which
@@ -1005,9 +1005,9 @@ impl<'a, 'gcx, 'tcx> ParamTy {
 ///
 /// Let's start with the reference type `&'b isize` that is the first
 /// argument to the inner function. This region `'b` is assigned a De
-/// Bruijn index of 1, meaning "the innermost binder" (in this case, a
+/// Bruijn index of 0, meaning "the innermost binder" (in this case, a
 /// fn). The region `'a` that appears in the second argument type (`&'a
-/// isize`) would then be assigned a De Bruijn index of 2, meaning "the
+/// isize`) would then be assigned a De Bruijn index of 1, meaning "the
 /// second-innermost binder". (These indices are written on the arrays
 /// in the diagram).
 ///
@@ -1017,15 +1017,15 @@ impl<'a, 'gcx, 'tcx> ParamTy {
 /// the outermost fn. But this time, this reference is not nested within
 /// any other binders (i.e., it is not an argument to the inner fn, but
 /// rather the outer one). Therefore, in this case, it is assigned a
-/// De Bruijn index of 1, because the innermost binder in that location
+/// De Bruijn index of 0, because the innermost binder in that location
 /// is the outer fn.
 ///
 /// [dbi]: http://en.wikipedia.org/wiki/De_Bruijn_index
 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug, Copy, PartialOrd, Ord)]
 pub struct DebruijnIndex {
     /// We maintain the invariant that this is never 0. So 1 indicates
-    /// the innermost binder. To ensure this, create with `DebruijnIndex::new`.
-    pub depth: u32,
+    /// the innermost binder.
+    index: u32,
 }
 
 pub type Region<'tcx> = &'tcx RegionKind;
@@ -1259,16 +1259,70 @@ impl<'a, 'tcx, 'gcx> PolyExistentialProjection<'tcx> {
 }
 
 impl DebruijnIndex {
-    pub fn new(depth: u32) -> DebruijnIndex {
-        assert!(depth > 0);
-        DebruijnIndex { depth: depth }
+    pub const INNERMOST: DebruijnIndex = DebruijnIndex { index: 0 };
+
+    /// Returns the resulting index when this value is moved into
+    /// `amount` number of new binders. So e.g. if you had
+    ///
+    ///    for<'a> fn(&'a x)
+    ///
+    /// and you wanted to change to
+    ///
+    ///    for<'a> fn(for<'b> fn(&'a x))
+    ///
+    /// you would need to shift the index for `'a` into 1 new binder.
+    #[must_use]
+    pub const fn shifted_in(self, amount: u32) -> DebruijnIndex {
+        DebruijnIndex { index: self.index + amount }
+    }
+
+    /// Update this index in place by shifting it "in" through
+    /// `amount` number of binders.
+    pub fn shift_in(&mut self, amount: u32) {
+        *self = self.shifted_in(amount);
+    }
+
+    /// Returns the resulting index when this value is moved out from
+    /// `amount` number of new binders.
+    #[must_use]
+    pub const fn shifted_out(self, amount: u32) -> DebruijnIndex {
+        DebruijnIndex { index: self.index - amount }
+    }
+
+    /// Update in place by shifting out from `amount` binders.
+    pub fn shift_out(&mut self, amount: u32) {
+        *self = self.shifted_out(amount);
     }
 
-    pub fn shifted(&self, amount: u32) -> DebruijnIndex {
-        DebruijnIndex { depth: self.depth + amount }
+    /// Adjusts any Debruijn Indices so as to make `to_binder` the
+    /// innermost binder. That is, if we have something bound at `to_binder`,
+    /// it will now be bound at INNERMOST. This is an appropriate thing to do
+    /// when moving a region out from inside binders:
+    ///
+    /// ```
+    ///             for<'a>   fn(for<'b>   for<'c>   fn(&'a u32), _)
+    /// // Binder:  D3           D2        D1            ^^
+    /// ```
+    ///
+    /// Here, the region `'a` would have the debruijn index D3,
+    /// because it is the bound 3 binders out. However, if we wanted
+    /// to refer to that region `'a` in the second argument (the `_`),
+    /// those two binders would not be in scope. In that case, we
+    /// might invoke `shift_out_to_binder(D3)`. This would adjust the
+    /// debruijn index of `'a` to D1 (the innermost binder).
+    ///
+    /// If we invoke `shift_out_to_binder` and the region is in fact
+    /// bound by one of the binders we are shifting out of, that is an
+    /// error (and should fail an assertion failure).
+    pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self {
+        self.shifted_out(to_binder.index - Self::INNERMOST.index)
     }
 }
 
+impl_stable_hash_for!(struct DebruijnIndex {
+    index
+});
+
 /// Region utilities
 impl RegionKind {
     pub fn is_late_bound(&self) -> bool {
@@ -1278,19 +1332,39 @@ impl RegionKind {
         }
     }
 
-    pub fn escapes_depth(&self, depth: u32) -> bool {
+    pub fn bound_at_or_above_binder(&self, index: DebruijnIndex) -> bool {
         match *self {
-            ty::ReLateBound(debruijn, _) => debruijn.depth > depth,
+            ty::ReLateBound(debruijn, _) => debruijn >= index,
             _ => false,
         }
     }
 
-    /// Returns the depth of `self` from the (1-based) binding level `depth`
-    pub fn from_depth(&self, depth: u32) -> RegionKind {
+    /// Adjusts any Debruijn Indices so as to make `to_binder` the
+    /// innermost binder. That is, if we have something bound at `to_binder`,
+    /// it will now be bound at INNERMOST. This is an appropriate thing to do
+    /// when moving a region out from inside binders:
+    ///
+    /// ```
+    ///             for<'a>   fn(for<'b>   for<'c>   fn(&'a u32), _)
+    /// // Binder:  D3           D2        D1            ^^
+    /// ```
+    ///
+    /// Here, the region `'a` would have the debruijn index D3,
+    /// because it is the bound 3 binders out. However, if we wanted
+    /// to refer to that region `'a` in the second argument (the `_`),
+    /// those two binders would not be in scope. In that case, we
+    /// might invoke `shift_out_to_binder(D3)`. This would adjust the
+    /// debruijn index of `'a` to D1 (the innermost binder).
+    ///
+    /// If we invoke `shift_out_to_binder` and the region is in fact
+    /// bound by one of the binders we are shifting out of, that is an
+    /// error (and should fail an assertion failure).
+    pub fn shifted_out_to_binder(&self, to_binder: ty::DebruijnIndex) -> RegionKind {
         match *self {
-            ty::ReLateBound(debruijn, r) => ty::ReLateBound(DebruijnIndex {
-                depth: debruijn.depth - (depth - 1)
-            }, r),
+            ty::ReLateBound(debruijn, r) => ty::ReLateBound(
+                debruijn.shifted_out_to_binder(to_binder),
+                r,
+            ),
             r => r
         }
     }
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index 9b7443f97ef..9ef3308efe6 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -555,7 +555,7 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
                           -> Option<ty::Binder<Ty<'tcx>>>
     {
         let closure_ty = self.mk_closure(closure_def_id, closure_substs);
-        let env_region = ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrEnv);
+        let env_region = ty::ReLateBound(ty::DebruijnIndex::INNERMOST, ty::BrEnv);
         let closure_kind_ty = closure_substs.closure_kind_ty(closure_def_id, self);
         let closure_kind = closure_kind_ty.to_opt_closure_kind()?;
         let env_ty = match closure_kind {
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 82afce415a7..4e7df0cac12 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -526,7 +526,7 @@ impl PrintContext {
                     ty::BrNamed(tcx.hir.local_def_id(CRATE_NODE_ID), name)
                 }
             };
-            tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1), br))
+            tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::INNERMOST, br))
         }).0;
         start_or_continue(f, "", "> ")?;
 
diff --git a/src/librustc_codegen_llvm/common.rs b/src/librustc_codegen_llvm/common.rs
index 6a4b87ced15..ab99d1f0f30 100644
--- a/src/librustc_codegen_llvm/common.rs
+++ b/src/librustc_codegen_llvm/common.rs
@@ -425,7 +425,7 @@ pub fn ty_fn_sig<'a, 'tcx>(cx: &CodegenCx<'a, 'tcx>,
             let tcx = cx.tcx;
             let sig = substs.poly_sig(def_id, cx.tcx);
 
-            let env_region = ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrEnv);
+            let env_region = ty::ReLateBound(ty::DebruijnIndex::INNERMOST, ty::BrEnv);
             let env_ty = tcx.mk_mut_ref(tcx.mk_region(env_region), ty);
 
             sig.map_bound(|sig| {
diff --git a/src/librustc_driver/test.rs b/src/librustc_driver/test.rs
index 46f552ed28d..b22817a066c 100644
--- a/src/librustc_driver/test.rs
+++ b/src/librustc_driver/test.rs
@@ -183,6 +183,9 @@ fn test_env_with_pool<F>(
     });
 }
 
+const D1: ty::DebruijnIndex = ty::DebruijnIndex::INNERMOST;
+const D2: ty::DebruijnIndex = D1.shifted_in(1);
+
 impl<'a, 'gcx, 'tcx> Env<'a, 'gcx, 'tcx> {
     pub fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
         self.infcx.tcx
@@ -332,7 +335,7 @@ impl<'a, 'gcx, 'tcx> Env<'a, 'gcx, 'tcx> {
     }
 
     pub fn t_rptr_late_bound(&self, id: u32) -> Ty<'tcx> {
-        let r = self.re_late_bound_with_debruijn(id, ty::DebruijnIndex::new(1));
+        let r = self.re_late_bound_with_debruijn(id, D1);
         self.infcx.tcx.mk_imm_ref(r, self.tcx().types.isize)
     }
 
@@ -489,7 +492,7 @@ fn subst_ty_renumber_bound() {
 
         // t_expected = fn(&'a isize)
         let t_expected = {
-            let t_ptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
+            let t_ptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
             env.t_fn(&[t_ptr_bound2], env.t_nil())
         };
 
@@ -526,7 +529,7 @@ fn subst_ty_renumber_some_bounds() {
         //
         // but not that the Debruijn index is different in the different cases.
         let t_expected = {
-            let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
+            let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
             env.t_pair(t_rptr_bound1, env.t_fn(&[t_rptr_bound2], env.t_nil()))
         };
 
@@ -554,10 +557,10 @@ fn escaping() {
         let t_rptr_free1 = env.t_rptr_free(1);
         assert!(!t_rptr_free1.has_escaping_regions());
 
-        let t_rptr_bound1 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(1));
+        let t_rptr_bound1 = env.t_rptr_late_bound_with_debruijn(1, D1);
         assert!(t_rptr_bound1.has_escaping_regions());
 
-        let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
+        let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
         assert!(t_rptr_bound2.has_escaping_regions());
 
         // t_fn = fn(A)
@@ -573,7 +576,7 @@ fn escaping() {
 #[test]
 fn subst_region_renumber_region() {
     test_env(EMPTY_SOURCE_STR, errors(&[]), |env| {
-        let re_bound1 = env.re_late_bound_with_debruijn(1, ty::DebruijnIndex::new(1));
+        let re_bound1 = env.re_late_bound_with_debruijn(1, D1);
 
         // type t_source<'a> = fn(&'a isize)
         let t_source = {
@@ -588,7 +591,7 @@ fn subst_region_renumber_region() {
         //
         // but not that the Debruijn index is different in the different cases.
         let t_expected = {
-            let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, ty::DebruijnIndex::new(2));
+            let t_rptr_bound2 = env.t_rptr_late_bound_with_debruijn(1, D2);
             env.t_fn(&[t_rptr_bound2], env.t_nil())
         };
 
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index a7cdcae9c07..67245bec7fb 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -19,8 +19,8 @@ use rustc::infer::LateBoundRegionConversionTime;
 use rustc::infer::type_variable::TypeVariableOrigin;
 use rustc::traits::error_reporting::ArgKind;
 use rustc::ty::{self, ToPolyTraitRef, Ty, GenericParamDefKind};
+use rustc::ty::fold::TypeFoldable;
 use rustc::ty::subst::Substs;
-use rustc::ty::TypeFoldable;
 use std::cmp;
 use std::iter;
 use rustc_target::spec::abi::Abi;
@@ -465,7 +465,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         // Create a `PolyFnSig`. Note the oddity that late bound
         // regions appearing free in `expected_sig` are now bound up
         // in this binder we are creating.
-        assert!(!expected_sig.sig.has_regions_escaping_depth(1));
+        assert!(!expected_sig.sig.has_regions_bound_above(ty::DebruijnIndex::INNERMOST));
         let bound_sig = ty::Binder::bind(self.tcx.mk_fn_sig(
             expected_sig.sig.inputs().iter().cloned(),
             expected_sig.sig.output(),
diff --git a/src/librustc_typeck/check/generator_interior.rs b/src/librustc_typeck/check/generator_interior.rs
index b3d2a09a72c..e234e2f0192 100644
--- a/src/librustc_typeck/check/generator_interior.rs
+++ b/src/librustc_typeck/check/generator_interior.rs
@@ -125,8 +125,7 @@ pub fn resolve_interior<'a, 'gcx, 'tcx>(fcx: &'a FnCtxt<'a, 'gcx, 'tcx>,
     let mut counter = 0;
     let type_list = fcx.tcx.fold_regions(&type_list, &mut false, |_, current_depth| {
         counter += 1;
-        fcx.tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(current_depth),
-                                        ty::BrAnon(counter)))
+        fcx.tcx.mk_region(ty::ReLateBound(current_depth, ty::BrAnon(counter)))
     });
 
     let witness = fcx.tcx.mk_generator_witness(ty::Binder::bind(type_list));
diff --git a/src/librustc_typeck/check/intrinsic.rs b/src/librustc_typeck/check/intrinsic.rs
index 5546aa58d4c..215a3163a9c 100644
--- a/src/librustc_typeck/check/intrinsic.rs
+++ b/src/librustc_typeck/check/intrinsic.rs
@@ -119,7 +119,7 @@ pub fn check_intrinsic_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             "pref_align_of" | "min_align_of" => (1, Vec::new(), tcx.types.usize),
             "size_of_val" |  "min_align_of_val" => {
                 (1, vec![
-                    tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1),
+                    tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::INNERMOST,
                                                                   ty::BrAnon(0))),
                                     param(0))
                  ], tcx.types.usize)
@@ -298,7 +298,7 @@ pub fn check_intrinsic_type<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             "unlikely" => (0, vec![tcx.types.bool], tcx.types.bool),
 
             "discriminant_value" => (1, vec![
-                    tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1),
+                    tcx.mk_imm_ref(tcx.mk_region(ty::ReLateBound(ty::DebruijnIndex::INNERMOST,
                                                                   ty::BrAnon(0))),
                                    param(0))], tcx.types.u64),
 
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index d0c67c2882c..a982724f957 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -689,7 +689,7 @@ fn has_late_bound_regions<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                     -> Option<Span> {
     struct LateBoundRegionsDetector<'a, 'tcx: 'a> {
         tcx: TyCtxt<'a, 'tcx, 'tcx>,
-        binder_depth: u32,
+        outer_index: ty::DebruijnIndex,
         has_late_bound_regions: Option<Span>,
     }
 
@@ -702,9 +702,9 @@ fn has_late_bound_regions<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
             if self.has_late_bound_regions.is_some() { return }
             match ty.node {
                 hir::TyBareFn(..) => {
-                    self.binder_depth += 1;
+                    self.outer_index.shift_in(1);
                     intravisit::walk_ty(self, ty);
-                    self.binder_depth -= 1;
+                    self.outer_index.shift_out(1);
                 }
                 _ => intravisit::walk_ty(self, ty)
             }
@@ -714,9 +714,9 @@ fn has_late_bound_regions<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                 tr: &'tcx hir::PolyTraitRef,
                                 m: hir::TraitBoundModifier) {
             if self.has_late_bound_regions.is_some() { return }
-            self.binder_depth += 1;
+            self.outer_index.shift_in(1);
             intravisit::walk_poly_trait_ref(self, tr, m);
-            self.binder_depth -= 1;
+            self.outer_index.shift_out(1);
         }
 
         fn visit_lifetime(&mut self, lt: &'tcx hir::Lifetime) {
@@ -727,8 +727,13 @@ fn has_late_bound_regions<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                 Some(rl::Region::Static) | Some(rl::Region::EarlyBound(..)) => {}
                 Some(rl::Region::LateBound(debruijn, _, _)) |
                 Some(rl::Region::LateBoundAnon(debruijn, _))
-                    if debruijn.depth < self.binder_depth => {}
-                _ => self.has_late_bound_regions = Some(lt.span),
+                    if debruijn < self.outer_index => {}
+                Some(rl::Region::LateBound(..)) |
+                Some(rl::Region::LateBoundAnon(..)) |
+                Some(rl::Region::Free(..)) |
+                None => {
+                    self.has_late_bound_regions = Some(lt.span);
+                }
             }
         }
     }
@@ -738,7 +743,9 @@ fn has_late_bound_regions<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                         decl: &'tcx hir::FnDecl)
                                         -> Option<Span> {
         let mut visitor = LateBoundRegionsDetector {
-            tcx, binder_depth: 1, has_late_bound_regions: None
+            tcx,
+            outer_index: ty::DebruijnIndex::INNERMOST,
+            has_late_bound_regions: None,
         };
         for lifetime in generics.lifetimes() {
             let hir_id = tcx.hir.node_to_hir_id(lifetime.lifetime.id);
diff --git a/src/test/ui/nll/closure-requirements/escape-argument-callee.stderr b/src/test/ui/nll/closure-requirements/escape-argument-callee.stderr
index d876c751a41..a0ad8ee4380 100644
--- a/src/test/ui/nll/closure-requirements/escape-argument-callee.stderr
+++ b/src/test/ui/nll/closure-requirements/escape-argument-callee.stderr
@@ -18,7 +18,7 @@ LL |         let mut closure = expect_sig(|p, y| *p = y);
    |
    = note: defining type: DefId(0/1:9 ~ escape_argument_callee[317d]::test[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's, 't0> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) mut &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) i32, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't0)) i32))
+               for<'r, 's, 't0> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) mut &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) i32, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't0)) i32))
            ]
 
 note: No external requirements
diff --git a/src/test/ui/nll/closure-requirements/escape-argument.stderr b/src/test/ui/nll/closure-requirements/escape-argument.stderr
index a9a52aba842..6aeb8d4fcd5 100644
--- a/src/test/ui/nll/closure-requirements/escape-argument.stderr
+++ b/src/test/ui/nll/closure-requirements/escape-argument.stderr
@@ -6,7 +6,7 @@ LL |         let mut closure = expect_sig(|p, y| *p = y);
    |
    = note: defining type: DefId(0/1:9 ~ escape_argument[317d]::test[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) mut &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) i32, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) i32))
+               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) mut &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) i32, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) i32))
            ]
 
 note: No external requirements
diff --git a/src/test/ui/nll/closure-requirements/propagate-approximated-fail-no-postdom.stderr b/src/test/ui/nll/closure-requirements/propagate-approximated-fail-no-postdom.stderr
index ef5a31e40d4..26ad522f6f4 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-fail-no-postdom.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-fail-no-postdom.stderr
@@ -24,7 +24,7 @@ LL | |         },
    |
    = note: defining type: DefId(0/1:20 ~ propagate_approximated_fail_no_postdom[317d]::supply[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#3r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
+               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#3r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
            ]
 
 note: No external requirements
diff --git a/src/test/ui/nll/closure-requirements/propagate-approximated-ref.stderr b/src/test/ui/nll/closure-requirements/propagate-approximated-ref.stderr
index 3a3236fd16c..537e951ddf1 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-ref.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-ref.stderr
@@ -18,7 +18,7 @@ LL | |     });
    |
    = note: defining type: DefId(0/1:18 ~ propagate_approximated_ref[317d]::supply[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) &'_#2r u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't3)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>))
+               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) &'_#2r u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't3)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>))
            ]
    = note: number of external vids: 3
    = note: where '_#1r: '_#2r
diff --git a/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-comparing-against-free.stderr b/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-comparing-against-free.stderr
index 6480cbe4431..93ae534b25c 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-comparing-against-free.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-comparing-against-free.stderr
@@ -23,7 +23,7 @@ LL | |     })
    |
    = note: defining type: DefId(0/1:12 ~ propagate_approximated_shorter_to_static_comparing_against_free[317d]::case1[0]::{{closure}}[0]) with closure substs [
                i32,
-               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>))
+               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>))
            ]
 
 note: No external requirements
@@ -51,7 +51,7 @@ LL | |     })
    |
    = note: defining type: DefId(0/1:13 ~ propagate_approximated_shorter_to_static_comparing_against_free[317d]::case2[0]::{{closure}}[0]) with closure substs [
                i32,
-               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>))
+               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>))
            ]
    = note: number of external vids: 2
    = note: where '_#1r: '_#0r
diff --git a/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-no-bound.stderr b/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-no-bound.stderr
index 6dcc8421177..4081ec65f80 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-no-bound.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-no-bound.stderr
@@ -18,7 +18,7 @@ LL | |     });
    |
    = note: defining type: DefId(0/1:18 ~ propagate_approximated_shorter_to_static_no_bound[317d]::supply[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't2)) u32>))
+               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't2)) u32>))
            ]
    = note: number of external vids: 2
    = note: where '_#1r: '_#0r
diff --git a/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-wrong-bound.stderr b/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-wrong-bound.stderr
index 1291f2e9901..7a745bb0964 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-wrong-bound.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-shorter-to-static-wrong-bound.stderr
@@ -18,7 +18,7 @@ LL | |     });
    |
    = note: defining type: DefId(0/1:18 ~ propagate_approximated_shorter_to_static_wrong_bound[317d]::supply[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't3)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>))
+               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't3)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>))
            ]
    = note: number of external vids: 3
    = note: where '_#1r: '_#0r
diff --git a/src/test/ui/nll/closure-requirements/propagate-approximated-val.stderr b/src/test/ui/nll/closure-requirements/propagate-approximated-val.stderr
index d1824a94151..4e2680585e9 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-val.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-val.stderr
@@ -18,7 +18,7 @@ LL | |     });
    |
    = note: defining type: DefId(0/1:18 ~ propagate_approximated_val[317d]::test[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
+               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
            ]
    = note: number of external vids: 3
    = note: where '_#1r: '_#2r
diff --git a/src/test/ui/nll/closure-requirements/propagate-despite-same-free-region.stderr b/src/test/ui/nll/closure-requirements/propagate-despite-same-free-region.stderr
index d6eeda881da..2cc9a11dbc3 100644
--- a/src/test/ui/nll/closure-requirements/propagate-despite-same-free-region.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-despite-same-free-region.stderr
@@ -16,7 +16,7 @@ LL | |         },
    |
    = note: defining type: DefId(0/1:16 ~ propagate_despite_same_free_region[317d]::supply[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
+               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
            ]
    = note: number of external vids: 3
    = note: where '_#1r: '_#2r
diff --git a/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-no-bounds.stderr b/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-no-bounds.stderr
index ffae47bd081..e53ece696c9 100644
--- a/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-no-bounds.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-no-bounds.stderr
@@ -24,7 +24,7 @@ LL | |     });
    |
    = note: defining type: DefId(0/1:18 ~ propagate_fail_to_approximate_longer_no_bounds[317d]::supply[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#1r u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
+               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#1r u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>))
            ]
 
 note: No external requirements
diff --git a/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-wrong-bounds.stderr b/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-wrong-bounds.stderr
index 01af756b833..45f308b2323 100644
--- a/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-wrong-bounds.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-fail-to-approximate-longer-wrong-bounds.stderr
@@ -24,7 +24,7 @@ LL | |     });
    |
    = note: defining type: DefId(0/1:18 ~ propagate_fail_to_approximate_longer_wrong_bounds[317d]::supply[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#1r u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) &'_#2r u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't3)) std::cell::Cell<&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>))
+               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) &'_#1r u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't0)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) &'_#2r u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't2)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) u32>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't3)) std::cell::Cell<&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 't1)) u32>))
            ]
 
 note: No external requirements
diff --git a/src/test/ui/nll/closure-requirements/return-wrong-bound-region.stderr b/src/test/ui/nll/closure-requirements/return-wrong-bound-region.stderr
index 4d021fb5454..9e6fd28565e 100644
--- a/src/test/ui/nll/closure-requirements/return-wrong-bound-region.stderr
+++ b/src/test/ui/nll/closure-requirements/return-wrong-bound-region.stderr
@@ -18,7 +18,7 @@ LL |     expect_sig(|a, b| b); // ought to return `a`
    |
    = note: defining type: DefId(0/1:9 ~ return_wrong_bound_region[317d]::test[0]::{{closure}}[0]) with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) i32, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) i32)) -> &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) i32
+               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) i32, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) i32)) -> &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) i32
            ]
 
 note: No external requirements
diff --git a/src/test/ui/nll/ty-outlives/ty-param-closure-approximate-lower-bound.stderr b/src/test/ui/nll/ty-outlives/ty-param-closure-approximate-lower-bound.stderr
index b4f51401a90..70bda0d7a18 100644
--- a/src/test/ui/nll/ty-outlives/ty-param-closure-approximate-lower-bound.stderr
+++ b/src/test/ui/nll/ty-outlives/ty-param-closure-approximate-lower-bound.stderr
@@ -25,7 +25,7 @@ LL |     twice(cell, value, |a, b| invoke(a, b));
    = note: defining type: DefId(0/1:14 ~ ty_param_closure_approximate_lower_bound[317d]::generic[0]::{{closure}}[0]) with closure substs [
                T,
                i16,
-               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) ()>>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) T))
+               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) ()>>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) T))
            ]
    = note: number of external vids: 2
    = note: where T: '_#1r
@@ -55,7 +55,7 @@ LL |     twice(cell, value, |a, b| invoke(a, b));
    = note: defining type: DefId(0/1:17 ~ ty_param_closure_approximate_lower_bound[317d]::generic_fail[0]::{{closure}}[0]) with closure substs [
                T,
                i16,
-               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 'r)) ()>>, &ReLateBound(DebruijnIndex { depth: 1 }, BrNamed(crate0:DefIndex(0:0), 's)) T))
+               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 'r)) ()>>, &ReLateBound(DebruijnIndex { index: 0 }, BrNamed(crate0:DefIndex(0:0), 's)) T))
            ]
    = note: number of external vids: 2
    = note: where T: '_#1r