[Python-Dev] Add a frozendict builtin type (original) (raw)

Victor Stinner victor.stinner at haypocalc.com
Mon Feb 27 19:53:27 CET 2012

Previous message: [Python-Dev] [Python-checkins] cpython (3.2): Updated logging cookbook with info on alternative format styles.
Next message: [Python-Dev] Add a frozendict builtin type
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Rationale

A frozendict type is a common request from users and there are various implementations. There are two main Python implementations:

"blacklist": frozendict inheriting from dict and overriding methods to raise an exception when trying to modify the frozendict
"whitelist": frozendict not inheriting from dict and only implement some dict methods, or implement all dict methods but raise exceptions when trying to modify the frozendict

The blacklist implementation has a major issue: it is still possible to call write methods of the dict class (e.g. dict.set(my_frozendict, key, value)).

The whitelist implementation has an issue: frozendict and dict are not "compatible", dict is not a subclass of frozendict (and frozendict is not a subclass of dict).

I propose to add a new frozendict builtin type and make dict type inherits from it. frozendict would not have methods to modify its content and values must be immutable.

Constraints

frozendict values must be immutable, as dict keys
frozendict can be used with the C API of the dict object (e.g. PyDict_GetItem) but write methods (e.g. PyDict_SetItem) would fail with a TypeError ("expect dict, got frozendict")
frozendict.hash() has to be determinist
frozendict has not the following methods: clear, delitem, pop, popitem, setdefault, setitem and update. As tuple/frozenset has less methods than list/set.
issubclass(dict, frozendict) is True, whereas issubclass(frozendict, dict) is False

Implementation

Add an hash field to the PyDictObject structure
Make dict inherits from frozendict
frozendict values are checked for immutability property by calling their hash method, with a fast-path for known immutable types (int, float, bytes, str, tuple, frozenset)
frozendict.hash computes hash(frozenset(self.items())) and caches the result is its private hash attribute

Attached patch is a work-in-progress implementation.

TODO

Add a frozendict abstract base class to collections?
frozendict may not overallocate dictionary buckets?

Examples of frozendict implementations:

http://bob.pythonmac.org/archives/2005/03/04/frozendict/ http://code.activestate.com/recipes/498072-implementing-an-immutable-dictionary/ http://code.activestate.com/recipes/414283-frozen-dictionaries/ http://corebio.googlecode.com/svn/trunk/apidocs/corebio.utils.frozendict-class.html http://code.google.com/p/lingospot/source/browse/trunk/frozendict/frozendict.py http://cmssdt.cern.ch/SDT/doxygen/CMSSW_4_4_2/doc/html/d6/d2f/classfrozendict_1_1frozendict.html

See also the recent discussion on python-list:

http://mail.python.org/pipermail/python-list/2012-February/1287658.html