Add a new private version to the builtin dict type

Issue #26058: Add a new private version to the builtin dict type, incremented
at each dictionary creation and at each dictionary change.

Implementation of the PEP 509.

8 files changed, 243 insertions, 4 deletions

diff --git a/Doc/whatsnew/3.6.rst b/Doc/whatsnew/3.6.rst
index a76ac9d..14d0579 100644
--- a/Doc/whatsnew/3.6.rst
+++ b/Doc/whatsnew/3.6.rst
@@ -367,6 +367,16 @@ class namespace, ``cls.__dict__``, is unchanged.
       PEP written and implemented by Eric Snow.
 
 
+PEP 509: Add a private version to dict
+--------------------------------------
+
+Add a new private version to the builtin ``dict`` type, incremented at
+each dictionary creation and at each dictionary change, to implement
+fast guards on namespaces.
+
+(Contributed by Victor Stinner in :issue:`26058`.)
+
+
 Other Language Changes
 ======================
 
diff --git a/Include/dictobject.h b/Include/dictobject.h
index 02d40ff..19194ed 100644
--- a/Include/dictobject.h
+++ b/Include/dictobject.h
@@ -26,6 +26,10 @@ typedef struct {
     /* Number of items in the dictionary */
     Py_ssize_t ma_used;
 
+    /* Dictionary version: globally unique, value change each time
+       the dictionary is modified */
+    uint64_t ma_version_tag;
+
     PyDictKeysObject *ma_keys;
 
     /* If ma_values is NULL, the table is "combined": keys and values
diff --git a/Lib/test/test_ordered_dict.py b/Lib/test/test_ordered_dict.py
index 43600e4..d6e72a6 100644
--- a/Lib/test/test_ordered_dict.py
+++ b/Lib/test/test_ordered_dict.py
@@ -655,7 +655,7 @@ class CPythonOrderedDictTests(OrderedDictTests, unittest.TestCase):
         size = support.calcobjsize
         check = self.check_sizeof
 
-        basicsize = size('n2P' + '3PnPn2P') + calcsize('2nP2n')
+        basicsize = size('n2P3PnPn2P') + 8 + calcsize('2nP2n')
         entrysize = calcsize('n2P')
         p = calcsize('P')
         nodesize = calcsize('Pn2P')
diff --git a/Lib/test/test_pep509.py b/Lib/test/test_pep509.py
new file mode 100644
index 0000000..5671f9f
--- /dev/null
+++ b/Lib/test/test_pep509.py
@@ -0,0 +1,186 @@
+"""
+Test implementation of the PEP 509: dictionary versionning.
+"""
+import unittest
+from test import support
+
+# PEP 509 is implemented in CPython but other Python implementations
+# don't require to implement it
+_testcapi = support.import_module('_testcapi')
+
+
+class DictVersionTests(unittest.TestCase):
+    type2test = dict
+
+    def setUp(self):
+        self.seen_versions = set()
+        self.dict = None
+
+    def check_version_unique(self, mydict):
+        version = _testcapi.dict_get_version(mydict)
+        self.assertNotIn(version, self.seen_versions)
+        self.seen_versions.add(version)
+
+    def check_version_changed(self, mydict, method, *args, **kw):
+        result = method(*args, **kw)
+        self.check_version_unique(mydict)
+        return result
+
+    def check_version_dont_change(self, mydict, method, *args, **kw):
+        version1 = _testcapi.dict_get_version(mydict)
+        self.seen_versions.add(version1)
+
+        result = method(*args, **kw)
+
+        version2 = _testcapi.dict_get_version(mydict)
+        self.assertEqual(version2, version1, "version changed")
+
+        return  result
+
+    def new_dict(self, *args, **kw):
+        d = self.type2test(*args, **kw)
+        self.check_version_unique(d)
+        return d
+
+    def test_constructor(self):
+        # new empty dictionaries must all have an unique version
+        empty1 = self.new_dict()
+        empty2 = self.new_dict()
+        empty3 = self.new_dict()
+
+        # non-empty dictionaries must also have an unique version
+        nonempty1 = self.new_dict(x='x')
+        nonempty2 = self.new_dict(x='x', y='y')
+
+    def test_copy(self):
+        d = self.new_dict(a=1, b=2)
+
+        d2 = self.check_version_dont_change(d, d.copy)
+
+        # dict.copy() must create a dictionary with a new unique version
+        self.check_version_unique(d2)
+
+    def test_setitem(self):
+        d = self.new_dict()
+
+        # creating new keys must change the version
+        self.check_version_changed(d, d.__setitem__, 'x', 'x')
+        self.check_version_changed(d, d.__setitem__, 'y', 'y')
+
+        # changing values must change the version
+        self.check_version_changed(d, d.__setitem__, 'x', 1)
+        self.check_version_changed(d, d.__setitem__, 'y', 2)
+
+    def test_setitem_same_value(self):
+        value = object()
+        d = self.new_dict()
+
+        # setting a key must change the version
+        self.check_version_changed(d, d.__setitem__, 'key', value)
+
+        # setting a key to the same value with dict.__setitem__
+        # must change the version
+        self.check_version_changed(d, d.__setitem__, 'key', value)
+
+        # setting a key to the same value with dict.update
+        # must change the version
+        self.check_version_changed(d, d.update, key=value)
+
+        d2 = self.new_dict(key=value)
+        self.check_version_changed(d, d.update, d2)
+
+    def test_setitem_equal(self):
+        class AlwaysEqual:
+            def __eq__(self, other):
+                return True
+
+        value1 = AlwaysEqual()
+        value2 = AlwaysEqual()
+        self.assertTrue(value1 == value2)
+        self.assertFalse(value1 != value2)
+
+        d = self.new_dict()
+        self.check_version_changed(d, d.__setitem__, 'key', value1)
+
+        # setting a key to a value equal to the current value
+        # with dict.__setitem__() must change the version
+        self.check_version_changed(d, d.__setitem__, 'key', value2)
+
+        # setting a key to a value equal to the current value
+        # with dict.update() must change the version
+        self.check_version_changed(d, d.update, key=value1)
+
+        d2 = self.new_dict(key=value2)
+        self.check_version_changed(d, d.update, d2)
+
+    def test_setdefault(self):
+        d = self.new_dict()
+
+        # setting a key with dict.setdefault() must change the version
+        self.check_version_changed(d, d.setdefault, 'key', 'value1')
+
+        # don't change the version if the key already exists
+        self.check_version_dont_change(d, d.setdefault, 'key', 'value2')
+
+    def test_delitem(self):
+        d = self.new_dict(key='value')
+
+        # deleting a key with dict.__delitem__() must change the version
+        self.check_version_changed(d, d.__delitem__, 'key')
+
+        # don't change the version if the key doesn't exist
+        self.check_version_dont_change(d, self.assertRaises, KeyError,
+                                       d.__delitem__, 'key')
+
+    def test_pop(self):
+        d = self.new_dict(key='value')
+
+        # pop() must change the version if the key exists
+        self.check_version_changed(d, d.pop, 'key')
+
+        # pop() must not change the version if the key does not exist
+        self.check_version_dont_change(d, self.assertRaises, KeyError,
+                                       d.pop, 'key')
+
+    def test_popitem(self):
+        d = self.new_dict(key='value')
+
+        # popitem() must change the version if the dict is not empty
+        self.check_version_changed(d, d.popitem)
+
+        # popitem() must not change the version if the dict is empty
+        self.check_version_dont_change(d, self.assertRaises, KeyError,
+                                       d.popitem)
+
+    def test_update(self):
+        d = self.new_dict(key='value')
+
+        # update() calling with no argument must not change the version
+        self.check_version_dont_change(d, d.update)
+
+        # update() must change the version
+        self.check_version_changed(d, d.update, key='new value')
+
+        d2 = self.new_dict(key='value 3')
+        self.check_version_changed(d, d.update, d2)
+
+    def test_clear(self):
+        d = self.new_dict(key='value')
+
+        # clear() must change the version if the dict is not empty
+        self.check_version_changed(d, d.clear)
+
+        # clear() must not change the version if the dict is empty
+        self.check_version_dont_change(d, d.clear)
+
+
+class Dict(dict):
+    pass
+
+
+class DictSubtypeVersionTests(DictVersionTests):
+    type2test = Dict
+
+
+if __name__ == "__main__":
+    unittest.main()
diff --git a/Lib/test/test_sys.py b/Lib/test/test_sys.py
index 6084d2d..aa89506 100644
--- a/Lib/test/test_sys.py
+++ b/Lib/test/test_sys.py
@@ -937,9 +937,9 @@ class SizeofTest(unittest.TestCase):
         # method-wrapper (descriptor object)
         check({}.__iter__, size('2P'))
         # dict
-        check({}, size('n2P') + calcsize('2nP2n') + 8 + (8*2//3)*calcsize('n2P'))
+        check({}, size('n2P') + 8 + calcsize('2nP2n') + 8 + (8*2//3)*calcsize('n2P'))
         longdict = {1:1, 2:2, 3:3, 4:4, 5:5, 6:6, 7:7, 8:8}
-        check(longdict, size('n2P') + calcsize('2nP2n') + 16 + (16*2//3)*calcsize('n2P'))
+        check(longdict, size('n2P') + 8 + calcsize('2nP2n') + 16 + (16*2//3)*calcsize('n2P'))
         # dictionary-keyview
         check({}.keys(), size('P'))
         # dictionary-valueview
@@ -1103,7 +1103,7 @@ class SizeofTest(unittest.TestCase):
         class newstyleclass(object): pass
         check(newstyleclass, s)
         # dict with shared keys
-        check(newstyleclass().__dict__, size('n2P' + '2nP2n'))
+        check(newstyleclass().__dict__, size('n2P' + '2nP2n') + 8)
         # unicode
         # each tuple contains a string and its expected character size
         # don't put any static strings here, as they may contain
diff --git a/Misc/NEWS b/Misc/NEWS
index 773de57..36db395 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -10,6 +10,10 @@ What's New in Python 3.6.0 beta 1
 Core and Builtins
 -----------------
 
+- Issue #26058: Add a new private version to the builtin dict type, incremented
+  at each dictionary creation and at each dictionary change. Implementation of
+  the PEP 509.
+
 - Issue #27364: A backslash-character pair that is not a valid escape sequence
   now generates a DeprecationWarning.
 
diff --git a/Modules/_testcapimodule.c b/Modules/_testcapimodule.c
index 7d7fa40..b5b8f1a 100644
--- a/Modules/_testcapimodule.c
+++ b/Modules/_testcapimodule.c
@@ -3915,6 +3915,21 @@ tracemalloc_get_traceback(PyObject *self, PyObject *args)
     return _PyTraceMalloc_GetTraceback(domain, (uintptr_t)ptr);
 }
 
+static PyObject *
+dict_get_version(PyObject *self, PyObject *args)
+{
+    PyDictObject *dict;
+    uint64_t version;
+
+    if (!PyArg_ParseTuple(args, "O!", &PyDict_Type, &dict))
+        return NULL;
+
+    version = dict->ma_version_tag;
+
+    Py_BUILD_ASSERT(sizeof(unsigned PY_LONG_LONG) >= sizeof(version));
+    return PyLong_FromUnsignedLongLong((unsigned PY_LONG_LONG)version);
+}
+
 
 static PyMethodDef TestMethods[] = {
     {"raise_exception",         raise_exception,                 METH_VARARGS},
@@ -4114,6 +4129,7 @@ static PyMethodDef TestMethods[] = {
     {"tracemalloc_track", tracemalloc_track, METH_VARARGS},
     {"tracemalloc_untrack", tracemalloc_untrack, METH_VARARGS},
     {"tracemalloc_get_traceback", tracemalloc_get_traceback, METH_VARARGS},
+    {"dict_get_version", dict_get_version, METH_VARARGS},
     {NULL, NULL} /* sentinel */
 };
 
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 3d5d4bd..d6f1835 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -237,6 +237,13 @@ static Py_ssize_t lookdict_split(PyDictObject *mp, PyObject *key,
 
 static int dictresize(PyDictObject *mp, Py_ssize_t minused);
 
+/* Global counter used to set ma_version_tag field of dictionary.
+ * It is incremented each time that a dictionary is created and each
+ * time that a dictionary is modified. */
+static uint64_t pydict_global_version = 0;
+
+#define DICT_NEXT_VERSION() (++pydict_global_version)
+
 /* Dictionary reuse scheme to save calls to malloc and free */
 #ifndef PyDict_MAXFREELIST
 #define PyDict_MAXFREELIST 80
@@ -511,6 +518,7 @@ new_dict(PyDictKeysObject *keys, PyObject **values)
     mp->ma_keys = keys;
     mp->ma_values = values;
     mp->ma_used = 0;
+    mp->ma_version_tag = DICT_NEXT_VERSION();
     return (PyObject *)mp;
 }
 
