Discussion: better derive for trait Eq

language design
1

TL;DR

adding a new type Derive (as a switch) on Ord, Eq, (and possibly Copy), to indicate whether derive PartialOrd, PartialEq, and Clone for them. By default it is False for compatiability issues, it will become True with some next edition.

Since there are not too much things to do, maybe we could just enable it in edition 2024.

Considering the following code:

use core::cmp::Ordering;
#[derive(Ord, PartialEq, Eq)]
struct Reversed<T:Ord>(T);
impl<T:Ord> PartialOrd for Reversed<T> {
    fn partial_cmp(&self, other:&Self) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
    }
}
fn main(){
    let a = &Reversed(1i32);
    let b = &Reversed(-1i32);
    println!("a {:?} than b, but a {:?} than b", a.partial_cmp(b), a.cmp(b))
    // a Some(Less) than b, but a Greater than b
}

Since PartialOrd is implemented by hand, and Ord is derived automatically from all its fields, there are some conflicts between PartialOrd and Ord.

It is documented that:

It’s easy to accidentally make cmp and partial_cmp disagree by deriving some of the traits and manually implementing others.

Violating these requirements is a logic error.

Since it is not happy to derive so many traits, and impl traits repeatly is not what we desired, several solutions are proposed.

This ACP is now, adding the following code:

