How to inform the compiler that the return value of a closure lives as long as the argument lives?

help
1

Hello.

My problem was to sort a Vec<String> by a key, that is a part of that string:

fn main() {
    let mut a = ["hello", "beta", "world", "alpha"].map(|s| s.to_string());

    a.sort_by_key(|s| &s[..1]);
}

The code above fails to compile with the following error:

error: lifetime may not live long enough
   |
26 |     a.sort_by_key(|s| &s[..1]);
   |                    -- ^^^^^^^ returning this value requires that `'1` must outlive `'2`
   |                    ||
   |                    |return type of closure is &'2 str
   |                    has type `&'1 String`

I know that I can use sort_by instead, to avoid dealing with lifetimes, but I want to understand why I can't use sort_by_key nevertheless.

The function sort_by_key:

pub fn sort_by_key<K, F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
       // ...
    }

I guess, the code fails to compile because the compiler cannot be certain that the returned value of the closure (wihch is a reference to argument &String) won't outline the String, since F: FnMut(&T) -> K does not specify any lifetime requirements for K. Therefore, the caller of the closure won't have any information about how long the returned value lives, possibly letting it outlive the referent.

The failure to compile is understandable, but then why can't we enforce the closure F to only return types that live at least as long as the argument lives? It can be easily done for regular functions:

fn bar<'a>(a: &'a String) -> &'a str {
    &a[..1]
}

But I don't know a way to make it work for closures, specifying the constraint in their template type, somewhat similar to this: F: FnMut(&'a) -> K + 'a. It doesn't work, because 'a is not defined anywhere.

Is it possible to inform the compiler that the return value of a closure lives as long as the argument lives? If not, why? Is it not implemented yet, or it is impossible to implmement without breaking rust safety guarantees?

2

Rust unfortunately has different lifetime rules for closures, and no nice syntax (yet) to change them. You need a type inference trick:

fn hint_lifetime(closure: impl for<'a> FnMut(&'a str) -> &'a str) { closure }

let closure_with_lifetime = hint_lifetime(|s| s);

BTW, FnMut(&T) means for<'a> FnMut(&'a T). This for syntax allows you to make a lifetime out of thin air (the reference is valid for any lifetime 'a).

7 Likes
3

Using sort_by_key still isn’t going to be possible, even with tricks @kornel mentioned or other (perhaps even future) ways of “informing” the compiler of the correct closure signature.

This is because the signature of sort_by_key itself, which is

F: FnMut(&T) -> K,
// which is elided/short for
F: for<'a> FnMut(&'a T) -> K,

declares that there’s a single type K that’s the same return type, for any lifetime 'a.

You can see e.g. the function sort_by_cached_key which has the exact same signature, but its implementation keeps around instances of K for longer than would be legal if the closure returned keys that keep the &T borrow alive.

The status quo is simply that it’s a known limitation of sort_by_key that the keys can’t (re-)borrow from &T argument, and you’ll have to fall back to sort_by for that use-case.

Nonetheless, I wouldn’t be surprised if eventually Rust evolves in such a way that the signature of sort_by_key itself can be changed and generalized – however this is only realistic in the somewhat distant future, as not even current unstable feature or concrete planned language features – as far as I’m aware of them – would handle this.

The best current Rust can do is

  • offer another helper function, e.g. sort_by_key_ref that explicitly expects FnMut(&T) -> &K, for the common-case that the key has a lifetime because it’s simply a reference itself
    • this doesn’t handle any more complex, but useful types. E.g. users might still want to be able to use keys such as (&K1, &K2)
  • use GATs to “model” type parameters with lifetime parameters, with some trait trait SomeTrait { type Associated<'a>; }, then work with the signature for<'a> FnMut(&'a T) -> K::Associated<'a>
    • this currently doesn’t play nicely with type inference at all; you’ll manually have to define some dummy/marker type K that explicitly defines the generic type via an explicit SomeTrait impl
6 Likes