Repository navigation
iter(ordered_dict) yields keys not in dict in some circumstances #63613
Description
| BPO | 19414 |
|---|---|
| Nosy | @arigo, @rhettinger, @abalkin, @ethanfurman, @Rosuav, @serhiy-storchaka |
| Files |
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']
Activity
nikratio commentedon Oct 27, 2013
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:
etc.
However, there is one case that results in a rather confusing error:
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.
(b) When iterating through an OrderedDict, check that the next element
is actually still in the hash, i.e. change
(c) Catch the KeyError in values(), and re-raise the proper exception in
class ValuesView:
(d) Extend the OrderedDict documentation to explicity document this
case.
Would any of those fixes be acceptable? Or is there an even better option?
nikratio commentedon Oct 27, 2013
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:
..but this actually breaks for
arigo commentedon Oct 27, 2013
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 commentedon Oct 27, 2013
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 commentedon Oct 27, 2013
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 commentedon Oct 28, 2013
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 commentedon Oct 28, 2013
I'm inclined to document that "iterating views while adding or deleting entries an ordered dictionary is an undefined behavior".
arigo commentedon Oct 28, 2013
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:
whereas it always raise RuntimeError with regular dicts, which are both ok choices. But silently not working would be much worse.
ethanfurman commentedon Oct 30, 2013
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 commentedon Oct 30, 2013
'list' doesn't, precisely.
ethanfurman commentedon Oct 30, 2013
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 commentedon Oct 30, 2013
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?
4 remaining items
ethanfurman commentedon Oct 30, 2013
Nikolaus, in reply to your question about "more to remember":
Even though I may not use it myself, if it is allowed then at some point I will see it in code; when that happens the sequence of events is something like:
passed in
list idiom); or
go back to calling code and make this an OrderedDict
I see that as a lot of extra effort for a non-necessary change.
nikratio commentedon Oct 30, 2013
Hmm. I see your point. You might be right (I'm not fully convinced yet though), but this bug is probably not a good place to go into more detail about this.
So what would be the best way to fix the immediate problem this was originally about? Raise a RuntimeError (as Armin suggested), or just end the iteration?
Note that RuntimeError would only be raised when the current element is removed from the dict, and the ordered dict would still tolerate other kinds of modifications.
Both variants would also be a change from previous behavior (were removing the current elements works as long as you do not remove the next one as well).
The minimally intrusive change would be to skip over elements that have been removed, but that comes at the expense of an additional membership test in each iteration.
ethanfurman commentedon Oct 30, 2013
Personally, I would rather see a RuntimeError raised.
serhiy-storchaka commentedon Oct 30, 2013
See also bpo-19332.
[-]OrderedDict.values() behavior for modified instance[/-][+]iter(ordered_dict) yields keys not in dict in some circumstances[/+]nikratio commentedon Jan 8, 2014
I have attached a patch that fixes this issue. Looking at Raymonds comments in bpo-19332, I have kept new code out of the critical path in __iter__ and instead modified the __delitem__ method (I assume that an element is removed only once, but may be iterated over many times). The updated __delitem__ now also updates the prev and next links of the removed item itself. When the current item is removed during an iteration, the iteration thus stops.
I hope that's an acceptable solution.
Rosuav commentedon Apr 12, 2014
I agree that current behaviour is a bit confusing; also, the implication is that deleting from the dictionary while you have an iterator may leave some hanging references around the place, which raises a red flag in my mind (maybe something else might find the stale data, too).
My inclination would be to Armin's idea of setting next to None. Seems simpler than trying too hard to patch around something that's a bad idea anyway.
nikratio commentedon Apr 13, 2014
The patch applies cleanly to 3.4 and 3.5, not sure why the review link does not show up. I'm attaching the file again, maybe that helps.
python-dev commentedon May 4, 2014
New changeset a3c345ba3563 by Raymond Hettinger in branch 'default':
Issue bpo-19414: Have the OrderedDict mark deleted links as unusable.
http://hg.python.org/cpython/rev/a3c345ba3563
rhettinger commentedon May 4, 2014
To address Armin's concern, I'm triggering an early failure by setting the link fields to None. That will help prevent accidental reliance on non-guaranteed behaviors.
nikratio commentedon May 8, 2014
Raymond, I think your patch does not really address the issue reported here. The dict documentation still guarantees that mutating a dict during iteration will raise a RuntimeError or may skip elements. The OrderedDict documentation still does not point out that OrderedDicts behave differently, yet they still raise a different exception than a regular dict in the same situation.
I believe it should be possible to pass an OrderedDict to any function expecting a regular dict. This is still not possible. But even if you think this is not desirable (or not worth the cost), could we at least *document* that OrderedDicts behave differently?
nikratio commentedon Jun 14, 2014
Raymond, it would be nice if you could respond to my last comment...
rhettinger commentedon Jun 15, 2014
Sorry Nikolaus, I'm happy with the code and docs as they are. In general, you should assume that unless documented otherwise, any pure python container (stdlib or 3rd party) has undefined behavior if you mutate while iterating (like you should not assume thread-safety unless a container is documented as threadsafe). At your behest, I added extra code to trigger an earlier and more visible failure in some circumstances, but that is the limit. OrderedDicts have been around for a good while (not just the stdlib but also in other code predating the one in the stdlib), so we know that this hasn't been a problem in practice.
Please declare victory, move on, and don't keep extending this closed thread.