Add var to BoundRegion. Add query to get bound vars for applicable items.

53 files changed, 1261 insertions, 372 deletions

diff --git a/compiler/rustc_hir/src/hir.rs b/compiler/rustc_hir/src/hir.rs
index 03af81ae02a..6317808e7fb 100644
--- a/compiler/rustc_hir/src/hir.rs
+++ b/compiler/rustc_hir/src/hir.rs
@@ -402,7 +402,7 @@ pub enum TraitBoundModifier {
 /// `typeck::collect::compute_bounds` matches these against
 /// the "special" built-in traits (see `middle::lang_items`) and
 /// detects `Copy`, `Send` and `Sync`.
-#[derive(Debug, HashStable_Generic)]
+#[derive(Clone, Debug, HashStable_Generic)]
 pub enum GenericBound<'hir> {
     Trait(PolyTraitRef<'hir>, TraitBoundModifier),
     // FIXME(davidtwco): Introduce `PolyTraitRef::LangItem`
@@ -2556,7 +2556,7 @@ pub enum UseKind {
 /// that the `ref_id` is for. Note that `ref_id`'s value is not the `HirId` of the
 /// trait being referred to but just a unique `HirId` that serves as a key
 /// within the resolution map.
-#[derive(Debug, HashStable_Generic)]
+#[derive(Clone, Debug, HashStable_Generic)]
 pub struct TraitRef<'hir> {
     pub path: &'hir Path<'hir>,
     // Don't hash the `ref_id`. It is tracked via the thing it is used to access.
@@ -2575,7 +2575,7 @@ impl TraitRef<'_> {
     }
 }
 
-#[derive(Debug, HashStable_Generic)]
+#[derive(Clone, Debug, HashStable_Generic)]
 pub struct PolyTraitRef<'hir> {
     /// The `'a` in `for<'a> Foo<&'a T>`.
     pub bound_generic_params: &'hir [GenericParam<'hir>],
diff --git a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
index 392553a80f9..c68705da413 100644
--- a/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
+++ b/compiler/rustc_infer/src/infer/canonical/canonicalizer.rs
@@ -621,7 +621,7 @@ impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
         r: ty::Region<'tcx>,
     ) -> ty::Region<'tcx> {
         let var = self.canonical_var(info, r.into());
-        let br = ty::BoundRegion { kind: ty::BrAnon(var.as_u32()) };
+        let br = ty::BoundRegion { var, kind: ty::BrAnon(var.as_u32()) };
         let region = ty::ReLateBound(self.binder_index, br);
         self.tcx().mk_region(region)
     }
diff --git a/compiler/rustc_infer/src/infer/canonical/query_response.rs b/compiler/rustc_infer/src/infer/canonical/query_response.rs
index f000d491b99..b8ecc949588 100644
--- a/compiler/rustc_infer/src/infer/canonical/query_response.rs
+++ b/compiler/rustc_infer/src/infer/canonical/query_response.rs
@@ -439,7 +439,7 @@ impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
 
                         // We only allow a `ty::INNERMOST` index in substitutions.
                         assert_eq!(debruijn, ty::INNERMOST);
-                        opt_values[br.assert_bound_var()] = Some(*original_value);
+                        opt_values[br.var] = Some(*original_value);
                     }
                 }
                 GenericArgKind::Const(result_value) => {
diff --git a/compiler/rustc_infer/src/infer/canonical/substitute.rs b/compiler/rustc_infer/src/infer/canonical/substitute.rs
index 387f480814a..553a11d4393 100644
--- a/compiler/rustc_infer/src/infer/canonical/substitute.rs
+++ b/compiler/rustc_infer/src/infer/canonical/substitute.rs
@@ -71,11 +71,10 @@ where
     if var_values.var_values.is_empty() {
         value
     } else {
-        let fld_r =
-            |br: ty::BoundRegion| match var_values.var_values[br.assert_bound_var()].unpack() {
-                GenericArgKind::Lifetime(l) => l,
-                r => bug!("{:?} is a region but value is {:?}", br, r),
-            };
+        let fld_r = |br: ty::BoundRegion| match var_values.var_values[br.var].unpack() {
+            GenericArgKind::Lifetime(l) => l,
+            r => bug!("{:?} is a region but value is {:?}", br, r),
+        };
 
         let fld_t = |bound_ty: ty::BoundTy| match var_values.var_values[bound_ty.var].unpack() {
             GenericArgKind::Type(ty) => ty,
diff --git a/compiler/rustc_middle/src/ich/impls_ty.rs b/compiler/rustc_middle/src/ich/impls_ty.rs
index c39ea5825a7..8e53e4ba948 100644
--- a/compiler/rustc_middle/src/ich/impls_ty.rs
+++ b/compiler/rustc_middle/src/ich/impls_ty.rs
@@ -70,16 +70,16 @@ impl<'a> HashStable<StableHashingContext<'a>> for ty::RegionKind {
             ty::ReEmpty(universe) => {
                 universe.hash_stable(hcx, hasher);
             }
-            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrAnon(i) }) => {
+            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrAnon(i), .. }) => {
                 db.hash_stable(hcx, hasher);
                 i.hash_stable(hcx, hasher);
             }
-            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrNamed(def_id, name) }) => {
+            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrNamed(def_id, name), .. }) => {
                 db.hash_stable(hcx, hasher);
                 def_id.hash_stable(hcx, hasher);
                 name.hash_stable(hcx, hasher);
             }
-            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrEnv }) => {
+            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrEnv, .. }) => {
                 db.hash_stable(hcx, hasher);
             }
             ty::ReEarlyBound(ty::EarlyBoundRegion { def_id, index, name }) => {
diff --git a/compiler/rustc_middle/src/infer/canonical.rs b/compiler/rustc_middle/src/infer/canonical.rs
index 5d0987193fa..5df2f91f09f 100644
--- a/compiler/rustc_middle/src/infer/canonical.rs
+++ b/compiler/rustc_middle/src/infer/canonical.rs
@@ -314,7 +314,8 @@ impl<'tcx> CanonicalVarValues<'tcx> {
                         tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
                     }
                     GenericArgKind::Lifetime(..) => {
-                        let br = ty::BoundRegion { kind: ty::BrAnon(i) };
+                        let br =
+                            ty::BoundRegion { var: ty::BoundVar::from_u32(i), kind: ty::BrAnon(i) };
                         tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
                     }
                     GenericArgKind::Const(ct) => tcx
diff --git a/compiler/rustc_middle/src/middle/resolve_lifetime.rs b/compiler/rustc_middle/src/middle/resolve_lifetime.rs
index 98802721954..aa6488b329e 100644
--- a/compiler/rustc_middle/src/middle/resolve_lifetime.rs
+++ b/compiler/rustc_middle/src/middle/resolve_lifetime.rs
@@ -83,4 +83,6 @@ pub struct ResolveLifetimes {
     /// be late-bound if (a) it does NOT appear in a where-clause and
     /// (b) it DOES appear in the arguments.
     pub late_bound: FxHashMap<LocalDefId, FxHashSet<ItemLocalId>>,
+
+    pub late_bound_vars: FxHashMap<LocalDefId, FxHashMap<ItemLocalId, Vec<ty::BoundVariableKind>>>,
 }
diff --git a/compiler/rustc_middle/src/query/mod.rs b/compiler/rustc_middle/src/query/mod.rs
index fbd5af9d0a9..99d063c7eea 100644
--- a/compiler/rustc_middle/src/query/mod.rs
+++ b/compiler/rustc_middle/src/query/mod.rs
@@ -1290,6 +1290,10 @@ rustc_queries! {
         -> Option<Vec<ObjectLifetimeDefault>> {
         desc { "looking up lifetime defaults for a region on an item" }
     }
+    query late_bound_vars_map(_: LocalDefId)
+        -> Option<&'tcx FxHashMap<ItemLocalId, Vec<ty::BoundVariableKind>>> {
+        desc { "looking up late bound vars" }
+    }
 
     query visibility(def_id: DefId) -> ty::Visibility {
         eval_always
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index 1f1840c0e4a..bb2b00cbaea 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -810,7 +810,7 @@ impl CanonicalUserType<'tcx> {
                             ty::ReLateBound(debruijn, br) => {
                                 // We only allow a `ty::INNERMOST` index in substitutions.
                                 assert_eq!(*debruijn, ty::INNERMOST);
-                                cvar == br.assert_bound_var()
+                                cvar == br.var
                             }
                             _ => false,
                         },
@@ -2672,6 +2672,17 @@ impl<'tcx> TyCtxt<'tcx> {
     pub fn object_lifetime_defaults(self, id: HirId) -> Option<Vec<ObjectLifetimeDefault>> {
         self.object_lifetime_defaults_map(id.owner)
     }
+
+    pub fn late_bound_vars(self, id: HirId) -> &'tcx List<ty::BoundVariableKind> {
+        self.mk_bound_variable_kinds(
+            self.late_bound_vars_map(id.owner)
+                .and_then(|map| map.get(&id.local_id).cloned())
+                .unwrap_or_else(|| {
+                    bug!("No bound vars found for {:?} ({:?})", self.hir().node_to_string(id), id)
+                })
+                .iter(),
+        )
+    }
 }
 
 impl TyCtxtAt<'tcx> {
diff --git a/compiler/rustc_middle/src/ty/fold.rs b/compiler/rustc_middle/src/ty/fold.rs
index 32101b4c8c9..368236b146f 100644
--- a/compiler/rustc_middle/src/ty/fold.rs
+++ b/compiler/rustc_middle/src/ty/fold.rs
@@ -634,6 +634,42 @@ impl<'tcx> TyCtxt<'tcx> {
         .0
     }
 
+    pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T
+    where
+        T: TypeFoldable<'tcx>,
+    {
+        self.replace_escaping_bound_vars(
+            value,
+            |r| {
+                self.mk_region(ty::ReLateBound(
+                    ty::INNERMOST,
+                    ty::BoundRegion {
+                        var: ty::BoundVar::from_usize(r.var.as_usize() + bound_vars),
+                        kind: r.kind,
+                    },
+                ))
+            },
+            |t| {
+                self.mk_ty(ty::Bound(
+                    ty::INNERMOST,
+                    ty::BoundTy {
+                        var: ty::BoundVar::from_usize(t.var.as_usize() + bound_vars),
+                        kind: t.kind,
+                    },
+                ))
+            },
+            |c, ty| {
+                self.mk_const(ty::Const {
+                    val: ty::ConstKind::Bound(
+                        ty::INNERMOST,
+                        ty::BoundVar::from_usize(c.as_usize() + bound_vars),
+                    ),
+                    ty,
+                })
+            },
+        )
+    }
+
     /// Returns a set of all late-bound regions that are constrained
     /// by `value`, meaning that if we instantiate those LBR with
     /// variables and equate `value` with something else, those
@@ -695,16 +731,21 @@ impl<'tcx> TyCtxt<'tcx> {
         T: TypeFoldable<'tcx>,
     {
         let mut counter = 0;
-        Binder::bind(
-            self.replace_late_bound_regions(sig, |_| {
-                let br = ty::BoundRegion { kind: ty::BrAnon(counter) };
+        let inner = self
+            .replace_late_bound_regions(sig, |_| {
+                let br = ty::BoundRegion {
+                    var: ty::BoundVar::from_u32(counter),
+                    kind: ty::BrAnon(counter),
+                };
                 let r = self.mk_region(ty::ReLateBound(ty::INNERMOST, br));
                 counter += 1;
                 r
             })
-            .0,
-            self,
-        )
+            .0;
+        let bound_vars = self.mk_bound_variable_kinds(
+            (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))),
+        );
+        Binder::bind_with_vars(inner, bound_vars)
     }
 }
 
@@ -777,27 +818,105 @@ impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector<'tcx> {
     }
 
     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
-        use std::collections::btree_map::Entry;
         match r {
-            ty::ReLateBound(index, br) if *index == self.binder_index => match br.kind {
-                ty::BrNamed(_def_id, _name) => {
-                    // FIXME
-                }
+            ty::ReLateBound(index, _br) if *index == self.binder_index => {
+                bug!("{:?} {:?}", index, _br)
+            }
 
-                ty::BrAnon(var) => match self.vars.entry(var) {
-                    Entry::Vacant(entry) => {
-                        entry.insert(ty::BoundVariableKind::Region(br.kind));
+            _ => (),
+        };
+
+        r.super_visit_with(self)
+    }
+}
+
+pub struct ValidateBoundVars<'tcx> {
+    bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
+    binder_index: ty::DebruijnIndex,
+    // We may encounter the same variable at different levels of binding, so
+    // this can't just be `Ty`
+    visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>,
+}
+
+impl<'tcx> ValidateBoundVars<'tcx> {
+    pub fn new(bound_vars: &'tcx ty::List<ty::BoundVariableKind>) -> Self {
+        ValidateBoundVars {
+            bound_vars,
+            binder_index: ty::INNERMOST,
+            visited: SsoHashSet::default(),
+        }
+    }
+}
+
+impl<'tcx> TypeVisitor<'tcx> for ValidateBoundVars<'tcx> {
+    type BreakTy = ();
+
+    fn visit_binder<T: TypeFoldable<'tcx>>(
+        &mut self,
+        t: &Binder<'tcx, T>,
+    ) -> ControlFlow<Self::BreakTy> {
+        self.binder_index.shift_in(1);
+        let result = t.super_visit_with(self);
+        self.binder_index.shift_out(1);
+        result
+    }
+
+    fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+        if t.outer_exclusive_binder < self.binder_index
+            || !self.visited.insert((self.binder_index, t))
+        {
+            return ControlFlow::BREAK;
+        }
+        match *t.kind() {
+            ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
+                if self.bound_vars.len() <= bound_ty.var.as_usize() {
+                    panic!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars);
+                }
+                let list_var = self.bound_vars[bound_ty.var.as_usize()];
+                match list_var {
+                    ty::BoundVariableKind::Ty(kind) => {
+                        if kind != bound_ty.kind {
+                            panic!(
+                                "Mismatched type kinds: {:?} doesn't var in list {:?}",
+                                bound_ty.kind, list_var
+                            );
+                        }
                     }
-                    Entry::Occupied(entry) => match entry.get() {
-                        ty::BoundVariableKind::Region(_) => {}
-                        _ => bug!("Conflicting bound vars"),
-                    },
-                },
+                    _ => panic!(
+                        "Mismatched bound variable kinds! Expected type, found {:?}",
+                        list_var
+                    ),
+                }
+            }
+
+            _ => (),
+        };
+
+        t.super_visit_with(self)
+    }
 
-                ty::BrEnv => {
-                    // FIXME
+    fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+        match r {
+            ty::ReLateBound(index, br) if *index == self.binder_index => {
+                if self.bound_vars.len() <= br.var.as_usize() {
+                    panic!("Not enough bound vars: {:?} not found in {:?}", *br, self.bound_vars);
                 }
-            },
+                let list_var = self.bound_vars[br.var.as_usize()];
+                match list_var {
+                    ty::BoundVariableKind::Region(kind) => {
+                        if kind != br.kind {
+                            panic!(
+                                "Mismatched region kinds: {:?} doesn't match var ({:?}) in list ({:?})",
+                                br.kind, list_var, self.bound_vars
+                            );
+                        }
+                    }
+                    _ => panic!(
+                        "Mismatched bound variable kinds! Expected region, found {:?}",
+                        list_var
+                    ),
+                }
+            }
 
             _ => (),
         };
diff --git a/compiler/rustc_middle/src/ty/layout.rs b/compiler/rustc_middle/src/ty/layout.rs
index 0d03cf4575f..e7bbdc3cceb 100644
--- a/compiler/rustc_middle/src/ty/layout.rs
+++ b/compiler/rustc_middle/src/ty/layout.rs
@@ -1,3 +1,4 @@
+// ignore-tidy-filelength
 use crate::ich::StableHashingContext;
 use crate::middle::codegen_fn_attrs::CodegenFnAttrFlags;
 use crate::mir::{GeneratorLayout, GeneratorSavedLocal};
