Why can `async_fn_traits` bypass the issue of the high-ranked lifetime in `Future`?

[xmh0511]

fn test_lifetime<F,U>(_:F) where F: for<'l> Fn(&'l str)->U{}

async fn ashow(_:& str){}
fn main(){
   test_lifetime(ashow);
}

For this example, the compiler will report some errors:

one type is more general than the other

As said in this answers, the type parameter U can only be resolved to a single type. In contrast, the returned type of ashow, saying OpaqueFuture<&'l str>, denotes an infinite type for every lifetime. So, the type parameter U cannot be resolved from OpaqueFuture<&'l str>.

However, I don't know why async_fn_traits can bypass this issue. I simplified its implementation as the following:

use std::future::Future;

trait MyFuture<T>{
    type OutputFuture;
    type Output;
}

impl<F,Fut,T> MyFuture<T> for F // #1
where F: Fn(T)->Fut,  
Fut:Future
{
    type OutputFuture = Fut;
    type Output = Fut::Output;
}

fn test_lifetime<F>(_:F) where F: for<'l> MyFuture<&'l str>{}

async fn ashow(_:& str){}
fn main(){
   test_lifetime(ashow);
}

First, with the trait bound for<'l> MyFuture<&'l str>, the type parameter T in the item at #1 is explicitly specified as &'l str, and &'l str is an infinite type for every lifetime 'l, why does the type parameter T can be specified as such an infinite type?

Second, resembling the U in the first example, why can the type parameter Fut in the item can be resolved to the infinite type OpaqueFuture<&'l str> but U cannot?

[quinedot]

The problem with

<F, Fut> where F: FnMut(&str) -> Fut

Is that Fut is a single type and this is resolved outside of the for<'any> binder, as in predicate logic.

Exists<a specific Fut> such that ForAll<'a> F: FnMut(&'a str) -> Fut

The &'a str argument can't escape the binder that introduces the lifetime; Fut can't vary underneath the binder.

Whereas with

<F> where F: for<'l> MyFuture<&'l str>

The return type is not bound to a specific type outside the binder. Implicitly the associated type exists... underneath the binder as an output of the implementation.

ForAll<'a> F: MyFuture<&'l str> such that
    Exists<a specific Fut, Out> such that
        Fut: Future<Output = Out>,
        <F as MyFuture<&'l str>>::OutputFuture = Fut,
        <F as MyFuture<&'l str>>::Output = Out,
        F: Fn(&'l str) -> Fut

---

The implementation of ashow is roughly^[1]

impl<'a> FnMut<('a str,)> for fn#ashow {
    type Output = SomeFuture<'a>; // Future Output = ()
    fn call_mut(&mut self, args: (&'a str,)) -> Self::Output {
        async move { let args = args; }
    }
}

Because of how the Fn types are defined, the output is always a single type within the implementation. Higher-rank bounds have to apply despite this in all cases. It's nothing async specific. All higher-ranked functions have an implementation defining the output type as a non-generic associated type.

The rub with writing the bounds is that Fn traits bounds force you to name the return type, even though it's an associated type, but futures are unnameable. And generic type parameters are the wrong tool for the job because they are a single type outside the binder (for<'a>).

The async_fn_traits are just rebuilding the Fn traits (along with some domain specific desired bounds on the return type) from the ground up in such a way that you don't have to name the return type. Thus the return types (associated types) are able to rely on lifetimes introduced in the binder (for<'a>).

It works the same way when people want a generic bound that can express functions that can borrow in a variety of ways (e.g. could be a reference or could be something else, and thus a generic type parameter is the wrong tool for the job), even when they have nothing to do with async.

So if you understand how this can work, you should understand how async_fn_traits works.

---

1. I'm taking shortcuts ↩︎

[xmh0511]

Frankly, It's a bit hard to understand. I'm not sure I 100% understand your answers, I tried to talk about my understanding in my way, inspired by this answer. For the first example, because the type parameter U must be resolved to a specific type when the function is called, whereas the purpose of the Higher-ranked trait bounds is late binding, in other words, late binding means the introduced type/lifetime parameter in it is not resolved when the contained item is instantiated, all of them are resolved in the context where the associated entity is used.

