====== 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** \\ {{ .:typecheckclassa.png?200&direct}}|1. ref != null, read tag \\ 2. array bit is 0 \\ 3. check type (see type checking for regular class)\\ returns true :-D|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 \\ {{ .:typecheck[s.png?200&direct}}|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 :-D |1. ref != null, read tag \\ 2. array bit is 1 \\ 3. check dimension \\ 4. component type = 0 \\ returns false |
^Object is of type [ClassA \\ {{ .:typecheck[classa.png?200&direct}}|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 :-D |

\\
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.

==== Special Case 'Object' ====
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:
  - 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.
  - 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.

==== checkcast ====
All the explanations above were for //instanceof//. For //checkcast// there are some modifications: 
  - The check against //Object// is never necessary. It will be eliminated already in the Bytecode.
  - A failing check has to cause an exception.
  - A ''null'' reference results in a positive check.

==== Type Checking for Regular Class ====
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: 
  - read tag of objectref (contains address of actual type descriptor)
  - 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. 
  - 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.
[{{ .:typecheck.png?600&direct | //Example of a type check //}}]

For the java code 
<code java>
ClassA1 o = new ClassA20();
((ClassA20)o).m1();
</code>
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''.
<code java>
ClassA1 o = new ClassA3();
((ClassA20)o).m1();
</code>
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.
<code java>
ClassA1 o = new ClassA21();
((ClassA20)o).m1();
</code>
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.
<code java>
ClassA1 o = new ClassA21();
((ClassA3)o).m1();
</code>
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:
<code java>
Object o;
((ClassX)o).m1();
</code>
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.

==== Type Check for Interface Type ====
Interface classes cannot be listed in the table with the standard classes. The reason is that interface classes do not have fixed offsets.\\
[{{ .:interfacetypecheck1.png?600&direct |//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. \\
[{{ .:interfacetypecheck2.png?300&direct | // 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.

==== Complex Use Case ====
The following code 
<code java>
  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;
</code>
leads to\\
[{{ .:typecheckexample1.png?600|//Type descriptors for complex use case//}}]\\
This example can be found in the test cases (//org.deepjava.comp.targettest.arrays.ArrayInstanceTest.testInstance4//).