use correct naming for the comparison traits and add trait inheritance

[thestinger]

Updated description

The target end point: https://gist.github.com/alexcrichton/10945968

Original issue

• rename Ord -> PartialOrd
• rename TotalOrd -> Ord
• rename Eq -> PartialEq
• rename TotalEq -> Eq
• PartialOrd inherits from PartialEq
• Ord inherits from Eq
• Ord inherits from PartialOrd
• Eq inherits from PartialEq
• remove equals method (TotalEq deriving needs to be redone)
• deriving Ord also derives PartialOrd
• deriving Eq also derives PartialEq

An implementation of Eq will simply mean that the PartialEq implementation provides equivalence rather than partial equivalence. An Ord implementation will add a single cmp method and the guarantee of the PartialOrd implementation providing a total order.

This allows code generic over Float to use the operators, since it will inherit from PartialEq and PartialOrd. Code generic over Eq and Ord will also be able to use the operators, despite not being designed to handle a partial order.

[nikomatsakis]

We had some discussion about this on IRC. I think this option is probably the best compromise.

(For my own reference, and to summarize other bugs, iiuc there are 3 fundamental options:

1. All total ordered.
2. Types may implement both partially and totally ordered traits, and the behavior of those traits may different.
3. The totally ordered traits do not define additional methods but simply imply additional laws governing the same methods of the partially ordered traits. That is, the ordering for a single type must be consistent. Implies that f32 and f64 do not implement Ord but only PartialOrd, and hence implies some kind of newtyped float types.

I think Option 3 is probably a good compromise between total principle (option 1) and total pragmatism (option 2), and I think that Option 3 is what this proposal is about.)

[pnkfelix]

@thestinger So you decided not to use the name Cmp for the comparison operator defining trait after all? What changed your mind after writing this comment?

[glaebhoerl]

Might it be worth adding an explicit

partial_cmp(&self, other: &Self) -> Option<Ordering>;

to PartialOrd?

For symmetry, you could also mirror this structure on the Eq side (add enum DefiniteEq { DefinitelyEqual, DefinitelyInequal }, fn Eq::def_eq -> DefiniteEq, fn PartialEq::partial_def_eq -> Option<DefiniteEq> - not with these names), but maybe that's too elaborate.

The motivation in either case is that it's way more obvious from the types that it's a partial ordering/equality (or rather, what is meant by "partial") if there's a method that returns an Option.

[thestinger]

@pnkfelix: I couldn't think of a corresponding name for Eq and I think this is more clear.

@glaebhoerl: It might be worth adding something like that, but for now I just want to land the simplifications and then figure out how to even approach renaming due to deriving.

[pnkfelix]

Assigning 1.0, P-backcompat-libs. What is outlined here is better than what we have now, so it is fine to continue down this path.

(I just want to add the caveat that for 1.0, we will not necessarily adopt this particular strategy for resolving this problem in the end, but we do need to resolve how we are dealing with this problem before 1.0.)

[pnkfelix]

copying this etherpad link over here from #12579 for posterity: https://etherpad.mozilla.org/uaxtsKwv8w. It contains an audit of which code is using which traits, and some notes on use cases.

[thestinger]

I also added a basic description to the issue, since the discussions leading to this plan took place over many issues.

[alexcrichton]

I was thinking about this tonight, and I wanted to jot down my ideas before I forget.

---

I found a very useful tactic for thinking about this to start from the goal and go back to the implementation. From all the discussions I've heard around this, it sounds like "total equality" is the correct default, but the idea of "partial equality" must be a property of the type, hence there should be a distinction in the traits.

I thought of these examples for how I expect usage of Eq and friends to look like:

// Struct that has all the comparison operators
// Fails if anything is a float
#[deriving(Eq, Ord)]
struct Foo { ... }

// Manual implementation of the == operator (you get != for free)
impl Eq for Foo {
    fn eq(&self, other: &Foo) -> bool { ... }
}

// Manual implementation of all comparison operators
impl Ord for Foo {
    fn cmp(&self, other: &Foo) -> Ordering { ... }
}

// This function can use the == operator (same for Ord and comparison operators)
fn foo<T: Eq>() {}

