Implement PartialOrd<str> for String, PartialOrd<[T]> for Vec<T>

[ecton]

Proposal

Problem statement

Currently, String and str implement PartialEq for each other, but do not
implement PartialOrd for each other. This is also true of Vec<T> and [T].
I want to submit a pull request adding implementations for PartialOrd to round
out the trait implementations of these types.

Motivating examples or use cases

When working on a sorted vec implementation, I originally implemented get()
lookups using PartialOrd<SearchType>. In effect, it looked like this:

struct Map<Key, Value>(Vec<(Key, Value)>);

impl<Key, Value> Map<Key, Value> {
    fn get<SearchKey>(&self, key: &SearchKey) -> Option<&Value>
    where
        Key: PartialOrd<SearchKey>,
        SearchKey: ?Sized,
    {
        todo!()
    }
}

fn main() {
    let map = Map(vec![(String::from("a"), ())]);
    map.get("a");
}

This does not compile, however, due this missing implementation.

I then looked at other standard library types that have Borrow implementations
that I'm aware of: OsString/OsStr and PathBuf/Path. Both implement
PartialOrd in addition to PartialEq.

Solution sketch

In alloc, add these implementation blocks:

// PartialOrd for String with str
impl PartialOrd<str> for String {}
impl<'a> PartialOrd<&'a str> for String {}
impl<'a> PartialOrd<Cow<'a, str>> for String {}

// PartialOrd for str with String
impl PartialOrd<String> for str {}
impl<'a> PartialOrd<&'a String> for str {}
impl<'a> PartialOrd<Cow<'a, str>> for str {}

// PartialOrd for Vec<T,A> with [T]
impl<T, U, A> PartialOrd<[U]> for Vec<T, A> where T: PartialOrd<U>, A: Allocator {}
impl<'a, T, U, A> PartialOrd<&'a [U]> for Vec<T, A> where T: PartialOrd<U>, A: Allocator  {}

// PartialOrd for Vec<T,A> with [T; N]
impl<T, U, A, const N: usize> PartialOrd<[U; N]> for Vec<T, A> where T: PartialOrd<U>, A: Allocator {}
impl<'a, T, U, A, const N: usize> PartialOrd<&'a [U; N]> for Vec<T, A> where T: PartialOrd<U>, A: Allocator  {}

// PartialOrd for [T] with Vec<U, A>
impl<T, U, A> PartialOrd<Vec<U,A>> for [T]  where T: PartialOrd<U>, A: Allocator {}
impl<'a, T, U, A> PartialOrd<&'a Vec<U, A>> for [T] where T: PartialOrd<U>, A: Allocator  {}

// PartialOrd for [T; N] with Vec<U, A>
impl<T, U, A, const N: usize> PartialOrd<Vec<U,A>> for [T; N]  where T: PartialOrd<U>, A: Allocator {}
impl<'a, T, U, A, const N: usize> PartialOrd<&'a Vec<U, A>> for [T; N] where T: PartialOrd<U>, A: Allocator  {}
impl<'a, T, U, A, const N: usize> PartialOrd<Cow<'a, U>> for [T; N] where T: PartialOrd<U>, A: Allocator  {}

This list of proposed implementations was gathered by looking at the PartialEq
list of String/Vec and adding the missing PartialOrd implementations. The
implementations for these blocks should be similar to their PartialEq
equivalents, but calling cmp/partial_cmp instead of eq.

Alternatives

Because of foreign trait implementation rules, the main workaround is to either
use a newtype wrapper that implements these traits or introduce new
traits that serve the same purpose as PartialOrd.

Links and related work

• Issue found for this request: impl PartialOrd<str> for String rust#82990

This is my first API change proposal. I feel like this is a fairly straightforward change, to the best of my knowledge, due to foreign trait implementation rules preventing these additional implementations from being breaking changes. I personally cannot think of a reason that these shouldn't be added, but I am new to std lib development, so I may not be aware of ways that these implementations could cause issues in the ecosystem.

[the8472]

When working on a sorted vec implementation, I originally implemented get() lookups using PartialOrd. In effect, it looked like this

Have you tried using Borrow in your implementation? HashMap::get uses it.

[ecton]

Have you tried using Borrow in your implementation? HashMap::get uses it.

Requiring Borrow<U> + U being PartialOrd does not guarantee that <T as PartialOrd<U>>::partial_cmp matches U::partial_cmp. In fact, the Borrow documentation uses HashMap as an example of this unenforced but sometimes expected behavior:

Further, when providing implementations for additional traits, it needs to be considered whether they should behave identically to those of the underlying type as a consequence of acting as a representation of that underlying type. Generic code typically uses Borrow when it relies on the identical behavior of these additional trait implementations. These traits will likely appear as additional trait bounds.

In particular Eq, Ord and Hash must be equivalent for borrowed and owned values: x.borrow() == y.borrow() should give the same result as x == y.

And, that is exactly what I'm trying to prevent when using an "interned string" smart pointer type. The interned string type supports Deref and Borrow into str, because that makes it be able to act like a smart pointer. However, I made this type specifically not implement PartialOrd<str> because the smart pointer's Ord implementation uses the actual pointer for sorting rather than the string contents. This flow allows sorting to be done incredibly quickly, but it won't be the same order as str::cmp uses.

While you may argue about this use case, requiring a direct PartialOrd<SearchKey> implementation and skipping the use of Borrow provides a perfect way to implement this type safety. This is because in the PartialOrd is documented as being explicitly required to be consistently implemented:

The methods of this trait must be consistent with each other and with those of PartialEq.

In my opinion, while Borrow offers a path to implement ordered collections, it is not the only or best path that could be provided if the standard library implemented PartialOrd more liberally.

[Amanieu]

We discussed this in the libs-api meeting and are happy with this change. However this should pass a crater run to check if the new impls cause any type inference failures.