(original) (raw)

changeset: 103351:d43f819caea7 user: Victor Stinner victor.stinner@gmail.com date: Thu Sep 08 12:51:24 2016 -0700 files: Doc/whatsnew/3.6.rst Include/dictobject.h Lib/test/test_ordered_dict.py Lib/test/test_pep509.py Lib/test/test_sys.py Misc/NEWS Modules/_testcapimodule.c Objects/dictobject.c description: 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. diff -r 199aca18d9a1 -r d43f819caea7 Doc/whatsnew/3.6.rst --- a/Doc/whatsnew/3.6.rst Thu Sep 08 14:47:23 2016 -0500 +++ b/Doc/whatsnew/3.6.rst Thu Sep 08 12:51:24 2016 -0700 @@ -367,6 +367,16 @@ 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 -r 199aca18d9a1 -r d43f819caea7 Include/dictobject.h --- a/Include/dictobject.h Thu Sep 08 14:47:23 2016 -0500 +++ b/Include/dictobject.h Thu Sep 08 12:51:24 2016 -0700 @@ -26,6 +26,10 @@ /* 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 -r 199aca18d9a1 -r d43f819caea7 Lib/test/test_ordered_dict.py --- a/Lib/test/test_ordered_dict.py Thu Sep 08 14:47:23 2016 -0500 +++ b/Lib/test/test_ordered_dict.py Thu Sep 08 12:51:24 2016 -0700 @@ -655,7 +655,7 @@ 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 -r 199aca18d9a1 -r d43f819caea7 Lib/test/test_pep509.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Lib/test/test_pep509.py Thu Sep 08 12:51:24 2016 -0700 @@ -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 -r 199aca18d9a1 -r d43f819caea7 Lib/test/test_sys.py --- a/Lib/test/test_sys.py Thu Sep 08 14:47:23 2016 -0500 +++ b/Lib/test/test_sys.py Thu Sep 08 12:51:24 2016 -0700 @@ -937,9 +937,9 @@ # 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 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 -r 199aca18d9a1 -r d43f819caea7 Misc/NEWS --- a/Misc/NEWS Thu Sep 08 14:47:23 2016 -0500 +++ b/Misc/NEWS Thu Sep 08 12:51:24 2016 -0700 @@ -10,6 +10,10 @@ 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 -r 199aca18d9a1 -r d43f819caea7 Modules/_testcapimodule.c --- a/Modules/_testcapimodule.c Thu Sep 08 14:47:23 2016 -0500 +++ b/Modules/_testcapimodule.c Thu Sep 08 12:51:24 2016 -0700 @@ -3915,6 +3915,21 @@ 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 @@ {"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 -r 199aca18d9a1 -r d43f819caea7 Objects/dictobject.c --- a/Objects/dictobject.c Thu Sep 08 14:47:23 2016 -0500 +++ b/Objects/dictobject.c Thu Sep 08 12:51:24 2016 -0700 @@ -237,6 +237,13 @@ 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 @@ 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 @@ 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 @@ 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 @@ assert(ix == mp->ma_used); *value_addr = value; mp->ma_used++; + mp->ma_version_tag = DICT_NEXT_VERSION(); return 0; } @@ -1533,6 +1545,7 @@ 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 @@ 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 @@ _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 @@ 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 @@ /* 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 @@ _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); /victor.stinner@gmail.com