classification
Title: Using OrderedDict.move_to_end during iteration is problematic.
Type: behavior Stage: resolved
Components: Library (Lib) Versions: Python 3.6, Python 3.5
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: eric.snow Nosy List: eric.snow, python-dev, rhettinger
Priority: normal Keywords: patch

Created on 2015-06-03 00:12 by eric.snow, last changed 2015-06-04 06:13 by eric.snow. This issue is now closed.

Files
File name Uploaded Description Edit
issue24369-iteration-mutation.diff eric.snow, 2015-06-03 18:35
Messages (6)
msg244718 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2015-06-03 00:12
While the dict/OrderedDict iterators already check for additions and deletions, using the OrderedDict.move_to_end during iteration can lead to surprising results.

The following results in an infinite loop:

    od = OrderedDict.fromkeys('abc')
    last = None
    for k in od:
        if last is not None:
            od.move_to_end(last)
        last = k

Ideally we could disallow changing order during iteration, just like we disallow deletion.  Since we've gone 3 minor versions already, would it be too late to break backward compatibility on this point?
msg244723 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-06-03 01:58
The C version should defend itself against any key-changes during iteration (see the state counter used in deque objects for an example of how to do this).   The pure python version of OrderedDict has only minimal defenses against mutating during iteration, and it should be left as-is.

FWIW, "surprising" is in the eye of the beholder.  When it comes to mutating containers during iteration, all kinds of things can happen (that is why databases implement reader and writer locks).  

The following results in an infinite loop:

    s = list('abc')
    for k in s:
        s.append(k)
msg244725 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2015-06-03 02:31
Sounds good.  Thanks, Raymond.
msg244785 - (view) Author: Eric Snow (eric.snow) * (Python committer) Date: 2015-06-03 18:35
Here's a patch that tracks changes to the C OrderedDict linked list, similar to how it's done in deque.  I've left the pure Python OrderedDict alone.

@Raymond, that state counter works great. :)
msg244800 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2015-06-04 05:43
This patch looks correct.  Go ahead and apply.
msg244803 - (view) Author: Roundup Robot (python-dev) Date: 2015-06-04 06:12
New changeset 0d8679858272 by Eric Snow in branch '3.5':
Issue #24369: Defend against key-changes during iteration.
https://hg.python.org/cpython/rev/0d8679858272
History
Date User Action Args
2015-06-04 06:13:02eric.snowsetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2015-06-04 06:12:36python-devsetnosy: + python-dev
messages: + msg244803
2015-06-04 05:43:02rhettingersetassignee: rhettinger -> eric.snow
messages: + msg244800
2015-06-03 18:35:40eric.snowsetfiles: + issue24369-iteration-mutation.diff
keywords: + patch
messages: + msg244785

stage: test needed -> patch review
2015-06-03 02:31:19eric.snowsetmessages: + msg244725
2015-06-03 01:58:20rhettingersetpriority: high -> normal
assignee: rhettinger
messages: + msg244723

versions: - Python 3.4
2015-06-03 00:12:18eric.snowcreate