Construire un frozendict en Python

Antoine "entwanne" Rozo

Mutabilité

• Il existe en Python des types mutables et immutables
• Les valeurs de types immutables ne peuvent pas être altérées
• Par exemple : int, float, str, tuple, frozenset

my_list = [0]
my_list[0] = 12
my_list

[12]

my_tuple = (0,)
my_tuple[0] = 12
my_tuple

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[3], line 2
      1 my_tuple = (0,)
----> 2 my_tuple[0] = 12
      3 my_tuple

TypeError: 'tuple' object does not support item assignment

Mutabilité

• Redéfinition ≠ altération

my_tuple = my_other_tuple = ()
my_tuple += (42,)
my_tuple

(42,)

my_other_tuple

()

Frozendict ?

• Python propose des équivalents immutables à ses collection muables :
  • list → tuple
  • set → frozenset
  • mais pas aux dictionnaires
• Il est impossible en Python de créer de nouveaux types immutables

• … vraiment ?

Construire un frozendict en Python

• Avec quelques contraintes :
  • En pur Python, sans extension C ou autre
  • S'appuyant uniquement sur la lib standard
  • Respectant l'interface du dictionnaire (mapping, opérateur d'union)
  • Parfaitement immutable & hashable
  • Accès aux éléments en temps constant (O(1))

Frozen dataclass

Frozen dataclass

• @dataclass(frozen=True) construit une dataclass immutable
• Stockant deux tuples : clés et valeurs

Frozen dataclass

• Première ébauche avec une interface provisoire

from dataclasses import dataclass
@dataclass(frozen=True)
class frozendict:
    _keys: tuple
    _values: tuple

    @classmethod
    def from_dict(cls, base={}, **kwargs):
        base = base | kwargs
        return cls(_keys=tuple(base.keys()), _values=tuple(base.values()))

fd = frozendict.from_dict(key='value')
fd

frozendict(_keys=('key',), _values=('value',))

Frozen dataclass

• L'objet semble bien immutable

fd._values[0] = None

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[8], line 1
----> 1 fd._values[0] = None

TypeError: 'tuple' object does not support item assignment

fd._values = (None,)

---------------------------------------------------------------------------
FrozenInstanceError                       Traceback (most recent call last)
Cell In[9], line 1
----> 1 fd._values = (None,)

File <string>:16, in __setattr__(self, name, value)

FrozenInstanceError: cannot assign to field '_values'

Frozen dataclass

• Mais pas trop !

fd.__dict__['_values'] = (None,)
fd

frozendict(_keys=('key',), _values=(None,))

Les slots à la rescousse

• Normal, c'est à cause de __dict__
• Utilisons donc des __slots__ (@dataclass(slots=True))

from dataclasses import dataclass
@dataclass(frozen=True, slots=True)
class frozendict:
    _keys: tuple
    _values: tuple

    @classmethod
    def from_dict(cls, base={}, **kwargs):
        base = base | kwargs
        return cls(_keys=tuple(base.keys()), _values=tuple(base.values()))

frozendict.__slots__

('_keys', '_values')

fd = frozendict.from_dict(key='value')
fd

frozendict(_keys=('key',), _values=('value',))

Les slots à la rescousse

• Jusqu'ici tout va bien

fd._values[0] = None

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[14], line 1
----> 1 fd._values[0] = None

TypeError: 'tuple' object does not support item assignment

fd._values = (None,)

---------------------------------------------------------------------------
FrozenInstanceError                       Traceback (most recent call last)
Cell In[15], line 1
----> 1 fd._values = (None,)

File <string>:16, in __setattr__(self, name, value)

FrozenInstanceError: cannot assign to field '_values'

fd.__dict__['_values'] = (None,)

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[16], line 1
----> 1 fd.__dict__['_values'] = (None,)

AttributeError: 'frozendict' object has no attribute '__dict__'

Les slots à la rescousse

• Et en fait non

object.__setattr__(fd, '_values', (None,))
fd

frozendict(_keys=('key',), _values=(None,))

• Inutile d'aller plus loin dans cette approche

Mapping proxy

Mapping proxy

