Uplift complex type ops back into typeck so we can call them locally

4 files changed, 558 insertions, 17 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs b/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs
index 455b53bfb7d..4e4172e7f41 100644
--- a/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs
@@ -1,6 +1,11 @@
-use rustc_middle::ty::{self, Ty, TyCtxt};
+use crate::traits::query::normalize::QueryNormalizeExt;
+use crate::traits::query::NoSolution;
+use crate::traits::{Normalized, ObligationCause, ObligationCtxt};
 
-pub use rustc_middle::traits::query::{DropckConstraint, DropckOutlivesResult};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_middle::traits::query::{DropckConstraint, DropckOutlivesResult};
+use rustc_middle::ty::{self, EarlyBinder, ParamEnvAnd, Ty, TyCtxt};
+use rustc_span::source_map::{Span, DUMMY_SP};
 
 /// This returns true if the type `ty` is "trivial" for
 /// dropck-outlives -- that is, if it doesn't require any types to
@@ -71,3 +76,263 @@ pub fn trivial_dropck_outlives<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool {
         | ty::Generator(..) => false,
     }
 }
+
+pub fn compute_dropck_outlives_inner<'tcx>(
+    ocx: &ObligationCtxt<'_, 'tcx>,
+    goal: ParamEnvAnd<'tcx, Ty<'tcx>>,
+) -> Result<DropckOutlivesResult<'tcx>, NoSolution> {
+    let tcx = ocx.infcx.tcx;
+    let ParamEnvAnd { param_env, value: for_ty } = goal;
+
+    let mut result = DropckOutlivesResult { kinds: vec![], overflows: vec![] };
+
+    // A stack of types left to process. Each round, we pop
+    // something from the stack and invoke
+    // `dtorck_constraint_for_ty_inner`. This may produce new types that
+    // have to be pushed on the stack. This continues until we have explored
+    // all the reachable types from the type `for_ty`.
+    //
+    // Example: Imagine that we have the following code:
+    //
+    // ```rust
+    // struct A {
+    //     value: B,
+    //     children: Vec<A>,
+    // }
+    //
+    // struct B {
+    //     value: u32
+    // }
+    //
+    // fn f() {
+    //   let a: A = ...;
+    //   ..
+    // } // here, `a` is dropped
+    // ```
+    //
+    // at the point where `a` is dropped, we need to figure out
+    // which types inside of `a` contain region data that may be
+    // accessed by any destructors in `a`. We begin by pushing `A`
+    // onto the stack, as that is the type of `a`. We will then
+    // invoke `dtorck_constraint_for_ty_inner` which will expand `A`
+    // into the types of its fields `(B, Vec<A>)`. These will get
+    // pushed onto the stack. Eventually, expanding `Vec<A>` will
+    // lead to us trying to push `A` a second time -- to prevent
+    // infinite recursion, we notice that `A` was already pushed
+    // once and stop.
+    let mut ty_stack = vec![(for_ty, 0)];
+
+    // Set used to detect infinite recursion.
+    let mut ty_set = FxHashSet::default();
+
+    let cause = ObligationCause::dummy();
+    let mut constraints = DropckConstraint::empty();
+    while let Some((ty, depth)) = ty_stack.pop() {
+        debug!(
+            "{} kinds, {} overflows, {} ty_stack",
+            result.kinds.len(),
+            result.overflows.len(),
+            ty_stack.len()
+        );
+        dtorck_constraint_for_ty_inner(tcx, DUMMY_SP, for_ty, depth, ty, &mut constraints)?;
+
+        // "outlives" represent types/regions that may be touched
+        // by a destructor.
+        result.kinds.append(&mut constraints.outlives);
+        result.overflows.append(&mut constraints.overflows);
+
+        // If we have even one overflow, we should stop trying to evaluate further --
+        // chances are, the subsequent overflows for this evaluation won't provide useful
+        // information and will just decrease the speed at which we can emit these errors
+        // (since we'll be printing for just that much longer for the often enormous types
+        // that result here).
+        if !result.overflows.is_empty() {
+            break;
+        }
+
+        // dtorck types are "types that will get dropped but which
+        // do not themselves define a destructor", more or less. We have
+        // to push them onto the stack to be expanded.
+        for ty in constraints.dtorck_types.drain(..) {
+            let Normalized { value: ty, obligations } =
+                ocx.infcx.at(&cause, param_env).query_normalize(ty)?;
+            ocx.register_obligations(obligations);
+
+            debug!("dropck_outlives: ty from dtorck_types = {:?}", ty);
+
+            match ty.kind() {
+                // All parameters live for the duration of the
+                // function.
+                ty::Param(..) => {}
+
+                // A projection that we couldn't resolve - it
+                // might have a destructor.
+                ty::Alias(..) => {
+                    result.kinds.push(ty.into());
+                }
+
+                _ => {
+                    if ty_set.insert(ty) {
+                        ty_stack.push((ty, depth + 1));
+                    }
+                }
+            }
+        }
+    }
+
+    debug!("dropck_outlives: result = {:#?}", result);
+    Ok(result)
+}
+
+/// Returns a set of constraints that needs to be satisfied in
+/// order for `ty` to be valid for destruction.
+pub fn dtorck_constraint_for_ty_inner<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    span: Span,
+    for_ty: Ty<'tcx>,
+    depth: usize,
+    ty: Ty<'tcx>,
+    constraints: &mut DropckConstraint<'tcx>,
+) -> Result<(), NoSolution> {
+    debug!("dtorck_constraint_for_ty_inner({:?}, {:?}, {:?}, {:?})", span, for_ty, depth, ty);
+
+    if !tcx.recursion_limit().value_within_limit(depth) {
+        constraints.overflows.push(ty);
+        return Ok(());
+    }
+
+    if trivial_dropck_outlives(tcx, ty) {
+        return Ok(());
+    }
+
+    match ty.kind() {
+        ty::Bool
+        | ty::Char
+        | ty::Int(_)
+        | ty::Uint(_)
+        | ty::Float(_)
+        | ty::Str
+        | ty::Never
+        | ty::Foreign(..)
+        | ty::RawPtr(..)
+        | ty::Ref(..)
+        | ty::FnDef(..)
+        | ty::FnPtr(_)
+        | ty::GeneratorWitness(..)
+        | ty::GeneratorWitnessMIR(..) => {
+            // these types never have a destructor
+        }
+
+        ty::Array(ety, _) | ty::Slice(ety) => {
+            // single-element containers, behave like their element
+            rustc_data_structures::stack::ensure_sufficient_stack(|| {
+                dtorck_constraint_for_ty_inner(tcx, span, for_ty, depth + 1, *ety, constraints)
+            })?;
+        }
+
+        ty::Tuple(tys) => rustc_data_structures::stack::ensure_sufficient_stack(|| {
+            for ty in tys.iter() {
+                dtorck_constraint_for_ty_inner(tcx, span, for_ty, depth + 1, ty, constraints)?;
+            }
+            Ok::<_, NoSolution>(())
+        })?,
+
+        ty::Closure(_, substs) => {
+            if !substs.as_closure().is_valid() {
+                // By the time this code runs, all type variables ought to
+                // be fully resolved.
+
+                tcx.sess.delay_span_bug(
+                    span,
+                    format!("upvar_tys for closure not found. Expected capture information for closure {ty}",),
+                );
+                return Err(NoSolution);
+            }
+
+            rustc_data_structures::stack::ensure_sufficient_stack(|| {
+                for ty in substs.as_closure().upvar_tys() {
+                    dtorck_constraint_for_ty_inner(tcx, span, for_ty, depth + 1, ty, constraints)?;
+                }
+                Ok::<_, NoSolution>(())
+            })?
+        }
+
+        ty::Generator(_, substs, _movability) => {
+            // rust-lang/rust#49918: types can be constructed, stored
+            // in the interior, and sit idle when generator yields
+            // (and is subsequently dropped).
+            //
+            // It would be nice to descend into interior of a
+            // generator to determine what effects dropping it might
+            // have (by looking at any drop effects associated with
+            // its interior).
+            //
+            // However, the interior's representation uses things like
+            // GeneratorWitness that explicitly assume they are not
+            // traversed in such a manner. So instead, we will
+            // simplify things for now by treating all generators as
+            // if they were like trait objects, where its upvars must
+            // all be alive for the generator's (potential)
+            // destructor.
+            //
+            // In particular, skipping over `_interior` is safe
+            // because any side-effects from dropping `_interior` can
+            // only take place through references with lifetimes
+            // derived from lifetimes attached to the upvars and resume
+            // argument, and we *do* incorporate those here.
+
+            if !substs.as_generator().is_valid() {
+                // By the time this code runs, all type variables ought to
+                // be fully resolved.
+                tcx.sess.delay_span_bug(
+                    span,
+                    format!("upvar_tys for generator not found. Expected capture information for generator {ty}",),
+                );
+                return Err(NoSolution);
+            }
+
+            constraints.outlives.extend(
+                substs
+                    .as_generator()
+                    .upvar_tys()
+                    .map(|t| -> ty::subst::GenericArg<'tcx> { t.into() }),
+            );
+            constraints.outlives.push(substs.as_generator().resume_ty().into());
+        }
+
+        ty::Adt(def, substs) => {
+            let DropckConstraint { dtorck_types, outlives, overflows } =
+                tcx.at(span).adt_dtorck_constraint(def.did())?;
+            // FIXME: we can try to recursively `dtorck_constraint_on_ty`
+            // there, but that needs some way to handle cycles.
+            constraints
+                .dtorck_types
+                .extend(dtorck_types.iter().map(|t| EarlyBinder(*t).subst(tcx, substs)));
+            constraints
+                .outlives
+                .extend(outlives.iter().map(|t| EarlyBinder(*t).subst(tcx, substs)));
+            constraints
+                .overflows
+                .extend(overflows.iter().map(|t| EarlyBinder(*t).subst(tcx, substs)));
+        }
+
+        // Objects must be alive in order for their destructor
+        // to be called.
+        ty::Dynamic(..) => {
+            constraints.outlives.push(ty.into());
+        }
+
+        // Types that can't be resolved. Pass them forward.
+        ty::Alias(..) | ty::Param(..) => {
+            constraints.dtorck_types.push(ty);
+        }
+
+        ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error(_) => {
+            // By the time this code runs, all type variables ought to
+            // be fully resolved.
+            return Err(NoSolution);
+        }
+    }
+
+    Ok(())
+}
diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs
index a2cfdeefd6f..01d7a1e7913 100644
--- a/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/type_op/ascribe_user_type.rs
@@ -1,9 +1,13 @@
 use crate::infer::canonical::{Canonical, CanonicalQueryResponse};
 use crate::traits::ObligationCtxt;
+use rustc_hir::def_id::{DefId, CRATE_DEF_ID};
+use rustc_infer::traits::Obligation;
 use rustc_middle::traits::query::NoSolution;
-use rustc_middle::ty::{ParamEnvAnd, TyCtxt};
+use rustc_middle::traits::{ObligationCause, ObligationCauseCode};
+use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt, UserSelfTy, UserSubsts, UserType};
 
 pub use rustc_middle::traits::query::type_op::AscribeUserType;
