Supprimer les références circulaires dans les dicts, les listes, les tuples

Question

J'ai ce code de hachage vraiment suivant qui supprime les références circulaires de tout type de structure de données construit à partir dict, tuple et list objets.

import ast 

def remove_circular_refs(o): 
    return ast.literal_eval(str(o).replace("{...}", 'None')) 

Mais je n'aime pas comment c'est hacky. Cela peut-il être fait sans transformer la structure de données en une représentation sous forme de chaîne?

Voici un exemple de structure pour tester avec:

doc1 = { 
    "key": "value", 
    "type": "test1", 
} 
doc1["self"] = doc1 
doc = { 
    'tags': 'Stackoverflow python question', 
    'type': 'Stackoverflow python question', 
} 
doc2 = { 
    'value': 2, 
    'id': 2, 
} 
remove_circular_refs(doc) 
remove_circular_refs(doc1) 
remove_circular_refs(doc2) 

Answer 1

Ne pas utiliser la conversion de chaîne, non. Il suffit de détecter la référence en parcourant la structure de données:

def remove_circular_refs(ob, _seen=None): 
    if _seen is None: 
     _seen = set() 
    if id(ob) in _seen: 
     # circular reference, remove it. 
     return None 
    _seen.add(id(ob)) 
    res = ob 
    if isinstance(ob, dict): 
     res = { 
      remove_circular_refs(k, _seen): remove_circular_refs(v, _seen) 
      for k, v in ob.items()} 
    elif isinstance(ob, (list, tuple, set, frozenset)): 
     res = type(ob)(remove_circular_refs(v, _seen) for v in ob) 
    # remove id again; only *nested* references count 
    _seen.remove(id(ob)) 
    return res 

Ce couvre dict, list, tuple, set et frozenset objets; il mémorise le id() de chaque objet vu, et quand on le voit à nouveau il est remplacé par None.

Démo:

>>> doc1 = { 
...  "key": "value", 
...  "type": "test1", 
... } 
>>> doc1["self"] = doc1 
>>> doc1 
{'key': 'value', 'type': 'test1', 'self': {...}} 
>>> remove_circular_refs(doc1) 
{'key': 'value', 'type': 'test1', 'self': None} 
>>> doc2 = { 
...  'foo': [], 
... } 
>>> doc2['foo'].append((doc2,)) 
>>> doc2 
{'foo': [({...},)]} 
>>> remove_circular_refs(doc2) 
{'foo': [(None,)]} 
>>> doc3 = { 
...  'foo': 'string 1', 'bar': 'string 1', 
...  'ham': 1, 'spam': 1 
... } 
>>> remove_circular_refs(doc3) 
{'foo': 'string 1', 'bar': 'string 1', 'ham': 1, 'spam': 1} 

Le dernier test, pour doc3, contient des références partagées; à la fois 'string 1' et 1 existent juste une fois en mémoire, avec le dictionnaire contenant plusieurs références à ces objets.