Python interpreter bug

[alainpoint@yahoo.fr]

Hello,

I came accross what i think is a serious bug in the python interpreter.

Membership testing seems not to work for list of objects when these
objects have a user-defined __cmp__ method.
It is present in Python 2.3 and 2.4. I don't know about other versions.
The following code illustrates the bug:
from random import choice
class OBJ:
def __init__(self,i dentifier):
self.id=identif ier
self.allocated= 0
def __cmp__(self,ot her):
return cmp(other.alloc ated,self.alloc ated)
mylist=[OBJ(i) for i in range(20)]
excluded=[obj for obj in mylist if obj.id>choice(r ange(20))]
for obj in mylist:
if obj in excluded:
assert obj.id in [objt.id for objt in excluded]
continue

Running the above snippet will trigger the assert. The culprit seems to
be the __cmp__ method which sorts on a key with constant value.
Best regards
Alain

[Simon Percivall]

Re: Python interpreter bug

Why would it be a bug? You've made it so that every instance of OBJ is
equal to every other instance of OBJ. The behaviour is as expected.

[Steve Holden]

Re: Python interpreter bug

alainpoint@yaho o.fr wrote:[color=blue]
> Hello,
>
> I came accross what i think is a serious bug in the python interpreter.
>
> Membership testing seems not to work for list of objects when these
> objects have a user-defined __cmp__ method.
> It is present in Python 2.3 and 2.4. I don't know about other versions.
> The following code illustrates the bug:
> from random import choice
> class OBJ:
> def __init__(self,i dentifier):
> self.id=identif ier
> self.allocated= 0
> def __cmp__(self,ot her):
> return cmp(other.alloc ated,self.alloc ated)
> mylist=[OBJ(i) for i in range(20)]
> excluded=[obj for obj in mylist if obj.id>choice(r ange(20))]
> for obj in mylist:
> if obj in excluded:
> assert obj.id in [objt.id for objt in excluded]
> continue
>[/color]
I presume you just put the "continue" in there for fun?
[color=blue][color=green][color=darkred]
>>> for obj in mylist:[/color][/color][/color]
.... print obj in excluded
....
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True[color=blue][color=green][color=darkred]
>>> OBJ(0) == OBJ(1)[/color][/color][/color]
True
[color=blue]
> Running the above snippet will trigger the assert. The culprit seems to
> be the __cmp__ method which sorts on a key with constant value.[/color]

Well indeed. As far as I can see your objects will all test equal. Did
you mean the __cmp__ method to return cmp(other.id, self.id)?

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[alainpoint@yahoo.fr]

Re: Python interpreter bug

There is definitely a bug.
Maybe the follownig snippet is more clear:
class OBJ:
def __init__(self,i dentifier):
self.id=identif ier
self.allocated= 0
#def __cmp__(self,ot her):
# return cmp(other.alloc ated,self.alloc ated)
mylist=[OBJ(i) for i in range(10)]
excluded=[obj for obj in mylist if obj.id in [2,4,6,8]]
exclusion_list_ by_id=[2,4,6,8]
print 'exclusion list by id=',exclusion_ list_by_id
for obj in mylist:
print 'current obj=',obj.id,
if obj in excluded:
print ' ---> THIS OBJECT IS EXCLUDED'
assert obj.id in exclusion_list_ by_id
continue
print

If you uncomment the two lines, the assert will be erroneously
triggered.
Alain

[Fredrik Lundh]

Re: Python interpreter bug

alainpoint@yaho o.fr wrote:
[color=blue]
> I came accross what i think is a serious bug in the python interpreter.[/color]
[color=blue]
> Membership testing seems not to work for list of objects when these
> objects have a user-defined __cmp__ method.[/color]

it does not work if they have *your* __cmp__ method, no. if you add
a print statement to the method, you'll figure out why:

def __cmp__(self,ot her):
print "CMP", other.allocated , self.allocated
return cmp(other.alloc ated,self.alloc ated)

</F>

[alainpoint@yahoo.fr]

Re: Python interpreter bug

Sorry Fredrik but I don't understand. Just comment out the assert and
you have different results depending on whether an unrelated sort
function is defined.
This seems weird to me !

[Steve Holden]