+use rustc_span::{Span, DUMMY_SP};
 
 impl<'tcx> super::QueryTypeOp<'tcx> for AscribeUserType<'tcx> {
     type QueryResponse = ();
@@ -23,9 +27,114 @@ impl<'tcx> super::QueryTypeOp<'tcx> for AscribeUserType<'tcx> {
     }
 
     fn perform_locally_in_new_solver(
-        _ocx: &ObligationCtxt<'_, 'tcx>,
-        _key: ParamEnvAnd<'tcx, Self>,
+        ocx: &ObligationCtxt<'_, 'tcx>,
+        key: ParamEnvAnd<'tcx, Self>,
     ) -> Result<Self::QueryResponse, NoSolution> {
-        todo!()
+        type_op_ascribe_user_type_with_span(ocx, key, None)
     }
 }
+
+/// The core of the `type_op_ascribe_user_type` query: for diagnostics purposes in NLL HRTB errors,
+/// this query can be re-run to better track the span of the obligation cause, and improve the error
+/// message. Do not call directly unless you're in that very specific context.
+pub fn type_op_ascribe_user_type_with_span<'tcx>(
+    ocx: &ObligationCtxt<'_, 'tcx>,
+    key: ParamEnvAnd<'tcx, AscribeUserType<'tcx>>,
+    span: Option<Span>,
+) -> Result<(), NoSolution> {
+    let (param_env, AscribeUserType { mir_ty, user_ty }) = key.into_parts();
+    debug!("type_op_ascribe_user_type: mir_ty={:?} user_ty={:?}", mir_ty, user_ty);
+    let span = span.unwrap_or(DUMMY_SP);
+    match user_ty {
+        UserType::Ty(user_ty) => relate_mir_and_user_ty(ocx, param_env, span, mir_ty, user_ty)?,
+        UserType::TypeOf(def_id, user_substs) => {
+            relate_mir_and_user_substs(ocx, param_env, span, mir_ty, def_id, user_substs)?
+        }
+    };
+    Ok(())
+}
+
+#[instrument(level = "debug", skip(ocx, param_env, span))]
+fn relate_mir_and_user_ty<'tcx>(
+    ocx: &ObligationCtxt<'_, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    span: Span,
+    mir_ty: Ty<'tcx>,
+    user_ty: Ty<'tcx>,
+) -> Result<(), NoSolution> {
+    let cause = ObligationCause::dummy_with_span(span);
+    let user_ty = ocx.normalize(&cause, param_env, user_ty);
+    ocx.eq(&cause, param_env, mir_ty, user_ty)?;
+
+    // FIXME(#104764): We should check well-formedness before normalization.
+    let predicate = ty::Binder::dummy(ty::PredicateKind::WellFormed(user_ty.into()));
+    ocx.register_obligation(Obligation::new(ocx.infcx.tcx, cause, param_env, predicate));
+    Ok(())
+}
+
+#[instrument(level = "debug", skip(ocx, param_env, span))]
+fn relate_mir_and_user_substs<'tcx>(
+    ocx: &ObligationCtxt<'_, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    span: Span,
+    mir_ty: Ty<'tcx>,
+    def_id: DefId,
+    user_substs: UserSubsts<'tcx>,
+) -> Result<(), NoSolution> {
+    let param_env = param_env.without_const();
+    let UserSubsts { user_self_ty, substs } = user_substs;
+    let tcx = ocx.infcx.tcx;
+    let cause = ObligationCause::dummy_with_span(span);
+
+    let ty = tcx.type_of(def_id).subst(tcx, substs);
+    let ty = ocx.normalize(&cause, param_env, ty);
+    debug!("relate_type_and_user_type: ty of def-id is {:?}", ty);
+
+    ocx.eq(&cause, param_env, mir_ty, ty)?;
+
+    // Prove the predicates coming along with `def_id`.
+    //
+    // Also, normalize the `instantiated_predicates`
+    // because otherwise we wind up with duplicate "type
+    // outlives" error messages.
+    let instantiated_predicates = tcx.predicates_of(def_id).instantiate(tcx, substs);
+
+    debug!(?instantiated_predicates);
+    for (instantiated_predicate, predicate_span) in instantiated_predicates {
+        let span = if span == DUMMY_SP { predicate_span } else { span };
+        let cause = ObligationCause::new(
+            span,
+            CRATE_DEF_ID,
+            ObligationCauseCode::AscribeUserTypeProvePredicate(predicate_span),
+        );
+        let instantiated_predicate =
+            ocx.normalize(&cause.clone(), param_env, instantiated_predicate);
+
+        ocx.register_obligation(Obligation::new(tcx, cause, param_env, instantiated_predicate));
+    }
+
+    if let Some(UserSelfTy { impl_def_id, self_ty }) = user_self_ty {
+        let self_ty = ocx.normalize(&cause, param_env, self_ty);
+        let impl_self_ty = tcx.type_of(impl_def_id).subst(tcx, substs);
+        let impl_self_ty = ocx.normalize(&cause, param_env, impl_self_ty);
+
+        ocx.eq(&cause, param_env, self_ty, impl_self_ty)?;
+        let predicate = ty::Binder::dummy(ty::PredicateKind::WellFormed(impl_self_ty.into()));
+        ocx.register_obligation(Obligation::new(tcx, cause.clone(), param_env, predicate));
+    }
+
+    // In addition to proving the predicates, we have to
+    // prove that `ty` is well-formed -- this is because
+    // the WF of `ty` is predicated on the substs being
+    // well-formed, and we haven't proven *that*. We don't
+    // want to prove the WF of types from  `substs` directly because they
+    // haven't been normalized.
+    //
+    // FIXME(nmatsakis): Well, perhaps we should normalize
+    // them?  This would only be relevant if some input
+    // type were ill-formed but did not appear in `ty`,
+    // which...could happen with normalization...
+    let predicate = ty::Binder::dummy(ty::PredicateKind::WellFormed(ty.into()));
+    ocx.register_obligation(Obligation::new(tcx, cause, param_env, predicate));
+    Ok(())
+}
diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs
index 9054bafc4a6..9989fc9c479 100644
--- a/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs
@@ -1,8 +1,15 @@
-use crate::infer::canonical::{Canonical, CanonicalQueryResponse};
+use crate::traits::query::NoSolution;
+use crate::traits::wf;
 use crate::traits::ObligationCtxt;
