I Can Has Invariant Mapz?

July 29, 2010

If I had to pick one of the major source of bugs in large refactorings I recently went through, it would probably be the bunch of methods in the java.util.Map interface which are contravariant on the key type. For instance, one can retrieve an element from a map using a supertype of its key type thanks to signature of #get(Object).

Map<Integer, String> map = newHashMap();
assertNull(map.get("im in ur programmz, codin in ur dialect"));

Now, I do understand that #get(K), #remove(K) and #containsKey(K) are indeed contravariant on K. After all, one can see these methods as functions from K to V, V and boolean, respectively, where K is the type of the keys and V the type of the values; and functions are contravariant on their argument types in Java. In other words, the function #get(Object) can be used wherever the function #get(Integer) is needed, as Object is a supertype of Integer. (Note that Map<K, V> itself is not contravariant on K, as there is a covariant occurrence of K in #keySet().)

However, I’ve never seen any code taking advantage of this property in practice. On the other hand, refactorings from Map<A, V> to Map<B, V> where the least common supertype of A and B is Object tend to lead to tricky bugs as the compiler cannot catch invocations of #get(Object), #remove(Object) or #containsKey(Object) that haven’t been modified, as exemplified by the second snippet below:

void doSomething(Map<Symbol, Quote> cache) {
  ...
  cache.get(symbol);
  ...
}

void doSomething(Map<Isin, Quote> cache) {
  ...
  cache.get(symbol);
  ...
}

Caches implemented using a ForwardingMap with expiring entries I encountered in recent refactorings were particularly error prone as they tend to be used in a lot of places. Breaking cache invalidation due to an incorrect use of #remove(Object) might have catastrophic consequences. You better have a good test coverage, as it is your only safety net.

To overcome this problem, I am now advocating against leaking maps out of
small, controlled scopes. As a replacement, one should either use a custom invariant interface such as

public interface QuoteCache {
  Quote get(Symbol symbol);
}

or wrap the map in the following interface:

public interface InvariantMap<K, V> {
  void clear();
  boolean containsKey(K key);
  boolean containsValue(Object value);
  Set<Entry<K, V>> entrySet();
  V get(K key);
  boolean isEmpty();
  Set<K> keySet();
  V put(K key, V value);
  void putAll(Map<? extends K, ? extends V> m);
  V remove(K key);
  int size();
  Collection<V> values();
}

Given a simple DelegatingInvariantMap implementation, the following factory is pretty useful:

public class InvariantMaps {

  public static <K, V> InvariantMap<K, V> newHashMap() {
    return delegate(new HashMap<K, V>());
  }

  public static <K extends Comparable<? super K>, V> InvariantMap<K, V> newTreeMap() {
    return delegate(new TreeMap<K, V>());
  }

  public static <K, V> InvariantMap<K, V> newTreeMap(Comparator<? super K> comparator) {
    return delegate(new TreeMap<K, V>(comparator));
  }

  public static <K, V> InvariantMap<K, V> delegate(Map<K, V> delegate) {
    return new DelegatingInvariantMap<K, V>(delegate);
  }

}