// in mod std::marker
pub struct True {_:()} // for trait only, should not construct it.
pub struct False {_:()} // for trait only, should not construct it.
pub type DeriveDefault = False; // use edition to switch it to True.
trait Sealed{}
pub trait Bool {} : Sealed
impl Bool for True {}
impl Bool for False {}
// trait
trait Ord {
    type Derive: Bool = DeriveDefault; // old impls are not affected, new for impls, this will set to True, enables the automatic derive.
    ...
}
impl<T:Ord<Derive = True>> for PartialOrd {
    fn partial_cmp(&self, other:&Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

In case we do not need the automatic impl, we could just disable it by set Derive=False. Remain the Derive field not set and impl the Partial* method will now raise a compile error, (not a slient logic error).

Old alternatives that seems not appealing

The first solution, modify the #[derive(Ord)] to the version with PartialOrd:

// suppose `T:PartialOrd` and such `PartialOrd` is `Ord`.
trait Ord : PartialOrd {
    // changing cmp to provided method:
    fn cmp(&self, other:&Self) -> Ordering {
        assert_unsafe_precondition!(
            check_library_ub,
            "the PartialOrd is not Ord",
            ( res: Ordering = self.partial_cmp(other) ) => res.is_some(),
        );
        if let Some(res) = self.partial_cmp(other) {
            res
        } else {
            unsafe { core::hint::unreachable_unchecked() }
        }
    }
    // the rest part keeps the same
    ...
}
// In this case, #[derive(Ord)] only needs a `impl Ord for T {}`.

But such operation is either not efficient (have runtime check) or unsafe (cannot ensure partial_cmp always returns Some).

The second solution, propose several new trait, called TotalOrd and TotalEq, thay require 2 methods and provides another 5 methods:

/// same to PartialEq, expect it impl Eq automatically
trait TotalEq {
    // requires
    /// equal
    /// Tests for `self` and `other` values to be equal, and is used by `==`.
    #[must_use]
    fn eq(&self, other:&Self) -> bool;

    // provides
    /// Tests for `!=`. The default implementation is almost always sufficient,
    /// and should not be overridden without very good reason.
    #[inline]
    #[must_use]
    fn ne(&self, other:&Self) -> bool {
        !self.eq(other)
    }
}
trait TotalOrd : TotalEq {
    // requires
    /// Tests less than (for `self` and `other`) and is used by the `<` operator.
    fn lt(&self, other:&Self) -> bool;

    // provides
    /// Tests less than or equal to (for `self` and `other`) and is used by the
    /// `<=` operator.
    #[inline]
    #[must_use]
    fn le(&self, other:&self) -> bool {
        self.lt(other) || self.eq(other)
    }
    /// Tests greater than (for `self` and `other`) and is used by the `>`
    /// operator.
    #[inline]
    #[must_use]
    fn gt(&self, other:&Self) -> bool {
        other.lt(self)
    }
    /// Tests greater than or equal to (for `self` and `other`) and is used by
    /// the `>=` operator.
    #[inline]
    #[must_use]
    fn ge(&self, other:&Self) -> bool {
        other.le(self)
    }
    /// This method returns an ordering between self and other values
    #[must_use]
    fn cmp(&self, other:&Self) -> Ordering {
        if self.lt(other) {
            Ordering::Less
        } else if self.gt(other) {
            Ordering::Greater
        } else {
            Ordering::Equal
        }
    }
}

impl<T:TotalEq> PartialEq for T {
    ...
}
impl<T:TotalEq + PartialEq> Eq for T {
    ...
}
impl<T:TotalOrd> PartialOrd for T {
    ...
}
impl<T:TotalOrd + PartialOrd> Ord for T {
    ...
}

The restriction is same to implement Eq and Ord directly, but with extra benefit that we won't check whether the PartialEq and PartialOrd has the same ordering.

With the blanket implementation, we could just derive or implement TotalEq and TotalOrd for the struct we want to use.

// before
#[derive(PartialEq, PartialOrd, Eq, Ord)]
struct Foo(...);

// after
#[derive(TotalEq, TotalOrd)]
struct Foo(...);

//---

// before
#[derive(PartialEq, Eq)]
struct CustomFoo(Foo);
// SAFETY: we need to check whether a.partial_cmp(b) == Some(Equal) <==> a==b
impl PartialOrd for CustomFoo {...}
// SAFETY: we need to check whether a.partial_cmp(b) == Some(a.cmp(b))
impl Ord for CustomFoo {...}

//after
#[derive(TotalEq)]
struct CustomFoo(Foo);
// SAFETY: we need to check whether (a.gt(b) | b.gt(a))  ==  (a!=b)
impl TotalOrd for CustomFoo {...}

For derive: Although the struct impls Eq(+Ord) should be TotalEq(+TotalOrd), for backward compatiable reason, the derived methods require T:Ord for TotalOrd and T:Eq for TotalEq.

The third solution:

Since the first one lack of logical support (and introduce unsafe code for performance), and the second one actually repeating things (TotalOrd is Ord, the only difference is what subtrait they are implemented), a final solution might be, allow Ord being both the old version of Ord, which compitable with old code, and allow Ord be the TotalOrd under a switch. The implementation is chosen to:

#![feature(associated_type_defaults)] // without this line we have to modify all the implementations by adding a switch.
trait Foo : PartialFoo {
    /// A newly added switch to show which trait it should be derived
    /// switch it to `Self` will enable the blanket impl 
    /// ```
    /// impl<T:Foo<Derive = Self>> PartialFoo for T {}
    /// ```
    /// Since old code has only T:Foo<Derive = PhantomData<Self>>, the derive behavior is disable by default.
    type Derive:?Sized = std::marker::PhantomData<Self>;

    // methods
    fn foo(&self) {
        println!("f")
    }
}
trait PartialFoo {
    fn partial_foo(&self) {
        println!("pf")
    }
}
impl<T:Foo<Derive=Self>> PartialFoo for T{
    /// if the derived trait does not satisfy the need, just do not set `Derive` to `Self`, and manually impl PartialFoo.
    fn partial_foo(&self) {
        println!("partial_foo_impl")
    }
}

// old impl is Ok
impl Foo for i32 {}
impl PartialFoo for i32 {}

// new derive is Ok
impl Foo for u32 {
    type Derive = Self; // PartialFoo is automatically derived.
}
// customize partial_foo in Foo is Ok
impl Foo for () {
    type Derive = Self;
    fn impl_partial_foo(&self) {
        println!("customized partial_foo")
    }
}
fn main(){
    1i32.foo();
    1i32.partial_foo();
    1u32.foo();
    1u32.partial_foo();
    ().foo();
    ().partial_foo();
}
2

I do not understand why you implement PartialOrd and derive Ord instead of doing it the other way around. What I would like to see is a derive on the Ord impl like this

#[derive(PartialOrd, PartialEq, Eq)]
impl Ord for Foo {
    // ...
}

to make writing consistent comparisons easier.

3

Currently, it just wrong.

#[derive(PartialOrd, PartialEq, Eq)]
struct Foo(i32);
impl Ord for Foo {
    fn cmp(&self, other:&Self) -> std::cmp::Ordering {other.0.cmp(&self.0)}
}
fn main(){
    println!("Foo(1) {:?} ({:?}) than Foo (-1)", Foo(1).partial_cmp(&Foo(-1)), Foo(1).cmp(&Foo(-1)))
    // output: Foo(1) Some(Greater) (Less) than Foo (-1)
}

Actaully, since #[derive(PartialOrd)] have no idea whether Ord is implemented, it cannot rely on T:Ord, and thus derive PartialOrd from Ord by any macro, is just impossible.

1 Like
4

This is why I put it on the impl block of the trait and not the struct declaration.

1 Like
5

Your last solution looks really interesting! Unfortunately #![feature(associated_type_defaults)] seems to be blocking on (among other things) dyn Trait usage, and also, mentioning Self in default associated type seems problematic, why not use PhantomData<()> and ()?

1 Like
6

I just forgot that simple implementation.

// in mod std::marker
pub struct True {_:()} // for trait only, should not construct it.
pub struct False {_:()} // for trait only, should not construct it.
pub type DeriveDefault = False; // use edition to switch it to True.
trait Sealed{}
pub trait Bool {} : Sealed
impl Bool for True {}
impl Bool for False {}
// trait
trait Ord {
    type Derive: Bool = DeriveDefault; // old impls are not affected, new for impls, this will set to True, enables the automatic derive.
    ...
}

Why derive PartialEq? It should be done in case Eq is derived. We cannot derive Eq without PartialEq

What's more, such derive should be done by default. When you impl Ord for T, the PartialOrd should be automatically derived/implemented. With your derive macro, that procedure cannot be done automatically. This is why I choose this implementation.

7

To get convenient consistent comparison. I imagine these attributes emit the following additional code

impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool {
        self.cmp(other).is_eq()
    }
}
impl Eq for Foo {}
impl PartialOrd for Foo {
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

I like to explicitly have the implemented traits mentioned in the code in a way that shows how these are implemented. For example you also have to derive/implement Clone if you derive/implement Copy. To you have the current problems and the goals you try to reach with this stated somewhere? Is there alrady some prior discussion?

I would like to have a solution that reduces boiler plate but still makes clear what trait is implemented.

8

explicitly means freedom, you have freedom to choose what to derive and what not to derive, but since we have lots of lints against that freedom ( derive_ord_xor_partial_ord, Clippy Lints), It is convention that usually need, rather than some explicitly defined things which we could ignore.

What's more, there is another interesting thing that worth discussed: You want to derive at the trait level, but how could we derive PartialEq in that trait level?

#[derive(PartialEq)] // no information for T is obtained
impl Eq for T {} // derive at the trait level is less powerful than it is in struct level

If you want both struct derive attribute and trait derive attribute, that may confusing.

But, with struct level derive, many thing could be hide. There are 2 method to achieve it:

// derive Eq with impl_eq and impl_ne for PartialEq
impl Eq for T {
    type DerivePartial = True; // suppose we have that.
    fn impl_eq(&self, other:&Self) -> bool { /*derived code*/ }
    fn impl_ne(&self, other:&Self) -> bool {!self.eq(other)}
    // the impl_* fns will be send to PartialEq by impl <T:Eq<DerivePartial = True>> PartialEq for T{...}
}

// derive Eq, but actually it is PartialEq that been derived:
impl PartialEq for T {
...//derived PartialEq
}
impl Eq for T {}
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.