Account for missing lifetime in opaque return type

When encountering an opaque closure return type that needs to bound a
lifetime to the function's arguments, including borrows and type params,
provide appropriate suggestions that lead to working code.

Get the user from

```rust
fn foo<G, T>(g: G, dest: &mut T) -> impl FnOnce()
where
    G: Get<T>
{
    move || {
        *dest = g.get();
    }
}
```

to

```rust
fn foo<'a, G: 'a, T>(g: G, dest: &'a mut T) -> impl FnOnce() +'a
where
    G: Get<T>
{
    move || {
        *dest = g.get();
    }
}
```

5 files changed, 359 insertions, 69 deletions

diff --git a/src/librustc_infer/infer/error_reporting/mod.rs b/src/librustc_infer/infer/error_reporting/mod.rs
index ae901982817..3b98d47778f 100644
--- a/src/librustc_infer/infer/error_reporting/mod.rs
+++ b/src/librustc_infer/infer/error_reporting/mod.rs
@@ -1682,49 +1682,70 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         bound_kind: GenericKind<'tcx>,
         sub: Region<'tcx>,
     ) -> DiagnosticBuilder<'a> {
+        let hir = &self.tcx.hir();
         // Attempt to obtain the span of the parameter so we can
         // suggest adding an explicit lifetime bound to it.
