slice::sort_by_key has more restrictions than slice::sort_by

[shepmaster]

I expected that these invocations of sort_by and sort_by_key would be equivalent:

struct Client(String);

impl Client {
    fn key(&self) -> &str {
        &self.0
    }
}

fn main() {
    let mut clients: Vec<Client> = vec![];

    // Error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
    clients.sort_by_key(|c| c.key());

    // OK
    clients.sort_by(|a, b| a.key().cmp(&b.key()));
}

The implementation of sort_by_key:

pub fn sort_by_key<B, F>(&mut self, mut f: F)
    where F: FnMut(&T) -> B, B: Ord
{
    self.sort_by(|a, b| f(a).cmp(&f(b)))
}

An initial attempt at using HRTB didn't seem to pan out:

pub fn sort_by_key<B, F>(&mut self, mut f: F)
    where for <'a> F: FnMut(&'a T) -> B + 'a,
          B: Ord

[hanna-kruppe]

I think this requires HKT (specifically, type parameters of kind lifetime -> *). For the sort_by_key call to be okay, the lifetime of the input reference ('a in the HRTB example) needs to be incorporated into B to make the return type &'a str, but B is a type parameter. The usual workarounds (impl<'a> IntoIterator for &'a Collection, hard-coding the return type to be a reference as in Deref) don't seem to apply.

[shepmaster]

I think this requires HKT

I was rather afraid of that.

[oli-obk]

fn my_sort_by_key<'a, B, F>(&mut self, f: F) where
    B: 'a + Ord,
    T: 'a,
    F: FnMut(&'a T) -> B;

Works just fine. But I might've missed some fancy interaction with other code, so maybe it's a breaking change.

[shepmaster]

@oli-obk did you try implementing the body of that function?

trait MySortByKey<T> {
    fn my_sort_by_key<'a, B, F>(&mut self, f: F)
    where
        B: 'a + Ord,
        T: 'a,
        F: FnMut(&'a T) -> B;
}

impl<T> MySortByKey<T> for [T] {
    fn my_sort_by_key<'a, B, F>(&mut self, f: F)
    where
        B: 'a + Ord,
        T: 'a,
        F: FnMut(&'a T) -> B,
    {
        let a = f(&self[0]);
        let b = f(&self[1]);
        
        match a.cmp(&b) {
            _ => self.swap(0, 1),
        }
    }
}

fn main() {}

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:16:19
   |
16 |         let a = f(&self[0]);
   |                   ^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 10:5...
  --> src/main.rs:10:5
   |
10 | /     fn my_sort_by_key<'a, B, F>(&mut self, f: F)
11 | |     where
12 | |         B: 'a + Ord,
13 | |         T: 'a,
...  |
21 | |         }
22 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:16:19
   |
16 |         let a = f(&self[0]);
   |                   ^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the method body at 10:5...
  --> src/main.rs:10:5
   |
10 | /     fn my_sort_by_key<'a, B, F>(&mut self, f: F)
11 | |     where
12 | |         B: 'a + Ord,
13 | |         T: 'a,
...  |
21 | |         }
22 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:16:19
   |
16 |         let a = f(&self[0]);
   |                   ^^^^^^^^

With your proposed signature, the caller of my_sort_by_key gets to specify the lifetime 'a which then must be constant during execution. However, the point of sorting is to move the items, changing their address and invalidating any lifetimes.

To do it, we need a way to say something like "there's a lifetime for each call to f and its return value which is disjoint from the passed in value and there's a generic type returned that respects that lifetime". Some made-up syntax like

F: for <'a> FnMut(&'a T) -> (B: Ord + 'a), 

[oli-obk]

Right, we can get around that with an intermediate trait:

trait MySortByKey<T> {
    fn my_sort_by_key<B, F>(&mut self, f: F)
    where
        B: Ord,
        F: for<'a> BorrowFn<'a, T, B>;
}

trait BorrowFn<'a, T: 'a, B: 'a>: FnMut(&'a T) -> B {}
impl<'a, T: 'a, B: 'a, F: FnMut(&'a T) -> B> BorrowFn<'a, T, B> for F {}

impl<T> MySortByKey<T> for [T] {
    fn my_sort_by_key<B, F>(&mut self, mut f: F)
    where
        B: Ord,
        F: for<'a> BorrowFn<'a, T, B>,
    {
        let a = f(&self[0]);
        let b = f(&self[1]);
        
        match a.cmp(&b) {
            _ => self.swap(0, 1),
        }
    }
}

fn main() {}

We can even make the intermediate trait unnameable: https://play.rust-lang.org/?gist=1039579366cc210732d3e4672b519370&version=stable

[shepmaster]

make the intermediate trait unnameable

