HRTBs: "implementation is not general enough", but it is

[comex]

Playground link

trait MyFn<'a> {}
impl<'a, F> MyFn<'a> for F where
    F: FnOnce(&'a i32) -> &'a i32 {}
    
fn foo<F>(f: F) where F: for<'a> MyFn<'a> {}
// This works:
// fn foo<F>(f: F) where F: for<'a> FnOnce(&'a i32) -> &'a i32 {}

fn main() {
    foo(|x: &i32| -> &i32 { x });
}

produces:

error: implementation of `MyFn` is not general enough
  --> src/main.rs:10:5
   |
1  | trait MyFn<'a> {}
   | ----------------- trait `MyFn` defined here
...
10 |     foo(|x: &i32| -> &i32 { x });
   |     ^^^ implementation of `MyFn` is not general enough
   |
   = note: `MyFn<'1>` would have to be implemented for the type `[closure@src/main.rs:10:9: 10:32]`, for any lifetime `'1`...
   = note: ...but `MyFn<'_>` is actually implemented for the type `[closure@src/main.rs:10:9: 10:32]`, for some specific lifetime `'2`

But clearly it actually is implemented for any lifetime.

[comex]

Update: This appears to only affect closures. It works with fns:

fn bar(x: &i32) -> &i32 { x }
foo(bar); // OK

as well as with a type that manually implements FnOnce:

struct Manual;
impl<'a> FnOnce<(&'a i32,)> for Manual {
    type Output = &'a i32;
    extern "rust-call" fn call_once(self, (x,): (&'a i32,)) -> &'a i32 { x }
}
foo(Manual); // OK

[comex]

In fact, we can make closures work by adding an extra bound:

trait MyFn<'a> {}
impl<'a, F> MyFn<'a> for F where
    F: FnOnce(&'a i32) -> &'a i32 {}

fn foo<F>(f: F) where
    F: for<'a> FnOnce(&'a i32) -> &'a i32, // <-- extra bound
    F: for<'a> MyFn<'a> {}

fn main() {
    foo(|x: &i32| -> &i32 { x }); // OK
}

On the other hand, if we instead add F: FnOnce(&'static i32) -> &'static i32, the error is still there. So the extra bound is presumably affecting how the type of the closure is inferred.

And if I add both extra bounds... I get a type error in the function definition!? Just filed that as #70290.

[Ekleog]

I've recently hit this issue with futures, where as far as I understand the proposed workaround cannot work because there is no way to write the extra bound.

The “idea” I'm trying to do is https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=71374a2f88a2650391dba9903c733ed5 (where I've replaced Future with Debug for ease of example): take as parameter a closure that returns a future capturing its arguments.

The best I could do to implement that without HKTs is https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=bef14e19fdf52d4df695f12ca493f8a1, which looks like it should work (like in this issue) ; but stops compiling as soon as a closure is used instead of a raw function.

[comex]

There's a way to make the workaround work by supplying the bound on the caller side. Based on your example:

// A function that just returns its argument, but serves as a type hint:
fn dummy<F>(f: F) -> F where F: for<'a> Fn(&'a u8) -> &'a u8 {
    f
}

// Doesn't work: foo(|x| x);
// Does work:
foo(dummy(|x| x));

This can be made a little less verbose by using a macro (and lifetime elision for good measure):

macro_rules! typed_closure {
    (($($bound:tt)*), $closure:expr) => { {
        fn _typed_closure_id<F>(f: F) -> F where F: $($bound)* { f }
        _typed_closure_id($closure)
    } }
}

foo(typed_closure!((Fn(&u8) -> &u8), |x| x));

Still, it is annoying that this is required.

[oberien]

This error doesn't only appear with closures, but also with function pointer types and Debug-derive. The following code results in a similar HRTB-based error (playground):

#[derive(Debug)]
enum Foo {
    Bar(fn(&())),
}

Error:

error: implementation of `std::fmt::Debug` is not general enough
   --> src/lib.rs:3:9
    |
3   |       Bar(fn(&())),
    |           ^^^^^^^ implementation of `std::fmt::Debug` is not general enough
    |
    = note: `std::fmt::Debug` would have to be implemented for the type `for<'r> fn(&'r ())`
    = note: ...but `std::fmt::Debug` is actually implemented for the type `fn(&'0 ())`, for some specific lifetime `'0`
    = note: this error originates in a derive macro (in Nightly builds, run with -Z macro-backtrace for more info)

[fleabitdev]

Possibly related, with a confusing error message:

trait MyTrait { }
impl<'a> MyTrait for &'a i32 { }

fn example<R: MyTrait, F: Fn(&i32) -> R>(_f: F) { }

fn main() {
    let func: fn(&i32) -> &i32 = |x| x;
    example(func);
}

error: implementation of `FnOnce` is not general enough
   --> src/main.rs:8:5
    |
8   |       example(func);
    |       ^^^^^^^ implementation of `FnOnce` is not general enough
    |
    = note: `FnOnce<(&'0 i32,)>` would have to be implemented for the type `for<'r> fn(&'r i32) -> &'r i32`, for some specific lifetime `'0`...
    = note: ...but `FnOnce<(&i32,)>` is actually implemented for the type `for<'r> fn(&'r i32) -> &'r i32`

This made it difficult to write a generic function which boxes and wraps a user-provided closure. I encountered the error whenever an HRTB constrained the closure's return value to have a lifetime matching one of its parameters. (The error still occurs if the R: MyTrait bound is removed.)

Adding a free lifetime parameter to the example function, and to MyTrait, suppresses the error. However, this isn't always possible; a free lifetime must accept all lifetimes, including 'static, so it will prevent F from being called with a reference to data constructed on the stack.

I did find a workaround, but it requires nightly. It exploits the fact that the type checker seems to be better at normalizing associated types in trait where-clauses rather than function where-clauses:

#![feature(unboxed_closures)]

trait MyTrait { }
impl<'a> MyTrait for &'a i32 { }

trait MyTraitOutput<Args>: Fn<Args> { }
impl<Args, F> MyTraitOutput<Args> for F
where
    F: Fn<Args>,
    <F as FnOnce<Args>>::Output: MyTrait
{ }

fn example<F: for<'a> Fn<(&'a i32,)>>(_f: F)
where
    F: for<'a> MyTraitOutput<(&'a i32,)>
{
    //call the closure and store its result. then, pass the result to methods on 
    //MyTraitOutput which forward to methods on MyTrait
}

[angelsl]

I think I'm running into this issue too, but I'm not too sure:

use std::future::Future;

struct A {}
struct B {}

async fn f<'a, G, Fut>(arg: &'a A, g: G)
where
    for<'b> G: Fn(&'a A, &'b B) -> Fut,
    Fut: Future<Output = String> + 'a,
{
    let b = B {};
    let ans = g(arg, &b).await;
}

fn main() {
    f(&A {}, async_func);
}

async fn async_func(a: &A, b: &B) -> String {
    "test".to_owned()
}

This produces:

error: implementation of `FnOnce` is not general enough
   --> src/main.rs:16:5
    |
16  |       f(&A {}, async_func);
    |       ^ implementation of `FnOnce` is not general enough
    |
    = note: `FnOnce<(&A, &'0 B)>` would have to be implemented for the type `for<'_, '_> fn(&A, &B) -> impl Future {async_func}`, for some specific lifetime `'0`...
    = note: ...but `FnOnce<(&A, &'b B)>` is actually implemented for the type `for<'_, '_> fn(&A, &B) -> impl Future {async_func}`

error: aborting due to previous error

error: could not compile `playground`