• Type immutable méconnu de la lib standard : mappingproxy
• Wrapper immutable sur un mapping (dictionnaire)
• Utilisé pour stocker les attributs d'une classe
• Vraie immutabilité (implémenté dans l'interpréteur)
  • Pas d'attribut exposé

Mapping proxy

• Il respecte l'interface des mappings

from types import MappingProxyType
m = MappingProxyType({'key': 'value'})
m

mappingproxy({'key': 'value'})

m['key']

'value'

• Est immutable

m['key2'] = None

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[20], line 1
----> 1 m['key2'] = None

TypeError: 'mappingproxy' object does not support item assignment

Mapping proxy

• Mais ne respecte pas à 100% l'interface voulue

type(m | MappingProxyType({}))

dict

Mapping proxy

• Mêmes performances que le dictionnaire
  • Ce n'est qu'un proxy sur ce dictionnaire

• Ce qui peut poser problème :

empty_dict = {}
empty_mapping = MappingProxyType(empty_dict)
empty_mapping

mappingproxy({})

empty_dict['key'] = 12
empty_mapping

mappingproxy({'key': 12})

Mapping proxy

• Et son hashabilité dépend de la valeur proxifiée

{empty_mapping}

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[24], line 1
----> 1 {empty_mapping}

TypeError: unhashable type: 'dict'

• Il faudrait le créer avec un mapping immutable…

Mapping proxy

• Et avec un wrapper copiant le dictionnaire et surchargeant l'opérateur | ?
  • On ne peut pas hériter de MappingProxyType
  • Comment stocker le mapping dans un attribut qui ne serait pas redéfinissable ?
  • Il reste un dictionnaire mutable quelque part en mémoire

Construire un type immutable

Se baser sur un type immutable existant

• Les types immutables de Python sont implémentés dans l'interpréteur, sans attributs
• On peut les étendre par héritage
  • Une classe héritant de tuple produit des tuples immutables

class T(tuple):
    pass

values = T((1, 2, 3))
values

(1, 2, 3)

values[0] = 3

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[26], line 1
----> 1 values[0] = 3

TypeError: 'T' object does not support item assignment

Collection immutable

• Quel type choisir pour l'étendre ?

• int / float / complex ? Pas pratique voire impossible

• str ? Mieux mais contraignant

• tuple ?
  • ((k1, v1), (k2, v2), ...) ou ((k1, k2, ...), (v1, v2, ...))
  • Pas mal mais demande du boulot pour les opérations en temps constant

• frozenset !
  • Implémente déjà une table de hashage

frozenset → frozendict

• frozendict = frozenset de paires (clé, valeur)

class frozendict(frozenset):
    def __new__(cls, base={}, /, **kwargs):
        return super().__new__(cls, dict(base, **kwargs).items())

frozenset → frozendict

• Premiers pas vers l'interface d'un mapping : protocole d'itération

class frozendict(...):
    [...]

    def __iter__(self):
        return self.keys()

    def items(self):
        return super().__iter__()

    def keys(self):
        return (key for key, _ in self.items())

    def values(self):
        return (value for _, value in self.items())

frozenset → frozendict

• Représentation similaire à celle d'un dictionnaire

class frozendict(...):
    [...]

    def __repr__(self):
        name = type(self).__name__
        if self:
            return f'{name}({dict(self.items())})'
        else:
            return f'{name}()'

frozenset → frozendict

fd = frozendict(key='value', foo='bar')
fd

frozendict({'foo': 'bar', 'key': 'value'})

list(fd)

['foo', 'key']

list(fd.keys())

['foo', 'key']

list(fd.values())

['bar', 'value']

list(fd.items())

[('foo', 'bar'), ('key', 'value')]

Opérateur in

• Comment gérer l'opération in ?
  • Comment savoir qu'une clé existe dans un des couples stockés ?

• Classe _matcher permettant _matcher(key) == (key, value)

class _matcher:
    def __init__(self, key):
        self.key = key

    def __eq__(self, rhs):
        key, value = rhs
        return self.key == key

Opérateur in

• Utilisée ensuite par __contains__

class frozendict(...):
    [...]

    def __contains__(self, key):
        return super().__contains__(_matcher(key))

fd = frozendict(key='value', foo='bar')

'key' in fd

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[38], line 1
----> 1 'key' in fd

Cell In[36], line 5, in frozendict.__contains__(self, key)
      4 def __contains__(self, key):
----> 5     return super().__contains__(_matcher(key))

TypeError: unhashable type: '_matcher'

Opérateur in

• Les valeurs égales doivent avoir le même hash
  • hash(_matcher(key)) == hash(key)

class _matcher:
    [...]

    def __hash__(self):
        return hash(self.key)

'key' in fd

False

• L'ensemble ne contient pas key mais (key, value)
  • hash(_matcher(key)) != hash((key, value))

Opérateur in

• Nouvelle classe _pair (couple immutable) pour garantir l'égalité de hash avec la clé

class _pair(tuple):
    def __new__(cls, key, value):
        return super().__new__(cls, (key, value))

    def __hash__(self):
        return hash(self[0])

• On stocke alors des _pair dans notre ensemble plutôt que des tuple

class frozendict(...):
    [...]

    def __new__(cls, base={}, /, **kwargs):
        return super().__new__(
            cls,
            (
                _pair(key, value)
                for key, value in dict(base, **kwargs).items()
            ),
        )

    def items(self):
        return (tuple(pair) for pair in super().__iter__())

Opérateur in

fd = frozendict(key='value', foo='bar')

'key' in fd

True

'foo' in fd

True

'key2' in fd

False

Opérateur []

• Comment gérer l'accès à un élément ?
  • Réutiliser l'opérateur in
  • Le _matcher peut stocker la valeur associée lors du test d'égalité

class _matcher:
    [...]

    def __eq__(self, rhs):
        key, value = rhs
        if self.key == key:
            self.value = value
            return True
        return False

Opérateur []

class frozendict(...):
    [...]

    def __getitem__(self, key):
        m = _matcher(key)
        if super().__contains__(m):
            return m.value
        raise KeyError(key)

fd = frozendict(key='value', foo='bar')

fd['key']

'value'

fd['foo']

'bar'

fd['key2']

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[52], line 1
----> 1 fd['key2']

Cell In[48], line 8, in frozendict.__getitem__(self, key)
      6 if super().__contains__(m):
      7     return m.value
----> 8 raise KeyError(key)

KeyError: 'key2'

Opérateur get

• Idem avec une valeur par défaut sur le _matcher

class _matcher:
    [...]

    def __init__(self, key, value=None):
        self.key = key
        self.value = value

class frozendict(...):
    [...]

    def get(self, key, default=None):
        m = _matcher(key, default)
        super().__contains__(m)
        return m.value

Opérateur get

fd = frozendict(key='value', foo='bar')

fd.get('key')

'value'

fd.get('key', 'default')

'value'

fd.get('key2')

fd.get('key2', 'default')

'default'

frozenset → frozendict

• Finalisons l'interface :
  • __len__ est déjà implémentée sur frozenset
  • Ajout des opérateurs d'égalité et d'union se basant sur des dictionnaires
  • Suppression des méthodes inutilisées de frozenset

class frozendict(...):
    [...]

    def __eq__(self, rhs):
        return dict(self) == rhs

    def __hash__(self):
        return hash(frozenset(self.items()))

    def __or__(self, rhs):
        return type(self)(dict(self) | rhs)

    def __ror__(self, lhs):
        return type(self)(lhs | dict(self))

    __and__ = None
    copy = None
    different = None
    intersection = None
    isdisjoint = None
    issubset = None
    issuperset = None
    symmetric_difference = None
    union = None

Quelques tests

empty_dict = frozendict()

assert str(empty_dict) == repr(empty_dict) == 'frozendict()'

assert len(empty_dict) == 0
assert list(empty_dict) == []

assert 'key' not in empty_dict
assert empty_dict.get('key') is None
assert empty_dict.get('key', 'default') == 'default'

assert list(empty_dict.keys()) == []
assert list(empty_dict.values()) == []
assert list(empty_dict.items()) == []

assert empty_dict == empty_dict
assert empty_dict == frozendict()
assert empty_dict == {}

assert hash(empty_dict) == hash(frozendict())

Quelques tests

fdict = frozendict({'key': 'value'})

assert str(fdict) == repr(fdict) == "frozendict({'key': 'value'})"

assert len(fdict) == 1
assert list(fdict) == ['key']

assert 'key' in fdict
assert fdict['key'] == 'value'
assert fdict.get('key') == 'value'

assert list(fdict.keys()) == ['key']
assert list(fdict.values()) == ['value']
assert list(fdict.items()) == [('key', 'value')]

assert fdict == fdict
assert fdict != empty_dict
assert fdict != {}
assert fdict == frozendict(key='value')
assert fdict == {'key': 'value'}

assert hash(fdict) == hash(frozendict(key='value'))
assert hash(fdict) != hash(empty_dict)
assert hash(fdict) != hash(frozendict(key=None))

frozenset → frozendict

• Encore un petit problème…

tuple(fdict)

('key',)

list(fdict)

['key']

set(fdict)

{('key', 'value')}

Wrapper immutable

Wrapper immutable

• Il faudrait un wrapper autour du frozenset
  • Mais un wrapper immutable

• Avec super !

t = super(tuple, (1, 2, 3))
t.__self__

(1, 2, 3)

t.__self__[0] = 4

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[67], line 1
----> 1 t.__self__[0] = 4

TypeError: 'tuple' object does not support item assignment

t.__self__ = (1, 2)

---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
Cell In[68], line 1
----> 1 t.__self__ = (1, 2)

AttributeError: readonly attribute

Wrapper immutable

• frozendict basé sur super utilisant un frozenset en suppprt

class frozendict(super):
    [...]

    def __init__(self, base={}, /, **kwargs):
        super().__init__(
            frozenset,
            frozenset(_pair(key, value) for key, value in dict(base, **kwargs).items()),
        )

Wrapper immutable

• Redéfinition de toutes les méthodes nécessaires
  • super().__self__ pour accéder au frozenset

class frozendict(...):
    [...]

    def __len__(self):
        return len(super().__self__)

    def __contains__(self, key):
        return _matcher(key) in super().__self__

    def __getitem__(self, key):
        m = _matcher(key)
        if m in super().__self__:
            return m.value
        raise KeyError

    def get(self, key, default=None):
        m = _matcher(key, default)
        m in super().__self__
        return m.value

Wrapper immutable

class frozendict(...):
    [...]

    def __iter__(self):
        it = iter(super().__self__)
        return (key for key, _ in it)

    def keys(self):
        return iter(self)

    def values(self):
        it = iter(super().__self__)
        return (value for _, value in it)

    def items(self):
        it = iter(super().__self__)
        return (tuple(pair) for pair in it)

Wrapper immutable

• Suppression des attributs inutilisés

class frozendict(...):
    [...]

    __self__ = None
    __self_class__ = None
    __thisclass__ = None

Wrapper immutable

• On reproduit les tests précédents

fdict = frozendict({'key': 'value'})

assert str(fdict) == repr(fdict) == "frozendict({'key': 'value'})"

assert len(fdict) == 1
assert list(fdict) == ['key']

assert 'key' in fdict
assert fdict['key'] == 'value'
assert fdict.get('key') == 'value'

assert list(fdict.keys()) == ['key']
assert list(fdict.values()) == ['value']
assert list(fdict.items()) == [('key', 'value')]

assert fdict == fdict
assert fdict != empty_dict
assert fdict != {}
assert fdict == frozendict(key='value')
assert fdict == {'key': 'value'}

assert hash(fdict) == hash(frozendict(key='value'))
assert hash(fdict) != hash(empty_dict)
assert hash(fdict) != hash(frozendict(key=None))

Wrapper immutable

• Et c'est tout bon !

tuple(fdict)

('key',)

list(fdict)

['key']

set(fdict)

{'key'}

Conclusion

Conclusion

• Le cachier des charges est rempli
• Prochainement un type frozenmap dans Python (PEP 603)

• http://github.com/entwanne/presentation_frozendict
  • Avec support et snippets

• Des questions ?