Immutable Object Graph with Cycles in Java
Tags: java, immutability, graph
Published: 2023-01-25 15:34:11

You are writing a Java program. You model your domain entities with objects referencing one another. You would like your objects to be immutable and therefore use `final` members in your classes.

Now you detect a problem: your object graph contains cycles. How do you instantiate your objects?

To illustrate, let's assume you have a class `Parent` and a class `Child`, and each references the other using final members:
```
class Parent {
        final Child child;

        final String name;

        Parent(Child child, String name) {
            this.child = child
            this.name = name;
        }

        public String toString() {
            return  name + " is the parent of " + this.child.name;
        }
    }

    static class Child {
        final Parent parent;

        final String name;

        Child(Parent parent, String name) {
            this.parent = parent;
            this.name = name;
        }

        public String toString() {
            return name + " is the child of " + this.parent.name;
        }

    }
```

When you try to instantiate a parent/child pair, you'll see there is no way to do that.

The problem is that you need the instance of Child for instantiating the parent and the instance of Parent for instantiating the child, and as these references inside the classes are final, you cannot have the one before you have the other. You somehow have to instantiate them at the same time... or somesuch.

However, it can be done, and here is how (omitting all the bells and whistles you would need for it to be thread-safe or otherwise nice, just laying out the main idea):
1. use the Builder pattern to create your objects
2. in the builder, keep a reference to the instance you return on calls to `build()`, and allow this instance to be set via a public method, e.g., `setProduct(T instance)`.
3. pass the builder for class X into the constructor of X
4. in the first line of the constructor, set the builder's instance to `this`, ie. `builder.setProduct(this)`.
5. instead of passing instances of classes to the constructors, pass Builders that return the instance on `build()`.

Here is the code:

```

public class ImmutableCyclicObjectGraphExperiment {


    static class Parent {
        final Child child;

        final String name;

        Parent(ParentBuilder builder, ChildBuilder childBuilder, String name) {
            builder.setInstance(this);
            this.child = childBuilder.build();
            this.name = name;
        }

        public String toString() {
            return  name + " is the parent of " + this.child.name;
        }
    }

    static class Child {
        final Parent parent;

        final String name;

        Child(ChildBuilder builder, ParentBuilder parentBuilder, String name) {
            builder.setInstance(this);
            this.parent = parentBuilder.build();
            this.name = name;
        }

        public String toString() {
            return name + " is the child of " + this.parent.name;
        }

    }

    static class ParentBuilder {
        ChildBuilder childBuilder;
        String name;
        Parent instance = null;

        public ParentBuilder() {
        }

        void setInstance(Parent instance){
            this.instance = instance;
        }

        Parent build() {
            if (this.instance == null) {
                this.instance = new Parent(this, this.childBuilder, this.name);
            }
            return this.instance;
        }

        public ParentBuilder child(ChildBuilder childBuilder) {
            this.childBuilder = childBuilder;
            return this;
        }

        public ParentBuilder name(String name) {
            this.name = name;
            return this;
        }
    }

    static class ChildBuilder {
        ParentBuilder parentBuilder;
        String name;
        Child instance = null;

        Child build() {
            if (this.instance == null) {
                this.instance = new Child(this, parentBuilder, name);
            }
            return this.instance;
        }

        void setInstance(Child instance) {
            this.instance = instance;
        }

        public ChildBuilder parent(ParentBuilder parentBuilder) {
            this.parentBuilder = parentBuilder;
            return this;
        }

        public ChildBuilder name(String name) {
            this.name = name;
            return this;
        }
    }


    public static void main(String[] args) {
        ParentBuilder pb = new ParentBuilder();
        ChildBuilder cb = new ChildBuilder();
        pb
            .name("Anakin")
            .child(cb);
        cb
            .name("Luke")
            .parent(pb);
        Parent p = pb.build();
        Child c = cb.build();
        System.out.println(p);
        System.out.println(c);
    }
}

```

What happens is that when `ParentBuilder.build()` is first called in the `main()` function, the builder calls the constructor of `Parent` and the reference `this` to the object being created is smuggled back out into the builder immediately. Then, in the next line of the same constructor, the `childBuilder`, passed as a constructor parameter, is used to obtain a `Child` instance. `childBuilder` calls the constructor of `Child`, passing a `ParentBuilder` instance, which is the same we already used in the `main()` function to begin instantiating a `Parent`, and which already holds the smuggled reference to the `Parent` still being created a few levels up the call stack. In the `Child` constructor, consequently, `parentBuilder.build()` returns the smuggled reference, which can be assigned to a final member, even though the object it references has not been fully instantiated. When `Child c = cb.build()` is called in the `main()` function, the instance is already fully instantiated and returned without calling the constructor.

As long as this happens within the same thread and you promise not to do anything with the instances but referencing them, you should be safe.



As expected, calling the `main()` method prints this:

```
Anakin is the parent of Luke
Luke is the child of Anakin
```

Immutable and cyclic, and all the indirection necessary is done at instantiation time. Isn't that nice?