Immutable instances with circular references

This post is a continuation from Mutability model for ResourceType and friends. At this point I'm just going to geek out on design options - this doesn't really apply to the WCF Data Services API.

The problem is this: let's say we want to have two immutable values that reference each other.

// Obvious way, but not immutable.
CircularRef a = new CircularRef();
CircularRef b = new CircularRef();
a.theOtherOne = b;
b.theOtherOne = a;

Here we're changing the values of 'theOtherOne' property, so it's clear that the instances aren't immutable - they will have a null before we set the property, and then a reference after, so it's changing.

We can try saving this case with constructors, but we only get half-way there - we can't make the references circular.

// The constructor takes value for theOtherName,
// but the second instance can't grab ahold of 'a'.
CircularRef a = new CircularRef(new CircularRef());

Here is a solution that is syntactically correct but I consider a rather poor design. It turns out that in C#, you are allowed to pass instances of this to other parts of the program before your constructor has finished running. This little sample shows how to leverage that.

class C {

public static void Main() {
  var a = new CircularRef();
  Console.WriteLine("Done!");
  a.WriteOut(new HashSet<CircularRef>());
}

}

public class CircularRef {
  private static int idGen;
  private readonly int id;
  private readonly CircularRef theOtherOne;

  public CircularRef() {
    this.theOtherOne = new CircularRef(this);
    this.id = idGen++;
  }

  public CircularRef(CircularRef theOtherOne) {
    this.theOtherOne = theOtherOne;
    this.id = idGen++;
  }

  public void WriteOut(HashSet<CircularRef> visited) {
    // We use the HashSet to ensure we don't keep looping.
    if (visited.Add(this)) {
      Console.WriteLine("Found " + this.id);
      this.theOtherOne.WriteOut(visited);
    } else {
      Console.WriteLine("Breaking loop at " + this.id);
    }
  }
}

If you run this program, you can see that the references are indeed set up to point to each other.

Done!
Found 1
Found 0
Breaking loop at 1

The reason why I don't like this, however, is that the readonly keyword on the fields can lead you to believe that the type works like an immutable type; in fact, you can see all fields are assigned by the time the constructor is done, another good indication. However, a subtle "gotcha" is introduced: during construction, one of the instances gets to see a half-initialized, mutating version of the other one, so all the guarantees go out the window. In our sample, the second instance sees the first instance with an id set to the default value of zero, but then at some point that id value is going to change, when the first instance finished construction with the idGen++ assignment.

There are other problems with this design as well: to initialize the second instance, you need to pass the parameters through the first constructor, so it's a brittle design and small changes will likely ripple through multiple places in the code base.

Well, this post is running longer than I intended, and I didn't even got to the use of names / tokens / monikers in reference handling, which is what I intended. So I'll close off with a promise to continue next time and the following bit of advise.

Good rule of thumb: don't expose the this instance from constructors to the rest of the world unless you are very, very careful, and your objects can deal with getting calls or being looked at before construction has finished.

Enjoy!