Using OrderedDict.move_to_end during iteration is problematic.

[ericsnowcurrently]

BPO	24369
Nosy	@rhettinger, @ericsnowcurrently
Files	issue24369-iteration-mutation.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/ericsnowcurrently'
closed_at = <Date 2015-06-04.06:13:02.847>
created_at = <Date 2015-06-03.00:12:18.679>
labels = ['type-bug', 'library']
title = 'Using OrderedDict.move_to_end during iteration is problematic.'
updated_at = <Date 2015-06-04.06:13:02.846>
user = 'https://github.com/ericsnowcurrently'

bugs.python.org fields:

activity = <Date 2015-06-04.06:13:02.846>
actor = 'eric.snow'
assignee = 'eric.snow'
closed = True
closed_date = <Date 2015-06-04.06:13:02.847>
closer = 'eric.snow'
components = ['Library (Lib)']
creation = <Date 2015-06-03.00:12:18.679>
creator = 'eric.snow'
dependencies = []
files = ['39610']
hgrepos = []
issue_num = 24369
keywords = ['patch']
message_count = 6.0
messages = ['244718', '244723', '244725', '244785', '244800', '244803']
nosy_count = 3.0
nosy_names = ['rhettinger', 'python-dev', 'eric.snow']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue24369'
versions = ['Python 3.5', 'Python 3.6']

[ericsnowcurrently]

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?

[rhettinger]

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)

[ericsnowcurrently]

Sounds good. Thanks, Raymond.

[ericsnowcurrently]

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. :)

[rhettinger]

This patch looks correct. Go ahead and apply.

[python-dev]

New changeset 0d8679858272 by Eric Snow in branch '3.5':
Issue bpo-24369: Defend against key-changes during iteration.
https://hg.python.org/cpython/rev/0d8679858272