CTM - Clone To Modify Pattern

Background

Functional programming is getting a lot of attention lately. Between its traits, one that is being copied by other languages in many different ways is Immutability.

Immutability on its own is very simple and at the same time, very powerful. It's simple because it simply means that an object content will not change. When we know that an object is immutable, we have the guarantee that we can give such object to other methods without risking to have a different object at the end. If we don't have such guarantee and we need it, we are usually forced to give a copy of such object to the method so our private instance is not touched.

Such guarantee is also excellent for multi-threaded scenarios. Many threads can simply access the same object at the same time without locks, as it is simply impossible for one thread to see an intermediary state between changes, as the object is not going to change at all (maybe a variable may be updated to point to another instance, but an existing instance is never going to change). Such behavior can greatly reduce the complexity of cache implementations, for example.

But differently than functional programming or really immutable objects, where each "mutation" means a new full object being allocated, I will present a pattern that I call CTM (meaning Clone to Modify).

The Different Kinds of Immutability

Before really presenting the Clone to Modify Pattern, I want to present some different kinds of immutability.

Read-Only Interface

This one is far from real immutability. The purpose in this case is to return an instance by an interface that sees the instance as read-only.

The problem in such approach is that the object can still be mutated, be it by the method that created it (so the receiver does not have any guarantee), be it by someone capable of casting the object back to its original mutable type (so the creator does not have a guarantee). Yet, in most cases, it looks like read-only and will avoid mutations to be done by pure accident.

Read-Only Wrapper

In this case, we have the List<T> and the ReadOnlyCollection<T>. The list is modifiable, but by calling the AsReadOnly(), we get another instance that can't be modified.

As it is another instance, we can't simply cast it back to the original List<T>, so it is safer than returning the object by a read-only interface. The receiver of such object is incapable of modifying it but the owner of the List<T> is still capable of modifying it.

In this case, or the receiver simply believes it is receiving an unmodifiable instance (maybe in the documentation such guarantee is given) or, if such guarantee must be enforced, an internal copy will be needed (and in threading scenarios, even the copy can be problematic).

Full Immutability

An object that is fully filled in its constructor and later doesn't allow you to change its contents is fully immutable. To achieve that, it can't have state changing methods, property setters or public fields that aren't readonly (ok, public fields are already a bad idea, but that's not the point). Also, if it has references, those references should not allow their content to be modified either (it is of no use to have a read-only reference to a List<T> when the list itself can be modified).

One example of such immutability is the string class. We can concatenate a string to another or Trim() it, but we are never changing the actual string, we are getting a new one with the desired change. So, if anyone had a reference to the old string, that old string is kept intact.

The big disadvantage of this kind of immutability is that we may need to make many intermediate copies if we want to make many different changes.

Mutable Until Frozen

In this situation, our objects starts their life as a mutable and, at a given moment, they are marked as immutable. From that point on, no more changes can be made.

In many situations this can be seen as a better kind of immutability because we don't need to give a lot of parameters to the constructor of the object and we also don't need to create many instances for the intermediate states.

Yet, this is a dangerous kind of immutability when multi-threading is involved. For example, it is possible that a CPU caches an area of memory that includes the initial state (yet mutable) of the object. Another CPU then changes the object and marks it as immutable. Then the CPU that already had such object (or part of it) in memory may check it and:

1. See it as still mutable, and effectively mutate it when it was already marked as immutable by another CPU;
2. Notice that the object is immutable (one part of the object that's up-to-date in memory) and access its contents without any kind of lock, reading out-of-date data that was in the CPU cache before the object becomes immutable.

Finally, but not less important, it is the fact that such object may be expected to be always mutable, but one thread may freeze it before another thread finishes all the mutations needed. Surely by not giving a mutable object to another thread, we can solve the problem, yet it is a possible problem.

Usually, a mutable until frozen gives the possibility to make a modifiable clone of the actual object. This is somewhat similar to the Clone to Modify Pattern, yet it does not share all the traits.

Always Modifiable Read-Only Flag

This one shares all the problems of the Mutable Until Frozen but it is still worse, as the object can be made mutable again. So you can get a read-only instance and, later, another method decides the object should not be read-only anymore and change its contents.

This can look pretty silly, but it is a common pattern for database records in memory. They are presented as read-only until someone calls Edit(). For that purpose, it works very well, but it does not give any guarantee in multi-threading scenarios or if you want to pass the object to a method and expect that it will remain unchanged.

Clone to Modify Pattern

The Clone to Modify Pattern requires all types to be broken into two. One completely mutable and one completely immutable.

It can look similar to the Mutable Until Frozen because users will generally create a mutable instance, will do all the actions they need with such instance and finally will create an immutable clone.

The difference here is that the mutable instance is left mutable, so if someone else already has a reference to it, expecting it to be mutable, well, it will always be.

As the immutable instance started as immutable, there is no risk of another thread seeing it as mutable, so we can really avoid any kind of synchronization (in .NET, there is a guarantee that we will never see junk memory when we access an object for the first time).

Also, to make the pattern complete, we can always create a mutable clone from an immutable object (or even from another mutable object).

So, the basic principle of the Clone to Modify Pattern is:

• Each type is split into two, one fully mutable and one fully immutable.
• You can create an immutable clone from the mutable instance.
• You can create mutable clones from the immutable or from another mutable instance.

And we can see an example of it here:

public enum Sex
{
  Male,
  Female
}
public sealed class MutablePerson
{
  public string Name { get; set; }
  public Sex Sex { get; set; }

  public string StreetName { get; set; }
  public int? StreetNumber { get; set; }
  public string StreetComplement { get; set; }

  public MutablePerson MutableClone()
  {
    MutablePerson clone = new MutablePerson();
    clone.Name = Name;
    clone.Sex = Sex;

    clone.StreetName = StreetName;
    clone.StreetNumber = StreetNumber;
    clone.StreetComplement = StreetComplement;
    return clone;

    // A return (MutablePerson)MemberwiseClone() should work too.
    // But I think it is slower... and also the actual implementation
    // is identical to the one in ImmutablePerson.
  }

  public ImmutablePerson Clone()
  {
    return new ImmutablePerson(this);
  }
}
public sealed class ImmutablePerson
{
  internal ImmutablePerson(MutablePerson source)
  {
    Name = source.Name;
    Sex = source.Sex;

    StreetName = source.StreetName;
    StreetNumber = source.StreetNumber;
    StreetComplement = source.StreetComplement;
  }

  public string Name { get; private set; }
  public Sex Sex { get; private set; }

  public string StreetName { get; private set; }
  public int? StreetNumber { get; private set; }
  public string StreetComplement { get; private set; }

  public MutablePerson MutableClone()
  {
    MutablePerson clone = new MutablePerson();
    clone.Name = Name;
    clone.Sex = Sex;

    clone.StreetName = StreetName;
    clone.StreetNumber = StreetNumber;
    clone.StreetComplement = StreetComplement;
    return clone;
  }
}

But at this point, we still have threading issues. We can consider such issues as bad utilization, yet I will explain it: The idea is that you should never give mutable objects to other threads or methods, only the immutable instances. If you create your mutable instance, fill it and then create the immutable instance, which you will give to other methods, there is no chance that the immutable object is somewhat "corrupted". But when creating a pattern, we should at least think about the bad utilizations and decide if we will simply document them as bad utilizations, telling that it is the user responsibility not to use it incorrectly, or if we will give a solution even to such cases, like immediate exceptions (which are much better than corrupted data to find the source of the problem).

So, first, how can we have a problem? And the answer is: It is possible that a mutable object is being changed from another thread while an immutable clone is being made.

For example, imagine that for a person's record, you can let the address empty or, if you fill it, you should fill it completely (like street name, number, city, etc). But you are cloning the object while such info is filled.

Here, we have many possible solutions:

1. We make the StreetName, StreetNumber, etc. properties as read-only and have a method like SetAddress() that receives all the parameters, validates them all and then fills the object. Many people think this is a solution because the user will call a single method to set all the properties at once, yet this will only work from a single thread perspective, as even if the user does a single call, filling the properties still requires many operations. There are many tricks to try to solve the problem, but usually they don't give a real guarantee, they'll only reduce the chances of problems (which in many cases is still worse, as the bugs become less predictable).
2. Guarantee that you only use atomic operations. For example, instead of a SetAddress(), the mutable Person has a property of type ImmutableAddress. This may sound strange, but the idea is: you replace the entire Address instance, be it with another ImmutableAddress that was already filled or by setting null. But it is simply "impossible" to give a partially filled address.
3. We use locks on the mutable types. We can still have a SetAddress() method to fill the entire address or nothing, but it will do its work inside a lock. If we don't use a setAddress() method, then we need a validation during the creation of the immutable version, which will be holding a lock. Yet no lock is required on the immutable instance then.
4. Following the WPF and Silverlight principle (which was partially implemented in Windows Forms controls), only the thread that created the mutable object can access it. In this case, all operations, including reads, will throw exceptions if called from another thread. Following the idea of the previous item, we can keep a SetAddress() method with the address properties as read-only or we can validate during the creation of the immutable instance. This one gives two advantages over the previous one: It is faster and it enforces the good pattern (well, you can still give the mutable object to other methods, but not to other threads).

In my opinion, the first option is not a solution at all, but can be used with the other solutions if you think that a SetAddress() method is better than letting the user fill each one of the address' properties independently.

The second solution works great in respect to the Person->Address situation. You can never read a partially filled Address, as replacing one address by another is an atomic operation. Yet, if the address itself is divided into a mutable and an immutable type, it is possible that the immutable type is created reading from a mutable object that is being modified by another thread during such creation, effectively creating a partial address. This is why I said it is "impossible" and not impossible to fill a partial address. Replacing the address instance can't be partially seen, but the ImmutableAddress itself may be corrupted already. So, to really solve the problem, we need to use one of the other alternatives.

Alternatives 3 and 4 work correctly. We can say that both are very similar: All actions (gets, sets, cloning, etc.) require either a lock or a thread check. Yet, checking if the actual thread is the creator thread is faster than any kind of lock and also helps developers to use the right pattern, which is: create the object, fill it, create an immutable clone, use the immutable instance to give to other methods or threads.

In fact, using the last option, if you really need or want to avoid the performance hit of the thread checking, you could avoid the check in specific builds (like in Release) while you keep it for debug builds. If you give the object to another thread, it will simply fail in debug, so you know you should not do that (or better, the user of your code will now). That's something you can't do if you decide to use locks, because the lock will guarantee the code to work in debug... so it can't be removed later.

So, we can resume the corrected Clone to Modify Pattern as:

• Each type is split into two, one fully mutable and one fully immutable.
• The mutable instance can only be changed from its creator thread.
• You can create an immutable clone from the mutable instance. In this case, the thread check is done and an extra validation can be done during such clone to guarantee that all contents are correct.
• You can create mutable clones from the immutable instance. In this case, the creator thread is the one doing the clone and a validation is not required as the immutable object is guaranteed to be valid.
• You can create mutable clones from another mutable instance. In this case, the thread checking needs to be performed but the data validation does not, as it will be performed later when an immutable clone is created.

And our previous example can be rewritten like this:

public enum Sex
{
  Male,
  Female
}
public sealed class MutablePerson
{
  private int _ownerThreadId;
  public MutablePerson()
  {
    _ownerThreadId = Thread.CurrentThread.ManagedThreadId;
  }
  private void _CheckThread()
  {
    if (Thread.CurrentThread.ManagedThreadId != _ownerThreadId)
      throw new InvalidOperationException
              ("This object can only be used by the thread that created it.");
  }

  // Note: The fields can be internal instead of private
  // to allow the immutable version to access this instance directly
  // during its constructor. But in such case, the mutable and immutable
  // classes should be in a different assembly than the code that uses
  // it. A friend class like in C++ will be so good here.
  private string _name;
  public string Name
  {
    get
    {
      _CheckThread();
      return _name;
    }
    set
    {
      _CheckThread();
      _name = value;
    }
  }

  private Sex _sex;
  public Sex Sex
  {
    get
    {
      _CheckThread();
      return _sex;
    }
    set
    {
      _CheckThread();
      _sex = value;
    }
  }

  private string _streetName;
  public string StreetName
  {
    get
    {
      _CheckThread();
      return _streetName;
    }
    set
    {
      _CheckThread();
      _streetName = value;
    }
  }

  private int? _streetNumber;
  public int? StreetNumber
  {
    get
    {
      _CheckThread();
      return _streetNumber;
    }
    set
    {
      _CheckThread();
      _streetNumber = value;
    }
  }

  private string _streetComplement;
  public string StreetComplement
  {
    get
    {
      _CheckThread();
      return _streetComplement;
    }
    set
    {
      _CheckThread();
      _streetComplement = value;
    }
  }

  public MutablePerson MutableClone()
  {
    _CheckThread();

    MutablePerson clone = new MutablePerson();
    clone._name = _name;
    clone._sex = _sex;

    clone._streetName = _streetName;
    clone._streetNumber = _streetNumber;
    clone._streetComplement = _streetComplement;
    return clone;
  }

  public ImmutablePerson Clone()
  {
    _CheckThread();

    if (StreetName != null || StreetNumber != null || StreetComplement != null)
    {
      // If a part of the address is filled, the full address must be filled.
      // Yet, the Complement is always optional.

      if (StreetName == null || StreetNumber == null)
        throw new InvalidOperationException("The address is only partially filled.");
    }

    return new ImmutablePerson(this);
  }
}
public sealed class ImmutablePerson
{
  internal ImmutablePerson(MutablePerson source)
  {
    Name = source.Name;
    Sex = source.Sex;

    StreetName = source.StreetName;
    StreetNumber = source.StreetNumber;
    StreetComplement = source.StreetComplement;
  }

  public string Name { get; private set; }
  public Sex Sex { get; private set; }

  public string StreetName { get; private set; }
  public int? StreetNumber { get; private set; }
  public string StreetComplement { get; private set; }

  // There is no need to make a read-only clone of a read-only instance.
  // That's why there is no Clone() method returning an immutable clone
  // like there is on the Mutable instance.

  public MutablePerson MutableClone()
  {
    MutablePerson clone = new MutablePerson();
    clone.Name = Name;
    clone.Sex = Sex;

    clone.StreetName = StreetName;
    clone.StreetNumber = StreetNumber;
    clone.StreetComplement = StreetComplement;
    return clone;
  }
}

Usefulness

OK, I just presented a pattern that initially looks like adding a lot of complexity to something simple. So, what is its real purpose and usefulness?

Well, the whole idea is the guarantee of immutability and real lock-free accesses. For example, in a "We control everything" situation, we can create a Person instance that is always mutable, give such instance to many methods and even other threads and, if we wrote those methods and threads, we can have the guarantee that the final object will not be changed.

But such guarantee only exists because we wrote all the code. What will happen if we are calling a method that we simply don't know what it is doing internally? Maybe in one situation, it does not mutate the state of our object but in another situation, it does. Or worse, today it does not change our object but that may change on the future, breaking the existing code.

In caching scenarios, for example, if I don't know if the object is immutable or not, I usually clone a found object before returning it. In fact, that was a bug that I needed to solve in different cache implementations because changing a returned object was known to be wrong, yet the developers considered it was the Cache that was bugged, not their use of the objects. But considering an object that was created and filled only once, and accessed millions of times, well, there were millions of unnecessary clones.

When there is a guarantee that the object will not change, we can avoid such unnecessary clones, which will also help reduce the number of garbage collections.

Immutable Collections

During the presentation of the different kinds of immutability I talked about the ReadOnlyCollection<T>, which is not really immutable but at least guarantees to the creator that receivers will not change the list (or array... the real mutable collection). Also, Microsoft is investing in real Immutable Collections now. Yet, an immutable collection is only really immutable if the objects it holds are also immutable.

If that's not the case, that only means you will not be able to add, remove or replace one item by another, yet the contents inside each item will still be modifiable. That's usually not what you want. If you want a collection to be immutable, you want that new items aren't added, removed, replaced and that existing items don't have their contents changed. So, you will want to use immutable objects too.

Completely Immutable Objects Give the Same Guarantee

Surely they do. But now think about an immutable object with 30 properties that can be filled.

Will you give 30 parameters to the constructor? To me, that's terrible!

Will you use a fluent-like API, so you start from an empty object and at each property set, you'll receive a new instance with a copy of the previous object, but with the right property filled? Well, if you do it, you will need 30 allocations to fill 30 properties. Also, if your fields are also read-only, you will still need to pass all the parameters in the constructor. If later you add a new property, you will need to rewrite all the constructor calls... very bad.

Will you use a helper object to fill all the properties? Then, well, you are almost using the Clone to Modify Pattern. After all, one object will be mutable, which you'll use to fill properties you want without clones, and then you create the other object, the immutable one, as a copy of it.

In such situation, be it the fully Clone to Modify Pattern or a reduced version of it, you will only allocate two objects. One initial object, which you can mutate as many times as needed and another one, which will be the immutable clone.

But if you want to use an object to fill the parameters and another to be immutable, it is better to implement the full pattern, and allow the immutable one to be cloned again as mutable.

I Understood All the Problems, but the Mutable Until Frozen Works for Me

It can work, but how exactly are you writing your mutable until frozen type?

If you don't do a lock or volatile read when it is frozen, you may have the problem of having an invalid value if the object was just frozen from another thread. OK, it is a bad utilization of the object and if you really consider that it's up to the users to use the object correctly, then fine. But if you want to give a real guarantee (with an immediate exception if something is wrong), then consider the Clone to Modify Pattern.

You still don't want the Clone to Modify Pattern, so you plan to make all your fields volatile? OK, you will make using your object slower. In fact, by simply reading a single property of your object the CPU caches will probably be cleared, making the next code to also run slower as the caches will need to be refilled. If you do it with all your properties and objects, well, things may start to become really slow without hard to find reasons, as it will be a problem in all properties, not something concentrated in a single method.

Which the Clone To Modify Pattern, setting values may have a small overhead (the thread check), but reading values on the immutable instances has no overhead at all.

Validated Types Can Be a Little Different Than Mutable/intermediate Types

The Clone To Modify Pattern gives one kind of advantage that's simply impossible to get with types that are frozen after they are created. It is the possibility to change data-types during the creation of the immutable instance.

To show an example, imagine that you want to put mandatory int properties in your type, yet 0 is a valid value and you want that users explicitly set a value of zero. If you declare your property as a normal int, then the zero will be the default value, so you decide to make the properties of type Nullable<int>.

But as you will do a validation while generating the immutable instance, it is guaranteed that such instance will never have a value of null, so you can declare the type as int in such instance.

This is a situation that completely immutable types that start as empty and use a fluent interface to be filled and objects that can be frozen can't solve, after all the same type should support the filled and unfilled values. But when we have an extra type as the final immutable instance, we have another chance to optimize the instance which, in this case, means we can use non-nullable types because we know the values simply can't be null.

The Limits of the Guarantee

The immutability guarantee is a guarantee to avoid errors, not a full guarantee. In fact, there is no real guarantee, ever. Reflection (capable of accessing private fields and changing readonly fields), unsafe code, changing values from the debugger or simply hacks in general can break the immutability guarantee.

If your code is victim of such mutability, well, I think it is a situation where you can say there is no bug in your code, it is a real bad utilization (or should I say a real hacking?) of your code. Except if you work in new ways of avoiding such hacks, then there is nothing to worry about.

A Matter of Quality

The entire pattern that I presented in this article can be seen as a Quality Pattern. As already explained, you can use mutable objects as parameters in many methods and as long as those methods don't change the received parameter, you can consider such object as immutable.

Yet, if you don't have the code of such methods (or if you don't verify them internally), you will need to believe they will work as expected. There will be no guarantee that a given parameter instance will not be mutated.