-        let type_param_span = match (self.in_progress_tables, bound_kind) {
-            (Some(ref table), GenericKind::Param(ref param)) => {
-                let table_owner = table.borrow().hir_owner;
-                table_owner.and_then(|table_owner| {
-                    let generics = self.tcx.generics_of(table_owner.to_def_id());
-                    // Account for the case where `param` corresponds to `Self`,
-                    // which doesn't have the expected type argument.
-                    if !(generics.has_self && param.index == 0) {
-                        let type_param = generics.type_param(param, self.tcx);
-                        let hir = &self.tcx.hir();
-                        type_param.def_id.as_local().map(|def_id| {
-                            // Get the `hir::Param` to verify whether it already has any bounds.
-                            // We do this to avoid suggesting code that ends up as `T: 'a'b`,
-                            // instead we suggest `T: 'a + 'b` in that case.
-                            let id = hir.as_local_hir_id(def_id);
-                            let mut has_bounds = false;
-                            if let Node::GenericParam(param) = hir.get(id) {
-                                has_bounds = !param.bounds.is_empty();
-                            }
-                            let sp = hir.span(id);
-                            // `sp` only covers `T`, change it so that it covers
-                            // `T:` when appropriate
-                            let is_impl_trait = bound_kind.to_string().starts_with("impl ");
-                            let sp = if has_bounds && !is_impl_trait {
-                                sp.to(self
-                                    .tcx
-                                    .sess
-                                    .source_map()
-                                    .next_point(self.tcx.sess.source_map().next_point(sp)))
-                            } else {
-                                sp
-                            };
-                            (sp, has_bounds, is_impl_trait)
-                        })
-                    } else {
-                        None
-                    }
-                })
+        let generics = self
+            .in_progress_tables
+            .and_then(|table| table.borrow().hir_owner)
+            .map(|table_owner| self.tcx.generics_of(table_owner.to_def_id()));
+        let type_param_span = match (generics, bound_kind) {
+            (Some(ref generics), GenericKind::Param(ref param)) => {
+                // Account for the case where `param` corresponds to `Self`,
+                // which doesn't have the expected type argument.
+                if !(generics.has_self && param.index == 0) {
+                    let type_param = generics.type_param(param, self.tcx);
+                    type_param.def_id.as_local().map(|def_id| {
+                        // Get the `hir::Param` to verify whether it already has any bounds.
+                        // We do this to avoid suggesting code that ends up as `T: 'a'b`,
+                        // instead we suggest `T: 'a + 'b` in that case.
+                        let id = hir.as_local_hir_id(def_id);
+                        let mut has_bounds = false;
+                        if let Node::GenericParam(param) = hir.get(id) {
+                            has_bounds = !param.bounds.is_empty();
+                        }
+                        let sp = hir.span(id);
+                        // `sp` only covers `T`, change it so that it covers
+                        // `T:` when appropriate
+                        let is_impl_trait = bound_kind.to_string().starts_with("impl ");
+                        let sp = if has_bounds && !is_impl_trait {
+                            sp.to(self
+                                .tcx
+                                .sess
+                                .source_map()
+                                .next_point(self.tcx.sess.source_map().next_point(sp)))
+                        } else {
+                            sp
+                        };
+                        (sp, has_bounds, is_impl_trait)
+                    })
+                } else {
+                    None
+                }
             }
             _ => None,
         };
+        let new_lt = generics
+            .as_ref()
+            .and_then(|g| {
+                let possible = ["'a", "'b", "'c", "'d", "'e", "'f", "'g", "'h", "'i", "'j", "'k"];
+                let lts_names = g
+                    .params
+                    .iter()
+                    .filter(|p| matches!(p.kind, ty::GenericParamDefKind::Lifetime))
+                    .map(|p| p.name.as_str())
+                    .collect::<Vec<_>>();
+                let lts = lts_names.iter().map(|s| -> &str { &*s }).collect::<Vec<_>>();
+                possible.iter().filter(|&candidate| !lts.contains(&*candidate)).next().map(|s| *s)
+            })
+            .unwrap_or("'lt");
+        let add_lt_sugg = generics
+            .as_ref()
+            .and_then(|g| g.params.first())
+            .and_then(|param| param.def_id.as_local())
+            .map(|def_id| {
+                (hir.span(hir.as_local_hir_id(def_id)).shrink_to_lo(), format!("{}, ", new_lt))
+            });
 
         let labeled_user_string = match bound_kind {
             GenericKind::Param(ref p) => format!("the parameter type `{}`", p),
@@ -1781,6 +1802,30 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
             }
         }
 
+        let new_binding_suggestion =
+            |err: &mut DiagnosticBuilder<'tcx>,
+             type_param_span: Option<(Span, bool, bool)>,
+             bound_kind: GenericKind<'tcx>| {
+                let msg = "consider introducing an explicit lifetime bound to unify the type \
+                    parameter and the output";
+                if let Some((sp, has_lifetimes, is_impl_trait)) = type_param_span {
+                    let suggestion = if is_impl_trait {
+                        (sp.shrink_to_hi(), format!(" + {}", new_lt))
+                    } else {
+                        let tail = if has_lifetimes { " +" } else { "" };
+                        (sp, format!("{}: {}{}", bound_kind, new_lt, tail))
+                    };
+                    let mut sugg =
+                        vec![suggestion, (span.shrink_to_hi(), format!(" + {}", new_lt))];
+                    if let Some(lt) = add_lt_sugg {
+                        sugg.push(lt);
+                        sugg.rotate_right(1);
+                    }
+                    // `MaybeIncorrect` due to issue #41966.
+                    err.multipart_suggestion(msg, sugg, Applicability::MaybeIncorrect);
+                }
+            };
+
         let mut err = match *sub {
             ty::ReEarlyBound(ty::EarlyBoundRegion { name, .. })
             | ty::ReFree(ty::FreeRegion { bound_region: ty::BrNamed(_, name), .. }) => {
@@ -1822,10 +1867,6 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                     "{} may not live long enough",
                     labeled_user_string
                 );
-                err.help(&format!(
-                    "consider adding an explicit lifetime bound for `{}`",
-                    bound_kind
-                ));
                 note_and_explain_region(
                     self.tcx,
                     &mut err,
@@ -1833,6 +1874,21 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                     sub,
                     "...",
                 );
+                if let Some(infer::RelateParamBound(_, t)) = origin {
+                    let t = self.resolve_vars_if_possible(&t);
+                    match t.kind {
+                        // We've got:
+                        // fn get_later<G, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+                        // suggest:
+                        // fn get_later<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ + 'a
+                        ty::Closure(_, _substs) | ty::Opaque(_, _substs) => {
+                            new_binding_suggestion(&mut err, type_param_span, bound_kind);
+                        }
+                        _ => {
+                            binding_suggestion(&mut err, type_param_span, bound_kind, new_lt);
+                        }
+                    }
+                }
                 err
             }
         };
diff --git a/src/librustc_infer/infer/error_reporting/nice_region_error/static_impl_trait.rs b/src/librustc_infer/infer/error_reporting/nice_region_error/static_impl_trait.rs
index 7f3ec852e41..4ad587db012 100644
--- a/src/librustc_infer/infer/error_reporting/nice_region_error/static_impl_trait.rs
+++ b/src/librustc_infer/infer/error_reporting/nice_region_error/static_impl_trait.rs
@@ -4,7 +4,7 @@ use crate::infer::error_reporting::msg_span_from_free_region;
 use crate::infer::error_reporting::nice_region_error::NiceRegionError;
 use crate::infer::lexical_region_resolve::RegionResolutionError;
 use rustc_errors::{Applicability, ErrorReported};
