Iterator Exports Mutability

Wrapping a collection without exporting any modifying methods should make an immutable object. Or not?

Iterator Exports Mutability

I just recognized this hidden trap, and as it is not obvious it seems to be time for a warning: Classes which implement java.util.Iterable, or export internal Iterables are possibly no longer immutable.

Example

In the recent years I tend more and more to make my classes immutable if possible, as a lot of synchronization problems (esp. with multi-threading) are just impossible then, they are also wonderful hash keys (never use mutable objects for that) and have some other nice advantages. Of course being immutable is a big drawback in various scenarios, but probably less often then you might think.

Let’s say I want to implement an immutable cookie jar which displays cookies of different kinds.

It could look like:

import com.sun.istack.internal.NotNull;

import java.util.*;

/**
 * A cookie jar.
 * 
 * Immutable, so everybody can look at the cookies, but nobody can take them away.
 */
public final class CookieJar
        implements Iterable<CookieJar.Cookie>
{
  /** 
   * A cookie.
   * Immutable.
   */
  public static final class Cookie
  {
    @NotNull
    private final String type;

    public Cookie(@NotNull String type)
    {
      this.type = type;
    }

    @NotNull
    public String getType()
    {
      return type;
    }
  }

    
  @NotNull
  private final Set<Cookie> cookies;

  
  public CookieJar(@NotNull Collection<Cookie> cookies)
  {
    this.cookies = new HashSet<>(cookies);
  }
  
  public CookieJar(Cookie ... cookies)
  {
    this(Arrays.asList(cookies));
  }

  @Override
  @NotNull
  public Iterator<Cookie> iterator()
  {
    return cookies.iterator();
  }
}  

Two Basic Rules for Immutable Classes

At first glance everything looks right. I remembered two crucial points:

  • always make immutable classes final
  • always deep copy all in- or outgoing data unless it’s immutable itself

Make Immutable Classes final

All immutable classes should be declared final. Otherwise it is possible to overload them with a new mutable implementation which breaks the immutability promise. In this case I could eg write my own EvilCookie:

public class EvilCookie extends CookieJar.Cookie
{
  public EvilCookie(@NotNull String type)
  {
    super(type);
  }

  @Override
  @NotNull
  public String getType()
  {
    final String myType = super.getType();
    if ("chocolate".equals(myType)  &&  Math.random() < 0.1) {
      return "I hate chocolate!";
    }
    return myType;
  }
}

This one would sometimes return a different type for a certain cookie, which is not exactly the behavior expected from an immutable class. Same could be done for the iterator() method in the CookieJar class.

Basically you can also make all methods final, which would allow to still enhance the immutable class. But as this really means all methods you’d have to remember to also make methods inherited from the base class final (eg hashCode()), which is easily forgotten, initially but especially when you tweak your class hierarchy or introduce new methods in the base class.

Deep Copy All In- and Outgoing Data

Your immutable class will hold some data. If this data is mutable you’ll need to deep copy the data when it enters your class via the constructor and each time when it leaves your class via a getter. Otherwise a malicious (or just stupid) programmer can change internal data of your immutable class, eg when he keeps a reference to the object used as a constructor parameter or just changes the returned object.

Obviously this can become expensive in some cases, so if possible you should avoid mutable objects inside your immutable classes. For exporting collection classes you can use one of the unmodifiableXXX() wrappers from the java.util.Collections utility class, but only if the elements of the collection are immutable!

In the implementation above indeed the incoming collections/arrays are copied, and String is already immutable itself. The internal Set is not accessible from the outside,

So Where’s the Problem?

The problem is hidden in the Iterator returned by the iterator() method. Although in the standard usage of an Iterable class there occurs no possible problem:

   for (CookieJar.Cookie cookie : myCookieJar) {   // hidden usage of myCookieJar.iterator()
     if ("chocolate".equals(cookie.getType())) {
       System.out.println("Yummy!");
     }
   }

there is a way to do harm:

   for (Iterator<CookieJar.Cookie> it = myCookieJar.iterator();
        it.hasNext(); ) {
      if ("chocolate".equals(it.next().getType())) {
        it.remove();
      }  
   }

Yuck, no more yummy chocolate cookies.

Yes, indeed there is a not well-known remove() method in Iterator, allowing to remove elements in the underlying collection. It may throw an UnsupportedOperationException for immutable classes, but in the above example it will work as expected.

Solutions

There are two obvious solutions for this:

  • make your collection unmodifiable
  • make your iterator unmodifiable

Both will only work when the collection elements are immutable. If not you’ll have to deep copy them once during construction and once each time you are giving them away.

Make Your Collection Unmodifiable

This is done during construction. Just make the first constructor look like:

  public CookieJar(@NotNull Collection<Cookie> cookies)
  {
    this.cookies = Collections.unmodifiableSet(new HashSet<>(cookies));
  }

Iterators from such wrapped collection will not allow removal, and if necessary you can even allow a getter which exports the collection itself.

Make Your Iterator Unmodifiable

This is done in the iterator() call. There is no nice convenience method for this, but it is simple enough:

  @Override
  @NotNull
  public Iterator<Cookie> iterator()
  {
    final Iterator<Cookie> it = cookies.iterator();
    return new Iterator<Cookie>()
    {
      @Override
      public boolean hasNext()
      {
        return it.hasNext();
      }

      @Override
      public Cookie next()
      {
        return it.next();  // remember to make a deep copy here when your element type is not immutable
      }

      // The following method code is no longer necessary in Java 8 and later
      // as throwing an UnsupportedException is now the default behavior.
      @Override
      public void remove()
      {
        throw new UnsupportedOperationException("Not modifiable!");
      }
    };
  }

My de·caff Commons provide convenience wrappers for this in the de.caff.generics.Types utility class:

  • the method unmodifiable(Iterator) returns the above unmodifiable Iterator wrapper
  • the method unmodifiable(ListIterator) does the same for a ListIterator

The old Enumeration interface has no need for a wrapper, as it does not provide a remove() method.