Issue #16991: Add a C implementation of collections.OrderedDict.

1 files changed, 184 insertions, 18 deletions

diff --git a/Lib/test/test_collections.py b/Lib/test/test_collections.py
index 58d2e9c54d..c6db13ecfb 100644
--- a/Lib/test/test_collections.py
+++ b/Lib/test/test_collections.py
@@ -1,7 +1,8 @@
 """Unit tests for collections.py."""
 
 import unittest, doctest, operator
-from test.support import TESTFN, forget, unlink
+from test.support import TESTFN, forget, unlink, import_fresh_module
+import contextlib
 import inspect
 from test import support
 from collections import namedtuple, Counter, OrderedDict, _count_elements
@@ -1609,9 +1610,24 @@ class TestCounter(unittest.TestCase):
 ### OrderedDict
 ################################################################################
 
-class TestOrderedDict(unittest.TestCase):
+py_coll = import_fresh_module('collections', blocked=['_collections'])
+c_coll = import_fresh_module('collections', fresh=['_collections'])
+
+
+@contextlib.contextmanager
+def replaced_module(name, replacement):
+    original_module = sys.modules[name]
+    sys.modules[name] = replacement
+    try:
+        yield
+    finally:
+        sys.modules[name] = original_module
+
+
+class OrderedDictTests:
 
     def test_init(self):
+        OrderedDict = self.module.OrderedDict
         with self.assertRaises(TypeError):
             OrderedDict([('a', 1), ('b', 2)], None)                                 # too many args
         pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
@@ -1635,6 +1651,7 @@ class TestOrderedDict(unittest.TestCase):
             [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7)])
 
     def test_update(self):
+        OrderedDict = self.module.OrderedDict
         with self.assertRaises(TypeError):
             OrderedDict().update([('a', 1), ('b', 2)], None)                        # too many args
         pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
@@ -1675,11 +1692,17 @@ class TestOrderedDict(unittest.TestCase):
         self.assertRaises(TypeError, OrderedDict().update, (), ())
         self.assertRaises(TypeError, OrderedDict.update)
 
+        self.assertRaises(TypeError, OrderedDict().update, 42)
+        self.assertRaises(TypeError, OrderedDict().update, (), ())
+        self.assertRaises(TypeError, OrderedDict.update)
+
     def test_abc(self):
+        OrderedDict = self.module.OrderedDict
         self.assertIsInstance(OrderedDict(), MutableMapping)
         self.assertTrue(issubclass(OrderedDict, MutableMapping))
 
     def test_clear(self):
+        OrderedDict = self.module.OrderedDict
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         shuffle(pairs)
         od = OrderedDict(pairs)
@@ -1688,6 +1711,7 @@ class TestOrderedDict(unittest.TestCase):
         self.assertEqual(len(od), 0)
 
     def test_delitem(self):
+        OrderedDict = self.module.OrderedDict
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         od = OrderedDict(pairs)
         del od['a']
@@ -1697,6 +1721,7 @@ class TestOrderedDict(unittest.TestCase):
         self.assertEqual(list(od.items()), pairs[:2] + pairs[3:])
 
     def test_setitem(self):
+        OrderedDict = self.module.OrderedDict
         od = OrderedDict([('d', 1), ('b', 2), ('c', 3), ('a', 4), ('e', 5)])
         od['c'] = 10           # existing element
         od['f'] = 20           # new element
@@ -1704,6 +1729,7 @@ class TestOrderedDict(unittest.TestCase):
                          [('d', 1), ('b', 2), ('c', 10), ('a', 4), ('e', 5), ('f', 20)])
 
     def test_iterators(self):
+        OrderedDict = self.module.OrderedDict
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         shuffle(pairs)
         od = OrderedDict(pairs)
@@ -1720,6 +1746,11 @@ class TestOrderedDict(unittest.TestCase):
         self.assertEqual(list(reversed(od.items())), list(reversed(pairs)))
 
     def test_detect_deletion_during_iteration(self):