Can you expand a bit more on what you mean by that? It would be nice if you'd also show an example usage of it. I tried with

fn main() {
    let mut a = [1,3,2];
    a.sort_by_key(|x| x);
    a.my_sort_by_key(|x| x);
}

And both failed (my_sort_by_key with one of those reallllly ugly errors).

[clarfonthey]

Perhaps a workaround is to add a sort_by_field version of sort_by_key which does exactly the same thing, only returning &K instead of K from the function.

[NovemberZulu]

I stumbled upon very similar issue while trying to sort by String field in a struct and ended up writing small wrappers like @clarcharr suggested. See https://play.rust-lang.org/?gist=906555798c392e3787a5eea151595c15&version=stable as an example. Does it make sense to develop this into a pull request?

[phansch]

triage: This is still a thing today, with a slightly better error message:

error: lifetime may not live long enough
  --> src/main.rs:13:29
   |
13 |     clients.sort_by_key(|c| c.key());
   |                          -- ^^^^^^^ returning this value requires that `'1` must outlive `'2`
   |                          ||
   |                          |return type of closure is &'2 str
   |                          has type `&'1 Client`

Playground

[danielhenrymantilla]

Now that the necessary HKT properties can be expressed in stable Rust, and have been expressed in the newly released ::lending-iterator crate¹, we can tackle the OP issue, as showcased in the docs of that crate:

struct Client { key: String, version: u8 }

fn main() {
    let clients: &mut [Client] = &mut [];

    // Error: cannot infer an appropriate lifetime for autoref due to conflicting requirements
    // clients.sort_by_key(|c| &c.key);

    // OK
    slice_sort_by_key::<HKT!(&str), _, _>(clients, |c| &c.key);

    // Important: owned case works too!
    slice_sort_by_key::<HKT!(u8), _, _>(clients, |c| c.version);
}

Footnotes

1. disclaimer: of mine ↩

[Jules-Bertholet]

The following compiles and runs as expected with -Ztrait-solver=next:

#![feature(closure_lifetime_binder)]
#![feature(unboxed_closures)]

fn sort_by_key<T, F>(s: &mut [T], mut f: F)
where
    F: for<'a> FnMut<(&'a T,)>,
    // instead of `B: Ord`
    for<'a> <F as FnOnce<(&'a T,)>>::Output: Ord,
{
    s.sort_by(|a, b| f(a).cmp(&f(b)))
}

#[derive(Debug)]
struct Client(String);

impl Client {
    fn key(&self) -> &str {
        &self.0
    }
}

fn main() {
    let mut test = vec![
        Client("c".to_string()),
        Client("a".to_string()),
        Client("b".to_string()),
    ];
    sort_by_key(&mut test, for<'a> |c: &'a Client| -> &'a str { c.key() });
    dbg!(test);
}

By eliminating the type parameter B entirely, we can sidestep the need for it to be an HKT.

[safinaskar]

Here is another way to solve the issue. It is based on previous @Jules-Bertholet's comment, but doesn't require -Ztrait-solver=next and thus can be run in playground. Also it requires one nightly feature less.

#![feature(closure_lifetime_binder)]

trait ABC<'a, T> {
    type B: Ord;
    fn ca(&mut self, a: &'a T) -> Self::B;
}

impl<'a, T: 'a, BB: Ord, XYZ> ABC<'a, T> for XYZ
where
    XYZ: FnMut(&'a T) -> BB
{
    type B = BB;
    fn ca(&mut self, a: &'a T) -> BB {
        self(a)
    }
}

fn sort_by_key<T, F>(s: &mut [T], mut f: F)
where
    F: for<'a> ABC<'a, T>,
{
    s.sort_by(|a, b| f.ca(a).cmp(&f.ca(b)))
}

#[derive(Debug)]
struct Client(String);

impl Client {
    fn key(&self) -> &str {
        &self.0
    }
}

fn main() {
    let mut test = vec![
        Client("c".to_string()),
        Client("a".to_string()),
        Client("b".to_string()),
    ];
    sort_by_key(&mut test, for<'a> |c: &'a Client| -> &'a str { c.key() });
    dbg!(test);
}

Playground: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=3bc32cf39a225ca491da94a3c8286e12

[safinaskar]

But I still don't like that two last solutions ( #34162 (comment) and #34162 (comment) ) require too many type annotations (for<'a> |c: &'a Client| -> &'a str { c.key() } instead of just |c|{ c.key() }). So we either need to fix type checker, either just implement sort_by_field as suggested by clarfonthey here: #34162 (comment)

[WaffleLapkin]

Note that sort_by_field wouldn't be able to handle cases where the key is not a reference, but another type with a lifetime derived from the input (although more rare, I could definitely imagine something like (&'a str, &'a str)).