Purifier1 Special Cases

Unresolved Null Object Issue

Brief Description

When a new object reference is created, it is often initilaized with null and set to point to a real object later on in the code. These variables are usually stored in the LocalVariables array with a type of ITEM_Null because there is no way to know from the instructions alone, at the time it is created, what type that variable actually represents. Although there are several ways to determine this information in some cases, there are cases where the current algorithm fails to determine what the indented type is. There are also cases where the current algorithm actually causes, otherwise correctly idetified types to be changed to incorrect types.

Status

This problem was thought to be solved because the information was available in LocalVariable table attributes. However, it turns out that this is not the case and that more research for a better algorithm is required.

Action Items

Find a better algorithm.

Test Cases Exhibiting Issue

Details

The issue is that the String array s (see source code below) is initialized with the null reference. In the bytecode, a null is stored in LocalVariables slot 1, but there is no way to calculate, just from the instructions, what type of object that null represents. There are some tricks for figuring this out, such as using an invoke instruction's signature further down stream. However, in this case, the only hint in the code is that a new String array is created and stored in that same location in the body of the try block. Unfortunately, there is no way to determine, from the instructions alone, if this is the initialization of that slot with a real object reference of the correct type or if it is simply being over written with a completely new object.

Since the generateStackMap method attempts to build a StackMap based on the contents of the instruction list, Exception table and the ConstantPoolGen alone, it is clearly not possible to resolve the type of LocalVariables slot 1 without some extra help. When using the Purifier1 as a standard preverifier, this is no problem because javac does leave LocalVariable attributes in the method that can be used to resolve these issues. Newer versions of the preverifier also leave LocalVariable attributes. However, if the intent is to modify an existing J2ME class that has been modified with an older preverifier, then the StackMap of the original method, before modification, can be used to solve these cases. Unfortunately, if the method is modified significantly then this won't work. Finally, for a method that is being created from scratch using BCEL, the generator will have to take the responsibility of specifying what these null object types are supposed to be.

Example

ProblemCases.unresolvedNullObject provides an example of this issue and is shown below.

The ProblemCases.nullObjectNeverInit2 and ProblemCases.nullObjectNeverInit test cases test an opposing situation where the ITEM_Null really should be in the StackMap. This helps ensure that the solutions to this problem don't remove ITEM_Nulls when they actually do belong.

Source Code

1:  public void unresolvedNullObject() {
2:    String[] s = null;
3:    int max = 5;
4:    try {
5:      s = new String[max];
6:      s[9] = "Out of bounds";
7:    } catch (ArrayIndexOutOfBoundsException aioob ) {
8:    }
9:  }

Bytecode

The following byte code is from the compiled and preverified class file created from the source in the previous section. The StackMap has been reformatted for readability.

0:    aconst_null
1:    astore_1
2:    iconst_5
3:    istore_2
4:    iload_2
5:    anewarray		<java.lang.String> (11)
8:    astore_1
9:    aload_1
10:   bipush		9
12:   ldc		"Out of bounds" (12)
14:   aastore
15:   goto		#19
18:   astore_3
19:   return

Exception handler(s) =
From	To	Handler	Type
4	15	18	java.lang.ArrayIndexOutOfBoundsException(13)

Attribute(s) =
StackMap(
	(
		offset = 18,
		locals = {
			(type=Object, (20)class=com.markcrocker.purifier.testcases.ProblemCases),
			(type=Object, (103)class=[Ljava.lang.String;),
			(type=Integer)
		},
		stack items = {
			(type=Object, (13)class=java.lang.ArrayIndexOutOfBoundsException)
		}
	)
	(
		offset = 19,
		locals = {
			(type=Object, (20)class=com.markcrocker.purifier.testcases.ProblemCases),
			(type=Object, (103)class=[Ljava.lang.String;),
			(type=Integer)
		}
	)
)

Data Flow Analysis

The aconst_null instruction at offset 0 puts a null on the stack and the following astore_1 puts the null on the LocalVariables table at slot 1. This is supposed to represent the String array object s even though there's no hint from the instructions what type it really is. Instruction 4 is the start of the try block, so what is on the LocalVariables table at that point is what is used for the Frame in the exception handler, which starts at offset 18. Although instructions at offsets 5 and 8 do put a String array into slot 1, it is not possible use this information to decide what type should be stored on slot 1 at offset 18.

Without any extra information from the LocalVariables, an existing StackMap or a downstream method invokation that uses the variable, the Purifier1 will produce a StackMap that includes:

		offset = 18,
		locals = {
			(type=Object, (20)class=com.markcrocker.purifier.testcases.ProblemCases),
			(type=Null),
			(type=Integer)
		},
		stack items = {
			(type=Object, (13)class=java.lang.ArrayIndexOutOfBoundsException)
		}

This is clearly in disagreement with the one in the bytecode above, but, without extra type information, this is the best that can be done.

Solutions

Because of the nature of this problem, there are several levels of solutions to provide as much flexibility as possible.

The first level of repair is in the LocalVariables.resolveConflicts method, which checks for cases where an incumbent ITEM_Null is challenged by an object. The conflict resolution code will treat the ITEM_Null type as if it is a subtype of the object and over-ride the ITEM_Null with the object.

Sometimes it is not possible to resolve Null objects in this way. One solution that is used inside of the StackMapGen.updateFrame method is to use the information in the signature of invocation instructions, such as invokevirtual, to determine what the data type of a Null is supposed to be. For this to work correctly, the DFA must be careful to make sure that when Frames are copied for storage, that the copy is not a deep copy. This is because the DFA needs to hold onto the actual StackMapType objects that are stored in the OperandStack and LocalVariables so that changes made to them in the invokeInstruction method affect the same objects that are used to generate the final StackMap.

This only provides a partial solution. A number of cases have been found that these techniques do not solve.

Back to Developer's Guide   Purifier1 Home Page