From 3b6a6b4215950bce2a3b4bfc7d1876ab11e5f591 Mon Sep 17 00:00:00 2001 From: Victor Stinner Date: Thu, 8 Sep 2016 12:51:24 -0700 Subject: 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. --- Doc/whatsnew/3.6.rst | 10 +++ Include/dictobject.h | 4 + Lib/test/test_ordered_dict.py | 2 +- Lib/test/test_pep509.py | 186 ++++++++++++++++++++++++++++++++++++++++++ Lib/test/test_sys.py | 6 +- Misc/NEWS | 4 + Modules/_testcapimodule.c | 16 ++++ Objects/dictobject.c | 19 +++++ 8 files changed, 243 insertions(+), 4 deletions(-) create mode 100644 Lib/test/test_pep509.py 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); -- cgit v0.12