+
+use rustc_infer::infer::canonical::Canonical;
+use rustc_infer::infer::outlives::components::{push_outlives_components, Component};
 use rustc_infer::traits::query::OutlivesBound;
-use rustc_middle::traits::query::NoSolution;
-use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt};
+use rustc_middle::infer::canonical::CanonicalQueryResponse;
+use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt, TypeVisitableExt};
+use rustc_span::def_id::CRATE_DEF_ID;
+use rustc_span::source_map::DUMMY_SP;
+use smallvec::{smallvec, SmallVec};
 
 #[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)]
 pub struct ImpliedOutlivesBounds<'tcx> {
@@ -42,9 +49,167 @@ impl<'tcx> super::QueryTypeOp<'tcx> for ImpliedOutlivesBounds<'tcx> {
     }
 
     fn perform_locally_in_new_solver(
-        _ocx: &ObligationCtxt<'_, 'tcx>,
-        _key: ParamEnvAnd<'tcx, Self>,
+        ocx: &ObligationCtxt<'_, 'tcx>,
+        key: ParamEnvAnd<'tcx, Self>,
     ) -> Result<Self::QueryResponse, NoSolution> {
-        todo!()
+        compute_implied_outlives_bounds_inner(ocx, key.param_env, key.value.ty)
+    }
+}
+
+pub fn compute_implied_outlives_bounds_inner<'tcx>(
+    ocx: &ObligationCtxt<'_, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    ty: Ty<'tcx>,
+) -> Result<Vec<OutlivesBound<'tcx>>, NoSolution> {
+    let tcx = ocx.infcx.tcx;
+
+    // Sometimes when we ask what it takes for T: WF, we get back that
+    // U: WF is required; in that case, we push U onto this stack and
+    // process it next. Because the resulting predicates aren't always
+    // guaranteed to be a subset of the original type, so we need to store the
+    // WF args we've computed in a set.
+    let mut checked_wf_args = rustc_data_structures::fx::FxHashSet::default();
+    let mut wf_args = vec![ty.into()];
+
+    let mut outlives_bounds: Vec<ty::OutlivesPredicate<ty::GenericArg<'tcx>, ty::Region<'tcx>>> =
+        vec![];
+
+    while let Some(arg) = wf_args.pop() {
+        if !checked_wf_args.insert(arg) {
+            continue;
+        }
+
+        // Compute the obligations for `arg` to be well-formed. If `arg` is
+        // an unresolved inference variable, just substituted an empty set
+        // -- because the return type here is going to be things we *add*
+        // to the environment, it's always ok for this set to be smaller
+        // than the ultimate set. (Note: normally there won't be
+        // unresolved inference variables here anyway, but there might be
+        // during typeck under some circumstances.)
+        //
+        // FIXME(@lcnr): It's not really "always fine", having fewer implied
+        // bounds can be backward incompatible, e.g. #101951 was caused by
+        // us not dealing with inference vars in `TypeOutlives` predicates.
+        let obligations = wf::obligations(ocx.infcx, param_env, CRATE_DEF_ID, 0, arg, DUMMY_SP)
+            .unwrap_or_default();
+
+        for obligation in obligations {
+            debug!(?obligation);
+            assert!(!obligation.has_escaping_bound_vars());
+
+            // While these predicates should all be implied by other parts of
+            // the program, they are still relevant as they may constrain
+            // inference variables, which is necessary to add the correct
+            // implied bounds in some cases, mostly when dealing with projections.
+            //
+            // Another important point here: we only register `Projection`
+            // predicates, since otherwise we might register outlives
+            // predicates containing inference variables, and we don't
+            // learn anything new from those.
+            if obligation.predicate.has_non_region_infer() {
+                match obligation.predicate.kind().skip_binder() {
+                    ty::PredicateKind::Clause(ty::Clause::Projection(..))
+                    | ty::PredicateKind::AliasRelate(..) => {
+                        ocx.register_obligation(obligation.clone());
+                    }
+                    _ => {}
+                }
+            }
+
+            let pred = match obligation.predicate.kind().no_bound_vars() {
+                None => continue,
+                Some(pred) => pred,
+            };
+            match pred {
+                ty::PredicateKind::Clause(ty::Clause::Trait(..))
+                // FIXME(const_generics): Make sure that `<'a, 'b, const N: &'a &'b u32>` is sound
+                // if we ever support that
+                | ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(..))
+                | ty::PredicateKind::Subtype(..)
+                | ty::PredicateKind::Coerce(..)
+                | ty::PredicateKind::Clause(ty::Clause::Projection(..))
+                | ty::PredicateKind::ClosureKind(..)
+                | ty::PredicateKind::ObjectSafe(..)
+                | ty::PredicateKind::ConstEvaluatable(..)
+                | ty::PredicateKind::ConstEquate(..)
+                | ty::PredicateKind::Ambiguous
+                | ty::PredicateKind::AliasRelate(..)
+                | ty::PredicateKind::TypeWellFormedFromEnv(..) => {}
+
+                // We need to search through *all* WellFormed predicates
+                ty::PredicateKind::WellFormed(arg) => {
+                    wf_args.push(arg);
+                }
+
+                // We need to register region relationships
+                ty::PredicateKind::Clause(ty::Clause::RegionOutlives(ty::OutlivesPredicate(
+                    r_a,
+                    r_b,
+                ))) => outlives_bounds.push(ty::OutlivesPredicate(r_a.into(), r_b)),
+
+                ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate(
+                    ty_a,
+                    r_b,
+                ))) => outlives_bounds.push(ty::OutlivesPredicate(ty_a.into(), r_b)),
+            }
+        }
+    }
+
+    // This call to `select_all_or_error` is necessary to constrain inference variables, which we
+    // use further down when computing the implied bounds.
+    match ocx.select_all_or_error().as_slice() {
+        [] => (),
+        _ => return Err(NoSolution),
     }
