Opened 6 years ago

Closed 13 days ago

#16537 closed enhancement (fixed)

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

Reported by: wluebbe Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: python3 Keywords: python3, richcmp
Cc: jpflori Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by chapoton)

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

#22349
Deprecate sorting of Graph vertices and edges by default

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
#24831src/sage/categories/functor.pyx
#24930src/sage/crypto/boolean_function.pyx
#25180src/sage/dynamics/flat_surfaces/strata.py deprecated in #20695
#25180src/sage/dynamics/interval_exchanges/labelled.py deprecated in #20695
#25180src/sage/dynamics/interval_exchanges/reduced.py deprecated in #20695
#24930src/sage/finance/time_series.pyx
#25063 src/sage/interfaces/axiom.py
#25063 src/sage/interfaces/giac.py
#25063 src/sage/interfaces/interface.py
#25063 src/sage/interfaces/lisp.py
#25063 src/sage/interfaces/maple.py
#25063 src/sage/interfaces/mathematica.py
#25063 src/sage/interfaces/polymake.py
#25063 src/sage/interfaces/r.py
#24793src/sage/misc/fast_methods.pyx
#25778src/sage/misc/lazy_import.pyx The __cmp__ here returns an error since #21247 but is not removed. Full removal in #25778
#24899src/sage/modular/modsym/p1list.pyx
#25412src/sage/modules/module.pyx Here __cmp__is only in the doc.
#25053src/sage/monoids/free_monoid_element.py
#25059src/sage/monoids/string_monoid.py
#25419src/sage/numerical/linear_functions.pyx Strange distinct uses of both old cmp and new richcmp
#25623src/sage/numerical/linear_tensor_element.pyx Strange distinct uses of both old cmp and new richcmp
#25060src/sage/rings/polynomial/multi_polynomial_element.py
#24931src/sage/rings/real_mpfr.pyx
#24980src/sage/schemes/generic/ambient_space.py
#24930src/sage/stats/intlist.pyx
#24791src/sage/structure/unique_representation.py __cmp__ only in the doc
#24980src/sage/tensor/modules/free_module_morphism.py
#25824src/sage/structure/element.pyxremaining calls to cmp() inside the documentation

Attachments (9)

experiments-with-rich-comparison.py (1.5 KB) - added by wluebbe 6 years ago.
Python script to demonstrate some "features" of rich comparison.
test-rich-comparison-python-2.7.6.txt (15.9 KB) - added by wluebbe 6 years ago.
test-rich-comparison-python-3.4.0.txt (15.9 KB) - added by wluebbe 6 years ago.
cmp-comparison-1.py (1.3 KB) - added by wluebbe 6 years ago.
cmp-comparison-python-2.7.6.txt (3.8 KB) - added by wluebbe 6 years ago.
cmp-comparison-python-3.4.0.txt (3.7 KB) - added by wluebbe 6 years ago.
rich-cmp-comparison-1.py (1.7 KB) - added by wluebbe 6 years ago.
rich-comparison-python-2.7.6.txt (5.1 KB) - added by wluebbe 6 years ago.
rich-comparison-python-3.4.0.txt (2.9 KB) - added by wluebbe 6 years ago.

Download all attachments as: .zip

Change History (77)

comment:1 Changed 6 years ago by 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!

Changed 6 years ago by wluebbe

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

Changed 6 years ago by wluebbe

Changed 6 years ago by wluebbe

Changed 6 years ago by wluebbe

Changed 6 years ago by wluebbe

Changed 6 years ago by wluebbe

Changed 6 years ago by wluebbe

Changed 6 years ago by wluebbe

Changed 6 years ago by wluebbe

comment:2 Changed 6 years ago by 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.

comment:3 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:4 Changed 6 years ago by aapitzsch

  • Dependencies set to #17175

comment:5 follow-ups: Changed 6 years ago by rws

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

comment:6 in reply to: ↑ 5 Changed 6 years ago by 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__.

comment:7 in reply to: ↑ 5 Changed 6 years ago by 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__.