-use rustc_middle::ty::{BoundRegion, FreeRegion, RegionKind};
+use rustc_middle::ty::RegionKind;
 
 impl<'a, 'tcx> NiceRegionError<'a, 'tcx> {
     /// Print the error message for lifetime errors when the return type is a static impl Trait.
@@ -37,13 +37,8 @@ impl<'a, 'tcx> NiceRegionError<'a, 'tcx> {
                         err.span_note(lifetime_sp, &format!("...can't outlive {}", lifetime));
                     }
 
-                    let lifetime_name = match sup_r {
-                        RegionKind::ReFree(FreeRegion {
-                            bound_region: BoundRegion::BrNamed(_, ref name),
-                            ..
-                        }) => name.to_string(),
-                        _ => "'_".to_owned(),
-                    };
+                    let lifetime_name =
+                        if sup_r.has_name() { sup_r.to_string() } else { "'_".to_owned() };
                     let fn_return_span = return_ty.unwrap().1;
                     if let Ok(snippet) =
                         self.tcx().sess.source_map().span_to_snippet(fn_return_span)
@@ -54,9 +49,9 @@ impl<'a, 'tcx> NiceRegionError<'a, 'tcx> {
                             err.span_suggestion(
                                 fn_return_span,
                                 &format!(
-                                    "you can add a bound to the return type to make it last \
-                                 less than `'static` and match {}",
-                                    lifetime,
+                                    "you can add a bound to the return type to make it last less \
+                                     than `'static` and match {}",
+                                    lifetime
                                 ),
                                 format!("{} + {}", snippet, lifetime_name),
                                 Applicability::Unspecified,
diff --git a/src/librustc_infer/infer/error_reporting/note.rs b/src/librustc_infer/infer/error_reporting/note.rs
index 8fbb89da5af..968c488bc00 100644
--- a/src/librustc_infer/infer/error_reporting/note.rs
+++ b/src/librustc_infer/infer/error_reporting/note.rs
@@ -56,8 +56,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                 err.span_note(
                     span,
                     &format!(
-                        "...so that the reference type `{}` does not outlive the \
-                                        data it points at",
+                        "...so that the reference type `{}` does not outlive the data it points at",
                         self.ty_to_string(ty)
                     ),
                 );
@@ -66,8 +65,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                 err.span_note(
                     span,
                     &format!(
-                        "...so that the type `{}` will meet its required \
-                                        lifetime bounds",
+                        "...so that the type `{}` will meet its required lifetime bounds",
                         self.ty_to_string(t)
                     ),
                 );
@@ -81,8 +79,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
             infer::CompareImplMethodObligation { span, .. } => {
                 err.span_note(
                     span,
-                    "...so that the definition in impl matches the definition from the \
-                               trait",
+                    "...so that the definition in impl matches the definition from the trait",
                 );
             }
         }
@@ -113,8 +110,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                     self.tcx.sess,
                     span,
                     E0312,
-                    "lifetime of reference outlives lifetime of \
-                                                borrowed content..."
+                    "lifetime of reference outlives lifetime of borrowed content..."
                 );
                 note_and_explain_region(
                     self.tcx,
@@ -138,8 +134,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                     self.tcx.sess,
                     span,
                     E0313,
-                    "lifetime of borrowed pointer outlives lifetime \
-                                                of captured variable `{}`...",
+                    "lifetime of borrowed pointer outlives lifetime of captured variable `{}`...",
                     var_name
                 );
                 note_and_explain_region(
@@ -163,8 +158,8 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                     self.tcx.sess,
                     span,
                     E0476,
-                    "lifetime of the source pointer does not outlive \
-                                                lifetime bound of the object type"
+                    "lifetime of the source pointer does not outlive lifetime bound of the \
+                     object type"
                 );
                 note_and_explain_region(self.tcx, &mut err, "object type is valid for ", sub, "");
                 note_and_explain_region(
@@ -181,8 +176,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                     self.tcx.sess,
                     span,
                     E0477,
-                    "the type `{}` does not fulfill the required \
-                                                lifetime",
+                    "the type `{}` does not fulfill the required lifetime",
                     self.ty_to_string(ty)
                 );
                 match *sub {
@@ -217,8 +211,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                     self.tcx.sess,
                     span,
                     E0482,
-                    "lifetime of return value does not outlive the \
-                                                function call"
+                    "lifetime of return value does not outlive the function call"
                 );
                 note_and_explain_region(
                     self.tcx,
diff --git a/src/test/ui/suggestions/lifetimes/missing-lifetimes-in-signature.rs b/src/test/ui/suggestions/lifetimes/missing-lifetimes-in-signature.rs
new file mode 100644
index 00000000000..b5f6fdeaa4e
--- /dev/null
+++ b/src/test/ui/suggestions/lifetimes/missing-lifetimes-in-signature.rs
@@ -0,0 +1,100 @@
+pub trait Get<T> {
+    fn get(self) -> T;
+}
+
+struct Foo {
+    x: usize,
+}
+
+impl Get<usize> for Foo {
+    fn get(self) -> usize {
+        self.x
+    }
+}
+
+fn foo<G, T>(g: G, dest: &mut T) -> impl FnOnce()
+where
+    G: Get<T>
+{
+    move || { //~ ERROR cannot infer an appropriate lifetime
+        *dest = g.get();
+    }
+}
+
+// After applying suggestion for `foo`:
+fn bar<G, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+//~^ ERROR the parameter type `G` may not live long enough
+where
+    G: Get<T>
+{
+    move || {
+        *dest = g.get();
+    }
+}
+
+
+// After applying suggestion for `bar`:
+fn baz<G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ //~ ERROR undeclared lifetime
+where
+    G: Get<T>
+{
+    move || {
+        *dest = g.get();
+    }
+}
+
+// After applying suggestion for `baz`:
+fn qux<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+//~^ ERROR the parameter type `G` may not live long enough
+where
+    G: Get<T>
+{
+    move || {
+        *dest = g.get();
+    }
+}
+
+// After applying suggestion for `qux`:
+// FIXME: we should suggest be suggesting to change `dest` to `&'a mut T`.
+fn bat<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ + 'a
+where
+    G: Get<T>
+{
+    move || { //~ ERROR cannot infer an appropriate lifetime
+        *dest = g.get();
+    }
+}
+
+// Potential incorrect attempt:
+fn bak<'a, G, T>(g: G, dest: &'a mut T) -> impl FnOnce() + 'a
+//~^ ERROR the parameter type `G` may not live long enough
+where
+    G: Get<T>
+{
+    move || {
+        *dest = g.get();
+    }
+}
+
+
+// We need to tie the lifetime of `G` with the lifetime of `&mut T` and the returned closure:
+fn ok<'a, G: 'a, T>(g: G, dest: &'a mut T) -> impl FnOnce() + 'a
+where
+    G: Get<T>
+{
+    move || {
+        *dest = g.get();
+    }
+}
+
+// This also works. The `'_` isn't necessary but it's where we arrive to following the suggestions:
+fn ok2<'a, G: 'a, T>(g: G, dest: &'a mut T) -> impl FnOnce() + '_ + 'a
+where
+    G: Get<T>
+{
+    move || {
+        *dest = g.get();
+    }
+}
+
+fn main() {}
diff --git a/src/test/ui/suggestions/lifetimes/missing-lifetimes-in-signature.stderr b/src/test/ui/suggestions/lifetimes/missing-lifetimes-in-signature.stderr
new file mode 100644
index 00000000000..d69db90f3ba
--- /dev/null
+++ b/src/test/ui/suggestions/lifetimes/missing-lifetimes-in-signature.stderr
@@ -0,0 +1,146 @@
+error[E0261]: use of undeclared lifetime name `'a`
+  --> $DIR/missing-lifetimes-in-signature.rs:37:11
+   |
+LL | fn baz<G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+   |        -  ^^ undeclared lifetime
+   |        |
+   |        help: consider introducing lifetime `'a` here: `'a,`
+
+error: cannot infer an appropriate lifetime
+  --> $DIR/missing-lifetimes-in-signature.rs:19:5
+   |
+LL |   fn foo<G, T>(g: G, dest: &mut T) -> impl FnOnce()
+   |                                       ------------- this return type evaluates to the `'static` lifetime...
+...
+LL | /     move || {
+LL | |         *dest = g.get();
+LL | |     }
+   | |_____^ ...but this borrow...
+   |
+note: ...can't outlive the anonymous lifetime #1 defined on the function body at 15:1
+  --> $DIR/missing-lifetimes-in-signature.rs:15:1
+   |
+LL | / fn foo<G, T>(g: G, dest: &mut T) -> impl FnOnce()
+LL | | where
+LL | |     G: Get<T>
+LL | | {
+...  |
+LL | |     }
+LL | | }
+   | |_^
+help: you can add a bound to the return type to make it last less than `'static` and match the anonymous lifetime #1 defined on the function body at 15:1
+   |
+LL | fn foo<G, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+   |                                     ^^^^^^^^^^^^^^^^^^
+
+error[E0311]: the parameter type `G` may not live long enough
+  --> $DIR/missing-lifetimes-in-signature.rs:25:37
+   |
+LL | fn bar<G, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+   |                                     ^^^^^^^^^^^^^^^^^^
+   |
+note: the parameter type `G` must be valid for the anonymous lifetime #1 defined on the function body at 25:1...
+  --> $DIR/missing-lifetimes-in-signature.rs:25:1
+   |
+LL | / fn bar<G, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+LL | |
+LL | | where
+LL | |     G: Get<T>
+...  |
+LL | |     }
+LL | | }
+   | |_^
+note: ...so that the type `[closure@$DIR/missing-lifetimes-in-signature.rs:30:5: 32:6 g:G, dest:&mut T]` will meet its required lifetime bounds
+  --> $DIR/missing-lifetimes-in-signature.rs:25:37
+   |
+LL | fn bar<G, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+   |                                     ^^^^^^^^^^^^^^^^^^
+help: consider introducing an explicit lifetime bound to unify the type parameter and the output
+   |
+LL | fn bar<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ + 'a
+   |        ^^^^^                                                   ^^^^
+
+error[E0311]: the parameter type `G` may not live long enough
+  --> $DIR/missing-lifetimes-in-signature.rs:47:45
+   |
+LL | fn qux<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+   |                                             ^^^^^^^^^^^^^^^^^^
+   |
+note: the parameter type `G` must be valid for the anonymous lifetime #1 defined on the function body at 47:1...
+  --> $DIR/missing-lifetimes-in-signature.rs:47:1
+   |
+LL | / fn qux<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+LL | |
+LL | | where
+LL | |     G: Get<T>
+...  |
+LL | |     }
+LL | | }
+   | |_^
+note: ...so that the type `[closure@$DIR/missing-lifetimes-in-signature.rs:52:5: 54:6 g:G, dest:&mut T]` will meet its required lifetime bounds
+  --> $DIR/missing-lifetimes-in-signature.rs:47:45
+   |
+LL | fn qux<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_
+   |                                             ^^^^^^^^^^^^^^^^^^
+help: consider introducing an explicit lifetime bound to unify the type parameter and the output
+   |
+LL | fn qux<'b, 'a, G: 'b + 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ + 'b
+   |        ^^^     ^^^^^^^                                                  ^^^^
+
+error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
+  --> $DIR/missing-lifetimes-in-signature.rs:63:5
+   |
+LL | /     move || {
+LL | |         *dest = g.get();
+LL | |     }
+   | |_____^
+   |
+note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the function body at 59:1...
+  --> $DIR/missing-lifetimes-in-signature.rs:59:1
+   |
+LL | / fn bat<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ + 'a
+LL | | where
+LL | |     G: Get<T>
+LL | | {
+...  |
+LL | |     }
+LL | | }
+   | |_^
+note: ...so that the types are compatible
+  --> $DIR/missing-lifetimes-in-signature.rs:63:5
+   |
+LL | /     move || {
+LL | |         *dest = g.get();
+LL | |     }
+   | |_____^
+   = note: expected  `&mut T`
+              found  `&mut T`
+note: but, the lifetime must be valid for the lifetime `'a` as defined on the function body at 59:8...
+  --> $DIR/missing-lifetimes-in-signature.rs:59:8
+   |
+LL | fn bat<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ + 'a
+   |        ^^
+note: ...so that return value is valid for the call
+  --> $DIR/missing-lifetimes-in-signature.rs:59:45
+   |
+LL | fn bat<'a, G: 'a, T>(g: G, dest: &mut T) -> impl FnOnce() + '_ + 'a
+   |                                             ^^^^^^^^^^^^^^^^^^^^^^^
+
+error[E0309]: the parameter type `G` may not live long enough
+  --> $DIR/missing-lifetimes-in-signature.rs:69:44
+   |
+LL | fn bak<'a, G, T>(g: G, dest: &'a mut T) -> impl FnOnce() + 'a
+   |            -                               ^^^^^^^^^^^^^^^^^^
+   |            |
+   |            help: consider adding an explicit lifetime bound...: `G: 'a`
+   |
+note: ...so that the type `[closure@$DIR/missing-lifetimes-in-signature.rs:74:5: 76:6 g:G, dest:&mut T]` will meet its required lifetime bounds
+  --> $DIR/missing-lifetimes-in-signature.rs:69:44
+   |
+LL | fn bak<'a, G, T>(g: G, dest: &'a mut T) -> impl FnOnce() + 'a
+   |                                            ^^^^^^^^^^^^^^^^^^
+
+error: aborting due to 6 previous errors
+
+Some errors have detailed explanations: E0261, E0309, E0495.
+For more information about an error, try `rustc --explain E0261`.