iter(ordered_dict) yields keys not in dict in some circumstances

[nikratio]

BPO	19414
Nosy	@arigo, @rhettinger, @abalkin, @ethanfurman, @Rosuav, @serhiy-storchaka
Files	issue19414.diff issue19414_r2.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/rhettinger'
closed_at = <Date 2014-05-04.05:05:02.940>
created_at = <Date 2013-10-27.03:27:54.629>
labels = ['type-bug', 'library']
title = 'iter(ordered_dict) yields keys not in dict in some circumstances'
updated_at = <Date 2014-06-15.01:00:31.828>
user = 'https://bugs.python.org/nikratio'

bugs.python.org fields:

activity = <Date 2014-06-15.01:00:31.828>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2014-05-04.05:05:02.940>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2013-10-27.03:27:54.629>
creator = 'nikratio'
dependencies = []
files = ['33359', '34804']
hgrepos = []
issue_num = 19414
keywords = ['patch']
message_count = 28.0
messages = ['201408', '201409', '201502', '201505', '201506', '201511', '201513', '201517', '201739', '201742', '201743', '201745', '201751', '201757', '201759', '201763', '201766', '201775', '201777', '201779', '207666', '215980', '216032', '217857', '217858', '218095', '220584', '220600']
nosy_count = 8.0
nosy_names = ['arigo', 'rhettinger', 'belopolsky', 'nikratio', 'ethan.furman', 'python-dev', 'Rosuav', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue19414'
versions = ['Python 3.5']

[nikratio]

The documentation says the following about modifying a dict while
iterating through its view:

| Iterating views while adding or deleting entries in the dictionary may
| raise a RuntimeError or fail to iterate over all entries.
(http://docs.python.org/3/library/stdtypes.html#dict-views)

The OrderedDict documentation doesn't have anything to say on the
subject. In practice, its implementation actually mostly correponds to
naive expectations:

>>> from collections import OrderedDict
>>> d = OrderedDict()
>>> for i in range(5):
...    d[i] = i
... 
>>> i = iter(d.values())
>>> next(i)
0
>>> del d[0]
>>> next(i)
1
>>> del d[2]
>>> next(i)
3
>>> d.move_to_end(1)
>>> next(i)
4
>>> next(i)
1
>>> 

etc.

However, there is one case that results in a rather confusing error:

>>> a = OrderedDict()
>>> a[0] = 0
>>> a[1] = 1
>>> a[2] = 2
>>> i = iter(a.values())
>>> next(i)
0
>>> del a[0]
>>> del a[1]
>>> next(i)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3.3/collections/abc.py", line 495, in __iter__
    yield self._mapping[key]
KeyError: 1

What happens here is that a[0] is returned from the linked list, but it
still contains links to a[1]. When a[1] is deleted, the links of its
predecessor and successor are updated, but a[0] still points to
a[1]. The OrderedList then hands a non-existing key to the values()
implementation in collections.abc.

The result is not only mightily confusing, but it is also not covered by
the documentation (KeyError isn't a RuntimeError).

I would very much like to see this fixed, but I'm not sure if there's a
good way to do that.

I see the following options:

(a) When deleting an element from an OrderedList, update the pointers in
the corresponding linked list element to the end of the list. Then
removing the currently "active" element during the iteration would
automatically end the iteration.

For that, we'd just have to add two lines to __delitem__:

    def __delitem__(self, key, dict_delitem=dict.__delitem__):
        dict_delitem(self, key)
        link = self.__map.pop(key)
        link_prev = link.prev
        link_next = link.next
        link_prev.next = link_next
        link_next.prev = link_prev

        link.prev = root # new 
        link.next = root # new
    

The new behavior is explicitly covered by the documentation
(changing the dict may result in incomplete iteration), but it's a
change to what happened before.

(b) When iterating through an OrderedDict, check that the next element
is actually still in the hash, i.e. change

    def __iter__(self):
        root = self.__root
        curr = root.next
        while curr is not root:
            yield curr.key
            curr = curr.next
    to

    def __iter__(self):
        root = self.__root
        curr = root.next
        while curr is not root and curr.key in self:
            yield curr.key
            curr = curr.next

that would terminate the iteration only in the special case, but
incur an extra dict lookup at every iteration.

Alternatively, one could try very hard to not stop the iteration:

    while curr is not root:
        yield curr.key
        while curr is not root:
            curr = curr.next
            if curr.key in self:
                break

(c) Catch the KeyError in values(), and re-raise the proper exception in
class ValuesView:

    def __iter__(self):
        for key in self._mapping:
            try:
                yield self._mapping[key]
            except KeyError:
                raise RuntimeError("underlying Mapping instance modified during iteration")

I consider this a bit ugly, because it may mask other problems in a
custom Mapping implementation (that may raise a KeyError because of
a bug in the Mapping implementation itself).

(d) Extend the OrderedDict documentation to explicity document this
case.

This has the drawback that it would probably be nicer to just have
the behavior be consistent and correspond to intuitive expectations.

Would any of those fixes be acceptable? Or is there an even better option?

[nikratio]

After thinking about this a bit more, I think this is actually a true bug in OrderedDict(), and only option (a) or be (b) really fix it.

Rationale:

I would expect that for any OrderedDict d, and any function modify_dict(d), the following assertion holds:

for key in d:
    assert key in d
    modify_dict(d)

..but this actually breaks for

def modify_dict(d):
    del d[0]
    del d[1]

[arigo]

Another option for the "try harder to raise RuntimeError" category (which I tend to like, because otherwise people are bound to write programs that rely on undocumented details):

In __delitem__() set link.next = None. In the various iterators check explicitly if curr.next is None, and raise RuntimeError if it is.

[nikratio]

Being able to modify an OrderedDict while iterating through it is pretty useful though.

What about documenting that modifying an OrderedDict is allowed, but may cause iteration to skip or repeat items (but do not allow it to raise RuntimeError)?

As far as I can tell, the current implementation will already guarantee that (as soon as this issue is fixed).

[arigo]

Modifying an ordered dict while iterating over it can be officially classified as an ok think to do, but then the precise behavior must described in the documentation in some details, with of course matching implementation(s) and tests. I mean by that that the behavior should not be "it might miss some elements", but rather something precise like: consider the ordered dict as simply a list of its elements, and consider __delitem__ as replacing an element with NULL. Then forward or backward iteration works like forward or backward iteration over this list, with the additional rule that NULL elements are skipped over.

It would imho be a good possible solution, but it obviously requires more effort.

[nikratio]

I'd be happy to provide a more extensive patch along the lines Armin suggested if that is considered a good idea (not sure who has to make that decision).

[rhettinger]

I'm inclined to document that "iterating views while adding or deleting entries an ordered dictionary is an undefined behavior".

[arigo]

Hi Raymond! Yes, I had the same reaction at first, but then it seemed to be possible to implement a reasonably good behavior with almost no performance hit.

Plainly undefined behaviors are a mess for other implementations because in half of the big projects people don't realize they depend on it at some place --- particularly if the behavior is "mostly sane", as it seems to be right now for OrderedDict.

For example, I believe the following code to always work:

    for key in ordered_dict:
        if some_condition:
            del ordered_dict[key]

whereas it always raise RuntimeError with regular dicts, which are both ok choices. But silently not working would be much worse.

[ethanfurman]

Do we currently have any data structures in Python, either built-in or in the stdlib, that aren't documented as raising RuntimeError if the size changes during iteration? list, dict, set, and defaultdict all behave this way.

If not, I think OrderedDict should behave this way as well.

[arigo]

'list' doesn't, precisely.

[ethanfurman]

Ah, right you are: list just acts wierd. ;)

So the question then becomes is OrderedDict more like a list or more like a dict?

It seems to me that OrderedDict is more like a dict.

[nikratio]

I agree that OrderedDict is more a dict than a list, but it is not clear to me why this means that it cannot extend a dict's functionality in that respect.

OrderedDict already adds functionality to dict (preserving the order), so why shouldn't it also allow changes during iteration?

I think these two things actually come together quite naturally, since it is the existence of an ordering that makes the behavior under changes during iteration well defined.

Is there really a danger that people will get confused because a previously undefined operation now becomes officially supported with a defined meaning?