ACP: PartialOrd<[U]> for [T]

[clarfonthey]

Proposal

Problem statement

Right now, there's an inconsistency between the partial_cmp method on iterators and the PartialOrd implementation for slices: iterators can be compared as long as their elements can be compared, but slices can only be compared if they're of the same type.

Motivating examples or use cases

Basically anything where you might want to have an asymmetric comparison. Simple example would be comparing a [String] with [&str], where one is the owned strings in some buffer and the other is user-provided strings from a test or something else.

Solution sketch

Change impl<T: PartialOrd> PartialOrd for [T] to impl<T: PartialOrd<U>, U> PartialOrd<[U]> for [T]. Everything else works as expected.

Solution caveats

Since I thought this would be a "cut and dried" fix, I figure I should point out that it's not quite so with the current standard library implementation of PartialOrd for slices.

Essentially, we want to specialize on PartialOrd for types that implement Ord, since it (presumably) removes all of the extra branch checks when performing the comparison. However, because Ord doesn't accept a type parameter but PartialOrd does, specialization would effectively be duplicating the type: impl<A: AlwaysApplicableOrd> SlicePartialOrd<A> for A is unsound since the lifetimes are verified for equality, when they might not be.

There is definitely a way of making this work, although it would probably require having some internal version of Ord which accepts a type parameter, then specializing on that. I think that the difficulty of implementation is worth considering here, although I also consider the lack of a general Partialord implementation a bug that is also worth considering.

Alternatives

We could just not. But since this is easily fixed, and slices have to have this trait implemented in the standard library, it feels like a no-brainer.

Links and related work

N/A

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[pitaj]

I believe that in the past this kind of thing has caused type inference to fail, breaking existing code. I don't see any consideration in the ACP for this.

[clarfonthey]

I didn't consider that bit mostly because this didn't cause type inference issues for PartialEq (which does have the asymmetric implementation) and so I don't see why PartialOrd should be any different. Unless there's something else that would cause that?

[joshtriplett]

We reviewed this in today's libs-api meeting. Given the existing PartialEq implementations, this might be possible without widespread inference breakage. ACP accepted; go ahead and give it a shot, and do a crater run to see if it causes breakage.

Please make sure that there are PartialOrd implementations corresponding to the existing PartialEq implementations (e.g. Vec as well, not just [U]).