Tested with version 3.2a2. Not tested on version 2.7.

The current implementation of functools.total_ordering generates a stack overflow because it implements the new comparison functions with inline operator, which the Python interpreter might reverse if "other" does not implement them. Reversing the comparison makes the interpreter call again the lambda function for comparison generating a stack overflow.

Run the attached test file for an example of this behavior.

Attached there is a solution of the problem, by implementing each comparison only with the class __xx__ and __eq__ operators.

Also in the file there is a complete test suite for it.

Thanks, this is a good idea.

Thanks for the report and patch.

Fixed. See r87853.

This also affects Python 2.7, where it hasn't been fixed. Maybe reopen it?

FWIW, I just tested svnmerging the revision, the patch applied with minor merge conflicts and the test suite passes.

Éric, would you like to apply this to 2.7?

New changeset 94c158199277 by Éric Araujo in branch '2.7':
Fix the total_ordering decorator to handle cross-type comparisons
http://hg.python.org/cpython/rev/94c158199277

This is not fixed. The accepted fix doesn't take NotImplemented into account, with the result that comparing two mutually-incomparable objects whose ordering operations were generated with total_ordering causes a stack overflow instead of the expected "TypeError: unorderable types: Foo() op Bar()".

I've attached a fix for this. It properly takes NotImplemented into account. It also generates __eq__ from __ne__ and vice versa if only one of them exists.

I'm not sure that we really care about handling NotImplemented (practicality beats purity). At some point, if someone writing a class wants complete control over the rich comparison methods, then they're going to have to write those methods.

But it seems pointless to force someone to implement all of the rich comparison methods when they may want to do something as simple as this:

class Foo:
    ...
    def __lt__(self, other):
        if not isinstance(other, Foo):
            return NotImplemented
        return self.some_value < other.some_value

It may seem pointless, but it takes less than a minute to do it and it would be both faster and clearer to do it manually. There's a limit to how much implicit code generation can or should be done automatically.

Also, I'm not too keen on the feature creep, or having the tool grow in complexity (making it harder to understand what it actually does). I would also be concerned about subtly changing the semantics for code that may already be using total_ordering -- the proposed change is probably harmless in most cases with only a minor performance hit, but it might break some code that currently works.

BTW, in Py3.x you get __ne__ for free whenever __eq__ is supplied.

Ok. I did write that against Python 2, so I wasn't aware of __eq__ and __ne__. I'll keep that in mind.

I am curious, however, as to how this could break existing code. It seems like code that relies on a stack overflow is already broken as it is.

I am curious, however, as to how this could break existing code.
It seems like code that relies on a stack overflow is already
broken as it is.

Probably so. I worry about changes in semantics but it might be harmless.

I like Nick Coghlan's suggestion in msg140493, but I think he was giving up too soon in the "or" cases, and I think the confusion could be slightly reduced by some re-spellings around return values and comments about short-circuiting.

def not_op(op, other):
# "not a < b" handles "a >= b"
# "not a <= b" handles "a > b"
# "not a >= b" handles "a < b"
# "not a > b" handles "a <= b"
op_result = op(other)
if op_result is NotImplemented:
return NotImplemented
return not op_result

def op_or_eq(op, self, other):
    # "a < b or a == b" handles "a <= b"
    # "a > b or a == b" handles "a >= b"
    op_result = op(other)
    if op_result is NotImplemented
        return self.__eq__(other) or NotImplemented
    if op_result:
        return True
    return self.__eq__(other)

def not_op_and_not_eq(op, self, other):
    # "not (a < b or a == b)" handles "a > b"
    # "not a < b and a != b" is equivalent
    # "not (a > b or a == b)" handles "a < b"
    # "not a > b and a != b" is equivalent
    op_result = op(other)
    if op_result is NotImplemented:
        return NotImplemented
    if op_result:
        return False
    return self.__ne__(other)

def not_op_or_eq(op, self, other):
    # "not a <= b or a == b" handles "a >= b"
    # "not a >= b or a == b" handles "a <= b"
    op_result = op(other)
    if op_result is NotImplemented:
        return self.__eq__(other) or NotImplemented
    if op_result:
        return self.__eq__(other)
    return True

def op_and_not_eq(op, self, other):
    # "a <= b and not a == b" handles "a < b"
    # "a >= b and not a == b" handles "a > b"
    op_result = op(other)
    if op_result is NotImplemented:
        return NotImplemented
    if op_result:
        return self.__ne__(other)
    return False

