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);
}

}