Sunday, May 20, 2007

A Limitation of Super Type Tokens

Watching Josh Bloch's presentation at JavaOne about new topics in the second edition of Effective Java makes me want to go out and get my own copy. Unfortunately, he's not scheduled to have the new edition in print until later this year.

There was a coincidental adjacency between two slides in Josh's talk that made me think a bit more about the idea of Super Type Tokens. The last slide of his discussion of generics gave a complete implementation of the mind-expanding Typesafe Heterogenous Containers (THC) pattern using Super Type Tokens:

import java.lang.reflect.*;

public abstract class TypeRef<T> {
    private final Type type;
    protected TypeRef() {
        ParameterizedType superclass = (ParameterizedType)
            getClass().getGenericSuperclass();
        type = superclass.getActualTypeArguments()[0];
    }
    @Override public boolean equals (Object o) {
        return o instanceof TypeRef &&
            ((TypeRef)o).type.equals(type);
    }
    @Override public int hashCode() {
        return type.hashCode();
    }
}

public class Favorites2 {
    private Map<TypeRef<?>, Object> favorites =
        new HashMap< TypeRef<?> , Object>();
    public <T> void setFavorite(TypeRef<T> type, T thing) {
        favorites.put(type, thing);
    }
    @SuppressWarning("unchecked")
    public <T> T getFavorite(TypeRef<T> type) {
        return (T) favorites.get(type);
    }
    public static void main(String[] args) {
        Favorites2 f = new Favorites2();
        List<String> stooges = Arrays.asList(
            "Larry", "Moe", "Curly");
        f.setFavorite(new TypeRef<List<String>>(){}, stooges);
        List<String> ls = f.getFavorite(
            new TypeRef<List<String>>(){});
    }
}

But on the very next slide, the very first bullet of the summary of his presentation reminds us

  • Don't ignore compiler warnings.

This was referring to Josh's advice earlier in the presentation not to ignore or suppress unchecked compiler warnings without trying to understand them. Ideally, you should only suppress these warnings when you have good reason to believe that the code is type-safe, even though you might not be able to convince the compiler of that fact.

The method Favorites2.getFavorite, above, is annotated to suppress a warning from the compiler. Without that annotation, the compiler complains about the cast to the type T, a type parameter. Is this code demonstrably type safe? Is it possible to cause this cast to fail using code that is otherwise completely type safe? Unfortunately, the cast is not safe:

class Oops {
    static Favorites2 f = new Favorites2();

    static <T> List<T> favoriteList() {
        TypeRef<List<T>> ref = new TypeRef<List<T>>(){};
        List<T> result = f.getFavorite(ref);
        if (result == null) {
            result = new ArrayList<T>();
            f.setFavorite(ref, result);
        }
        return result;
    }

    public static void main(String[] args) {
        List<String> ls = favoriteList();
        List<Integer> li = favoriteList();
        li.add(1);
        for (String s : ls) System.out.println(s);
    }
}

This program compiles without warning, but it exposes the loopole in the type system created by the cast to T in Favorites2.getFavorite. The compiler's warning does, after all, tell us about a weakness in the type safety of the program.

The issue is a subtle one: TypeRef treats two types as the same when the underlying java.lang.reflect.Type objects are equal. A given java.lang.reflect.Type object represents a particular static type appearing in the source, but if it is a type variable it can represent a different dynamic type from one point in the program's execution to another. The program Oops exploits that mismatch.

The Super Type Token pattern can be redeemed by disallowing the use of type variables anywhere in the Type object it stores. That can be enforced at runtime (but not at compile time) in the constructor.

Perhaps a better solution would be to reify generics (i.e., "erase erasure") in the language, making all this nonsense unnecessary.

7 comments:

elizarov said...