+        # XXX This test should also work under cOrderedDict.
+        if self.module is c_coll:
+            raise unittest.SkipTest("only valid for pure Python OrderedDict")
+
+        OrderedDict = self.module.OrderedDict
         od = OrderedDict.fromkeys('abc')
         it = iter(od)
         key = next(it)
@@ -1729,7 +1760,21 @@ class TestOrderedDict(unittest.TestCase):
             # The only guarantee that the next() will not succeed
             next(it)
 
+    def test_sorted_iterators(self):
+        OrderedDict = self.module.OrderedDict
+        with self.assertRaises(TypeError):
+            OrderedDict([('a', 1), ('b', 2)], None)
+        pairs = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
+        od = OrderedDict(pairs)
+        self.assertEqual(sorted(od), [t[0] for t in pairs])
+        self.assertEqual(sorted(od.keys()), [t[0] for t in pairs])
+        self.assertEqual(sorted(od.values()), [t[1] for t in pairs])
+        self.assertEqual(sorted(od.items()), pairs)
+        self.assertEqual(sorted(reversed(od)),
+                         sorted([t[0] for t in reversed(pairs)]))
+
     def test_popitem(self):
+        OrderedDict = self.module.OrderedDict
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         shuffle(pairs)
         od = OrderedDict(pairs)
@@ -1739,7 +1784,18 @@ class TestOrderedDict(unittest.TestCase):
             od.popitem()
         self.assertEqual(len(od), 0)
 
+    def test_popitem_last(self):
+        OrderedDict = self.module.OrderedDict
+        pairs = [(i, i) for i in range(30)]
+
+        obj = OrderedDict(pairs)
+        for i in range(8):
+            obj.popitem(True)
+        obj.popitem(True)
+        self.assertEqual(len(obj), 21)
+
     def test_pop(self):
+        OrderedDict = self.module.OrderedDict
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         shuffle(pairs)
         od = OrderedDict(pairs)
@@ -1764,6 +1820,7 @@ class TestOrderedDict(unittest.TestCase):
             m.pop('a')
 
     def test_equality(self):
+        OrderedDict = self.module.OrderedDict
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         shuffle(pairs)
         od1 = OrderedDict(pairs)
@@ -1779,6 +1836,7 @@ class TestOrderedDict(unittest.TestCase):
         self.assertNotEqual(od1, OrderedDict(pairs[:-1]))
 
     def test_copying(self):
+        OrderedDict = self.module.OrderedDict
         # Check that ordered dicts are copyable, deepcopyable, picklable,
         # and have a repr/eval round-trip
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
@@ -1787,12 +1845,17 @@ class TestOrderedDict(unittest.TestCase):
             msg = "\ncopy: %s\nod: %s" % (dup, od)
             self.assertIsNot(dup, od, msg)
             self.assertEqual(dup, od)
+            self.assertEqual(list(dup.items()), list(od.items()))
+            self.assertEqual(len(dup), len(od))
+            self.assertEqual(type(dup), type(od))
         check(od.copy())
         check(copy.copy(od))
         check(copy.deepcopy(od))
-        for proto in range(pickle.HIGHEST_PROTOCOL + 1):
-            with self.subTest(proto=proto):
-                check(pickle.loads(pickle.dumps(od, proto)))
+        # pickle directly pulls the module, so we have to fake it
+        with replaced_module('collections', self.module):
+            for proto in range(pickle.HIGHEST_PROTOCOL + 1):
+                with self.subTest(proto=proto):
+                    check(pickle.loads(pickle.dumps(od, proto)))
         check(eval(repr(od)))
         update_test = OrderedDict()
         update_test.update(od)
@@ -1800,6 +1863,7 @@ class TestOrderedDict(unittest.TestCase):
         check(OrderedDict(od))
 
     def test_yaml_linkage(self):
+        OrderedDict = self.module.OrderedDict
         # Verify that __reduce__ is setup in a way that supports PyYAML's dump() feature.
         # In yaml, lists are native but tuples are not.
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
@@ -1809,6 +1873,7 @@ class TestOrderedDict(unittest.TestCase):
         self.assertTrue(all(type(pair)==list for pair in od.__reduce__()[1]))
 
     def test_reduce_not_too_fat(self):
