ACP: remove HRTB from `[T]::is_sorted_by{,_key}`

[lukas-code]

Proposal

Problem statement

Currently, the unstable function is_sorted_by_key is defined to take a closure with an implied higher-ranked lifetime bound (shown explicitly here):

pub fn is_sorted_by_key<F, K>(&self, f: F) -> bool
where
    F: for<'a> FnMut(&'a T) -> K,
    K: PartialOrd,
{ /* ... */ }

This means that the return value of the closure cannot borrow from the closure's argument.

In contrast, the stable function binary_search_by_key takes a closure where the lifetime of the argument is the same as the lifetime of the slice. This allows the closure to borrow its return value from its argument.

pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
where
    F: FnMut(&'a T) -> B,
    B: Ord,
{ /* ... */ }

In this ACP I am proposing to change the function signature of [T]::is_sorted_by and [T]::is_sorted_by_key to match [T]::binary_search_by and [T]::binary_search_by_key and remove the higher-ranked trait bound:

pub fn is_sorted_by<'a, F>(&'a self, mut compare: F) -> bool
where
    F: FnMut(&'a T, &'a T) -> Option<Ordering>,
{ /* ... */ }

pub fn is_sorted_by_key<'a, F, K>(&'a self, f: F) -> bool
where
    F: FnMut(&'a T) -> K,
    K: PartialOrd,
{ /* ... */ }

Motivation, use-cases

One of the main uses of is_sorted{,_by,_by_key} is to check the precondition before using binary_search{,_by,_key}, but this doesn't work in some cases today because of the different function signatures: (Playground link)

struct Record {
    name: String,
    // ... more fields here ...
}

let records = [
    Record {
        name: "Alice".to_owned(),
    },
    Record {
        name: "Bob".to_owned(),
    },
];

debug_assert!(records.is_sorted_by_key(|r| &r.name));
//~^ ERROR: lifetime may not live long enough

let who = "Bob";
match records.binary_search_by_key(&who, |r| &r.name) {
    Ok(pos) => println!("{who} is in place {pos} alphabetically"),
    Err(_) => println!("sorry, we couldn't find {who} in our records"),
}

What about [T]::is_sorted_by?

I don't have a compelling use case for is_sorted_by at the moment, but if we're updating one of these, we should probably update the other as well. For what it's worth, this will allow the following to compile:

let mut outer = &String::new();
records.is_sorted_by(|left, right| {
    outer = &left.name;
    None
});

What about Iterator::is_sorted_by{,_key}?

This problem does not exist for Iterator::is_sorted_by_key, because that takes its argument by value instead of by reference:

fn is_sorted_by_key<F, K>(self, f: F) -> bool
where
    Self: Sized,
    F: FnMut(Self::Item) -> K,
    K: PartialOrd,
{ /* ... */ }

Changing Iterator::is_sorted_by is probably not possible, because that one will drop the elements of the iterator while iterating over then.

Solution sketches

This will "just work" by changing the function signatures: rust-lang/rust#102977

As far as I know this will allow strictly more code to compile.

Links and related work

• RFC for is_sorted: RFC: Add is_sorted to the standard library rfcs#2351
• Tracking issue for is_sorted: Tracking issue for RFC 2351, "Add is_sorted to the standard library" rust#53485
• PR that changed Iterator::is_sorted_by_key to allow borrowing the return value from the argument: Only call the closure parameter of Iterator::is_sorted_by_key once per item rust#62473
• Proposed PR to update [T]::is_sorted_by_{,key}: remove HRTB from [T]::is_sorted_by{,_key} rust#102977

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[m-ou-se]

We discussed this in the libs-api meeting a few weeks ago, but forgot to reply here. Sorry!

This change looks fine to us. :)