Raymond, one of the devs here at the PyCon AU sprints has been looking into providing an updated patch for this. Do you mind if I reassign the issue to myself to review their patch (once it is uploaded)?

Attaching patch with Nick Coghlan's suggested code from msg140493 and associated tests. The tests extend the single test case that had already been added for earlier changes based on this bug. The tests check that a TypeError is raised, rather than a stack overflow occurring, when two instances of classes decorated with total_ordering that return NotImplemented, are compared, with each of the four comparison operators. For each operator, a test is included that would cause the recursion error if not for the code patch, as well as one where this error does not occur as there is no recursion.

Patch tested against the default branch.

As part of this, I finally reviewed Jim's proposed alternate implementations for the helper functions. Katie's patch used my version while I figured out the differences in behaviour :)

The key difference between them relates to the following different approaches to handling unknown types in __eq__:

@functools.total_ordering
class TotallyOrderedEqualsReturnsFalse:
   def __init__(self, value):
       self._value = value
   def __eq__(self, other):
       return isinstance(other, Weird) and self._value == other._value
   def __lt__(self, other):
       if not isinstance(other, Weird): return NotImplemented
       return self._value < other._value

@functools.total_ordering
class TotallyOrderedEqualsReturnsNotImplemented:
   def __init__(self, value):
       self._value = value
   def __eq__(self, other):
       if not isinstance(other, Weird): return NotImplemented
       return self._value == other._value
   def __lt__(self, other):
       if not isinstance(other, Weird): return NotImplemented
       return self._value < other._value

Formally, the version which returns False directly is incorrect - it should be returning NotImplemented, and letting Python take of converting two results of NotImplemented to an equality comparison result of False.

In practice, lots of types are written that way, so we need to preserve the current behaviour of not checking the equality operations if the ordered comparison isn't implemented, or we will inadvertently end up making "<=" or ">=" return an answer instead of raising TypeError.

On Mon, Jul 8, 2013 at 3:30 AM, Nick Coghlan wrote:

The key difference between them relates to the following different approaches to handling unknown types in __eq__:

@functools.total_ordering
class TotallyOrderedEqualsReturnsFalse:
...
def __eq__(self, other):
return isinstance(other, Weird) and self._value == other._value

@functools.total_ordering
class TotallyOrderedEqualsReturnsNotImplemented:
...
def __eq__(self, other):
if not isinstance(other, Weird): return NotImplemented
return self._value == other._value

Formally, the version which returns False directly is incorrect - it should be returning NotImplemented, and letting Python take of converting two results of NotImplemented to an equality comparison result of False.

I had not considered this. I'm not sure exactly where to improve the
docs, but I think it would be helpful to use a docstring (or at least
comments) on the test cases, so that at least someone looking at the
exact test cases will understand the subtlety.

In practice, lots of types are written that way, so we need to preserve the current behaviour of not checking the equality operations if the ordered comparison isn't implemented, or we will inadvertently end up making "<=" or ">=" return an answer instead of raising TypeError.

I had viewed that as a feature; for types where only some values will
have a useful answer, I had thought it better to still return that
answer for the values that do have one. I freely acknowledge that
others may disagree, and if you say the issue was already settled,
then that also matters.

-jJ

I'm actually not sure which of us is correct - Katie and I will be looking into it further today to compare the existing implementation, my proposal and yours to see if there's a clear winner in terms of consistent.

It may be that we end up choosing the version that pushes towards more correct behaviour, since types incorrectly returning True or False from comparisons (instead of NotImplemented) is actually a pretty common bug preventing the creation of unrelated types that interoperate cleanly with an existing type.

OK, I had misunderstood the way Jim's code works (it still coerces a "False" result for __eq__ into NotImplemented if the ordered comparison returns NotImplemented).