@@ -1074,6 +1082,7 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
             ep->me_value = value;
         }
         mp->ma_used++;
+        mp->ma_version_tag = DICT_NEXT_VERSION();
         mp->ma_keys->dk_usable--;
         mp->ma_keys->dk_nentries++;
         assert(mp->ma_keys->dk_usable >= 0);
@@ -1085,6 +1094,8 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
     old_value = *value_addr;
     if (old_value != NULL) {
         *value_addr = value;
+        mp->ma_version_tag = DICT_NEXT_VERSION();
+
         Py_DECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
         return 0;
     }
@@ -1094,6 +1105,7 @@ insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
     assert(ix == mp->ma_used);
     *value_addr = value;
     mp->ma_used++;
+    mp->ma_version_tag = DICT_NEXT_VERSION();
     return 0;
 }
 
@@ -1533,6 +1545,7 @@ _PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
     old_value = *value_addr;
     *value_addr = NULL;
     mp->ma_used--;
+    mp->ma_version_tag = DICT_NEXT_VERSION();
     if (_PyDict_HasSplitTable(mp)) {
         mp->ma_keys->dk_usable = 0;
     }
@@ -1568,6 +1581,7 @@ PyDict_Clear(PyObject *op)
     mp->ma_keys = Py_EMPTY_KEYS;
     mp->ma_values = empty_values;
     mp->ma_used = 0;