// This function can also use the == operator (same for PartialOrd and comparison operators)
fn foo<T: PartialEq>() {}

With this in mind, the current plan of action (the checklist at the top) achieves almost all of these, except for the manual implementation ones. We have made explicit decision in the past to keep deriving simple (not have lots of options to customize the derived code). I would expect manual implementations of Eq and Ord to be fairly common. Having to explain why our default equality trait to implement is called PartialEq would make me quite sad.

Essentially, this proposed system makes it quite nice to use the comparison traits, but it makes it unwieldy to define them manually. This musing isn't very useful unless something good comes of it, so here's a todo list which may be able to address my concerns:

• trait Eq { fn eq(&self) -> bool; }
• trait PartialEq { fn equals(&self) -> bool; fn nequals(&self) -> bool; }
• trait Ord { fn cmp(&self) -> Ordering; }
• trait PartialOrd { /* four comparison methods returning bool */ }
• Keep the partial/total traits entirely separate. Do not link them with inheritance.
• Wire all operators to the partial traits.
• deriving(Trait) only derives the Trait trait for all traits. (deriving a total ordering doesn't also derive a partial ordering).
• impl<T: Eq> PartialEq for T { ... }
• impl<T: Ord> PartialOrd for T { ... }

With this checklist, I believe that both my constraints and the constraints at the top of this issue are all satisfied. The only snag is that the current version of the compiler will reject any manual implementations of PartialEq and PartialOrd (hence floats would have nothing implemented).

We were talking at the work week about lifting this restriction, and if others are amenable to this strategy, I would like to rekindle discussion about lifting the restriction. It looks that with the traits not linked to one another that you almost never have to see that the partial orderings exist, but you get them all for free. Additionally, deriving doesn't start doing super magical things for the comparison traits (deriving two traits actually), but rather it only ever derives one.

[thestinger]

For many types, it's going to be inefficient to define the methods returning bool by reusing cmp. LLVM is often going to fail to optimize it to the ideal implementation for non-trivial types with pointers, and with a generic implementation there's no way to provide an override. It would also mean that there would be an extra user-facing equality method, which I think is confusing.

In my opinion, there's a language flaw we should fix here and I don't think this is the only place it's going to come up. A numeric hierarchy or container hierarchy will run into these same issues, as some types can provide more guarantees than others. There will be cases where there's something to gain from splitting up the trait hierarchy a bit more, but it currently adds noise for every single implementation. While adding two more hooks to the compiler for the total ordering traits can sidestep most of the issues here, I think a more general solution would be nicer.

It should be possible to make use of trait inheritance for fine-grained trait hierarchies without placing a large burden on every implementation. I really liked @sfackler's proposal about this on IRC and have been thinking about it some more. If the language allowed you to implement methods from supertraits in the same implementation block, the syntactic noise would go away. It would also mean that deriving would still only be outputting a single implementation block, but I don't think it's an incredibly important concern. With a generic implementation, you're just as unable to define the PartialEq trait yourself after deriving Eq.

[alexcrichton]

If performance is the only concern, I think that it can be circumvented where necessary. You can always create a newtype wrapper and implement PartialEq directly. It would require that the consumer uses a PartialEq instead of Eq bound, but if you're dealing with very performance sensitive code you're likely at liberty to change that already. It doesn't quite sound like a showstopper to me.

It's tough to consider this in a world where you can implement multiple traits in one block as I'm not quite sure how that would all work out. It's certainly RFC-worthy, and I'd like to see that before going down the rabbit hole of figuring out how it would interact with everything else.

[thestinger]

The performance issue here is sometimes a large one. If the methods are not implemented directly on some types, it can perform 2 units of work (< then ==) instead of one. This sometimes involves more than one pass over a sequence, etc. if there's not an efficient single-pass cmp implemented or even possible.

[alexcrichton]

Another thought to address your concern on performance, how about:

trait Ord {
    /* four comparison methods (default methods) */
    fn cmp(&self, other: &Self) -> Ordering;
}

That should allow overriding where necessary for performance and the PartialOrd trait would just call the Ord trait's methods.

I also think that RFC 48 would enable the solution I outlined above.

[alexcrichton]

This is what I'm thinking: https://gist.github.com/alexcrichton/10945968

[thestinger]

@alexcrichton: Assuming the trait changes allow doing it that way, I fully support it. I haven't yet read the RFC though... there are a lot of them.

[liigo]

@alexcrichton Could the trait that has method cmp be named Cmp? Currently most traits have the same name with its major method. (Eq/eq, Drop/drop, etc.)

[thestinger]

I think Ord is a better name because it gets across that it provides an ordering. The cmp method is not used nearly as often as the comparison methods via the operator overloads. This also provides an obvious name for the partial ordering equivalent (PartialOrd).

[pnkfelix]

(perhaps another way to satisfy @liigo would be to name the method in question ord instead of cmp. But I don't actually care terribly much about this particular bikeshed.)

[liigo]

I'm OK for Ord/ord
2014年4月18日 上午6:16于 "Felix S Klock II" notifications@github.com写道：

(perhaps another way to satisfy @Liligo would be to name the method in
question ord instead of cmp. But I don't actually care terribly much
about this particular bikeshed.)

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/12517#issuecomment-40769253
.

[sfackler]

Note that all of the default implementations in @alexcrichton's gist above need to be removed for PartialEq and PartialOrd. They assume total equality/ordering which would mean that the author should be implementing the other trait. I'm writing up an RFC to tweak some of this.

[sfackler]

@alexcrichton would types implementing TotalOrd also implement PartialOrd? It seems like they should but wouldn't it require some compiler magic in this case?

EDIT: Nevermind, I totally misread that.

[sfackler]

How would the automatic implementation setup work with wrapper types that want to implement whichever of the cmp traits the wrapped type implements?

[sfackler]

Here's an updated version of the gist with the default methods removed: https://gist.github.com/sfackler/80c6d544701937ad4ce6

[brson]

@alexcrichton What's the state of this? Is it really just deriving? Do we really need that or can we declare victory?

[alexcrichton]

This is mainly waiting on trait reform to land first. With trait reform it will be possible to say just deriving(Eq) and it will no longer be necessary (in fact, impossible!) to implement both Eq and PartialEq

[japaric]

I think this will need "negative bounds" to avoid "conflicting implementations" in some instances:

impl<T: Eq> PartialEq for T {  //~ error: conflicting implementations for trait `PartialEq`
    fn eq(&self, other: &T) -> bool { Eq::eq(self, other) }
    fn ne(&self, other: &T) -> bool { !Eq::eq(self, other) }
}

impl<T: Eq> Eq for [T, ..2] {
    fn eq(&self, other: &[T, ..2]) -> bool { /* */ }
}

impl<T: PartialEq> PartialEq for [T, ..2] {  // note: note conflicting implementation here
    fn eq(&self, other: &[T, ..2]) -> bool { /* */ }
}

You can see why this is the case, with the following example:

1. You manually impl Eq for int
2. Because of the first blanket impl, int gets PartialEq for free
3. Because of the second impl, and since int: Eq (1), now [int, ..2] implements Eq
4. Because of the first blanket impl, [int, ..2] gets PartialEq for free as well
5. Because of the third impl and since int: PartialEq (2), [int, ..2] gets another PartialEq implementation, which conflicts with the one from (4).

The "proper" solution is to add a negative bound to third impl:

impl<T: PartialEq + !Eq> PartialEq for [T, ..2] {
    fn eq(&self, other: &[T, ..2]) -> bool { /* */ }
}

That way (5) won't happen, and no implementation conflict will arise.

As a work-around (until we get negative bounds) we can just drop the third impl. In that case float ergonomics will suffer, for instance [0f32, 1.] == [0., 1.] won't work. To ease the pain we could manually impl PartialEq for [f32, ..N] up to N = 32, etc.

[aturon]

@japaric Unfortunately, similar problems crop up for other types, like tuples. Negative bounds would indeed solve this problem, but they are very unlikely to happen for 1.0. We need a different plan here.

[glaebhoerl]

See also #17884 which has the same issue.

[aturon]

@alexcrichton I believe this is as done as it's going to be. Shall we close?

[alexcrichton]

I believe so as well. Woohoo!