However, I spent some more time tinkering with it today (see
https://bitbucket.org/ncoghlan/misc/src/856bd105e5e43cb96ebaa2d250c3c801da571953/tinkering/comparisons.py?at=default ) which shows that my version (which ignores __eq__ entirely if the ordered comparison returns NotImplemented) is consistent with the current behaviour, while accepting a "True" return from __eq__ in that case (as Jim's version does) may result in some existing TypeError results becoming "True" comparison results instead.

Since this is such an incredibly niche edge case (the ordered comparison has to return NotImplemented while __eq__ returns True), I remaining consistent with the existing behaviour is the most important consideration. We'll add a test case to ensure this remains consistent, though.

The other code clarification changes look reasonable though - Katie plans to incorporate several of those.

Attached is a new patch, which includes Nick's logic from msg140493, some of the code readability changes Jim suggested in msg151989 (but not the behavioural changes), and associated tests. On Nick's advice, I have also replaced the dunder equals calls with the standard comparators (==/!=), given not all classes will necessarily have both NE and EQ, and made the comparison the last action in each method, for consistency.

Test cases have been added to check a TypeError is raised, rather than True being returned, when GE/LE is called on two objects that are equal but have a comparator that returns NotImplemented.

Nick, let me know when you think it is ready and I'll review the patch.

I think I spotted a logic bug in _not_op_and_not_eq (it uses "or" instead
of "and" in the final line) , so I suspect we still have a missing test
case in the latest patch. (My fault - I should have suggested using
coverage.py to ensure all the branches were covered by the chosen test
cases).

The general structure of the proposed update is complete though.

Since this is such an incredibly niche edge case
(the ordered comparison has to return NotImplemented
while __eq__ returns True),

*and* the types are explicitly supposed to ordered,
based on what is being tested

I remaining consistent with the existing behaviour
is the most important consideration.

Agreed, once I consider that additional caveat.

After more thought, I'm changing this to Py3.4 only. For prior versions, I'm content to document that there is no support for NotImplemented, and if that is needed, then people should write-out all six rich comparisons without using the total ordering decorator.

I don't think it is a good idea to introduce the new behaviors into otherwise stable point releases. This patch is somewhat complex and has potential for bugs, unexpected behaviors, misunderstandings, and intra-version compatability issues (like the problems that occurred when True and False were added in a point release many years ago).

Agreed.

I had actually assumed this would be 3.4 only, otherwise I wouldn't have
suggested using the new subtest feature in the test case.

Nick is correct; a logic bug was introduced during refactoring, which is fixed in the attached patch. The tests introduced with my original patch cover cases where an operation is not implemented, so it would be inappropriate to add a test case there that would have caught the aforementioned error. Instead I have added some extra cases to the existing total_ordering tests; these now fail when encountering this (now fixed) logic error.

Thanks Katie - Raymond, the patch is ready for review now

If you're happy with it, then the only other things it should need prior to commit are NEWS and ACKS entries (I think it's too esoteric a fix to mention in What's New).

Hello, I have run into this when I wanted to use OrderedEnum and the example in enum docs seemed too repetitive to me. It's nice to know that it's being worked on.

Raymond, do you still want to look at this one? Otherwise I'll finish it up
and commit it before the next alpha (I'll check the example in the enum
docs to see if it can be simplified, too).

Updated patch that includes the simplified OrderedEnum example in the enum docs and also updates the enum tests to check that type errors are correctly raised between different kinds of ordered enum.

Raymond, I'm happy to leave this until alpha 4, but I'm raising the priority a bit since I think the inclusion of Enum in the standard library increases the chances of people wanting to use functools.total_ordering to avoid writing out the comparison methods in situations where incompatible types may encounter each other.

Nick, the latest version of the patch looks like a correct solution.

Before applying, please add a block comment showing why these shenanigans are necessary (i.e. the use self.__lt__ instead of the less-than operator because the former doesn't fall into recursive operator flipping).

Also, please add a note to the docs indicating 1) that NotImplemented is now supported as of version 3.4 and 2) that when speed matters, it is always better to code all four ordering operators by hand rather than paying the cost of total_ordering's layers of indirection.

One other thought: The OrderedEnum example should not use the total ordering decorator.

To the extent that the docs are trying to teach how to use Enum, they should focus on that task and not make a side-trip into the world of class decorators. And to the extent that the docs are trying to show an example of production code, it would be better for speed and ease of tracing through a debugger to just define all four ordering comparisons.

New changeset ad9f207645ab by Nick Coghlan in branch 'default':
Close bpo-10042: functools.total_ordering now handles NotImplemented
http://hg.python.org/cpython/rev/ad9f207645ab

The committed patched was based directly on Katie's last version, without my enum changes.

Raymond - feel free to tweak the wording on the docs notes or the explanatory comment if you see anything that could be improved.

Thanks Nick and Katie. This looks great. :-)

New changeset 1cc413874631 by R David Murray in branch 'default':
whatsnew: total_ordering supports NotImplemented (bpo-10042)
http://hg.python.org/cpython/rev/1cc413874631