Can the trait bound on P be relaxed to PartialOrd?

[Zabot]

I was recently surprised by PriorityQueue popping items in a seemingly random order despite setting priorities when I inserted. I had implemented Ord::cmp by unwrapping PartialOrd::partial_cmp for some testing and since I didn't see any panics I thought things were working correctly, when in fact all of my comparisons were returning None.

As far as I can tell PriorityQueue doesn't actually call any function in Ord, just the comparison operators in bubble up, which always return false if partial_cmp is None. Would it make sense to relax the bound to P: PartialOrd, to make this behavior less surprising? Or alternatively use Ord::cmp explicitly instead of PartialOrd::lt? As it stands PriorityQueue is perfectly happy to operate on priorities that implement Ord by unconditionally panicking, despite the fact that Ord is explicitly required, which seems very surprising.

According to the docs for Ord if both Ord and PartialOrd are implemented, PartialOrd should always return Some(self.cmp(other)), which would also have solved my issue, but it relies on convention rather then the compiler to enforce that behavior.

Happy to follow up with a PR if there's a change warranted here!

[garro95]

I don't think it makes sense to relax the trait bound because there is no good behavior for priorities that cannot be compared: as you experienced, the resulting order may seem random.

On the other hand, panicking may be surprising as well if the trait bound required PartialOrd when it should have required Ord, that implies partial_cmp(a, b) == Some(cmp(a, b)).

I am not against explicitly using Ord::cmp, I only fear it could make the code less readable.

Regarding conventions, that is not the only one we rely on. In the past, for example, the k1 == k2 -> hash(k1) == hash(k2) rule that must hold when implementing Hash and Eq created confusion, and I added some wording in the documentation to make it clear.

Some words can be added for this property as well.

[Zabot]

Looks like cmp::Ordering has some helpers that I think would help with readability.

if a < b {
...
}

becomes

if a.cmp(b).is_lt() {
...
}

I agree the readability isn't quite as good. I personally tend to prefer named methods rather then overloaded operators when using traits to make it obvious that the operator may be non-trivial, but that's more of a personal preference rather then an objectively better. I do think its worth it here to avoid using PartialOrd by accident.

[garro95]

Feel free to open a PR with such changes and I'll review it