[Python-Dev] Pre-PEP: Mutable keys in dictionaries (original) (raw)

Just van Rossum just@letterror.com
Thu, 6 Feb 2003 00:54:26 +0100

Here's a quick pre-PEP.

Allow mutable objects as dictionary keys in certain cases by adding a new protocol. dict.setitem() and contains() would work like this bit of pseudo code:

def setitem(self, key, value): if not hashable(key): if hasattr(key, "immutable_copy"): key = key.immutable_copy() else: raise TypeError, "unhashable key" ...insert value with key into dict...

def contains(self, key): if not hashable(key): if hasattr(key, "temporary_immutable"): key = key.temporary_immutable() else: raise TypeError, "unhashable key" ...test for key membership...

(other methods would be similar)

When implemented in C in dictobject.c, this would add no overhead for the "normal" case (when keys are directly hashable).

The temporary_immutable part of the protocol is needed to avoid unneccesary copying in those cases where the key isn't actually inserted into the dict, but is only used for membership testing. It would return a wrapper around the mutable object, defining eq and hash. (This idea is stolen from the sets.py module.) If an implementer doesn't care about this efficiency, temporary_immutable can be an alias to immutable_copy.

Use Cases:

Backwards compatibilty:

100%.

Overhead added

None

Implementation

There's quite a bit of code duplication in those areas of dictobject.c that matter for this proposal, so implementing it will take longer than the 10 minutes I originally estimated . Perhaps this is a good opportunity to refactor these bits into inline functions? Not being a C guru I can't judge whether this is possible or desirable with the set of compilers that Python must be built with.

Just