@@ -2481,21 +2482,42 @@ impl<'tcx> ty::Instance<'tcx> {
             ty::Closure(def_id, substs) => {
                 let sig = substs.as_closure().sig();
 
-                let env_ty = tcx.closure_env_ty(def_id, substs).unwrap();
-                sig.map_bound(|sig| {
+                let bound_vars = tcx.mk_bound_variable_kinds(
+                    sig.bound_vars()
+                        .iter()
+                        .chain(iter::once(ty::BoundVariableKind::Region(ty::BrEnv))),
+                );
+                let br = ty::BoundRegion {
+                    var: ty::BoundVar::from_usize(bound_vars.len() - 1),
+                    kind: ty::BoundRegionKind::BrEnv,
+                };
+                let env_region = ty::ReLateBound(ty::INNERMOST, br);
+                let env_ty = tcx.closure_env_ty(def_id, substs, env_region).unwrap();
+
+                let sig = sig.skip_binder();
+                ty::Binder::bind_with_vars(
                     tcx.mk_fn_sig(
-                        iter::once(env_ty.skip_binder()).chain(sig.inputs().iter().cloned()),
+                        iter::once(env_ty).chain(sig.inputs().iter().cloned()),
                         sig.output(),
                         sig.c_variadic,
                         sig.unsafety,
                         sig.abi,
-                    )
-                })
+                    ),
+                    bound_vars,
+                )
             }
             ty::Generator(_, substs, _) => {
                 let sig = substs.as_generator().poly_sig();
 
-                let br = ty::BoundRegion { kind: ty::BrEnv };
+                let bound_vars = tcx.mk_bound_variable_kinds(
+                    sig.bound_vars()
+                        .iter()
+                        .chain(iter::once(ty::BoundVariableKind::Region(ty::BrEnv))),
+                );
+                let br = ty::BoundRegion {
+                    var: ty::BoundVar::from_usize(bound_vars.len() - 1),
+                    kind: ty::BoundRegionKind::BrEnv,
+                };
                 let env_region = ty::ReLateBound(ty::INNERMOST, br);
                 let env_ty = tcx.mk_mut_ref(tcx.mk_region(env_region), ty);
 
@@ -2504,21 +2526,21 @@ impl<'tcx> ty::Instance<'tcx> {
                 let pin_substs = tcx.intern_substs(&[env_ty.into()]);
                 let env_ty = tcx.mk_adt(pin_adt_ref, pin_substs);
 
-                sig.map_bound(|sig| {
-                    let state_did = tcx.require_lang_item(LangItem::GeneratorState, None);
-                    let state_adt_ref = tcx.adt_def(state_did);
-                    let state_substs =
-                        tcx.intern_substs(&[sig.yield_ty.into(), sig.return_ty.into()]);
-                    let ret_ty = tcx.mk_adt(state_adt_ref, state_substs);
-
+                let sig = sig.skip_binder();
+                let state_did = tcx.require_lang_item(LangItem::GeneratorState, None);
+                let state_adt_ref = tcx.adt_def(state_did);
+                let state_substs = tcx.intern_substs(&[sig.yield_ty.into(), sig.return_ty.into()]);
+                let ret_ty = tcx.mk_adt(state_adt_ref, state_substs);
+                ty::Binder::bind_with_vars(
                     tcx.mk_fn_sig(
                         [env_ty, sig.resume_ty].iter(),
                         &ret_ty,
                         false,
                         hir::Unsafety::Normal,
                         rustc_target::spec::abi::Abi::Rust,
-                    )
-                })
+                    ),
+                    bound_vars,
+                )
             }
             _ => bug!("unexpected type {:?} in Instance::fn_sig", ty),
         }
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index a09573fac02..6574c938260 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -543,10 +543,33 @@ impl<'tcx> Predicate<'tcx> {
         // substitution code expects equal binding levels in the values
         // from the substitution and the value being substituted into, and
         // this trick achieves that).
-        let substs = trait_ref.skip_binder().substs;
-        let pred = self.kind().skip_binder();
-        let new = pred.subst(tcx, substs);
-        tcx.reuse_or_mk_predicate(self, ty::Binder::bind(new, tcx))
+
+        // Working through the second example:
+        // trait_ref: for<'x> T: Foo1<'^0.0>; substs: [T, '^0.0]
+        // predicate: for<'b> Self: Bar1<'a, '^0.0>; substs: [Self, 'a, '^0.0]
+        // We want to end up with:
+        //     for<'x, 'b> T: Bar1<'^0.0, '^0.1>
+        // To do this:
+        // 1) We must shift all bound vars in predicate by the length
+        //    of trait ref's bound vars. So, we would end up with predicate like
+        //    Self: Bar1<'a, '^0.1>
+        // 2) We can then apply the trait substs to this, ending up with
+        //    T: Bar1<'^0.0, '^0.1>
+        // 3) Finally, to create the final bound vars, we concatenate the bound
+        //    vars of the trait ref with those of the predicate:
+        //    ['x, 'b]
+        let bound_pred = self.kind();
+        let pred_bound_vars = bound_pred.bound_vars();
+        let trait_bound_vars = trait_ref.bound_vars();
+        // 1) Self: Bar1<'a, '^0.0> -> Self: Bar1<'a, '^0.1>
+        let shifted_pred =
+            tcx.shift_bound_var_indices(trait_bound_vars.len(), bound_pred.skip_binder());
+        // 2) Self: Bar1<'a, '^0.1> -> T: Bar1<'^0.0, '^0.1>
+        let new = shifted_pred.subst(tcx, trait_ref.skip_binder().substs);
+        // 3) ['x] + ['b] -> ['x, 'b]
+        let bound_vars =
+            tcx.mk_bound_variable_kinds(trait_bound_vars.iter().chain(pred_bound_vars));
+        tcx.reuse_or_mk_predicate(self, ty::Binder::bind_with_vars(new, bound_vars))
     }
 }
 
diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs
index acb5c474164..b8f39fce21d 100644
--- a/compiler/rustc_middle/src/ty/print/pretty.rs
+++ b/compiler/rustc_middle/src/ty/print/pretty.rs
@@ -1636,7 +1636,7 @@ impl<F: fmt::Write> PrettyPrinter<'tcx> for FmtPrinter<'_, 'tcx, F> {
                 data.name != kw::Empty && data.name != kw::UnderscoreLifetime
             }
 
-            ty::ReLateBound(_, ty::BoundRegion { kind: br })
+            ty::ReLateBound(_, ty::BoundRegion { kind: br, .. })
             | ty::ReFree(ty::FreeRegion { bound_region: br, .. })
             | ty::RePlaceholder(ty::Placeholder { name: br, .. }) => {
                 if let ty::BrNamed(_, name) = br {
@@ -1715,7 +1715,7 @@ impl<F: fmt::Write> FmtPrinter<'_, '_, F> {
                     return Ok(self);
                 }
             }
-            ty::ReLateBound(_, ty::BoundRegion { kind: br })
+            ty::ReLateBound(_, ty::BoundRegion { kind: br, .. })
             | ty::ReFree(ty::FreeRegion { bound_region: br, .. })
             | ty::RePlaceholder(ty::Placeholder { name: br, .. }) => {
                 if let ty::BrNamed(_, name) = br {
@@ -1821,7 +1821,8 @@ impl<F: fmt::Write> FmtPrinter<'_, 'tcx, F> {
                     ty::BrNamed(DefId::local(CRATE_DEF_INDEX), name)
                 }
             };
-            self.tcx.mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion { kind }))
+            self.tcx
+                .mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion { var: br.var, kind }))
         });
         start_or_continue(&mut self, "", "> ")?;
 
@@ -1865,7 +1866,7 @@ impl<F: fmt::Write> FmtPrinter<'_, 'tcx, F> {
         struct LateBoundRegionNameCollector<'a>(&'a mut FxHashSet<Symbol>);
         impl<'tcx> ty::fold::TypeVisitor<'tcx> for LateBoundRegionNameCollector<'_> {
             fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
