Why can't I use a key function that returns a reference when sorting a vector with sort_by_key?

Question

I'm trying to sort a Vec<String> using a key function that returns references to the strings in the vector. A contrived example is to use the identity function as key function (which of course is useless, but it's the minimal example to reproduce my problem):

fn key(x: &String) -> &String {
    x
}

fn example(items: Vec<String>) {
    items.sort_by_key(key);
}

This gives the following error:

error[E0308]: mismatched types
   --> src/lib.rs:6:11
    |
6   |     items.sort_by_key(key);
    |           ^^^^^^^^^^^ lifetime mismatch
    |
    = note: expected associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
               found associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
    = note: the required lifetime does not necessarily outlive the empty lifetime
note: the lifetime requirement is introduced here

I don't understand why I get this error, so I tried to track this down. I first implemented my own version of sort_by_key():

fn sort_by_key<T, K: Ord>(a: &mut [T], key: fn(&T) -> K) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

When trying to call this function, I get what looks like the "opposite" error:

error[E0308]: mismatched types
 --> src/lib.rs:6:29
  |
6 |     sort_by_key(&mut items, key);
  |                             ^^^ one type is more general than the other
  |
  = note: expected fn pointer `for<'r> fn(&'r String) -> &String`
             found fn pointer `for<'r> fn(&'r String) -> &'r String`

I can make this code compile by fixing the key type to &T instead of using the generic parameter K, or by using &K instead of K as return type for the key function:

fn sort_by_key_v2<T: Ord>(a: &mut [T], key: fn(&T) -> &T) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

fn sort_by_key_v3<T, K: Ord>(a: &mut [T], key: fn(&T) -> &K) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

I also tried adding lifetime annotations, but that only shifted the error around without resolving it.

Here's the three versions of the sort_by_key() function on the Playground.

Why am I getting these errors? Is there any way to fix them while keeping the key type K completely generic?

Answer 1

For now, you have to use the "long" form:

v.sort_by(|x, y| key(x).cmp(&key(y)));

Why am I getting these errors? Is there any way to fix them?

The cause and fix are one-and-the same: Rust is simply not currently expressive enough to represent what you want. The feature needed is called generic associated types (GATs); previously known as associated type constructors (ATCs) or higher-kinded types (HKTs).

From the associated issue:

For the sort_by_key call to be okay, the lifetime of the input reference [...] needs to be incorporated into B to make the return type &'a str, but B is a type parameter.

I don't know if the signature for sort_by_key will be able to be seamlessly moved to a GAT when they are implemented. It seems doubtful at this point, as the Fn* traits themselves would likely need to be changed.

---

In similar cases where you control the signature of all the types, you can require that a reference be returned:

use std::cmp::Ordering;

struct User {
    name: String,
}

fn compare_keys<T, R>(a: T, b: T, key: impl Fn(&T) -> &R) -> Ordering
where
    for<'a> &'a R: Ord,
{
    let ak = key(&a);
    let bk = key(&b);
    ak.cmp(&bk)
}

fn main() {
    let alice = User {
        name: String::from("alice"),
    };
    let bob = User {
        name: String::from("bob"),
    };

    compare_keys(alice, bob, |u| &u.name);
}

This is non-ideal because now you cannot return a non-reference, but there's simply no complete solution until GATs are implemented. You may be able to add a parallel methods like sort_by and sort_by_key, depending on your case.