Tracking issue for RFC 2351, "Add is_sorted to the standard library"

[Centril]

Feature gate: #![feature(is_sorted)]

This is a tracking issue for is_sorted{_by,_by_key} functions on [T] and Iterator (rust-lang/rfcs#2351).

Public API

impl<T> [T] {
    pub fn is_sorted(&self) -> bool
    where
        T: PartialOrd;

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

// core::iter

pub trait Iterator {
    // all the other methods omitted

    fn is_sorted(self) -> bool
    where
        Self: Sized,
        Self::Item: PartialOrd;

    fn is_sorted_by<F>(mut self, compare: F) -> bool
    where
        Self: Sized,
        F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>;

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

Steps / History

• Implementation: Add is_sorted to Iterator and [T] #55045
• Only call the closure parameter of Iterator::is_sorted_by_key once per item #62473
• remove HRTB from [T]::is_sorted_by{,_key} #102977
• Add more comprehensive tests for is_sorted and friends #112699
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• Require Ord instead of only PartialOrd?
  • Answered by Make is_sorted[_by_key] require Ord instead of PartialOrd and remove Iterator::is_sorted_by_key #81382 (comment) (no, PartialOrd is the right bound)
• Should Iterator::is_sorted_by_key be added as well?
  • It was added in the original implementation PR
• Add std::cmp::is_sorted instead?
• Should is_sorted_by take a closure returning bool instead of Option<Ordering>?

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[LukasKalbertodt]

@gnzlbg Would you be interested in implementing this? You basically already wrote the code. I think it would be fancy to have this SIMD code in the standard library. (Or should we start with only the fully generic algorithm?). PS: Sorry for not having reviewed #53386 yet -- I hope I'll find the time and mental capacity to do that in the near future!

@Centril The links for the unresolved questions are dead (still pointing to the 0000 file). Could you or anyone update them? :)

---

Regarding the "Should Iterator::is_sorted_by_key be added as well?" question: this last minute comment in the RFC thread argues that this method should be added:

I feel like it is not a question about how easy it is to do it yourself using map but more about completeness of the api.

And people seem to agree. So I'd also say that this method should be added.

[Centril]

@LukasKalbertodt done :)

[Centril]

cc @SimonSapin re. the unresolved questions (particularly around is_sorted_by_key).

[gnzlbg]

I don't know when I can work on this, but I can mentor anyone wanting to implement this or wanting to port the implementation of the is_sorted crate.

[SimonSapin]

Oh, I didn’t realized that Iterator::is_sorted_by_key was not part of the RFC when I proposed FCP. I thought there was consensus to include it for consistence, both internal and with the existing sort_by_key/min_by_key/max_by_key methods which are also redundant with their respective method like sort_by.

We do have precedent of adding some APIs that can be expressed as a terse combination of existing APIs: #49098

@clarcharr, you expressed the opposite in rust-lang/rfcs#2351 (comment). Do you still think it should not be included?

[clarfonthey]

At the time I made that comment, I didn't realise that max_by_key and min_by_key were already stable (as of 1.6, which is a while ago). Basically, there are two options:

1. Deprecate max_by_key and min_by_key and don't add is_sorted_by_key.
2. Add is_sorted_by_key.

I feel like the usefulness of these should be re-evaluated, as it forces the key to outlive any reference to self rather than just the current reference to self. Basically, we'd need something similar to GAT for it to be useful, and map already exists.

Personally, I'd prefer option 1. But option 2 is also acceptable and there may be a way to make these functions work with GAT in the future.

[gnzlbg]

@SimonSapin would you like to be the reviewer of a PR implementing this ? If so, I'd like to discuss with somebody first how the is_sorted crate is structure, and how to best implement this functionality in the std library.

[gnzlbg]

So I don't know how to properly implement this in core.

The is_sorted functionality should use intrinsics when available at run-time. The iter and slice modules in core do not have access to run-time detection (that requires std), but e.g. the Iterator trait exported by core and std has to be the same, so we can't override the core implementation in std to add run-time detection on top.

After talking with @SimonSapin on IRC, I am just going to add the naive versions to core which get picked up by std and call it a day. Those who need more performance can just use is_sorted from crates.io. Adding vectorized versions of the is_sorted functionality isn't worth it either, because one would need to re-compile core to profit from it (using crates.io is just easier). Maybe if we get newer targets in the future with more features enabled this might become worth it.

[kleimkuhler]

I have interest in working on this RFC. This would be a significant learning experience for me, but I don't see any reason why I should not be able to complete it.

@gnzlbg If your offer for being available as a mentor is still open, I'd like to take you up on that!

If there is any concern in timeline (I should be able to begin implementing this week) or preference for someone who may have more experience, I have no problem with that; just let me know!

[gnzlbg]

An efficient implementation of this is probably blocked on rust-lang/rfcs#2492 (e.g. see rust-lang/rfcs#2492 (comment)) , since until then we cannot really use SIMD in libcore effectively.

My recommendation is that if you want to implement this now, you should just adapt rust-itertools/itertools#261 which is a straight-forward plain Rust implementation. Maybe with some tweaks one can get it to auto-vectorize in some cases. This would allow us to get experience with the API until the other problems are solved.

[kleimkuhler]

Thanks for the links; it makes sense that a more efficient implementation is blocked on that right now.

To clarify on my initial comment (and what you picked up on in your last sentence), is the "learning" part of this would be more related to familiarizing myself with the API and codebase.

I think an initial implementation based off rust-itertools/itertools#261 could be a good first step and we'll keep an eye on the progress of rust-lang/rfcs#2492?

[kleimkuhler]

@gnzlbg You'll find my initial implementation in the PR above (#55045). I'm not sure who should be officially reviewing this, but I can update the PR if need be!

[kleimkuhler]

@SimonSapin It was asked a few comments up if you'd like to be the reviewer of this PR? I still need to assign someone to review it, but I'm just not sure who.

[mtak-]

This has broken the is_sorted crate on nightly. Is the only workaround to turn the feature flag on or use an older nightly?

   --> ~/.cargo/registry/src/github.com-1ecc6299db9ec823/is_sorted-0.1.0/src/lib.rs:119:31
    |
119 |         self.map(|v| key(&v)).is_sorted()
    |                               ^^^^^^^^^
    |
    = help: add #![feature(is_sorted)] to the crate attributes to enable

[clarfonthey]

Call IsSorted::is_sorted directly.

[mtak-]

@clarcharr The above error happens when adding is_sorted as a dependency (without using it). The is_sorted crate itself no longer builds.

[CryZe]

You can send a PR to the is_sorted crate and use the patch section in your Cargo.toml in the meantime until it is merged and published.

[gnzlbg]

@mtak- thank you for the PR, i've merged it already, will fix the doc tests and do a release so that the world keeps going.

The collision between the is_sorted crate and this PR was expected, I guess I could have fixed that a priori. Sorry about that. Keep in mind that if you are using the is_sorted crate, if you don't disambiguate your code the implementations of libcore will be picked after a re-compile.

[leonardo-m]

If slice::sort uses F: FnMut(&T, &T) -> Ordering, then perhaps is_sorted_by could use the same.

[nm17]

A suggestion: Rust compiler should raise a compiler error when is_sorted or one of the related functions is called on keys or values of a HashMap, since depending on their order is UB.

[clarfonthey]

Depending on the order of items in a HashMap isn't UB; the order is just not guaranteed. The difference here is one thing is unsafe and one is just a bad idea.

[rdrpenguin04]

"Revisit test suite" can probably be checked off due to #112699.

I feel like this could probably be stabilized as-is, and more could be added in later.

[WaffleLapkin]

Nominating for T-libs-api: this API existed for a while, and the only question left seems to be whatever cmp::is_sorted would be a better API option. Thus, I'm proposing stabilization :)

Note: while trying to check the implementation history I've updated the issue text with the newer format, hopefully it makes it easier to understand what this issue tracks, exactly.

While doing that I've also found two questions in the comments that did not seem to be fully answered:

• Tracking issue for RFC 2351, "Add is_sorted to the standard library" #53485 (comment) — questions whatever Option<Ordering> is the right thing to ask for is_sorted_by
• Tracking issue for RFC 2351, "Add is_sorted to the standard library" #53485 (comment) — questions whatever we should have a function that returns a position up to which everything is sorted

[m-ou-se]

We dicsussed this in a recent libs-api meeting.

• Using bool rather than Option<Ordering> for the return value of the closure to is_sorted_by seems clearer and more flexible. E.g. then you can use a < b or a <= b depending on whether it should be strictly increasing or not, etc.
• There wasn't much enthusiasm for adding a function to return the position up to which everything is sorted. That is easy enough to write manually, and is probably too niche to warrant its own function. Iterator has convenience methods for common operations, but it doesn't need a method for every possible operation.

[Jules-Bertholet]

This was already mentioned earlier, but is_sorted_by_key, like all the by_key methods, suffers from #34162; a fix would require removing the K type parameter.