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.

We *do* care about NotImplemented, that's the whole point of this bug report. I don't see how this is a problem in the new_total_ordering.py example. Can you give an example of when you get a stack overflow?

The examples in new_total_ordering are in themselves badly implemented, as they do check of the class with an isinstance, but if it is not the correct instance, they will return False or raise a TypeError. That's wrong, they should return NotImplemented, to give the other class a chance. But that is not a problem for the tests, it's only a problem if you use the tests as examples of how to implement a comparable class.

But in no case am I able to get a stack overflow here, which I can with the old total_ordering recipe.

I'm attaching a file with the example classes returning NotImplemented, and a different implementation of a total ordering, as an example of how returning NotImplemented by one class will give the chance to the other class. This is the ultimate cause of the bug, and new_total_ordering handles it properly.

I've attached a file demonstrating the stack overflow. It assumes total_ordering has been defined as per new_total_ordering.py.

Ah! I see how you mean. The problem isn't just if you turn the conversion around from self > other to other < self. The problem in fact appears when a rich text function uses the <>!= operators on self directly.

I tried a version which uses the __xx__ operators directly and that works for the ones that does not use "not". "not NotImplemented" is false, for obvious reasons, and that means that with for example "lambda self, other: not self.__ge__(other)" will return False, when it should return NotImplemented.

In effect this means that the total ordering recipe only works as long as you don't compare two classes that use the total ordering recipe. :-)

I don't think the lambda technique is going to work properly. Of course we can say that we should care about NotImplemented, but then first of all this recipe needs a big "this is broken, don't use it unless you know what you are doing" label, and secondly I don't think it should have been included in the first place if we can't make it work properly.

That's my point. My version, sane_total_ordering.py, fixes this by using traditional functions and explicit NotImplemented checks.

Yeah, I can't say it's pretty though. :) Anyway this is an issue for 3.2 and 2.7 as well, then, so I add them back.

Ok. Yeah, I won't argue that it's pretty :-)

I think the whole issue is indeed how NotImplemented is treated. To me saying that 'not NotImplemented' is True is wrong. About the stack overflow I found there are various possible fixes, however none will nice.

By definition, NotImplemented is the way that a method or operation have to signal to the interpreter that it doesn't know how to handle given operand types. IMHO, it shouldn't be possible to receive NotImplemented as operand value, and it shouldn't have a boolean value. Indeed, t should be handled as a special case by the interpreter.

To go further, I am not really sure that NotImplemented should be a return value. Probably, an exception that is trapped by the interpreter when evaluating an expression would be easier to define and handle.

Of course, such a change should be deeply grokked before being put in place, also because of the high impact on code that already relies on NotImplemented having a value.

I was also surprised by the special return value, but it seems a bit overkill to change the implementation of rich comparison operators just because it's tricky to make a short and pretty class decorator that extends some operators to all operators. :)

And removing the support for returning NotImplemented is something that only can be done at the earliest in 3.4 anyway.

On the one hand, it's not just a matter of total_ordering and rich comparison operators, because all user defined operators may return NotImplemented when they get types that they don't know how to handle.

On the other hand, if such a decision is taken, a long path should be planned to move handling of unknown types from one way to the other.

NotImplemented is a speed and maintainability hack - the runtime cost and additional code complexity involved in doing the same operator signalling via exceptions would be prohibitive (check Objects/abstract.c in the CPython source if you want the gory details).

As far as an implementation of @total_ordering that correctly handles NotImplemented goes, yes, I absolutely agree we should do this correctly. The fact that it is *hard* is an argument in *favour* of us getting it right, as there is a decent chance that manually written comparison operations will also stuff it up.

That said, I don't think sane_total_ordering quite gets the semantics right, either.

Some helper functions in the closure would let the existing lambda functions be updated to do the right thing (and I believe the semantics I have used below are the correct ones for handling NotImplemented in @total_ordering). (I haven't actually run this code as yet, but it should give a clear idea of what I mean)

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 op_result
   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:
     # Short circuit OR, as op is True
     # NotImplemented is also passed back here
     return op_result
   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:
     # Short circuit AND, as not_op is False
     # NotImplemented is also passed back here
     if op_result is NotImplemented:
       return op_result
     return not op_result
   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 op_result
   if op_result:
     return self.__eq__(other)
   # Short circuit OR, as not_op is True
   return not op_result

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 op_result
   if op_result:
     return self.__ne__(other)
   # Short circuit AND, as op is False
   return op_result

The conversion table then looks like:

convert = {
  '__lt__': [
    ('__gt__',
      lambda self, other: not_op_and_not_eq(self.__lt__, self, other)),
    ('__le__',
      lambda self, other: op_or_eq(self.__lt__, self, other)),
    ('__ge__',
      lambda self, other: not_op(self.__lt__, other))
  ],
  '__le__': [
    ('__ge__',
      lambda self, other: not_op_or_eq(self.__le__, self, other)),
    ('__lt__',
      lambda self, other: op_and_not_eq(self.__le__, self, other)),
    ('__gt__',
      lambda self, other: not_op(self.__le__, other))
  ],
  '__gt__': [
    ('__lt__',
      lambda self, other: not_op_and_not_eq(self.__gt__, self, other)),
    ('__ge__',
      lambda self, other: op_or_eq(self.__gt__, self, other)),
    ('__le__',
      lambda self, other: not_op(self.__gt__, other))
  ],
  '__ge__': [
    ('__le__',
      lambda self, other: not_op_or_eq(self.__ge__, self, other)),
    ('__gt__',
      lambda self, other: op_and_not_eq(self.__ge__, self, other)),
    ('__lt__',
      lambda self, other: not_op(self.__ge__, other))
  ]
}

Also, a note regarding efficiency: as it calls the underlying methods directly and avoids recursing through the full operand coercion machinery, I would actually expect this approach to run faster than the current implementation.

Changed stage and resolution to reflect the fact that none of the existing patches adequately address the problem.

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