+        OrderedDict = self.module.OrderedDict
         # do not save instance dictionary if not needed
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         od = OrderedDict(pairs)
@@ -1817,15 +1882,20 @@ class TestOrderedDict(unittest.TestCase):
         self.assertIsNotNone(od.__reduce__()[2])
 
     def test_pickle_recursive(self):
+        OrderedDict = self.module.OrderedDict
         od = OrderedDict()
         od[1] = od
-        for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1):
-            dup = pickle.loads(pickle.dumps(od, proto))
-            self.assertIsNot(dup, od)
-            self.assertEqual(list(dup.keys()), [1])
-            self.assertIs(dup[1], dup)
+
+        # pickle directly pulls the module, so we have to fake it
+        with replaced_module('collections', self.module):
+            for proto in range(-1, pickle.HIGHEST_PROTOCOL + 1):
+                dup = pickle.loads(pickle.dumps(od, proto))
+                self.assertIsNot(dup, od)
+                self.assertEqual(list(dup.keys()), [1])
+                self.assertIs(dup[1], dup)
 
     def test_repr(self):
+        OrderedDict = self.module.OrderedDict
         od = OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])
         self.assertEqual(repr(od),
             "OrderedDict([('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)])")
@@ -1833,6 +1903,7 @@ class TestOrderedDict(unittest.TestCase):
         self.assertEqual(repr(OrderedDict()), "OrderedDict()")
 
     def test_repr_recursive(self):
+        OrderedDict = self.module.OrderedDict
         # See issue #9826
         od = OrderedDict.fromkeys('abc')
         od['x'] = od
@@ -1840,6 +1911,7 @@ class TestOrderedDict(unittest.TestCase):
             "OrderedDict([('a', None), ('b', None), ('c', None), ('x', ...)])")
 
     def test_setdefault(self):
+        OrderedDict = self.module.OrderedDict
         pairs = [('c', 1), ('b', 2), ('a', 3), ('d', 4), ('e', 5), ('f', 6)]
         shuffle(pairs)
         od = OrderedDict(pairs)
@@ -1858,16 +1930,19 @@ class TestOrderedDict(unittest.TestCase):
         self.assertEqual(Missing().setdefault(5, 9), 9)
 
     def test_reinsert(self):
+        OrderedDict = self.module.OrderedDict
         # Given insert a, insert b, delete a, re-insert a,
         # verify that a is now later than b.
         od = OrderedDict()
         od['a'] = 1
         od['b'] = 2
         del od['a']
+        self.assertEqual(list(od.items()), [('b', 2)])
         od['a'] = 1
         self.assertEqual(list(od.items()), [('b', 2), ('a', 1)])
 
     def test_move_to_end(self):
+        OrderedDict = self.module.OrderedDict
         od = OrderedDict.fromkeys('abcde')
         self.assertEqual(list(od), list('abcde'))
         od.move_to_end('c')
@@ -1880,14 +1955,18 @@ class TestOrderedDict(unittest.TestCase):
         self.assertEqual(list(od), list('cabde'))
         with self.assertRaises(KeyError):
             od.move_to_end('x')
+        with self.assertRaises(KeyError):
+            od.move_to_end('x', 0)
 
     def test_sizeof(self):
+        OrderedDict = self.module.OrderedDict
         # Wimpy test: Just verify the reported size is larger than a regular dict
         d = dict(a=1)
         od = OrderedDict(**d)
         self.assertGreater(sys.getsizeof(od), sys.getsizeof(d))
 
     def test_views(self):
+        OrderedDict = self.module.OrderedDict
         # See http://bugs.python.org/issue24286
         s = 'the quick brown fox jumped over a lazy dog yesterday before dawn'.split()
         od = OrderedDict.fromkeys(s)
