Tuesday, February 13, 2007

Java generics and the covariance and contravariance of arguments

Well given we require 1.5 now for other reasons, and 1.5 does complain if you don't constrain generic classes I have finally bitten the bullet and started using generics. Unfortunately I just got bitten by what I suspect is going to be a very common mistake - in this case by failing to properly consider the type equivalence of parametrised method calls.

Consider the following code:

public interface TestInterface { }

public class TestClass implements TestInterface { }

import java.util.ArrayList;
import java.util.List;

public class Test {
 private List<testclass> list;

 public TestInterface test() {
   list = new ArrayList<testclass>();
   list.add(new TestClass());

   return covariant(list);
 }

 public TestInterface covariant(List<testinterface> ilist) {
   return ilist.remove(0);
 }
}
Now there is absolutely no reason why this should not work. It is trivially inferable that the above code treats ilist as covariant in the list-type - and that therefore this code is statically correct.

Of course Java's typing has never been particularly smart. List<t1>.add(T1) is contra-variant in t1, and T2 List<t2>.get(int) is co-variant in t2; so the Java compiler is correct to infer that in the general case List<t1> and List<t2> are substitutable iff t1 == t2.

If we can't declare a generic parameter to be covariant in its type parameter we have a serious problem - it means that any non-trivial algorithm involving collections is going to run afoul of this. You might consider trying to cast your way around it:

 public TestInterface test() {
   list = new ArrayList<testclass>();
   list.add(new TestClass());

   return covariant((List<testinterface>)list);
 }
but not surprisingly that didn't work.
Test.java:11: inconvertible types
found   : java.util.List<testclass>
required: java.util.List<testinterface>
 return convariant((List<testinterface>)list);
                                       ^
1 error
If you continue to hack at it you might try a double cast via a non-generic List.
 public TestInterface test() {
   list = new ArrayList<testclass>();
   list.add(new TestClass());

   return covariant((List<testinterface>)((List)list));
 }
This works but leaves us with the unchecked/unsafe operation warning:
Note: Test.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
Now this is a perfectly reasonable warning - it is unchecked; it is unsafe; and more importantly it does violate encapsulation. The problem here is that the caller should not be defining the type invariants of the callee - that's the job of the method signature!

The correct solution is to allow us to declare covariant() to be covariant in its argument; and fortunately Java does support this.

To declare an argument to be covariant in its type parameter you can use the extends keyword:

 public TestInterface covariant(List<? extends TestInterface> ilist) {
   return ilist.remove(0);
 }
To declare an argument to be contravariant in its type parameter you use the super keyword:
 public void contravariant(List<? super TestClass> clist, TestClass c) {
   clist.add(c);
 }
Without these two facilities generics would be badly broken, so I am glad Sun had the presence of mind to include them - btw if you are using Java 1.5 I strongly recommend you read the Java Generics Tutorial

As an aside it is worth noting that as Java includes a Top type 'Object', List is a common covariant type - sufficiently common that Sun has included a syntactic sugar for it, List. Personally I'm not sure this was such a good idea, List would work anyway, and I think I would prefer to have kept the covariance explicit.

Update: Corrected capitalisation error in initial java example.

No comments: