classification
Title: UserDict test assumes ordered dict repr
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.4
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: christian.heimes, haypo, larry, pitrou, python-dev, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2013-11-20 17:09 by larry, last changed 2013-11-22 02:36 by python-dev. This issue is now closed.

Files
File name Uploaded Description Edit
issue19664.patch serhiy.storchaka, 2013-11-21 18:12 review
Messages (10)
msg203509 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2013-11-20 17:09
If you run Lib/test/test_userdict.py enough times, sooner or later it'll produce a spurious error.  I wrote a shell script that ran "./python -m test test_userdict" a zillion times; here's a snippet of output from running that script:

[...]
1 test OK.
[1/1] test_userdict
1 test OK.
[1/1] test_userdict
1 test OK.
[1/1] test_userdict
test test_userdict failed -- Traceback (most recent call last):
  File "/home/larry/src/python/clinic/Lib/test/test_userdict.py", line 48, in test_all
    self.assertEqual(repr(u2), repr(d2))
AssertionError: "{'one': 1, 'two': 2}" != "{'two': 2, 'one': 1}"
- {'one': 1, 'two': 2}
+ {'two': 2, 'one': 1}


1 test failed:
    test_userdict
[1/1] test_userdict
1 test OK.
[1/1] test_userdict
1 test OK.
[...]

Line 48 reads as follows:
    self.assertEqual(repr(u2), repr(d2))

I realize this code is ancient--but it seems to rely on repr of a dict producing consistent output, which is silly and has always been wrong.

Raymond, you want to take this?
msg203514 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2013-11-20 17:16
In test_set, I fixed the issue by parsing repr() output, sorting items and then compare sorted items :-)
msg203519 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-11-20 18:22
> I realize this code is ancient--but it seems to rely on repr of a dict 
> producing consistent output, which is silly

Well, it sounds a bit weird to me... If you're building the dict always in the same way, intuitively it should always produce the same repr() during the same interpreter session. Do you know why it doesn't?
msg203524 - (view) Author: Larry Hastings (larry) * (Python committer) Date: 2013-11-20 19:35
I don't know for sure--I haven't stepped through it--but here's an informed guess.  It relies on key collision.

The first dict is created the normal way.  It contains two values, "one" (set to 1) and "two" (set to 2), inserted in that order.

The second dict is created by calling dict.update(), passing in the first dict.  update() iterates over the keys of the dict's hash table with a simple for(;;) loop, copying the key and value each time.  The order is effectively random.

The repr() then iterates over the keys using the same simple for(;;) loop, spitting out key=value strings.

Let's assume that the keys collide.  "one" is inserted first, so it gets its first choice.  "two" is inserted second so it must probe.  Let's assume that its second choice is a key slot *lower* (nearer to [0]) than "one".

Now when we use update(), the for(;;) loop sees "two" first.  So "two" gets its first choice, which means "one" must now probe.  If "one"'s second choice is a key slot *higher* (further from [0]) than "two", we'll see the behavior.

(Why does this only happen sometimes?  Because we're using "hash randomization".)
msg203525 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-11-20 19:40
> I don't know for sure--I haven't stepped through it--but here's an
> informed guess.  It relies on key collision.

Ok, I see. The frequency of the errors then depends on the frequency of
collisions for two fixed keys and a varying hash seed...
msg203662 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-11-21 18:12
Here is a patch for test_userdict.
msg203687 - (view) Author: STINNER Victor (haypo) * (Python committer) Date: 2013-11-21 22:45
issue19664.patch looks good to me.

Funny fact: test_repr() of test_dict only test dictionaries with 1 item :)
msg203703 - (view) Author: Roundup Robot (python-dev) Date: 2013-11-22 00:18
New changeset a0ec33b83ba4 by Christian Heimes in branch 'default':
Issue #19664: test_userdict's repr test no longer depends on the order
http://hg.python.org/cpython/rev/a0ec33b83ba4
msg203704 - (view) Author: Christian Heimes (christian.heimes) * (Python committer) Date: 2013-11-22 00:20
Thanks Serhiy! Your patch was simple yet elegant. :)
msg203713 - (view) Author: Roundup Robot (python-dev) Date: 2013-11-22 02:36
New changeset b62eb82ca5ef by Christian Heimes in branch 'default':
Issue #19664: fix another flake test_userdict test
http://hg.python.org/cpython/rev/b62eb82ca5ef
History
Date User Action Args
2013-11-22 02:36:57python-devsetmessages: + msg203713
2013-11-22 00:20:06christian.heimessetstatus: open -> closed
resolution: fixed
messages: + msg203704

stage: needs patch -> resolved
2013-11-22 00:18:03python-devsetnosy: + python-dev
messages: + msg203703
2013-11-21 22:45:03hayposetmessages: + msg203687
2013-11-21 18:12:38serhiy.storchakasetfiles: + issue19664.patch

nosy: + serhiy.storchaka
messages: + msg203662

keywords: + patch
2013-11-21 16:31:23christian.heimessetnosy: + christian.heimes
2013-11-21 08:21:34rhettingersetassignee: rhettinger
2013-11-20 19:40:45pitrousetmessages: + msg203525
2013-11-20 19:35:16larrysetmessages: + msg203524
2013-11-20 18:22:35pitrousetnosy: + pitrou
messages: + msg203519
2013-11-20 17:16:13hayposetnosy: + haypo
messages: + msg203514
2013-11-20 17:09:42larrycreate