Conceptual question on serializing data with circular references

I am trying to implement a serializer in python which tries to do something like this.

If there is an object Foo, having a forward reference to Bar, the serializer would dump all the data in Foo, and the reference would be converted into a data dump of Bar. Things would be done recursively like this for any arbitrary depth.

But there is a problem I run into with this approach, that of circular references, what if Foo references Bar and Bar references Foo? An infinite recursion would be created then.

开发者_开发技巧

What are the approaches to tackling this problem.

Note: I have no control over the data I would be serializing, so I can't rule out circular references.

---

Flatten out the structure beforehand with a depth-first search that records which items it has seen. Assign each object an id and replace object references with id references.

(In essence, turn it into a graph.)

---

Keep a list of objects you've already serialized. Every object you attempt to serialize should be checked against this list. A similar approach is to toggle a boolean within each object as to whether it's been serialized already, and thus not to continue for this object.

---

Study the Python pickle module which automatically handles circular references through serialization. It uses object ids to store references. Source code for Python 2.6.6 is here.