Support __richcmp__ in Python classes

[jdemeyer]

Sage has a lot of functionality to deal with "rich comparisons" using __richcmp__ in Cython or _richcmp_ in Python or Cython for subclasses of Element. However, we are still missing rich comparison support for Python classes which are not subclasses from Element.

A good example of this is RealSet in src/sage/sets/real_set.py. Currently, comparison is implemented using __cmp__. Changing this to Python 3 comparisons would normally require 6 methods (__eq__, __ne__, __lt__, __le__, __gt__, __ge__). It would be convenient to support this with just one __richcmp__ method like in Cython.

This ticket proposes:

1. Add a decorator richcmp_method which adds support for __richcmp__ to a Python class.

2. Implement RealSet.__richcmp__ using this.

[tscrim]

What about using @total_ordering to reduce the number of rich comparison methods? I know this is an abuse of terminology, but it does mean we only need to define __eq__ and __lt__. However, I generally do like the idea of having a consistent API.

[jdemeyer]

Replying to tscrim:

What about using @total_ordering to reduce the number of rich comparison methods?

1. @total_ordering reduces the number of rich comparison methods from 6 to 2. This ticket reduces it from 6 to 1.

2. @total_ordering is less efficient (if you only have == and <, you might need two calls to determine <=)

---

New commits:

​256bf19	Move richcmp stuff to new file richcmp.pyx
​b591b78	Support __richcmp__ in Python classes
​47f97ec	Implement RealSet comparisons using __richcmp__

[chapoton]

Note that from #22828, there is

def richcmp_by_eq_and_lt(left, right, op):

in

src/sage/rings/asymptotic/misc.py

that should also be moved to the common new place.

[jdemeyer]

Replying to chapoton:

Note that from #22828, there is

def richcmp_by_eq_and_lt(left, right, op):

in

src/sage/rings/asymptotic/misc.py

that should also be moved to the common new place.

Makes sense. I created #23109 for that.

[tscrim]

Typo in richcmp_method: mtehod. Have you run some timings to compare how this works versus direct implementation versus @total_ordering in Python classes? I can do this, but not for 2-3 days because I will be traveling.

[jdemeyer]

Replying to tscrim:

Have you run some timings to compare how this works versus direct implementation versus @total_ordering in Python classes? I can do this, but not for 2-3 days because I will be traveling.

I just did that, see cmp-timing.py​

First of all, for a plain equality check (@total_ordering is not involved in this), the timing is almost the same for __eq__ and __richcmp__, the latter being just slightly slower:

sage: load("cmp-timing.py")
sage: timeit('A1 == A2', number=1000000, repeat=100)
1000000 loops, best of 100: 281 ns per loop
sage: timeit('B1 == B2', number=1000000, repeat=100)
1000000 loops, best of 100: 293 ns per loop

Now, comparisons involving @total_ordering take almost twice or three times as much time:

sage: load("cmp-timing.py")
sage: timeit('A1 > A2', number=1000000, repeat=20)   # calls A2.__lt__(A1)
1000000 loops, best of 20: 557 ns per loop
sage: timeit('B1 > B2', number=1000000, repeat=20)
1000000 loops, best of 20: 292 ns per loop

sage: load("cmp-timing.py")
sage: timeit('A2 <= A1', number=1000000, repeat=20)  # Calls A2.__lt__(A1) and A2.__eq__(A1)
1000000 loops, best of 20: 820 ns per loop
sage: timeit('B2 <= B1', number=1000000, repeat=20)
1000000 loops, best of 20: 293 ns per loop

As one might expect, the time is roughly linear in the number of Python method calls.

[jdemeyer]

Small script to test timing

[tscrim]

Thank you for running those timings. That is more than enough to convince me. If tests pass, you can set a positive review on my behalf. Sleepy time for me now. :)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​acfd0aa

Typo

[vbraun]

This happened randomly:

sage -t --long src/sage/sets/real_set.py
**********************************************************************
File "src/sage/sets/real_set.py", line 701, in sage.sets.real_set.RealSet.__richcmp__
Failed example:
    cmp(I1, I2)
Expected:
    1
Got:
    -1
**********************************************************************
File "src/sage/sets/real_set.py", line 703, in sage.sets.real_set.RealSet.__richcmp__
Failed example:
    sorted([I1, I2])
Expected:
    [(0, 5], (1, 3]]
Got:
    [(1, 3], (0, 5]]
**********************************************************************
1 item had failures:
   2 of   6 in sage.sets.real_set.RealSet.__richcmp__
    [203 tests, 2 failures, 0.55 s]

[jdemeyer]

Confirmed. It seems that the category framework gets in the way. Commenting out this line fixes the problem

Parent.__init__(self, category = Sets())

[tscrim]

I really would not want to go backwards in category initalization for parents. Although the category methods should not be interfering. I don't see how they would cause problems...

[jdemeyer]

Replying to tscrim:

I really would not want to go backwards in category initalization for parents.

Sorry, I didn't say that we should remove that line. Just that removing that line fixes this specific problem that __richcmp__ doesn't work.

[jdemeyer]

OK, the real problem is that the richcmp_method decorator doesn't work with subclassing. It only works on the class where it is defined, not on subclasses. Given that the category framework creates a RealSet_with_category subclass, this breaks.

