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.

14 files changed, 84 insertions, 47 deletions

diff --git a/src/test/ui/derives/derive-assoc-type-not-impl.stderr b/src/test/ui/derives/derive-assoc-type-not-impl.stderr
index 45a906a3947..72dd9c153ab 100644
--- a/src/test/ui/derives/derive-assoc-type-not-impl.stderr
+++ b/src/test/ui/derives/derive-assoc-type-not-impl.stderr
@@ -13,16 +13,17 @@ LL | struct NotClone;
 LL |     Bar::<NotClone> { x: 1 }.clone();
    |                              ^^^^^ method cannot be called on `Bar<NotClone>` due to unsatisfied trait bounds
    |
-note: the following trait bounds were not satisfied because of the requirements of the implementation of `Clone` for `_`:
-      `NotClone: Clone`
+note: trait bound `NotClone: Clone` was not satisfied
   --> $DIR/derive-assoc-type-not-impl.rs:6:10
    |
 LL | #[derive(Clone)]
-   |          ^^^^^
+   |          ^^^^^ unsatisfied trait bound introduced in this `derive` macro
+   = note: the following trait bounds were not satisfied:
+           `NotClone: Clone`
+           which is required by `Bar<NotClone>: Clone`
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following trait defines an item `clone`, perhaps you need to implement it:
            candidate #1: `Clone`
-   = note: this error originates in the derive macro `Clone` (in Nightly builds, run with -Z macro-backtrace for more info)
 help: consider annotating `NotClone` with `#[derive(Clone)]`
    |
 LL | #[derive(Clone)]
diff --git a/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.rs b/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.rs
index 8b6f7c41a7c..655abd18da1 100644
--- a/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.rs
+++ b/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.rs
@@ -12,7 +12,10 @@ trait M {
 }
 
 impl<T: X<Y<i32> = i32>> M for T {}
-//~^ NOTE the following trait bounds were not satisfied
+//~^ NOTE trait bound `<S as X>::Y<i32> = i32` was not satisfied
+//~| NOTE unsatisfied trait bound introduced here
+//~| NOTE
+//~| NOTE
 
 struct S;
 //~^ NOTE method `f` not found for this
diff --git a/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.stderr b/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.stderr
index 3eeb9540e73..9eeebd80afe 100644
--- a/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.stderr
+++ b/src/test/ui/generic-associated-types/method-unsatified-assoc-type-predicate.stderr
@@ -1,5 +1,5 @@
 error[E0599]: the method `f` exists for struct `S`, but its trait bounds were not satisfied
-  --> $DIR/method-unsatified-assoc-type-predicate.rs:27:7
+  --> $DIR/method-unsatified-assoc-type-predicate.rs:30:7
    |
 LL | struct S;
    | ---------
@@ -11,12 +11,13 @@ LL | struct S;
 LL |     a.f();
    |       ^ method cannot be called on `S` due to unsatisfied trait bounds
    |
-note: the following trait bounds were not satisfied because of the requirements of the implementation of `M` for `_`:
-      `<S as X>::Y<i32> = i32`
-  --> $DIR/method-unsatified-assoc-type-predicate.rs:14:26
+note: trait bound `<S as X>::Y<i32> = i32` was not satisfied
+  --> $DIR/method-unsatified-assoc-type-predicate.rs:14:11
    |
 LL | impl<T: X<Y<i32> = i32>> M for T {}
-   |                          ^     ^
+   |           ^^^^^^^^^^^^   -     -
+   |           |
+   |           unsatisfied trait bound introduced here
 
 error: aborting due to previous error
 
