[Python-Dev] Add a frozendict builtin type

Mon Feb 27 19:53:27 CET 2012

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

--