From 78601a38c22ba1f09104e2562a10a94cbd36f5f0 Mon Sep 17 00:00:00 2001
From: Victor Stinner <victor.stinner@gmail.com>
Date: Fri, 9 Sep 2016 19:28:36 -0700
Subject: 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.
---
 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
index 6c47066..fb954c8 100644
--- a/Lib/test/test_dict.py
+++ b/Lib/test/test_dict.py
@@ -4,6 +4,7 @@ import gc
 import pickle
 import random
 import string
+import sys
 import unittest
 import weakref
 from test import support
@@ -838,6 +839,74 @@ class DictTest(unittest.TestCase):
             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
index 461eb57..8a13fb4 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -1546,21 +1546,27 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
         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 @@ _PyDict_Pop(PyDictObject *mp, PyObject *key, PyObject *deflt)
         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;
 }
 
-- 
cgit v0.12