comment:8 Changed 5 years ago by jpflori

  • Cc jpflori added

comment:9 Changed 4 years ago by jdemeyer

  • Component changed from distribution to python3

comment:10 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-7.4
  • Type changed from PLEASE CHANGE to enhancement

comment:11 Changed 4 years ago by chapoton

  • Milestone changed from sage-7.4 to sage-7.6

comment:12 Changed 4 years ago by chapoton

  • Description modified (diff)

comment:13 Changed 3 years ago by chapoton

  • Milestone changed from sage-7.6 to sage-8.0

comment:14 Changed 3 years ago by chapoton

  • Description modified (diff)
  • Milestone changed from sage-8.0 to sage-8.1

comment:15 Changed 3 years ago by 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__.

comment:16 follow-up: Changed 3 years ago by 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.

comment:17 Changed 3 years ago by 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.

comment:18 Changed 3 years ago by 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.

Last edited 3 years ago by embray (previous) (diff)

comment:19 Changed 3 years ago by embray

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

comment:20 in reply to: ↑ 16 Changed 3 years ago by 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>

comment:21 follow-up: Changed 3 years ago by chapoton

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

EDIT: see #24383 for that

Last edited 3 years ago by chapoton (previous) (diff)

comment:22 Changed 3 years ago by 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.

Last edited 3 years ago by embray (previous) (diff)

comment:23 in reply to: ↑ 21 Changed 3 years ago by 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.

comment:24 follow-up: Changed 3 years ago by 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.

comment:25 in reply to: ↑ 24 ; follow-up: Changed 3 years ago by 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.

comment:26 in reply to: ↑ 25 Changed 3 years ago by 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.

comment:27 follow-up: Changed 3 years ago by 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.

comment:28 in reply to: ↑ 27 Changed 3 years ago by 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__.

comment:29 follow-up: Changed 3 years ago by embray

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

comment:30 in reply to: ↑ 29 Changed 3 years ago by jdemeyer

Replying to embray:

I'm not talking about Python 2.

Yes, I understood that now..

comment:31 Changed 3 years ago by embray

  • Description modified (diff)
  • Keywords richcmp added

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).

comment:32 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:33 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:34 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:35 follow-up: Changed 3 years ago by jdemeyer

  • Description modified (diff)

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 !=.

comment:36 Changed 3 years ago by 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.

comment:37 Changed 3 years ago by embray

  • Description modified (diff)

comment:38 in reply to: ↑ 35 ; follow-up: Changed 3 years ago by 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.

comment:39 Changed 3 years ago by embray

  • Description modified (diff)

comment:40 in reply to: ↑ 38 Changed 3 years ago by 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 :-)

comment:41 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:42 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:43 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:44 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:45 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:46 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:47 Changed 3 years ago by chapoton

  • Description modified (diff)

comment:48 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:49 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:50 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:51 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:52 Changed 2 years ago by jdemeyer

#22349 is a major open issue here.

comment:53 Changed 2 years ago by jdemeyer

  • Description modified (diff)

comment:54 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:55 Changed 2 years ago by embray

  • Description modified (diff)

comment:56 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:57 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:58 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:59 Changed 2 years ago by chapoton

  • Dependencies #17175 deleted
  • Milestone changed from sage-8.1 to sage-8.3

comment:60 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:61 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:62 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:63 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:64 Changed 2 years ago by chapoton

  • Description modified (diff)

comment:65 Changed 2 years ago by vdelecroix

  • Milestone changed from sage-8.3 to sage-8.4

update milestone 8.3 -> 8.4

comment:66 Changed 23 months ago by chapoton

  • Milestone changed from sage-8.4 to sage-8.5

comment:67 Changed 2 weeks ago by slelievre

  • Milestone changed from sage-8.5 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

Ready to close this? With only #22349 left open, the meta-ticket is less useful.

comment:68 Changed 13 days ago by chapoton

  • Resolution set to fixed
  • Status changed from needs_review to closed

ok, I guess this can be closed. Agreed.

Note: See TracTickets for help on using tickets.