detect circular reference in an object

Question

Suppose you have a java object, would it be possible to detect where exists circular references inside that java object?

I would like to hear if there is a library to deal with this problem.

Thanks in advance.

Answer 1

Beware, this is not trivial task, but you already know this, right? ;)

In Java there is implementation of IdentityHashMap that is designed to be uses in such cases.

Answer 2

Conceptually simple, but can be quite complex to implement.

First off, a lot depends on what type of objects you're dealing with. If only a small number of object classes, and you "own" the classes and can modify them to add "search yourself" code, then it becomes much easier:

Add an interface to each class and implement the "search yourself" method in each class. The method receives a list of objects, and returns a return code. The method compares its own address to each object on the list, returning true (ie, loop found) if one matches. Then (if no match) it adds its own address to the list and calls, in turn, the "search yourself" method of each object reference it contains. If any of these calls results in a true return code, that is returned, otherwise false is returned. (This is a "depth-first, recursive" search.)

If you don't "own" the classes then you must use reflections to implement essentially the above algorithm without modifying the classes.

There are other search algorithms that can be used -- "breadth-first", and various non-recursive versions of depth-first, but they all represent trade-offs of one sort or another of between heap storage, stack storage, and performance.

Answer 3

A bit of a lateral answer, but how about using net.sf.json.JSONObject.fromObject(...) which checks for circular references and throws an exception if any are found. Also, you can configure the library to handle circular references differently if necessary. You would have to write a getter for those class members that exist in the cyclical relationship, since that is what JSONObject uses to create the JSON.