functools.total_ordering fails to handle NotImplemented correctly

[8dfb8b75-dc62-4aed-8f22-56c39cf98f18]

BPO	10042
Nosy	@rhettinger, @ncoghlan, @merwok, @regebro, @ethanfurman, @jimjjewett
Files	test_total_ordering.py: Example file new_total_ordering.py: Possible solution of bug sane_total_ordering.py: Rewrite of total_ordering that takes NotImplemented into account new_total_ordering_notimplemented.py new_total_ordering_overflow.py 10042.patch: Patch with Nick's code from msg140493 and matching tests 10042_new_total_ordering_with_tests.patch: New patch adding logic from Nick, Jim and some extra code improvements, plus more tests 10042_revised.patch: Revised patch, including code changes and tests issue10042_with_enum_updates.diff: Updated total_ordering with simplified OrderedEnum example

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = 'https://github.com/ncoghlan' closed_at = created_at = labels = ['type-feature', 'library'] title = 'functools.total_ordering fails to handle NotImplemented correctly' updated_at = user = 'https://bugs.python.org/francescor' ``` bugs.python.org fields: ```python activity = actor = 'python-dev' assignee = 'ncoghlan' closed = True closed_date = closer = 'python-dev' components = ['Library (Lib)'] creation = creator = 'francescor' dependencies = [] files = ['19144', '19145', '21708', '21711', '21712', '30859', '30871', '30923', '31890'] hgrepos = [] issue_num = 10042 keywords = ['patch'] message_count = 52.0 messages = ['118096', '118097', '118128', '125758', '126729', '128057', '131379', '131385', '133999', '134001', '134002', '134003', '134004', '134005', '134013', '134014', '134015', '134016', '134018', '134022', '134024', '134155', '134163', '134205', '140493', '140494', '142703', '151989', '192619', '192624', '192626', '192654', '192707', '192709', '192712', '192730', '192745', '192842', '192846', '192869', '193076', '193078', '198073', '198197', '198522', '198523', '198676', '198678', '198780', '198781', '198818', '213099'] nosy_count = 12.0 nosy_names = ['rhettinger', 'ncoghlan', 'eric.araujo', 'lregebro', 'francescor', 'ethan.furman', 'catalin.iacob', 'python-dev', 'javawizard', 'Jim.Jewett', 'Drekin', 'codemiller'] pr_nums = [] priority = 'normal' resolution = 'fixed' stage = 'resolved' status = 'closed' superseder = None type = 'enhancement' url = 'https://bugs.python.org/issue10042' versions = ['Python 3.4'] ```

[8dfb8b75-dc62-4aed-8f22-56c39cf98f18]

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.

[8dfb8b75-dc62-4aed-8f22-56c39cf98f18]

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.

[rhettinger]

Thanks, this is a good idea.

[rhettinger]

Thanks for the report and patch.

Fixed. See r87853.

[1a1c8953-fd3a-4521-a1c0-eee1dd92646e]

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

[merwok]

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

[rhettinger]

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

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

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

[ae09771c-ff81-4bf3-b932-e7e2c9177d39]

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.

[rhettinger]

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.

[ae09771c-ff81-4bf3-b932-e7e2c9177d39]

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

[rhettinger]

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.

[ae09771c-ff81-4bf3-b932-e7e2c9177d39]

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.

[rhettinger]

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.

[1a1c8953-fd3a-4521-a1c0-eee1dd92646e]

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.

[1a1c8953-fd3a-4521-a1c0-eee1dd92646e]

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.

[ae09771c-ff81-4bf3-b932-e7e2c9177d39]

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

[1a1c8953-fd3a-4521-a1c0-eee1dd92646e]

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.

[ae09771c-ff81-4bf3-b932-e7e2c9177d39]

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

[1a1c8953-fd3a-4521-a1c0-eee1dd92646e]

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.

[ae09771c-ff81-4bf3-b932-e7e2c9177d39]

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

[8dfb8b75-dc62-4aed-8f22-56c39cf98f18]

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.

[1a1c8953-fd3a-4521-a1c0-eee1dd92646e]

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.

[8dfb8b75-dc62-4aed-8f22-56c39cf98f18]

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.

[ncoghlan]

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))
  ]
}

[ncoghlan]

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.

[ncoghlan]

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

[74c4563b-ab1c-43d8-9219-30c4eca796bc]

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

[ncoghlan]

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

[1d5bd97c-2525-42ba-a694-02cdea8b03d3]

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.

[ncoghlan]

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.

[74c4563b-ab1c-43d8-9219-30c4eca796bc]

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.totalordering class TotallyOrderedEqualsReturnsFalse: ... def \_eq__(self, other): return isinstance(other, Weird) and self._value == other._value

@functools.totalordering 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

[ncoghlan]

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.

[ncoghlan]

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.

[1d5bd97c-2525-42ba-a694-02cdea8b03d3]

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.

[rhettinger]

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

[ncoghlan]

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.

[74c4563b-ab1c-43d8-9219-30c4eca796bc]

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.

[rhettinger]

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

[ncoghlan]

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.

[1d5bd97c-2525-42ba-a694-02cdea8b03d3]

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.

[ncoghlan]

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

[90ff3b65-5c08-4f89-bb59-3f03c3cccbb5]

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.

[ncoghlan]

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

[ncoghlan]

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.

[ncoghlan]

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.

[rhettinger]

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.

[rhettinger]

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.

[1762cc99-3127-4a62-9baf-30c3d0f51ef7]

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

[ncoghlan]

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.