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[]

Answer 3

Arrays do explicitly remember their type, you can even get it at runtime (array.getClass().getComponentType()).

When storing to an array, the VM will check if the element to be store is assignment compatible with the array's component type. If it isn't, you get ArrayStoreException.

Collections (as ArrayList) do internally declare their backing arrays as Object[], thus they can store anything, even types they are not allowed to store by their generic definition.

Answer 4

3) Whether you do AA a = new AA(); or AA a = new BB();, the compiler does not remember later what you assigned to a, only that its declared type is AA. However, in the latter case, you can in fact assign the value of a to an element of a BB[], so arr2[0] = a; should not give you a runtime exception. Thus, the compiler cannot tell in advance. (Besides, you could try nasty things to change the value of a at runtime between the respective lines...)

2) Had you used List<AA> listAA = listBB;, you would have gotten a compile error. So what you expected from the array example -- compile time detection of an arising impossible assignment -- in fact works with lists! If you leave out the generic type parameter, however, you will get a raw-type list, to which you can assign other lists without reasonable type checks. This is best considered a leftover from early Java, which should be avoided. If you added the following line below you question's code:

BB item = listBB.get(0);

Do you think it should/will compile? Should/will it run (and, if so, what should be its result)?

The how part of 1) probably warrants a separate question.

Answer 5

1. Simply speaking: arrays are a class. BB[] does not extend AA[] even though BB extends AA.
2. In the early days pre-generics. ArrayLists held Objects. so anything could be held in an ArrayList. If you had an Array of Object, you could play the same game. Now with generics you can specify an ArrayList with a specific type like ArrayList<String>.

3. actually the problem is on line 2:

   AA[] arr2=arr;
   

Let's make the problem a little easier. You have a vehicle class and a bike and a car class that extends vehicle. You can not have

Bike b=new Bike()
Car c=b;

arr2 is an array and arr is an array, but the class is different. Does that help?