samskivert: Riddle me this

09 June 2010

I don’t expect anyone to know the answer to this question, but I’m hoping that bitching about it will improve my mood sufficiently to prepare me for the painful foray into the guts of javac that will be needed to find the answer myself.

There’s a very sophisticated pile of code in com.sun.tools.javac.comp.Infer that infers the type of a universally quantified method application, given its signature and actual parameter types. To clarify what that means, let’s look at some code. Suppose you have an interface like the following and a universally quantified method which uses it:

    public static interface Predicate<T> {
        boolean apply (T arg);
    }

    public static <T> Predicate<T> id (Predicate<T> pred) {
        return pred;
    }

    public static final Predicate<Integer> FALSE = new Predicate<Integer>() {
        public boolean apply (Integer arg) {
            return false;
        }
    };

    public static void testId () {
        assert id(FALSE).apply(0) == false;
    }

If you were to put on your magical x-ray glasses and watch the compiler as it processed this code, you’d see at some point a call to Infer.instantiateMethod where it attempted to determine the type of the expression id(FALSE). This call would be told that it has a method of type <T>(Predicate<T>)Predicate<T> (which means we have a method forall T that takes a Predicate<T> and returns a Predicate<T>), and it has a list of type arguments to be inferred, just T, and that the type of the single argument to the method is Predicate<Integer>.

Infer.instantiateMethod is very smart, and it will tell us that this particular expression has type (Predicate<Integer>)Predicate<Integer>. This is just what I would expect.

Now suppose we decide to get fancy, and make our id() method contravariant in its type parameter:

    public static <T> Predicate<T> id (final Predicate<? super T> pred) {
        return new Predicate<T>() {
            public boolean apply (T arg) {
                return pred.apply(arg);
            }
        };
    }

Don’t mind the fact that the body of the method got more complex. That’s invisible to Infer.instantiateMethod, it only sees the type signature. So as far as it’s concerned, the only change is that the Predicate<T> formal parameter type is now Predicate<? super T>.

However, when we put on our x-ray specs, we see some funny behavior from Infer.instantiateMethod. Now instead of typing id(FALSE) as (Predicate<? super Integer>)Predicate<Integer>, which is what I would expect, it types it as (Predicate<? super T>)Predicate<T>. Note that this is not the same as the uninstantiated type of the method which is <T>(Predicate<? super T>)Predicate<T>. It has thrown away the universal quantification and given us back a type that contains free type variables.

So clearly there must be some other magic somewhere in the compiler that can somehow differentiate between a sanely typed method and a bizarrely typed method, and knows what to do with those free type variables. I’m not especially looking forward to tracking that code down and figuring out how it works.

©1999–2015 Michael Bayne