By this logic, the type parameter U that is introduced in test_lifetime will be resolved once test_lifetime is called, however, the late binding F: for<'l> Fn(&'l str)->U means the lifetime 'l is resolved in the subsequent context, however, in the context of resolving U, the lifetime 'l means all lifetimes and that specific U cannot vary with 'l to denote ReturnedFuture<&'l str> for any lifetime.

For the second example, MyFuture does not use any type parameter introduced in test_lifetime, which means, the type parameters introduced in the implementation of MyFuture are all resolved in the late binding context, together with lifetime 'l introduced in for<'l>(the compiler checks the trait bound F: for <'l> MyFuture<&'l str>, which uses the generic implementation), in other words, all type parameters introduced in the implementation of MyFuture are associated with the high-ranked lifetime 'l, they can be varied with 'l.

Is my understanding right?

[quinedot]

@xmh0511

For the second example, MyFuture does not use any type parameter introduced in test_lifetime, which means, the type parameters introduced in the implementation of MyFuture are all resolved in the late binding context, together with lifetime 'l introduced in for<'l>(the compiler checks the trait bound F: for <'l> MyFuture<&'l str>, which uses the generic implementation),

Yes, I think you understand the fundamentals.

@xmh0511

in other words, all type parameters introduced in the implementation of MyFuture are associated with the high-ranked lifetime 'l, they can be varied with 'l.

They are introduced in a context where 'l exists, so they can depend on 'l. They don't have to, but they can.

Whereas in the failing example, U is introduced outside of the context of 'l and thus cannot depend on 'l.

---

Let me try once more with the logic based approach. These mean different things:

• "There is some food that everybody eats"
  • Exists<F: Food> such that ForAll<P: Person> [ P eats F ]
• "Everybody eats some food"
  • ForAll<P: Person> Exists<F: Food> such that [ P eats F ]

You want the latter: For every input, there exists an output future. You don't want: There exists a (single) future that's the output for every input. async_fn_traits exists because there's no direct way to ask for the latter.

// We can express this one directly today... but it doesn't
// mean what you want.
Exists<U> ForAll<'l> F: Fn(&'l str) -> U

fn test_lifetime<F,U>(_:F) where for<'l> F: Fn(&'l str) -> U {}

// This is the version you want, but we have to express the bound
// indirectly
ForAll<'l> Exists<U> F: Fn(&'l str) -> U

fn test_lifetime<F>(_:F) where for<'l> F: MyFuture<&'l str> {}

// Desugared supertrait bound:
// for<'l> F: Fn(&'l str) -> <F as MyFuture<&'l str>>::OutputFuture

We can imagine extensions to the language that do let us express this directly...

//                vvvvvvvvvvvvvvvvvvvvvvv `Ret` can rely on `'l`
<F> where for<'l> exists<Ret: Future<..>> F: Fn(&'l str) -> Ret

//  vvvvvv "generic type constructors" in addition to generic types
<F, Ret<*>> for<'l> F: Fn(&'l str) -> Ret<'l>

// Opaque existentials in bounds
<F> for<'l> Fn(&'l str) -> impl use<'l> Future<Output = ()>

// Stabilize the `Fn` traits...
<F> for<'l> Fn(&'l str, Output: Future<Output = ()>>)

...and what they all have in common is that they let you introduce some type beneath the binder so that it can rely on the lifetime introduced in the binder.

They let you write "ForAll Exists" bounds in addition to the "Exists ForAll" bounds which are more natural to write today.

[xmh0511]

@quinedot

They are introduced in a context where 'l exists, so they can depend on 'l. They don't have to, but they can.

Whereas in the failing example, U is introduced outside of the context of 'l and thus cannot depend on 'l.

