Type Checking

For Bytecode instructions checkcast and instanceof the type must be checked during runtime. Two cases must be considered: checking for an array class or checking for a regular class. Checking for interfaces is discussed below.
Since the dynamic type of an object cannot be known the type checking for any type must work properly. The following table shows all possible casses. ClassA is a regular class, [S is an array of base type (here array of short) and [ClassA is an array of ClassA.

	check for ClassA	check for [S	check for [ClassA
Object is of type ClassA	1. ref != null, read tag 2. array bit is 0 3. check type (see type checking for regular class) returns true	1. ref != null, read tag 2. array bit is 0 returns false	1. ref != null, read tag 2. array bit is 0 returns false
Object is of type [S	1. ref != null, read tag 2. array bit is 1 returns false	1. ref != null, read tag lesen 2. array bit is 1 3. tag = type desc. of [S returns true	1. ref != null, read tag 2. array bit is 1 3. check dimension 4. component type = 0 returns false
Object is of type [ClassA	1. ref != null, read tag 2. array bit is 1 returns false	1. ref != null, read tag 2. array bit is 1 3. tag = type desc. of [S returns false	1. ref != null, read tag 2. array bit is 1 3. check dimension 4. component type != 0 5. get component type from type desc. 6. check for type returns true

If the object is of type [ClassA and is checked for type [IA (while ClassA implements interface IA), the check must return true. This is ok because under point 6. of the last case the type check will get the type descriptor of ClassA which contains IA. Further details can be found further down in Type Check for Interface Type.
The opposite case must work as well. An object is of type [IA and is checked against [IA or one of its superinterfaces. In 6. there is a check against the interface type. If the object is of type [IA and is checked against [ClassA then this check will be in 6. For this reason, the type descriptors of the interfaces must contain the base classes, similar to the type descriptors of the standard classes. With interfaces this is simply the class Object. All other entries must be empty (see below Type Checking for Regular Class).
Hint: As soon as there is a type check against an array of interfaces, a type descriptor for this interface must be created. On the other hand, if the object at runtime is of type array of standard class, then the interface descriptor won't be used. It will be used solely in case when the type at runtime is itself of type array of interfaces.

When you check against Object, the result must be true if the object is an array (of any type).
A check against an array of Object leads to two cases:

1. The reference points to an array of regular classes: the check returns true if the dimension (of the type to check against) is lower or equal than the actual dimension.
2. The reference points to an array of base types: the check returns true if the dimension (of the type to check against) is lower than the actual dimension.

All the explanations above were for instanceof. For checkcast there are some modifications:

1. The check against Object is never necessary. It will be eliminated already in the Bytecode.
2. A failing check has to cause an exception.
3. A null reference results in a positive check.

Both instructions checkcast and instanceof fetch an object reference from the operand stack. The type to check against is referenced in the constant pool. The check runs as follows:

1. read tag of objectref (contains address of actual type descriptor)
2. the base class to check against must be present in the type descriptor. For this purpose the compiler calculates the offset of this class in the type descriptor.
3. this address must be identical with the address of the type descriptor of the actual object.

The type descriptor of a class is constructed as follows: the base class 0 is always Object. The entry contains the address of the type descriptor of Object. This entry is followed by the other superclasses. The address of the own class is entered as the last entry. All derived classes must have the same order for the base classes. The example below shows the execution of a type check.

Example of a type check

For the java code

ClassA1 o = new ClassA20();
((ClassA20)o).m1();

the compiler calculates the offset in the type descriptor of the class ClassA20 to be 2, because ClassA20 is the second extension of Object. The reference o points to an instance of ClassA20 at runtime. Accordingly, the address of ClassA20 will be retrieved from the type descriptor and compared to ClassA20. The type check will return true.

ClassA1 o = new ClassA3();
((ClassA20)o).m1();

In this case the compiler will determine the offset to be 2. The reference points to ClassA3 at runtime. With offset 2 the address of ClassA20 will be fetched and the check is successful.

ClassA1 o = new ClassA21();
((ClassA20)o).m1();

Here again, the compiler calculates the offset to be 2. However, the reference points to ClassA21. With offset 2 the address of ClassA21 will be fetched and compared to ClassA20. The check must return false.

All the type descriptors must have the same number of entries. All descriptors must be filled with empty entries up to the maximal number of entries. This ensures that non-valid addresses are read, see the following example.

ClassA1 o = new ClassA21();
((ClassA3)o).m1();

The offset will be calculated to be 3. In the type descriptor of ClassA21 the entry at offset 3 must be 0.
Let's consider another case:

Object o;
((ClassX)o).m1();

The static type of o is Object. The runtime type could be anything. Therefore, we could check against any type. For instance, ClassX could have the offset 10. Hence, all type descriptors must have at least 10 entries.

Interface classes cannot be listed in the table with the standard classes. The reason is that interface classes do not have fixed offsets.

Interface classes have different offsets

Depending on the extension hierarchy the interface occupies different places in the table and the compiler cannot calculate a fixed offset to check against.
For this reason the type descriptor has a table with all interfaces that this class implements. The compiler will determine at compile time for which interfaces there is ever a type check. Only these will be inserted into the table.

Type descriptor with checkIds of its interfaces

All the affected interfaces get numbered (chkId) and will be inserted into the table starting with the highest number. The checking can now run as follows: the compiler knows the chkId of the interface to check against. It will search chkId in the table. If found, the check returns true else false. The last entry must be 0 in order to end the search.
Here again, checkcast and instanceof differ slightly.

The following code

  Object[][][] o = new Object[2][3][4]; 
  A[] x = new AA[5];
  o[0][0] = x;
  o[0][1][2] = x;
  short[][] y = new short[2][3];
  o[1][0] = y;
  o[1][1][0] = y;

leads to

Type descriptors for complex use case

This example can be found in the test cases (org.deepjava.comp.targettest.arrays.ArrayInstanceTest.testInstance4).