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: ```python assignee = None closed_at = None created_at = labels = ['interpreter-core', 'type-bug', '3.11'] title = 'Incorrect operand precedence when implementing sequences in C' updated_at = user = 'https://github.com/terryjreedy' ``` bugs.python.org fields: ```python activity = actor = 'gregory.p.smith' assignee = 'none' closed = False closed_date = None closer = None components = ['Interpreter Core'] creation = 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

[7aa6e20b-8983-474f-b2ae-de7eff1caa04]

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.

[7aa6e20b-8983-474f-b2ae-de7eff1caa04]

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 sqrepeat, 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.

[ncoghlan]

I think the roundup/Hg integration may be getting confused by the merges of the cpython main line of development with my sandbox.

[benjaminp]

Is that a patch you can put on Rietveld then? (/me wanting to review)

[ncoghlan]

MvL says the review creation script should be able to cope with the rdiff output within the next day or so.

[terryjreedy]

b9b7d4c10bc4.diff is a huge compilation of all commits from the last few days, with the abstract.c diff buried about 3/4ths of the way through.

[ncoghlan]

We know, I left it there to help MvL debug the issues in the diff generator.

The version I created with the rdiff extension is correct though, and Martin fixed the Reitveld integration to handle the extra lines at the start of the diff.

I wouldn't actually commit the change as it stands (if nothing else, PyErr_Matches() calls are needed in the unicode methods), but it gives a clear idea of the magnitude of the changes needed.

[ncoghlan]

The draft code is now only on the "respect_LHS_precedence" branch of my sandbox repository.

[ncoghlan]

Well, there and in the named diff file on here, of course.

[ncoghlan]

Martin and I are still experimenting with this issue as a test case for the remote repository diff calculator, so apologies for the noise as we add and remove patch files.

[ncoghlan]

And, back on topic...

I've been pondering this problem and the approach I adopted in my branch and decided it's the *wrong* way to go about it. It takes an already complex piece of code and makes it even more complicated.

A completely different approach that I'm considering is to instead make types defined in C behave more like their counterparts defined in Python. The reason sequences implemented in Python don't have this problem is because their nb_add and nbmul slots get filled in with functions that call up into the Python _\[ri]add and __[ri]mul implementations.

So my thought is that, when the type construction machinery is filling in the type slots, we could actually do something similar at the C level: define a standard _PySequenceAsNumber variable and add a pointer to that in to the tp_as_number slot. The nb_add and nb_mul slots in this structure would reference functions that delegated the relevant operations to sq_concat and sq_repeat.

I haven't actually tried this approach, so there may be practical issues with it that haven't occurred to me as yet, but it's definitely appealing as it has the potential to *simplify* the dispatch code in abstract.c instead of making it even more complicated.

[ncoghlan]

Heh, rereading the issue comments, I noticed that my latest idea is quite similar to what Terry suggested last year, just using delegation to adjust the signatures appropriately rather than copying the function pointers directly over.

[ncoghlan]

I'm currently planning to postpone fixing this until 3.4. However, if someone else wants to pick it up for 3.3, go ahead.

[ncoghlan]

Updated issue title to better describe the symptoms of the issue (and hopefully make it so I don't spend 5 minutes remembering the issue title every time I want to look at it...)

[ncoghlan]

Nathaniel Smith pointed out on python-dev (https://mail.python.org/pipermail/python-dev/2015-May/140006.html) that NumPy is relying on this bug to implement elementwise multiplication of a list by a scalar array:

In [9]: [1, 2] * np.array(2)
Out[9]: array([2, 4])

He also pointed out that PyPy implemented bug-for-bug compatibility with this some time back: https://bitbucket.org/pypy/pypy/src/a1a494787f4112e42f50c6583e0fea18db3fb4fa/pypy/objspace/descroperation.py?at=default#cl-692

[iritkatriel]

Reproduced on 3.11.

[gpshead]

Given that a lot of code is presumably relying on this (see the notes from 2015)... I wouldn't be surprised if this turns into a wart we document but not actually fix. :/

Or a conditional behavior we control via a from __future__ import correct_extension_operator_precedence on a per file / per Notebook basis.

Ever actually flipping the default sounds difficult without disruption. We'd need input from the community where extensions that rely on it have been produced and widely deployed.

[ncoghlan]

In line with @gpshead's comment, perhaps this should be closed in favour of the docs issue in #83483?

[jeff5]

In line with @gpshead's comment, perhaps this should be closed in favour of the docs issue in #83483?

While the improvements in #83483 seem really good (thanks), I did not see this issue resolved there yet. Your link there to a closely-related, but I think different issue #74326 (thanks again) shows this divergence to be a recurring surprise to users who dig deep. I have come across these too, but found this issue to follow, rather than raise it again. And this is a really good exploration of it, even if it leads (so far) to an impasse.

I'm not sure how you can document this, in an implementation-neutral way as a Python "feature". The data model [1] is clear but CPython works differently, with unintended consequences. It could be documented as a known divergence of the C implementation from the Python data model. It is not corrected because one well-known project and unknown others rely on it.

[1] https://docs.python.org/3.11/reference/datamodel.html#emulating-container-types