I think it may be a simple way to conclude their difference: If a type parameter U is not introduced in a late binding context(as far as now, Rust does not have for<U>), the U is never considered a type parameter in the view of the late binding context, instead, U is a specific type that is instantiated in the signature where the late binding appears.

---

I have a question for the higher-ranked trait bound F: for<'l> MyFuture<&'l str>, does it mean, for the type F, the compiler checks whether there exists a corresponding implementation of trait MyFuture for every lifetime?

And the boilerplate

impl<F,Fut,T> MyFuture<T> for F // #1
where F: Fn(T)->Fut,  
Fut:Future {
    // ...
   // fn invoke(self, t:T){self(t);}
}

can supply that, for every type T, we implement MyFuture for the type F, since different lifetimes in &'l str form distinct types, hence with every lifetime, we finally have an infinite amount of implementations of MyFuture for F such that F: for<'l> MyFuture<&'l str> is true.

However, once we use F, for example

fn test_lifetime<F>(f:F) where F: for<'l> MyFuture<&'l str>{
    let s:&'static str = "ABC";
    MyFuture::invoke(f, s); //#2
}

The compiler will select one appropriate implementation with a specific lifetime(for example, 'static) in the infinite set produced by the boilerplate to be used at #2. The lifetime parameter denotes a specific lifetime within the selected implementation.

---

If my above understanding is right, then the reason for why fn test_lifetime<F>(_:F) where F: for<'l> MyFuture<&'l str>{} does work is that when the compiler checking the trait bound F: for<'l> MyFuture<&'l str>{}, the boilerplate can produce a corresponding implementation for every lifetime 'l, hence for every lifetime 'l, we can have a corresponding T and Fut in this context, in other words, when a generic implementation is used in the late binding context, all the type parameter introduced in that generic implementation are type parameters in the view of late binding as if they were introduced like for<T, Fut> .

[quinedot]

@xmh0511

I think it may be a simple way to conclude their difference: If a type parameter U is not introduced in a late binding context(as far as now, Rust does not have for), the U is never considered a type parameter in the view of the late binding context, instead, U is a specific type that is instantiated in the signature where the late binding appears.

Sounds correct to me.

@xmh0511

I have a question for the higher-ranked trait bound F: for<'l> MyFuture<&'l str>, does it mean, for the type F, the compiler checks whether there exists a corresponding implementation of trait MyFuture for every lifetime?

I think this is basically getting back to this comment and other parts of that thread -- how does the compiler actually check higher-ranked bounds?

Query: Does SomeFn: for<'l> MyFuture<&'l str>
  Use placeholder '0
  Query: Does SomeFn: MyFuture<&'0 str>
    Candidate: impl<F, Fut, T> MyFuture<T> for F
    Matches with F=SomeFn, T=&'0 str, Fut=CompilerGenerated<'0>
      SomeFn: Fn(&'0 str) -> CompilerGenerated<'0> -- yes
      CompilerGenerated<'0>: Future -- yes
    Plug holes
      for<'a> SomeFn: Fn(&'a str) -> CompilerGenerated<'a> -- yes
      for<'a> CompilerGenerated<'a>: Future -- yes

Perhaps one way to think of it -- the compiler eventually checks the explicit bounds you can't write due to, e.g., the lack of generic type constructors.

An example I think I deleted from a previous draft for context.

// We can't write
fn check<F>(_: F)
where
    F: Fn(&str) -> &str OR F: Fn(&str) -> NonRef<'_>
    //                  ^^

// So instead we have an indirect workaround
//          vvvvvvvvvvvvvvvvvvvvvvvvvvvv
fn check<F: for<'a> MaybeBorrow<&'a str>>(_: F) {}

// But once it has enough context, the compiler eventually does
// check one of
F: Fn(&str) -> &str
// OR
F: Fn(&str) -> NonRef<'_>
// OR ... some other borrowing signature

// In order to confirm the supertrait bound

@xmh0511

the boilerplate can produce a corresponding implementation for every lifetime 'l, hence for every lifetime 'l, we can have a corresponding T and Fut in this context,

Yes, that's the idea.

@xmh0511

in other words, when a generic implementation is used in the late binding context, all the type parameter introduced in that generic implementation are type parameters in the view of late binding as if they were introduced like for<T, Fut> .

Hmmm.... this is an interesting idea / mental model! I would have to play with it and compare/contrast with the "plug holes" concept I looked up in the compiler guide to see how well they match up. But I think you may be on to something here.

[xmh0511]

@quinedot

I think this is basically getting back to this comment and other parts of that thread -- how does the compiler actually check higher-ranked bounds?

After reading the linked comment and together with this post, a higher-ranked trait bound, for example, for<'a> F:Trait<'a> seems to require that there exists a higher-ranked implementation for the specific type F, so the crucial is what a higher-ranked implementation is, I think, a trait bound like T:'a in the implementation does not limit that 'a is a higher-ranked lifetime, instead, if that lifetime parameter is used to construct the implementing type F, the lifetime is not higher-ranked because F is a single specific type with a particular lifetime, which limits what lifetime parameter can be.

So, in my current mental model, I think the compiler checks the higher-ranked trait bound as if it would only need to look up whether a higher-ranked implementation of the implemented trait existed for the implementing type, and if the implementation exists and the further trait bounds in the implementation that will impose on that implementing type are true, the check is successful, which is shown likes the Explict example in your comment.

---

BTW, I don't know the reason implied by the diagnosis

trait MyFn<'a>{}

struct A<T>(T);

impl<'a,'d,F> MyFn<'a> for A<F>
where F:Fn(&'a i32){
    
}
fn check<F>(_:F) where F: for<'a> MyFn<'a>{} 

fn check2<'a,F:Fn(&'a i32)>(f:F){
    check(A(f));
}