@@ -1895,6 +1974,7 @@ class TestOrderedDict(unittest.TestCase):
         self.assertEqual(od.items(), dict(od).items())
 
     def test_override_update(self):
+        OrderedDict = self.module.OrderedDict
         # Verify that subclasses can override update() without breaking __init__()
         class MyOD(OrderedDict):
             def update(self, *args, **kwds):
@@ -1902,18 +1982,101 @@ class TestOrderedDict(unittest.TestCase):
         items = [('a', 1), ('c', 3), ('b', 2)]
         self.assertEqual(list(MyOD(items).items()), items)
 
-class GeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
-    type2test = OrderedDict
+
+class PurePythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
+
+    module = py_coll
+
+
+@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
+class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
+
+    module = c_coll
+
+    def test_delitem_hash_collision(self):
+        OrderedDict = self.module.OrderedDict
+
+        class Key:
+            def __init__(self, hash):
+                self._hash = hash
+                self.value = str(id(self))
+            def __hash__(self):
+                return self._hash
+            def __eq__(self, other):
+                try:
+                    return self.value == other.value
+                except AttributeError:
+                    return False
+            def __repr__(self):
+                return self.value
+
+        def blocking_hash(hash):
+            # See the collision-handling in lookdict (in Objects/dictobject.c).
+            MINSIZE = 8
+            i = (hash & MINSIZE-1)
+            return (i << 2) + i + hash + 1
+
+        COLLIDING = 1
+
+        key = Key(COLLIDING)
+        colliding = Key(COLLIDING)
+        blocking = Key(blocking_hash(COLLIDING))
+
+        od = OrderedDict()
+        od[key] = ...
+        od[blocking] = ...
+        od[colliding] = ...
+        od['after'] = ...
+
+        del od[blocking]
+        del od[colliding]
+        self.assertEqual(list(od.items()), [(key, ...), ('after', ...)])
+
+
+class PurePythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
+
+    @classmethod
+    def setUpClass(cls):
+        cls.type2test = py_coll.OrderedDict
 
     def test_popitem(self):
         d = self._empty_mapping()
         self.assertRaises(KeyError, d.popitem)
 
-class MyOrderedDict(OrderedDict):
-    pass
 
-class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
-    type2test = MyOrderedDict
+@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
+class CPythonGeneralMappingTests(mapping_tests.BasicTestMappingProtocol):
+
+    @classmethod
+    def setUpClass(cls):
+        cls.type2test = c_coll.OrderedDict
+
+    def test_popitem(self):
+        d = self._empty_mapping()
+        self.assertRaises(KeyError, d.popitem)
+
+
+class PurePythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
+
+    @classmethod
+    def setUpClass(cls):
+        class MyOrderedDict(py_coll.OrderedDict):
+            pass
+        cls.type2test = MyOrderedDict
+
+    def test_popitem(self):
+        d = self._empty_mapping()
+        self.assertRaises(KeyError, d.popitem)
+
+
+@unittest.skipUnless(c_coll, 'requires the C version of the collections module')
+class CPythonSubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
+
+    @classmethod
+    def setUpClass(cls):
+        class MyOrderedDict(c_coll.OrderedDict):
+            pass
+        cls.type2test = MyOrderedDict
 
     def test_popitem(self):
         d = self._empty_mapping()
@@ -1930,8 +2093,11 @@ def test_main(verbose=None):
     NamedTupleDocs = doctest.DocTestSuite(module=collections)
     test_classes = [TestNamedTuple, NamedTupleDocs, TestOneTrickPonyABCs,
                     TestCollectionABCs, TestCounter, TestChainMap,
-                    TestOrderedDict, GeneralMappingTests, SubclassMappingTests,
-                    TestUserObjects]
+                    PurePythonOrderedDictTests, CPythonOrderedDictTests,
+                    PurePythonGeneralMappingTests, CPythonGeneralMappingTests,
+                    PurePythonSubclassMappingTests, CPythonSubclassMappingTests,
+                    TestUserObjects,
+                    ]
     support.run_unittest(*test_classes)
     support.run_doctest(collections, verbose)