+
+    // We lazily compute the outlives components as
+    // `select_all_or_error` constrains inference variables.
+    let implied_bounds = outlives_bounds
+        .into_iter()
+        .flat_map(|ty::OutlivesPredicate(a, r_b)| match a.unpack() {
+            ty::GenericArgKind::Lifetime(r_a) => vec![OutlivesBound::RegionSubRegion(r_b, r_a)],
+            ty::GenericArgKind::Type(ty_a) => {
+                let ty_a = ocx.infcx.resolve_vars_if_possible(ty_a);
+                let mut components = smallvec![];
+                push_outlives_components(tcx, ty_a, &mut components);
+                implied_bounds_from_components(r_b, components)
+            }
+            ty::GenericArgKind::Const(_) => unreachable!(),
+        })
+        .collect();
+
+    Ok(implied_bounds)
+}
+
+/// When we have an implied bound that `T: 'a`, we can further break
+/// this down to determine what relationships would have to hold for
+/// `T: 'a` to hold. We get to assume that the caller has validated
+/// those relationships.
+fn implied_bounds_from_components<'tcx>(
+    sub_region: ty::Region<'tcx>,
+    sup_components: SmallVec<[Component<'tcx>; 4]>,
+) -> Vec<OutlivesBound<'tcx>> {
+    sup_components
+        .into_iter()
+        .filter_map(|component| {
+            match component {
+                Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
+                Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
+                Component::Alias(p) => Some(OutlivesBound::RegionSubAlias(sub_region, p)),
+                Component::EscapingAlias(_) =>
+                // If the projection has escaping regions, don't
+                // try to infer any implied bounds even for its
+                // free components. This is conservative, because
+                // the caller will still have to prove that those
+                // free components outlive `sub_region`. But the
+                // idea is that the WAY that the caller proves
+                // that may change in the future and we want to
+                // give ourselves room to get smarter here.
+                {
+                    None
+                }
+                Component::UnresolvedInferenceVariable(..) => None,
+            }
+        })
+        .collect()
 }
diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs
index 8b3a20a88f0..98894263374 100644
--- a/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs
@@ -1,7 +1,9 @@
 use crate::infer::canonical::{Canonical, CanonicalQueryResponse};
-use crate::traits::query::dropck_outlives::{trivial_dropck_outlives, DropckOutlivesResult};
+use crate::traits::query::dropck_outlives::{
+    compute_dropck_outlives_inner, trivial_dropck_outlives,
+};
 use crate::traits::ObligationCtxt;
-use rustc_middle::traits::query::NoSolution;
+use rustc_middle::traits::query::{DropckOutlivesResult, NoSolution};
 use rustc_middle::ty::{ParamEnvAnd, Ty, TyCtxt};
 
 #[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)]
@@ -51,9 +53,9 @@ impl<'tcx> super::QueryTypeOp<'tcx> for DropckOutlives<'tcx> {
     }
 
     fn perform_locally_in_new_solver(
-        _ocx: &ObligationCtxt<'_, 'tcx>,
-        _key: ParamEnvAnd<'tcx, Self>,
+        ocx: &ObligationCtxt<'_, 'tcx>,
+        key: ParamEnvAnd<'tcx, Self>,
     ) -> Result<Self::QueryResponse, NoSolution> {
-        todo!()
+        compute_dropck_outlives_inner(ocx, key.param_env.and(key.value.dropped_ty))
     }
 }