[tscrim]

Replying to jdemeyer:

Replying to tscrim:

I really would not want to go backwards in category initalization for parents.

Sorry, I didn't say that we should remove that line. Just that removing that line fixes this specific problem that __richcmp__ doesn't work.

I didn't mean to imply you were. I just wanted to make it clear that we didn't want to do this in case someone else came along and saw this.

[tscrim]

Replying to jdemeyer:

OK, the real problem is that the richcmp_method decorator doesn't work with subclassing. It only works on the class where it is defined, not on subclasses. Given that the category framework creates a RealSet_with_category subclass, this breaks.

Perhaps the way to go would be to bind __eq__ and friends to a particular class that compare with the __richcmp__?

[jdemeyer]

OK, I think the problem is that my trick doesn't add slot wrappers (attributes like __eq__ on the class). I'll try to add those wrappers and see if that works.

[jdemeyer]

New commits:

​b591b78	Support __richcmp__ in Python classes
​47f97ec	Implement RealSet comparisons using __richcmp__
​acfd0aa	Typo
​1569dda	Merge tag '8.0.beta10' into t/23102/acfd0aaea4de51b64c21fdd1a7a8d6e9174448de
​f52d5c3	Install slot wrappers for rich comparison methods

[tscrim]

If I understand correctly what is going on, then yes, this should work in general. So I'm going to set it to a positive review since it works AFAIK.

Erik, I'm cc-ing you in case you know something about the inner workings of Python and can confirm the code looks proper. If you don't, then no need to respond.

[jdemeyer]

Of course, none of this slot stuff is documented anywhere in the Python docs... the only way to figure it out is to read the Python source code.

[embray]

Why

if type(slotwrapper).__name__ != 'wrapper_descriptor':

and not explicitly something like

if type(slotwrapper) != PyWrapperDescr_Type:

?

[embray]

One other minor concern: If a class has both __richcmp__ and, say, __lt__, this will just silently override the __lt__. For consistency with Cython, I'd say having both should be an outright error (with Cython it will just raise a compiler error if you try to define __lt__ in a cdef class). So maybe it should raise a RuntimeError if a class tries to define both.

But that also raises the question of what to do with subclasses. If you subclass a class with __richcmp__ and add an __lt__ in the subclass, the subclass's __lt__ should take over. I think that's what will happen anyways.

But what if you subclass a class that has __lt__ and add __richcmp__ in the subclass?

[embray]

But what if you subclass a class that has __lt__ and add __richcmp__ in the subclass?

To answer my own question, this wouldn't be a concern I guess since this will just override the parent class's __lt__ and that's to be expected.

It would be good to have a test of subclassing and overriding one of the comparison operators though.

[vbraun]

ready to merge == positive review != let somebody else look at it first, Travis

[jdemeyer]

So, is it merged or not? I think Erik's comments make sense, but they could easily be addressed in a follow-up ticket.

[vbraun]

Not merged

[embray]

They could definitely be addressed in a followup ticket (if indeed my comments need addressing at all).

[embray]

As an aside, I wonder if there's ever been a proposal to actually support __richcmp__ in user-defined classes (in a manner similar to this, such that it would automatically implment the individual comparison methods). And if it has been proposed I wonder why it was rejected. I'm going to search around a bit for answers...

[embray]

A close reading of PEP-207 reveals:

The choice of six special methods was made over a single (e.g. __richcmp__) method to allow the dispatching on the opcode to be performed at the level of the C implementation rather than the user-defined method.

which makes perfect sense. But, if as Sage demonstrates, there's a usecase for a single user-defined __richcmp__ I don't see why it shouldn't be an option...

[tscrim]

As Jeroen and Erik said, I felt it could be merged into Sage and further changes could be handled on followup tickets.

---

New commits:

​b591b78	Support __richcmp__ in Python classes
​47f97ec	Implement RealSet comparisons using __richcmp__
​acfd0aa	Typo

[jdemeyer]

I'll work on it right now.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​49b6f76	Support __richcmp__ in Python classes
​d343d9d	Implement RealSet comparisons using __richcmp__
​3aac3cc	Typo
​86e9fcf	Install slot wrappers for rich comparison methods

[jdemeyer]

Travis: you put back the wrong branch. This is the original branch, rebased to 8.0.beta11.

[tscrim]

Ah, sorry; I had thought u/jdemeyer/acfd0aaea4de51b64c21fdd1a7a8d6e9174448de was just a trac formatting error.

[jdemeyer]

Replying to embray:

if type(slotwrapper) != PyWrapperDescr_Type:

Good point. It didn't occur to me to use the C/API for this. Python doesn't expose this type anywhere AFAIK, but the C/API does.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4d1021b

Further fixes and tests for richcmp_method

[jdemeyer]

I think this addresses all Erik's concerns.

[embray]

Replying to jdemeyer:

Replying to embray:

if type(slotwrapper) != PyWrapperDescr_Type:

Good point. It didn't occur to me to use the C/API for this. Python doesn't expose this type anywhere AFAIK, but the C/API does.

You can get at it in Python, for example, with type(bytes.__lt__), but in Cython you might as well just use the type directly since it's exposed by the C API.

[chapoton]

is this ready to go ?

[jdemeyer]

Erik?

[embray]

Yep, perfect--thanks.