Issue #27275: Fixed implementation of pop() and popitem() methods in

subclasses of accelerated OrderedDict.

3 files changed, 69 insertions, 22 deletions

diff --git a/Lib/test/test_ordered_dict.py b/Lib/test/test_ordered_dict.py
index 901d4b2..fb3cd8b 100644
--- a/Lib/test/test_ordered_dict.py
+++ b/Lib/test/test_ordered_dict.py
@@ -730,5 +730,64 @@ class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
         self.assertRaises(KeyError, d.popitem)
 
 
+class SimpleLRUCache:
+
+    def __init__(self, size):
+        super().__init__()
+        self.size = size
+
+    def __getitem__(self, item):
+        value = super().__getitem__(item)
+        self.move_to_end(item)
+        return value
+
+    def __setitem__(self, key, value):
+        while key not in self and len(self) >= self.size:
+            self.popitem(last=False)
+        super().__setitem__(key, value)
+        self.move_to_end(key)
+
+
+class SimpleLRUCacheTests:
+
+    def test_add_after_full(self):
+        c = self.type2test(2)
+        c['t1'] = 1
+        c['t2'] = 2
+        c['t3'] = 3
+        self.assertEqual(list(c), ['t2', 't3'])
+
+    def test_popitem(self):
+        c = self.type2test(3)
+        for i in range(1, 4):
+            c[i] = i
+        self.assertEqual(c.popitem(last=False), (1, 1))
+        self.assertEqual(c.popitem(last=True), (3, 3))
+
+    def test_change_order_on_get(self):
+        c = self.type2test(3)
+        for i in range(1, 4):
+            c[i] = i
+        self.assertEqual(list(c), list(range(1, 4)))
+        self.assertEqual(c[2], 2)
+        self.assertEqual(list(c), [1, 3, 2])
+
+
+class PySimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
+
+    class type2test(SimpleLRUCache, py_coll.OrderedDict):
+        pass
+
+
+@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
+class CSimpleLRUCacheTests(SimpleLRUCacheTests, unittest.TestCase):
+
+    @classmethod
+    def setUpClass(cls):
+        class type2test(SimpleLRUCache, c_coll.OrderedDict):
+            pass
+        cls.type2test = type2test
+
+
 if __name__ == "__main__":
     unittest.main()
diff --git a/Misc/NEWS b/Misc/NEWS
index a20870f..7b1d9d9 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -113,6 +113,9 @@ Core and Builtins
 Library
 -------
 
+- Issue #27275: Fixed implementation of pop() and popitem() methods in
+  subclasses of accelerated OrderedDict.
+
 - Issue #28255: calendar.TextCalendar().prmonth() no longer prints a space
   at the start of new line after printing a month's calendar.  Patch by
   Xiang Zhang.
diff --git a/Objects/odictobject.c b/Objects/odictobject.c
index a6963d7..b4940e3 100644
--- a/Objects/odictobject.c
+++ b/Objects/odictobject.c
@@ -1099,28 +1099,13 @@ _odict_popkey_hash(PyObject *od, PyObject *key, PyObject *failobj,
     }
 
     /* Now delete the value from the dict. */
-    if (PyODict_CheckExact(od)) {
-        if (node != NULL) {
-            value = _PyDict_GetItem_KnownHash(od, key, hash);  /* borrowed */
-            if (value != NULL) {
-                Py_INCREF(value);
-                if (_PyDict_DelItem_KnownHash(od, key, hash) < 0) {
-                    Py_DECREF(value);
-                    return NULL;
-                }
-            }
-        }
-    }
-    else {
-        int exists = PySequence_Contains(od, key);
-        if (exists < 0)
-            return NULL;
-        if (exists) {
-            value = PyObject_GetItem(od, key);
-            if (value != NULL) {
-                if (PyObject_DelItem(od, key) == -1) {
-                    Py_CLEAR(value);
-                }
+    if (node != NULL) {
+        value = _PyDict_GetItem_KnownHash(od, key, hash);  /* borrowed */
+        if (value != NULL) {
+            Py_INCREF(value);
+            if (_PyDict_DelItem_KnownHash(od, key, hash) < 0) {
+                Py_DECREF(value);
+                return NULL;
             }
         }
     }