Lifetime parameters in generic types, and their relation to higher order trait bounds

Problem

I made a user forum post about an issue I had related to this, but essentially, lifetime parameters in generic types (which don't really exist currently, and have to be specified using turbofish syntax by the caller IIRC) are not usable in higher order trait bounds, and worse, there is no way to override the default (inferred lifetime) manually (AFAIK). Below is an example of this behavior.

Example: playground

struct Wrapper<'a>(&'a str);

fn foo<F1, F2, T>(f1: F1, f2: F2, base: &'static str)
where 
    F1: for<'a> Fn(&'a str) -> T,
    F2: Fn(T) -> bool
{
    let owned = base.to_owned();
    let str_ref = owned.as_ref();
    let result = f1(str_ref);
    assert!(f2(result));
}

fn dummy<'l>(s: &'l str) -> Wrapper<'l> {
    Wrapper(s)
}

fn main() {
    foo(dummy, |_| true, "test");
/*
error[E0271]: type mismatch resolving `for<'a> <for<'l> fn(&'l str) -> Wrapper<'l> {dummy} as std::ops::FnOnce<(&'a str,)>>::Output == _`
  --> src/main.rs:19:5
   |
3  | fn foo<F1, F2, T>(f1: F1, f2: F2, base: &'static str)
   |    ---
4  | where 
5  |     F1: for<'a> Fn(&'a str) -> T,
   |                                - required by this bound in `foo`
...
19 |     foo(dummy, |_| true, "test");
   |     ^^^ expected bound lifetime parameter 'a, found concrete lifetime
*/
    foo(dummy as for<'r> fn(&'r str) -> Wrapper<'r>, |_| true, "test");
/*
error[E0271]: type mismatch resolving `for<'a> <for<'r> fn(&'r str) -> Wrapper<'r> as std::ops::FnOnce<(&'a str,)>>::Output == _`
  --> src/main.rs:33:5
   |
3  | fn foo<F1, F2, T>(f1: F1, f2: F2, base: &'static str)
   |    ---
4  | where 
5  |     F1: for<'a> Fn(&'a str) -> T,
   |                                - required by this bound in `foo`
...
33 |     foo(dummy as for<'r> fn(&'r str) -> Wrapper<'r>, |_| true, "test");
   |     ^^^ expected bound lifetime parameter 'a, found concrete lifetime
*/
    foo::<_,_,Wrapper>(dummy, |_| true, "test");
/*
error[E0271]: type mismatch resolving `for<'a> <for<'l> fn(&'l str) -> Wrapper<'l> {dummy} as std::ops::FnOnce<(&'a str,)>>::Output == Wrapper<'_>`
  --> src/main.rs:47:5
   |
3  | fn foo<F1, F2, T>(f1: F1, f2: F2, base: &'static str)
   |    ---
4  | where 
5  |     F1: for<'a> Fn(&'a str) -> T,
   |                                - required by this bound in `foo`
...
47 |     foo::<_,_,Wrapper>(dummy, |_| true, "test");
   |     ^^^^^^^^^^^^^^^^^^ expected bound lifetime parameter 'a, found concrete lifetime
*/
    foo::<_,_,Wrapper>(dummy as for<'r> fn(&'r str) -> Wrapper<'r>, |_| true, "test");
/*
error[E0271]: type mismatch resolving `for<'a> <for<'r> fn(&'r str) -> Wrapper<'r> as std::ops::FnOnce<(&'a str,)>>::Output == Wrapper<'_>`
  --> src/main.rs:61:5
   |
3  | fn foo<F1, F2, T>(f1: F1, f2: F2, base: &'static str)
   |    ---
4  | where 
5  |     F1: for<'a> Fn(&'a str) -> T,
   |                                - required by this bound in `foo`
...
61 |     foo::<_,_,Wrapper>(dummy as for<'r> fn(&'r str) -> Wrapper<'r>, |_| true, "test");
   |     ^^^^^^^^^^^^^^^^^^ expected bound lifetime parameter 'a, found concrete lifetime
*/
}

As far as I can tell, there is no way to specify the parameters to Wrapper in the called function's higher order trait bounds, to match those specified in the dummy function. In fact, there is no way to override the lifetime parameters to foo's T with anything defined by a higher order trait bound. If I'm wrong please let me know.

Solution

There should be syntax and semantics (or better documentation if there is actually a way to do this) created to allow the binding of lifetime parameters in generics. I believe a good start would be syntax like T<'l> allowed in generic parameters to signify types with lifetime parameters.

Example:

struct Wrapper<'a>(&'a str);

fn foo<F1, F2, T<'l>>(f1: F1, f2: F2, base: &'static str)
where 
    F1:  for<'a> Fn(&'a str) -> T<'a>,
    F2: Fn(T) -> bool
{
    let owned = base.to_owned();
    let str_ref = owned.as_ref();
    let result = f1(str_ref);
    assert!(f2(result));
}
...

Thoughts? Opinions?

1 Like

This would require higher kinded types or similar. This is something that can be done with GATs, but those are in the very early stages of implementation. So there isn't a way to do this, even on nightly.

2 Likes

This seems to be like what you're suggesting adding is higher kinded type parameters. T here looks like something like a type, but missing a generic parameter. As @RustyYato mentioned, generic associated types are the closest thing to higher kinded types that have been accepted as an RFC, and have an inclusion plan in Rust.

The GAT version of this would look roughly like:

trait FnRes {
    type Res<'a>;
}

struct Wrapper<'a>(&'a str);
struct UsingWrapper;
impl FnRes for UsingWrapper {
    type Res<'a> = Wrapper<'a>;
}

fn foo<F1, F2, T: FnWrapper>(f1: F1, f2: F2, base: &'static str)
where 
    F1: for<'a> Fn(&'a str) -> T::Res<'a>,
    F2: Fn(T::Res) -> bool
{
    let owned = base.to_owned();
    let str_ref = owned.as_ref();
    let result = f1(str_ref);
    assert!(f2(result));
}

foo::<_, _, UsingWrapper>(...);

Back to your proposal.

I kind of like the syntax T<'l>, but I think it might deserve more bikeshedding. Having this would introduce something fundamentally new to rust: a "type like" thing which is not a full type since you must specify a lifetime before using it. I know there have been past HKT proposals, so it might be worth looking at those.

GATs avoid the problem of partially applied / incomplete types by never actually letting T::Res exist as a type. Rather, it only uses fully concrete types, and the partial / generic parts exist only as associated types. (in the above example, we never pass an incomplete type to foo).

As for the underlying functionality, it's a sound idea. We want something like this, and after implementing GATs, a more convenient syntax could certainly be helpful. However, I doubt it will ever come before we get GATs, as the implementation would be bottlenecked by the same things that are currently bottlenecking GATs. Mainly, chalk needs to reach an MVP state, and we need to integrate it into rustc's trait resolution and inference engine.

1 Like

Here is the closest you can get right now,

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=aad6cf797fe3ba0a4535a6da65b061b8

Since you can't name function types (or closure typees) you would have to implement MyFn by hand in order to make this compile.

Ignoring the ICE that it currently produces, I would expect the following to work:

#![feature(unboxed_closures)]

struct Wrapper<'a>(&'a str);

fn foo<F1, F2>(f1: F1, f2: F2, base: &str)
where 
    F1: for<'a> Fn<(&'a str,)>,
    F2: Fn(<F1 as FnOnce<(&str,)>>::Output) -> bool,
{
    let owned = base.to_owned();
    let str_ref = owned.as_ref();
    let result = f1(str_ref);
    assert!(f2(result));
}

fn dummy<'l>(s: &'l str) -> Wrapper<'l> {
    Wrapper(s)
}

fn main() {
    foo(dummy, |_| true, "test");
}
2 Likes

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=aad6cf797fe3ba0a4535a6da65b061b8

I went to the playground and that doesn't actually compile though :confused:

That's why I said this

You can make it compile, but it's ugly and I would try and avoid this bound altogether until we have a better story for Hkt/GATs

1 Like