-                if let ty::ReLateBound(_, ty::BoundRegion { kind: ty::BrNamed(_, name) }) = *r {
+                if let ty::ReLateBound(_, ty::BoundRegion { kind: ty::BrNamed(_, name), .. }) = *r {
                     self.0.insert(name);
                 }
                 r.super_visit_with(self)
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index 1884df0c67b..e352d0bc756 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -6,6 +6,7 @@ use self::TyKind::*;
 
 use crate::infer::canonical::Canonical;
 use crate::ty::fold::BoundVarsCollector;
+use crate::ty::fold::ValidateBoundVars;
 use crate::ty::subst::{GenericArg, InternalSubsts, Subst, SubstsRef};
 use crate::ty::InferTy::{self, *};
 use crate::ty::{
@@ -63,22 +64,10 @@ pub enum BoundRegionKind {
 #[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable, Debug, PartialOrd, Ord)]
 #[derive(HashStable)]
 pub struct BoundRegion {
+    pub var: BoundVar,
     pub kind: BoundRegionKind,
 }
 
-impl BoundRegion {
-    /// When canonicalizing, we replace unbound inference variables and free
-    /// regions with anonymous late bound regions. This method asserts that
-    /// we have an anonymous late bound region, which hence may refer to
-    /// a canonical variable.
-    pub fn assert_bound_var(&self) -> BoundVar {
-        match self.kind {
-            BoundRegionKind::BrAnon(var) => BoundVar::from_u32(var),
-            _ => bug!("bound region is not anonymous"),
-        }
-    }
-}
-
 impl BoundRegionKind {
     pub fn is_named(&self) -> bool {
         match *self {
@@ -987,13 +976,17 @@ where
         value.visit_with(&mut collector);
         Binder(value, collector.into_vars(tcx))
     }
-}
 
-impl<'tcx, T> Binder<'tcx, T> {
     pub fn bind_with_vars(value: T, vars: &'tcx List<BoundVariableKind>) -> Binder<'tcx, T> {
+        if cfg!(debug_assertions) {
+            let mut validator = ValidateBoundVars::new(vars);
+            value.visit_with(&mut validator);
+        }
         Binder(value, vars)
     }
+}
 
+impl<'tcx, T> Binder<'tcx, T> {
     /// Skips the binder and returns the "bound" value. This is a
     /// risky thing to do because it's easy to get confused about
     /// De Bruijn indices and the like. It is usually better to
@@ -1022,18 +1015,31 @@ impl<'tcx, T> Binder<'tcx, T> {
         Binder(&self.0, self.1)
     }
 
-    pub fn map_bound_ref<F, U>(&self, f: F) -> Binder<'tcx, U>
+    pub fn map_bound_ref_unchecked<F, U>(&self, f: F) -> Binder<'tcx, U>
+    where
+        F: FnOnce(&T) -> U,
+    {
+        let value = f(&self.0);
+        Binder(value, self.1)
+    }
+
+    pub fn map_bound_ref<F, U: TypeFoldable<'tcx>>(&self, f: F) -> Binder<'tcx, U>
     where
         F: FnOnce(&T) -> U,
     {
         self.as_ref().map_bound(f)
     }
 
-    pub fn map_bound<F, U>(self, f: F) -> Binder<'tcx, U>
+    pub fn map_bound<F, U: TypeFoldable<'tcx>>(self, f: F) -> Binder<'tcx, U>
     where
         F: FnOnce(T) -> U,
     {
-        Binder(f(self.0), self.1)
+        let value = f(self.0);
+        if cfg!(debug_assertions) {
+            let mut validator = ValidateBoundVars::new(self.1);
+            value.visit_with(&mut validator);
+        }
+        Binder(value, self.1)
     }
 
     /// Wraps a `value` in a binder, using the same bound variables as the
@@ -1045,7 +1051,14 @@ impl<'tcx, T> Binder<'tcx, T> {
     /// don't actually track bound vars. However, semantically, it is different
     /// because bound vars aren't allowed to change here, whereas they are
     /// in `bind`. This may be (debug) asserted in the future.
-    pub fn rebind<U>(&self, value: U) -> Binder<'tcx, U> {
+    pub fn rebind<U>(&self, value: U) -> Binder<'tcx, U>
+    where
+        U: TypeFoldable<'tcx>,
+    {
+        if cfg!(debug_assertions) {
+            let mut validator = ValidateBoundVars::new(self.bound_vars());
+            value.visit_with(&mut validator);
+        }
         Binder(value, self.1)
     }
 
@@ -1066,20 +1079,6 @@ impl<'tcx, T> Binder<'tcx, T> {
         if self.0.has_escaping_bound_vars() { None } else { Some(self.skip_binder()) }
     }
 
-    /// Given two things that have the same binder level,
-    /// and an operation that wraps on their contents, executes the operation
-    /// and then wraps its result.
-    ///
-    /// `f` should consider bound regions at depth 1 to be free, and
-    /// anything it produces with bound regions at depth 1 will be
-    /// bound in the resulting return value.
-    pub fn fuse<U, F, R>(self, u: Binder<'tcx, U>, f: F) -> Binder<'tcx, R>
-    where
-        F: FnOnce(T, U) -> R,
-    {
-        Binder(f(self.0, u.0), self.1)
-    }
-
     /// Splits the contents into two things that share the same binder
     /// level as the original, returning two distinct binders.
     ///
@@ -1204,7 +1203,7 @@ pub type PolyFnSig<'tcx> = Binder<'tcx, FnSig<'tcx>>;
 impl<'tcx> PolyFnSig<'tcx> {
     #[inline]
     pub fn inputs(&self) -> Binder<'tcx, &'tcx [Ty<'tcx>]> {
-        self.map_bound_ref(|fn_sig| fn_sig.inputs())
+        self.map_bound_ref_unchecked(|fn_sig| fn_sig.inputs())
     }
     #[inline]
     pub fn input(&self, index: usize) -> ty::Binder<'tcx, Ty<'tcx>> {
diff --git a/compiler/rustc_middle/src/ty/util.rs b/compiler/rustc_middle/src/ty/util.rs
index 93fbc1f53b2..b211ac2a79f 100644
--- a/compiler/rustc_middle/src/ty/util.rs
+++ b/compiler/rustc_middle/src/ty/util.rs
@@ -499,18 +499,18 @@ impl<'tcx> TyCtxt<'tcx> {
         self,
         closure_def_id: DefId,
         closure_substs: SubstsRef<'tcx>,
-    ) -> Option<ty::Binder<'tcx, Ty<'tcx>>> {
+        env_region: ty::RegionKind,
+    ) -> Option<Ty<'tcx>> {
         let closure_ty = self.mk_closure(closure_def_id, closure_substs);
-        let br = ty::BoundRegion { kind: ty::BrEnv };
-        let env_region = ty::ReLateBound(ty::INNERMOST, br);
         let closure_kind_ty = closure_substs.as_closure().kind_ty();
         let closure_kind = closure_kind_ty.to_opt_closure_kind()?;
+        debug_assert!(!closure_ty.has_escaping_bound_vars());
         let env_ty = match closure_kind {
             ty::ClosureKind::Fn => self.mk_imm_ref(self.mk_region(env_region), closure_ty),
             ty::ClosureKind::FnMut => self.mk_mut_ref(self.mk_region(env_region), closure_ty),
             ty::ClosureKind::FnOnce => closure_ty,
         };
-        Some(ty::Binder::bind(env_ty, self))
+        Some(env_ty)
     }
 
     /// Returns `true` if the node pointed to by `def_id` is a `static` item.
diff --git a/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs b/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs
index 4f61b8d0910..6ea0ba0a8e1 100644
--- a/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs
+++ b/compiler/rustc_mir/src/borrow_check/diagnostics/mod.rs
@@ -502,7 +502,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         // lifetimes without names with the value `'0`.
         match ty.kind() {
             ty::Ref(
-                ty::RegionKind::ReLateBound(_, ty::BoundRegion { kind: br })
+                ty::RegionKind::ReLateBound(_, ty::BoundRegion { kind: br, .. })
                 | ty::RegionKind::RePlaceholder(ty::PlaceholderRegion { name: br, .. }),
                 _,
                 _,
@@ -523,7 +523,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> {
         let region = match ty.kind() {
             ty::Ref(region, _, _) => {
                 match region {
-                    ty::RegionKind::ReLateBound(_, ty::BoundRegion { kind: br })
+                    ty::RegionKind::ReLateBound(_, ty::BoundRegion { kind: br, .. })
                     | ty::RegionKind::RePlaceholder(ty::PlaceholderRegion { name: br, .. }) => {
                         printer.region_highlight_mode.highlighting_bound_region(*br, counter)
                     }
diff --git a/compiler/rustc_mir/src/borrow_check/universal_regions.rs b/compiler/rustc_mir/src/borrow_check/universal_regions.rs
index f295693781e..c2ac1e289ce 100644
--- a/compiler/rustc_mir/src/borrow_check/universal_regions.rs
+++ b/compiler/rustc_mir/src/borrow_check/universal_regions.rs
@@ -596,24 +596,38 @@ impl<'cx, 'tcx> UniversalRegionsBuilder<'cx, 'tcx> {
                 assert_eq!(self.mir_def.did.to_def_id(), def_id);
                 let closure_sig = substs.as_closure().sig();
                 let inputs_and_output = closure_sig.inputs_and_output();
-                let closure_ty = tcx.closure_env_ty(def_id, substs).unwrap();
-                ty::Binder::fuse(closure_ty, inputs_and_output, |closure_ty, inputs_and_output| {
-                    // The "inputs" of the closure in the
-                    // signature appear as a tuple.  The MIR side
-                    // flattens this tuple.
-                    let (&output, tuplized_inputs) = inputs_and_output.split_last().unwrap();
-                    assert_eq!(tuplized_inputs.len(), 1, "multiple closure inputs");
-                    let inputs = match tuplized_inputs[0].kind() {
-                        ty::Tuple(inputs) => inputs,
-                        _ => bug!("closure inputs not a tuple: {:?}", tuplized_inputs[0]),
-                    };
+                let bound_vars = tcx.mk_bound_variable_kinds(
+                    inputs_and_output
+                        .bound_vars()
+                        .iter()
+                        .chain(iter::once(ty::BoundVariableKind::Region(ty::BrEnv))),
+                );
+                let br = ty::BoundRegion {
+                    var: ty::BoundVar::from_usize(bound_vars.len() - 1),
+                    kind: ty::BrEnv,
+                };
+                let env_region = ty::ReLateBound(ty::INNERMOST, br);
+                let closure_ty = tcx.closure_env_ty(def_id, substs, env_region).unwrap();
+
+                // The "inputs" of the closure in the
+                // signature appear as a tuple.  The MIR side
+                // flattens this tuple.
+                let (&output, tuplized_inputs) =
+                    inputs_and_output.skip_binder().split_last().unwrap();
+                assert_eq!(tuplized_inputs.len(), 1, "multiple closure inputs");
+                let inputs = match tuplized_inputs[0].kind() {
+                    ty::Tuple(inputs) => inputs,
+                    _ => bug!("closure inputs not a tuple: {:?}", tuplized_inputs[0]),
+                };
 
+                ty::Binder::bind_with_vars(
                     tcx.mk_type_list(
                         iter::once(closure_ty)
                             .chain(inputs.iter().map(|k| k.expect_ty()))
                             .chain(iter::once(output)),
-                    )
-                })
+                    ),
+                    bound_vars,
+                )
             }
 
             DefiningTy::Generator(def_id, substs, movability) => {
diff --git a/compiler/rustc_mir_build/src/build/mod.rs b/compiler/rustc_mir_build/src/build/mod.rs
index 9f1de3349a5..c90f94c6d63 100644
--- a/compiler/rustc_mir_build/src/build/mod.rs
+++ b/compiler/rustc_mir_build/src/build/mod.rs
@@ -252,8 +252,13 @@ fn liberated_closure_env_ty(
         _ => bug!("closure expr does not have closure type: {:?}", closure_ty),
     };
 
-    let closure_env_ty = tcx.closure_env_ty(closure_def_id, closure_substs).unwrap();
-    tcx.erase_late_bound_regions(closure_env_ty)
+    let bound_vars =
+        tcx.mk_bound_variable_kinds(std::iter::once(ty::BoundVariableKind::Region(ty::BrEnv)));
+    let br =
+        ty::BoundRegion { var: ty::BoundVar::from_usize(bound_vars.len() - 1), kind: ty::BrEnv };
+    let env_region = ty::ReLateBound(ty::INNERMOST, br);
+    let closure_env_ty = tcx.closure_env_ty(closure_def_id, closure_substs, env_region).unwrap();
+    tcx.erase_late_bound_regions(ty::Binder::bind_with_vars(closure_env_ty, bound_vars))
 }
 
 #[derive(Debug, PartialEq, Eq)]
diff --git a/compiler/rustc_resolve/src/late.rs b/compiler/rustc_resolve/src/late.rs
index 1377bb781d0..25acbd478bf 100644
--- a/compiler/rustc_resolve/src/late.rs
+++ b/compiler/rustc_resolve/src/late.rs
@@ -34,6 +34,7 @@ use tracing::debug;
 
 mod diagnostics;
 crate mod lifetimes;
+crate mod supertraits;
 
 type Res = def::Res<NodeId>;
 
diff --git a/compiler/rustc_resolve/src/late/lifetimes.rs b/compiler/rustc_resolve/src/late/lifetimes.rs
index 8e0309225de..79d81ef047e 100644
--- a/compiler/rustc_resolve/src/late/lifetimes.rs
+++ b/compiler/rustc_resolve/src/late/lifetimes.rs
@@ -30,7 +30,7 @@ use std::cell::Cell;
 use std::fmt;
 use std::mem::take;
 
-use tracing::debug;
+use tracing::{debug, span, Level};
 
 // This counts the no of times a lifetime is used
 #[derive(Clone, Copy, Debug)]
@@ -44,7 +44,7 @@ trait RegionExt {
 
     fn late(index: u32, hir_map: &Map<'_>, param: &GenericParam<'_>) -> (ParamName, Region);
 
-    fn late_anon(named_late_bound_vars: u32, anon_index: &Cell<u32>) -> Region;
+    fn late_anon(named_late_bound_vars: u32, index: &Cell<u32>) -> Region;
 
     fn id(&self) -> Option<DefId>;
 
@@ -150,6 +150,8 @@ struct NamedRegionMap {
     // be late-bound if (a) it does NOT appear in a where-clause and
     // (b) it DOES appear in the arguments.
     late_bound: HirIdSet,
+
+    late_bound_vars: HirIdMap<Vec<ty::BoundVariableKind>>,
 }
 
 crate struct LifetimeContext<'a, 'tcx> {
@@ -164,13 +166,15 @@ crate struct LifetimeContext<'a, 'tcx> {
     /// correct when representing these constraints, we should only introduce one
     /// scope. However, we want to support both locations for the quantifier and
     /// during lifetime resolution we want precise information (so we can't
-    /// desugar in an earlier phase).
+    /// desugar in an earlier phase). Moreso, an error here doesn't cause a bail
+    /// from type checking, so we need to be extra careful that we don't lose
+    /// any bound var information.
     ///
     /// So, if we encounter a quantifier at the outer scope, we set
     /// `trait_ref_hack` to `true` (and introduce a scope), and then if we encounter
     /// a quantifier at the inner scope, we error. If `trait_ref_hack` is `false`,
     /// then we introduce the scope at the inner quantifier.
-    trait_ref_hack: bool,
+    trait_ref_hack: Option<(Vec<ty::BoundVariableKind>, u32)>,
 
     /// Used to disallow the use of in-band lifetimes in `fn` or `Fn` syntax.
     is_in_fn_syntax: bool,
@@ -228,8 +232,19 @@ enum Scope<'a> {
         /// of the resulting opaque type.
         opaque_type_parent: bool,
 
+        /// We need to keep track of the number of named late bound vars, since
+        /// we may have elided lifetimes that have an index starting *after*
+        /// these.
         named_late_bound_vars: u32,
 
+        from_poly_trait_ref: bool,
+
+        /// The late bound vars for a given item are stored by `HirId` to be
+        /// queried later. However, if we enter an elision scope, we have to
+        /// later append the elided bound vars to the list and need to know what
+        /// to append to.
+        hir_id: hir::HirId,
+
         s: ScopeRef<'a>,
     },
 
@@ -257,6 +272,51 @@ enum Scope<'a> {
         s: ScopeRef<'a>,
     },
 
+    /// This is a particularly interesting consequence of how we handle poly
+    /// trait refs. See `trait_ref_hack` for additional info. This bit is
+    /// important w.r.t. querying late-bound vars.
+    ///
+    /// To completely understand why this is necessary, first it's important to
+    /// realize that `T: for<'a> U + for<'a, 'b> V` is actually two separate
+    /// trait refs: `T: for<'a> U` and `T: for<'b> V` and as such, the late
+    /// bound vars on each needs to be tracked separately. Also, in this case,
+    /// are *three* relevant `HirId`s: one for the entire bound and one
+    /// for each separate one.
+    ///
+    /// Next, imagine three different poly trait refs:
+    ///   1) `for<'a, 'b> T: U<'a, 'b>`
+    ///   2) `T: for<'a, 'b> U<'a, 'b>`
+    ///   3) `for<'a> T: for<'b> U<'a, 'b>`
+    ///
+    /// First, note that the third example is semantically invalid and an error,
+    /// but we *must* handle it as valid, since type checking isn't bailed out
+    /// of. Other than that, if ask for bound vars for each, we expect
+    /// `['a, 'b]`. If we *didn't* allow binders before `T`, then we would
+    /// always introduce a binder scope at the inner trait ref. This is great,
+    /// becauase later on during type-checking, we will ask "what are the late
+    /// bound vars on this trait ref". However, because we allow bound vars on
+    /// the bound itself, we have to have some way of keeping track of the fact
+    /// that we actually want to store the late bound vars as being associated
+    /// with the trait ref; this is that.
+    ///
+    /// One alternative way to handle this would be to just introduce a new
+    /// `Binder` scope, but that's semantically a bit different, since bound
+    /// vars from both `for<...>`s *do* share the same binder level.
+    TraitRefHackInner {
+        hir_id: hir::HirId,
+        named_late_bound_vars: u32,
+        s: ScopeRef<'a>,
+    },
+
+    /// When we have nested trait refs, we concanetate late bound vars for inner
+    /// trait refs from outer ones. But we also need to include any HRTB
+    /// lifetimes encountered when identifying the trait that an associated type
+    /// is declared on.
+    Supertrait {
+        lifetimes: Vec<ty::BoundVariableKind>,
+        s: ScopeRef<'a>,
+    },
+
     Root,
 }
 
@@ -272,6 +332,8 @@ impl<'a> fmt::Debug for TruncatedScopeDebug<'a> {
                 track_lifetime_uses,
                 opaque_type_parent,
                 named_late_bound_vars,
+                from_poly_trait_ref,
+                hir_id,
                 s: _,
             } => f
                 .debug_struct("Binder")
@@ -280,6 +342,8 @@ impl<'a> fmt::Debug for TruncatedScopeDebug<'a> {
                 .field("track_lifetime_uses", track_lifetime_uses)
                 .field("opaque_type_parent", opaque_type_parent)
                 .field("named_late_bound_vars", named_late_bound_vars)
+                .field("from_poly_trait_ref", from_poly_trait_ref)
+                .field("hir_id", hir_id)
                 .field("s", &"..")
                 .finish(),
             Scope::Body { id, s: _ } => {
@@ -293,6 +357,17 @@ impl<'a> fmt::Debug for TruncatedScopeDebug<'a> {
                 .field("lifetime", lifetime)
                 .field("s", &"..")
                 .finish(),
+            Scope::TraitRefHackInner { hir_id, named_late_bound_vars, s: _ } => f
+                .debug_struct("TraitRefHackInner")
+                .field("hir_id", hir_id)
+                .field("named_late_bound_vars", named_late_bound_vars)
+                .field("s", &"..")
+                .finish(),
+            Scope::Supertrait { lifetimes, s: _ } => f
+                .debug_struct("Supertrait")
+                .field("lifetimes", lifetimes)
+                .field("s", &"..")
+                .finish(),
             Scope::Root => f.debug_struct("Root").finish(),
         }
     }
@@ -342,6 +417,7 @@ pub fn provide(providers: &mut ty::query::Providers) {
                 _ => None,
             }
         },
+        late_bound_vars_map: |tcx, id| resolve_lifetimes_for(tcx, id).late_bound_vars.get(&id),
 
         ..*providers
     };
@@ -399,13 +475,16 @@ fn do_resolve(
     trait_definition_only: bool,
 ) -> ResolveLifetimes {
     let item = tcx.hir().expect_item(tcx.hir().local_def_id_to_hir_id(local_def_id));
-    let mut named_region_map =
-        NamedRegionMap { defs: Default::default(), late_bound: Default::default() };
+    let mut named_region_map = NamedRegionMap {
+        defs: Default::default(),
+        late_bound: Default::default(),
+        late_bound_vars: Default::default(),
+    };
     let mut visitor = LifetimeContext {
         tcx,
         map: &mut named_region_map,
         scope: ROOT_SCOPE,
-        trait_ref_hack: false,
+        trait_ref_hack: None,
         is_in_fn_syntax: false,
         is_in_const_generic: false,
         trait_definition_only,
@@ -426,6 +505,10 @@ fn do_resolve(
         let map = rl.late_bound.entry(hir_id.owner).or_default();
         map.insert(hir_id.local_id);
     }
+    for (hir_id, v) in named_region_map.late_bound_vars {
+        let map = rl.late_bound_vars.entry(hir_id.owner).or_default();
+        map.insert(hir_id.local_id, v);
+    }
 
     debug!(?rl.defs);
     rl
@@ -511,6 +594,19 @@ fn sub_items_have_self_param(node: &hir::ItemKind<'_>) -> bool {
     matches!(*node, hir::ItemKind::Trait(..) | hir::ItemKind::TraitAlias(..))
 }
 
+fn late_region_as_bound_region<'tcx>(tcx: TyCtxt<'tcx>, region: &Region) -> ty::BoundVariableKind {
+    match region {
+        Region::LateBound(_, _, def_id, _) => {
+            let name = tcx.hir().name(tcx.hir().local_def_id_to_hir_id(def_id.expect_local()));
+            ty::BoundVariableKind::Region(ty::BrNamed(*def_id, name))
+        }
+        Region::LateBoundAnon(_, _, anon_idx) => {
+            ty::BoundVariableKind::Region(ty::BrAnon(*anon_idx))
+        }
+        _ => bug!("{:?} is not a late region", region),
+    }
+}
+
 impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
     type Map = Map<'tcx>;
 
@@ -538,11 +634,59 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
         self.labels_in_fn = saved;
     }
 
+    fn visit_fn(
+        &mut self,
+        fk: intravisit::FnKind<'tcx>,
+        fd: &'tcx hir::FnDecl<'tcx>,
+        b: hir::BodyId,
+        s: rustc_span::Span,
+        hir_id: hir::HirId,
+    ) {
+        let name = match fk {
+            intravisit::FnKind::ItemFn(id, _, _, _) => id.as_str(),
+            intravisit::FnKind::Method(id, _, _) => id.as_str(),
+            intravisit::FnKind::Closure => Symbol::intern("closure").as_str(),
+        };
+        let name: &str = &name;
+        let span = span!(Level::DEBUG, "visit_fn", name);
+        let _enter = span.enter();
+        match fk {
+            // Any `Binders` are handled elsewhere
+            intravisit::FnKind::ItemFn(..) | intravisit::FnKind::Method(..) => {
+                intravisit::walk_fn(self, fk, fd, b, s, hir_id)
+            }
+            intravisit::FnKind::Closure => {
+                self.map.late_bound_vars.insert(hir_id, vec![]);
+                let scope = Scope::Binder {
+                    hir_id,
+                    lifetimes: FxHashMap::default(),
+                    next_early_index: self.next_early_index(),
+                    s: self.scope,
+                    track_lifetime_uses: true,
+                    opaque_type_parent: false,
+                    named_late_bound_vars: 0,
+                    from_poly_trait_ref: false,
+                };
+                self.with(scope, move |_old_scope, this| {
+                    intravisit::walk_fn(this, fk, fd, b, s, hir_id)
+                });
+            }
+        }
+    }
+
     fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) {
+        match &item.kind {
+            hir::ItemKind::Impl(hir::Impl { of_trait, .. }) => {
+                if let Some(of_trait) = of_trait {
+                    self.map.late_bound_vars.insert(of_trait.hir_ref_id, Vec::default());
+                }
+            }
+            _ => {}
+        }
         match item.kind {
             hir::ItemKind::Fn(ref sig, ref generics, _) => {
                 self.missing_named_lifetime_spots.push(generics.into());
-                self.visit_early_late(None, &sig.decl, generics, |this| {
+                self.visit_early_late(None, item.hir_id(), &sig.decl, generics, |this| {
                     intravisit::walk_item(this, item);
                 });
                 self.missing_named_lifetime_spots.pop();
@@ -590,6 +734,16 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                                     self.map.late_bound.insert(hir::HirId { owner, local_id });
                                 });
                             }
+                            for (&owner, late_bound_vars) in
+                                resolved_lifetimes.late_bound_vars.iter()
+                            {
+                                late_bound_vars.iter().for_each(|(&local_id, late_bound_vars)| {
+                                    self.map.late_bound_vars.insert(
+                                        hir::HirId { owner, local_id },
+                                        late_bound_vars.clone(),
+                                    );
+                                });
+                            }
                             break;
                         }
                         hir::Node::Crate(_) => bug!("No Item about an OpaqueTy"),
@@ -629,12 +783,15 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                         }
                     })
                     .collect();
+                self.map.late_bound_vars.insert(item.hir_id(), vec![]);
                 let scope = Scope::Binder {
+                    hir_id: item.hir_id(),
                     lifetimes,
                     next_early_index: index + non_lifetime_count,
                     opaque_type_parent: true,
                     track_lifetime_uses,
                     named_late_bound_vars: 0,
+                    from_poly_trait_ref: false,
                     s: ROOT_SCOPE,
                 };
                 self.with(scope, |old_scope, this| {
@@ -649,7 +806,7 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
     fn visit_foreign_item(&mut self, item: &'tcx hir::ForeignItem<'tcx>) {
         match item.kind {
             hir::ForeignItemKind::Fn(ref decl, _, ref generics) => {
-                self.visit_early_late(None, decl, generics, |this| {
+                self.visit_early_late(None, item.hir_id(), decl, generics, |this| {
                     intravisit::walk_foreign_item(this, item);
                 })
             }
@@ -681,23 +838,32 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 };
                 self.missing_named_lifetime_spots
                     .push(MissingLifetimeSpot::HigherRanked { span, span_type });
+                let mut named_late_bound_vars = 0;
+                let (lifetimes, binders): (FxHashMap<hir::ParamName, Region>, Vec<_>) = c
+                    .generic_params
+                    .iter()
+                    .filter_map(|param| match param.kind {
+                        GenericParamKind::Lifetime { .. } => {
+                            let late_bound_idx = named_late_bound_vars;
+                            named_late_bound_vars += 1;
+                            let pair = Region::late(late_bound_idx, &self.tcx.hir(), param);
+                            let r = pair.1.clone();
+                            let r = late_region_as_bound_region(self.tcx, &r);
+                            Some((pair, r))
+                        }
+                        _ => None,
+                    })
+                    .unzip();
+                self.map.late_bound_vars.insert(ty.hir_id, binders);
                 let scope = Scope::Binder {
-                    lifetimes: c
-                        .generic_params
-                        .iter()
-                        .enumerate()
-                        .filter_map(|(idx, param)| match param.kind {
-                            GenericParamKind::Lifetime { .. } => {
-                                Some(Region::late(idx as u32, &self.tcx.hir(), param))
-                            }
-                            _ => None,
-                        })
-                        .collect(),
+                    hir_id: ty.hir_id,
+                    lifetimes,
                     s: self.scope,
                     next_early_index,
                     track_lifetime_uses: true,
                     opaque_type_parent: false,
-                    named_late_bound_vars: c.generic_params.len() as u32,
+                    named_late_bound_vars,
+                    from_poly_trait_ref: false,
                 };
                 self.with(scope, |old_scope, this| {
                     // a bare fn has no bounds, so everything
@@ -874,18 +1040,21 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                     }
                 }
                 let next_early_index = index + non_lifetime_count;
+                self.map.late_bound_vars.insert(ty.hir_id, vec![]);
 
                 if let Some(elision_region) = elision {
                     let scope =
                         Scope::Elision { elide: Elide::Exact(elision_region), s: self.scope };
                     self.with(scope, |_old_scope, this| {
                         let scope = Scope::Binder {
+                            hir_id: ty.hir_id,
                             lifetimes,
                             next_early_index,
                             s: this.scope,
                             track_lifetime_uses: true,
                             opaque_type_parent: false,
                             named_late_bound_vars: 0,
+                            from_poly_trait_ref: false,
                         };
                         this.with(scope, |_old_scope, this| {
                             this.visit_generics(generics);
@@ -896,12 +1065,14 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                     });
                 } else {
                     let scope = Scope::Binder {
+                        hir_id: ty.hir_id,
                         lifetimes,
                         next_early_index,
                         s: self.scope,
                         track_lifetime_uses: true,
                         opaque_type_parent: false,
                         named_late_bound_vars: 0,
+                        from_poly_trait_ref: false,
                     };
                     self.with(scope, |_old_scope, this| {
                         this.visit_generics(generics);
@@ -923,6 +1094,7 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 let tcx = self.tcx;
                 self.visit_early_late(
                     Some(tcx.hir().get_parent_item(trait_item.hir_id())),
+                    trait_item.hir_id(),
                     &sig.decl,
                     &trait_item.generics,
                     |this| intravisit::walk_trait_item(this, trait_item),
@@ -948,13 +1120,16 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                         }
                     })
                     .collect();
+                self.map.late_bound_vars.insert(trait_item.hir_id(), vec![]);
                 let scope = Scope::Binder {
+                    hir_id: trait_item.hir_id(),
                     lifetimes,
                     next_early_index: index + non_lifetime_count,
                     s: self.scope,
                     track_lifetime_uses: true,
                     opaque_type_parent: true,
                     named_late_bound_vars: 0,
+                    from_poly_trait_ref: false,
                 };
                 self.with(scope, |old_scope, this| {
                     this.check_lifetime_params(old_scope, &generics.params);
@@ -986,6 +1161,7 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 let tcx = self.tcx;
                 self.visit_early_late(
                     Some(tcx.hir().get_parent_item(impl_item.hir_id())),
+                    impl_item.hir_id(),
                     &sig.decl,
                     &impl_item.generics,
                     |this| intravisit::walk_impl_item(this, impl_item),
@@ -998,7 +1174,7 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 let mut index = self.next_early_index();
                 let mut non_lifetime_count = 0;
                 debug!("visit_ty: index = {}", index);
-                let lifetimes = generics
+                let lifetimes: FxHashMap<hir::ParamName, Region> = generics
                     .params
                     .iter()
                     .filter_map(|param| match param.kind {
@@ -1011,13 +1187,16 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                         }
                     })
                     .collect();
+                self.map.late_bound_vars.insert(ty.hir_id, vec![]);
                 let scope = Scope::Binder {
+                    hir_id: ty.hir_id,
                     lifetimes,
                     next_early_index: index + non_lifetime_count,
                     s: self.scope,
                     track_lifetime_uses: true,
                     opaque_type_parent: true,
                     named_late_bound_vars: 0,
+                    from_poly_trait_ref: false,
                 };
                 self.with(scope, |old_scope, this| {
                     this.check_lifetime_params(old_scope, &generics.params);
@@ -1100,32 +1279,40 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                     ref bound_generic_params,
                     ..
                 }) => {
-                    let lifetimes: FxHashMap<_, _> = bound_generic_params
+                    let mut named_late_bound_vars = 0;
+                    let (lifetimes, binders): (FxHashMap<_, _>, Vec<_>) = bound_generic_params
                         .iter()
-                        .enumerate()
-                        .filter_map(|(idx, param)| match param.kind {
+                        .filter_map(|param| match param.kind {
                             GenericParamKind::Lifetime { .. } => {
-                                Some(Region::late(idx as u32, &self.tcx.hir(), param))
+                                let late_bound_idx = named_late_bound_vars;
+                                named_late_bound_vars += 1;
+                                let pair = Region::late(late_bound_idx, &self.tcx.hir(), param);
+                                let r = pair.1.clone();
+                                let r = late_region_as_bound_region(self.tcx, &r);
+                                Some((pair, r))
                             }
                             _ => None,
                         })
-                        .collect();
+                        .unzip();
+                    self.map.late_bound_vars.insert(bounded_ty.hir_id, binders.clone());
                     if !lifetimes.is_empty() {
                         let next_early_index = self.next_early_index();
                         let scope = Scope::Binder {
+                            hir_id: bounded_ty.hir_id,
                             lifetimes,
                             s: self.scope,
                             next_early_index,
                             track_lifetime_uses: true,
                             opaque_type_parent: false,
-                            named_late_bound_vars: bound_generic_params.len() as u32,
+                            named_late_bound_vars,
+                            from_poly_trait_ref: true,
                         };
                         let result = self.with(scope, |old_scope, this| {
                             this.check_lifetime_params(old_scope, &bound_generic_params);
                             this.visit_ty(&bounded_ty);
-                            this.trait_ref_hack = true;
+                            this.trait_ref_hack = Some((binders, named_late_bound_vars));
                             walk_list!(this, visit_param_bound, bounds);
-                            this.trait_ref_hack = false;
+                            this.trait_ref_hack = None;
                         });
                         result
                     } else {
@@ -1155,14 +1342,17 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 
     fn visit_param_bound(&mut self, bound: &'tcx hir::GenericBound<'tcx>) {
         match bound {
-            hir::GenericBound::LangItemTrait { .. } if !self.trait_ref_hack => {
+            hir::GenericBound::LangItemTrait(_, _, hir_id, _) if self.trait_ref_hack.is_none() => {
+                self.map.late_bound_vars.insert(*hir_id, vec![]);
                 let scope = Scope::Binder {
+                    hir_id: *hir_id,
                     lifetimes: FxHashMap::default(),
                     s: self.scope,
                     next_early_index: self.next_early_index(),
                     track_lifetime_uses: true,
                     opaque_type_parent: false,
                     named_late_bound_vars: 0,
+                    from_poly_trait_ref: false,
                 };
                 self.with(scope, |_, this| {
                     intravisit::walk_param_bound(this, bound);
@@ -1181,40 +1371,144 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
 
         let should_pop_missing_lt = self.is_trait_ref_fn_scope(trait_ref);
 
-        let trait_ref_hack = take(&mut self.trait_ref_hack);
-        if !trait_ref_hack
-            || trait_ref
-                .bound_generic_params
-                .iter()
-                .any(|param| matches!(param.kind, GenericParamKind::Lifetime { .. }))
-        {
-            if trait_ref_hack {
-                struct_span_err!(
-                    self.tcx.sess,
-                    trait_ref.span,
-                    E0316,
-                    "nested quantification of lifetimes"
-                )
-                .emit();
-            }
-            let next_early_index = self.next_early_index();
-            let scope = Scope::Binder {
-                lifetimes: trait_ref
+        let trait_ref_hack = self.trait_ref_hack.take();
+        let next_early_index = self.next_early_index();
+        // See note on `trait_ref_hack`. If `for<..>` has been defined in both
+        // the outer and inner part of the trait ref, emit an error.
+        let has_lifetimes = trait_ref.bound_generic_params.iter().any(|param| match param.kind {
+            GenericParamKind::Lifetime { .. } => true,
+            _ => false,
+        });
+        if trait_ref_hack.is_some() && has_lifetimes {
+            struct_span_err!(
+                self.tcx.sess,
+                trait_ref.span,
+                E0316,
+                "nested quantification of lifetimes"
+            )
+            .emit();
+        }
+
+        let (binders, named_late_bound_vars, lifetimes) =
+            if let Some((mut binders, mut named_late_bound_vars)) = trait_ref_hack.clone() {
+                let initial_binders = named_late_bound_vars;
+                binders.extend(trait_ref.bound_generic_params.iter().filter_map(|param| {
+                    match param.kind {
+                        GenericParamKind::Lifetime { .. } => {
+                            let late_bound_idx = named_late_bound_vars;
+                            named_late_bound_vars += 1;
+                            let region = Region::late(late_bound_idx, &self.tcx.hir(), param).1;
+                            Some(late_region_as_bound_region(self.tcx, &region))
+                        }
+                        GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => None,
+                    }
+                }));
+
+                let mut named_late_bound_vars = initial_binders;
+                let lifetimes: FxHashMap<hir::ParamName, Region> = trait_ref
                     .bound_generic_params
                     .iter()
-                    .enumerate()
-                    .filter_map(|(idx, param)| match param.kind {
+                    .filter_map(|param| match param.kind {
                         GenericParamKind::Lifetime { .. } => {
-                            Some(Region::late(idx as u32, &self.tcx.hir(), param))
+                            let late_bound_idx = named_late_bound_vars;
+                            named_late_bound_vars += 1;
+                            Some(Region::late(late_bound_idx, &self.tcx.hir(), param))
                         }
                         _ => None,
                     })
-                    .collect(),
+                    .collect();
+
+                (binders, named_late_bound_vars, lifetimes)
+            } else {
+                let mut supertrait_lifetimes = vec![];
+                let mut scope = self.scope;
+                let mut binders = loop {
+                    match scope {
+                        Scope::Body { .. } | Scope::Root => {
+                            break vec![];
+                        }
+
+                        Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
+                            scope = s;
+                        }
+
+                        Scope::TraitRefHackInner { hir_id, .. } => {
+                            // Nested poly trait refs have the binders concatenated
+                            // If we reach `TraitRefHackInner`, then there is only one more `Binder` above us,
+                            // over all the bounds. We don't want this, since all the lifetimes we care about
+                            // are here anyways.
+                            let mut full_binders =
+                                self.map.late_bound_vars.entry(*hir_id).or_default().clone();
+                            full_binders.extend(supertrait_lifetimes.into_iter());
+                            break full_binders;
+                        }
+
+                        Scope::Supertrait { s, lifetimes } => {
+                            supertrait_lifetimes = lifetimes.clone();
+                            scope = s;
+                        }
+
+                        Scope::Binder { hir_id, from_poly_trait_ref, .. } => {
+                            if !from_poly_trait_ref {
+                                // We should only see super trait lifetimes if there is a `Binder` above
+                                assert!(supertrait_lifetimes.is_empty());
+                                break vec![];
+                            }
+                            // Nested poly trait refs have the binders concatenated
+                            let mut full_binders =
+                                self.map.late_bound_vars.entry(*hir_id).or_default().clone();
+                            full_binders.extend(supertrait_lifetimes.into_iter());
+                            break full_binders;
+                        }
+                    }
+                };
+                let mut named_late_bound_vars = binders.len() as u32;
+                let local_binders: Vec<_> = trait_ref
+                    .bound_generic_params
+                    .iter()
+                    .filter_map(|param| match param.kind {
+                        GenericParamKind::Lifetime { .. } => {
+                            let late_bound_idx = named_late_bound_vars;
+                            named_late_bound_vars += 1;
+                            let region = Region::late(late_bound_idx, &self.tcx.hir(), param).1;
+                            Some(late_region_as_bound_region(self.tcx, &region))
+                        }
+                        GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => None,
+                    })
+                    .collect();
+
+                let mut named_late_bound_vars = binders.len() as u32;
+                let lifetimes: FxHashMap<hir::ParamName, Region> = trait_ref
+                    .bound_generic_params
+                    .iter()
+                    .filter_map(|param| match param.kind {
+                        GenericParamKind::Lifetime { .. } => {
+                            let late_bound_idx = named_late_bound_vars;
+                            named_late_bound_vars += 1;
+                            Some(Region::late(late_bound_idx, &self.tcx.hir(), param))
+                        }
+                        _ => None,
+                    })
+                    .collect();
+
+                binders.extend(local_binders.into_iter());
+
+                (binders, named_late_bound_vars, lifetimes)
+            };
+
+        debug!(?binders);
+        self.map.late_bound_vars.insert(trait_ref.trait_ref.hir_ref_id, binders);
+
+        if trait_ref_hack.is_none() || has_lifetimes {
+            let scope = Scope::Binder {
+                hir_id: trait_ref.trait_ref.hir_ref_id,
+                lifetimes,
                 s: self.scope,
                 next_early_index,
                 track_lifetime_uses: true,
                 opaque_type_parent: false,
-                named_late_bound_vars: trait_ref.bound_generic_params.len() as u32,
+                named_late_bound_vars: named_late_bound_vars as u32,
+                from_poly_trait_ref: true,
             };
             self.with(scope, |old_scope, this| {
                 this.check_lifetime_params(old_scope, &trait_ref.bound_generic_params);
@@ -1222,7 +1516,14 @@ impl<'a, 'tcx> Visitor<'tcx> for LifetimeContext<'a, 'tcx> {
                 this.visit_trait_ref(&trait_ref.trait_ref);
             });
         } else {
-            self.visit_trait_ref(&trait_ref.trait_ref);
+            let scope = Scope::TraitRefHackInner {
+                hir_id: trait_ref.trait_ref.hir_ref_id,
+                named_late_bound_vars: named_late_bound_vars as u32,
+                s: self.scope,
+            };
+            self.with(scope, |_old_scope, this| {
+                this.visit_trait_ref(&trait_ref.trait_ref);
+            });
         }
         self.trait_ref_hack = trait_ref_hack;
         if should_pop_missing_lt {
@@ -1374,7 +1675,9 @@ fn extract_labels(ctxt: &mut LifetimeContext<'_, '_>, body: &hir::Body<'_>) {
             match *scope {
                 Scope::Body { s, .. }
                 | Scope::Elision { s, .. }
-                | Scope::ObjectLifetimeDefault { s, .. } => {
+                | Scope::ObjectLifetimeDefault { s, .. }
+                | Scope::TraitRefHackInner { s, .. }
+                | Scope::Supertrait { s, .. } => {
                     scope = s;
                 }
 
@@ -1563,11 +1866,12 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
         let labels_in_fn = take(&mut self.labels_in_fn);
         let xcrate_object_lifetime_defaults = take(&mut self.xcrate_object_lifetime_defaults);
         let missing_named_lifetime_spots = take(&mut self.missing_named_lifetime_spots);
+        let trait_ref_hack = take(&mut self.trait_ref_hack);
         let mut this = LifetimeContext {
             tcx: *tcx,
             map,
             scope: &wrap_scope,
-            trait_ref_hack: self.trait_ref_hack,
+            trait_ref_hack,
             is_in_fn_syntax: self.is_in_fn_syntax,
             is_in_const_generic: self.is_in_const_generic,
             trait_definition_only: self.trait_definition_only,
@@ -1587,6 +1891,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
         self.labels_in_fn = this.labels_in_fn;
         self.xcrate_object_lifetime_defaults = this.xcrate_object_lifetime_defaults;
         self.missing_named_lifetime_spots = this.missing_named_lifetime_spots;
+        self.trait_ref_hack = this.trait_ref_hack;
     }
 
     /// helper method to determine the span to remove when suggesting the
@@ -1881,6 +2186,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
     fn visit_early_late<F>(
         &mut self,
         parent_id: Option<hir::HirId>,
+        hir_id: hir::HirId,
         decl: &'tcx hir::FnDecl<'tcx>,
         generics: &'tcx hir::Generics<'tcx>,
         walk: F,
@@ -1890,16 +2196,16 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
         insert_late_bound_lifetimes(self.map, decl, generics);
 
         // Find the start of nested early scopes, e.g., in methods.
-        let mut index = 0;
+        let mut next_early_index = 0;
         if let Some(parent_id) = parent_id {
             let parent = self.tcx.hir().expect_item(parent_id);
             if sub_items_have_self_param(&parent.kind) {
-                index += 1; // Self comes before lifetimes
+                next_early_index += 1; // Self comes before lifetimes
             }
             match parent.kind {
                 hir::ItemKind::Trait(_, _, ref generics, ..)
                 | hir::ItemKind::Impl(hir::Impl { ref generics, .. }) => {
-                    index += generics.params.len() as u32;
+                    next_early_index += generics.params.len() as u32;
                 }
                 _ => {}
             }
@@ -1907,17 +2213,17 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 
         let mut non_lifetime_count = 0;
         let mut named_late_bound_vars = 0;
-        let lifetimes = generics
+        let lifetimes: FxHashMap<hir::ParamName, Region> = generics
             .params
             .iter()
-            .enumerate()
-            .filter_map(|(idx, param)| match param.kind {
+            .filter_map(|param| match param.kind {
                 GenericParamKind::Lifetime { .. } => {
                     if self.map.late_bound.contains(&param.hir_id) {
+                        let late_bound_idx = named_late_bound_vars;
                         named_late_bound_vars += 1;
-                        Some(Region::late(idx as u32, &self.tcx.hir(), param))
+                        Some(Region::late(late_bound_idx, &self.tcx.hir(), param))
                     } else {
-                        Some(Region::early(&self.tcx.hir(), &mut index, param))
+                        Some(Region::early(&self.tcx.hir(), &mut next_early_index, param))
                     }
                 }
                 GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => {
@@ -1926,15 +2232,37 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                 }
             })
             .collect();
-        let next_early_index = index + non_lifetime_count;
+        let next_early_index = next_early_index + non_lifetime_count;
 
+        let mut named_late_bound_vars = 0;
+        let binders: Vec<_> = generics
+            .params
+            .iter()
+            .filter_map(|param| match param.kind {
+                GenericParamKind::Lifetime { .. } => {
+                    if self.map.late_bound.contains(&param.hir_id) {
+                        let late_bound_idx = named_late_bound_vars;
+                        named_late_bound_vars += 1;
+                        let r = Region::late(late_bound_idx, &self.tcx.hir(), param).1;
+                        let r = late_region_as_bound_region(self.tcx, &r);
+                        Some(r)
+                    } else {
+                        None
+                    }
+                }
+                GenericParamKind::Type { .. } | GenericParamKind::Const { .. } => None,
+            })
+            .collect();
+        self.map.late_bound_vars.insert(hir_id, binders);
         let scope = Scope::Binder {
+            hir_id,
             lifetimes,
             next_early_index,
             s: self.scope,
             opaque_type_parent: true,
             track_lifetime_uses: false,
-            named_late_bound_vars,
+            named_late_bound_vars: named_late_bound_vars as u32,
+            from_poly_trait_ref: false,
         };
         self.with(scope, move |old_scope, this| {
             this.check_lifetime_params(old_scope, &generics.params);
@@ -1957,7 +2285,9 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                 Scope::Binder { s, .. }
                 | Scope::Body { s, .. }
                 | Scope::Elision { s, .. }
-                | Scope::ObjectLifetimeDefault { s, .. } => scope = s,
+                | Scope::ObjectLifetimeDefault { s, .. }
+                | Scope::TraitRefHackInner { s, .. }
+                | Scope::Supertrait { s, .. } => scope = s,
             }
         }
     }
@@ -1989,6 +2319,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
         // given name or we run out of scopes.
         // search.
         let mut late_depth = 0;
+        let mut in_poly_trait_ref = false;
         let mut scope = self.scope;
         let mut outermost_body = None;
         let result = loop {
@@ -2006,7 +2337,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     break None;
                 }
 
-                Scope::Binder { ref lifetimes, s, .. } => {
+                Scope::Binder { ref lifetimes, from_poly_trait_ref, s, .. } => {
                     match lifetime_ref.name {
                         LifetimeName::Param(param_name) => {
                             if let Some(&def) = lifetimes.get(&param_name.normalize_to_macros_2_0())
@@ -2017,11 +2348,35 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                         _ => bug!("expected LifetimeName::Param"),
                     }
 
-                    late_depth += 1;
+                    match (from_poly_trait_ref, in_poly_trait_ref) {
+                        // This is the first binder we see that is a poly trait ref; add one to the
+                        // late depth and mark that we're potentially in nested trait refs.
+                        (true, false) => {
+                            in_poly_trait_ref = true;
+                            late_depth += 1;
+                        }
+                        // We've already seen a binder that is a poly trait ref and this one is too,
+                        // that means that they are nested and we are concatenating the bound vars;
+                        // don't increase the late depth.
+                        (true, true) => {}
+                        // We've exited nested poly trait refs; add one to the late depth and mark
+                        // that we are no longer in nested trait refs
+                        (false, true) => {
+                            in_poly_trait_ref = false;
+                            late_depth += 1;
+                        }
+                        // Any other kind of nested binders: just increase late depth.
+                        (false, false) => {
+                            late_depth += 1;
+                        }
+                    }
                     scope = s;
                 }
 
-                Scope::Elision { s, .. } | Scope::ObjectLifetimeDefault { s, .. } => {
+                Scope::Elision { s, .. }
+                | Scope::ObjectLifetimeDefault { s, .. }
+                | Scope::TraitRefHackInner { s, .. }
+                | Scope::Supertrait { s, .. } => {
                     scope = s;
                 }
             }
@@ -2117,6 +2472,8 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                 _ => None,
             })
             .collect();
+        // We short-circuit here if all are elided in order to pluralize
+        // possible errors
         if elide_lifetimes {
             self.resolve_elided_lifetimes(&lifetimes);
         } else {
@@ -2171,7 +2528,9 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 
                         Scope::Binder { s, .. }
                         | Scope::Elision { s, .. }
-                        | Scope::ObjectLifetimeDefault { s, .. } => {
+                        | Scope::ObjectLifetimeDefault { s, .. }
+                        | Scope::TraitRefHackInner { s, .. }
+                        | Scope::Supertrait { s, .. } => {
                             scope = s;
                         }
                     }
@@ -2271,15 +2630,50 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
             generic_args.args.iter().any(|arg| matches!(arg, GenericArg::Lifetime(_)));
 
         // Resolve lifetimes found in the type `XX` from `Item = XX` bindings.
-        for b in generic_args.bindings {
+        for binding in generic_args.bindings {
             let scope = Scope::ObjectLifetimeDefault {
                 lifetime: if has_lifetime_parameter { None } else { Some(Region::Static) },
                 s: self.scope,
             };
-            self.with(scope, |_, this| this.visit_assoc_type_binding(b));
+            if let Some(type_def_id) = type_def_id {
+                let lifetimes =
+                    LifetimeContext::supertrait_bounds(self.tcx, type_def_id, binding.ident);
+                if let Some(lifetimes) = lifetimes {
+                    self.with(scope, |_, this| {
+                        let scope = Scope::Supertrait { lifetimes, s: this.scope };
+                        this.with(scope, |_, this| this.visit_assoc_type_binding(binding));
+                    });
+                } else {
+                    self.with(scope, |_, this| this.visit_assoc_type_binding(binding));
+                }
+            } else {
+                self.with(scope, |_, this| this.visit_assoc_type_binding(binding));
+            }
         }
     }
 
+    fn trait_defines_associated_type_named(
+        tcx: TyCtxt<'tcx>,
+        trait_def_id: DefId,
+        assoc_name: Ident,
+    ) -> bool {
+        tcx.associated_items(trait_def_id)
+            .find_by_name_and_kind(tcx, assoc_name, ty::AssocKind::Type, trait_def_id)
+            .is_some()
+    }
+
+    fn supertrait_bounds(
+        tcx: TyCtxt<'tcx>,
+        def_id: DefId,
+        assoc_name: Ident,
+    ) -> Option<Vec<ty::BoundVariableKind>> {
+        let all_candidates = super::supertraits::supertraits(tcx, def_id);
+        let mut matching_candidates = all_candidates
+            .filter(|r| LifetimeContext::trait_defines_associated_type_named(tcx, r.0, assoc_name));
+
+        matching_candidates.next().map(|c| c.1.into_iter().collect())
+    }
+
     #[tracing::instrument(level = "debug", skip(self))]
     fn visit_fn_like_elision(
         &mut self,
@@ -2287,11 +2681,29 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
         output: Option<&'tcx hir::Ty<'tcx>>,
     ) {
         debug!("visit_fn_like_elision: enter");
-        let named_late_bound_vars = match *self.scope {
-            Scope::Binder { named_late_bound_vars, .. } => named_late_bound_vars,
-            Scope::Body { .. } => 0,
-            _ => bug!("{:?}", self.scope),
+        let mut scope = &*self.scope;
+        let (hir_id, named_late_bound_vars) = loop {
+            match scope {
+                Scope::Binder { hir_id, named_late_bound_vars, .. }
+                | Scope::TraitRefHackInner { hir_id, named_late_bound_vars, .. } => {
+                    break (*hir_id, *named_late_bound_vars);
+                }
+                Scope::Body { id, .. } => break (id.hir_id, 0),
+                Scope::ObjectLifetimeDefault { ref s, .. }
+                | Scope::Elision { ref s, .. }
+                | Scope::Supertrait { ref s, .. } => {
+                    scope = *s;
+                }
+                Scope::Root => bug!("In fn_like_elision without appropriate scope above"),
+            }
         };
+        let mut gather = GatherAnonLifetimes { anon_count: 0 };
+        for input in inputs {
+            gather.visit_ty(input);
+        }
+        self.map.late_bound_vars.entry(hir_id).or_default().extend(
+            (0..gather.anon_count).map(|var| ty::BoundVariableKind::Region(ty::BrAnon(var))),
+        );
         let arg_scope = Scope::Elision {
             elide: Elide::FreshLateAnon(named_late_bound_vars, Cell::new(0)),
             s: self.scope,
@@ -2563,6 +2975,41 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                 }
             }
         }
+
+        struct GatherAnonLifetimes {
+            anon_count: u32,
+        }
+        impl<'v> Visitor<'v> for GatherAnonLifetimes {
+            type Map = intravisit::ErasedMap<'v>;
+
+            fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
+                NestedVisitorMap::None
+            }
+
+            fn visit_ty(&mut self, ty: &hir::Ty<'_>) {
+                if let hir::TyKind::BareFn(_) = ty.kind {
+                    return;
+                }
+                intravisit::walk_ty(self, ty);
+            }
+
+            fn visit_generic_args(
+                &mut self,
+                path_span: Span,
+                generic_args: &'v hir::GenericArgs<'v>,
+            ) {
+                if generic_args.parenthesized {
+                    return;
+                }
+                intravisit::walk_generic_args(self, path_span, generic_args)
+            }
+
+            fn visit_lifetime(&mut self, lifetime_ref: &hir::Lifetime) {
+                if lifetime_ref.is_elided() {
+                    self.anon_count += 1;
+                }
+            }
+        }
     }
 
     fn resolve_elided_lifetimes(&mut self, lifetime_refs: &[&'tcx hir::Lifetime]) {
@@ -2574,6 +3021,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 
         let span = lifetime_refs[0].span;
         let mut late_depth = 0;
+        let mut in_poly_trait_ref = false;
         let mut scope = self.scope;
         let mut lifetime_names = FxHashSet::default();
         let mut lifetime_spans = vec![];
@@ -2584,7 +3032,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
 
                 Scope::Root => break None,
 
-                Scope::Binder { s, ref lifetimes, .. } => {
+                Scope::Binder { s, ref lifetimes, from_poly_trait_ref, .. } => {
                     // collect named lifetimes for suggestions
                     for name in lifetimes.keys() {
                         if let hir::ParamName::Plain(name) = name {
@@ -2592,7 +3040,21 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                             lifetime_spans.push(name.span);
                         }
                     }
-                    late_depth += 1;
+                    // See comments in `resolve_lifetime_ref`
+                    match (from_poly_trait_ref, in_poly_trait_ref) {
+                        (true, false) => {
+                            in_poly_trait_ref = true;
+                            late_depth += 1;
+                        }
+                        (true, true) => {}
+                        (false, true) => {
+                            in_poly_trait_ref = false;
+                            late_depth += 1;
+                        }
+                        (false, false) => {
+                            late_depth += 1;
+                        }
+                    }
                     scope = s;
                 }
 
@@ -2602,6 +3064,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                             for lifetime_ref in lifetime_refs {
                                 let lifetime = Region::late_anon(named_late_bound_vars, counter)
                                     .shifted(late_depth);
+
                                 self.insert_lifetime(lifetime_ref, lifetime);
                             }
                             return;
@@ -2638,7 +3101,9 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     return;
                 }
 
-                Scope::ObjectLifetimeDefault { s, .. } => {
+                Scope::ObjectLifetimeDefault { s, .. }
+                | Scope::TraitRefHackInner { s, .. }
+                | Scope::Supertrait { s, .. } => {
                     scope = s;
                 }
             }
@@ -2744,11 +3209,25 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
     fn resolve_object_lifetime_default(&mut self, lifetime_ref: &'tcx hir::Lifetime) {
         debug!("resolve_object_lifetime_default(lifetime_ref={:?})", lifetime_ref);
         let mut late_depth = 0;
+        let mut in_poly_trait_ref = false;
         let mut scope = self.scope;
         let lifetime = loop {
             match *scope {
-                Scope::Binder { s, .. } => {
-                    late_depth += 1;
+                Scope::Binder { s, from_poly_trait_ref, .. } => {
+                    match (from_poly_trait_ref, in_poly_trait_ref) {
+                        (true, false) => {
+                            in_poly_trait_ref = true;
+                            late_depth += 1;
+                        }
+                        (true, true) => {}
+                        (false, true) => {
+                            in_poly_trait_ref = false;
+                            late_depth += 1;
+                        }
+                        (false, false) => {
+                            late_depth += 1;
+                        }
+                    }
                     scope = s;
                 }
 
@@ -2757,6 +3236,10 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                 Scope::Body { .. } | Scope::ObjectLifetimeDefault { lifetime: None, .. } => return,
 
                 Scope::ObjectLifetimeDefault { lifetime: Some(l), .. } => break l,
+
+                Scope::TraitRefHackInner { s, .. } | Scope::Supertrait { s, .. } => {
+                    scope = s;
+                }
             }
         };
         self.insert_lifetime(lifetime_ref, lifetime.shifted(late_depth));
@@ -2880,7 +3363,9 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
             match *old_scope {
                 Scope::Body { s, .. }
                 | Scope::Elision { s, .. }
-                | Scope::ObjectLifetimeDefault { s, .. } => {
+                | Scope::ObjectLifetimeDefault { s, .. }
+                | Scope::TraitRefHackInner { s, .. }
+                | Scope::Supertrait { s, .. } => {
                     old_scope = s;
                 }
 
@@ -2926,7 +3411,7 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                 // A lifetime only used in a fn argument could as well
                 // be replaced with `'_`, as that would generate a
                 // fresh name, too.
-                Scope::Elision { elide: Elide::FreshLateAnon(_, _), .. } => break true,
+                Scope::Elision { elide: Elide::FreshLateAnon(..), .. } => break true,
 
                 // In the return type or other such place, `'_` is not
                 // going to make a fresh name, so we cannot
@@ -2936,7 +3421,9 @@ impl<'a, 'tcx> LifetimeContext<'a, 'tcx> {
                     elide: Elide::Exact(_) | Elide::Error(_) | Elide::Forbid, ..
                 } => break false,
 
-                Scope::ObjectLifetimeDefault { s, .. } => scope = s,
+                Scope::ObjectLifetimeDefault { s, .. }
+                | Scope::TraitRefHackInner { s, .. }
+                | Scope::Supertrait { s, .. } => scope = s,
             }
         }
     }
diff --git a/compiler/rustc_resolve/src/late/supertraits.rs b/compiler/rustc_resolve/src/late/supertraits.rs
new file mode 100644
index 00000000000..2130c33bd77
--- /dev/null
+++ b/compiler/rustc_resolve/src/late/supertraits.rs
@@ -0,0 +1,60 @@
+use smallvec::{smallvec, SmallVec};
+
+use rustc_data_structures::fx::FxHashSet;
+use rustc_hir::def_id::DefId;
+use rustc_middle::ty::{self, TyCtxt};
+
+pub struct Elaborator<'tcx> {
+    tcx: TyCtxt<'tcx>,
+    stack: SmallVec<[(DefId, SmallVec<[ty::BoundVariableKind; 8]>); 8]>,
+    visited: FxHashSet<DefId>,
+}
+
+#[allow(dead_code)]
+pub fn supertraits<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> Elaborator<'tcx> {
+    Elaborator { tcx, stack: smallvec![(def_id, smallvec![])], visited: Default::default() }
+}
+
+impl<'tcx> Elaborator<'tcx> {
+    fn elaborate(&mut self, def_id: DefId, bound_vars: &SmallVec<[ty::BoundVariableKind; 8]>) {
+        let tcx = self.tcx;
+
+        let predicates = tcx.super_predicates_of(def_id);
+        let obligations = predicates.predicates.iter().filter_map(|&(pred, _)| {
+            let bound_predicate = pred.kind();
+            match bound_predicate.skip_binder() {
+                ty::PredicateKind::Trait(data, _) => {
+                    // The order here needs to match what we would get from `subst_supertrait`
+                    let pred_bound_vars = bound_predicate.bound_vars();
+                    let mut all_bound_vars = bound_vars.clone();
+                    all_bound_vars.extend(pred_bound_vars.iter());
+                    let super_def_id = data.trait_ref.def_id;
+                    Some((super_def_id, all_bound_vars))
+                }
+                _ => None,
+            }
+        });
+
+        let visited = &mut self.visited;
+        let obligations = obligations.filter(|o| visited.insert(o.0));
+        self.stack.extend(obligations);
+    }
+}
+
+impl<'tcx> Iterator for Elaborator<'tcx> {
+    type Item = (DefId, SmallVec<[ty::BoundVariableKind; 8]>);
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        (self.stack.len(), None)
+    }
+
+    fn next(&mut self) -> Option<Self::Item> {
+        match self.stack.pop() {
+            Some((def_id, bound_vars)) => {
+                self.elaborate(def_id, &bound_vars);
+                Some((def_id, bound_vars))
+            }
+            None => None,
+        }
+    }
+}
diff --git a/compiler/rustc_symbol_mangling/src/v0.rs b/compiler/rustc_symbol_mangling/src/v0.rs
index 0bb5dd117a0..37a834043f6 100644
--- a/compiler/rustc_symbol_mangling/src/v0.rs
+++ b/compiler/rustc_symbol_mangling/src/v0.rs
@@ -318,7 +318,7 @@ impl Printer<'tcx> for SymbolMangler<'tcx> {
 
             // Late-bound lifetimes use indices starting at 1,
             // see `BinderLevel` for more details.
-            ty::ReLateBound(debruijn, ty::BoundRegion { kind: ty::BrAnon(i) }) => {
+            ty::ReLateBound(debruijn, ty::BoundRegion { kind: ty::BrAnon(i), .. }) => {
                 let binder = &self.binders[self.binders.len() - 1 - debruijn.index()];
                 let depth = binder.lifetime_depths.start + i;
 
diff --git a/compiler/rustc_traits/src/chalk/db.rs b/compiler/rustc_traits/src/chalk/db.rs
index 5c0cb2fb835..8c97e606c56 100644
--- a/compiler/rustc_traits/src/chalk/db.rs
+++ b/compiler/rustc_traits/src/chalk/db.rs
@@ -735,7 +735,10 @@ fn bound_vars_for_item(tcx: TyCtxt<'tcx>, def_id: DefId) -> SubstsRef<'tcx> {
             .into(),
 
         ty::GenericParamDefKind::Lifetime => {
-            let br = ty::BoundRegion { kind: ty::BrAnon(substs.len() as u32) };
+            let br = ty::BoundRegion {
+                var: ty::BoundVar::from_usize(substs.len()),
+                kind: ty::BrAnon(substs.len() as u32),
+            };
             tcx.mk_region(ty::RegionKind::ReLateBound(ty::INNERMOST, br)).into()
         }
 
diff --git a/compiler/rustc_traits/src/chalk/lowering.rs b/compiler/rustc_traits/src/chalk/lowering.rs
index f9de41ee893..39890fd5b05 100644
--- a/compiler/rustc_traits/src/chalk/lowering.rs
+++ b/compiler/rustc_traits/src/chalk/lowering.rs
@@ -434,17 +434,11 @@ impl<'tcx> LowerInto<'tcx, chalk_ir::Lifetime<RustInterner<'tcx>>> for Region<'t
             ReEarlyBound(_) => {
                 panic!("Should have already been substituted.");
             }
-            ReLateBound(db, br) => match br.kind {
-                ty::BoundRegionKind::BrAnon(var) => {
-                    chalk_ir::LifetimeData::BoundVar(chalk_ir::BoundVar::new(
-                        chalk_ir::DebruijnIndex::new(db.as_u32()),
-                        var as usize,
-                    ))
-                    .intern(interner)
-                }
-                ty::BoundRegionKind::BrNamed(_def_id, _name) => unimplemented!(),
-                ty::BrEnv => unimplemented!(),
-            },
+            ReLateBound(db, br) => chalk_ir::LifetimeData::BoundVar(chalk_ir::BoundVar::new(
+                chalk_ir::DebruijnIndex::new(db.as_u32()),
+                br.var.as_usize(),
+            ))
+            .intern(interner),
             ReFree(_) => unimplemented!(),
             ReStatic => chalk_ir::LifetimeData::Static.intern(interner),
             ReVar(_) => unimplemented!(),
@@ -467,7 +461,10 @@ impl<'tcx> LowerInto<'tcx, Region<'tcx>> for &chalk_ir::Lifetime<RustInterner<'t
         let kind = match self.data(interner) {
             chalk_ir::LifetimeData::BoundVar(var) => ty::RegionKind::ReLateBound(
                 ty::DebruijnIndex::from_u32(var.debruijn.depth()),
-                ty::BoundRegion { kind: ty::BrAnon(var.index as u32) },
+                ty::BoundRegion {
+                    var: ty::BoundVar::from_usize(var.index),
+                    kind: ty::BrAnon(var.index as u32),
+                },
             ),
             chalk_ir::LifetimeData::InferenceVar(_var) => unimplemented!(),
             chalk_ir::LifetimeData::Placeholder(p) => {
@@ -900,7 +897,7 @@ impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector<'tcx> {
                     },
                 },
 
-                ty::BrEnv => unimplemented!(),
+                ty::BoundRegionKind::BrEnv => unimplemented!(),
             },
 
             ty::ReEarlyBound(_re) => {
@@ -948,7 +945,7 @@ impl<'a, 'tcx> TypeFolder<'tcx> for NamedBoundVarSubstitutor<'a, 'tcx> {
             ty::ReLateBound(index, br) if *index == self.binder_index => match br.kind {
                 ty::BrNamed(def_id, _name) => match self.named_parameters.get(&def_id) {
                     Some(idx) => {
-                        let new_br = ty::BoundRegion { kind: ty::BrAnon(*idx) };
+                        let new_br = ty::BoundRegion { var: br.var, kind: ty::BrAnon(*idx) };
                         return self.tcx.mk_region(RegionKind::ReLateBound(*index, new_br));
                     }
                     None => panic!("Missing `BrNamed`."),
@@ -1031,12 +1028,16 @@ impl<'tcx> TypeFolder<'tcx> for ParamsSubstitutor<'tcx> {
             // This covers any region variables in a goal, right?
             ty::ReEarlyBound(_re) => match self.named_regions.get(&_re.def_id) {
                 Some(idx) => {
-                    let br = ty::BoundRegion { kind: ty::BrAnon(*idx) };
+                    let br = ty::BoundRegion {
+                        var: ty::BoundVar::from_u32(*idx),
+                        kind: ty::BrAnon(*idx),
+                    };
                     self.tcx.mk_region(RegionKind::ReLateBound(self.binder_index, br))
                 }
                 None => {
                     let idx = self.named_regions.len() as u32;
-                    let br = ty::BoundRegion { kind: ty::BrAnon(idx) };
+                    let br =
+                        ty::BoundRegion { var: ty::BoundVar::from_u32(idx), kind: ty::BrAnon(idx) };
                     self.named_regions.insert(_re.def_id, idx);
                     self.tcx.mk_region(RegionKind::ReLateBound(self.binder_index, br))
                 }
diff --git a/compiler/rustc_typeck/src/astconv/generics.rs b/compiler/rustc_typeck/src/astconv/generics.rs
index 9625211109d..845375f3e32 100644
--- a/compiler/rustc_typeck/src/astconv/generics.rs
+++ b/compiler/rustc_typeck/src/astconv/generics.rs
@@ -166,7 +166,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         parent_substs: &[subst::GenericArg<'tcx>],
         has_self: bool,
         self_ty: Option<Ty<'tcx>>,
-        arg_count: GenericArgCountResult,
+        arg_count: &GenericArgCountResult,
         ctx: &mut impl CreateSubstsForGenericArgsCtxt<'a, 'tcx>,
     ) -> SubstsRef<'tcx> {
         // Collect the segments of the path; we need to substitute arguments
diff --git a/compiler/rustc_typeck/src/astconv/mod.rs b/compiler/rustc_typeck/src/astconv/mod.rs
index 711466e774d..8d55bc8f2f3 100644
--- a/compiler/rustc_typeck/src/astconv/mod.rs
+++ b/compiler/rustc_typeck/src/astconv/mod.rs
@@ -210,14 +210,20 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         let r = match tcx.named_region(lifetime.hir_id) {
             Some(rl::Region::Static) => tcx.lifetimes.re_static,
 
-            Some(rl::Region::LateBound(debruijn, _, id, _)) => {
-                let name = lifetime_name(id.expect_local());
-                let br = ty::BoundRegion { kind: ty::BrNamed(id, name) };
+            Some(rl::Region::LateBound(debruijn, index, def_id, _)) => {
+                let name = lifetime_name(def_id.expect_local());
+                let br = ty::BoundRegion {
+                    var: ty::BoundVar::from_u32(index),
+                    kind: ty::BrNamed(def_id, name),
+                };
                 tcx.mk_region(ty::ReLateBound(debruijn, br))
             }
 
-            Some(rl::Region::LateBoundAnon(debruijn, _index, anon_index)) => {
-                let br = ty::BoundRegion { kind: ty::BrAnon(anon_index) };
+            Some(rl::Region::LateBoundAnon(debruijn, index, anon_index)) => {
+                let br = ty::BoundRegion {
+                    var: ty::BoundVar::from_u32(index),
+                    kind: ty::BrAnon(anon_index),
+                };
                 tcx.mk_region(ty::ReLateBound(debruijn, br))
             }
 
@@ -266,7 +272,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         def_id: DefId,
         item_segment: &hir::PathSegment<'_>,
     ) -> SubstsRef<'tcx> {
-        let (substs, assoc_bindings, _) = self.create_substs_for_ast_path(
+        let (substs, _) = self.create_substs_for_ast_path(
             span,
             def_id,
             &[],
@@ -275,6 +281,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             item_segment.infer_args,
             None,
         );
+        let assoc_bindings = self.create_assoc_bindings_for_generic_args(item_segment.args());
 
         if let Some(b) = assoc_bindings.first() {
             Self::prohibit_assoc_ty_binding(self.tcx(), b.span);
@@ -314,6 +321,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     /// `[Vec<u8>, u8]` and `generic_args` are the arguments for the associated
     /// type itself: `['a]`. The returned `SubstsRef` concatenates these two
     /// lists: `[Vec<u8>, u8, 'a]`.
+    #[tracing::instrument(level = "debug", skip(self, span))]
     fn create_substs_for_ast_path<'a>(
         &self,
         span: Span,
@@ -323,15 +331,10 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         generic_args: &'a hir::GenericArgs<'_>,
         infer_args: bool,
         self_ty: Option<Ty<'tcx>>,
-    ) -> (SubstsRef<'tcx>, Vec<ConvertedBinding<'a, 'tcx>>, GenericArgCountResult) {
+    ) -> (SubstsRef<'tcx>, GenericArgCountResult) {
         // If the type is parameterized by this region, then replace this
         // region with the current anon region binding (in other words,
         // whatever & would get replaced with).
-        debug!(
-            "create_substs_for_ast_path(def_id={:?}, self_ty={:?}, \
-                generic_args={:?})",
-            def_id, self_ty, generic_args
-        );
 
         let tcx = self.tcx();
         let generics = tcx.generics_of(def_id);
@@ -367,7 +370,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         // here and so associated type bindings will be handled regardless of whether there are any
         // non-`Self` generic parameters.
         if generics.params.len() == 0 {
-            return (tcx.intern_substs(&[]), vec![], arg_count);
+            return (tcx.intern_substs(&[]), arg_count);
         }
 
         let is_object = self_ty.map_or(false, |ty| ty == self.tcx().types.trait_object_dummy_self);
@@ -540,7 +543,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             parent_substs,
             self_ty.is_some(),
             self_ty,
-            arg_count.clone(),
+            &arg_count,
             &mut substs_ctx,
         );
 
@@ -551,6 +554,18 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             generic_args.args.is_empty(),
         );
 
+        debug!(
+            "create_substs_for_ast_path(generic_params={:?}, self_ty={:?}) -> {:?}",
+            generics, self_ty, substs
+        );
+
+        (substs, arg_count)
+    }
+
+    fn create_assoc_bindings_for_generic_args<'a>(
+        &self,
+        generic_args: &'a hir::GenericArgs<'_>,
+    ) -> Vec<ConvertedBinding<'a, 'tcx>> {
         // Convert associated-type bindings or constraints into a separate vector.
         // Example: Given this:
         //
@@ -581,12 +596,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             })
             .collect();
 
-        debug!(
-            "create_substs_for_ast_path(generic_params={:?}, self_ty={:?}) -> {:?}",
-            generics, self_ty, substs
-        );
-
-        (substs, assoc_bindings, arg_count)
+        assoc_bindings
     }
 
     crate fn create_substs_for_associated_item(
@@ -636,8 +646,27 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         )
     }
 
-    /// The given trait-ref must actually be a trait.
-    pub(super) fn instantiate_poly_trait_ref_inner(
+    /// Given a trait bound like `Debug`, applies that trait bound the given self-type to construct
+    /// a full trait reference. The resulting trait reference is returned. This may also generate
+    /// auxiliary bounds, which are added to `bounds`.
+    ///
+    /// Example:
+    ///
+    /// ```
+    /// poly_trait_ref = Iterator<Item = u32>
+    /// self_ty = Foo
+    /// ```
+    ///
+    /// this would return `Foo: Iterator` and add `<Foo as Iterator>::Item = u32` into `bounds`.
+    ///
+    /// **A note on binders:** against our usual convention, there is an implied bounder around
+    /// the `self_ty` and `poly_trait_ref` parameters here. So they may reference bound regions.
+    /// If for example you had `for<'a> Foo<'a>: Bar<'a>`, then the `self_ty` would be `Foo<'a>`
+    /// where `'a` is a bound region at depth 0. Similarly, the `poly_trait_ref` would be
+    /// `Bar<'a>`. The returned poly-trait-ref will have this binder instantiated explicitly,
+    /// however.
+    #[tracing::instrument(level = "debug", skip(self, span, constness, bounds, speculative))]
+    pub fn instantiate_poly_trait_ref(
         &self,
         trait_ref: &hir::TraitRef<'_>,
         span: Span,
@@ -648,18 +677,25 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     ) -> GenericArgCountResult {
         let trait_def_id = trait_ref.trait_def_id().unwrap_or_else(|| FatalError.raise());
 
-        debug!("instantiate_poly_trait_ref({:?}, def_id={:?})", trait_ref, trait_def_id);
-
         self.prohibit_generics(trait_ref.path.segments.split_last().unwrap().1);
 
-        let (substs, assoc_bindings, arg_count) = self.create_substs_for_ast_trait_ref(
+        let tcx = self.tcx();
+        let bound_vars = tcx.late_bound_vars(trait_ref.hir_ref_id);
+        debug!(?bound_vars);
+
+        let (substs, arg_count) = self.create_substs_for_ast_trait_ref(
             trait_ref.path.span,
             trait_def_id,
             self_ty,
             trait_ref.path.segments.last().unwrap(),
         );
-        let poly_trait_ref = ty::Binder::bind(ty::TraitRef::new(trait_def_id, substs), self.tcx());
+        let assoc_bindings = self
+            .create_assoc_bindings_for_generic_args(trait_ref.path.segments.last().unwrap().args());
+
+        let poly_trait_ref =
+            ty::Binder::bind_with_vars(ty::TraitRef::new(trait_def_id, substs), bound_vars);
 
+        debug!(?poly_trait_ref, ?assoc_bindings);
         bounds.trait_bounds.push((poly_trait_ref, span, constness));
 
         let mut dup_bindings = FxHashMap::default();
@@ -677,50 +713,9 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             // Okay to ignore `Err` because of `ErrorReported` (see above).
         }
 
-        debug!(
-            "instantiate_poly_trait_ref({:?}, bounds={:?}) -> {:?}",
-            trait_ref, bounds, poly_trait_ref
-        );
-
         arg_count
     }
 
-    /// Given a trait bound like `Debug`, applies that trait bound the given self-type to construct
-    /// a full trait reference. The resulting trait reference is returned. This may also generate
-    /// auxiliary bounds, which are added to `bounds`.
-    ///
-    /// Example:
-    ///
-    /// ```
-    /// poly_trait_ref = Iterator<Item = u32>
-    /// self_ty = Foo
-    /// ```
-    ///
-    /// this would return `Foo: Iterator` and add `<Foo as Iterator>::Item = u32` into `bounds`.
-    ///
-    /// **A note on binders:** against our usual convention, there is an implied bounder around
-    /// the `self_ty` and `poly_trait_ref` parameters here. So they may reference bound regions.
-    /// If for example you had `for<'a> Foo<'a>: Bar<'a>`, then the `self_ty` would be `Foo<'a>`
-    /// where `'a` is a bound region at depth 0. Similarly, the `poly_trait_ref` would be
-    /// `Bar<'a>`. The returned poly-trait-ref will have this binder instantiated explicitly,
-    /// however.
-    pub fn instantiate_poly_trait_ref(
-        &self,
-        poly_trait_ref: &hir::PolyTraitRef<'_>,
-        constness: Constness,
-        self_ty: Ty<'tcx>,
-        bounds: &mut Bounds<'tcx>,
-    ) -> GenericArgCountResult {
-        self.instantiate_poly_trait_ref_inner(
-            &poly_trait_ref.trait_ref,
-            poly_trait_ref.span,
-            constness,
-            self_ty,
-            bounds,
-            false,
-        )
-    }
-
     pub fn instantiate_lang_item_trait_ref(
         &self,
         lang_item: hir::LangItem,
@@ -732,7 +727,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     ) {
         let trait_def_id = self.tcx().require_lang_item(lang_item, Some(span));
 
-        let (substs, assoc_bindings, _) = self.create_substs_for_ast_path(
+        let (substs, _) = self.create_substs_for_ast_path(
             span,
             trait_def_id,
             &[],
@@ -741,7 +736,11 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             false,
             Some(self_ty),
         );
-        let poly_trait_ref = ty::Binder::bind(ty::TraitRef::new(trait_def_id, substs), self.tcx());
+        let assoc_bindings = self.create_assoc_bindings_for_generic_args(args);
+        let tcx = self.tcx();
+        let bound_vars = tcx.late_bound_vars(hir_id);
+        let poly_trait_ref =
+            ty::Binder::bind_with_vars(ty::TraitRef::new(trait_def_id, substs), bound_vars);
         bounds.trait_bounds.push((poly_trait_ref, span, Constness::NotConst));
 
         let mut dup_bindings = FxHashMap::default();
@@ -765,23 +764,23 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         self_ty: Ty<'tcx>,
         trait_segment: &hir::PathSegment<'_>,
     ) -> ty::TraitRef<'tcx> {
-        let (substs, assoc_bindings, _) =
+        let (substs, _) =
             self.create_substs_for_ast_trait_ref(span, trait_def_id, self_ty, trait_segment);
+        let assoc_bindings = self.create_assoc_bindings_for_generic_args(trait_segment.args());
         if let Some(b) = assoc_bindings.first() {
             Self::prohibit_assoc_ty_binding(self.tcx(), b.span);
         }
         ty::TraitRef::new(trait_def_id, substs)
     }
 
+    #[tracing::instrument(level = "debug", skip(self, span))]
     fn create_substs_for_ast_trait_ref<'a>(
         &self,
         span: Span,
         trait_def_id: DefId,
         self_ty: Ty<'tcx>,
         trait_segment: &'a hir::PathSegment<'a>,
-    ) -> (SubstsRef<'tcx>, Vec<ConvertedBinding<'a, 'tcx>>, GenericArgCountResult) {
-        debug!("create_substs_for_ast_trait_ref(trait_segment={:?})", trait_segment);
-
+    ) -> (SubstsRef<'tcx>, GenericArgCountResult) {
         self.complain_about_internal_fn_trait(span, trait_def_id, trait_segment);
 
         self.create_substs_for_ast_path(
@@ -803,7 +802,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     }
 
     // Returns `true` if a bounds list includes `?Sized`.
-    pub fn is_unsized(&self, ast_bounds: &[&hir::GenericBound<'_>], span: Span) -> bool {
+    pub fn is_unsized(&self, ast_bounds: &[hir::GenericBound<'_>], span: Span) -> bool {
         let tcx = self.tcx();
 
         // Try to find an unbound in bounds.
@@ -858,28 +857,44 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     /// **A note on binders:** there is an implied binder around
     /// `param_ty` and `ast_bounds`. See `instantiate_poly_trait_ref`
     /// for more details.
+    #[tracing::instrument(level = "debug", skip(self, bounds))]
     fn add_bounds(
         &self,
         param_ty: Ty<'tcx>,
-        ast_bounds: &[&hir::GenericBound<'_>],
+        ast_bounds: &[hir::GenericBound<'_>],
         bounds: &mut Bounds<'tcx>,
+        bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
     ) {
         let constness = self.default_constness_for_trait_bounds();
         for ast_bound in ast_bounds {
             match *ast_bound {
                 hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::None) => {
-                    self.instantiate_poly_trait_ref(b, constness, param_ty, bounds);
+                    self.instantiate_poly_trait_ref(
+                        &b.trait_ref,
+                        b.span,
+                        constness,
+                        param_ty,
+                        bounds,
+                        false,
+                    );
                 }
                 hir::GenericBound::Trait(ref b, hir::TraitBoundModifier::MaybeConst) => {
-                    self.instantiate_poly_trait_ref(b, Constness::NotConst, param_ty, bounds);
+                    self.instantiate_poly_trait_ref(
+                        &b.trait_ref,
+                        b.span,
+                        Constness::NotConst,
+                        param_ty,
+                        bounds,
+                        false,
+                    );
                 }
                 hir::GenericBound::Trait(_, hir::TraitBoundModifier::Maybe) => {}
                 hir::GenericBound::LangItemTrait(lang_item, span, hir_id, args) => self
                     .instantiate_lang_item_trait_ref(
-                        *lang_item, *span, *hir_id, args, param_ty, bounds,
+                        lang_item, span, hir_id, args, param_ty, bounds,
                     ),
                 hir::GenericBound::Outlives(ref l) => bounds.region_bounds.push((
-                    ty::Binder::bind(self.ast_region_to_region(l, None), self.tcx()),
+                    ty::Binder::bind_with_vars(self.ast_region_to_region(l, None), bound_vars),
                     l.span,
                 )),
             }
@@ -909,7 +924,6 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         sized_by_default: SizedByDefault,
         span: Span,
     ) -> Bounds<'tcx> {
-        let ast_bounds: Vec<_> = ast_bounds.iter().collect();
         self.compute_bounds_inner(param_ty, &ast_bounds, sized_by_default, span)
     }
 
@@ -929,7 +943,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             if let Some(trait_ref) = ast_bound.trait_ref() {
                 if let Some(trait_did) = trait_ref.trait_def_id() {
                     if self.tcx().trait_may_define_assoc_type(trait_did, assoc_name) {
-                        result.push(ast_bound);
+                        result.push(ast_bound.clone());
                     }
                 }
             }
@@ -941,13 +955,13 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     fn compute_bounds_inner(
         &self,
         param_ty: Ty<'tcx>,
-        ast_bounds: &[&hir::GenericBound<'_>],
+        ast_bounds: &[hir::GenericBound<'_>],
         sized_by_default: SizedByDefault,
         span: Span,
     ) -> Bounds<'tcx> {
         let mut bounds = Bounds::default();
 
-        self.add_bounds(param_ty, ast_bounds, &mut bounds);
+        self.add_bounds(param_ty, ast_bounds, &mut bounds, ty::List::empty());
 
         bounds.implicitly_sized = if let SizedByDefault::Yes = sized_by_default {
             if !self.is_unsized(ast_bounds, span) { Some(span) } else { None }
@@ -964,6 +978,10 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
     /// **A note on binders:** given something like `T: for<'a> Iterator<Item = &'a u32>`, the
     /// `trait_ref` here will be `for<'a> T: Iterator`. The `binding` data however is from *inside*
     /// the binder (e.g., `&'a u32`) and hence may reference bound regions.
+    #[tracing::instrument(
+        level = "debug",
+        skip(self, bounds, speculative, dup_bindings, path_span)
+    )]
     fn add_predicates_for_ast_type_binding(
         &self,
         hir_ref_id: hir::HirId,
@@ -990,7 +1008,6 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         //
         // We want to produce `<B as SuperTrait<i32>>::T == foo`.
 
-        debug!(?hir_ref_id, ?trait_ref, ?binding, ?bounds, "add_predicates_for_ast_type_binding",);
         let tcx = self.tcx();
 
         let candidate =
@@ -1140,10 +1157,8 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 //
                 // Calling `skip_binder` is okay, because `add_bounds` expects the `param_ty`
                 // parameter to have a skipped binder.
-                let param_ty =
-                    tcx.mk_projection(assoc_ty.def_id, projection_ty.skip_binder().substs);
-                let ast_bounds: Vec<_> = ast_bounds.iter().collect();
-                self.add_bounds(param_ty, &ast_bounds, bounds);
+                let param_ty = tcx.mk_ty(ty::Projection(projection_ty.skip_binder()));
+                self.add_bounds(param_ty, ast_bounds, bounds, candidate.bound_vars());
             }
         }
         Ok(())
@@ -1177,10 +1192,12 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                     Err(GenericArgCountMismatch { invalid_args: cur_potential_assoc_types, .. }),
                 ..
             } = self.instantiate_poly_trait_ref(
-                trait_bound,
+                &trait_bound.trait_ref,
+                trait_bound.span,
                 Constness::NotConst,
                 dummy_self,
                 &mut bounds,
+                false,
             ) {
                 potential_assoc_types.extend(cur_potential_assoc_types);
             }
@@ -2169,12 +2186,13 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         }
     }
 
-    /// Parses the programmer's textual representation of a type into our
-    /// internal notion of a type.
     pub fn ast_ty_to_ty(&self, ast_ty: &hir::Ty<'_>) -> Ty<'tcx> {
         self.ast_ty_to_ty_inner(ast_ty, false)
     }
 
+    /// Parses the programmer's textual representation of a type into our
+    /// internal notion of a type.
+    ///
     /// Turns a `hir::Ty` into a `Ty`. For diagnostics' purposes we keep track of whether trait
     /// objects are borrowed like `&dyn Trait` to avoid emitting redundant errors.
     #[tracing::instrument(level = "debug", skip(self))]
@@ -2200,6 +2218,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
                 require_c_abi_if_c_variadic(tcx, &bf.decl, bf.abi, ast_ty.span);
 
                 tcx.mk_fn_ptr(self.ty_of_fn(
+                    ast_ty.hir_id,
                     bf.unsafety,
                     bf.abi,
                     &bf.decl,
@@ -2242,7 +2261,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
             }
             hir::TyKind::Path(hir::QPath::LangItem(lang_item, span)) => {
                 let def_id = tcx.require_lang_item(lang_item, Some(span));
-                let (substs, _, _) = self.create_substs_for_ast_path(
+                let (substs, _) = self.create_substs_for_ast_path(
                     span,
                     def_id,
                     &[],
@@ -2279,7 +2298,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         result_ty
     }
 
-    pub fn impl_trait_ty_to_ty(
+    fn impl_trait_ty_to_ty(
         &self,
         def_id: DefId,
         lifetimes: &[hir::GenericArg<'_>],
@@ -2340,6 +2359,7 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
 
     pub fn ty_of_fn(
         &self,
+        hir_id: hir::HirId,
         unsafety: hir::Unsafety,
         abi: abi::Abi,
         decl: &hir::FnDecl<'_>,
@@ -2350,6 +2370,8 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
         debug!("ty_of_fn");
 
         let tcx = self.tcx();
+        let bound_vars = tcx.late_bound_vars(hir_id);
+        debug!(?bound_vars);
 
         // We proactively collect all the inferred type params to emit a single error per fn def.
         let mut visitor = PlaceholderHirTyCollector::default();
@@ -2369,10 +2391,8 @@ impl<'o, 'tcx> dyn AstConv<'tcx> + 'o {
 
         debug!("ty_of_fn: output_ty={:?}", output_ty);
 
-        let bare_fn_ty = ty::Binder::bind(
-            tcx.mk_fn_sig(input_tys, output_ty, decl.c_variadic, unsafety, abi),
-            tcx,
-        );
+        let fn_ty = tcx.mk_fn_sig(input_tys, output_ty, decl.c_variadic, unsafety, abi);
+        let bare_fn_ty = ty::Binder::bind_with_vars(fn_ty, bound_vars);
 
         if !self.allow_ty_infer() {
             // We always collect the spans for placeholder types when evaluating `fn`s, but we
diff --git a/compiler/rustc_typeck/src/check/closure.rs b/compiler/rustc_typeck/src/check/closure.rs
index 2f30621b019..22d3dc6bdc0 100644
--- a/compiler/rustc_typeck/src/check/closure.rs
+++ b/compiler/rustc_typeck/src/check/closure.rs
@@ -69,7 +69,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         let expr_def_id = self.tcx.hir().local_def_id(expr.hir_id);
 
         let ClosureSignatures { bound_sig, liberated_sig } =
-            self.sig_of_closure(expr_def_id.to_def_id(), decl, body, expected_sig);
+            self.sig_of_closure(expr.hir_id, expr_def_id.to_def_id(), decl, body, expected_sig);
 
         debug!("check_closure: ty_of_closure returns {:?}", liberated_sig);
 
@@ -288,15 +288,16 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
 
     fn sig_of_closure(
         &self,
+        hir_id: hir::HirId,
         expr_def_id: DefId,
         decl: &hir::FnDecl<'_>,
         body: &hir::Body<'_>,
         expected_sig: Option<ExpectedSig<'tcx>>,
     ) -> ClosureSignatures<'tcx> {
         if let Some(e) = expected_sig {
-            self.sig_of_closure_with_expectation(expr_def_id, decl, body, e)
+            self.sig_of_closure_with_expectation(hir_id, expr_def_id, decl, body, e)
         } else {
-            self.sig_of_closure_no_expectation(expr_def_id, decl, body)
+            self.sig_of_closure_no_expectation(hir_id, expr_def_id, decl, body)
         }
     }
 
@@ -304,13 +305,14 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     /// types that the user gave into a signature.
     fn sig_of_closure_no_expectation(
         &self,
+        hir_id: hir::HirId,
         expr_def_id: DefId,
         decl: &hir::FnDecl<'_>,
         body: &hir::Body<'_>,
     ) -> ClosureSignatures<'tcx> {
         debug!("sig_of_closure_no_expectation()");
 
-        let bound_sig = self.supplied_sig_of_closure(expr_def_id, decl, body);
+        let bound_sig = self.supplied_sig_of_closure(hir_id, expr_def_id, decl, body);
 
         self.closure_sigs(expr_def_id, body, bound_sig)
     }
@@ -364,6 +366,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     ///   regions with depth 1, which are bound then by the closure.
     fn sig_of_closure_with_expectation(
         &self,
+        hir_id: hir::HirId,
         expr_def_id: DefId,
         decl: &hir::FnDecl<'_>,
         body: &hir::Body<'_>,
@@ -375,7 +378,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         // expectation if things don't see to match up with what we
         // expect.
         if expected_sig.sig.c_variadic() != decl.c_variadic {
-            return self.sig_of_closure_no_expectation(expr_def_id, decl, body);
+            return self.sig_of_closure_no_expectation(hir_id, expr_def_id, decl, body);
         } else if expected_sig.sig.skip_binder().inputs_and_output.len() != decl.inputs.len() + 1 {
             return self.sig_of_closure_with_mismatched_number_of_arguments(
                 expr_def_id,
@@ -411,9 +414,15 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         // Along the way, it also writes out entries for types that the user
         // wrote into our typeck results, which are then later used by the privacy
         // check.
-        match self.check_supplied_sig_against_expectation(expr_def_id, decl, body, &closure_sigs) {
+        match self.check_supplied_sig_against_expectation(
+            hir_id,
+            expr_def_id,
+            decl,
+            body,
+            &closure_sigs,
+        ) {
             Ok(infer_ok) => self.register_infer_ok_obligations(infer_ok),
-            Err(_) => return self.sig_of_closure_no_expectation(expr_def_id, decl, body),
+            Err(_) => return self.sig_of_closure_no_expectation(hir_id, expr_def_id, decl, body),
         }
 
         closure_sigs
@@ -460,6 +469,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     /// strategy.
     fn check_supplied_sig_against_expectation(
         &self,
+        hir_id: hir::HirId,
         expr_def_id: DefId,
         decl: &hir::FnDecl<'_>,
         body: &hir::Body<'_>,
@@ -469,7 +479,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
         //
         // (See comment on `sig_of_closure_with_expectation` for the
         // meaning of these letters.)
-        let supplied_sig = self.supplied_sig_of_closure(expr_def_id, decl, body);
+        let supplied_sig = self.supplied_sig_of_closure(hir_id, expr_def_id, decl, body);
 
         debug!("check_supplied_sig_against_expectation: supplied_sig={:?}", supplied_sig);
 
@@ -534,6 +544,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     /// Also, record this closure signature for later.
     fn supplied_sig_of_closure(
         &self,
+        hir_id: hir::HirId,
         expr_def_id: DefId,
         decl: &hir::FnDecl<'_>,
         body: &hir::Body<'_>,
@@ -545,6 +556,8 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             decl, body.generator_kind,
         );
 
+        let bound_vars = self.tcx.late_bound_vars(hir_id);
+
         // First, convert the types that the user supplied (if any).
         let supplied_arguments = decl.inputs.iter().map(|a| astconv.ast_ty_to_ty(a));
         let supplied_return = match decl.output {
@@ -571,7 +584,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             },
         };
 
-        let result = ty::Binder::bind(
+        let result = ty::Binder::bind_with_vars(
             self.tcx.mk_fn_sig(
                 supplied_arguments,
                 supplied_return,
@@ -579,7 +592,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 hir::Unsafety::Normal,
                 Abi::RustCall,
             ),
-            self.tcx,
+            bound_vars,
         );
 
         debug!("supplied_sig_of_closure: result={:?}", result);
diff --git a/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs b/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs
index a7a412f06be..9ace4550421 100644
--- a/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs
+++ b/compiler/rustc_typeck/src/check/fn_ctxt/_impl.rs
@@ -1462,7 +1462,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                 &[][..],
                 has_self,
                 self_ty,
-                arg_count,
+                &arg_count,
                 &mut CreateCtorSubstsContext {
                     fcx: self,
                     span,
diff --git a/compiler/rustc_typeck/src/check/generator_interior.rs b/compiler/rustc_typeck/src/check/generator_interior.rs
index 969359a3c21..e40aa914858 100644
--- a/compiler/rustc_typeck/src/check/generator_interior.rs
+++ b/compiler/rustc_typeck/src/check/generator_interior.rs
@@ -186,7 +186,10 @@ pub fn resolve_interior<'a, 'tcx>(
                 // which means that none of the regions inside relate to any other, even if
                 // typeck had previously found constraints that would cause them to be related.
                 let folded = fcx.tcx.fold_regions(erased, &mut false, |_, current_depth| {
-                    let br = ty::BoundRegion { kind: ty::BrAnon(counter) };
+                    let br = ty::BoundRegion {
+                        var: ty::BoundVar::from_u32(counter),
+                        kind: ty::BrAnon(counter),
+                    };
                     let r = fcx.tcx.mk_region(ty::ReLateBound(current_depth, br));
                     counter += 1;
                     r
@@ -202,11 +205,15 @@ pub fn resolve_interior<'a, 'tcx>(
 
     // Extract type components to build the witness type.
     let type_list = fcx.tcx.mk_type_list(type_causes.iter().map(|cause| cause.ty));
-    let witness = fcx.tcx.mk_generator_witness(ty::Binder::bind(type_list, fcx.tcx));
+    let bound_vars = fcx.tcx.mk_bound_variable_kinds(
+        (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))),
+    );
+    let witness =
+        fcx.tcx.mk_generator_witness(ty::Binder::bind_with_vars(type_list, bound_vars.clone()));
 
     // Store the generator types and spans into the typeck results for this generator.
     visitor.fcx.inh.typeck_results.borrow_mut().generator_interior_types =
-        ty::Binder::bind(type_causes, fcx.tcx);
+        ty::Binder::bind_with_vars(type_causes, bound_vars);
 
     debug!(
         "types in generator after region replacement {:?}, span = {:?}",
diff --git a/compiler/rustc_typeck/src/check/intrinsic.rs b/compiler/rustc_typeck/src/check/intrinsic.rs
index 3b399b86718..303a77507cf 100644
--- a/compiler/rustc_typeck/src/check/intrinsic.rs
+++ b/compiler/rustc_typeck/src/check/intrinsic.rs
@@ -101,12 +101,21 @@ pub fn check_intrinsic_type(tcx: TyCtxt<'_>, it: &hir::ForeignItem<'_>) {
     let intrinsic_name = tcx.item_name(it.def_id.to_def_id());
     let name_str = intrinsic_name.as_str();
 
+    let bound_vars = tcx.mk_bound_variable_kinds(
+        [ty::BoundVariableKind::Region(ty::BrAnon(0)), ty::BoundVariableKind::Region(ty::BrEnv)]
+            .iter()
+            .copied(),
+    );
     let mk_va_list_ty = |mutbl| {
         tcx.lang_items().va_list().map(|did| {
-            let region = tcx
-                .mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion { kind: ty::BrAnon(0) }));
-            let env_region =
-                tcx.mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion { kind: ty::BrEnv }));
+            let region = tcx.mk_region(ty::ReLateBound(
+                ty::INNERMOST,
+                ty::BoundRegion { var: ty::BoundVar::from_u32(0), kind: ty::BrAnon(0) },
+            ));
+            let env_region = tcx.mk_region(ty::ReLateBound(
+                ty::INNERMOST,
+                ty::BoundRegion { var: ty::BoundVar::from_u32(1), kind: ty::BrEnv },
+            ));
             let va_list_ty = tcx.type_of(did).subst(tcx, &[region.into()]);
             (tcx.mk_ref(env_region, ty::TypeAndMut { ty: va_list_ty, mutbl }), va_list_ty)
         })
@@ -305,7 +314,7 @@ pub fn check_intrinsic_type(tcx: TyCtxt<'_>, it: &hir::ForeignItem<'_>) {
                     tcx.associated_items(tcx.lang_items().discriminant_kind_trait().unwrap());
                 let discriminant_def_id = assoc_items.in_definition_order().next().unwrap().def_id;
 
-                let br = ty::BoundRegion { kind: ty::BrAnon(0) };
+                let br = ty::BoundRegion { var: ty::BoundVar::from_u32(0), kind: ty::BrAnon(0) };
                 (
                     1,
                     vec![
@@ -366,7 +375,7 @@ pub fn check_intrinsic_type(tcx: TyCtxt<'_>, it: &hir::ForeignItem<'_>) {
         (n_tps, inputs, output, unsafety)
     };
     let sig = tcx.mk_fn_sig(inputs.into_iter(), output, false, unsafety, Abi::RustIntrinsic);
-    let sig = ty::Binder::bind(sig, tcx);
+    let sig = ty::Binder::bind_with_vars(sig, bound_vars);
     equate_intrinsic_type(tcx, it, n_tps, sig)
 }
 
diff --git a/compiler/rustc_typeck/src/check/method/confirm.rs b/compiler/rustc_typeck/src/check/method/confirm.rs
index 900bd2885fd..f546a0d8963 100644
--- a/compiler/rustc_typeck/src/check/method/confirm.rs
+++ b/compiler/rustc_typeck/src/check/method/confirm.rs
@@ -381,7 +381,7 @@ impl<'a, 'tcx> ConfirmContext<'a, 'tcx> {
             parent_substs,
             false,
             None,
-            arg_count_correct,
+            &arg_count_correct,
             &mut MethodSubstsCtxt { cfcx: self, pick, seg },
         )
     }
diff --git a/compiler/rustc_typeck/src/check/mod.rs b/compiler/rustc_typeck/src/check/mod.rs
index ad9bb703779..0760d59875c 100644
--- a/compiler/rustc_typeck/src/check/mod.rs
+++ b/compiler/rustc_typeck/src/check/mod.rs
@@ -497,6 +497,7 @@ fn typeck_with_fallback<'tcx>(
                 let fcx = FnCtxt::new(&inh, param_env, body.value.hir_id);
                 <dyn AstConv<'_>>::ty_of_fn(
                     &fcx,
+                    id,
                     header.unsafety,
                     header.abi,
                     decl,
diff --git a/compiler/rustc_typeck/src/collect.rs b/compiler/rustc_typeck/src/collect.rs
index ed4c0f8b828..afe52c97733 100644
--- a/compiler/rustc_typeck/src/collect.rs
+++ b/compiler/rustc_typeck/src/collect.rs
@@ -1712,6 +1712,7 @@ fn fn_sig(tcx: TyCtxt<'_>, def_id: DefId) -> ty::PolyFnSig<'_> {
                 }
                 None => <dyn AstConv<'_>>::ty_of_fn(
                     &icx,
+                    hir_id,
                     sig.header.unsafety,
                     sig.header.abi,
                     &sig.decl,
@@ -1729,6 +1730,7 @@ fn fn_sig(tcx: TyCtxt<'_>, def_id: DefId) -> ty::PolyFnSig<'_> {
             ..
         }) => <dyn AstConv<'_>>::ty_of_fn(
             &icx,
+            hir_id,
             header.unsafety,
             header.abi,
             decl,
@@ -2082,6 +2084,7 @@ fn gather_explicit_predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericP
         match predicate {
             hir::WherePredicate::BoundPredicate(bound_pred) => {
                 let ty = icx.to_ty(&bound_pred.bounded_ty);
+                let bound_vars = icx.tcx.late_bound_vars(bound_pred.bounded_ty.hir_id);
 
                 // Keep the type around in a dummy predicate, in case of no bounds.
                 // That way, `where Ty:` is not a complete noop (see #53696) and `Ty`
@@ -2097,12 +2100,12 @@ fn gather_explicit_predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericP
                     } else {
                         let span = bound_pred.bounded_ty.span;
                         let re_root_empty = tcx.lifetimes.re_root_empty;
-                        let predicate = ty::Binder::bind(
+                        let predicate = ty::Binder::bind_with_vars(
                             ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(
                                 ty,
                                 re_root_empty,
                             )),
-                            tcx,
+                            bound_vars,
                         );
                         predicates.insert((predicate.to_predicate(tcx), span));
                     }
@@ -2120,10 +2123,12 @@ fn gather_explicit_predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericP
                             let mut bounds = Bounds::default();
                             let _ = <dyn AstConv<'_>>::instantiate_poly_trait_ref(
                                 &icx,
-                                &poly_trait_ref,
+                                &poly_trait_ref.trait_ref,
+                                poly_trait_ref.span,
                                 constness,
                                 ty,
                                 &mut bounds,
+                                false,
                             );
                             predicates.extend(bounds.predicates(tcx, ty));
                         }
@@ -2146,11 +2151,11 @@ fn gather_explicit_predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericP
                             let region =
                                 <dyn AstConv<'_>>::ast_region_to_region(&icx, lifetime, None);
                             predicates.insert((
-                                ty::Binder::bind(
+                                ty::Binder::bind_with_vars(
                                     ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(
                                         ty, region,
                                     )),
-                                    tcx,
+                                    bound_vars,
                                 )
                                 .to_predicate(tcx),
                                 lifetime.span,
@@ -2373,7 +2378,14 @@ fn predicates_from_bound<'tcx>(
             };
 
             let mut bounds = Bounds::default();
-            let _ = astconv.instantiate_poly_trait_ref(tr, constness, param_ty, &mut bounds);
+            let _ = astconv.instantiate_poly_trait_ref(
+                &tr.trait_ref,
+                tr.span,
+                constness,
+                param_ty,
+                &mut bounds,
+                false,
+            );
             bounds.predicates(astconv.tcx(), param_ty)
         }
         hir::GenericBound::LangItemTrait(lang_item, span, hir_id, args) => {
@@ -2409,8 +2421,10 @@ fn compute_sig_of_foreign_fn_decl<'tcx>(
     } else {
         hir::Unsafety::Unsafe
     };
+    let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
     let fty = <dyn AstConv<'_>>::ty_of_fn(
         &ItemCtxt::new(tcx, def_id),
+        hir_id,
         unsafety,
         abi,
         decl,
diff --git a/compiler/rustc_typeck/src/lib.rs b/compiler/rustc_typeck/src/lib.rs
index cb442344fa2..4244d37232f 100644
--- a/compiler/rustc_typeck/src/lib.rs
+++ b/compiler/rustc_typeck/src/lib.rs
@@ -430,7 +430,7 @@ pub fn hir_ty_to_ty<'tcx>(tcx: TyCtxt<'tcx>, hir_ty: &hir::Ty<'_>) -> Ty<'tcx> {
     let env_node_id = tcx.hir().get_parent_item(hir_ty.hir_id);
     let env_def_id = tcx.hir().local_def_id(env_node_id);
     let item_cx = self::collect::ItemCtxt::new(tcx, env_def_id.to_def_id());
-    item_cx.to_ty(hir_ty)
+    AstConv::ast_ty_to_ty(&item_cx, hir_ty)
 }
 
 pub fn hir_trait_to_predicates<'tcx>(
@@ -445,7 +445,7 @@ pub fn hir_trait_to_predicates<'tcx>(
     let env_def_id = tcx.hir().local_def_id(env_hir_id);
     let item_cx = self::collect::ItemCtxt::new(tcx, env_def_id.to_def_id());
     let mut bounds = Bounds::default();
-    let _ = <dyn AstConv<'_>>::instantiate_poly_trait_ref_inner(
+    let _ = <dyn AstConv<'_>>::instantiate_poly_trait_ref(
         &item_cx,
         hir_trait,
         DUMMY_SP,
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 58869296d09..217e899001e 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -411,7 +411,7 @@ impl Clean<Option<Lifetime>> for ty::RegionKind {
     fn clean(&self, _cx: &mut DocContext<'_>) -> Option<Lifetime> {
         match *self {
             ty::ReStatic => Some(Lifetime::statik()),
-            ty::ReLateBound(_, ty::BoundRegion { kind: ty::BrNamed(_, name) }) => {
+            ty::ReLateBound(_, ty::BoundRegion { kind: ty::BrNamed(_, name), .. }) => {
                 Some(Lifetime(name))
             }
             ty::ReEarlyBound(ref data) => Some(Lifetime(data.name)),
diff --git a/src/librustdoc/clean/utils.rs b/src/librustdoc/clean/utils.rs
index 32bac53e8f5..60cbe9f376f 100644
--- a/src/librustdoc/clean/utils.rs
+++ b/src/librustdoc/clean/utils.rs
@@ -97,7 +97,7 @@ fn external_generic_args(
         .iter()
         .filter_map(|kind| match kind.unpack() {
             GenericArgKind::Lifetime(lt) => match lt {
-                ty::ReLateBound(_, ty::BoundRegion { kind: ty::BrAnon(_) }) => {
+                ty::ReLateBound(_, ty::BoundRegion { kind: ty::BrAnon(_), .. }) => {
                     Some(GenericArg::Lifetime(Lifetime::elided()))
                 }
                 _ => lt.clean(cx).map(GenericArg::Lifetime),
diff --git a/src/test/incremental/hashes/function_interfaces.rs b/src/test/incremental/hashes/function_interfaces.rs
index ed67b2dcb04..c8530c70f78 100644
--- a/src/test/incremental/hashes/function_interfaces.rs
+++ b/src/test/incremental/hashes/function_interfaces.rs
@@ -118,7 +118,7 @@ pub fn type_parameter<T>() {}
 pub fn lifetime_parameter() {}
 
 #[cfg(not(cfail1))]
-#[rustc_clean(cfg = "cfail2", except = "hir_owner, hir_owner_nodes, generics_of")]
+#[rustc_clean(cfg = "cfail2", except = "hir_owner, hir_owner_nodes, generics_of,fn_sig")]
 #[rustc_clean(cfg = "cfail3")]
 pub fn lifetime_parameter<'a>() {}
 
@@ -150,7 +150,7 @@ pub fn lifetime_bound<'a, T>() {}
 #[cfg(not(cfail1))]
 #[rustc_clean(
     cfg = "cfail2",
-    except = "hir_owner, hir_owner_nodes, generics_of, type_of, predicates_of"
+    except = "hir_owner, hir_owner_nodes, generics_of, type_of, predicates_of,fn_sig"
 )]
 #[rustc_clean(cfg = "cfail3")]
 pub fn lifetime_bound<'a, T: 'a>() {}
@@ -183,7 +183,7 @@ pub fn second_lifetime_bound<'a, 'b, T: 'a>() {}
 #[cfg(not(cfail1))]
 #[rustc_clean(
     cfg = "cfail2",
-    except = "hir_owner, hir_owner_nodes, generics_of, type_of, predicates_of"
+    except = "hir_owner, hir_owner_nodes, generics_of, type_of, predicates_of,fn_sig"
 )]
 #[rustc_clean(cfg = "cfail3")]
 pub fn second_lifetime_bound<'a, 'b, T: 'a + 'b>() {}
diff --git a/src/test/incremental/hashes/inherent_impls.rs b/src/test/incremental/hashes/inherent_impls.rs
index ae8f2ace217..ee7b258cec4 100644
--- a/src/test/incremental/hashes/inherent_impls.rs
+++ b/src/test/incremental/hashes/inherent_impls.rs
@@ -312,7 +312,7 @@ impl Foo {
     // if we lower generics before the body, then the `HirId` for
     // things in the body will be affected. So if you start to see
     // `typeck` appear dirty, that might be the cause. -nmatsakis
-    #[rustc_clean(cfg="cfail2", except="hir_owner,hir_owner_nodes")]
+    #[rustc_clean(cfg="cfail2", except="hir_owner,hir_owner_nodes,fn_sig")]
     #[rustc_clean(cfg="cfail3")]
     pub fn add_lifetime_parameter_to_method<'a>(&self) { }
 }
@@ -360,7 +360,7 @@ impl Foo {
 impl Foo {
     #[rustc_clean(
         cfg="cfail2",
-        except="hir_owner,hir_owner_nodes,generics_of,predicates_of,type_of"
+        except="hir_owner,hir_owner_nodes,generics_of,predicates_of,type_of,fn_sig"
     )]
     #[rustc_clean(cfg="cfail3")]
     pub fn add_lifetime_bound_to_lifetime_param_of_method<'a, 'b: 'a>(&self) { }
@@ -388,7 +388,7 @@ impl Foo {
     // body will be affected. So if you start to see `typeck`
     // appear dirty, that might be the cause. -nmatsakis
     #[rustc_clean(cfg="cfail2", except="hir_owner,hir_owner_nodes,generics_of,predicates_of,\
-                                        type_of")]
+                                        type_of,fn_sig")]
     #[rustc_clean(cfg="cfail3")]
     pub fn add_lifetime_bound_to_type_param_of_method<'a, T: 'a>(&self) { }
 }
diff --git a/src/test/ui/associated-type-bounds/hrtb.rs b/src/test/ui/associated-type-bounds/hrtb.rs
new file mode 100644
index 00000000000..7ab3836493b
--- /dev/null
+++ b/src/test/ui/associated-type-bounds/hrtb.rs
@@ -0,0 +1,65 @@
+// check-pass
+
+#![feature(associated_type_bounds)]
+
+trait A<'a> {}
+trait B<'b> {}
+fn foo<T>()
+where
+    for<'a> T: A<'a> + 'a,
+{
+}
+trait C<'c>: for<'a> A<'a> + for<'b> B<'b> {
+    type As;
+}
+struct D<T>
+where
+    T: for<'c> C<'c, As: A<'c>>,
+{
+    t: std::marker::PhantomData<T>,
+}
+
+trait E<'e> {
+    type As;
+}
+trait F<'f>: for<'a> A<'a> + for<'e> E<'e> {}
+struct G<T>
+where
+    for<'f> T: F<'f, As: E<'f>> + 'f,
+{
+    t: std::marker::PhantomData<T>,
+}
+
+trait I<'a, 'b, 'c> {
+    type As;
+}
+trait H<'d, 'e>: for<'f> I<'d, 'f, 'e> + 'd {}
+fn foo2<T>()
+where
+    T: for<'g> H<'g, 'g, As: for<'h> H<'h, 'g> + 'g>,
+{
+}
+
+fn foo3<T>()
+where
+    T: for<'i> H<'i, 'i, As: for<'j> H<'j, 'i, As: for<'k> I<'i, 'k, 'j> + 'j> + 'i>,
+{
+}
+fn foo4<T>()
+where
+    T: for<'l, 'i> H<'l, 'i, As: for<'j> H<'j, 'i, As: for<'k> I<'l, 'k, 'j> + 'j> + 'i>,
+{
+}
+
+struct X<'x, 'y> {
+    x: std::marker::PhantomData<&'x ()>,
+    y: std::marker::PhantomData<&'y ()>,
+}
+
+fn foo5<T>()
+where
+    T: for<'l, 'i> H<'l, 'i, As: for<'j> H<'j, 'i, As: for<'k> H<'j, 'k, As = X<'j, 'k>> + 'j> + 'i>
+{
+}
+
+fn main() {}
diff --git a/src/test/ui/hrtb/complex.rs b/src/test/ui/hrtb/complex.rs
index 0bcda8c01cd..8cdfe247e02 100644
--- a/src/test/ui/hrtb/complex.rs
+++ b/src/test/ui/hrtb/complex.rs
@@ -9,12 +9,20 @@ trait C<'c>: for<'a> A<'a> + for<'b> B<'b> {
 struct D<T> where T: for<'c> C<'c, As=&'c ()> {
     t: std::marker::PhantomData<T>,
 }
-trait E<'e> {
+trait E<'e, 'g> {
     type As;
 }
-trait F<'f>: for<'a> A<'a> + for<'e> E<'e> {}
+trait F<'f>: for<'a> A<'a> + for<'e> E<'e, 'f> {}
 struct G<T> where T: for<'f> F<'f, As=&'f ()> {
     t: std::marker::PhantomData<T>,
 }
+trait H<'a, 'b> {
+    type As;
+}
+trait I<'a>: for<'b> H<'a, 'b> {}
+
+struct J<T> where T: for<'i> I<'i, As=&'i ()> {
+    t: std::marker::PhantomData<T>,
+}
 
 fn main() {}
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 4e122d930fc..ff16bf0e078 100644
--- a/src/test/ui/nll/closure-requirements/escape-argument-callee.stderr
+++ b/src/test/ui/nll/closure-requirements/escape-argument-callee.stderr
@@ -6,7 +6,7 @@ LL |         let mut closure = expect_sig(|p, y| *p = y);
    |
    = note: defining type: test::{closure#0} with closure substs [
                i16,
-               for<'r, 's, 't0> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) mut &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) i32, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t0) }) i32)),
+               for<'r, 's, 't0> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) mut &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) i32, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 2, kind: BrNamed('t0) }) i32)),
                (),
            ]
 
diff --git a/src/test/ui/nll/closure-requirements/escape-argument.stderr b/src/test/ui/nll/closure-requirements/escape-argument.stderr
index 44d1d2327fc..22398f08572 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: test::{closure#0} with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) mut &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) i32, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) i32)),
+               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) mut &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) i32, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) i32)),
                (),
            ]
 
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 fa9f994c4fa..11420efaa06 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
@@ -10,7 +10,7 @@ LL | |         },
    |
    = note: defining type: supply::{closure#0} with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>, std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) &'_#3r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>)),
+               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>, std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) &'_#3r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#4r
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 0555f79bcb0..98c3c28fb43 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-ref.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-ref.stderr
@@ -11,7 +11,7 @@ LL | |     });
    |
    = note: defining type: supply::{closure#0} with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) &'_#2r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t3) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) u32>)),
+               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 2, kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) &'_#2r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 4, kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 5, kind: BrNamed('t3) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#3r
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 0932f941548..30ef343b261 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
@@ -10,7 +10,7 @@ LL | |     })
    |
    = note: defining type: case1::{closure#0} with closure substs [
                i32,
-               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>)),
+               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>)),
                (),
            ]
 
@@ -49,7 +49,7 @@ LL | |     })
    |
    = note: defining type: case2::{closure#0} with closure substs [
                i32,
-               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>)),
+               for<'r> extern "rust-call" fn((std::cell::Cell<&'_#1r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>)),
                (),
            ]
    = note: number of external vids: 2
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 bf6e2a922ed..29993b129c7 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
@@ -12,7 +12,7 @@ LL | |     });
    |
    = note: defining type: supply::{closure#0} with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t2) }) u32>)),
+               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 2, kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 4, kind: BrNamed('t2) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#2r
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 a3d993848cb..cb505d8b1ec 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
@@ -12,7 +12,7 @@ LL | |     });
    |
    = note: defining type: supply::{closure#0} with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t0) }) std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t3) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) u32>)),
+               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 2, kind: BrNamed('t0) }) std::cell::Cell<&'_#2r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 4, kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 5, kind: BrNamed('t3) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#3r
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 60dca1baa40..2ec9d4d8db1 100644
--- a/src/test/ui/nll/closure-requirements/propagate-approximated-val.stderr
+++ b/src/test/ui/nll/closure-requirements/propagate-approximated-val.stderr
@@ -11,7 +11,7 @@ LL | |     });
    |
    = note: defining type: test::{closure#0} with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>)),
+               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#3r
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 cbb10eb187e..21e4232c788 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
@@ -10,7 +10,7 @@ LL | |         },
    |
    = note: defining type: supply::{closure#0} with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>)),
+               for<'r, 's> extern "rust-call" fn((std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) &'_#2r u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) u32>, std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#3r
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 f9f1d8bb6ff..8b9b0435420 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
@@ -11,7 +11,7 @@ LL | |     });
    |
    = note: defining type: supply::{closure#0} with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) &'_#1r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>)),
+               for<'r, 's, 't0, 't1, 't2> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) &'_#1r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 2, kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 4, kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#2r
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 1587c28e1be..060ce690f03 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
@@ -11,7 +11,7 @@ LL | |     });
    |
    = note: defining type: supply::{closure#0} with closure substs [
                i16,
-               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) &'_#1r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) &'_#2r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t3) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('t1) }) u32>)),
+               for<'r, 's, 't0, 't1, 't2, 't3> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) &'_#1r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 2, kind: BrNamed('t0) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) &'_#2r u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 4, kind: BrNamed('t2) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) u32>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 5, kind: BrNamed('t3) }) std::cell::Cell<&ReLateBound(DebruijnIndex(0), BoundRegion { var: 3, kind: BrNamed('t1) }) u32>)),
                (),
            ]
    = note: late-bound region is '_#3r
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 44f743310b4..5fc1d5c4361 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
@@ -6,7 +6,7 @@ LL |     expect_sig(|a, b| b); // ought to return `a`
    |
    = note: defining type: test::{closure#0} with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) i32, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) i32)) -> &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) i32,
+               for<'r, 's> extern "rust-call" fn((&ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) i32, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) i32)) -> &ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) i32,
                (),
            ]
 
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 dbf76cd1329..baf223b786b 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
@@ -6,7 +6,7 @@ LL |     twice(cell, value, |a, b| invoke(a, b));
    |
    = note: defining type: generic::<T>::{closure#0} with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) ()>>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) T)),
+               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) ()>>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) T)),
                (),
            ]
    = note: number of external vids: 2
@@ -31,7 +31,7 @@ LL |     twice(cell, value, |a, b| invoke(a, b));
    |
    = note: defining type: generic_fail::<T>::{closure#0} with closure substs [
                i16,
-               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('r) }) ()>>, &ReLateBound(DebruijnIndex(0), BoundRegion { kind: BrNamed('s) }) T)),
+               for<'r, 's> extern "rust-call" fn((std::option::Option<std::cell::Cell<&'_#1r &ReLateBound(DebruijnIndex(0), BoundRegion { var: 0, kind: BrNamed('r) }) ()>>, &ReLateBound(DebruijnIndex(0), BoundRegion { var: 1, kind: BrNamed('s) }) T)),
                (),
            ]
    = note: late-bound region is '_#2r