Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
Tracked by #54279
shepmaster opened this issue Jun 8, 2016 · 19 comments
Open
Tracked by #54279

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

shepmaster opened this issue Jun 8, 2016 · 19 comments
Labels
C-bug Category: This is a bug. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@shepmaster
Copy link
Member

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
Copy link
Contributor

hanna-kruppe commented Jun 8, 2016

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
Copy link
Member Author

I think this requires HKT

I was rather afraid of that.

@steveklabnik steveklabnik added T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. and removed A-libs labels Mar 24, 2017
@Mark-Simulacrum Mark-Simulacrum added the C-bug Category: This is a bug. label Jul 25, 2017
@oli-obk
Copy link
Contributor

oli-obk commented Aug 21, 2017

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
Copy link
Member Author

@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
Copy link
Contributor

oli-obk commented Aug 28, 2017

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
Copy link
Member Author

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Member

phansch commented Jun 28, 2020

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

@mimoo

This comment was marked as off-topic.

@chpio

This comment was marked as off-topic.

@mimoo

This comment was marked as off-topic.

@ebroto

This comment has been minimized.

@danielhenrymantilla
Copy link
Contributor

danielhenrymantilla commented Jul 20, 2022

Now that the necessary HKT properties can be expressed in stable Rust, and have been expressed in the newly released ::lending-iterator crate1, 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
Copy link
Contributor

Jules-Bertholet commented Apr 7, 2023

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
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Member

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)).

@crlf0710
Copy link
Member

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());
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-bug Category: This is a bug. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests