Rollup merge of #124682 - estebank:issue-40990, r=pnkfelix

Suggest setting lifetime in borrowck error involving types with elided lifetimes

```
error: lifetime may not live long enough
  --> $DIR/ex3-both-anon-regions-both-are-structs-2.rs:7:5
   |
LL | fn foo(mut x: Ref, y: Ref) {
   |        -----       - has type `Ref<'_, '1>`
   |        |
   |        has type `Ref<'_, '2>`
LL |     x.b = y.b;
   |     ^^^^^^^^^ assignment requires that `'1` must outlive `'2`
   |
help: consider introducing a named lifetime parameter
   |
LL | fn foo<'a>(mut x: Ref<'a, 'a>, y: Ref<'a, 'a>) {
   |       ++++           ++++++++        ++++++++
```

As can be seen above, it currently doesn't try to compare the `ty::Ty` lifetimes that diverged vs the `hir::Ty` to correctly suggest the following

```
help: consider introducing a named lifetime parameter
   |
LL | fn foo<'a>(mut x: Ref<'_, 'a>, y: Ref<'_, 'a>) {
   |       ++++           ++++++++        ++++++++
```

but I believe this to still be an improvement over the status quo.

Fix #40990.

2 files changed, 131 insertions, 35 deletions

diff --git a/compiler/rustc_infer/messages.ftl b/compiler/rustc_infer/messages.ftl
index 64f52ea7ac1..8f1c4ad462a 100644
--- a/compiler/rustc_infer/messages.ftl
+++ b/compiler/rustc_infer/messages.ftl
@@ -164,7 +164,10 @@ infer_label_bad = {$bad_kind ->
 infer_lf_bound_not_satisfied = lifetime bound not satisfied
 infer_lifetime_mismatch = lifetime mismatch
 
-infer_lifetime_param_suggestion = consider introducing a named lifetime parameter{$is_impl ->
+infer_lifetime_param_suggestion = consider {$is_reuse ->
+    [true] reusing
+    *[false] introducing
+} a named lifetime parameter{$is_impl ->
     [true] {" "}and update trait if needed
     *[false] {""}
 }
diff --git a/compiler/rustc_infer/src/errors/mod.rs b/compiler/rustc_infer/src/errors/mod.rs
index 2acaeac2439..8bb0dc39143 100644
--- a/compiler/rustc_infer/src/errors/mod.rs
+++ b/compiler/rustc_infer/src/errors/mod.rs
@@ -1,9 +1,11 @@
 use hir::GenericParamKind;
+use rustc_data_structures::fx::FxHashSet;
 use rustc_errors::{
     codes::*, Applicability, Diag, DiagMessage, DiagStyledString, EmissionGuarantee, IntoDiagArg,
     MultiSpan, SubdiagMessageOp, Subdiagnostic,
 };
 use rustc_hir as hir;
+use rustc_hir::intravisit::{walk_ty, Visitor};
 use rustc_hir::FnRetTy;
 use rustc_macros::{Diagnostic, Subdiagnostic};
 use rustc_middle::ty::print::TraitRefPrintOnlyTraitPath;
@@ -355,31 +357,33 @@ impl Subdiagnostic for AddLifetimeParamsSuggestion<'_> {
         _f: &F,
     ) {
         let mut mk_suggestion = || {
-            let (
-                hir::Ty { kind: hir::TyKind::Ref(lifetime_sub, _), .. },
-                hir::Ty { kind: hir::TyKind::Ref(lifetime_sup, _), .. },
-            ) = (self.ty_sub, self.ty_sup)
-            else {
-                return false;
-            };
-
-            if !lifetime_sub.is_anonymous() || !lifetime_sup.is_anonymous() {
-                return false;
-            };
-
             let Some(anon_reg) = self.tcx.is_suitable_region(self.sub) else {
                 return false;
             };
 
             let node = self.tcx.hir_node_by_def_id(anon_reg.def_id);
             let is_impl = matches!(&node, hir::Node::ImplItem(_));
-            let generics = match node {
+            let (generics, parent_generics) = match node {
                 hir::Node::Item(&hir::Item {
                     kind: hir::ItemKind::Fn(_, ref generics, ..),
                     ..
                 })
                 | hir::Node::TraitItem(&hir::TraitItem { ref generics, .. })
-                | hir::Node::ImplItem(&hir::ImplItem { ref generics, .. }) => generics,
+                | hir::Node::ImplItem(&hir::ImplItem { ref generics, .. }) => (
+                    generics,
+                    match self.tcx.parent_hir_node(self.tcx.local_def_id_to_hir_id(anon_reg.def_id))
+                    {
+                        hir::Node::Item(hir::Item {
+                            kind: hir::ItemKind::Trait(_, _, ref generics, ..),
+                            ..
+                        })
+                        | hir::Node::Item(hir::Item {
+                            kind: hir::ItemKind::Impl(hir::Impl { ref generics, .. }),
+                            ..
+                        }) => Some(generics),
+                        _ => None,
+                    },
+                ),
                 _ => return false,
             };
 
@@ -390,24 +394,112 @@ impl Subdiagnostic for AddLifetimeParamsSuggestion<'_> {
                 .map(|p| p.name.ident().name)
                 .find(|i| *i != kw::UnderscoreLifetime);
             let introduce_new = suggestion_param_name.is_none();
+
+            let mut default = "'a".to_string();
+            if let Some(parent_generics) = parent_generics {
+                let used: FxHashSet<_> = parent_generics
+                    .params
+                    .iter()
+                    .filter(|p| matches!(p.kind, GenericParamKind::Lifetime { .. }))
+                    .map(|p| p.name.ident().name)
+                    .filter(|i| *i != kw::UnderscoreLifetime)
+                    .map(|l| l.to_string())
+                    .collect();
+                if let Some(lt) =
+                    ('a'..='z').map(|it| format!("'{it}")).find(|it| !used.contains(it))
+                {
+                    // We want a lifetime that *isn't* present in the `trait` or `impl` that assoc
+                    // `fn` belongs to. We could suggest reusing one of their lifetimes, but it is
+                    // likely to be an over-constraining lifetime requirement, so we always add a
+                    // lifetime to the `fn`.
+                    default = lt;
+                }
+            }
             let suggestion_param_name =
-                suggestion_param_name.map(|n| n.to_string()).unwrap_or_else(|| "'a".to_owned());
-
-            debug!(?lifetime_sup.ident.span);
-            debug!(?lifetime_sub.ident.span);
-            let make_suggestion = |ident: Ident| {
-                let sugg = if ident.name == kw::Empty {
-                    format!("{suggestion_param_name}, ")
-                } else if ident.name == kw::UnderscoreLifetime && ident.span.is_empty() {
-                    format!("{suggestion_param_name} ")
-                } else {
-                    suggestion_param_name.clone()
-                };
-                (ident.span, sugg)
-            };
-            let mut suggestions =
-                vec![make_suggestion(lifetime_sub.ident), make_suggestion(lifetime_sup.ident)];
+                suggestion_param_name.map(|n| n.to_string()).unwrap_or_else(|| default);
+
+            struct ImplicitLifetimeFinder {
+                suggestions: Vec<(Span, String)>,
+                suggestion_param_name: String,
+            }
 
+            impl<'v> Visitor<'v> for ImplicitLifetimeFinder {
+                fn visit_ty(&mut self, ty: &'v hir::Ty<'v>) {
+                    let make_suggestion = |ident: Ident| {
+                        if ident.name == kw::Empty && ident.span.is_empty() {
+                            format!("{}, ", self.suggestion_param_name)
+                        } else if ident.name == kw::UnderscoreLifetime && ident.span.is_empty() {
+                            format!("{} ", self.suggestion_param_name)
+                        } else {
+                            self.suggestion_param_name.clone()
+                        }
+                    };
+                    match ty.kind {
+                        hir::TyKind::Path(hir::QPath::Resolved(_, path)) => {
+                            for segment in path.segments {
+                                if let Some(args) = segment.args {
+                                    if args.args.iter().all(|arg| {
+                                        matches!(
+                                            arg,
+                                            hir::GenericArg::Lifetime(lifetime)
+                                            if lifetime.ident.name == kw::Empty
+                                        )
+                                    }) {
+                                        self.suggestions.push((
+                                            segment.ident.span.shrink_to_hi(),
+                                            format!(
+                                                "<{}>",
+                                                args.args
+                                                    .iter()
+                                                    .map(|_| self.suggestion_param_name.clone())
+                                                    .collect::<Vec<_>>()
+                                                    .join(", ")
+                                            ),
+                                        ));
+                                    } else {
+                                        for arg in args.args {
+                                            if let hir::GenericArg::Lifetime(lifetime) = arg
+                                                && lifetime.is_anonymous()
+                                            {
+                                                self.suggestions.push((
+                                                    lifetime.ident.span,
+                                                    make_suggestion(lifetime.ident),
+                                                ));
+                                            }
+                                        }
+                                    }
+                                }
+                            }
+                        }
+                        hir::TyKind::Ref(lifetime, ..) if lifetime.is_anonymous() => {
+                            self.suggestions
+                                .push((lifetime.ident.span, make_suggestion(lifetime.ident)));
+                        }
+                        _ => {}
+                    }
+                    walk_ty(self, ty);
+                }
+            }
+            let mut visitor = ImplicitLifetimeFinder {
+                suggestions: vec![],
+                suggestion_param_name: suggestion_param_name.clone(),
+            };
+            if let Some(fn_decl) = node.fn_decl()
+                && let hir::FnRetTy::Return(ty) = fn_decl.output
+            {
+                visitor.visit_ty(ty);
+            }
+            if visitor.suggestions.is_empty() {
+                // Do not suggest constraining the `&self` param, but rather the return type.
+                // If that is wrong (because it is not sufficient), a follow up error will tell the
+                // user to fix it. This way we lower the chances of *over* constraining, but still
+                // get the cake of "correctly" contrained in two steps.
+                visitor.visit_ty(self.ty_sup);
+            }
+            visitor.visit_ty(self.ty_sub);
+            if visitor.suggestions.is_empty() {
+                return false;
+            }
             if introduce_new {
                 let new_param_suggestion = if let Some(first) =
                     generics.params.iter().find(|p| !p.name.ident().span.is_empty())
@@ -417,15 +509,16 @@ impl Subdiagnostic for AddLifetimeParamsSuggestion<'_> {
                     (generics.span, format!("<{suggestion_param_name}>"))
                 };
 
-                suggestions.push(new_param_suggestion);
+                visitor.suggestions.push(new_param_suggestion);
             }
-
-            diag.multipart_suggestion(
+            diag.multipart_suggestion_verbose(
                 fluent::infer_lifetime_param_suggestion,
-                suggestions,
+                visitor.suggestions,
                 Applicability::MaybeIncorrect,
             );
             diag.arg("is_impl", is_impl);
+            diag.arg("is_reuse", !introduce_new);
+
             true
         };
         if mk_suggestion() && self.add_note {