classification
Title: Incorrect operand precedence when implementing sequences in C
Type: behavior Stage: needs patch
Components: Interpreter Core Versions: Python 3.4
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: Carl.Friedrich.Bolz, Trundle, alex, benjamin.peterson, daniel.urban, eric.araujo, eric.snow, meador.inge, ncoghlan, rhettinger, terry.reedy
Priority: normal Keywords: patch

Created on 2011-03-12 21:24 by terry.reedy, last changed 2013-01-04 14:43 by ncoghlan.

Files
File name Uploaded Description Edit
issue11477_LHS_prededence.diff ncoghlan, 2011-03-15 17:48 Patch generated via rdiff extension review
650549138a3d.diff loewis, 2011-03-24 07:32
8bd713a823b5.diff loewis, 2011-03-24 23:38 review
Repositories containing patches
http://hg.python.org/sandbox/ncoghlan#respect_LHS_precedence
Messages (24)
msg130698 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-12 21:24
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.
msg130728 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-13 06:49
Second link to pydev should be
http://mail.python.org/pipermail/python-dev/2011-March/109130.html
msg130736 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2011-03-13 11:19
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.
msg130812 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-14 13:34
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.
msg130866 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-14 17:43
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.
msg130867 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-14 17:48
And if num-add is present and seq-add not, copy the other way, even if it were recommended to only use the former.
msg130909 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2011-03-14 21:37
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."
msg130925 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-14 23:03
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.
msg130974 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-15 14:01
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.
msg130976 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-15 14:16
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.
msg130994 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-15 16:38
Trying out the hg integration MvL added to Roundup.
msg131001 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-15 17:48
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.
msg131004 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-15 17:50
I think the roundup/Hg integration may be getting confused by the merges of the cpython main line of development with my sandbox.
msg131007 - (view) Author: Benjamin Peterson (benjamin.peterson) * (Python committer) Date: 2011-03-15 17:53
Is that a patch you can put on Rietveld then? (/me wanting to review)
msg131022 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-15 19:10
MvL says the review creation script should be able to cope with the rdiff output within the next day or so.
msg131030 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2011-03-15 19:52
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.
msg131057 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-15 22:33
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.
msg131211 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-17 02:19
The draft code is now only on the "respect_LHS_precedence" branch of my sandbox repository.
msg131212 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-17 02:20
Well, there and in the named diff file on here, of course.
msg132052 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2011-03-24 23:10
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.
msg158917 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-04-21 12:46
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 nb_mul 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.
msg158918 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-04-21 12:50
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.
msg160138 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2012-05-07 11:38
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.
msg179031 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2013-01-04 14:43
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...)
History
Date User Action Args
2013-01-04 14:43:01ncoghlansetmessages: + msg179031
title: Bug in code dispatching based on internal slots -> Incorrect operand precedence when implementing sequences in C
2012-05-07 11:38:16ncoghlansetassignee: ncoghlan ->
messages: + msg160138
versions: + Python 3.4, - Python 3.3
2012-04-21 12:50:16ncoghlansetmessages: + msg158918
2012-04-21 12:46:40ncoghlansetmessages: + msg158917
2012-03-04 06:32:21eric.snowsetnosy: + eric.snow
2011-03-24 23:38:16loewissetfiles: + 8bd713a823b5.diff
2011-03-24 23:22:59loewissetfiles: - 8bd713a823b5.diff
2011-03-24 23:22:35loewissetfiles: + 8bd713a823b5.diff
2011-03-24 23:22:09loewissetfiles: - 8bd713a823b5.diff
2011-03-24 23:10:19ncoghlansetmessages: + msg132052
2011-03-24 22:53:08ncoghlansetfiles: + 8bd713a823b5.diff
2011-03-24 16:23:38rhettingersetnosy: + rhettinger
2011-03-24 07:32:42loewissetfiles: + 650549138a3d.diff
2011-03-24 07:31:51loewissetfiles: - 650549138a3d.diff
2011-03-24 07:13:20loewissetfiles: - f1bd5468dae6.diff
2011-03-24 07:12:19loewissetfiles: + 650549138a3d.diff
2011-03-17 02:21:54alexsetnosy: + alex
2011-03-17 02:20:56ncoghlansetnosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg131212
2011-03-17 02:19:22ncoghlansetnosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg131211
2011-03-17 02:16:19loewissetfiles: + f1bd5468dae6.diff
nosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-17 02:12:32loewissetfiles: - f1bd5468dae6.diff
nosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-17 02:11:45loewissetfiles: + f1bd5468dae6.diff
nosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-17 02:09:11loewissetfiles: - f1bd5468dae6.diff
nosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-17 02:08:07loewissetfiles: + f1bd5468dae6.diff
nosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-17 02:05:08loewissetfiles: - b9b7d4c10bc4.diff
nosy: terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-15 22:59:04arigosetnosy: - arigo
2011-03-15 22:33:15ncoghlansetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg131057
2011-03-15 19:52:36terry.reedysetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg131030
2011-03-15 19:10:12ncoghlansetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, benjamin.peterson, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg131022
2011-03-15 17:53:40benjamin.petersonsetnosy: + benjamin.peterson
messages: + msg131007
2011-03-15 17:50:46ncoghlansetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg131004
2011-03-15 17:49:32ncoghlansetfiles: - 2f5db44c98f2.diff
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-15 17:49:03ncoghlansetfiles: + 2f5db44c98f2.diff
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-15 17:48:20ncoghlansetfiles: + issue11477_LHS_prededence.diff
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg131001
2011-03-15 16:41:51ncoghlansetfiles: + b9b7d4c10bc4.diff
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-15 16:41:28ncoghlansetfiles: - 85d7c99fd31e.diff
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-15 16:39:01ncoghlansetfiles: + 85d7c99fd31e.diff
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
keywords: + patch
2011-03-15 16:38:20ncoghlansethgrepos: + hgrepo3
messages: + msg130994
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-15 14:16:21ncoghlansetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg130976
2011-03-15 14:01:06ncoghlansetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg130974
2011-03-14 23:03:43terry.reedysetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg130925
2011-03-14 21:37:25arigosetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg130909
2011-03-14 17:48:05terry.reedysetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg130867
2011-03-14 17:43:37terry.reedysetnosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
messages: + msg130866
2011-03-14 13:36:54ncoghlansetassignee: ncoghlan
nosy: arigo, terry.reedy, ncoghlan, Carl.Friedrich.Bolz, eric.araujo, Trundle, meador.inge, daniel.urban
2011-03-14 13:34:11ncoghlansetnosy: + ncoghlan
messages: + msg130812
2011-03-14 12:33:58Carl.Friedrich.Bolzsetnosy: + Carl.Friedrich.Bolz
2011-03-13 13:54:21meador.ingesetnosy: + meador.inge
2011-03-13 11:19:20arigosetnosy: + arigo
messages: + msg130736
2011-03-13 08:05:16daniel.urbansetnosy: + daniel.urban
2011-03-13 06:49:35terry.reedysetnosy: terry.reedy, eric.araujo, Trundle
messages: + msg130728
2011-03-12 22:35:47eric.araujosetnosy: + eric.araujo
2011-03-12 21:25:28Trundlesetnosy: + Trundle
2011-03-12 21:24:50terry.reedycreate