Higher-rank trait bounds return type lifetimes

help
1

Hi,
I'm playing around with HRTBs and am running into some confusion with lifetimes for return types. So I started with the following code (which works):

fn foo<F>(_: F)
where
    for <'a> F: Fn(&'a str)
{}

fn alpha<'a>(_: &'a str) {}

fn main() {
    foo::<_>(alpha);
}

However, the following code does not work:

fn bar<F>(_: F)
where
    for <'a> F: Fn() -> &'a str
{}

fn beta<'a>() -> &'a str {
    &""
}

fn main() {
    bar::<_>(beta);
}

I'm struggling to understand how the second block is fundamentally different from the first block. I understand that F: Fn() -> &'a str gets desugared into Fn<(()), Output = &'a str> and so something something associated type lifetimes have to depend on the input, but I don't intuitively understand why.

We have a function beta that can return a string with an arbitrary lifetime, and yet it does not satisfy the trait bound.

In the error docs for the associated error E0582 there is the following snippet:

fn bar<F>(t: F)
    // No type can satisfy this requirement, since `'a` does not
    // appear in any of the input types (here, `i32`):
    where F: for<'a> Fn(i32) -> Option<&'a i32>
{
}

fn main() { }

But shouldn't the function:

fn f<'a>(_: i32) -> Option<&'a i32> {
    None
}

satisfy this constraint? Clearly I'm misunderstanding something. Thanks in advance for any help.

2

I’m not familiar with this issue myself, but I would guess that you should understand the problem not as “But shouldn't the function … satisfy this constraint?” — not about matching fn f with the trait bound — but rather: when the function is called, what is the lifetime of the output? There’s no way to pick, in the proper fashion (by selecting the input generics and seeing what the output lifetime is), and presumably there is some unsoundness that occurs if free choice is allowed.

We could imagine that Rust could have some sort of higher-ranked generic parameters to make this possible:

fn bar<F<'a>>(t: F)
where
    for<'a> F<'a>: Fn(i32) -> Option<&'a i32>

Then each call site is in principle parameterizable in the same way the original function is: t::<'a>() like f::<'a>(). But there is nothing like that in today’s Rust.

3

Here's an optional playground exercise you may want to try before reading this comment, in case that fits your learning style.

You can think of the function item type's trait implementations as something like this:

impl<'a> FnOnce<()> for fn#beta<'a> {
    type Output = &'a str;
    fn call_once(self, args: ()) -> Self::Output {
        "" // Nit: no need for `&`, `""` is already a `&str`
    }
}

Note that the lifetime in the associated type has to come from somewhere; you can't have unconstrained generics in an implementation. There's no lifetime parameter on the trait and no lifetimes in the type parameters on the trait, so the lifetime has to be a parameter of the function item type. (If the lifetime wasn't part of the implementing type, there wouldn't be a single type solution to "what's the associated type in this implementation?".)

The lifetime parameter being on the function item type means that there is no single fn#beta type that implements Fn() -> &'a str for all lifetimes 'a. Instead each fn#beta<'x> implements Fn() -> &'x str for the singular particular lifetime 'x. [1]

In rustc parlance, the lifetime is "early bound". This particular example has it's own subsection in the dev guide.

In contrast, the lifetime on alpha is "late bound" (not a parameter of the function item type):

impl<'a> FnOnce<(&'a str,)> for fn#alpha {
    type Output = ();
    fn call_once(self, (_,): (&'a str,)) -> Self::Output {
    }
}

And here there is a single fn#alpha type that implements Fn(&'a str) for all lifetimes 'a, and thus can meet a for<'a> F: Fn(&'a str) bound.

As it turns out, while the compiler correctly makes the lifetime early bound with functions like beta in your OP, it fails to do so in some other cases such as closures.[2] That's a soundness hole which is tracked in this issue. The issue has concrete examples of how this can lead to a UAF using only safe code.

  1. Note that type parameters like F correspond to a single type. As @kpreid said, there are no "F<'..>" generic parameters. ↩︎

  2. Even with beta it incorrectly allows beta::<'not_static> to satisfy a 'static bound, which is also unsound. ↩︎

3 Likes