Thursday, June 24, 2010

Abolish the Mutants! .. or do we need Setable and Mapable Interfaces?

No, this is not about a well-known film series. This is about software development! Forgive me for the lurid title :-)

Some weeks ago I was writing about an unexpected behaviour when you use Map.Entry objects in HashSets. The problem was emerging because the code assumed an object to be immutable that was not. More generally, we can ask: What elements can we put into a Set or use as the key of a Map?

In the javadoc to java.util.Map we find following warning:
Note: great care must be exercised if mutable objects are used as map
keys.  The behavior of a map is not specified if the value of an object is
changed in a manner that affects equals comparisons while the
object is a key in the map.
Unfortunately, we usually do not immediately see wheter an object can be changed in such a way or not and therefore are clueless whether we are allowed to use it as the key of a mapping. We need to check the implementation of the class and possible sub-classes. If we are dealing with an interface we would have to check all implementations which is an impossible task as new implementations might be added in the future.

The inventors of the java collection library could have diminished this problem by introducing an interface Setable resp. Mapable which mark whether a class is designed for being put into a set resp. for being the key in a map. Map and Set could then allow only objects implementing these interfaces. However, these interface names are rather cumbersome and as they choose not to do this, we need to find another way of dealing with this issue.

Universum java est omnis divisa in partes tres

If we look at the universe of all java objects we can group them into three distinct sets:
  1. Immutable objects
  2. Entities
  3. Neither 1 nor 2
Immutable objects are objects which never change their internal state. They are created fully-initialized, their hash code never changes and the equality relation formed by their equals method remains the same in their full livetime. They are perfect set members and hash keys!

Entities can change their internal state over time but they have a constant identity-giving property. Every java class which does not override equals and hashCode from java.lang.Object fullfills this requirement: It's identity is given by it's address in memory (which is only accessable to the jvm but nonetheless it is consistently defined). In other cases, the entity's identity is given by some id which might be a final long field or some special guid. The equals and hashCode methods must then be defined on this id only and not on any other fields. This makes entities suitable for sets and maps.

The remaining objects which are neither immutable nor entities can change their identity over time. I will therefore call them mutants for now. We should use them in sets and maps only if we can somehow guarantee that they will never mutate (change their identity) the entire time while they are used in the sets or maps!

Avoid Mutants!

Unfortunately, there are many mutants hiding in the java libraries:
  • java.util.List and all its implementations
  • java.util.Set and all its implementations
  • java.util.Map and all its implementations
  • java.util.BitSet
  • java.util.Date
  • ...
So, what can you do if you want to use a list of elements safely as key to a map, for example?

public class Registry {
  private Map<List<String>, String> map = new HashMap<List<String>, String>();

  public void put(List<String> strings, String value) {
    // oops, unsafe!
    map.put(strings, value);

The list of strings is a potential mutant!

  public void put(List<String> strings, String value) {
    // oops, still unsafe!
    map.put(Collections.unmodifiableList(strings), value);

Wrapping the mutant into an unmodifiable list will still not work as the caller of the method still has a reference to the list and can therefore modify it!

  public void put(List<String> strings, String value) {
    map.put(createImmutableCopy(strings), value);

  private List<String> createImmutableCopy(List<String> strings) {
    return Collections.unmodifiableList(new ArrayList<String>(strings));

We need to both copy the list and put it into a unmodifiable wrapper! Now we can guarantee that this list will never change again because there are no references to the wrapped ArrayList except by the Collections.UnmodifiableList wrapper which guards it from modifications. Note that we have this guarantee only because we know that the list is an direct result from our helper function. If we pass the list to some other method it will have to be treated as potential mutant there again...

As you see, mutants cause a lot of trouble and work to ensure they do not change their identity again. Therefore my demand is cleary: Do not write any mutant classes! By cleverly compositing immutable classes and entitiy classes you can always avoid the danger-bringing mutants.

No comments:

Post a Comment