diff --git a/src/test/ui/hrtb/issue-30786.migrate.stderr b/src/test/ui/hrtb/issue-30786.migrate.stderr
index a2ab1f1856d..7ffe2f4cd7e 100644
--- a/src/test/ui/hrtb/issue-30786.migrate.stderr
+++ b/src/test/ui/hrtb/issue-30786.migrate.stderr
@@ -10,14 +10,14 @@ LL | pub struct Map<S, F> {
 LL |     let filter = map.filterx(|x: &_| true);
    |                      ^^^^^^^ method cannot be called on `Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>` due to unsatisfied trait bounds
    |
-note: the following trait bounds were not satisfied because of the requirements of the implementation of `StreamExt` for `_`:
-      `&'a mut Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
+note: the following trait bounds were not satisfied:
       `&'a mut &Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
       `&'a mut &mut Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
-  --> $DIR/issue-30786.rs:105:9
+      `&'a mut Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
+  --> $DIR/issue-30786.rs:105:50
    |
 LL | impl<T> StreamExt for T where for<'a> &'a mut T: Stream {}
-   |         ^^^^^^^^^     ^
+   |         ---------     -                          ^^^^^^ unsatisfied trait bound introduced here
 
 error[E0599]: the method `countx` exists for struct `Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>`, but its trait bounds were not satisfied
   --> $DIR/issue-30786.rs:140:24
@@ -31,14 +31,14 @@ LL | pub struct Filter<S, F> {
 LL |     let count = filter.countx();
    |                        ^^^^^^ method cannot be called on `Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>` due to unsatisfied trait bounds
    |
-note: the following trait bounds were not satisfied because of the requirements of the implementation of `StreamExt` for `_`:
-      `&'a mut Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
+note: the following trait bounds were not satisfied:
       `&'a mut &Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
       `&'a mut &mut Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
-  --> $DIR/issue-30786.rs:105:9
+      `&'a mut Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
+  --> $DIR/issue-30786.rs:105:50
    |
 LL | impl<T> StreamExt for T where for<'a> &'a mut T: Stream {}
-   |         ^^^^^^^^^     ^
+   |         ---------     -                          ^^^^^^ unsatisfied trait bound introduced here
 
 error: aborting due to 2 previous errors
 
diff --git a/src/test/ui/hrtb/issue-30786.nll.stderr b/src/test/ui/hrtb/issue-30786.nll.stderr
index a2ab1f1856d..7ffe2f4cd7e 100644
--- a/src/test/ui/hrtb/issue-30786.nll.stderr
+++ b/src/test/ui/hrtb/issue-30786.nll.stderr
@@ -10,14 +10,14 @@ LL | pub struct Map<S, F> {
 LL |     let filter = map.filterx(|x: &_| true);
    |                      ^^^^^^^ method cannot be called on `Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>` due to unsatisfied trait bounds
    |
-note: the following trait bounds were not satisfied because of the requirements of the implementation of `StreamExt` for `_`:
-      `&'a mut Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
+note: the following trait bounds were not satisfied:
       `&'a mut &Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
       `&'a mut &mut Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
-  --> $DIR/issue-30786.rs:105:9
+      `&'a mut Map<Repeat, [closure@$DIR/issue-30786.rs:126:27: 126:36]>: Stream`
+  --> $DIR/issue-30786.rs:105:50
    |
 LL | impl<T> StreamExt for T where for<'a> &'a mut T: Stream {}
-   |         ^^^^^^^^^     ^
+   |         ---------     -                          ^^^^^^ unsatisfied trait bound introduced here
 
 error[E0599]: the method `countx` exists for struct `Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>`, but its trait bounds were not satisfied
   --> $DIR/issue-30786.rs:140:24
@@ -31,14 +31,14 @@ LL | pub struct Filter<S, F> {
 LL |     let count = filter.countx();
    |                        ^^^^^^ method cannot be called on `Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>` due to unsatisfied trait bounds
    |
-note: the following trait bounds were not satisfied because of the requirements of the implementation of `StreamExt` for `_`:
-      `&'a mut Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
+note: the following trait bounds were not satisfied:
       `&'a mut &Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
       `&'a mut &mut Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
-  --> $DIR/issue-30786.rs:105:9
+      `&'a mut Filter<Map<Repeat, for<'r> fn(&'r u64) -> &'r u64 {identity::<u64>}>, [closure@$DIR/issue-30786.rs:139:30: 139:42]>: Stream`
+  --> $DIR/issue-30786.rs:105:50
    |
 LL | impl<T> StreamExt for T where for<'a> &'a mut T: Stream {}
-   |         ^^^^^^^^^     ^
+   |         ---------     -                          ^^^^^^ unsatisfied trait bound introduced here
 
 error: aborting due to 2 previous errors
 
diff --git a/src/test/ui/missing-trait-bounds/missing-trait-bounds-for-method-call.stderr b/src/test/ui/missing-trait-bounds/missing-trait-bounds-for-method-call.stderr
index 2f0fd692a44..f3c6b39e62e 100644
--- a/src/test/ui/missing-trait-bounds/missing-trait-bounds-for-method-call.stderr
+++ b/src/test/ui/missing-trait-bounds/missing-trait-bounds-for-method-call.stderr
@@ -7,11 +7,20 @@ LL | struct Foo<T> {
 LL |         self.foo();
    |              ^^^ method cannot be called on `&Foo<T>` due to unsatisfied trait bounds
    |
-   = note: the following trait bounds were not satisfied:
-           `T: Default`
-           which is required by `Foo<T>: Bar`
-           `T: Bar`
-           which is required by `Foo<T>: Bar`
+note: trait bound `T: Default` was not satisfied
+  --> $DIR/missing-trait-bounds-for-method-call.rs:10:9
+   |
+LL | impl<T: Default + Bar> Bar for Foo<T> {}
+   |         ^^^^^^^        ---     ------
+   |         |
+   |         unsatisfied trait bound introduced here
+note: trait bound `T: Bar` was not satisfied
+  --> $DIR/missing-trait-bounds-for-method-call.rs:10:19
+   |
+LL | impl<T: Default + Bar> Bar for Foo<T> {}
+   |                   ^^^  ---     ------
+   |                   |
+   |                   unsatisfied trait bound introduced here
 help: consider restricting the type parameters to satisfy the trait bounds
    |
 LL | struct Foo<T> where T: Bar, T: Default {
@@ -26,9 +35,13 @@ LL | struct Fin<T> where T: Bar {
 LL |         self.foo();
    |              ^^^ method cannot be called on `&Fin<T>` due to unsatisfied trait bounds
    |
-   = note: the following trait bounds were not satisfied:
-           `T: Default`
-           which is required by `Fin<T>: Bar`
+note: trait bound `T: Default` was not satisfied
+  --> $DIR/missing-trait-bounds-for-method-call.rs:23:9
+   |
+LL | impl<T: Default + Bar> Bar for Fin<T> {}
+   |         ^^^^^^^        ---     ------
+   |         |
+   |         unsatisfied trait bound introduced here
 help: consider restricting the type parameter to satisfy the trait bound
    |
 LL | struct Fin<T> where T: Bar, T: Default {
diff --git a/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.precise.stderr b/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.precise.stderr
index fedb1ffdea9..9dbaffd4c15 100644
--- a/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.precise.stderr
+++ b/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.precise.stderr
@@ -54,6 +54,12 @@ LL |         const _: () = check($exp);
 LL |     ConstDropImplWithBounds::<NonTrivialDrop>(PhantomData),
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected an implementor of trait `~const Destruct`
    |
+note: required because of the requirements on the impl of `~const Destruct` for `ConstDropImplWithBounds<NonTrivialDrop>`
+  --> $DIR/const-drop-fail.rs:28:25
+   |
+LL | impl<T: ~const A> const Drop for ConstDropImplWithBounds<T> {
+   |                         ^^^^     ^^^^^^^^^^^^^^^^^^^^^^^^^^
+   = note: 1 redundant requirement hidden
    = note: required because of the requirements on the impl of `~const Destruct` for `ConstDropImplWithBounds<NonTrivialDrop>`
 note: required by a bound in `check`
   --> $DIR/const-drop-fail.rs:34:19
diff --git a/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.stock.stderr b/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.stock.stderr
index fedb1ffdea9..9dbaffd4c15 100644
--- a/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.stock.stderr
+++ b/src/test/ui/rfc-2632-const-trait-impl/const-drop-fail.stock.stderr
@@ -54,6 +54,12 @@ LL |         const _: () = check($exp);
 LL |     ConstDropImplWithBounds::<NonTrivialDrop>(PhantomData),
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected an implementor of trait `~const Destruct`
    |
+note: required because of the requirements on the impl of `~const Destruct` for `ConstDropImplWithBounds<NonTrivialDrop>`
+  --> $DIR/const-drop-fail.rs:28:25
+   |
+LL | impl<T: ~const A> const Drop for ConstDropImplWithBounds<T> {
+   |                         ^^^^     ^^^^^^^^^^^^^^^^^^^^^^^^^^
+   = note: 1 redundant requirement hidden
    = note: required because of the requirements on the impl of `~const Destruct` for `ConstDropImplWithBounds<NonTrivialDrop>`
 note: required by a bound in `check`
   --> $DIR/const-drop-fail.rs:34:19
diff --git a/src/test/ui/specialization/defaultimpl/specialization-trait-not-implemented.stderr b/src/test/ui/specialization/defaultimpl/specialization-trait-not-implemented.stderr
index 81e2a9a1ffc..9894ecc64b5 100644
--- a/src/test/ui/specialization/defaultimpl/specialization-trait-not-implemented.stderr
+++ b/src/test/ui/specialization/defaultimpl/specialization-trait-not-implemented.stderr
@@ -20,8 +20,7 @@ LL | struct MyStruct;
 LL |     println!("{}", MyStruct.foo_one());
    |                             ^^^^^^^ method cannot be called on `MyStruct` due to unsatisfied trait bounds
    |
-note: the following trait bounds were not satisfied because of the requirements of the implementation of `Foo` for `_`:
-      `MyStruct: Foo`
+note: trait bound `MyStruct: Foo` was not satisfied
   --> $DIR/specialization-trait-not-implemented.rs:14:17
    |
 LL | default impl<T> Foo for T {
diff --git a/src/test/ui/traits/alias/cross-crate.stderr b/src/test/ui/traits/alias/cross-crate.stderr
index 3c3b6e56690..d0d00c97e83 100644
--- a/src/test/ui/traits/alias/cross-crate.stderr
+++ b/src/test/ui/traits/alias/cross-crate.stderr
@@ -5,6 +5,7 @@ LL |     use_alias::<Rc<u32>>();
    |                 ^^^^^^^ `Rc<u32>` cannot be sent between threads safely
    |
    = help: the trait `Send` is not implemented for `Rc<u32>`
+   = note: required because of the requirements on the impl of `SendSync` for `Rc<u32>`
 note: required by a bound in `use_alias`
   --> $DIR/cross-crate.rs:10:17
    |
@@ -18,6 +19,7 @@ LL |     use_alias::<Rc<u32>>();
    |                 ^^^^^^^ `Rc<u32>` cannot be shared between threads safely
    |
    = help: the trait `Sync` is not implemented for `Rc<u32>`
+   = note: required because of the requirements on the impl of `SendSync` for `Rc<u32>`
 note: required by a bound in `use_alias`
   --> $DIR/cross-crate.rs:10:17
    |
diff --git a/src/test/ui/traits/inductive-overflow/supertrait-auto-trait.stderr b/src/test/ui/traits/inductive-overflow/supertrait-auto-trait.stderr
index 8405d7ddc7a..9ceeea4872f 100644
--- a/src/test/ui/traits/inductive-overflow/supertrait-auto-trait.stderr
+++ b/src/test/ui/traits/inductive-overflow/supertrait-auto-trait.stderr
@@ -14,7 +14,11 @@ LL |     let (a, b) = copy(NoClone);
    |                  |
    |                  required by a bound introduced by this call
    |
-   = note: required because of the requirements on the impl of `Magic` for `NoClone`
+note: required because of the requirements on the impl of `Magic` for `NoClone`
+  --> $DIR/supertrait-auto-trait.rs:8:12
+   |
+LL | auto trait Magic: Copy {}
+   |            ^^^^^
 note: required by a bound in `copy`
   --> $DIR/supertrait-auto-trait.rs:10:12
    |
diff --git a/src/test/ui/union/union-derive-clone.mirunsafeck.stderr b/src/test/ui/union/union-derive-clone.mirunsafeck.stderr
index e8e65fe5d1d..de0bc7830b7 100644
--- a/src/test/ui/union/union-derive-clone.mirunsafeck.stderr
+++ b/src/test/ui/union/union-derive-clone.mirunsafeck.stderr
@@ -13,6 +13,11 @@ LL | struct CloneNoCopy;
 LL |     let w = u.clone();
    |               ^^^^^ method cannot be called on `U5<CloneNoCopy>` due to unsatisfied trait bounds
    |
+note: trait bound `CloneNoCopy: Copy` was not satisfied
+  --> $DIR/union-derive-clone.rs:28:10
+   |
+LL | #[derive(Clone, Copy)]
+   |          ^^^^^ unsatisfied trait bound introduced in this `derive` macro
    = note: the following trait bounds were not satisfied:
            `CloneNoCopy: Copy`
            which is required by `U5<CloneNoCopy>: Clone`
diff --git a/src/test/ui/union/union-derive-clone.thirunsafeck.stderr b/src/test/ui/union/union-derive-clone.thirunsafeck.stderr
index e8e65fe5d1d..de0bc7830b7 100644
--- a/src/test/ui/union/union-derive-clone.thirunsafeck.stderr
+++ b/src/test/ui/union/union-derive-clone.thirunsafeck.stderr
@@ -13,6 +13,11 @@ LL | struct CloneNoCopy;
 LL |     let w = u.clone();
    |               ^^^^^ method cannot be called on `U5<CloneNoCopy>` due to unsatisfied trait bounds
    |
+note: trait bound `CloneNoCopy: Copy` was not satisfied
+  --> $DIR/union-derive-clone.rs:28:10
+   |
+LL | #[derive(Clone, Copy)]
+   |          ^^^^^ unsatisfied trait bound introduced in this `derive` macro
    = note: the following trait bounds were not satisfied:
            `CloneNoCopy: Copy`
            which is required by `U5<CloneNoCopy>: Clone`
diff --git a/src/test/ui/wf/hir-wf-check-erase-regions.stderr b/src/test/ui/wf/hir-wf-check-erase-regions.stderr
index aef6db0a40b..0d9b9627562 100644
--- a/src/test/ui/wf/hir-wf-check-erase-regions.stderr
+++ b/src/test/ui/wf/hir-wf-check-erase-regions.stderr
@@ -5,11 +5,7 @@ LL |     type IntoIter = std::iter::Flatten<std::slice::Iter<'a, T>>;
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ `&T` is not an iterator
    |
    = help: the trait `Iterator` is not implemented for `&T`
-note: required because of the requirements on the impl of `IntoIterator` for `&T`
-  --> $DIR/hir-wf-check-erase-regions.rs:6:29
-   |
-LL | impl<'a, T, const N: usize> IntoIterator for &'a Table<T, N> {
-   |                             ^^^^^^^^^^^^     ^^^^^^^^^^^^^^^
+   = note: required because of the requirements on the impl of `IntoIterator` for `&T`
 note: required by a bound in `Flatten`
   --> $SRC_DIR/core/src/iter/adapters/flatten.rs:LL:COL
    |
@@ -23,11 +19,7 @@ LL |     fn into_iter(self) -> Self::IntoIter {
    |                           ^^^^^^^^^^^^^^ `&T` is not an iterator
    |
    = help: the trait `Iterator` is not implemented for `&T`
-note: required because of the requirements on the impl of `IntoIterator` for `&T`
-  --> $DIR/hir-wf-check-erase-regions.rs:6:29
-   |
-LL | impl<'a, T, const N: usize> IntoIterator for &'a Table<T, N> {
-   |                             ^^^^^^^^^^^^     ^^^^^^^^^^^^^^^
+   = note: required because of the requirements on the impl of `IntoIterator` for `&T`
 note: required by a bound in `Flatten`
   --> $SRC_DIR/core/src/iter/adapters/flatten.rs:LL:COL
    |