How do arrays "remember" their types in Java?

Question

Consider the following code:

class AA { }  class BB extends AA { }  public class Testing {      public static void main(String[] args) {         BB[] arr = new BB[10];         AA[] arr2 = arr;          BB b = new BB();         AA a = new AA();         arr2[0] = a; // ArrayStoreException at runtime         arr2[1] = b;          List<BB> listBB = new ArrayList<>();         List listAA = listBB;         listAA.add("hello world.txt");      } } 

In the above example, I get the ArrayStoreException when I try arr2[0] = a. That means the array remembers what type it must accept. But the List does not remember them. It simply compiles and runs fine. The ClassCastException will be thrown when I retrieve the object BB.

So the questions are:

1. How an array remembers its type (I know it's called "reification"). How this happens exactly?

2. And why only arrays are bestowed with this power but not ArrayList although it uses an array under its hood.

3. Why can't ArrayStoreException be detected at compile time, i.e when I do arr2[0] = a, it could cause a compiler error, instead of detecting it at runtime.

Thanks.

Answer 1

1. The type information for arrays, unlike for generics, is stored at runtime. This has been part of Java since the beginning of it. At runtime, a AA[] can be distinguished from a BB[], because the JVM knows their types.

2. An ArrayList (and the rest of the Collections framework) uses generics, which is subject to type erasure. At runtime, the generic type parameter is not available, so an ArrayList<BB> is indistinguishable from an ArrayList<AA>; they are both just ArrayLists to the JVM.

3. The compiler only knows that arr2 is a AA[]. If you have a AA[], the compiler can only assume that it can store an AA. The compiler will not detect a type safety issue in that you are placing an AA in what's really a BB[] there, because it only sees the AA[] reference. Unlike generics, Java arrays are covariant, in that a BB[] is an AA[] because a BB is an AA. But that introduces the possibility of what you just demonstrated - an ArrayStoreException, because the object referred to by arr2 is really a BB[], which will not handle an AA as an element.

Answer 2

1. Each time a value is stored into an array, the compiler inserts a check. Then at run-time it validates the type of the value is equal to the run-time type of the array.

2. Generics were introduced. Generics are invariant and can be verified at compile time. (At run-time the generic types are erased).

3. Here is an example of the failing case (from wikipedia):

// a is a single-element array of String String[] a = new String[1];  // b is an array of Object Object[] b = a;  // Assign an Integer to b. This would be possible if b really were // an array of Object, but since it really is an array of String, // we will get a java.lang.ArrayStoreException. b[0] = 1; 

The compiler cannot detect that the third statement will result in an ArrayStoreException. With regard to the third statement, the compiler sees that we are adding an Integer to an Object[] array. This is perfectly legal.

Background / Reasoning (from wikipedia)

Early versions of Java and C# did not include generics (a.k.a. parametric polymorphism). In such a setting, making arrays invariant rules out useful polymorphic programs. For example, consider writing a function to shuffle an array, or a function that tests two arrays for equality using the Object.equals method on the elements. The implementation does not depend on the exact type of element stored in the array, so it should be possible to write a single function that works on all types of arrays. It is easy to implement functions of type

boolean equalArrays (Object[] a1, Object[] a2); void shuffleArray(Object[] a); 

However, if array types were treated as invariant, it would only be possible to call these functions on an array of exactly the type Object[]. One could not, for example, shuffle an array of strings.

Therefore, both Java and C# treat array types covariantly. For instance, in C# string[] is a subtype of object[], and in Java String[] is a subtype of Object[]