Rust: Error in derived `PartialOrd` for structs based on types with incomparable elements.

[0ndorio]

If a type deriving PartialOrd wraps another type which contains incomparable elements - and therefore only defines an implementation of PartialOrd and not a Ord - the derived implementations of the le and ge functions are flawed.

The leads to a state where the internal type returns false as result of the expressions a <= b and b >= a for two incomparable elements a and b while the wrapper returns true. [[playground](https://play.rust-lang.org/?gist=e5a683321648f0df437ec9c861197e87&version=stable)]

If we look into the attached output of cargo-expand it becomes clear that both implementations ignore the the underlying type only implements PartialOrd and may contain incomparable elements which can't be checked by (a < b) || !(b < a) or (a > b) || !(a > b).

Expanded: Less or Equal

    #[inline]
    fn le(&self, __arg_0: &StructWithoutOrd) -> bool {
        match *__arg_0 {
            StructWithoutOrd(ref __self_1_0) => match *self {
                StructWithoutOrd(ref __self_0_0) => {
                    (*__self_0_0) < (*__self_1_0) || !((*__self_1_0) < (*__self_0_0)) && true
                }   
            },  
        }   
    }

Expanded: Greater or Equal

    #[inline]
    fn ge(&self, __arg_0: &StructWithoutOrd) -> bool {
        match *__arg_0 {
            StructWithoutOrd(ref __self_1_0) => match *self {
                StructWithoutOrd(ref __self_0_0) => {
                    (*__self_0_0) > (*__self_1_0) || !((*__self_1_0) > (*__self_0_0)) && true
                }   
            },  
        }   
    }

[leoyvens]

This is very weird because it's inconsistent with the behavior of PartialOrd for floats. This simplified case will print false :

#[derive(PartialOrd, PartialEq)]
struct MyFloat(f64);
fn main() {
    println!("{}", (0.0 / 0.0 >= 0.0) == (MyFloat(0.0 / 0.0) >= MyFloat(0.0)))
}

Which is highly inconsistent. This would be a difficult breaking change to make, perhaps not even worth fixing.

Edit: I asked on IRC and it seems this issue is somewhat known, but I don't see any other bugs tracking it.

[eddyb]

Why are comparison operators used more than once? This could cause exponential cost, at worst (in the depth of the value), especially for recursive structures.

cc @Manishearth @alexcrichton

[Manishearth]

We should just forward to .le(), yes?

This isn't a breaking change, seems like a bug and it doesn't break compilation.

[nox]

It's a change of behaviour that people may be relying on. Forwarding to .le doesn't help, given you need to do self.0 < other.0 || self.0 == other.0 && (self.1 < other.1 || …).

[0ndorio]

I can understand that a fix in such deep integrated code almost automatically involves a breaking change but I would still argue that its actually logically wrong and therefore should be fixed. A potential alternative way could be to add a new lint check which warns about using <= and => on types which only implement PartialOrd as the result of such a check may not lead to the expected result.

(A similar procedure was proposed by @oli-obk in rust-lang-nursery/rust-clippy#2626 for a related issue.)

[nox]

@0ndorio Oh yeah definitely, I do want to fix this issue and consider the current behaviour a bug too, I'm just pointing out that it is observable and thus people may be relying on it. I'm certainly not hoping that people are relying on it.

[varkor]

@eddyb: you need both comparison operations per pair of values because there are three conditions (<, > or unrelated); as far as I can tell, you can't reuse any of the operations.

[eddyb]

@varkor Can't you use partial_ord recursively?

[varkor]

~@eddyb: Oh, that's a good point. I'll update the PR to use partial_cmp instead.~

Actually, this is going to end up generating a ton of nested if expressions to use partial_cmp instead of the other operations, to make sure we only generate results lazily. It might still be a win for performance, but the generated code is going to be much messier.

[eddyb]

@varkor What do you mean, can't we rely on the Ordering chaining functionality?

[varkor]

https://github.com/rust-lang/rust/issues/49650#issuecomment-379467572 is addressed by #50011.

[leoyvens]

This issue is not totally fixed, only the performance issues were (thanks, @varkor!). Could someone reopen?

[varkor]

@leodasvacas: https://github.com/rust-lang/rust/pull/49881 fixed this originally, and then https://github.com/rust-lang/rust/pull/50011 followed up on it to fix the inefficiency.

[leoyvens]

@varkor Ah great, nevermind me then.