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

Opened by Jake Goulding at 2024-10-19 01:33:42

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

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.
Hanna Kruppe at 2016-06-08 15:08:56
I think this requires HKT

I was rather afraid of that.
Jake Goulding at 2016-06-08 15:19:36
```
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.
Oli Scherer at 2017-08-21 14:23:48

@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),

Jake Goulding at 2017-08-25 13:26:14

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

Oli Scherer at 2017-08-28 08:56:22

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).
Jake Goulding at 2017-08-28 12:57:06
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.
Clar Fon at 2018-01-05 00:31:58
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?
Maxim Nazarenko at 2018-02-22 00:38:59

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

Phil Hansch at 2020-06-28 06:22:45

getting this here also, can't upgrade to 1.46.0 due to this
David Wong at 2020-10-08 03:59:09
getting this here also, can't upgrade to 1.46.0 due to this

This is an old problem, why should this prevent you from upgrading to a new rust version? All rust versions in existence so far have this problem.
chpio at 2020-10-08 09:15:15
clippy warns on this now, and the project I work on doesn't let you land if you don't fix all clippy warnings
David Wong at 2020-10-09 00:51:06
@mimoo Clippy should not be hitting this in beta. If you can't upgrade you can allow the lint meanwhile. If you still have the problem in beta, let's discuss this in Clippy's repo to avoid the off-topic.
Eduardo Broto at 2020-10-09 06:43:17

Now that the necessary HKT properties can be expressed in stable Rust, and have been expressed in the newly released ::lending-iterator crate[^1], 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);
}

[^1]: disclaimer: of mine

Daniel Henry-Mantilla at 2022-07-20 13:05:57

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.

Jules Bertholet at 2023-04-07 20:02:38

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

Askar Safin at 2023-10-02 13:23:33

But I still don't like that two last solutions ( https://github.com/rust-lang/rust/issues/34162#issuecomment-1500599928 and https://github.com/rust-lang/rust/issues/34162#issuecomment-1743010732 ) 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: https://github.com/rust-lang/rust/issues/34162#issuecomment-355439910
Askar Safin at 2023-10-02 15:53:46
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)).
waffle at 2024-06-17 23:10:59

Maybe this can get covered by future extension of RTN, and some syntax sugar is even better:

#![feature(fn_traits)]
#![feature(unboxed_closures)]
#![feature(return_type_notation)]
#![feature(type_ascription)]

struct Client(String);

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

trait Tr<T>
{
    fn sort_by_key2<F>(&mut self, f: F)
    where
        F: for<'a> FnMut<(&'a T,), call_mut(..): Ord>;
    // error: return type notation used on function that is not `async` and does not return `impl Trait`
}

impl<T> Tr<T> for Vec<T> {
    fn sort_by_key2<F>(&mut self, f: F)
    where
        F: for<'a> FnMut<(&'a T,), call_mut(..): Ord>
    {
        todo!();
    }
}

fn main() {
    let mut clients: Vec<Client> = vec![];
    clients.sort_by_key2(|c| c.key());
}

Charles Lew at 2024-10-19 01:33:42