Re: Python interpreter bug

alainpoint@yaho o.fr wrote:[color=blue]
> Sorry Fredrik but I don't understand. Just comment out the assert and
> you have different results depending on whether an unrelated sort
> function is defined.
> This seems weird to me !
>[/color]
Perhaps you don't understand what's going on. The test

obj in excluded

is succeeding for all your objects because all instances of the OBJ
class compare equal, and so the assert is failing for the ones that
don;t actually appear in the "excluded" list.

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[alainpoint@yahoo.fr]

Re: Python interpreter bug

I understand this, Steve.
I thought the _cmp_ method was a helper for sorting purposes. Why is it
that a membership test needs to call the __cmp__ method?
If this isn't a bug, it is at least unexpected in my eyes.
Maybe a candidate for inclusion in the FAQ?
Thank you for answering
Alain

[Fredrik Lundh]

Re: Python interpreter bug

alainpoint@yaho o.fr wrote:
[color=blue]
> Sorry Fredrik but I don't understand. Just comment out the assert and
> you have different results depending on whether an unrelated sort
> function is defined.
>
> This seems weird to me ![/color]

not if you look at what it prints.

(if it seems weird to you that 0 equals 0, it's time for a break)

</F>

[wittempj@hotmail.com]

Re: Python interpreter bug

Your __cmp__ method will always return 0, so all objects will be equal
when you add the method, as Simon and Steve pointed out. The result is
all objects will pass the test of being a member of excluded.
If you do not add a __cmp__ method objects will be compared on identy -
call the id() function to see the identity of an object. An alternative
would be Steve's proposal to compare on the id attribute instead of the
allocated attribute

[wittempj@hotmail.com]

Re: Python interpreter bug

Your __cmp__ method will always return 0, so all objects will be equal
when you add the method, as Simon and Steve pointed out. The result is
all objects will pass the test of being a member of excluded.
If you do not add a __cmp__ method objects will be compared on identy -
call the id() function to see the identity of an object. An alternative
would be Steve's proposal to compare on the id attribute instead of the
allocated attribute

[Fredrik Lundh]

Re: Python interpreter bug

alainpoint@yaho o.fr wrote:
[color=blue]
> Why is it that a membership test needs to call the __cmp__ method?[/color]

because the membership test has to check if the tested item is a member
of the sequence. if it doesn't do that, it's hardly qualifies as a membership
test. from the reference manual:

For the list and tuple types, x in y is true if and only if there exists an
index i such that x == y[i] is true.

</F>

[alainpoint@yahoo.fr]

Re: Python interpreter bug

In fact, i want to sort the list based on the 'allocated attribute' and
at the same time, test membership based on the id attribute.
__cmp__ logically implies an ordering test, not an identity test. These
two notions seems to be confounded in python which is unfortunate. Two
objects could have the same rank while still being different.
Alain

[brianmce@gmail.com]

Re: Python interpreter bug

For this, you can also define the __eq__ method, which will be
preferred to __cmp__ for equallity tests while still using __cmp__ for
searching / comparisons.

[Carsten Haese]

Re: Python interpreter bug

On Fri, 2005-10-07 at 10:33, alainpoint@yaho o.fr wrote:[color=blue]
> In fact, i want to sort the list based on the 'allocated attribute' and
> at the same time, test membership based on the id attribute.
> __cmp__ logically implies an ordering test, not an identity test. These
> two notions seems to be confounded in python which is unfortunate. Two
> objects could have the same rank while still being different.
> Alain[/color]

You could use the id in __cmp__ as a tie-breaker if the two objects have
equal "allocated" values.

By the way, __cmp__ is not an identity test. The "in" operator doesn't
use object identity, it uses object equality, and __cmp__ does serve to
test object equality (if no __eq__ method is present).

Perhaps the following example will clarify the behavior of "in":
[color=blue][color=green][color=darkred]
>>> A = [1]
>>> B = [1]
>>> A==B[/color][/color][/color]
True[color=blue][color=green][color=darkred]
>>> A is B[/color][/color][/color]
False[color=blue][color=green][color=darkred]
>>> A in ["spam", 42, B][/color][/color][/color]
True

HTH,

Carsten Haese.