Python 3 preparation: Use "rich comparison" - std function cmp() is gone, method __cmp__ is ignored

[wluebbe]

Since Py2.1 there are the rich comparison special methods (__eq__, __ne__, __lt__, __le__, __gt__, __ge__) to implement comparison operators (==, !=, <, <=, >, >= respectively) for custom classes.

This is more flexible (but somewhat more tedious) than defining the special method __cmp__.

In Py3 the special method __cmp__ is ignored. The standard function cmp() (which is mostly used to implement __cmp__ methods) is gone.

One may define a replacement function like

def cmp(a, b):
    return (a > b) - (a < b)

But this does not improved performance. And it does not seem forward looking ...

Unfortunately __cmp__ and cmp() are used a LOT in Sage. And the migration to rich comparison can not be done purely mechanical :-(

Since Py2.7 there is a class decorator ​functools.total_ordering to help to create the full set of special method __lt__, __le__, __gt__, __ge__ when given one of those.
See Lennart Regebro's ​Chapter: Use rich comparison operators for a more detailed discussion.

Useful tool to see the size of the remaining problem:

git grep -c "^[^#]*[^a-z\._]cmp(" *.py
git grep -c "^[^#]*[^a-z\._]cmp(" *.pyx

This ticket is tracked as a dependency of meta-ticket ticket:15980.

---

Progress

Several tickets have already been submitted and merged for fixing __cmp__ -> __richcmp__ issues in Python 3. The remaining issues will be tracked here:

Open

No results

In Progress

No results

Modules needing work

The following modules still contain __cmp__ either in user-visible classes or in tests that may need to be addressed for Python 3.

Ticket	Module	Notes
#24831	src/sage/categories/functor.pyx
#24930	src/sage/crypto/boolean_function.pyx
#?????	src/sage/dynamics/flat_surfaces/strata.py	deprecated
#?????	src/sage/dynamics/interval_exchanges/labelled.py	deprecated
#?????	src/sage/dynamics/interval_exchanges/reduced.py	deprecated
#24930	src/sage/finance/time_series.pyx
#?????	src/sage/interfaces/axiom.py
#?????	src/sage/interfaces/giac.py
#?????	src/sage/interfaces/interface.py
#?????	src/sage/interfaces/lisp.py
#?????	src/sage/interfaces/maple.py
#?????	src/sage/interfaces/mathematica.py
#?????	src/sage/interfaces/polymake.py
#?????	src/sage/interfaces/r.py
#24793	src/sage/misc/fast_methods.pyx
#?????	src/sage/misc/lazy_import.pyx	The __cmp__ here returns an error since #21247 but is not removed.
#24899	src/sage/modular/modsym/p1list.pyx
#?????	src/sage/modules/module.pyx	Here __cmp__is only in the doc.
#?????	src/sage/monoids/free_monoid_element.py
#?????	src/sage/monoids/string_monoid.py
#?????	src/sage/numerical/linear_functions.pyx
#?????	src/sage/numerical/linear_tensor_element.pyx
#?????	src/sage/rings/polynomial/multi_polynomial_element.py
#24931	src/sage/rings/real_mpfr.pyx
#?????	src/sage/schemes/generic/ambient_space.py
#24930	src/sage/stats/intlist.pyx
#?????	src/sage/structure/unique_representation.py
#?????	src/sage/tensor/modules/free_module_morphism.py

[wluebbe]

I did some grepping to get a first impression of the amount of work required:

git grep -P "def\s+__cmp__" |wc -l	377
git grep -P "def\s+__eq__" |wc -l	170
git grep -P "def\s+__ne__" |wc -l	70
git grep -P "def\s+__lt__" |wc -l	29
git grep -P "def\s+__le__" |wc -l	18
git grep -P "def\s+__gt__" |wc -l	21
git grep -P "def\s+__ge__" |wc -l	18
git grep -P "\bcmp\s*\(" |wc -l	1042

The conclusion seems that we have to implement rich comparison (i.e. define __eq__ with __ne__ and __gt__ with the class decorator functools.total_ordering) for about 350 classes!

And then there are those 1000+ calls to cmp.

And unfortunately the changes are mostly not syntactical but they require insight into the code!

[wluebbe]

Python script to demonstrate some "features" of rich comparison.

[wluebbe]

Some remarks on the attached files:

• The 1st script shows the effects of varying which of the special methods __eq__, __ne__, __lt__ and @total_ordering are defined. The 2nd and 3rd files show the results for Py2 and Py3 respectively.
  • In Py2 all of ("eq", "ne", "lt", "total") must be used to always obtain correct results.
  • In Py3 it appears that "ne" is implied (be "eq").
  • For correct behavior in Py2 and Py3 all of "eq", "ne", "lt", "total" should be used.
• The 4th script shows the results of the comparison operators when defining no __cmp_ or using a self defined cmp or using the standard library cmp. The 5th and 6th files show the results for Py2 and Py3 respectively.
  • In Py2 "no_cmp" gives often wrong results, but always correct results when __cmp__ is defined.
  • In Py3 there are always type errors for "lt", "le", "gt"and "ge". For "eq" and "ne" some wrong and some correct.
  • __cmp__ does not work in Py3! Rich comparison must be implemented!
• The 7th script shows whether it possible to define the rich comparison special methods using cmp. The 8nd and 9th files show the results for Py2 and Py3 respectively.
  • In Py2 it is possible.
  • In Py3 one needs a user defined cmp function that is based on < and >.
  • Both in Py2 and Py3 @total_ordering is required.

[rws]

Can the work be reduced by including the code in ​http://www.voidspace.org.uk/python/articles/comparison.shtml into the SageObject class?

[nbruin]

Replying to rws:

Can the work be reduced by including the code in ​http://www.voidspace.org.uk/python/articles/comparison.shtml into the SageObject class?

I suspect that sage.structure.element.Element is a better location for it, since SageObject doesn't have any comparison infrastructure, and Element has.

In any case, the quoted code cannot be used verbatim, since these classes are cdef cython, where the interface is via the __richcmp__ special method, not the various __eq__ etc.

Element already has a __richcmp__, as well as a __cmp__. Precedence rules for comparison lookup in Python 2 imply that __cmp__ should never be triggered. The implementation there in some branches will try to look up __cmp__. This would be a good place to start looking into how much we really depend on __cmp__.

[jdemeyer]

Currently, a Sage Element already implements rich comparison using __cmp__/_cmp_/_cmp_c_impl (for simplification of this, see #17890). In my opinion, there is nothing wrong with keeping that behaviour even in Python 3.

My conclusion from this is that the problem really is cmp() and not __cmp__.

[chapoton]

There is no longer any call of cmp() in the code. There remains a few in the doc.

And probably we still need to convert a few __cmp__ to __richcmp__.

[embray]

As a word of warning, it seems that @total_ordering does not work with pure Python classes that have a Cython base class that implements __richcmp__, as it will inherit all the generated slots from the base class. For Element classes they can implement _richcmp_, but I'm not sure what the best solution is in general.

[embray]

In particular I ran into this with a class that was derived from WithEqualityById, which implements __richcmp__. Looking at its __richcmp__, though, it really shouldn't have one, and should only implement __eq__ I think, since the ordering operators are all NotImplemented anyways.

[embray]

It looks like even if just implementing __eq__, CPython adds its own slots for all the comparison operators that override any defined in the base classes. So that's kind of annoying.

[embray]

Oh well, I forgot Jeroen did richcmp_method, even though I think I reviewed it. That should be preferred over total_ordering probably.

[jdemeyer]

Replying to embray:

As a word of warning, it seems that @total_ordering does not work with pure Python classes that have a Cython base class that implements __richcmp__, as it will inherit all the generated slots from the base class.

Why does this problem not appear for every (new-style) class then? The base class object already has those slots:

>>> object.__lt__
<method-wrapper '__lt__' of type object at 0x7fe14ebdf0e0>

[chapoton]

There remains also self.cmp_letters = cmp in sage/combinat/words/words.py

EDIT: see #24383 for that

[embray]

That's exactly the problem. The way total_ordering implemented it does something like:

for op in ['__lt__', '__gt__', ...]:
    if getattr(cls, op, None) is not getattr(object, op, None):
        # Do something...

So if there is a built-in base class that is not object it fails, even if it's still wrapping the standard implementation of that slot. I would consider this a bug in Python--it shouldn't be doing identity comparison on the slot wrapper object itself.

[embray]

Replying to chapoton:

There remains also self.cmp_letters = cmp in sage/combinat/words/words.py

I think my plan was to just remove that outright since it's deprecated for some time and nothing uses it.

[jdemeyer]

Sorry, I was wrong. Actually, object.__eq__ is really the method type.__eq__ bound to the object instance:

>>> object.__eq__(object)
True

So the type object does not have rich comparison slots.

[embray]

Replying to jdemeyer:

Sorry, I was wrong. Actually, object.__eq__ is really the method type.__eq__ bound to the object instance:

>>> object.__eq__(object)
True

So the type object does not have rich comparison slots.

To be clear (and part of the problem) is that there's only one rich comparison slot (tp_richcompare). So if even one rich comparison operator is overloaded in a cdef class (say, __eq__), then all the rich comparison methods get new slot wrappers rather than inheriting them from object, even though the implementations for those operators are still the defaults.

[jdemeyer]

Replying to embray:

all the rich comparison methods get new slot wrappers rather than inheriting them from object

As I said, I was wrong: object does not implement rich comparison:

>>> a = object()
>>> a.__lt__
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'object' object has no attribute '__lt__'

So rich comparison obviously cannot be inherited from object.

[embray]

You must be looking at Python 2. On Python 3 it does. There's just a slight difference in where it inherits the default behavior from.

[jdemeyer]

Replying to embray:

You must be looking at Python 2. On Python 3 it does. There's just a slight difference in where it inherits the default behavior from.

Right!

Python 3.4.1 (default, Sep  4 2015, 12:50:14) 
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> a = object()
>>> a.__lt__
<method-wrapper '__lt__' of object object at 0x7f4ccf850070>

On Python 2, object has neither __cmp__ nor __eq__.

[embray]

I must be missing your point. I'm not talking about Python 2.

[jdemeyer]

Replying to embray:

I'm not talking about Python 2.

Yes, I understood that now..

[embray]

Adding a table or tracking modules that still need __cmp__ work (maybe--this is just based on a grep and has not been closely reviewed).

[jdemeyer]

For cdef classes in Cython code, this will be slightly easier with Cython 0.28 since that allows using Python methods like __eq__ instead of __richcmp__. That makes sense in particular when you only really want to implement == and !=.

[embray]

I'm still working on organizing some of these things. Instead of putting notes in the "ticket" column please just put notes in the module column (or a separate column--perhaps I'll do that).

Even "deprecated" modules still need a ticket related to removing them if it's deprecated.

[embray]

Replying to jdemeyer:

For cdef classes in Cython code, this will be slightly easier with Cython 0.28 since that allows using Python methods like __eq__ instead of __richcmp__. That makes sense in particular when you only really want to implement == and !=.

Sort of. There's a bug in Cython that makes it impossible to compile such code if the comparison method has a docstring.

[jdemeyer]

Replying to embray:

Sort of. There's a bug in Cython that makes it impossible to compile such code if the comparison method has a docstring.

That's why I said Cython 0.28 :-)