[Python-checkins] cpython: Fix SystemError in compact dict

[victor.stinner]

https://hg.python.org/cpython/rev/4a5b61b0d090
changeset:   103540:4a5b61b0d090
user:        Victor Stinner <victor.stinner at gmail.com>
date:        Fri Sep 09 19:28:36 2016 -0700
summary:
  Fix SystemError in compact dict

Issue #28040: Fix _PyDict_DelItem_KnownHash() and _PyDict_Pop(): convert
splitted table to combined table to be able to delete the item.

Write an unit test for the issue.

Patch by INADA Naoki.

files:
  Lib/test/test_dict.py |  69 +++++++++++++++++++++++++++++++
  Objects/dictobject.c  |  52 ++++++++++++++--------
  2 files changed, 102 insertions(+), 19 deletions(-)


diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py
--- a/Lib/test/test_dict.py
+++ b/Lib/test/test_dict.py
@@ -4,6 +4,7 @@
 import pickle
 import random
 import string
+import sys
 import unittest
 import weakref
 from test import support
@@ -838,6 +839,74 @@
             pass
         self._tracked(MyDict())
 
+    def make_shared_key_dict(self, n):
+        class C:
+            pass
+
+        dicts = []
+        for i in range(n):
+            a = C()
+            a.x, a.y, a.z = 1, 2, 3
+            dicts.append(a.__dict__)
+
+        return dicts
+
+    @support.cpython_only
+    def test_splittable_del(self):
+        """split table must be combined when del d[k]"""
+        a, b = self.make_shared_key_dict(2)
+
+        orig_size = sys.getsizeof(a)
+
+        del a['y']  # split table is combined
+        with self.assertRaises(KeyError):
+            del a['y']
+
+        self.assertGreater(sys.getsizeof(a), orig_size)
+        self.assertEqual(list(a), ['x', 'z'])
+        self.assertEqual(list(b), ['x', 'y', 'z'])
+
+        # Two dicts have different insertion order.
+        a['y'] = 42
+        self.assertEqual(list(a), ['x', 'z', 'y'])
+        self.assertEqual(list(b), ['x', 'y', 'z'])
+
+    @support.cpython_only
+    def test_splittable_pop(self):
+        """split table must be combined when d.pop(k)"""
+        a, b = self.make_shared_key_dict(2)
+
+        orig_size = sys.getsizeof(a)
+
+        a.pop('y')  # split table is combined
+        with self.assertRaises(KeyError):
+            a.pop('y')
+
+        self.assertGreater(sys.getsizeof(a), orig_size)
+        self.assertEqual(list(a), ['x', 'z'])
+        self.assertEqual(list(b), ['x', 'y', 'z'])
+
+        # Two dicts have different insertion order.
+        a['y'] = 42
+        self.assertEqual(list(a), ['x', 'z', 'y'])
+        self.assertEqual(list(b), ['x', 'y', 'z'])
+
+    @support.cpython_only
+    def test_splittable_popitem(self):
+        """split table must be combined when d.popitem()"""
+        a, b = self.make_shared_key_dict(2)
+
+        orig_size = sys.getsizeof(a)
+
+        item = a.popitem()  # split table is combined
+        self.assertEqual(item, ('z', 3))
+        with self.assertRaises(KeyError):
+            del a['z']
+
+        self.assertGreater(sys.getsizeof(a), orig_size)
+        self.assertEqual(list(a), ['x', 'y'])
+        self.assertEqual(list(b), ['x', 'y', 'z'])
+
     def test_iterator_pickling(self):
         for proto in range(pickle.HIGHEST_PROTOCOL + 1):
             data = {1:"a", 2:"b", 3:"c"}
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1546,21 +1546,27 @@
         return -1;
     }
     assert(dk_get_index(mp->ma_keys, hashpos) == ix);
+
+    // Split table doesn't allow deletion.  Combine it.
+    if (_PyDict_HasSplitTable(mp)) {
+        if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
+            return -1;
+        }
+        ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos);
+        assert(ix >= 0);
+    }
+
     old_value = *value_addr;
+    assert(old_value != NULL);
     *value_addr = NULL;
     mp->ma_used--;
     mp->ma_version_tag = DICT_NEXT_VERSION();
-    if (_PyDict_HasSplitTable(mp)) {
-        mp->ma_keys->dk_usable = 0;
-    }
-    else {
-        ep = &DK_ENTRIES(mp->ma_keys)[ix];
-        dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
-        ENSURE_ALLOWS_DELETIONS(mp);
-        old_key = ep->me_key;
-        ep->me_key = NULL;
-        Py_DECREF(old_key);
-    }
+    ep = &DK_ENTRIES(mp->ma_keys)[ix];
+    dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
+    ENSURE_ALLOWS_DELETIONS(mp);
+    old_key = ep->me_key;
+    ep->me_key = NULL;
+    Py_DECREF(old_key);
     Py_DECREF(old_value);
     return 0;
 }
@@ -1725,18 +1731,26 @@
         return NULL;
     }
 
+    // Split table doesn't allow deletion.  Combine it.
+    if (_PyDict_HasSplitTable(mp)) {
+        if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
+            return NULL;
+        }
+        ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &value_addr, &hashpos);
+        assert(ix >= 0);
+    }
+
     old_value = *value_addr;
+    assert(old_value != NULL);
     *value_addr = NULL;
     mp->ma_used--;
     mp->ma_version_tag = DICT_NEXT_VERSION();
-    if (!_PyDict_HasSplitTable(mp)) {
-        dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
-        ep = &DK_ENTRIES(mp->ma_keys)[ix];
-        ENSURE_ALLOWS_DELETIONS(mp);
-        old_key = ep->me_key;
-        ep->me_key = NULL;
-        Py_DECREF(old_key);
-    }
+    dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
+    ep = &DK_ENTRIES(mp->ma_keys)[ix];
+    ENSURE_ALLOWS_DELETIONS(mp);
+    old_key = ep->me_key;
+    ep->me_key = NULL;
+    Py_DECREF(old_key);
     return old_value;
 }
 

-- 
Repository URL: https://hg.python.org/cpython