Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

6 files changed, 1437 insertions, 0 deletions

diff --git a/compiler/rustc_infer/src/infer/outlives/components.rs b/compiler/rustc_infer/src/infer/outlives/components.rs
new file mode 100644
index 000000000..b2d7f4a66
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/outlives/components.rs
@@ -0,0 +1,219 @@
+// The outlines relation `T: 'a` or `'a: 'b`. This code frequently
+// refers to rules defined in RFC 1214 (`OutlivesFooBar`), so see that
+// RFC for reference.
+
+use rustc_data_structures::sso::SsoHashSet;
+use rustc_middle::ty::subst::{GenericArg, GenericArgKind};
+use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable};
+use smallvec::{smallvec, SmallVec};
+
+#[derive(Debug)]
+pub enum Component<'tcx> {
+    Region(ty::Region<'tcx>),
+    Param(ty::ParamTy),
+    UnresolvedInferenceVariable(ty::InferTy),
+
+    // Projections like `T::Foo` are tricky because a constraint like
+    // `T::Foo: 'a` can be satisfied in so many ways. There may be a
+    // where-clause that says `T::Foo: 'a`, or the defining trait may
+    // include a bound like `type Foo: 'static`, or -- in the most
+    // conservative way -- we can prove that `T: 'a` (more generally,
+    // that all components in the projection outlive `'a`). This code
+    // is not in a position to judge which is the best technique, so
+    // we just product the projection as a component and leave it to
+    // the consumer to decide (but see `EscapingProjection` below).
+    Projection(ty::ProjectionTy<'tcx>),
+
+    // In the case where a projection has escaping regions -- meaning
+    // regions bound within the type itself -- we always use
+    // the most conservative rule, which requires that all components
+    // outlive the bound. So for example if we had a type like this:
+    //
+    //     for<'a> Trait1<  <T as Trait2<'a,'b>>::Foo  >
+    //                      ~~~~~~~~~~~~~~~~~~~~~~~~~
+    //
+    // then the inner projection (underlined) has an escaping region
+    // `'a`. We consider that outer trait `'c` to meet a bound if `'b`
+    // outlives `'b: 'c`, and we don't consider whether the trait
+    // declares that `Foo: 'static` etc. Therefore, we just return the
+    // free components of such a projection (in this case, `'b`).
+    //
+    // However, in the future, we may want to get smarter, and
+    // actually return a "higher-ranked projection" here. Therefore,
+    // we mark that these components are part of an escaping
+    // projection, so that implied bounds code can avoid relying on
+    // them. This gives us room to improve the regionck reasoning in
+    // the future without breaking backwards compat.
+    EscapingProjection(Vec<Component<'tcx>>),
+}
+
+/// Push onto `out` all the things that must outlive `'a` for the condition
+/// `ty0: 'a` to hold. Note that `ty0` must be a **fully resolved type**.
+pub fn push_outlives_components<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    ty0: Ty<'tcx>,
+    out: &mut SmallVec<[Component<'tcx>; 4]>,
+) {
+    let mut visited = SsoHashSet::new();
+    compute_components(tcx, ty0, out, &mut visited);
+    debug!("components({:?}) = {:?}", ty0, out);
+}
+
+fn compute_components<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    ty: Ty<'tcx>,
+    out: &mut SmallVec<[Component<'tcx>; 4]>,
+    visited: &mut SsoHashSet<GenericArg<'tcx>>,
+) {
+    // Descend through the types, looking for the various "base"
+    // components and collecting them into `out`. This is not written
+    // with `collect()` because of the need to sometimes skip subtrees
+    // in the `subtys` iterator (e.g., when encountering a
+    // projection).
+    match *ty.kind() {
+            ty::FnDef(_, substs) => {
+                // HACK(eddyb) ignore lifetimes found shallowly in `substs`.
+                // This is inconsistent with `ty::Adt` (including all substs)
+                // and with `ty::Closure` (ignoring all substs other than
+                // upvars, of which a `ty::FnDef` doesn't have any), but
+                // consistent with previous (accidental) behavior.
+                // See https://github.com/rust-lang/rust/issues/70917
+                // for further background and discussion.
+                for child in substs {
+                    match child.unpack() {
+                        GenericArgKind::Type(ty) => {
+                            compute_components(tcx, ty, out, visited);
+                        }
+                        GenericArgKind::Lifetime(_) => {}
+                        GenericArgKind::Const(_) => {
+                            compute_components_recursive(tcx, child, out, visited);
+                        }
+                    }
+                }
+            }
+
+            ty::Array(element, _) => {
+                // Don't look into the len const as it doesn't affect regions
+                compute_components(tcx, element, out, visited);
+            }
+
+            ty::Closure(_, ref substs) => {
+                let tupled_ty = substs.as_closure().tupled_upvars_ty();
+                compute_components(tcx, tupled_ty, out, visited);
+            }
+
+            ty::Generator(_, ref substs, _) => {
+                // Same as the closure case
+                let tupled_ty = substs.as_generator().tupled_upvars_ty();
+                compute_components(tcx, tupled_ty, out, visited);
+
+                // We ignore regions in the generator interior as we don't
+                // want these to affect region inference
+            }
+
+            // All regions are bound inside a witness
+            ty::GeneratorWitness(..) => (),
+
+            // OutlivesTypeParameterEnv -- the actual checking that `X:'a`
+            // is implied by the environment is done in regionck.
+            ty::Param(p) => {
+                out.push(Component::Param(p));
+            }
+
+            // For projections, we prefer to generate an obligation like
+            // `<P0 as Trait<P1...Pn>>::Foo: 'a`, because this gives the
+            // regionck more ways to prove that it holds. However,
+            // regionck is not (at least currently) prepared to deal with
+            // higher-ranked regions that may appear in the
+            // trait-ref. Therefore, if we see any higher-ranked regions,
+            // we simply fallback to the most restrictive rule, which
+            // requires that `Pi: 'a` for all `i`.
+            ty::Projection(ref data) => {
+                if !data.has_escaping_bound_vars() {
+                    // best case: no escaping regions, so push the
+                    // projection and skip the subtree (thus generating no
+                    // constraints for Pi). This defers the choice between
+                    // the rules OutlivesProjectionEnv,
+                    // OutlivesProjectionTraitDef, and
+                    // OutlivesProjectionComponents to regionck.
+                    out.push(Component::Projection(*data));
+                } else {
+                    // fallback case: hard code
+                    // OutlivesProjectionComponents.  Continue walking
+                    // through and constrain Pi.
+                    let mut subcomponents = smallvec![];
+                    let mut subvisited = SsoHashSet::new();
+                    compute_components_recursive(tcx, ty.into(), &mut subcomponents, &mut subvisited);
+                    out.push(Component::EscapingProjection(subcomponents.into_iter().collect()));
+                }
+            }
+
+            // We assume that inference variables are fully resolved.
+            // So, if we encounter an inference variable, just record
+            // the unresolved variable as a component.
+            ty::Infer(infer_ty) => {
+                out.push(Component::UnresolvedInferenceVariable(infer_ty));
+            }
+
+            // Most types do not introduce any region binders, nor
+            // involve any other subtle cases, and so the WF relation
+            // simply constraints any regions referenced directly by
+            // the type and then visits the types that are lexically
+            // contained within. (The comments refer to relevant rules
+            // from RFC1214.)
+            ty::Bool |            // OutlivesScalar
+            ty::Char |            // OutlivesScalar
+            ty::Int(..) |         // OutlivesScalar
+            ty::Uint(..) |        // OutlivesScalar
+            ty::Float(..) |       // OutlivesScalar
+            ty::Never |           // ...
+            ty::Adt(..) |         // OutlivesNominalType
+            ty::Opaque(..) |      // OutlivesNominalType (ish)
+            ty::Foreign(..) |     // OutlivesNominalType
+            ty::Str |             // OutlivesScalar (ish)
+            ty::Slice(..) |       // ...
+            ty::RawPtr(..) |      // ...
+            ty::Ref(..) |         // OutlivesReference
+            ty::Tuple(..) |       // ...
+            ty::FnPtr(_) |        // OutlivesFunction (*)
+            ty::Dynamic(..) |     // OutlivesObject, OutlivesFragment (*)
+            ty::Placeholder(..) |
+            ty::Bound(..) |
+            ty::Error(_) => {
+                // (*) Function pointers and trait objects are both binders.
+                // In the RFC, this means we would add the bound regions to
+                // the "bound regions list".  In our representation, no such
+                // list is maintained explicitly, because bound regions
+                // themselves can be readily identified.
+                compute_components_recursive(tcx, ty.into(), out, visited);
+            }
+        }
+}
+
+/// Collect [Component]s for *all* the substs of `parent`.
+///
+/// This should not be used to get the components of `parent` itself.
+/// Use [push_outlives_components] instead.
+pub(super) fn compute_components_recursive<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    parent: GenericArg<'tcx>,
+    out: &mut SmallVec<[Component<'tcx>; 4]>,
+    visited: &mut SsoHashSet<GenericArg<'tcx>>,
+) {
+    for child in parent.walk_shallow(visited) {
+        match child.unpack() {
+            GenericArgKind::Type(ty) => {
+                compute_components(tcx, ty, out, visited);
+            }
+            GenericArgKind::Lifetime(lt) => {
+                // Ignore late-bound regions.
+                if !lt.is_late_bound() {
+                    out.push(Component::Region(lt));
+                }
+            }
+            GenericArgKind::Const(_) => {
+                compute_components_recursive(tcx, child, out, visited);
+            }
+        }
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/outlives/env.rs b/compiler/rustc_infer/src/infer/outlives/env.rs
new file mode 100644
index 000000000..b2decd64f
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/outlives/env.rs
@@ -0,0 +1,131 @@
+use crate::infer::free_regions::FreeRegionMap;
+use crate::infer::{GenericKind, InferCtxt};
+use crate::traits::query::OutlivesBound;
+use rustc_data_structures::fx::FxIndexSet;
+use rustc_middle::ty::{self, ReEarlyBound, ReFree, ReVar, Region};
+
+use super::explicit_outlives_bounds;
+
+/// The `OutlivesEnvironment` collects information about what outlives
+/// what in a given type-checking setting. For example, if we have a
+/// where-clause like `where T: 'a` in scope, then the
+/// `OutlivesEnvironment` would record that (in its
+/// `region_bound_pairs` field). Similarly, it contains methods for
+/// processing and adding implied bounds into the outlives
+/// environment.
+///
+/// Other code at present does not typically take a
+/// `&OutlivesEnvironment`, but rather takes some of its fields (e.g.,
+/// `process_registered_region_obligations` wants the
+/// region-bound-pairs). There is no mistaking it: the current setup
+/// of tracking region information is quite scattered! The
+/// `OutlivesEnvironment`, for example, needs to sometimes be combined
+/// with the `middle::RegionRelations`, to yield a full picture of how
+/// (lexical) lifetimes interact. However, I'm reluctant to do more
+/// refactoring here, since the setup with NLL is quite different.
+/// For example, NLL has no need of `RegionRelations`, and is solely
+/// interested in the `OutlivesEnvironment`. -nmatsakis
+#[derive(Clone)]
+pub struct OutlivesEnvironment<'tcx> {
+    pub param_env: ty::ParamEnv<'tcx>,
+    free_region_map: FreeRegionMap<'tcx>,
+
+    // Contains the implied region bounds in scope for our current body.
+    //
+    // Example:
+    //
+    // ```
+    // fn foo<'a, 'b, T>(x: &'a T, y: &'b ()) {
+    //   bar(x, y, |y: &'b T| { .. } // body B1)
+    // } // body B0
+    // ```
+    //
+    // Here, when checking the body B0, the list would be `[T: 'a]`, because we
+    // infer that `T` must outlive `'a` from the implied bounds on the
+    // fn declaration.
+    //
+    // For the body B1 however, the list would be `[T: 'a, T: 'b]`, because we
+    // also can see that -- within the closure body! -- `T` must
+    // outlive `'b`. This is not necessarily true outside the closure
+    // body, since the closure may never be called.
+    region_bound_pairs: RegionBoundPairs<'tcx>,
+}
+
+/// "Region-bound pairs" tracks outlives relations that are known to
+/// be true, either because of explicit where-clauses like `T: 'a` or
+/// because of implied bounds.
+pub type RegionBoundPairs<'tcx> =
+    FxIndexSet<ty::OutlivesPredicate<GenericKind<'tcx>, Region<'tcx>>>;
+
+impl<'a, 'tcx> OutlivesEnvironment<'tcx> {
+    pub fn new(param_env: ty::ParamEnv<'tcx>) -> Self {
+        let mut env = OutlivesEnvironment {
+            param_env,
+            free_region_map: Default::default(),
+            region_bound_pairs: Default::default(),
+        };
+
+        env.add_outlives_bounds(None, explicit_outlives_bounds(param_env));
+
+        env
+    }
+
+    /// Borrows current value of the `free_region_map`.
+    pub fn free_region_map(&self) -> &FreeRegionMap<'tcx> {
+        &self.free_region_map
+    }
+
+    /// Borrows current `region_bound_pairs`.
+    pub fn region_bound_pairs(&self) -> &RegionBoundPairs<'tcx> {
+        &self.region_bound_pairs
+    }
+
+    /// Processes outlives bounds that are known to hold, whether from implied or other sources.
+    ///
+    /// The `infcx` parameter is optional; if the implied bounds may
+    /// contain inference variables, it must be supplied, in which
+    /// case we will register "givens" on the inference context. (See
+    /// `RegionConstraintData`.)
+    pub fn add_outlives_bounds<I>(
+        &mut self,
+        infcx: Option<&InferCtxt<'a, 'tcx>>,
+        outlives_bounds: I,
+    ) where
+        I: IntoIterator<Item = OutlivesBound<'tcx>>,
+    {
+        // Record relationships such as `T:'x` that don't go into the
+        // free-region-map but which we use here.
+        for outlives_bound in outlives_bounds {
+            debug!("add_outlives_bounds: outlives_bound={:?}", outlives_bound);
+            match outlives_bound {
+                OutlivesBound::RegionSubParam(r_a, param_b) => {
+                    self.region_bound_pairs
+                        .insert(ty::OutlivesPredicate(GenericKind::Param(param_b), r_a));
+                }
+                OutlivesBound::RegionSubProjection(r_a, projection_b) => {
+                    self.region_bound_pairs
+                        .insert(ty::OutlivesPredicate(GenericKind::Projection(projection_b), r_a));
+                }
+                OutlivesBound::RegionSubRegion(r_a, r_b) => {
+                    if let (ReEarlyBound(_) | ReFree(_), ReVar(vid_b)) = (r_a.kind(), r_b.kind()) {
+                        infcx
+                            .expect("no infcx provided but region vars found")
+                            .add_given(r_a, vid_b);
+                    } else {
+                        // In principle, we could record (and take
+                        // advantage of) every relationship here, but
+                        // we are also free not to -- it simply means
+                        // strictly less that we can successfully type
+                        // check. Right now we only look for things
+                        // relationships between free regions. (It may
+                        // also be that we should revise our inference
+                        // system to be more general and to make use
+                        // of *every* relationship that arises here,
+                        // but presently we do not.)
+                        self.free_region_map.relate_regions(r_a, r_b);
+                    }
+                }
+            }
+        }
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/outlives/mod.rs b/compiler/rustc_infer/src/infer/outlives/mod.rs
new file mode 100644
index 000000000..2a085288f
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/outlives/mod.rs
@@ -0,0 +1,37 @@
+//! Various code related to computing outlives relations.
+
+pub mod components;
+pub mod env;
+pub mod obligations;
+pub mod test_type_match;
+pub mod verify;
+
+use rustc_middle::traits::query::OutlivesBound;
+use rustc_middle::ty;
+
+#[instrument(level = "debug", skip(param_env))]
+pub fn explicit_outlives_bounds<'tcx>(
+    param_env: ty::ParamEnv<'tcx>,
+) -> impl Iterator<Item = OutlivesBound<'tcx>> + 'tcx {
+    param_env
+        .caller_bounds()
+        .into_iter()
+        .map(ty::Predicate::kind)
+        .filter_map(ty::Binder::no_bound_vars)
+        .filter_map(move |kind| match kind {
+            ty::PredicateKind::Projection(..)
+            | ty::PredicateKind::Trait(..)
+            | ty::PredicateKind::Coerce(..)
+            | ty::PredicateKind::Subtype(..)
+            | ty::PredicateKind::WellFormed(..)
+            | ty::PredicateKind::ObjectSafe(..)
+            | ty::PredicateKind::ClosureKind(..)
+            | ty::PredicateKind::TypeOutlives(..)
+            | ty::PredicateKind::ConstEvaluatable(..)
+            | ty::PredicateKind::ConstEquate(..)
+            | ty::PredicateKind::TypeWellFormedFromEnv(..) => None,
+            ty::PredicateKind::RegionOutlives(ty::OutlivesPredicate(r_a, r_b)) => {
+                Some(OutlivesBound::RegionSubRegion(r_b, r_a))
+            }
+        })
+}
diff --git a/compiler/rustc_infer/src/infer/outlives/obligations.rs b/compiler/rustc_infer/src/infer/outlives/obligations.rs
new file mode 100644
index 000000000..ad052f58c
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/outlives/obligations.rs
@@ -0,0 +1,470 @@
+//! Code that handles "type-outlives" constraints like `T: 'a`. This
+//! is based on the `push_outlives_components` function defined in rustc_infer,
+//! but it adds a bit of heuristics on top, in particular to deal with
+//! associated types and projections.
+//!
+//! When we process a given `T: 'a` obligation, we may produce two
+//! kinds of constraints for the region inferencer:
+//!
+//! - Relationships between inference variables and other regions.
+//!   For example, if we have `&'?0 u32: 'a`, then we would produce
+//!   a constraint that `'a <= '?0`.
+//! - "Verifys" that must be checked after inferencing is done.
+//!   For example, if we know that, for some type parameter `T`,
+//!   `T: 'a + 'b`, and we have a requirement that `T: '?1`,
+//!   then we add a "verify" that checks that `'?1 <= 'a || '?1 <= 'b`.
+//!   - Note the difference with the previous case: here, the region
+//!     variable must be less than something else, so this doesn't
+//!     affect how inference works (it finds the smallest region that
+//!     will do); it's just a post-condition that we have to check.
+//!
+//! **The key point is that once this function is done, we have
+//! reduced all of our "type-region outlives" obligations into relationships
+//! between individual regions.**
+//!
+//! One key input to this function is the set of "region-bound pairs".
+//! These are basically the relationships between type parameters and
+//! regions that are in scope at the point where the outlives
+//! obligation was incurred. **When type-checking a function,
+//! particularly in the face of closures, this is not known until
+//! regionck runs!** This is because some of those bounds come
+//! from things we have yet to infer.
+//!
+//! Consider:
+//!
+//! ```
+//! fn bar<T>(a: T, b: impl for<'a> Fn(&'a T)) {}
+//! fn foo<T>(x: T) {
+//!     bar(x, |y| { /* ... */})
+//!          // ^ closure arg
+//! }
+//! ```
+//!
+//! Here, the type of `y` may involve inference variables and the
+//! like, and it may also contain implied bounds that are needed to
+//! type-check the closure body (e.g., here it informs us that `T`
+//! outlives the late-bound region `'a`).
+//!
+//! Note that by delaying the gathering of implied bounds until all
+//! inference information is known, we may find relationships between
+//! bound regions and other regions in the environment. For example,
+//! when we first check a closure like the one expected as argument
+//! to `foo`:
+//!
+//! ```
+//! fn foo<U, F: for<'a> FnMut(&'a U)>(_f: F) {}
+//! ```
+//!
+//! the type of the closure's first argument would be `&'a ?U`. We
+//! might later infer `?U` to something like `&'b u32`, which would
+//! imply that `'b: 'a`.
+
+use crate::infer::outlives::components::{push_outlives_components, Component};
+use crate::infer::outlives::env::OutlivesEnvironment;
+use crate::infer::outlives::env::RegionBoundPairs;
+use crate::infer::outlives::verify::VerifyBoundCx;
+use crate::infer::{
+    self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, UndoLog, VerifyBound,
+};
+use crate::traits::{ObligationCause, ObligationCauseCode};
+use rustc_data_structures::undo_log::UndoLogs;
+use rustc_hir::def_id::LocalDefId;
+use rustc_middle::ty::subst::GenericArgKind;
+use rustc_middle::ty::{self, Region, Ty, TyCtxt, TypeVisitable};
+use smallvec::smallvec;
+
+impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
+    /// Registers that the given region obligation must be resolved
+    /// from within the scope of `body_id`. These regions are enqueued
+    /// and later processed by regionck, when full type information is
+    /// available (see `region_obligations` field for more
+    /// information).
+    #[instrument(level = "debug", skip(self))]
+    pub fn register_region_obligation(&self, obligation: RegionObligation<'tcx>) {
+        let mut inner = self.inner.borrow_mut();
+        inner.undo_log.push(UndoLog::PushRegionObligation);
+        inner.region_obligations.push(obligation);
+    }
+
+    pub fn register_region_obligation_with_cause(
+        &self,
+        sup_type: Ty<'tcx>,
+        sub_region: Region<'tcx>,
+        cause: &ObligationCause<'tcx>,
+    ) {
+        let origin = SubregionOrigin::from_obligation_cause(cause, || {
+            infer::RelateParamBound(
+                cause.span,
+                sup_type,
+                match cause.code().peel_derives() {
+                    ObligationCauseCode::BindingObligation(_, span) => Some(*span),
+                    _ => None,
+                },
+            )
+        });
+
+        self.register_region_obligation(RegionObligation { sup_type, sub_region, origin });
+    }
+
+    /// Trait queries just want to pass back type obligations "as is"
+    pub fn take_registered_region_obligations(&self) -> Vec<RegionObligation<'tcx>> {
+        std::mem::take(&mut self.inner.borrow_mut().region_obligations)
+    }
+
+    /// NOTE: Prefer using [`InferCtxt::check_region_obligations_and_report_errors`]
+    /// instead of calling this directly.
+    ///
+    /// Process the region obligations that must be proven (during
+    /// `regionck`) for the given `body_id`, given information about
+    /// the region bounds in scope and so forth. This function must be
+    /// invoked for all relevant body-ids before region inference is
+    /// done (or else an assert will fire).
+    ///
+    /// See the `region_obligations` field of `InferCtxt` for some
+    /// comments about how this function fits into the overall expected
+    /// flow of the inferencer. The key point is that it is
+    /// invoked after all type-inference variables have been bound --
+    /// towards the end of regionck. This also ensures that the
+    /// region-bound-pairs are available (see comments above regarding
+    /// closures).
+    ///
+    /// # Parameters
+    ///
+    /// - `region_bound_pairs_map`: the set of region bounds implied by
+    ///   the parameters and where-clauses. In particular, each pair
+    ///   `('a, K)` in this list tells us that the bounds in scope
+    ///   indicate that `K: 'a`, where `K` is either a generic
+    ///   parameter like `T` or a projection like `T::Item`.
+    /// - `param_env` is the parameter environment for the enclosing function.
+    /// - `body_id` is the body-id whose region obligations are being
+    ///   processed.
+    #[instrument(level = "debug", skip(self, region_bound_pairs))]
+    pub fn process_registered_region_obligations(
+        &self,
+        region_bound_pairs: &RegionBoundPairs<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+    ) {
+        assert!(
+            !self.in_snapshot.get(),
+            "cannot process registered region obligations in a snapshot"
+        );
+
+        let my_region_obligations = self.take_registered_region_obligations();
+
+        for RegionObligation { sup_type, sub_region, origin } in my_region_obligations {
+            debug!(
+                "process_registered_region_obligations: sup_type={:?} sub_region={:?} origin={:?}",
+                sup_type, sub_region, origin
+            );
+
+            let sup_type = self.resolve_vars_if_possible(sup_type);
+
+            let outlives =
+                &mut TypeOutlives::new(self, self.tcx, &region_bound_pairs, None, param_env);
+            outlives.type_must_outlive(origin, sup_type, sub_region);
+        }
+    }
+
+    /// Processes registered region obliations and resolves regions, reporting
+    /// any errors if any were raised. Prefer using this function over manually
+    /// calling `resolve_regions_and_report_errors`.
+    pub fn check_region_obligations_and_report_errors(
+        &self,
+        generic_param_scope: LocalDefId,
+        outlives_env: &OutlivesEnvironment<'tcx>,
+    ) {
+        self.process_registered_region_obligations(
+            outlives_env.region_bound_pairs(),
+            outlives_env.param_env,
+        );
+
+        self.resolve_regions_and_report_errors(generic_param_scope, outlives_env)
+    }
+}
+
+/// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
+/// obligation into a series of `'a: 'b` constraints and "verify"s, as
+/// described on the module comment. The final constraints are emitted
+/// via a "delegate" of type `D` -- this is usually the `infcx`, which
+/// accrues them into the `region_obligations` code, but for NLL we
+/// use something else.
+pub struct TypeOutlives<'cx, 'tcx, D>
+where
+    D: TypeOutlivesDelegate<'tcx>,
+{
+    // See the comments on `process_registered_region_obligations` for the meaning
+    // of these fields.
+    delegate: D,
+    tcx: TyCtxt<'tcx>,
+    verify_bound: VerifyBoundCx<'cx, 'tcx>,
+}
+
+pub trait TypeOutlivesDelegate<'tcx> {
+    fn push_sub_region_constraint(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        a: ty::Region<'tcx>,
+        b: ty::Region<'tcx>,
+    );
+
+    fn push_verify(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        kind: GenericKind<'tcx>,
+        a: ty::Region<'tcx>,
+        bound: VerifyBound<'tcx>,
+    );
+}
+
+impl<'cx, 'tcx, D> TypeOutlives<'cx, 'tcx, D>
+where
+    D: TypeOutlivesDelegate<'tcx>,
+{
+    pub fn new(
+        delegate: D,
+        tcx: TyCtxt<'tcx>,
+        region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
+        implicit_region_bound: Option<ty::Region<'tcx>>,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> Self {
+        Self {
+            delegate,
+            tcx,
+            verify_bound: VerifyBoundCx::new(
+                tcx,
+                region_bound_pairs,
+                implicit_region_bound,
+                param_env,
+            ),
+        }
+    }
+
+    /// Adds constraints to inference such that `T: 'a` holds (or
+    /// reports an error if it cannot).
+    ///
+    /// # Parameters
+    ///
+    /// - `origin`, the reason we need this constraint
+    /// - `ty`, the type `T`
+    /// - `region`, the region `'a`
+    pub fn type_must_outlive(
+        &mut self,
+        origin: infer::SubregionOrigin<'tcx>,
+        ty: Ty<'tcx>,
+        region: ty::Region<'tcx>,
+    ) {
+        debug!("type_must_outlive(ty={:?}, region={:?}, origin={:?})", ty, region, origin);
+
+        assert!(!ty.has_escaping_bound_vars());
+
+        let mut components = smallvec![];
+        push_outlives_components(self.tcx, ty, &mut components);
+        self.components_must_outlive(origin, &components, region);
+    }
+
+    fn components_must_outlive(
+        &mut self,
+        origin: infer::SubregionOrigin<'tcx>,
+        components: &[Component<'tcx>],
+        region: ty::Region<'tcx>,
+    ) {
+        for component in components.iter() {
+            let origin = origin.clone();
+            match component {
+                Component::Region(region1) => {
+                    self.delegate.push_sub_region_constraint(origin, region, *region1);
+                }
+                Component::Param(param_ty) => {
+                    self.param_ty_must_outlive(origin, region, *param_ty);
+                }
+                Component::Projection(projection_ty) => {
+                    self.projection_must_outlive(origin, region, *projection_ty);
+                }
+                Component::EscapingProjection(subcomponents) => {
+                    self.components_must_outlive(origin, &subcomponents, region);
+                }
+                Component::UnresolvedInferenceVariable(v) => {
+                    // ignore this, we presume it will yield an error
+                    // later, since if a type variable is not resolved by
+                    // this point it never will be
+                    self.tcx.sess.delay_span_bug(
+                        origin.span(),
+                        &format!("unresolved inference variable in outlives: {:?}", v),
+                    );
+                }
+            }
+        }
+    }
+
+    fn param_ty_must_outlive(
+        &mut self,
+        origin: infer::SubregionOrigin<'tcx>,
+        region: ty::Region<'tcx>,
+        param_ty: ty::ParamTy,
+    ) {
+        debug!(
+            "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})",
+            region, param_ty, origin
+        );
+
+        let generic = GenericKind::Param(param_ty);
+        let verify_bound = self.verify_bound.generic_bound(generic);
+        self.delegate.push_verify(origin, generic, region, verify_bound);
+    }
+
+    #[tracing::instrument(level = "debug", skip(self))]
+    fn projection_must_outlive(
+        &mut self,
+        origin: infer::SubregionOrigin<'tcx>,
+        region: ty::Region<'tcx>,
+        projection_ty: ty::ProjectionTy<'tcx>,
+    ) {
+        // This case is thorny for inference. The fundamental problem is
+        // that there are many cases where we have choice, and inference
+        // doesn't like choice (the current region inference in
+        // particular). :) First off, we have to choose between using the
+        // OutlivesProjectionEnv, OutlivesProjectionTraitDef, and
+        // OutlivesProjectionComponent rules, any one of which is
+        // sufficient.  If there are no inference variables involved, it's
+        // not hard to pick the right rule, but if there are, we're in a
+        // bit of a catch 22: if we picked which rule we were going to
+        // use, we could add constraints to the region inference graph
+        // that make it apply, but if we don't add those constraints, the
+        // rule might not apply (but another rule might). For now, we err
+        // on the side of adding too few edges into the graph.
+
+        // Compute the bounds we can derive from the trait definition.
+        // These are guaranteed to apply, no matter the inference
+        // results.
+        let trait_bounds: Vec<_> =
+            self.verify_bound.projection_declared_bounds_from_trait(projection_ty).collect();
+
+        debug!(?trait_bounds);
+
+        // Compute the bounds we can derive from the environment. This
+        // is an "approximate" match -- in some cases, these bounds
+        // may not apply.
+        let mut approx_env_bounds =
+            self.verify_bound.projection_approx_declared_bounds_from_env(projection_ty);
+        debug!("projection_must_outlive: approx_env_bounds={:?}", approx_env_bounds);
+
+        // Remove outlives bounds that we get from the environment but
+        // which are also deducible from the trait. This arises (cc
+        // #55756) in cases where you have e.g., `<T as Foo<'a>>::Item:
+        // 'a` in the environment but `trait Foo<'b> { type Item: 'b
+        // }` in the trait definition.
+        approx_env_bounds.retain(|bound_outlives| {
+            // OK to skip binder because we only manipulate and compare against other
+            // values from the same binder. e.g. if we have (e.g.) `for<'a> <T as Trait<'a>>::Item: 'a`
+            // in `bound`, the `'a` will be a `^1` (bound, debruijn index == innermost) region.
+            // If the declaration is `trait Trait<'b> { type Item: 'b; }`, then `projection_declared_bounds_from_trait`
+            // will be invoked with `['b => ^1]` and so we will get `^1` returned.
+            let bound = bound_outlives.skip_binder();
+            match *bound.0.kind() {
+                ty::Projection(projection_ty) => self
+                    .verify_bound
+                    .projection_declared_bounds_from_trait(projection_ty)
+                    .all(|r| r != bound.1),
+
+                _ => panic!("expected only projection types from env, not {:?}", bound.0),
+            }
+        });
+
+        // If declared bounds list is empty, the only applicable rule is
+        // OutlivesProjectionComponent. If there are inference variables,
+        // then, we can break down the outlives into more primitive
+        // components without adding unnecessary edges.
+        //
+        // If there are *no* inference variables, however, we COULD do
+        // this, but we choose not to, because the error messages are less
+        // good. For example, a requirement like `T::Item: 'r` would be
+        // translated to a requirement that `T: 'r`; when this is reported
+        // to the user, it will thus say "T: 'r must hold so that T::Item:
+        // 'r holds". But that makes it sound like the only way to fix
+        // the problem is to add `T: 'r`, which isn't true. So, if there are no
+        // inference variables, we use a verify constraint instead of adding
+        // edges, which winds up enforcing the same condition.
+        let needs_infer = projection_ty.needs_infer();
+        if approx_env_bounds.is_empty() && trait_bounds.is_empty() && needs_infer {
+            debug!("projection_must_outlive: no declared bounds");
+
+            for k in projection_ty.substs {
+                match k.unpack() {
+                    GenericArgKind::Lifetime(lt) => {
+                        self.delegate.push_sub_region_constraint(origin.clone(), region, lt);
+                    }
+                    GenericArgKind::Type(ty) => {
+                        self.type_must_outlive(origin.clone(), ty, region);
+                    }
+                    GenericArgKind::Const(_) => {
+                        // Const parameters don't impose constraints.
+                    }
+                }
+            }
+
+            return;
+        }
+
+        // If we found a unique bound `'b` from the trait, and we
+        // found nothing else from the environment, then the best
+        // action is to require that `'b: 'r`, so do that.
+        //
+        // This is best no matter what rule we use:
+        //
+        // - OutlivesProjectionEnv: these would translate to the requirement that `'b:'r`
+        // - OutlivesProjectionTraitDef: these would translate to the requirement that `'b:'r`
+        // - OutlivesProjectionComponent: this would require `'b:'r`
+        //   in addition to other conditions
+        if !trait_bounds.is_empty()
+            && trait_bounds[1..]
+                .iter()
+                .map(|r| Some(*r))
+                .chain(
+                    // NB: The environment may contain `for<'a> T: 'a` style bounds.
+                    // In that case, we don't know if they are equal to the trait bound
+                    // or not (since we don't *know* whether the environment bound even applies),
+                    // so just map to `None` here if there are bound vars, ensuring that
+                    // the call to `all` will fail below.
+                    approx_env_bounds.iter().map(|b| b.map_bound(|b| b.1).no_bound_vars()),
+                )
+                .all(|b| b == Some(trait_bounds[0]))
+        {
+            let unique_bound = trait_bounds[0];
+            debug!("projection_must_outlive: unique trait bound = {:?}", unique_bound);
+            debug!("projection_must_outlive: unique declared bound appears in trait ref");
+            self.delegate.push_sub_region_constraint(origin, region, unique_bound);
+            return;
+        }
+
+        // Fallback to verifying after the fact that there exists a
+        // declared bound, or that all the components appearing in the
+        // projection outlive; in some cases, this may add insufficient
+        // edges into the inference graph, leading to inference failures
+        // even though a satisfactory solution exists.
+        let generic = GenericKind::Projection(projection_ty);
+        let verify_bound = self.verify_bound.generic_bound(generic);
+        debug!("projection_must_outlive: pushing {:?}", verify_bound);
+        self.delegate.push_verify(origin, generic, region, verify_bound);
+    }
+}
+
+impl<'cx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'tcx> {
+    fn push_sub_region_constraint(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        a: ty::Region<'tcx>,
+        b: ty::Region<'tcx>,
+    ) {
+        self.sub_regions(origin, a, b)
+    }
+
+    fn push_verify(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        kind: GenericKind<'tcx>,
+        a: ty::Region<'tcx>,
+        bound: VerifyBound<'tcx>,
+    ) {
+        self.verify_generic_bound(origin, kind, a, bound)
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/outlives/test_type_match.rs b/compiler/rustc_infer/src/infer/outlives/test_type_match.rs
new file mode 100644
index 000000000..772e297b7
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/outlives/test_type_match.rs
@@ -0,0 +1,207 @@
+use std::collections::hash_map::Entry;
+
+use rustc_data_structures::fx::FxHashMap;
+use rustc_middle::ty::TypeVisitable;
+use rustc_middle::ty::{
+    self,
+    error::TypeError,
+    relate::{self, Relate, RelateResult, TypeRelation},
+    Ty, TyCtxt,
+};
+
+use crate::infer::region_constraints::VerifyIfEq;
+
+/// Given a "verify-if-eq" type test like:
+///
+///     exists<'a...> {
+///         verify_if_eq(some_type, bound_region)
+///     }
+///
+/// and the type `test_ty` that the type test is being tested against,
+/// returns:
+///
+/// * `None` if `some_type` cannot be made equal to `test_ty`,
+///   no matter the values of the variables in `exists`.
+/// * `Some(r)` with a suitable bound (typically the value of `bound_region`, modulo
+///   any bound existential variables, which will be substituted) for the
+///   type under test.
+///
+/// NB: This function uses a simplistic, syntactic version of type equality.
+/// In other words, it may spuriously return `None` even if the type-under-test
+/// is in fact equal to `some_type`. In practice, though, this is used on types
+/// that are either projections like `T::Item` or `T` and it works fine, but it
+/// could have trouble when complex types with higher-ranked binders and the
+/// like are used. This is a particular challenge since this function is invoked
+/// very late in inference and hence cannot make use of the normal inference
+/// machinery.
+#[tracing::instrument(level = "debug", skip(tcx, param_env))]
+pub fn extract_verify_if_eq<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    verify_if_eq_b: &ty::Binder<'tcx, VerifyIfEq<'tcx>>,
+    test_ty: Ty<'tcx>,
+) -> Option<ty::Region<'tcx>> {
+    assert!(!verify_if_eq_b.has_escaping_bound_vars());
+    let mut m = Match::new(tcx, param_env);
+    let verify_if_eq = verify_if_eq_b.skip_binder();
+    m.relate(verify_if_eq.ty, test_ty).ok()?;
+
+    if let ty::RegionKind::ReLateBound(depth, br) = verify_if_eq.bound.kind() {
+        assert!(depth == ty::INNERMOST);
+        match m.map.get(&br) {
+            Some(&r) => Some(r),
+            None => {
+                // If there is no mapping, then this region is unconstrained.
+                // In that case, we escalate to `'static`.
+                Some(tcx.lifetimes.re_static)
+            }
+        }
+    } else {
+        // The region does not contain any bound variables, so we don't need
+        // to do any substitution.
+        //
+        // Example:
+        //
+        // for<'a> <T as Foo<'a>>::Item: 'b
+        //
+        // In this case, we've now matched and found a value for
+        // `'a`, but it doesn't affect the bound `'b`.
+        Some(verify_if_eq.bound)
+    }
+}
+
+/// True if a (potentially higher-ranked) outlives
+#[tracing::instrument(level = "debug", skip(tcx, param_env))]
+pub(super) fn can_match_erased_ty<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    outlives_predicate: ty::Binder<'tcx, ty::TypeOutlivesPredicate<'tcx>>,
+    erased_ty: Ty<'tcx>,
+) -> bool {
+    assert!(!outlives_predicate.has_escaping_bound_vars());
+    let erased_outlives_predicate = tcx.erase_regions(outlives_predicate);
+    let outlives_ty = erased_outlives_predicate.skip_binder().0;
+    if outlives_ty == erased_ty {
+        // pointless micro-optimization
+        true
+    } else {
+        Match::new(tcx, param_env).relate(outlives_ty, erased_ty).is_ok()
+    }
+}
+
+struct Match<'tcx> {
+    tcx: TyCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    pattern_depth: ty::DebruijnIndex,
+    map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>,
+}
+
+impl<'tcx> Match<'tcx> {
+    fn new(tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Match<'tcx> {
+        Match { tcx, param_env, pattern_depth: ty::INNERMOST, map: FxHashMap::default() }
+    }
+}
+
+impl<'tcx> Match<'tcx> {
+    /// Creates the "Error" variant that signals "no match".
+    fn no_match<T>(&self) -> RelateResult<'tcx, T> {
+        Err(TypeError::Mismatch)
+    }
+
+    /// Binds the pattern variable `br` to `value`; returns an `Err` if the pattern
+    /// is already bound to a different value.
+    #[tracing::instrument(level = "debug", skip(self))]
+    fn bind(
+        &mut self,
+        br: ty::BoundRegion,
+        value: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        match self.map.entry(br) {
+            Entry::Occupied(entry) => {
+                if *entry.get() == value {
+                    Ok(value)
+                } else {
+                    self.no_match()
+                }
+            }
+            Entry::Vacant(entry) => {
+                entry.insert(value);
+                Ok(value)
+            }
+        }
+    }
+}
+
+impl<'tcx> TypeRelation<'tcx> for Match<'tcx> {
+    fn tag(&self) -> &'static str {
+        "Match"
+    }
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.tcx
+    }
+    fn param_env(&self) -> ty::ParamEnv<'tcx> {
+        self.param_env
+    }
+    fn a_is_expected(&self) -> bool {
+        true
+    } // irrelevant
+
+    fn relate_with_variance<T: Relate<'tcx>>(
+        &mut self,
+        _: ty::Variance,
+        _: ty::VarianceDiagInfo<'tcx>,
+        a: T,
+        b: T,
+    ) -> RelateResult<'tcx, T> {
+        self.relate(a, b)
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn regions(
+        &mut self,
+        pattern: ty::Region<'tcx>,
+        value: ty::Region<'tcx>,
+    ) -> RelateResult<'tcx, ty::Region<'tcx>> {
+        debug!("self.pattern_depth = {:?}", self.pattern_depth);
+        if let ty::RegionKind::ReLateBound(depth, br) = pattern.kind() && depth == self.pattern_depth {
+            self.bind(br, value)
+        } else if pattern == value {
+            Ok(pattern)
+        } else {
+            self.no_match()
+        }
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn tys(&mut self, pattern: Ty<'tcx>, value: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
+        if pattern == value { Ok(pattern) } else { relate::super_relate_tys(self, pattern, value) }
+    }
+
+    #[instrument(skip(self), level = "debug")]
+    fn consts(
+        &mut self,
+        pattern: ty::Const<'tcx>,
+        value: ty::Const<'tcx>,
+    ) -> RelateResult<'tcx, ty::Const<'tcx>> {
+        debug!("{}.consts({:?}, {:?})", self.tag(), pattern, value);
+        if pattern == value {
+            Ok(pattern)
+        } else {
+            relate::super_relate_consts(self, pattern, value)
+        }
+    }
+
+    fn binders<T>(
+        &mut self,
+        pattern: ty::Binder<'tcx, T>,
+        value: ty::Binder<'tcx, T>,
+    ) -> RelateResult<'tcx, ty::Binder<'tcx, T>>
+    where
+        T: Relate<'tcx>,
+    {
+        self.pattern_depth.shift_in(1);
+        let result = Ok(pattern.rebind(self.relate(pattern.skip_binder(), value.skip_binder())?));
+        self.pattern_depth.shift_out(1);
+        result
+    }
+}
diff --git a/compiler/rustc_infer/src/infer/outlives/verify.rs b/compiler/rustc_infer/src/infer/outlives/verify.rs
new file mode 100644
index 000000000..c7d7ef40d
--- /dev/null
+++ b/compiler/rustc_infer/src/infer/outlives/verify.rs
@@ -0,0 +1,373 @@
+use crate::infer::outlives::components::{compute_components_recursive, Component};
+use crate::infer::outlives::env::RegionBoundPairs;
+use crate::infer::region_constraints::VerifyIfEq;
+use crate::infer::{GenericKind, VerifyBound};
+use rustc_data_structures::captures::Captures;
+use rustc_data_structures::sso::SsoHashSet;
+use rustc_hir::def_id::DefId;
+use rustc_middle::ty::subst::{GenericArg, Subst};
+use rustc_middle::ty::{self, EarlyBinder, OutlivesPredicate, Ty, TyCtxt};
+
+use smallvec::smallvec;
+
+/// The `TypeOutlives` struct has the job of "lowering" a `T: 'a`
+/// obligation into a series of `'a: 'b` constraints and "verifys", as
+/// described on the module comment. The final constraints are emitted
+/// via a "delegate" of type `D` -- this is usually the `infcx`, which
+/// accrues them into the `region_obligations` code, but for NLL we
+/// use something else.
+pub struct VerifyBoundCx<'cx, 'tcx> {
+    tcx: TyCtxt<'tcx>,
+    region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
+    /// During borrowck, if there are no outlives bounds on a generic
+    /// parameter `T`, we assume that `T: 'in_fn_body` holds.
+    ///
+    /// Outside of borrowck the only way to prove `T: '?0` is by
+    /// setting  `'?0` to `'empty`.
+    implicit_region_bound: Option<ty::Region<'tcx>>,
+    param_env: ty::ParamEnv<'tcx>,
+}
+
+impl<'cx, 'tcx> VerifyBoundCx<'cx, 'tcx> {
+    pub fn new(
+        tcx: TyCtxt<'tcx>,
+        region_bound_pairs: &'cx RegionBoundPairs<'tcx>,
+        implicit_region_bound: Option<ty::Region<'tcx>>,
+        param_env: ty::ParamEnv<'tcx>,
+    ) -> Self {
+        Self { tcx, region_bound_pairs, implicit_region_bound, param_env }
+    }
+
+    /// Returns a "verify bound" that encodes what we know about
+    /// `generic` and the regions it outlives.
+    pub fn generic_bound(&self, generic: GenericKind<'tcx>) -> VerifyBound<'tcx> {
+        let mut visited = SsoHashSet::new();
+        match generic {
+            GenericKind::Param(param_ty) => self.param_bound(param_ty),
+            GenericKind::Projection(projection_ty) => {
+                self.projection_bound(projection_ty, &mut visited)
+            }
+        }
+    }
+
+    fn param_bound(&self, param_ty: ty::ParamTy) -> VerifyBound<'tcx> {
+        debug!("param_bound(param_ty={:?})", param_ty);
+
+        // Start with anything like `T: 'a` we can scrape from the
+        // environment. If the environment contains something like
+        // `for<'a> T: 'a`, then we know that `T` outlives everything.
+        let declared_bounds_from_env = self.declared_generic_bounds_from_env(param_ty);
+        let mut param_bounds = vec![];
+        for declared_bound in declared_bounds_from_env {
+            let bound_region = declared_bound.map_bound(|outlives| outlives.1);
+            if let Some(region) = bound_region.no_bound_vars() {
+                // This is `T: 'a` for some free region `'a`.
+                param_bounds.push(VerifyBound::OutlivedBy(region));
+            } else {
+                // This is `for<'a> T: 'a`. This means that `T` outlives everything! All done here.
+                return VerifyBound::AllBounds(vec![]);
+            }
+        }
+
+        // Add in the default bound of fn body that applies to all in
+        // scope type parameters:
+        if let Some(r) = self.implicit_region_bound {
+            param_bounds.push(VerifyBound::OutlivedBy(r));
+        }
+
+        if param_bounds.is_empty() {
+            // We know that all types `T` outlive `'empty`, so if we
+            // can find no other bound, then check that the region
+            // being tested is `'empty`.
+            VerifyBound::IsEmpty
+        } else if param_bounds.len() == 1 {
+            // Micro-opt: no need to store the vector if it's just len 1
+            param_bounds.pop().unwrap()
+        } else {
+            // If we can find any other bound `R` such that `T: R`, then
+            // we don't need to check for `'empty`, because `R: 'empty`.
+            VerifyBound::AnyBound(param_bounds)
+        }
+    }
+
+    /// Given a projection like `T::Item`, searches the environment
+    /// for where-clauses like `T::Item: 'a`. Returns the set of
+    /// regions `'a` that it finds.
+    ///
+    /// This is an "approximate" check -- it may not find all
+    /// applicable bounds, and not all the bounds it returns can be
+    /// relied upon. In particular, this check ignores region
+    /// identity. So, for example, if we have `<T as
+    /// Trait<'0>>::Item` where `'0` is a region variable, and the
+    /// user has `<T as Trait<'a>>::Item: 'b` in the environment, then
+    /// the clause from the environment only applies if `'0 = 'a`,
+    /// which we don't know yet. But we would still include `'b` in
+    /// this list.
+    pub fn projection_approx_declared_bounds_from_env(
+        &self,
+        projection_ty: ty::ProjectionTy<'tcx>,
+    ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> {
+        let projection_ty = GenericKind::Projection(projection_ty).to_ty(self.tcx);
+        let erased_projection_ty = self.tcx.erase_regions(projection_ty);
+        self.declared_generic_bounds_from_env_for_erased_ty(erased_projection_ty)
+    }
+
+    /// Searches the where-clauses in scope for regions that
+    /// `projection_ty` is known to outlive. Currently requires an
+    /// exact match.
+    pub fn projection_declared_bounds_from_trait(
+        &self,
+        projection_ty: ty::ProjectionTy<'tcx>,
+    ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
+        self.declared_projection_bounds_from_trait(projection_ty)
+    }
+
+    pub fn projection_bound(
+        &self,
+        projection_ty: ty::ProjectionTy<'tcx>,
+        visited: &mut SsoHashSet<GenericArg<'tcx>>,
+    ) -> VerifyBound<'tcx> {
+        debug!("projection_bound(projection_ty={:?})", projection_ty);
+
+        let projection_ty_as_ty =
+            self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs);
+
+        // Search the env for where clauses like `P: 'a`.
+        let env_bounds = self
+            .projection_approx_declared_bounds_from_env(projection_ty)
+            .into_iter()
+            .map(|binder| {
+                if let Some(ty::OutlivesPredicate(ty, r)) = binder.no_bound_vars() && ty == projection_ty_as_ty {
+                    // Micro-optimize if this is an exact match (this
+                    // occurs often when there are no region variables
+                    // involved).
+                    VerifyBound::OutlivedBy(r)
+                } else {
+                    let verify_if_eq_b = binder.map_bound(|ty::OutlivesPredicate(ty, bound)| VerifyIfEq { ty, bound });
+                    VerifyBound::IfEq(verify_if_eq_b)
+                }
+            });
+
+        // Extend with bounds that we can find from the trait.
+        let trait_bounds = self
+            .projection_declared_bounds_from_trait(projection_ty)
+            .map(|r| VerifyBound::OutlivedBy(r));
+
+        // see the extensive comment in projection_must_outlive
+        let recursive_bound = {
+            let mut components = smallvec![];
+            let ty = self.tcx.mk_projection(projection_ty.item_def_id, projection_ty.substs);
+            compute_components_recursive(self.tcx, ty.into(), &mut components, visited);
+            self.bound_from_components(&components, visited)
+        };
+
+        VerifyBound::AnyBound(env_bounds.chain(trait_bounds).collect()).or(recursive_bound)
+    }
+
+    fn bound_from_components(
+        &self,
+        components: &[Component<'tcx>],
+        visited: &mut SsoHashSet<GenericArg<'tcx>>,
+    ) -> VerifyBound<'tcx> {
+        let mut bounds = components
+            .iter()
+            .map(|component| self.bound_from_single_component(component, visited))
+            .filter(|bound| {
+                // Remove bounds that must hold, since they are not interesting.
+                !bound.must_hold()
+            });
+
+        match (bounds.next(), bounds.next()) {
+            (Some(first), None) => first,
+            (first, second) => {
+                VerifyBound::AllBounds(first.into_iter().chain(second).chain(bounds).collect())
+            }
+        }
+    }
+
+    fn bound_from_single_component(
+        &self,
+        component: &Component<'tcx>,
+        visited: &mut SsoHashSet<GenericArg<'tcx>>,
+    ) -> VerifyBound<'tcx> {
+        match *component {
+            Component::Region(lt) => VerifyBound::OutlivedBy(lt),
+            Component::Param(param_ty) => self.param_bound(param_ty),
+            Component::Projection(projection_ty) => self.projection_bound(projection_ty, visited),
+            Component::EscapingProjection(ref components) => {
+                self.bound_from_components(components, visited)
+            }
+            Component::UnresolvedInferenceVariable(v) => {
+                // ignore this, we presume it will yield an error
+                // later, since if a type variable is not resolved by
+                // this point it never will be
+                self.tcx.sess.delay_span_bug(
+                    rustc_span::DUMMY_SP,
+                    &format!("unresolved inference variable in outlives: {:?}", v),
+                );
+                // add a bound that never holds
+                VerifyBound::AnyBound(vec![])
+            }
+        }
+    }
+
+    /// Searches the environment for where-clauses like `G: 'a` where
+    /// `G` is either some type parameter `T` or a projection like
+    /// `T::Item`. Returns a vector of the `'a` bounds it can find.
+    ///
+    /// This is a conservative check -- it may not find all applicable
+    /// bounds, but all the bounds it returns can be relied upon.
+    fn declared_generic_bounds_from_env(
+        &self,
+        param_ty: ty::ParamTy,
+    ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> {
+        let generic_ty = param_ty.to_ty(self.tcx);
+        self.declared_generic_bounds_from_env_for_erased_ty(generic_ty)
+    }
+
+    /// Searches the environment to find all bounds that apply to `erased_ty`.
+    /// Obviously these must be approximate -- they are in fact both *over* and
+    /// and *under* approximated:
+    ///
+    /// * Over-approximated because we erase regions, so
+    /// * Under-approximated because we look for syntactic equality and so for complex types
+    ///   like `<T as Foo<fn(&u32, &u32)>>::Item` or whatever we may fail to figure out
+    ///   all the subtleties.
+    ///
+    /// In some cases, such as when `erased_ty` represents a `ty::Param`, however,
+    /// the result is precise.
+    fn declared_generic_bounds_from_env_for_erased_ty(
+        &self,
+        erased_ty: Ty<'tcx>,
+    ) -> Vec<ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>> {
+        let tcx = self.tcx;
+
+        // To start, collect bounds from user environment. Note that
+        // parameter environments are already elaborated, so we don't
+        // have to worry about that.
+        let c_b = self.param_env.caller_bounds();
+        let param_bounds = self.collect_outlives_from_predicate_list(erased_ty, c_b.into_iter());
+
+        // Next, collect regions we scraped from the well-formedness
+        // constraints in the fn signature. To do that, we walk the list
+        // of known relations from the fn ctxt.
+        //
+        // This is crucial because otherwise code like this fails:
+        //
+        //     fn foo<'a, A>(x: &'a A) { x.bar() }
+        //
+        // The problem is that the type of `x` is `&'a A`. To be
+        // well-formed, then, A must outlive `'a`, but we don't know that
+        // this holds from first principles.
+        let from_region_bound_pairs =
+            self.region_bound_pairs.iter().filter_map(|&OutlivesPredicate(p, r)| {
+                debug!(
+                    "declared_generic_bounds_from_env_for_erased_ty: region_bound_pair = {:?}",
+                    (r, p)
+                );
+                let p_ty = p.to_ty(tcx);
+                let erased_p_ty = self.tcx.erase_regions(p_ty);
+                (erased_p_ty == erased_ty)
+                    .then_some(ty::Binder::dummy(ty::OutlivesPredicate(p.to_ty(tcx), r)))
+            });
+
+        param_bounds
+            .chain(from_region_bound_pairs)
+            .inspect(|bound| {
+                debug!(
+                    "declared_generic_bounds_from_env_for_erased_ty: result predicate = {:?}",
+                    bound
+                )
+            })
+            .collect()
+    }
+
+    /// Given a projection like `<T as Foo<'x>>::Bar`, returns any bounds
+    /// declared in the trait definition. For example, if the trait were
+    ///
+    /// ```rust
+    /// trait Foo<'a> {
+    ///     type Bar: 'a;
+    /// }
+    /// ```
+    ///
+    /// then this function would return `'x`. This is subject to the
+    /// limitations around higher-ranked bounds described in
+    /// `region_bounds_declared_on_associated_item`.
+    fn declared_projection_bounds_from_trait(
+        &self,
+        projection_ty: ty::ProjectionTy<'tcx>,
+    ) -> impl Iterator<Item = ty::Region<'tcx>> + 'cx + Captures<'tcx> {
+        debug!("projection_bounds(projection_ty={:?})", projection_ty);
+        let tcx = self.tcx;
+        self.region_bounds_declared_on_associated_item(projection_ty.item_def_id)
+            .map(move |r| EarlyBinder(r).subst(tcx, projection_ty.substs))
+    }
+
+    /// Given the `DefId` of an associated item, returns any region
+    /// bounds attached to that associated item from the trait definition.
+    ///
+    /// For example:
+    ///
+    /// ```rust
+    /// trait Foo<'a> {
+    ///     type Bar: 'a;
+    /// }
+    /// ```
+    ///
+    /// If we were given the `DefId` of `Foo::Bar`, we would return
+    /// `'a`. You could then apply the substitutions from the
+    /// projection to convert this into your namespace. This also
+    /// works if the user writes `where <Self as Foo<'a>>::Bar: 'a` on
+    /// the trait. In fact, it works by searching for just such a
+    /// where-clause.
+    ///
+    /// It will not, however, work for higher-ranked bounds like:
+    ///
+    /// ```compile_fail,E0311
+    /// trait Foo<'a, 'b>
+    /// where for<'x> <Self as Foo<'x, 'b>>::Bar: 'x
+    /// {
+    ///     type Bar;
+    /// }
+    /// ```
+    ///
+    /// This is for simplicity, and because we are not really smart
+    /// enough to cope with such bounds anywhere.
+    fn region_bounds_declared_on_associated_item(
+        &self,
+        assoc_item_def_id: DefId,
+    ) -> impl Iterator<Item = ty::Region<'tcx>> {
+        let tcx = self.tcx;
+        let bounds = tcx.item_bounds(assoc_item_def_id);
+        bounds
+            .into_iter()
+            .filter_map(|p| p.to_opt_type_outlives())
+            .filter_map(|p| p.no_bound_vars())
+            .map(|b| b.1)
+    }
+
+    /// Searches through a predicate list for a predicate `T: 'a`.
+    ///
+    /// Careful: does not elaborate predicates, and just uses `==`
+    /// when comparing `ty` for equality, so `ty` must be something
+    /// that does not involve inference variables and where you
+    /// otherwise want a precise match.
+    fn collect_outlives_from_predicate_list(
+        &self,
+        erased_ty: Ty<'tcx>,
+        predicates: impl Iterator<Item = ty::Predicate<'tcx>>,
+    ) -> impl Iterator<Item = ty::Binder<'tcx, ty::OutlivesPredicate<Ty<'tcx>, ty::Region<'tcx>>>>
+    {
+        let tcx = self.tcx;
+        let param_env = self.param_env;
+        predicates.filter_map(|p| p.to_opt_type_outlives()).filter(move |outlives_predicate| {
+            super::test_type_match::can_match_erased_ty(
+                tcx,
+                param_env,
+                *outlives_predicate,
+                erased_ty,
+            )
+        })
+    }
+}