Sort_by_key, and probably a simple lifetime issue

help
#1

What I thought was a trivially simple thing…

    let mut v = Vec::<(OsString, u32)>::new();

    v.sort_by_key(|(e, _)| e);

That is, vec of tuples, sort by .0. (Playground link) This gets me,

6 |     v.sort_by_key(|(e, _)| e)
  |                    ------- ^ returning this value requires that `'1` must outlive `'2`
  |                    |     |
  |                    |     return type of closure is &'2 OsString
  |                    has type `&'1 (OsString, u32)`

What I don't get is … why? Like, sure, the &OsString reference is only as good as long as the &(…) tuple ref, but shouldn't my closure here be fine, as something like |&'a (<the tuple>)| -> &'a OsString?

Is this the same problem as this? (I'm pretty tired, and the brain is pretty fried.)

#2

Looking at the Vec::sort_by_key() signature:

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

The relevant part, if I am not mistaken, is the F: FnMut(&T) -> K bound. This is equivalent to F: for<'a> FnMut(&'a T) -> K; that is, the function must produce a valid K no matter how short-lived 'a is. Since K can only be a single type, there's no way to have it match every possible 'a. In the compiler error, 'a is called '1, and the lifetime of K is called '2. This seems to be the same issue as the one you linked.

2 Likes
#3

Hmm. I guess I expected K in that bound to be an implicit K + '_? (Where the '_ on that would be the same as the one on &T.)

#4

Unfortunately, that doesn't really work. The closure has type for<'a> FnMut(&'a T) -> K. The for<'a> means that this closure works for all possible lifetimes 'a; the only guarantee is that 'a lasts at least until the closure returns. The caller can drop its T immediately after the closure returns, and since there can only be one single type K (it's one of the parameters of sort_by_key), the closure must assume this worst-case scenario in its return type. This is what the compiler error is trying to say: for every possible input lifetime '1, you're trying to return the same output lifetime '2. However, the only output lifetime '2 which matches all possible inputs is the one that ends once the closure returns. Therefore, you are not actually allowed to return a value of type &'2 OsString, since '2 is inherently tied to the closure call.

#5

Like the other topic said, you can use sort_by (or sort_by_unstable) instead.

The rest of this post looks at your intuition and the various ways it might work, but doesn't today. The TL;DR is that there is no such K + '_ feature for type parameters K.

Type parameters always resolve to a single type. K + '_ doesn't mean anything for type parameter K, but if it did, it would probably mean K: '_ and not actually help; in the given context that would be the same restrictions that are on K today, because K must still be a single type outside of that bound. You instead need some way to declare the output (K) in a location where it can "see" the input lifetime it relies on.

So the K + '_ you intuited would instead have to be something like a GAT (generic associated type), and not a type parameter:

// Not how these traits actually work
F: FnMut(&T) -> F::Output<'_>

But that's not how FnMut and friends are designed -- and GATs are not stable. The closest we have right now is return position impl Trait, but that can't be used in bounds.

// Not supported, but perhaps closest to what you intuited
// (You also lose the ability to "name" `K`, in current Rust)
F: FnMut(&T) -> impl Ord + '_

Alternatively, one would think it was possible with the unboxed_closures feature and higher-ranked bounds, but even that hits normalization issues.

#![feature(unboxed_closures)]
// ...
    pub fn sort_by_key<F>(&mut self, f: F)
    where
        // The same bound but without naming the output type
        F: for<'any> FnMut<(&'any T,)>,
        // Saying the output type must always be `Ord`
        for<'any> <F as FnOnce<(&'any T,)>>::Output: Ord,

(See also or more specifically probably this one.)

Any of these that did work would be an increased commitment on behalf of the method, i.e. would support cases that aren't supported today. However, assuming they didn't break inference, it's probably a reasonable extension.

Alternatively you would need "type constructor parameters" instead of type parameters:

// Made up future Rust syntax and capability
pub fn sort_by_key<K<*>, F>(&mut self, F)
where
    F: FnMut(&T) -> K<'_>,
    for<'any> K<'any>: Ord,

But this version is actually less capable than the above future possibilities, as by stating the Ord bound separately from F and T, K<'_> must be defined for all lifetimes. In the above examples, it would only need to be defined where T is defined. (If T is static, this makes no difference, but T might not be static.)

Contrast with F: FnMut(&T) -> impl Ord + '_, where the Ord bound on the output is within the context of the input (&T).

Moreover, I'm unaware of any serious proposal to add type constructor parameters to Rust.

1 Like