Subclassing and Java Generics, revisited

Posted on November 3, 2010 by Tommy McGuire

Labels: software development, notation, java, programming language

Last summer, I wrote a post working through the relationship between subtyping and generics in Java. Unfortunately, I never really related my conclusions to Java as it is spoken in the wild. The topic came up again, and once again I not only could not remember the ideas, I couldn't even remember the words.

Specifically, the problem started with an attempt to create a Map whose values were themselves Maps.

Map<String, Map<String,String>> map = new HashMap<String, HashMap<String,String>>();

(The red highlighted code will not compile and shows the cute little red underline in Eclipse.)

The question became one of generics and subtyping with the following attempt to fix the error, which appears to work but just pushes the error down to the use of the map.

Map<String, ? extends Map<String,String>> map = new HashMap<String, HashMap<String,String>>();
map.put("one", new HashMap<String, String>());

The problem there, I think, is that the Java compiler believes the values of map to be some-anonymous-but-concrete subtype of Map<String,String>, and sees the call to put() as an attempt to insert a HashMap<String,String> into a position requiring some-anonymous-but-concrete subtype of Map<String,String>, which does not match HashMap<String,String>. Or something like that.

The ultimate fix is to un-typo the HashMap constructor call in the original assignment to map, leaving the values of the map to be generic Map<String,String>'s rather than specific HashMaps.

Map<String, Map<String,String>> map = new HashMap<String, Map<String,String>>();
map.put("one", new HashMap<String, String>());

Class structure

Anyway, my purpose here is to recreate my table of what works and what does not using actual Java code rather than the pseudo-Java examples of my previous post. The class structure I need to work with is:

public class A { }
public class B extends A { }
public class C extends A { }

To briefly recap my previous post, given those class definitions where B is a subtype of A (or, B <: A),

List can be used as a subtype of List<A> (or List <: List<A>), which is described as a covariant use,
List<A> can be used as a subtype of List (or List<A> <: List), which is described as a contravariant use, or
List<A> and List can be entirely unrelated and cannot be interchanged, which is described as invariant.

The two important variations are covariance and contravariance (in C++ with templates, as far as I know, generics are treated as invariant, which is entirely reasonable if somewhat less featuriferous).

Whether covariance or contravariance works depends on how the subtype relationship is being used. Now, by "works" I mean "is guaranteed not to result in runtime errors". Further, by "how the subtype relationship is being used", I mean "whether information is being inserted or extracted from the generic type".

The following table shows the four possibilities, with resulting errors. (I have highlighted the extends/super keywords to show the relationship with covariance and contravariance.) Each quadrant of the table contains two methods. The first, top method has a generically typed, covariant- or contravariant-use parameter, which potentially shows a compile-time error. The second, bottom, method shows code that uses the top method to either insert or extract an element from a List.

	Covariant	Contravariant
Extraction	public A covExtInner(List<? extends A> as) { return as.get(0); } public void covariantExtraction() { List<B> bs = new ArrayList<B>(); bs.add(new B()); A a = covExtInner(bs); }	public B conExtInner(List<? super B> bs) { return bs.get(0); } public void contravariantExtraction() { List<A> as = new ArrayList<A>(); as.add(new A()); B b = conExtInner(as); }
Insertion	public void covInsInner(List<? extends A> as, A a) { as.add(a); } public void covariantInsertion() { List<B> bs = new ArrayList<B>(); A a = new A(); covInsInner(bs, a); }	public void conInsInner(List<? super B> bs, B b) { bs.add(b); } public void contravariantInsertion() { List<A> as = new ArrayList<A>(); B b = new B(); conInsInner(as, b); }

Covariant

Contravariant

Extraction

public A covExtInner(List<? extends A> as) {
    return as.get(0);
  }
  
  public void covariantExtraction() {
    List<B> bs = new ArrayList<B>();
    bs.add(new B());
    
    A a = covExtInner(bs);
  }

public B conExtInner(List<? super B> bs) {
    return bs.get(0);
  }
  
  public void contravariantExtraction() {
    List<A> as = new ArrayList<A>();
    as.add(new A());
    
    B b = conExtInner(as);
  }

Insertion

public void covInsInner(List<? extends A> as, A a) {
    as.add(a);
  }
  
  public void covariantInsertion() {
    List<B> bs = new ArrayList<B>();
    A a = new A();
    
    covInsInner(bs, a);
  }

public void conInsInner(List<? super B> bs, B b) {
    bs.add(b);
  }
  
  public void contravariantInsertion() {
    List<A> as = new ArrayList<A>();
    B b = new B();
    
    conInsInner(as, b);
  }

Valid operations

The upper left and lower right quadrants show valid operations, which are guaranteed not to result in runtime errors and which therefore do not generate compile-time errors.

Covariant extraction

The upper left quadrant shows a List of B's passed to a method which retrieves an element as an instance of A and returns it. Simple and working.

Contravariant insertion

The lower right quadrant shows a List of A's and a B passed to a method that treats the list as if it were a List of some superclass of B, and adds the B instance to it. Once again, works fine.

Invalid operations

The upper right and lower left quadrants show problematic operations, which could potentially cause errors at runtime. The compile-time error is shown in red.

Covariant insertion

The lower left quadrant shows an attempt to write a method with a covariant use which attempts to insert an element. The compiler generates an error on the call to add().

Consider what would happen if the compiler did not flag the call to add(): the method covInsInner would be able to insert any A into the as list; rather than an A, it could insert a C or any other subtype of A. However, the covariantInsertion method that called covInsInner is using a List of B's, and the insertion of anything that is not a B corrupts the list.

Java chooses to flag the call to add() as the error, rather than, say, the call to covInsInner, because the call to covInsInner looks correct: bs is a List of something that extends A. The error arises with the call to add() because as is passed as covariant; the "? extends ..." syntax does not modify A, but rather indicates that the List can be used in a covariant manner. And the call to add() is not a covariant usage.

Contravariant extraction

The upper right quadrant shows an attempt to write a method with a contravariant use which attempts to extract an element. The compiler generates an error on the call to get().

Consider what could happen if the compiler did not flag the call to add(): The conExtInner method could extract a B object from a list of A objects, resulting in a class cast error at runtime.

Java again chooses to flag the call to get() because the type "List<? super B>" marks the List bs as a contravariant usage, and get() is not allowed by that usage.

The bottom line

The syntax "? extends A" marks the type as a covariant usage, allowing collections of subtypes of A to be assigned, but only allowing extraction. The "? super B" syntax marks the type as a contravariant usage, allowing collections of supertypes of B to be assigned, but only allowing insertion. Or, as Naftalin and Wadler put it in Java Generics,

The Get and Put Principle: use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when you both get and put.

Or, more succintly, extends = covariant = read-only and super = contravariant = write-only.

[Edit] Del just reminded me of a key point: The covariant and contravariant markers might appear to modify the type argument to the generic, but they do not. The type List<? extends ...> controls the usage of the List; it does not affect the contents of the list.