[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Change by Łukasz Langa : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___ ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Łukasz Langa added the comment: New changeset 8c9f847997196aa76500d1ae104cbe7fe2a467ed by Serhiy Storchaka in branch 'main': bpo-27275: Change popitem() and pop() methods of collections.OrderedDict (GH-27530) https://github.com/python/cpython/commit/8c9f847997196aa76500d1ae104cbe7fe2a467ed

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Raymond Hettinger added the comment: > I am not sure how far we should backport these changes > if backport them. We've had no reports of the current code causing problems for any existing applications (except the LRU recipe in the docs), so there is likely no value in making backports.

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: PR 27528 makes the C implementation of OrderedDict.popitem() consistent with the Python implementation (do not call overridden __getitem__ and __setitem__). PR 27530 changes also both implementations of OrderedDict.pop(). It simplifies the C code, but

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Change by Serhiy Storchaka : -- pull_requests: +26045 pull_request: https://github.com/python/cpython/pull/27530 ___ Python tracker ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Raymond Hettinger added the comment: Let's do the right thing and fix the pure python OrderedDict.pop() method as well. -- ___ Python tracker ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Change by Serhiy Storchaka : -- pull_requests: +26043 pull_request: https://github.com/python/cpython/pull/27528 ___ Python tracker ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: It is complicated. The pure Python implementation of OrderedDict.popitem() and OrderedDict.pop() are not consistent. The former uses dict.pop() which doesn't call __getitem__ and __setitem__. The latter calls __getitem__ and __setitem__. The C

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Change by Serhiy Storchaka : -- versions: +Python 3.10, Python 3.11, Python 3.9 -Python 3.5, Python 3.6, Python 3.7 ___ Python tracker ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: It was reverted because it did not keep the C version in harmony with the pure Python version. In the pure Python version pop() calls __getitem__ and __delitem__ which can be overridden in subclasses of OrederedDict. My patch always called

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Raymond Hettinger added the comment: > I think Serhiy's patch here (before revert) may be a > good idea (to re-apply). That seems sensible to me as well. It keeps the C version in harmony with the pure python version and it follows how regular dict's are implemented. Serhiy, do you

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Dennis Sweeney added the comment: bpo-44782 was opened about the `class LRU(OrderedDict)` in the OrderedDict docs, and its pop() method failing. I think Serhiy's patch here (before revert) may be a good idea (to re-apply). I think it is reasonable to ignore user-implemented dunder methods

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Roundup Robot added the comment: New changeset 3f816eecc53e by Serhiy Storchaka in branch '3.5': Backed out changeset 9f7505019767 (issue #27275). https://hg.python.org/cpython/rev/3f816eecc53e -- ___ Python tracker

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: In issue28014 __getitem__() is idempotent. Multiple calls of __getitem__() return the same result and keep the OrderedDict in the same state. > I'd be perfectly happy with making popitem implemented in terms of pop on > subclasses when pop is overridden (if

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Josh Rosenberg added the comment: The Python implementation of OrderedDict breaks for issue28014, at least on 3.4.3 (it doesn't raise KeyError, but if you check the repr, it's only showing one of the two entries, because calling __getitem__ is rearranging the OrderedDict). >>> s =

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: Ah, what is the reason for this code! But Python implementation of popitem() don't call overridden __getitem__/__delitem__. It uses dict.pop(). Simplified C implementation is closer to Python implementation. expiringdict is not the only implementation

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Josh Rosenberg added the comment: Explaining expiringdict's issue: It's two race conditions, with itself, not another thread. Example scenario (narrow race window): 1. An entry has an expiry time of X (so it will self-delete at time X or later) 2. At time X-1, the PySequence_Contains check is

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Josh Rosenberg added the comment: Serhiy, doesn't this patch "fix" the issue by making subclasses with custom __getitem__/__delitem__ implementations not have them invoked by the superclass's pop/popitem? The old code meant that pop and popitem didn't need to be overridden even if you

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Roundup Robot added the comment: New changeset 9f7505019767 by Serhiy Storchaka in branch '3.5': Issue #27275: Fixed implementation of pop() and popitem() methods in https://hg.python.org/cpython/rev/9f7505019767 New changeset 2def8a24c299 by Serhiy Storchaka in branch '3.6': Issue #27275:

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Changes by Serhiy Storchaka : -- assignee: -> serhiy.storchaka ___ Python tracker ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: Eric, could you please look at the patch? Maybe I missed some reasons for current implementation. -- ___ Python tracker

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

INADA Naoki added the comment: lgtm -- nosy: +inada.naoki ___ Python tracker ___ ___ Python-bugs-list mailing

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: Proposed patch makes the implementation of pop() and popitem() methods of the C implementation of OrderedDict matching the Python implementation. This fixes issue28014 and I suppose this fixes this issue too. -- keywords: +patch stage: test needed

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Zachary Ware added the comment: Attaching test case from #28014 here since this issue looks close enough to that one to be caused by the same thing. -- nosy: +zach.ware Added file: http://bugs.python.org/file44459/simple_lru.py ___ Python tracker

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Xiang Zhang added the comment: There seems to be some difference behaviours between C version and pure Python version when it comes to subclass. Except popitem, the constructor also goes different code path. There may be more. Should these differences be eliminated or they are accepted?

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

William Pitcock added the comment: It seems to me that calling __contains__() (PySequence_Contains()) isn't necessary, as the first and last elements of the list are already known, and therefore known to be in the list. Revising the behaviour of popitem() to avoid calling

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Xiang Zhang added the comment: Raymond, In single threaded case popitem may still fail. I want to correct my last message that popitem does not fail in this case because it calls __getitem__ but instead it calls __contains__[1]. In __contains__ it deletes the item since it expires, and

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Changes by Serhiy Storchaka : -- nosy: +eric.snow ___ Python tracker ___ ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

William Pitcock added the comment: At least in my case, the application is single-threaded. I don't think this is a locking-related issue as the expiringdict test case itself fails which is also single-threaded. -- ___ Python tracker

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Raymond Hettinger added the comment: I'm wondering if the expiringdict(1) needs to have locked wrappers for the inherited methods: def __delitem__(self, key): with self.lock: OrderedDict.__delitem__(self, key) Otherwise, there is a risk that one thread is deleting a

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Xiang Zhang added the comment: I think your expiringdict seems not work with the C version OrderedDict, you may need to change your implementation or clarify that :(. The C version's OrderedDict.popitem may call your __getitem__ which then does deletion and emit KeyError when expires. I think

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

William Pitcock added the comment: A frequent reproducer is to run the expiringdict tests on Python 3.5.1, unfortunately I cannot come up with a testcase. Replacing use of popitem() with "del self[next(OrderedDict.__iter__(self))]" removes the KeyErrors and the structure otherwise works fine.

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

Serhiy Storchaka added the comment: Could you please provide short example? -- nosy: +serhiy.storchaka stage: -> test needed ___ Python tracker ___

[issue27275] KeyError thrown by optimised collections.OrderedDict.popitem()

New submission from William Pitcock: The C-based optimised version of collections.OrderedDict occasionally throws KeyErrors when deleting items. See https://github.com/mailgun/expiringdict/issues/16 for an example of this regression. Backporting 3.6's patches to 3.5.1 does not resolve the