[issue23987] docs about containers membership testing wrong for broken objects

[Peter Nowee]

Change by Peter Nowee :


--
nosy: +peternowee

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Raymond Hettinger]

Raymond Hettinger  added the comment:

It looks like the identity-implies-equality part of this has already been taken 
care of.   The __hash__ invariant also appears to now have extensive coverage, 
some in the glossary and much more in the data model section of the reference.  
Cute puzzles like a __hash__ returning a random value can be left for 
stackoverflow.

--
resolution:  -> out of date
stage:  -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Ethan Furman]

Changes by Ethan Furman et...@stoneleaf.us:


--
nosy:  -ethan.furman

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Raymond Hettinger]

Raymond Hettinger added the comment:

There is a separate report for taking care of the identity check for contains:  
https://bugs.python.org/issue23986

I think notes about crazy hashes shouldn't spill all over our docs.  At best, 
it warrants a FAQ entry about how hash tables work.

The risk here is that in an effort to be more precise, it is easy impair the 
usability of the docs.  The wording in question has been around for a very long 
time and has overall done a good job of explaining the intent of the 
in-operator to all but the most pedantic reader, The operators 'in' and 'not 
in' test for membership. 'x in s' evaluates to true if x is a member of s, and 
false otherwise.

If you really want to be precise, the *only* thing that can be broadly stated 
about the in-operator is that it calls __contains__ on an object that that 
object can implement whatever logic it wants (hash table lookup, linear search, 
google search, random result, etc).  But then, this is no different than most 
magic methods in that regard.

--
assignee: docs@python - rhettinger
nosy: +rhettinger

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[R. David Murray]

R. David Murray added the comment:

Yes, that's what I had in mind.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Ethan Furman]

Ethan Furman added the comment:

So something like:

For container types such as list, tuple, or collections.deque, the expression 
'x in y' is equivalent to 'any(x is e or x == e for e in y)'.  For container 
types such as set, frozenset, and dict, this equivalence expression is modified 
by the addition of 'if hash(x) == hash(e)'.

?

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Jonathan Sharpe]

Jonathan Sharpe added the comment:

I don't think it's as simple as linking to the hashable definition. The 
equivalent expression is simply wrong for dict/set/frozenset, as those types 
check hash equality, not identity.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Ethan Furman]

New submission from Ethan Furman:

https://docs.python.org/3/reference/expressions.html#comparisons:

The operators 'in' and 'not in' test for membership. 'x in s' evaluates to true 
if x is a member of s, and false otherwise. 'x not in s' returns the negation 
of 'x in s'. All built-in sequences and set types support this as well as 
dictionary, for which 'in' tests whether the dictionary has a given key. For 
container types such as list, tuple, set, frozenset, dict, or 
collections.deque, the expression 'x in y' is equivalent to 'any(x is e or x == 
e for e in y)'.

StackOverflow question for context: http://stackoverflow.com/q/29692140/208880

Summary:  if a user creates a broken object such that __hash__ returns a random 
number with every invocation, then that object will get lost in a dict or set; 
but the above statement about 'equivalent to' claims that such an object will 
still be found.

On the other hand, https://docs.python.org/3/glossary.html#term-hashable says 
that a constant return value is required for an object to be hashable (of 
course, Python can't tell if future calls to __hash__ will return the same 
value).

Perhaps a link to the #term-hashable would be appropriate?

--
messages: 241320
nosy: eric.araujo, ethan.furman, ezio.melotti, georg.brandl
priority: normal
severity: normal
status: open
title: docs about containers membership testing wrong for broken objects
versions: Python 3.4, Python 3.5

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Jonathan Sharpe]

Changes by Jonathan Sharpe j.r.sharpe+pyt...@gmail.com:


--
assignee:  - docs@python
components: +Documentation
nosy: +docs@python, jonrsharpe

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Ethan Furman]

Ethan Furman added the comment:

It's not quite that simple -- those containers use the hash to find the objects 
that will be first checked by identity, and then equality* -- otherwise they 
would have to do a complete scan from first key to last, and that would kill 
performance.

...

Okay, I see your point -- even for sane objects, a systematic check of every 
key is not undertaken for the hash-type containers.

Perhaps something like:

For container types such as list, tuple, or collections.deque, the expression 
'x in y' is equivalent to 'any(x is e or x == e for e in y)'.  For container 
types such as set, frozenset, and dict, 'x in y' is equivalent to 'any(x is e 
or x == e for e in z)' where 'z' is a collection of objects in 'y' that have 
the same hash.

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[Ethan Furman]

Ethan Furman added the comment:

I think I like that better than my suggestion.  :)

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue23987] docs about containers membership testing wrong for broken objects

[R. David Murray]

R. David Murray added the comment:

Could we add For dictionaries and sets this equivalence expression is modified 
by the addition of 'if hash(x) == hash(e)'?

--
nosy: +r.david.murray

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue23987
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com