^^^^^^^^^^^ requires that 'a must outlive 'static

why does a specific type F that satisfies F:Fn(&'static i32) satisfy for<'a> F: Fn(&'a i32)?

I don't find a document that would say Fn(&'static i32): Fn(&'a i32), based on that we know the satisfaction(for the lifetime) is transitive, for example, 'x:'static and 'static:'y, we can infer that 'x:'y.

PS：add 'a:'static does not compile too, maybe a diagnosis issue about rustc.

[quinedot]

@xmh0511

why does a specific type F that satisfies F:Fn(&'static i32) satisfy for<'a> F: Fn(&'a i32)?

It doesn't mean that (try replacing 'a with 'static). Satifsying Fn(&'static i32) is necessary, but not sufficient, to satisfy for<'a> Fn(&'a i32).

The diagnostic probably makes more sense in other contexts (?).

@xmh0511

I don't find a document that would say Fn(&'static i32): Fn(&'a i32), based on that we know the satisfaction(for the lifetime) is transitive, for example, 'x:'static and 'static:'y, we can infer that 'x:'y.

Parameters of traits are invariant, and there's no bound on the trait requiring that either.

And arguments of function pointers/function item types/closures are contravariant incidentally, so the for those, the subtyping goes in the other direction.

[xmh0511]

The diagnosis requires that 'a must outlive 'static just has some misleading, as you said, Satisfying Fn(&'static i32) is a necessary condition of satisfying for<'a> Fn(&'a i32) but not a sufficient condition.

The code does not compile even though I added 'a:'static.

[quinedot]

Yeah, it's not really all that helpful in this context. The "it's not higher ranked" error is the important part.

[xmh0511]

In the last example,

impl<'a,'d,F> MyFn<'a> for A<F>
where F:Fn(&'a i32){
    
}

This implementation is a candidate of eligible higher-ranked implementations, merely, the supplied F in

fn check<F>(_:F) where F: for<'a> MyFn<'a>{} 

fn check2<'a,F:Fn(&'a i32)>(f:F){
    check(A(f));
}

makes the trait bound where F:Fn(&'a i32) not true, hence the generic implementation is not viable one, which makes that F: for<'a> MyFn<'a> is not satisfied.