[issue19414] OrderedDict.values() behavior for modified instance
Ethan Furman added the comment: 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. -- nosy: +ethan.furman ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Armin Rigo added the comment: 'list' doesn't, precisely. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Ethan Furman added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Nikolaus Rath added the comment: 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? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Ethan Furman added the comment: The further from dict it goes, the more there is to remember. Considering the work around is so simple, I just don't think it's worth it: for key in list(ordered_dict): if some_condition: del ordered_dict[key] A simple list around the dict and we're good to go; and this trick works with dicts, defaultdicts, sets, lists (when you don't want the skipping behavior), etc. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Nikolaus Rath added the comment: The workaround is trivial, but there is no technical necessity for it, and it involves copying the entire dict into a list purely for.. what exactly? I guess I do not understand the drawback of allowing changes. What is wrong with for key in ordered_dict: if some_condition: del ordered_dict[key] to be working? Is it really just the fact that the above could does not work for regular dicts? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Nikolaus Rath added the comment: Ethan: when you say ..the more there is to remember, what exactly do you mean? I can see that it is important to remember that you're *not allowed* to make changes during iteration for a regular dict. But is there really a significant cognitive burden if it were allowed for ordered dicts? You're not forced to use the feature, since you can still safely continue to use ordered dicts like regular dicts. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Ethan Furman added the comment: Firstly, you're not copying the entire dict, just its keys. [1] Secondly, you're only copying the keys when you'll be adding/deleting keys from the dict. Thirdly, using the list idiom means you can use OrderedDicts, defaultdicts, dicts, sets, and most likely any other mapping type the same way, whereas if you make OrderedDict special in this area you've locked out the other types. In my opinion the differences in OrderedDict should be limited to what is necessary to make a dict ordered. The ability to insert/delete keys while iterating is not necessary to maintaining an order, and the break from other dicts doesn't add enough value to make it worth it. So, yes, the short answer is because Python's other similar types don't do it that way, OrderedDict shouldn't either. [1] If the dict is large, collect the to_be_deleted keys in a separate list and remove them after the loop. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Ethan Furman added the comment: 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: 1) hey, that won't work 2) oh, wait, is this an OrderedDict? 3) (yes) oh, okay, it's fine then done 3) (no) hmm, well, it was supposed to be, but a regular dict was passed in 4) okay, we either fix the code here to handle regular dicts (use 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Nikolaus Rath added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Ethan Furman added the comment: Personally, I would rather see a RuntimeError raised. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Serhiy Storchaka added the comment: See also issue19332. -- nosy: +serhiy.storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Armin Rigo added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Changes by Ned Deily n...@acm.org: -- nosy: +rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Armin Rigo added the comment: 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. -- nosy: +arigo ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Nikolaus Rath added the comment: 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). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Armin Rigo added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Nikolaus Rath added the comment: 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). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Changes by Raymond Hettinger raymond.hettin...@gmail.com: -- assignee: - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Raymond Hettinger added the comment: I'm inclined to document that iterating views while adding or deleting entries an ordered dictionary is an undefined behavior. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
New submission from Nikolaus Rath: 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? -- components: Library (Lib) messages: 201408 nosy: Nikratio priority: normal severity: normal status: open title: OrderedDict.values() behavior for modified instance type: behavior versions: Python 3.5 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19414] OrderedDict.values() behavior for modified instance
Nikolaus Rath added the comment: 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] -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19414 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
