The goal of a programming language’s type system is to provide guarantees about what types can be encountered at certain points in your program; to document the values we expect to see in a way that the compiler can verify. But Java’s type system has holes, the guarantees can be broken. Some of these holes are deliberate, mostly for backward compatibility. For example using raw types or unchecked casts you can cause heap pollution. Heap pollution means that the content of a parameterized type does not match its type.
1 2 3 4 5 6 | List<String> stringList = new ArrayList<>();List list = stringList;// compiler warning: unchecked call to add(E) as a member of the raw type java.util.Listlist.add(1);// throws java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.StringString s = stringList.get(0); |
These come with compiler warnings, so you know you’re leaving the safety of the type system when you use them.
Here’s the story of what I found looking for constructs that the compiler and/or specification claim are safe, do not generate warnings, but cause heap pollution, leading to a ClassCastException where there is no explicit cast.
The examples here were tested with JDK 10, but most of them work (sometimes with small changes) in older versions too.
About wildcards and capture conversion
First, a quick introduction into my mental model of wildcards and capture conversion. Take a variable defined as List<?> a. You can assign Lists of any type to it, but when you take its value, you have a List of a concrete unknown type. The expression a has as type the capture conversion of List<?>, which is a non-denotable type: a type that cannot be expressed in the Java language, but is commonly written as List<capture of ?>. Capture conversion replaces every top-level type argument that is a wildcard with a capture of that wildcard; e.g. the capture conversion of Map<List<?>, ?> is Map<List<?>, capture of ?>.
To help understand the difference between a wildcard and a captured type: a List<List<?>> is a List to which you can add any other type of List; it can e.g. contain a List<String> and a List<Integer>. A List<List<capture of ?>> contains Lists of an unknown type, and all those Lists have the same unknown type.
Capture conversion is applied by the compiler to the type of every expression, and produces a unique type every time it is applied. That leads to counter-intuitive restrictions such as adding an element of a list in the same list (a.add(a.get(0))) not being considered type-safe. The capture of ? in the type of the first a is not the same as the second a. That makes sense if you consider that the value of a might have changed between the a.get and the a.add calls.
A capture type represents the specific type for a wildcard in a single execution of a single expression. But an expression in a program only has one type, and can be executed multiple times, e.g in a for-loop. So how can that type represent only a single execution? The trick is that capture types only exist in the scope of a single expression; their scope is so narrow that within that scope the expression can only be executed once. A capture type cannot escape outside the body of the for-loop in which it is created, because that would require having a variable of the capture type, and there isn’t any way to express such a variable in the Java syntax.
Or can it?…
Lambda expressions are broken
For capture types to represent the type of a single execution of an expression, the assumption is made that within an expression (the scope of the capture type) every sub-expression (that can reference the capture type) is only executed once. That assumption might have been correct when this was introduced in Java 5, but not anymore. A lambda expression is a sub-expression that can be evaluated multiple times within the same expression. That’s quite a fundamental problem. To make this sound important we could say lambdas make Java’s type system unsound.
Take this example:
1 2 3 4 5 | List<String> stringList = new ArrayList<>();Stream.of(stringList, Arrays.asList(1)) .map(list -> list) .reduce((list1, list2) -> {list1.addAll(list2); return list1;});String v = stringList.get(0); // ClassCastException |
Here, different instances of a wildcard type are squeezed through the same captured type, and then made to interact with each other. The Stream.of creates a Stream<List<?>>, a stream of lists each of an unknown type. Then in the seemingly redundant map step that List<?> type is capture converted to List<capture of ?>. That incorrectly turns it into a Stream<List<capture of ?>>, meaning a stream of lists all of the same type. The reduce step then abuses that to move elements from the List<Integer> into the List<String>, breaking the type system.
Local inner classes are broken
That lambdas problem got me thinking: Are there other kinds of types that are only visible in a limited scope, for a single execution, but could creep out of that scope? Well, local inner classes (classes declared inside of a method) have limited scope. And if it is a generic method, then we also get a type variable that’s assumed to only represent a type for one execution of that method. A problem exploiting that is that you can only have one execution of the method in scope at a time, and if it moves out of scope we lose the type information. But unlike capture types these types have names, so we can restore the type information with a cast.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | Object prev;<T> T go(T t) { class A extends ArrayList<T> { } if (prev == null) { // first execution A a = new A(); a.add(t); prev = a; return null; } else { // second execution return ((A) prev).get(0); }}go(1);String s = go(""); // ClassCastException |
You can argue it’s the cast in there is what indirectly leads to the ClassCastException. But note that checked (not unchecked) casts are supposed to be safe: they should either succeed when the runtime value has the right type, or fail immediately. Checked casts causing heap pollution are a type system loophole. Just in case you’re not convinced, we can do this without an explicit cast, by instead throwing the value straight from one invocation of the method into another.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | <T> T go(T in, Object other) { class A extends RuntimeException { T t; } if (other != null) { // first execution try { go(other, null); } catch (A a) { return a.t; // returns other } throw new AssertionError(); // unreachable } else { A a = new A(); a.t = in; throw a; }}String s = go("", 1); // ClassCastException |
Note that inner classes nested in generic classes, on the other hand, are treated like generic types. That means casts to them are unchecked, and they cannot extend Throwable. It’s an oversight that the same wasn’t done for local classes in generic methods.
Inner classes in generic classes are broken
There’s another problem with anonymous inner classes extending inner classes nested in generic classes when the outer instance has a wildcard in its type. Whew, that’s a mouthful. It creates a class whose supertype has a capture type as type parameter. That’s as if you could write class MyList extends ArrayList<capture of ?>. That’s just nonsense.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | // generic class with inner classclass Box<A> { A a; Box(A a) { this.a = a; } class Inner { void setA(A newA) { a = newA; } A getA() { return a; } }}Object prev;Box<String> stringBox = new Box<>("1");// box is the outer instance, with a wildcard typefor (Box<?> box : List.of(stringBox, new Box<>(1))) { // the anonymous inner class, with the weird supertype box.new Inner() {{ if (prev == null) prev = this; else this.getClass().cast(prev).setA(this.getA()); }};}String s = stringBox.a; // ClassCastException |
There are more problems with such a class: the class file format has no way to properly represent its generic type signature. If we try to access that type using ((Box<?>)stringBox).new Inner(){}.getClass().getGenericSuperclass(), we get a java.lang.reflect.GenericSignatureFormatError. The type system just isn’t equipped to deal with this construct.
Type variable bound checking is broken
Ever since generics were introduced, there have been problems with where exactly capture conversion should be applied. The situation has definitely improved since Java 5, but it didn’t take long for me to stumble upon this problem still persisting in Java 10.
Take a class defined as class Grid<T> extends ArrayList<List<T>>. If you naively fill in the type variable T with the type argument, then it looks like a Grid<?> is a subtype of List<List<?>>. But that’s not right: in a Grid<?> every cell has the same type, while in a List<List<?>> different rows can have different types of cells. Capture conversion is supposed to solve that problem. But outside of expressions, for example in the bounds on type variables, it’s not applied consistently. So Java allows us to define this inconsistent class hierarchy:
1 2 3 4 5 6 7 8 9 10 | class Grid<T> extends ArrayList<List<T>> {}class Wrapper<T extends List<List<?>>> extends ArrayList<T> {}// the definition of this class should not have been legalclass GridWrapper<T extends Grid<?>> extends Wrapper<T> {}GridWrapper<Grid<String>> gridWrapper = new GridWrapper<>();gridWrapper.add(new Grid<>());Wrapper<?> wrapper = gridWrapper;wrapper.get(0).add(List.of(1));String s = gridWrapper.get(0).get(0).get(0); // ClassCastException |
Outer type variables as bound of inner classes are broken
First some background on bounds of capture types. When capture conversion creates a capture type out of a wildcard, it includes the bounds on the type variable also as a bound (supertype) of that capture type. For example, if you’d declare a class Foo<T extends Number> {}, then the capture conversion of Foo<?> is Foo<capture of ?>, where that capture has Number as bound. The bound of the capture type is not always the same as the bound on the type variable. For example in class Bar<T, S extends T> the capture type for the wildcard in Bar<String, ?> does not have T as bound, but is replaced with its value, String. So far so good.
This goes wrong when the bound on a type variable refers to a type variable of an outer class. Then the type variable replacement doesn’t seem to happen.
1 2 3 4 5 6 7 8 9 10 11 | class Outer<P> { class MyList<I extends P> extends ArrayList<I> { MyList(I i) {add(i);} } P getIt(Outer<?>.MyList<?> myList) { return myList.get(0); // this should not be valid }}// ClassCastExceptionString s = new Outer<String>().getIt( new Outer<Integer>().new MyList<Integer>(1)); |
In this example myList is a MyList<capture of ?>, where P is an upper bound of that capture. That’s a different P than the one that happens to be in scope there, causing the mixup.
Honorable mention 1: Unboxing in lambdas is broken
Looking for constructs that throw unexpected ClassCastExceptions lead me to this weird one. This does not qualify as a type system loophole, but oh compiler, what were you thinking?
1 2 | List.of('x', 'y').stream() .max((a, b) -> {return List.of(a).get(0);}); |
The lambda expression given to max is a Comparator, which is supposed to return an int. In this example it indirectly returns a Character, which is supposed to be unboxed to char and then converted to int. Something goes wrong in there, leading to a ClassCastException for casting a Character to an Integer.
Honorable mention 2: TreeSet is broken
It’s not just the type system that has problems, the standard library isn’t entirely type-safe either. Today’s shortest participant in our show of unexpected ClassCastExceptions:
1 | new TreeSet<>(){{add(1);add("");}}; |
That one is disqualified as a flaw because the TreeSet.add javadoc specifically says that it “throws ClassCastException if the specified object cannot be compared with the elements currently in this set”. But the implementation of that relies on an unchecked cast that can lead to heap pollution elsewhere:
1 2 3 4 5 6 | List<String> stringList = new ArrayList<>();TreeSet<List<String>> set = new TreeSet<>( (a, b) -> {b.addAll(a); return 0;});set.add(stringList);set.remove(List.of(0));String s = stringList.get(0); // ClassCastException |
It’s always been broken
Googling around (after I wrote the above) shows me that Capture variables should not escape lambda bodies was known since 2016 (but with a more complicated setup). And incorrect treatment of wildcards in subtyping looks pretty similar to my type variable bound checking problem. And maybe some of the other problems here aren’t new either.
Talking about known problems, I must also mention the “Java is Unsound” post (and paper). That was a great find, interesting read. But I have a different view on these things: None of this comes close to impacting security. And that’s not just by luck. Heap pollution was a deliberate compromise in the type system. Java’s generics have always been known to be too fragile to fully trust. Many problems in it have been popping up ever since it was introduced (and most of those were fixed over time).
Oh no, what do we do?
The Java type system is full of loopholes. Some are deliberate, some are accidental. The difference is that some generate compiler warnings, and some do not. The kind of compiler warnings that most programmers ignore or suppress, without giving it much thought. In practice any sufficiently large Java program makes use of the deliberate loopholes in unsafe ways; because it’s the most practical thing to do. That includes the Java collections library. It’s unlikely you’ll run into the accidental loopholes of this post by accident. That doesn’t mean we should throw our hands in the air and stop trying to make it better. Java’s type system has taken a beating by the desire for backward compatibility and the interaction of its growing list of features. It needs some love to get it back in shape.
Everything is broken. Everything is fine.
[Update: Opened new JDK bugs: JDK-8203335, JDK-8203337, JDK-8203338 and JDK-8203340]
For comments on this, see https://news.ycombinator.com/item?id=17565652