Opened 8 years ago
Closed 17 months 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:  sageduplicate/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 )
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 "^[^#]*[^az\._]cmp(" *.py git grep c "^[^#]*[^az\._]cmp(" *.pyx
This ticket is tracked as a dependency of metaticket 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 uservisible 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  
#25180  src/sage/dynamics/flat_surfaces/strata.py  deprecated in #20695 
#25180  src/sage/dynamics/interval_exchanges/labelled.py  deprecated in #20695 
#25180  src/sage/dynamics/interval_exchanges/reduced.py  deprecated in #20695 
#24930  src/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  
#24793  src/sage/misc/fast_methods.pyx  
#25778  src/sage/misc/lazy_import.pyx  The __cmp__ here returns an error since #21247 but is not removed. Full removal in #25778

#24899  src/sage/modular/modsym/p1list.pyx  
#25412  src/sage/modules/module.pyx  Here __cmp__ is only in the doc.

#25053  src/sage/monoids/free_monoid_element.py  
#25059  src/sage/monoids/string_monoid.py  
#25419  src/sage/numerical/linear_functions.pyx  Strange distinct uses of both old cmp and new richcmp 
#25623  src/sage/numerical/linear_tensor_element.pyx  Strange distinct uses of both old cmp and new richcmp 
#25060  src/sage/rings/polynomial/multi_polynomial_element.py  
#24931  src/sage/rings/real_mpfr.pyx  
#24980  src/sage/schemes/generic/ambient_space.py  
#24930  src/sage/stats/intlist.pyx  
#24791  src/sage/structure/unique_representation.py  __cmp__ only in the doc

#24980  src/sage/tensor/modules/free_module_morphism.py  
#25824  src/sage/structure/element.pyx  remaining calls to cmp() inside the documentation 
Attachments (9)
Change History (77)
comment:1 Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
comment:2 Changed 8 years ago by
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 definedcmp
or using the standard librarycmp
. 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!
 In Py2 "no_cmp" gives often wrong results, but always correct results when
 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 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:4 Changed 7 years ago by
 Dependencies set to #17175
comment:5 followups: ↓ 6 ↓ 7 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
 Cc jpflori added
comment:9 Changed 6 years ago by
 Component changed from distribution to python3
comment:10 Changed 5 years ago by
 Milestone changed from sage6.4 to sage7.4
 Type changed from PLEASE CHANGE to enhancement
comment:11 Changed 5 years ago by
 Milestone changed from sage7.4 to sage7.6
comment:12 Changed 5 years ago by
 Description modified (diff)
comment:13 Changed 5 years ago by
 Milestone changed from sage7.6 to sage8.0
comment:14 Changed 4 years ago by
 Description modified (diff)
 Milestone changed from sage8.0 to sage8.1
comment:15 Changed 4 years ago by
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 followup: ↓ 20 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
It looks like even if just implementing __eq__
, Cython adds its own slots for all the comparison operators that override any defined in the base classes. So that's kind of annoying.
comment:19 Changed 4 years ago by
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 4 years ago by
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 (newstyle) class then? The base class object
already has those slots:
>>> object.__lt__ <methodwrapper '__lt__' of type object at 0x7fe14ebdf0e0>
comment:21 followup: ↓ 23 Changed 4 years ago by
There remains also self.cmp_letters = cmp
in sage/combinat/words/words.py
EDIT: see #24383 for that
comment:22 Changed 4 years ago by
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 builtin 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 Pythonit shouldn't be doing identity comparison on the slot wrapper object itself.
comment:23 in reply to: ↑ 21 Changed 4 years ago by
Replying to chapoton:
There remains also
self.cmp_letters = cmp
insage/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 followup: ↓ 25 Changed 4 years ago by
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 ; followup: ↓ 26 Changed 4 years ago by
Replying to jdemeyer:
Sorry, I was wrong. Actually,
object.__eq__
is really the methodtype.__eq__
bound to theobject
instance:>>> object.__eq__(object) TrueSo 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 4 years ago by
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 followup: ↓ 28 Changed 4 years ago by
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 4 years ago by
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__ <methodwrapper '__lt__' of object object at 0x7f4ccf850070>
On Python 2, object
has neither __cmp__
nor __eq__
.
comment:29 followup: ↓ 30 Changed 4 years ago by
I must be missing your point. I'm not talking about Python 2.
comment:30 in reply to: ↑ 29 Changed 4 years ago by
comment:31 Changed 4 years ago by
 Description modified (diff)
 Keywords richcmp added
Adding a table or tracking modules that still need __cmp__
work (maybethis is just based on a grep and has not been closely reviewed).
comment:32 Changed 4 years ago by
 Description modified (diff)
comment:33 Changed 4 years ago by
 Description modified (diff)
comment:34 Changed 4 years ago by
 Description modified (diff)
comment:35 followup: ↓ 38 Changed 4 years ago by
 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 4 years ago by
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 columnperhaps I'll do that).
Even "deprecated" modules still need a ticket related to removing them if it's deprecated.
comment:37 Changed 4 years ago by
 Description modified (diff)
comment:38 in reply to: ↑ 35 ; followup: ↓ 40 Changed 4 years ago by
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 4 years ago by
 Description modified (diff)
comment:40 in reply to: ↑ 38 Changed 4 years ago by
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 4 years ago by
 Description modified (diff)
comment:42 Changed 4 years ago by
 Description modified (diff)
comment:43 Changed 4 years ago by
 Description modified (diff)
comment:44 Changed 4 years ago by
 Description modified (diff)
comment:45 Changed 4 years ago by
 Description modified (diff)
comment:46 Changed 4 years ago by
 Description modified (diff)
comment:47 Changed 4 years ago by
 Description modified (diff)
comment:48 Changed 4 years ago by
 Description modified (diff)
comment:49 Changed 4 years ago by
 Description modified (diff)
comment:50 Changed 4 years ago by
 Description modified (diff)
comment:51 Changed 4 years ago by
 Description modified (diff)
comment:52 Changed 4 years ago by
#22349 is a major open issue here.
comment:53 Changed 4 years ago by
 Description modified (diff)
comment:54 Changed 4 years ago by
 Description modified (diff)
comment:55 Changed 4 years ago by
 Description modified (diff)
comment:56 Changed 4 years ago by
 Description modified (diff)
comment:57 Changed 4 years ago by
 Description modified (diff)
comment:58 Changed 4 years ago by
 Description modified (diff)
comment:59 Changed 4 years ago by
 Dependencies #17175 deleted
 Milestone changed from sage8.1 to sage8.3
comment:60 Changed 4 years ago by
 Description modified (diff)
comment:61 Changed 4 years ago by
 Description modified (diff)
comment:62 Changed 4 years ago by
 Description modified (diff)
comment:63 Changed 4 years ago by
 Description modified (diff)
comment:64 Changed 4 years ago by
 Description modified (diff)
comment:65 Changed 3 years ago by
 Milestone changed from sage8.3 to sage8.4
update milestone 8.3 > 8.4
comment:66 Changed 3 years ago by
 Milestone changed from sage8.4 to sage8.5
comment:67 Changed 17 months ago by
 Milestone changed from sage8.5 to sageduplicate/invalid/wontfix
 Status changed from new to needs_review
Ready to close this? With only #22349 left open, the metaticket is less useful.
comment:68 Changed 17 months ago by
 Resolution set to fixed
 Status changed from needs_review to closed
ok, I guess this can be closed. Agreed.
I did some grepping to get a first impression of the amount of work required:
git grep P "def\s+__cmp__" wc l
git grep P "def\s+__eq__" wc l
git grep P "def\s+__ne__" wc l
git grep P "def\s+__lt__" wc l
git grep P "def\s+__le__" wc l
git grep P "def\s+__gt__" wc l
git grep P "def\s+__ge__" wc l
git grep P "\bcmp\s*\(" wc l
The conclusion seems that we have to implement rich comparison (i.e. define
__eq__
with__ne__
and__gt__
with the class decoratorfunctools.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!