Properly track `ImplObligation`s

Instead of probing for all possible impls that could have caused an
`ImplObligation`, keep track of its `DefId` and obligation spans for
accurate error reporting.

Follow up to #89580. Addresses #89418.

Remove some unnecessary clones.

Tweak output for auto trait impl obligations.

3 files changed, 145 insertions, 88 deletions

diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
index b617067e66d..d65b390af34 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
@@ -507,8 +507,8 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
         let body_id = obligation.cause.body_id;
         let span = obligation.cause.span;
         let real_trait_pred = match &*code {
-            ObligationCauseCode::ImplDerivedObligation(cause)
-            | ObligationCauseCode::DerivedObligation(cause)
+            ObligationCauseCode::ImplDerivedObligation(cause) => cause.derived.parent_trait_pred,
+            ObligationCauseCode::DerivedObligation(cause)
             | ObligationCauseCode::BuiltinDerivedObligation(cause) => cause.parent_trait_pred,
             _ => trait_pred,
         };
@@ -790,8 +790,8 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
             return false;
         };
 
-        if let ObligationCauseCode::ImplDerivedObligation(obligation) = code {
-            try_borrowing(obligation.parent_trait_pred, &[])
+        if let ObligationCauseCode::ImplDerivedObligation(cause) = &*code {
+            try_borrowing(cause.derived.parent_trait_pred, &[])
         } else if let ObligationCauseCode::BindingObligation(_, _)
         | ObligationCauseCode::ItemObligation(_) = code
         {
@@ -1433,13 +1433,43 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                 ObligationCauseCode::FunctionArgumentObligation { parent_code, .. } => {
                     next_code = Some(parent_code.as_ref());
                 }
+                ObligationCauseCode::ImplDerivedObligation(cause) => {
+                    let ty = cause.derived.parent_trait_pred.skip_binder().self_ty();
+                    debug!(
+                        "maybe_note_obligation_cause_for_async_await: ImplDerived \
+                         parent_trait_ref={:?} self_ty.kind={:?}",
+                        cause.derived.parent_trait_pred,
+                        ty.kind()
+                    );
+
+                    match *ty.kind() {
+                        ty::Generator(did, ..) => {
+                            generator = generator.or(Some(did));
+                            outer_generator = Some(did);
+                        }
+                        ty::GeneratorWitness(..) => {}
+                        ty::Tuple(_) if !seen_upvar_tys_infer_tuple => {
+                            // By introducing a tuple of upvar types into the chain of obligations
+                            // of a generator, the first non-generator item is now the tuple itself,
+                            // we shall ignore this.
+
+                            seen_upvar_tys_infer_tuple = true;
+                        }
+                        _ if generator.is_none() => {
+                            trait_ref = Some(cause.derived.parent_trait_pred.skip_binder());
+                            target_ty = Some(ty);
+                        }
+                        _ => {}
+                    }
+
+                    next_code = Some(cause.derived.parent_code.as_ref());
+                }
                 ObligationCauseCode::DerivedObligation(derived_obligation)
-                | ObligationCauseCode::BuiltinDerivedObligation(derived_obligation)
-                | ObligationCauseCode::ImplDerivedObligation(derived_obligation) => {
+                | ObligationCauseCode::BuiltinDerivedObligation(derived_obligation) => {
                     let ty = derived_obligation.parent_trait_pred.skip_binder().self_ty();
                     debug!(
                         "maybe_note_obligation_cause_for_async_await: \
-                            parent_trait_ref={:?} self_ty.kind={:?}",
+                         parent_trait_ref={:?} self_ty.kind={:?}",
                         derived_obligation.parent_trait_pred,
                         ty.kind()
                     );
@@ -2166,7 +2196,8 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                 }
             }
             ObligationCauseCode::ImplDerivedObligation(ref data) => {
-                let mut parent_trait_pred = self.resolve_vars_if_possible(data.parent_trait_pred);
+                let mut parent_trait_pred =
+                    self.resolve_vars_if_possible(data.derived.parent_trait_pred);
                 parent_trait_pred.remap_constness_diag(param_env);
                 let parent_def_id = parent_trait_pred.def_id();
                 let msg = format!(
@@ -2174,51 +2205,63 @@ impl<'a, 'tcx> InferCtxtExt<'tcx> for InferCtxt<'a, 'tcx> {
                     parent_trait_pred.print_modifiers_and_trait_path(),
                     parent_trait_pred.skip_binder().self_ty()
                 );
-                let mut candidates = vec![];
-                self.tcx.for_each_relevant_impl(
-                    parent_def_id,
-                    parent_trait_pred.self_ty().skip_binder(),
-                    |impl_def_id| match self.tcx.hir().get_if_local(impl_def_id) {
-                        Some(Node::Item(hir::Item {
-                            kind: hir::ItemKind::Impl(hir::Impl { .. }),
-                            ..
-                        })) => {
-                            candidates.push(impl_def_id);
-                        }
-                        _ => {}
-                    },
-                );
-                match &candidates[..] {
-                    [def_id] => match self.tcx.hir().get_if_local(*def_id) {
-                        Some(Node::Item(hir::Item {
-                            kind: hir::ItemKind::Impl(hir::Impl { of_trait, self_ty, .. }),
-                            ..
-                        })) => {
-                            let mut spans = Vec::with_capacity(2);
-                            if let Some(trait_ref) = of_trait {
-                                spans.push(trait_ref.path.span);
-                            }
-                            spans.push(self_ty.span);
-                            err.span_note(spans, &msg)
+                let mut is_auto_trait = false;
+                match self.tcx.hir().get_if_local(data.impl_def_id) {
+                    Some(Node::Item(hir::Item {
+                        kind: hir::ItemKind::Trait(is_auto, ..),
+                        ident,
+                        ..
+                    })) => {
+                        // FIXME: we should do something else so that it works even on crate foreign
+                        // auto traits.
+                        is_auto_trait = matches!(is_auto, hir::IsAuto::Yes);
+                        err.span_note(ident.span, &msg)
+                    }
+                    Some(Node::Item(hir::Item {
+                        kind: hir::ItemKind::Impl(hir::Impl { of_trait, self_ty, .. }),
+                        ..
+                    })) => {
+                        let mut spans = Vec::with_capacity(2);
+                        if let Some(trait_ref) = of_trait {
+                            spans.push(trait_ref.path.span);
                         }
-                        _ => err.note(&msg),
-                    },
+                        spans.push(self_ty.span);
+                        err.span_note(spans, &msg)
+                    }
                     _ => err.note(&msg),
                 };
 
                 let mut parent_predicate = parent_trait_pred.to_predicate(tcx);
-                let mut data = data;
+                let mut data = &data.derived;
                 let mut count = 0;
                 seen_requirements.insert(parent_def_id);
+                if is_auto_trait {
+                    // We don't want to point at the ADT saying "required because it appears within
+                    // the type `X`", like we would otherwise do in test `supertrait-auto-trait.rs`.
+                    while let ObligationCauseCode::BuiltinDerivedObligation(derived) =
+                        &*data.parent_code
+                    {
+                        let child_trait_ref =
+                            self.resolve_vars_if_possible(derived.parent_trait_pred);
+                        let child_def_id = child_trait_ref.def_id();
+                        if seen_requirements.insert(child_def_id) {
+                            break;
+                        }
+                        data = derived;
+                        parent_predicate = child_trait_ref.to_predicate(tcx);
+                        parent_trait_pred = child_trait_ref;
+                    }
+                }
                 while let ObligationCauseCode::ImplDerivedObligation(child) = &*data.parent_code {
                     // Skip redundant recursive obligation notes. See `ui/issue-20413.rs`.
-                    let child_trait_pred = self.resolve_vars_if_possible(child.parent_trait_pred);
+                    let child_trait_pred =
+                        self.resolve_vars_if_possible(child.derived.parent_trait_pred);
                     let child_def_id = child_trait_pred.def_id();
                     if seen_requirements.insert(child_def_id) {
                         break;
                     }
                     count += 1;
-                    data = child;
+                    data = &child.derived;
                     parent_predicate = child_trait_pred.to_predicate(tcx);
                     parent_trait_pred = child_trait_pred;
                 }
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index df760a166e8..9c871eea1cd 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -18,24 +18,17 @@ use rustc_span::def_id::DefId;
 
 use crate::traits::project::{normalize_with_depth, normalize_with_depth_to};
 use crate::traits::select::TraitObligationExt;
-use crate::traits::util;
-use crate::traits::util::{closure_trait_ref_and_return_type, predicate_for_trait_def};
-use crate::traits::ImplSource;
-use crate::traits::Normalized;
-use crate::traits::OutputTypeParameterMismatch;
-use crate::traits::Selection;
-use crate::traits::TraitNotObjectSafe;
-use crate::traits::VtblSegment;
-use crate::traits::{BuiltinDerivedObligation, ImplDerivedObligation};
+use crate::traits::util::{self, closure_trait_ref_and_return_type, predicate_for_trait_def};
 use crate::traits::{
-    ImplSourceAutoImplData, ImplSourceBuiltinData, ImplSourceClosureData,
-    ImplSourceConstDestructData, ImplSourceDiscriminantKindData, ImplSourceFnPointerData,
-    ImplSourceGeneratorData, ImplSourceObjectData, ImplSourcePointeeData, ImplSourceTraitAliasData,
-    ImplSourceTraitUpcastingData, ImplSourceUserDefinedData,
+    BuiltinDerivedObligation, DerivedObligationCause, ImplDerivedObligation,
+    ImplDerivedObligationCause, ImplSource, ImplSourceAutoImplData, ImplSourceBuiltinData,
+    ImplSourceClosureData, ImplSourceConstDestructData, ImplSourceDiscriminantKindData,
+    ImplSourceFnPointerData, ImplSourceGeneratorData, ImplSourceObjectData, ImplSourcePointeeData,
+    ImplSourceTraitAliasData, ImplSourceTraitUpcastingData, ImplSourceUserDefinedData, Normalized,
+    ObjectCastObligation, Obligation, ObligationCause, OutputTypeParameterMismatch,
+    PredicateObligation, Selection, SelectionError, TraitNotObjectSafe, TraitObligation,
+    Unimplemented, VtblSegment,
 };
-use crate::traits::{ObjectCastObligation, PredicateObligation, TraitObligation};
-use crate::traits::{Obligation, ObligationCause};
-use crate::traits::{SelectionError, Unimplemented};
 
 use super::BuiltinImplConditions;
 use super::SelectionCandidate::{self, *};
@@ -321,28 +314,29 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!(?nested, "vtable_auto_impl");
         ensure_sufficient_stack(|| {
             let cause = obligation.derived_cause(BuiltinDerivedObligation);
-            let mut obligations = self.collect_predicates_for_types(
-                obligation.param_env,
-                cause,
-                obligation.recursion_depth + 1,
-                trait_def_id,
-                nested,
-            );
 
             let trait_obligations: Vec<PredicateObligation<'_>> =
                 self.infcx.commit_unconditionally(|_| {
                     let poly_trait_ref = obligation.predicate.to_poly_trait_ref();
                     let trait_ref = self.infcx.replace_bound_vars_with_placeholders(poly_trait_ref);
-                    let cause = obligation.derived_cause(ImplDerivedObligation);
                     self.impl_or_trait_obligations(
-                        cause,
+                        &cause,
                         obligation.recursion_depth + 1,
                         obligation.param_env,
                         trait_def_id,
                         &trait_ref.substs,
+                        obligation.predicate,
                     )
                 });
 
+            let mut obligations = self.collect_predicates_for_types(
+                obligation.param_env,
+                cause,
+                obligation.recursion_depth + 1,
+                trait_def_id,
+                nested,
+            );
+
             // Adds the predicates from the trait.  Note that this contains a `Self: Trait`
             // predicate as usual.  It won't have any effect since auto traits are coinductive.
             obligations.extend(trait_obligations);
@@ -365,14 +359,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         self.infcx.commit_unconditionally(|_| {
             let substs = self.rematch_impl(impl_def_id, obligation);
             debug!(?substs, "impl substs");
-            let cause = obligation.derived_cause(ImplDerivedObligation);
             ensure_sufficient_stack(|| {
                 self.vtable_impl(
                     impl_def_id,
                     substs,
-                    cause,
+                    &obligation.cause,
                     obligation.recursion_depth + 1,
                     obligation.param_env,
+                    obligation.predicate,
                 )
             })
         })
@@ -382,9 +376,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         &mut self,
         impl_def_id: DefId,
         substs: Normalized<'tcx, SubstsRef<'tcx>>,
-        cause: ObligationCause<'tcx>,
+        cause: &ObligationCause<'tcx>,
         recursion_depth: usize,
         param_env: ty::ParamEnv<'tcx>,
+        parent_trait_pred: ty::Binder<'tcx, ty::TraitPredicate<'tcx>>,
     ) -> ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>> {
         debug!(?impl_def_id, ?substs, ?recursion_depth, "vtable_impl");
 
@@ -394,6 +389,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             param_env,
             impl_def_id,
             &substs.value,
+            parent_trait_pred,
         );
 
         debug!(?impl_obligations, "vtable_impl");
@@ -566,11 +562,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             let substs = trait_ref.substs;
 
             let trait_obligations = self.impl_or_trait_obligations(
-                obligation.cause.clone(),
+                &obligation.cause,
                 obligation.recursion_depth,
                 obligation.param_env,
                 trait_def_id,
                 &substs,
+                obligation.predicate,
             );
 
             debug!(?trait_def_id, ?trait_obligations, "trait alias obligations");
@@ -1073,14 +1070,30 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 });
                 let substs = self.rematch_impl(impl_def_id, &new_obligation);
                 debug!(?substs, "impl substs");
-                let cause = obligation.derived_cause(ImplDerivedObligation);
+
+                let derived = DerivedObligationCause {
+                    parent_trait_pred: obligation.predicate,
+                    parent_code: obligation.cause.clone_code(),
+                };
+                let derived_code = ImplDerivedObligation(Box::new(ImplDerivedObligationCause {
+                    derived,
+                    impl_def_id,
+                    span: obligation.cause.span,
+                }));
+
+                let cause = ObligationCause::new(
+                    obligation.cause.span,
+                    obligation.cause.body_id,
+                    derived_code,
+                );
                 ensure_sufficient_stack(|| {
                     self.vtable_impl(
                         impl_def_id,
                         substs,
-                        cause,
+                        &cause,
                         new_obligation.recursion_depth + 1,
                         new_obligation.param_env,
+                        obligation.predicate,
                     )
                 })
             });
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 5d07139e87b..c15afa33d2b 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -13,15 +13,11 @@ use super::project::ProjectionTyObligation;
 use super::util;
 use super::util::{closure_trait_ref_and_return_type, predicate_for_trait_def};
 use super::wf;
-use super::DerivedObligationCause;
-use super::Normalized;
-use super::Obligation;
-use super::ObligationCauseCode;
-use super::Selection;
-use super::SelectionResult;
-use super::TraitQueryMode;
-use super::{ErrorReporting, Overflow, SelectionError};
-use super::{ObligationCause, PredicateObligation, TraitObligation};
+use super::{
+    DerivedObligationCause, ErrorReporting, ImplDerivedObligation, ImplDerivedObligationCause,
+    Normalized, Obligation, ObligationCause, ObligationCauseCode, Overflow, PredicateObligation,
+    Selection, SelectionError, SelectionResult, TraitObligation, TraitQueryMode,
+};
 
 use crate::infer::{InferCtxt, InferOk, TypeFreshener};
 use crate::traits::error_reporting::InferCtxtExt;
@@ -2333,11 +2329,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     #[tracing::instrument(level = "debug", skip(self, cause, param_env))]
     fn impl_or_trait_obligations(
         &mut self,
-        cause: ObligationCause<'tcx>,
+        cause: &ObligationCause<'tcx>,
         recursion_depth: usize,
         param_env: ty::ParamEnv<'tcx>,
         def_id: DefId,           // of impl or trait
         substs: SubstsRef<'tcx>, // for impl or trait
+        parent_trait_pred: ty::Binder<'tcx, ty::TraitPredicate<'tcx>>,
     ) -> Vec<PredicateObligation<'tcx>> {
         let tcx = self.tcx();
 
@@ -2359,8 +2356,17 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         debug!(?predicates);
         assert_eq!(predicates.parent, None);
         let mut obligations = Vec::with_capacity(predicates.predicates.len());
-        for (predicate, _) in predicates.predicates {
-            debug!(?predicate);
+        let parent_code = cause.clone_code();
+        for (predicate, span) in predicates.predicates {
+            let span = *span;
+            let derived =
+                DerivedObligationCause { parent_trait_pred, parent_code: parent_code.clone() };
+            let code = ImplDerivedObligation(Box::new(ImplDerivedObligationCause {
+                derived,
+                impl_def_id: def_id,
+                span,
+            }));
+            let cause = ObligationCause::new(cause.span, cause.body_id, code);
             let predicate = normalize_with_depth_to(
                 self,
                 param_env,
@@ -2369,12 +2375,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 predicate.subst(tcx, substs),
                 &mut obligations,
             );
-            obligations.push(Obligation {
-                cause: cause.clone(),
-                recursion_depth,
-                param_env,
-                predicate,
-            });
+            obligations.push(Obligation { cause, recursion_depth, param_env, predicate });
         }
 
         obligations