- A Concurrent Affair - https://www.concurrentaffair.org -

Java Generics Unsound?

Just a few days ago, I complained about the fact that erasure made it impossible to throw generified exceptions [1] in Java. That’s an inconvenience, but two students at the University of Tokyo and Tsukuba University have run into a real problem with erasure and the current Java compiler [2] (Moez found this on the Types-list [3]).

Dear all,

Hiromasa Kido, an undergraduate student in the University of Tokyo,
has found the problem below in the implementation of generics in Java.
Another student, Kouta Mizushima, in Tsukuba University, reported
that it also reproduces in Eclipse (which has its own compiler).

----------------------------------------------------------------------
C:\WINDOWS\Temp>c:\progra~1\java\jdk1.6.0\bin\java -version
java version "1.6.0-rc"
Java(TM) SE Runtime Environment (build 1.6.0-rc-b100)
Java HotSpot(TM) Client VM (build 1.6.0-rc-b100, mixed mode, sharing)

C:\WINDOWS\Temp>type B.java
1
2
3
4
5
6
7
8
9
class A{
       public int compareTo(Object [4] o){ return 0; }
}
class B extends A implements Comparable<B>{
       public int compareTo(B b){ return 0; }
       public static void main(String [5][] argv){
               System [6].out.println(new B().compareTo(new Object [4]()));
       }
}
C:\WINDOWS\Temp>c:\progra~1\java\jdk1.6.0\bin\javac -Xlint B.java

C:\WINDOWS\Temp>c:\progra~1\java\jdk1.6.0\bin\java B
Exception in thread "main" java.lang.ClassCastException:
  java.lang.Object cannot be cast to B
        at B.compareTo(B.java:7)
        at B.main(B.java:13)

C:\WINDOWS\Temp>
----------------------------------------------------------------------

Here is my understanding (confirmed by Atsushi Igarashi) of the
problem: after erasure (i.e., replacing every type variable with the
Object class), an auxiliary method (called bridged method) like

1
2
3
  public int compareTo(Object [4] x){
    return compareTo((B)x);
  }

is created by the compiler in class B. However, this additional
method happens to override A.compareTo and raises an unexpected
ClassCastException.

We have already submitted a bug report to Sun. My question is: Is this a bug in the compiler, or in the design of the language? On one hand, it is a compiler bug because the bridge method, inserted by the compiler, is doing the harm. On the other hand, it would be hard for any compilers to implement generic interfaces without bridge methods (unless we modify the present JVM). In my understading, such overriding as above is not forbidden in the current language specification (page 227 and page 478 perhaps).

Does any expert in this list have a word on this matter…?

Thanks in advance,

Eijiro Sumii
http://www.kb.ecei.tohoku.ac.jp/~sumii/

(quoted with permission)

In my opinion, it is both a bug in the compiler and a result of the design of the language:

Primarily, this is a bug in the compiler. When the erased version of a method overrides another method that is different — they have different signatures! — the compiler should not allow it. Because of the bridge method, which through erasure gets the same signature as
the original method in the superclass and therefore overrides it, delegates to method in the subclass (and performs the required type cast in the process), Java essentially abandons nominal subtyping here and creates a kind of structural subtyping between the methods that were originally unrelated. Structural subtyping doesn’t even exist in Java! (Update: I have realized that it’s not really structural subtyping, but it has its appeal to me. The two methods are forced into a subtyping relationship just because of the way “they fall into place”, and in structural subtyping, one type is a subtype of another if “things just fall into place” right. The Java subtyping has definitely changed, and it appears as if by accident the compiler attempts to do something like structural subtyping — produced by the name clash — and fails).

Via the bridge method, there now is a structural subtyping relationship between the two methods int A.compareTo(Object o) and int
B.compareTo(B b)
. With structural subtyping, as with any subtyping relation, the parameter types need to be contravariant, and here they clearly are not. B is a subclass of A, so the parameter of B‘s method should be a superclass of the parameter of A‘s method, but the exact opposite is the case.

This is a really interesting problem, because it is not only a bug or an oversight in the compiler, it is not only a problem with the language design and erasure, it completely changes the subtyping relation for Java!

The Java compiler must recognize this result of creating the bridge
method and generate a compiler error, much like in the following example, where return types of the same method foo (and because of the resulting structural subtyping behavior, B‘s methods in Hiromasa’s example is overriding A‘s method!) in two classes in a nominal superclass-subclass, A and B, relationshipare not covariant:

1
2
3
4
5
6
7
8
class A{
 public Integer [7] foo() { return 0; }
}
class B extends A {
 // Error: foo() in B cannot override foo() in A;
 // attempting to use incompatible return type
 public Object [4] foo() { return null; }
}

Just as much as the compiler should have recognized the result of creating the bridge method, the language design using erasure is at fault. There is no obvious reason except for Java’s method lookup mechanism why Hiromasa’s code should generate a compiler error or a ClassCastException. Under normal circumstances, methods are allowed to
be overloaded, as this example demonstrates:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class A{
 public void bar(Object [4] o) {
   System [6].out.println("A");
 }
}
class B extends A {
 public void bar(B b) {
   System [6].out.println("B");
 }
 public static void main(String [5][] argv){
   A a = new A(); B b = new B();
   a.bar(a); // A
   a.bar(b); // A
   b.bar(a); // A
   b.bar(b); // B
 }
}

Erasure has forced Sun to do all sorts of compromises and — as this case demonstrates — create strange corner cases that should work but don’t. Just a few days ago, I discovered that generic classes cannot extend (or rather implement, but the compiler error message says “extend”) Throwable. Java’s erasure makes it impossible to throw generified exceptions! After erasure, it’s not possible anymore to distinguish a MyException<T1> from a MyException<T1>.

I must admit that a couple of years ago, I couldn’t quite understand what was so bad about erasure. First-class genericity is cool, sure, but generics with erasure worked, right? No. I’m finding out more and more often that they don’t.

[8] [9]Share [10]