But to create such guarantee, we have overheads (the thread check on the mutable instance and the need to do an immutable clone). So, is it worth it?

And the answer is almost the same as: It is worth checking if a parameter is null and throwing ArgumentNullExceptions?

That's extra code added by the programmer, with the sole purpose of giving an error message immediately instead of receiving a NullReferenceException later. And, in fact, is it worth that the .NET check for null values to throw NullReferenceExceptions? Isn't better to simply dereference the null value and let the program corrupt memory?

If you think that Quality means better Performance, then the answer is No. Using a fully mutable object as read-only, avoiding any locks and any cloning is faster and reduces the amount of code written.

But if you think that Quality means that a future bad piece of code will not corrupt the state of the actual good piece of code, then this pattern is a Quality Pattern. If you think that quality is to have something that will help identify the bad pieces of code immediately and at the right places instead of having to spend hours (or even days) trying to figure out what is wrong, then this is again a Quality Pattern.

So, what is quality for you? Code that runs in the fastest possible manner if used correctly, but that may corrupt states everywhere if used incorrectly, or code that has a good performance (not best) but that will throw exceptions if used incorrectly, without corrupting the rest of the application?

Conclusion

Here, I wanted to present a pattern that I use for some time and that I consider very useful when our code needs to give a specific guarantee, which I consider to be a Quality Pattern because it will not let the states of the objects to be corrupted and, by throwing immediate exceptions if used incorrectly, forces the users of such components to use them correctly.

The pattern surely increases the amount of code written and there are many places for improvements. I actually generate code at run-time that deal with the pattern and implement interfaces (you can see it in the article: CTM - Clone To Modify Model), but such approach also has disadvantages, as there is a single interface that looks always modifiable (but the immutable version throws ReadOnlyExceptions on the setters) and also that reduces the advantage of the lock-free reads as virtual calls are required. Another solution to the problem is to generate code from templates before compiling, yet, that's not that easy to integrate with the development environment.

Well... who knows? The event add and remove methods by themselves are a lock-free pattern implemented by the compiler, so maybe we will find an immutable/mutable pattern automatically implemented by some compiler some day (or maybe one already exists and I am not aware of).

Version History

• May, 07, 2013: Added the Validated Types can be a little different than Mutable/Intermediate Types topic
• May, 05, 2013: Initial version