Btw, there is a way to reify generics in Java without adding “List<class T>” syntax that you've mentioned in the original reification post. The first [at the most useful] step is to start recording reified types in all generic class instantiations at JVM level and bytecode level. Whenever constructor is invoked, the actual type parameters passed shall be recorded (I'll omit approaches for implementation at JVM level). If raw type is instantiated, then this fact should be recorded too.
Even though it is not 100% satisfactory from type-safety point of view (you still have to allow all the old code to work), it will solve most of practical issues arising from the lack of reification:
1) You will be able to retrieve runtime type arguments of a given Object (i.e. runtime Type and not just runtime Class) with something like Object.getType() method.
2) You will be allowed to write class literals for generic types (the result will be Type for compatibility as you’ve blogged somewhere before) and use them with Type.isInstance method in a useful way.
3) You will be able to instanceof for instantiations of generic types.
4) Serialization can be updated to store/load those actual type parameters for non-raw types.
However, for compatibility reasons, raw types and unchecked casts shall be still allowed. So, you can have a case where variable "v" has a declared generic type, for example, "List<String>", but at the same time "v instanceof List<String>" is false (and it is indeed heap pollution!!!). It will not cause any compatibility problems, though, since you could not write this instanceof in the old code, but it will remove the necessity of having to deal with those unsafe "type token" patterns.
With the above facilities at hand you will be able to write 100% safe implementation of “Favorites” class.

Tom Palmer said...

Reified generics could be nice if done right.

Concerning compiler warnings today: I've _never_ heard of _anyone_ that had common problems with ClassCastExceptions. The gymnastics required to avoid compiler warnings with Java 5 generics are ridiculous. The errors are fine, but the static enforcement at the warning level is clearly incompetent. I find that using generics makes my code easier to read _sometimes_ in that I know what kinds of data I'm working with. But the gymnastics sometimes makes that readability go out the window. I just turn off generics compiler warnings all the way in Eclipse. Makes my life a lot happier. And I still don't get ClassCastExceptions but once in a blue moon.

Anonymous said...

Neal,

Really, instead of starting with "closures" (aka function pointer made to java), why not simply start with real-life genericity implementation into Java ?

I mean, genericity at this time (read with erasure) is cool but usefullness limited, because appart from simplifying the code, it does not bring any runtime value.

As an example, on a List of type T as you can not get the exact runtime generic (parameter) class, you can not work using genericity to perform predefine operations such as : add a new element of same "minimum" type, get all the properties of the collection to display it, ...

We don't need "closure" by now, and not in a way that will break the object oriented programming (current proposition).

But we do need right now runtime genericity to bring next generation of framework that will automatically operate with data according to usual ways. Genericity to generify the code, in other words !

prunge said...

I also believe that reification of generics should be a priority.

The type safety given by compiler checking is fine, but at runtime I feel we have taken a step backwards It is quite possible to have a List<String> hold something other than Strings if there are raw types used anywhere - and as a developer of a single module how am I guaranteed that other modules or third party libraries do the right thing? Certainly not by runtime checking OR compile time checking (unless you recompile all third party libraries from scratch and observe all the compiler warnings).

I have seen it now many times that, especially when forced to deal with non-generified APIs or when having to pull generic types out of a non-typesafe map (e.g. servlet attributes), developers simply use @SuppressWarnings due to frustration in not being able to check whether their collections match the appropriate type which ends up destroying the whole point of generics.

Richard Kennard said...

Just a little niggle to the previous comments: saying that generics 'does not bring any runtime value' is demonstrably false.

Classes, Methods and Fields all maintain their generic information at runtime, and many frameworks couldn't work without this.

For example...

@Entity
class Shop
{
@OneToMany
Set<Fruit> setFruit;
}

...JPA uses generic information at runtime to know that setFruit is a Set of Fruit.

Cow_woC said...

I agree with the comment made by one of the other posters: please work to get Reified Generics into Java before Closures. In my opinion this cleanup is far more important.

James said...

For those wanting reified generics, go vote on the following RFE:

Add reification of generic type parameters to the Java programming language