Rust has trouble seeing higher ranked lifetimes through generics

[Stebalien]

Rust has trouble seeing that a generic function is "generic" over higher ranked lifetimes. This behavior is best described by example. Given:

fn id<X>(x: X) -> X { x }

fn id_wrapped<'a, T>(v: &'a T) -> &'a T {
    // Defined for<'a>. No coercion.
    id::<&'a T>(v)
}

fn has_hrl<F: Fn(&()) -> &()>(f: F) {}

fn main() {
    has_hrl(id);
    has_hrl(id_wrapped);
    has_hrl(|x| id(x));
}

Rust complains:

error[E0281]: type mismatch: the type `fn(_) -> _ {id::<_>}` implements the trait `std::ops::Fn<(_,)>`, but the trait `for<'r> std::ops::Fn<(&'r (),)>` is required (expected concrete lifetime, found bound lifetime parameter )
  --> tmp.rs:11:5
   |
11 |     has_hrl(id);
   |     ^^^^^^^
   |
   = note: required by `has_hrl`

error[E0271]: type mismatch resolving `for<'r> <fn(_) -> _ {id::<_>} as std::ops::FnOnce<(&'r (),)>>::Output == &'r ()`
  --> tmp.rs:11:5
   |
11 |     has_hrl(id);
   |     ^^^^^^^ expected bound lifetime parameter , found concrete lifetime
   |
   = note: concrete lifetime that was found is lifetime '_#0r
   = note: required by `has_hrl`

error: aborting due to 2 previous errors

However, the has_hrl(id_wrapped) and has_hrl(|x| id(x)) calls demonstrate that, at some level, the rust type checker infers that id implements for<'r> Fn(&'r ()) -> &'r (). That's why I filed this as a bug instead of an RFC issue. However, I can move this if you feel that it's too much of a feature request.

---

My motivation is functional programming. Not being able to infer that a generic function is defined for some HRL makes it impossible to use such functions with, e.g., Iterator::filter.

[Stebalien]

/cc @bluss @iopq

[iopq]

I'm currently not able to use the library version of the function because of this limitation and I have to "specialize" manually by adding my own definition. This defeats the point of having libraries for functional programming in Rust, since the code doesn't compile due to this limitation.

[arielb1]

@iopq

That's an inherent limitation - generic type parameters can only be instantiated monomorphically:∀T. fn(T) -> T can't be instantiated to ∀'a. fn(&'a u32) -> &'a u32.

[Stebalien]

@arielb1,

Then how does id_wrapped work? To the best of my understanding, it's doing exactly what you're saying can't be done.

[arielb1]

@Stebalien

id_wrapped uses a lifetime parameter, not a type parameter. It starts as being ∀T ∀'a. fn(&'a T) -> &'a T.

[Stebalien]

@arielb1 Sorry, I should have explained further. id_wrapped is instantiated exactly once, therefore, it's body must be defined (in the executable) exactly once. Therefore, the rust compiler must be able to somehow tell that id::<'a, T> is defined for all 'a because the caller, id_wrapped, is defined for all 'a and is instantiated exactly once.

Here, I'm asking that rust use this knowledge to infer that <typeof id>: for<'a> Fn(&'a T) -> &'a T.

[arielb1]

As a trait object? The problem is that <typeof id>, which is basically System F's ∀T. T -> T (except for irrelevant fn-item vs. fn-ptr issues), is not really a type within Rust's trait/type system. Rust types can not contain higher-rank type parameters, and this is not expected to change in the nearby future (see: impredicativity). So when you use a Rust type, it is always instantiated to a type with no higher-ranked type parameters.

id_wrapped works because it uses a skolemized type, rather than a higher-ranked one.

[withoutboats]

@arielb1 Types which are higher-rank over lifetimes only don't suffer from impredicativity issues, no? You can't self-reference because they aren't of the correct kind for the higher-rank parameter.

Not saying they wouldn't be complicated to implement, just that I don't think they necessarily introduce decidability problems.

[steveklabnik]

Triage: this still fails to compile.

[estebank]

Triage: current output

error: implementation of `FnOnce` is not general enough
  --> src/main.rs:11:5
   |
11 |     has_hrl(id);
   |     ^^^^^^^ implementation of `FnOnce` is not general enough
   |
   = note: `fn(&'2 ()) -> &'2 () {id::<&'2 ()>}` must implement `FnOnce<(&'1 (),)>`, for any lifetime `'1`...
   = note: ...but it actually implements `FnOnce<(&'2 (),)>`, for some specific lifetime `'2`