Deep copying Java objects with circular references

Question

How would I go about implementing a deep copy for Foo? It contains an instance of Bar, which then has a reference to that Foo.

public class Foo {

    Bar bar;

    Foo () {
        bar = new Bar(this);
    }

    Foo (Foo oldFoo) {
        bar = new Bar(oldFoo.bar);
    }

    public static void main(String[] args) {
        Foo foo = new Foo();
        Foo newFoo = new Foo(foo);
    }

    class Bar {
        Foo foo;

        Bar (Foo foo) {
            this.foo = foo;
        }

        Bar (Bar oldBar) {
            foo = newFoo(oldbar.Foo);
        }
    }
}

As it stands, this code would cause a stack overflow due to infinite recursion.

Also, this is the most simplistic example I could construct. In practice, the object graph would be larger, with multiple instance variables which could themselves be collections. Think multiple Bars, with multiple Foos, for instance.

---

EDIT: I'm currently in the process of implementing @chiastic-security's method. Am I doing it correctly for Foo? I'm using a separate HashMap to contain all parts of the object graph so that I can write the deep copy functionality as generally as possible.

Foo (Foo oldFoo) throws Exception {
    this(oldFoo, new IdentityHashMap<Object, Object>(), new IdentityHashSet<Object>());
}

Foo (Foo oldFoo, IdentityHashMap<Object, Object> clonedObjects, IdentityHashSet<Object> cloning) throws Exception {
    System.out.println("Copying a Foo");

    HashMap<Object, Object> newToOldObjectGraph = new HashMap<Object, Object>();
    newToOldObjectGraph.put(bar, oldFoo.bar);
    deepCopy(newToOldObjectGraph, clonedObjects, cloning);
}

void deepCopy(HashMap<Object, Object> newToOldObjectGraph, IdentityHashMap<Object, Object> clonedObjects, IdentityHashSet<Object> cloning) throws Exception {
    for (Entry<Object, Object> entry : newToOldObjectGraph.entrySet()) {
        Object newObj = entry.getKey();
        Object oldObj = entry.getValue();

        if (clonedObjects.containsKey(oldObj)) {
            newObj = clonedObjects.get(oldObj);
        }
        else if (cloning.contains(oldObj)){
            newObj = null;
        }
        else {
            cloning.add(oldObj);
            // Recursively deep clone
            newObj = newObj.getClass().getConstructor(oldObj.getClass(), clonedObjects.getClass(), cloning.getClass()).
                newInstance(oldObj, clonedObjects, cloning);

            clonedObjects.put(oldObj, newObj);
            cloning.remove(oldObj);
        }
        if (newObj == null && clonedObjects.containsKey(oldObj)) {
            newObj = clonedObjects.get(oldObj);
        }
    }
}

Answer 1

The easiest way to implement a deep copy that might involve circular references, if you want it to be tolerant of changes to the structure later, would be to use an IdentityHashMap and an IdentityHashSet (from here). When you want to copy:

1. Create an empty IdentityHashMap<Object,Object>, to map source objects to their clones.
2. Create an empty IdentityHashSet<Object> to track all the objects that are currently in the process of being cloned, but haven't yet finished.
3. Start the copy process going. At each stage, when you want to copy an object, look it up in your IdentityHashMap to see if you've already cloned that bit. If you have, return the copy that you find in the IdentityHashMap.
4. Check in the IdentityHashSet to see if you're in the middle of cloning the object you've now reached (because of a circular reference). If you have, just set it to null for now, and move on.
5. If you haven't previously cloned this (i.e., the source object isn't in the map), and you're not in the middle of cloning it (i.e., it's not in the set), add it to the IdentityHashSet, recursively deep clone it, and then when you've finished the recursive call, add the source/clone pair to the IdentityHashMap, and remove it from the IdentityHashSet.
6. Now at the end of your recursive cloning, you need to deal with the null references you left hanging because you encountered a circular reference. You can walk the graph of source and destination simultaneously. Whenever you find an object in the source graph, look it up in your IdentityHashMap, and find out what it should map to. If it exists in the IdentityHashMap, and if it's currently null in the destination graph, then you can set the destination reference to the clone you find in the IdentityHashMap.

This will make sure you don't clone the same part of the graph twice, but always end up with the same reference whenever there's an object that appears twice in your graph. It will also mean that circular references don't cause infinite recursion.

The point of using the Identity versions is that if two objects in your graph are the same as determined by .equals(), but different instances as determined by ==, then a HashSet and HashMap would identify the two, and you'd end up joining things together that shouldn't be joined. The Identity versions will treat two instances as the same only if they're identical, i.e., the same as determined by ==.

If you want to do all this but without having to implement it yourself, you could have a look at the Java Deep Cloning Library.