+    mp->ma_version_tag = DICT_NEXT_VERSION();
     /* ...then clear the keys and values */
     if (oldvalues != NULL) {
         n = oldkeys->dk_nentries;
@@ -1706,9 +1720,11 @@ _PyDict_Pop(PyDictObject *mp, PyObject *key, PyObject *deflt)
         _PyErr_SetKeyError(key);
         return NULL;
     }
+
     old_value = *value_addr;
     *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];
@@ -2659,6 +2675,7 @@ PyDict_SetDefault(PyObject *d, PyObject *key, PyObject *defaultobj)
         mp->ma_keys->dk_usable--;
         mp->ma_keys->dk_nentries++;
         mp->ma_used++;
+        mp->ma_version_tag = DICT_NEXT_VERSION();
     }
     else
         val = *value_addr;
@@ -2752,6 +2769,7 @@ dict_popitem(PyDictObject *mp)
     /* We can't dk_usable++ since there is DKIX_DUMMY in indices */
     mp->ma_keys->dk_nentries = i;
     mp->ma_used--;
+    mp->ma_version_tag = DICT_NEXT_VERSION();
     return res;
 }
 
@@ -2970,6 +2988,7 @@ dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
         _PyObject_GC_UNTRACK(d);
 
     d->ma_used = 0;
+    d->ma_version_tag = DICT_NEXT_VERSION();
     d->ma_keys = new_keys_object(PyDict_MINSIZE);
     if (d->ma_keys == NULL) {
         Py_DECREF(self);