Incorrect operand precedence when implementing sequences in C

[terryjreedy]

BPO	11477
Nosy	@rhettinger, @terryjreedy, @gpshead, @ncoghlan, @cfbolz, @benjaminp, @merwok, @alex, @Trundle, @meadori, @durban, @ericsnowcurrently, @serhiy-storchaka, @iritkatriel
Files	issue11477_LHS_prededence.diff: Patch generated via rdiff extension 650549138a3d.diff 8bd713a823b5.diff

^{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:

assignee = None
closed_at = None
created_at = <Date 2011-03-12.21:24:50.923>
labels = ['interpreter-core', 'type-bug', '3.11']
title = 'Incorrect operand precedence when implementing sequences in C'
updated_at = <Date 2021-10-26.00:55:14.406>
user = 'https://github.com/terryjreedy'

bugs.python.org fields:

activity = <Date 2021-10-26.00:55:14.406>
actor = 'gregory.p.smith'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2011-03-12.21:24:50.923>
creator = 'terry.reedy'
dependencies = []
files = ['21219', '21368', '21386']
hgrepos = ['3']
issue_num = 11477
keywords = ['patch']
message_count = 27.0
messages = ['130698', '130728', '130736', '130812', '130866', '130867', '130909', '130925', '130974', '130976', '130994', '131001', '131004', '131007', '131022', '131030', '131057', '131211', '131212', '132052', '158917', '158918', '160138', '179031', '243301', '405003', '405017']
nosy_count = 14.0
nosy_names = ['rhettinger', 'terry.reedy', 'gregory.p.smith', 'ncoghlan', 'Carl.Friedrich.Bolz', 'benjamin.peterson', 'eric.araujo', 'alex', 'Trundle', 'meador.inge', 'daniel.urban', 'eric.snow', 'serhiy.storchaka', 'iritkatriel']
pr_nums = []
priority = 'normal'
resolution = None
stage = 'patch review'
status = 'open'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue11477'
versions = ['Python 3.11']

[terryjreedy]

Example (which can serve as testcase with buggy output corrected).

class C(object):
    def __iter__(self):
        yield 'yes!'
    def __radd__(self, other):
        other.append('bug!')
        return other
    def __rmul__(self, other):
        other *= 2
        return other
    def __index__(self):
          return 3

class L(list):
    def __iadd__(self, other):
        list.__iadd__(self,other)
        return self
    def __mul__(self, other):
        return L(list.__imul__(self,other))

z1, z2, c = [], L(), C()
z1 += c
z2 += c
print(z1, z2, [1]*c, L([1])*c)
>>> 
['bug!'] ['yes!'] [1, 1] [1, 1, 1] # PyPy prints ['yes!'], [1, 1, 1]

Cause was diagnosed by Greg Price in
http://codespeak.net/pipermail/pypy-dev/2011q1/006958.html
as checking forward and reverse numeric slots before checking sequence slots for C-coded classes. Such a difference does not exist in Python itself.

In "About raising NotPortableWarning for CPython specific code"
pydev thread starting at
http://codespeak.net/pipermail/pypy-dev/2011q1/006958.html

Nick Coghlin identified the fix as "When a given operation has multiple C level slots, shouldn't we be checking all the LHS slots before checking any of the RHS slots?"

Guido replied "Yeah, indeed, on everything you said. The code dispatching based on internal slots is horribly ad-hoc and likely wrong in subtle ways."

I personally think fix should be backported to 2.7 and 3.2, but did not select them because that may be controversial.

[terryjreedy]

Second link to pydev should be
http://mail.python.org/pipermail/python-dev/2011-March/109130.html

[arigo]

Note that I "fixed" one case in PyPy: if the class C has no __iter__() but only __radd__(), and we call "somelist += C()". This was done simply by having somelist.__iadd__(x) return NotImplemented in case x is not iterable, instead of propagating the TypeError.

This fix doesn't change the outcome in the case reported here: if there are two possible ways to get a valid answer, then PyPy will systematically prefer the way implemented by the LHS method over the way implemented by the RHS method, whereas CPython might not.

[ncoghlan]

Armin, I'm not sure returning NotImplemented from __iadd__ is a good idea in this case. It means "+=" on a mutable object may silently fail to mutate in-place - enabling that seems rather questionable.

[terryjreedy]

It seems to me that the underlying (design) flaw is having duplicate slots in the C type structure*. I presume that having two different functions in num-add and seq-add (concat) (I know, not quite the proper names), etc, is an error. I also assume that changing the structure is out, whether frozen in the ABI or not, as disabling every extention type.

But could we change how the slots are handled? For instance, when class is created, if nun-add is absent and seq-add is present, copy seq-add to num-add and thereafter only use num-add and treat seq-add as a dummy left for back compatibility. In other words, merge the duplicate slots in their effect, so there is a proper 1-1 relationship between syntax operators and methods, as there is for Python-coded classes.

*I am guessing that this was for convenience -- making a number? fill in num slots; making a sequence? fill in seq slots. Or perhaps Guido once had some idea of possibly separating the operators/functions at the Python level. Does not matter at present.

[terryjreedy]

And if num-add is present and seq-add not, copy the other way, even if it were recommended to only use the former.

[arigo]

Nick: we get a TypeError anyway if we do unsupported things like "lst += None". It seems to me that you are confusing levels, unless you can point out a specific place in the documentation that would say "never return NotImplemented from __iadd__(), __imul__(), etc."

[terryjreedy]

I think Nick's point, and one I agree with, is (or amounts to):
'somelist += ob' == 'somelist.__iadd__(ob)' ==
'somelist.extend(ob)' == 'somelist[len(somelist):len(somelist)]=ob'
is defined and should be implemented for all somelist,ob pairs. If ob is an iterable, add the items at the end; if not, raise TypeError.

CPython currently has a bug that breaks the middle equality in a peculiar case. We recognize that and hope to fix it.

The proper, future-proof fix for Greg Price & Co. is for them to

1. use somelist.append(ob) to append a single object, iterable or not, to somelist. If they insist on (mis)using += for appending,
2. add the trivial __iter__ yielding just the instance to all classes whose instances are ever a target of 'somelist += instance'. Or
3. wrap each non-iterable instance in an iterable, such as a tuple:
   "somelist += (non-iterable,).
   Any of these (1. actually) should have been done in the first place, as has always been documented.

[ncoghlan]

Armin: yeah, I learned better in the course of trying to fix this misbehaviour in CPython. I've adjusted assorted sq_concat methods to return NotImplemented in the sandbox where I'm working on this, along with modifying abstract.c to correctly cope with that.

Terry: the slot signatures vary, so copying function pointers around isn't really viable. I'm just fixing abstract.c to call the slots in the right order.

The fun part is that historically, CPython didn't check for NotImplemented returns from sq_concat and sq_repeat, so those methods are all written to raise TypeError explicitly, which breaks delegation to __radd__ methods (i.e. exactly the same thing Armin fixed in PyPy).

As far as 2.7 and 3.2 go, I'm thinking a Py3k warning in the next 2.7 release and a CompatibilityWarning (once we have it) in the next 3.2 will be a possibility. However, I want to finish the patch and see the magnitude of the change before deciding what we do with the maintenance versions.

[ncoghlan]

My work in progress is on the respect_LHS_precedence branch in http://hg.python.org/sandbox/ncoghlan

Current status is that I have tests for correct handling of sq_concat and sq_repeat, and am close to having sq_concat and sq_inplace_concat behaving correctly.

I'm not happy with the current duplication of checks in abstract.c, but I'll look for ways to make the code prettier after it is working properly.

[ncoghlan]

Trying out the hg integration MvL added to Roundup.

[ncoghlan]

I generated a patch between my sandbox and the main repository using the rdiff extension immediately after syncing with the main line of development. ("hg diff --reverse cpython" where cpython is aliased to the main repository)

This is the output I was hoping to get from the automated branch checking.