>> * frozendict values must be immutable, as dict keys
>
> Why? That may be useful, but an immutable dict whose values
> might mutate is also useful; by forcing that choice, it starts
> to feel too specialized for a builtin.
Hum, I realized that calling hash(my_frozendict) on a frozendict
instance is enough to check if a frozendict only contains immutable
objects. And it is also possible to check manually that values are
immutable *before* creating the frozendict.
I also prefer to not check for immutability because it does simplify
the code :-)
$ diffstat frozendict-3.patch
Include/dictobject.h | 9 +
Lib/collections/abc.py | 1
Lib/test/test_dict.py | 59 +++++++++++
Objects/dictobject.c | 256 ++++++++++++++++++++++++++++++++++++++++++-------
Objects/object.c | 3
Python/bltinmodule.c | 1
6 files changed, 295 insertions(+), 34 deletions(-)
The patch is quite small to add a new builtin type. That's because
most of the code is shared with the builtin dict type. (But the patch
doesn't include the documentation, it didn't write it yet.)
Victor
diff --git a/Include/dictobject.h b/Include/dictobject.h
--- a/Include/dictobject.h
+++ b/Include/dictobject.h
@@ -84,10 +84,14 @@ struct _dictobject {
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, Py_hash_t hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
+
+ /* only used by frozendict */
+ Py_hash_t hash;
};
#endif /* Py_LIMITED_API */
PyAPI_DATA(PyTypeObject) PyDict_Type;
+PyAPI_DATA(PyTypeObject) PyFrozenDict_Type;
PyAPI_DATA(PyTypeObject) PyDictIterKey_Type;
PyAPI_DATA(PyTypeObject) PyDictIterValue_Type;
PyAPI_DATA(PyTypeObject) PyDictIterItem_Type;
@@ -97,7 +101,12 @@ PyAPI_DATA(PyTypeObject) PyDictValues_Ty
#define PyDict_Check(op) \
PyType_FastSubclass(Py_TYPE(op), Py_TPFLAGS_DICT_SUBCLASS)
+#define PyFrozenDict_Check(op) \
+ (PyDict_Check(op) || \
+ Py_TYPE(op) == &PyFrozenDict_Type || \
+ PyType_IsSubtype(Py_TYPE(op), &PyFrozenDict_Type))
#define PyDict_CheckExact(op) (Py_TYPE(op) == &PyDict_Type)
+#define PyFrozenDict_CheckExact(op) (Py_TYPE(op) == &PyFrozenDict_Type)
#define PyDictKeys_Check(op) (Py_TYPE(op) == &PyDictKeys_Type)
#define PyDictItems_Check(op) (Py_TYPE(op) == &PyDictItems_Type)
#define PyDictValues_Check(op) (Py_TYPE(op) == &PyDictValues_Type)
diff --git a/Lib/collections/abc.py b/Lib/collections/abc.py
--- a/Lib/collections/abc.py
+++ b/Lib/collections/abc.py
@@ -401,6 +401,7 @@ class Mapping(Sized, Iterable, Container
def __ne__(self, other):
return not (self == other)
+Mapping.register(frozendict)
class MappingView(Sized):
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
@@ -788,11 +788,70 @@ class Dict(dict):
class SubclassMappingTests(mapping_tests.BasicTestMappingProtocol):
type2test = Dict
+
+class FrozenDictTests(unittest.TestCase):
+ def test_constructor(self):
+ # unorderable keys and values
+ frozendict(x=b'abc', y='abc')
+ frozendict({b'abc': 1, 'abc': 2})
+
+ # hashable keys and values
+ class Hashable:
+ pass
+ for hashable in (5, 1.0, "abc", (1, 2), Hashable()):
+ frozendict(key=hashable)
+ frozendict(hashable=0)
+
+ # not hashable keys or values
+ class NotHashable:
+ def __hash__(self):
+ raise TypeError("not hashable")
+ for not_hashable in ([], {}, NotHashable()):
+ frozendict(key=not_hashable)
+ frozendict(not_hashable=0)
+
+ def test_copy(self):
+ self.assertIsInstance(frozendict().copy(),
+ frozendict)
+ self.assertEqual(frozendict(x=1, y=2).copy(),
+ frozendict(x=1, y=2))
+
+ def test_dir(self):
+ self.assertEqual(
+ set(dir(frozendict)) - set(dir(object)),
+ {'__contains__', '__getitem__', '__iter__', '__len__',
+ 'copy', 'fromkeys', 'get', 'items', 'keys', 'values'})
+
+ def test_fromkeys(self):
+ self.assertEqual(frozendict.fromkeys('ai'),
+ frozendict(a=None, i=None))
+
+ def test_hash(self):
+ self.assertEqual(hash(frozendict()),
+ hash(frozenset()))
+ self.assertEqual(hash(frozendict({1: 2})),
+ hash(frozenset({(1, 2)})))
+
+ a = frozendict.fromkeys('ai')
+ b = frozendict.fromkeys('ia')
+ self.assertEqual(hash(a), hash(b))
+ self.assertNotEqual(tuple(a.items()), tuple(b.items()))
+
+ # not hashable
+ f = frozendict(x=[])
+ self.assertRaises(TypeError, hash, f)
+
+ def test_repr(self):
+ self.assertEqual(repr(frozendict()), "frozendict({})")
+ self.assertEqual(repr(frozendict(x=1)), "frozendict({'x': 1})")
+
+
def test_main():
support.run_unittest(
DictTest,
GeneralMappingTests,
SubclassMappingTests,
+ FrozenDictTests,
)
if __name__ == "__main__":
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -25,6 +25,8 @@ set_key_error(PyObject *arg)
Py_DECREF(tup);
}
+static PyObject *frozendict_new(void);
+
/* Define this out if you don't want conversion statistics on exit. */
#undef SHOW_CONVERSION_COUNTS
@@ -461,7 +463,7 @@ _PyDict_HasOnlyStringKeys(PyObject *dict
{
Py_ssize_t pos = 0;
PyObject *key, *value;
- assert(PyDict_Check(dict));
+ assert(PyFrozenDict_Check(dict));
/* Shortcut */
if (((PyDictObject *)dict)->ma_lookup == lookdict_unicode)
return 1;
@@ -725,7 +727,7 @@ PyDict_GetItem(PyObject *op, PyObject *k
PyDictObject *mp = (PyDictObject *)op;
PyDictEntry *ep;
PyThreadState *tstate;
- if (!PyDict_Check(op))
+ if (!PyFrozenDict_Check(op))
return NULL;
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1)
@@ -775,7 +777,7 @@ PyDict_GetItemWithError(PyObject *op, Py
PyDictObject*mp = (PyDictObject *)op;
PyDictEntry *ep;
- if (!PyDict_Check(op)) {
+ if (!PyFrozenDict_Check(op)) {
PyErr_BadInternalCall();
return NULL;
}
@@ -840,6 +842,27 @@ dict_set_item_by_hash_or_entry(register
* remove them.
*/
int
+basedict_setitem(PyObject *op, PyObject *key, PyObject *value)
+{
+ register Py_hash_t hash;
+
+ assert(PyFrozenDict_Check(op));
+ assert(key);
+ assert(value);
+ if (PyUnicode_CheckExact(key)) {
+ hash = ((PyASCIIObject *) key)->hash;
+ if (hash == -1)
+ hash = PyObject_Hash(key);
+ }
+ else {
+ hash = PyObject_Hash(key);
+ if (hash == -1)
+ return -1;
+ }
+ return dict_set_item_by_hash_or_entry(op, key, hash, NULL, value);
+}
+
+int
PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
{
register Py_hash_t hash;
@@ -913,9 +936,10 @@ PyDict_Clear(PyObject *op)
Py_ssize_t i, n;
#endif
- if (!PyDict_Check(op))
+ if (!PyFrozenDict_Check(op))
return;
mp = (PyDictObject *)op;
+
#ifdef Py_DEBUG
n = mp->ma_mask + 1;
i = 0;
@@ -992,7 +1016,7 @@ PyDict_Next(PyObject *op, Py_ssize_t *pp
register Py_ssize_t mask;
register PyDictEntry *ep;
- if (!PyDict_Check(op))
+ if (!PyFrozenDict_Check(op))
return 0;
i = *ppos;
if (i < 0)
@@ -1019,7 +1043,7 @@ _PyDict_Next(PyObject *op, Py_ssize_t *p
register Py_ssize_t mask;
register PyDictEntry *ep;
- if (!PyDict_Check(op))
+ if (!PyFrozenDict_Check(op))
return 0;
i = *ppos;
if (i < 0)
@@ -1143,6 +1167,18 @@ Done:
return result;
}
+static PyObject *
+frozendict_repr(PyDictObject *mp)
+{
+ PyObject *repr, *result;
+ repr = dict_repr(mp);
+ if (repr == NULL)
+ return NULL;
+ result = PyUnicode_FromFormat("frozendict(%S)", repr);
+ Py_DECREF(repr);
+ return result;
+}
+
static Py_ssize_t
dict_length(PyDictObject *mp)
{
@@ -1198,6 +1234,11 @@ dict_ass_sub(PyDictObject *mp, PyObject
return PyDict_SetItem((PyObject *)mp, v, w);
}
+static PyMappingMethods frozendict_as_mapping = {
+ (lenfunc)dict_length, /*mp_length*/
+ (binaryfunc)dict_subscript, /*mp_subscript*/
+};
+
static PyMappingMethods dict_as_mapping = {
(lenfunc)dict_length, /*mp_length*/
(binaryfunc)dict_subscript, /*mp_subscript*/
@@ -1391,9 +1432,9 @@ dict_fromkeys(PyObject *cls, PyObject *a
return NULL;
}
- if (PyDict_CheckExact(d)) {
+ if (PyFrozenDict_CheckExact(d) || PyDict_CheckExact(d)) {
while ((key = PyIter_Next(it)) != NULL) {
- status = PyDict_SetItem(d, key, value);
+ status = basedict_setitem(d, key, value);
Py_DECREF(key);
if (status < 0)
goto Fail;
@@ -1470,7 +1511,7 @@ PyDict_MergeFromSeq2(PyObject *d, PyObje
PyObject *fast; /* item as a 2-tuple or 2-list */
assert(d != NULL);
- assert(PyDict_Check(d));
+ assert(PyFrozenDict_Check(d));
assert(seq2 != NULL);
it = PyObject_GetIter(seq2);
@@ -1512,7 +1553,7 @@ PyDict_MergeFromSeq2(PyObject *d, PyObje
key = PySequence_Fast_GET_ITEM(fast, 0);
value = PySequence_Fast_GET_ITEM(fast, 1);
if (override || PyDict_GetItem(d, key) == NULL) {
- int status = PyDict_SetItem(d, key, value);
+ int status = basedict_setitem(d, key, value);
if (status < 0)
goto Fail;
}
@@ -1549,12 +1590,13 @@ PyDict_Merge(PyObject *a, PyObject *b, i
* things quite efficiently. For the latter, we only require that
* PyMapping_Keys() and PyObject_GetItem() be supported.
*/
- if (a == NULL || !PyDict_Check(a) || b == NULL) {
+ if (a == NULL || !PyFrozenDict_Check(a) || b == NULL) {
PyErr_BadInternalCall();
return -1;
}
mp = (PyDictObject*)a;
- if (PyDict_Check(b)) {
+
+ if (PyFrozenDict_Check(b)) {
other = (PyDictObject*)b;
if (other == mp || other->ma_used == 0)
/* a.update(a) or a.update({}); nothing to do */
@@ -1575,16 +1617,16 @@ PyDict_Merge(PyObject *a, PyObject *b, i
}
for (i = 0; i <= other->ma_mask; i++) {
entry = &other->ma_table[i];
- if (entry->me_value != NULL &&
- (override ||
- PyDict_GetItem(a, entry->me_key) == NULL)) {
- Py_INCREF(entry->me_key);
- Py_INCREF(entry->me_value);
- if (insertdict(mp, entry->me_key,
- entry->me_hash,
- entry->me_value) != 0)
- return -1;
- }
+ if (entry->me_value == NULL)
+ continue;
+ if (!override && PyDict_GetItem(a, entry->me_key) != NULL)
+ continue;
+ Py_INCREF(entry->me_key);
+ Py_INCREF(entry->me_value);
+ if (insertdict(mp, entry->me_key,
+ entry->me_hash,
+ entry->me_value) != 0)
+ return -1;
}
}
else {
@@ -1618,7 +1660,7 @@ PyDict_Merge(PyObject *a, PyObject *b, i
Py_DECREF(key);
return -1;
}
- status = PyDict_SetItem(a, key, value);
+ status = basedict_setitem(a, key, value);
Py_DECREF(key);
Py_DECREF(value);
if (status < 0) {
@@ -1658,10 +1700,27 @@ PyDict_Copy(PyObject *o)
return NULL;
}
+static PyObject *
+frozendict_copy(PyObject *o)
+{
+ PyObject *copy;
+ if (o == NULL || !PyFrozenDict_Check(o)) {
+ PyErr_BadInternalCall();
+ return NULL;
+ }
+ copy = frozendict_new();
+ if (copy == NULL)
+ return NULL;
+ if (PyDict_Merge(copy, o, 1) == 0)
+ return copy;
+ Py_DECREF(copy);
+ return NULL;
+}
+
Py_ssize_t
PyDict_Size(PyObject *mp)
{
- if (mp == NULL || !PyDict_Check(mp)) {
+ if (mp == NULL || !PyFrozenDict_Check(mp)) {
PyErr_BadInternalCall();
return -1;
}
@@ -1671,7 +1730,7 @@ PyDict_Size(PyObject *mp)
PyObject *
PyDict_Keys(PyObject *mp)
{
- if (mp == NULL || !PyDict_Check(mp)) {
+ if (mp == NULL || !PyFrozenDict_Check(mp)) {
PyErr_BadInternalCall();
return NULL;
}
@@ -1681,7 +1740,7 @@ PyDict_Keys(PyObject *mp)
PyObject *
PyDict_Values(PyObject *mp)
{
- if (mp == NULL || !PyDict_Check(mp)) {
+ if (mp == NULL || !PyFrozenDict_Check(mp)) {
PyErr_BadInternalCall();
return NULL;
}
@@ -1691,7 +1750,7 @@ PyDict_Values(PyObject *mp)
PyObject *
PyDict_Items(PyObject *mp)
{
- if (mp == NULL || !PyDict_Check(mp)) {
+ if (mp == NULL || !PyFrozenDict_Check(mp)) {
PyErr_BadInternalCall();
return NULL;
}
@@ -1746,7 +1805,7 @@ dict_richcompare(PyObject *v, PyObject *
int cmp;
PyObject *res;
- if (!PyDict_Check(v) || !PyDict_Check(w)) {
+ if (!PyFrozenDict_Check(v) || !PyFrozenDict_Check(w)) {
res = Py_NotImplemented;
}
else if (op == Py_EQ || op == Py_NE) {
@@ -2034,7 +2093,29 @@ PyDoc_STRVAR(items__doc__,
PyDoc_STRVAR(values__doc__,
"D.values() -> an object providing a view on D's values");
-static PyMethodDef mapp_methods[] = {
+static PyMethodDef frozendict_methods[] = {
+ {"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
+ contains__doc__},
+ {"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
+ getitem__doc__},
+ {"__sizeof__", (PyCFunction)dict_sizeof, METH_NOARGS,
+ sizeof__doc__},
+ {"get", (PyCFunction)dict_get, METH_VARARGS,
+ get__doc__},
+ {"keys", (PyCFunction)dictkeys_new, METH_NOARGS,
+ keys__doc__},
+ {"items", (PyCFunction)dictitems_new, METH_NOARGS,
+ items__doc__},
+ {"values", (PyCFunction)dictvalues_new, METH_NOARGS,
+ values__doc__},
+ {"fromkeys", (PyCFunction)dict_fromkeys, METH_VARARGS | METH_CLASS,
+ fromkeys__doc__},
+ {"copy", (PyCFunction)frozendict_copy, METH_NOARGS,
+ copy__doc__},
+ {NULL, NULL} /* sentinel */
+};
+
+static PyMethodDef dict_methods[] = {
{"__contains__",(PyCFunction)dict_contains, METH_O | METH_COEXIST,
contains__doc__},
{"__getitem__", (PyCFunction)dict_subscript, METH_O | METH_COEXIST,
@@ -2138,6 +2219,33 @@ dict_new(PyTypeObject *type, PyObject *a
return self;
}
+static PyObject *
+frozendict_new(void)
+{
+ PyObject *self;
+ PyDictObject *d;
+
+ self = dict_new(&PyFrozenDict_Type, NULL, NULL);
+ if (self == NULL)
+ return NULL;
+ d = (PyDictObject *)self;
+ d->hash = -1;
+ return self;
+}
+
+static PyObject *
+frozendict___new__(PyTypeObject *type, PyObject *args, PyObject *kwds)
+{
+ PyObject *self = frozendict_new();
+ if (self == NULL)
+ return NULL;
+ if (dict_update_common(self, args, kwds, "frozendict") == -1) {
+ Py_DECREF(self);
+ return NULL;
+ }
+ return self;
+}
+
static int
dict_init(PyObject *self, PyObject *args, PyObject *kwds)
{
@@ -2150,6 +2258,86 @@ dict_iter(PyDictObject *dict)
return dictiter_new(dict, &PyDictIterKey_Type);
}
+static Py_hash_t
+frozendict_hash(PyObject *self)
+{
+ PyDictObject *frozendict = (PyDictObject *)self;
+ PyObject *items, *frozen_items;
+ Py_hash_t hash;
+
+ if (frozendict->hash != -1)
+ return frozendict->hash;
+
+ items = PyObject_CallMethod(self, "items", "");
+ if (items == NULL)
+ return -1;
+ frozen_items = PyFrozenSet_New(items);
+ Py_DECREF(items);
+ if (frozen_items == NULL)
+ return -1;
+ hash = PyObject_Hash(frozen_items);
+ Py_DECREF(frozen_items);
+ if (hash == -1)
+ return -1;
+
+ frozendict->hash = hash;
+ return hash;
+}
+
+PyDoc_STRVAR(frozendict_doc,
+"frozendict() -> new empty frozen dictionary\n"
+"frozendict(mapping) -> new frozen dictionary initialized from a mapping object's\n"
+" (key, value) pairs\n"
+"frozendict(iterable) -> new frozen dictionary initialized as if via:\n"
+" d = {}\n"
+" for k, v in iterable:\n"
+" d[k] = v\n"
+"frozendict(**kwargs) -> new frozen dictionary initialized with the name=value\n"
+" pairs in the keyword argument list. For example: frozendict(one=1, two=2)");
+
+PyTypeObject PyFrozenDict_Type = {
+ PyVarObject_HEAD_INIT(&PyType_Type, 0)
+ "frozendict",
+ sizeof(PyDictObject),
+ 0,
+ (destructor)dict_dealloc, /* tp_dealloc */
+ 0, /* tp_print */
+ 0, /* tp_getattr */
+ 0, /* tp_setattr */
+ 0, /* tp_reserved */
+ (reprfunc)frozendict_repr, /* tp_repr */
+ 0, /* tp_as_number */
+ &dict_as_sequence, /* tp_as_sequence */
+ &frozendict_as_mapping, /* tp_as_mapping */
+ frozendict_hash, /* tp_hash */
+ 0, /* tp_call */
+ 0, /* tp_str */
+ PyObject_GenericGetAttr, /* tp_getattro */
+ 0, /* tp_setattro */
+ 0, /* tp_as_buffer */
+ Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
+ Py_TPFLAGS_BASETYPE, /* tp_flags */
+ frozendict_doc, /* tp_doc */
+ dict_traverse, /* tp_traverse */
+ dict_tp_clear, /* tp_clear */
+ dict_richcompare, /* tp_richcompare */
+ 0, /* tp_weaklistoffset */
+ (getiterfunc)dict_iter, /* tp_iter */
+ 0, /* tp_iternext */
+ frozendict_methods, /* tp_methods */
+ 0, /* tp_members */
+ 0, /* tp_getset */
+ 0, /* tp_base */
+ 0, /* tp_dict */
+ 0, /* tp_descr_get */
+ 0, /* tp_descr_set */
+ 0, /* tp_dictoffset */
+ 0, /* tp_init */
+ PyType_GenericAlloc, /* tp_alloc */
+ frozendict___new__, /* tp_new */
+ PyObject_GC_Del, /* tp_free */
+};
+
PyDoc_STRVAR(dictionary_doc,
"dict() -> new empty dictionary\n"
"dict(mapping) -> new dictionary initialized from a mapping object's\n"
@@ -2190,7 +2378,7 @@ PyTypeObject PyDict_Type = {
0, /* tp_weaklistoffset */
(getiterfunc)dict_iter, /* tp_iter */
0, /* tp_iternext */
- mapp_methods, /* tp_methods */
+ dict_methods, /* tp_methods */
0, /* tp_members */
0, /* tp_getset */
0, /* tp_base */
@@ -2324,7 +2512,7 @@ static PyObject *dictiter_iternextkey(di
if (d == NULL)
return NULL;
- assert (PyDict_Check(d));
+ assert (PyFrozenDict_Check(d));
if (di->di_used != d->ma_used) {
PyErr_SetString(PyExc_RuntimeError,
@@ -2396,7 +2584,7 @@ static PyObject *dictiter_iternextvalue(
if (d == NULL)
return NULL;
- assert (PyDict_Check(d));
+ assert (PyFrozenDict_Check(d));
if (di->di_used != d->ma_used) {
PyErr_SetString(PyExc_RuntimeError,
@@ -2468,7 +2656,7 @@ static PyObject *dictiter_iternextitem(d
if (d == NULL)
return NULL;
- assert (PyDict_Check(d));
+ assert (PyFrozenDict_Check(d));
if (di->di_used != d->ma_used) {
PyErr_SetString(PyExc_RuntimeError,
@@ -2589,7 +2777,7 @@ dictview_new(PyObject *dict, PyTypeObjec
PyErr_BadInternalCall();
return NULL;
}
- if (!PyDict_Check(dict)) {
+ if (!PyFrozenDict_Check(dict)) {
/* XXX Get rid of this restriction later */
PyErr_Format(PyExc_TypeError,
"%s() requires a dict argument, not '%s'",
diff --git a/Objects/object.c b/Objects/object.c
--- a/Objects/object.c
+++ b/Objects/object.c
@@ -1620,6 +1620,9 @@ _Py_ReadyTypes(void)
if (PyType_Ready(&PyRange_Type) < 0)
Py_FatalError("Can't initialize range type");
+ if (PyType_Ready(&PyFrozenDict_Type) < 0)
+ Py_FatalError("Can't initialize frozendict type");
+
if (PyType_Ready(&PyDict_Type) < 0)
Py_FatalError("Can't initialize dict type");
diff --git a/Python/bltinmodule.c b/Python/bltinmodule.c
--- a/Python/bltinmodule.c
+++ b/Python/bltinmodule.c
@@ -2396,6 +2396,7 @@ _PyBuiltin_Init(void)
SETBUILTIN("enumerate", &PyEnum_Type);
SETBUILTIN("filter", &PyFilter_Type);
SETBUILTIN("float", &PyFloat_Type);
+ SETBUILTIN("frozendict", &PyFrozenDict_Type);
SETBUILTIN("frozenset", &PyFrozenSet_Type);
SETBUILTIN("property", &PyProperty_Type);
SETBUILTIN("int", &PyLong_Type);
_______________________________________________
Python-Dev mailing list
[email protected]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
