MethodAnalyzer.java revision 122eba5cecf44f6c819854e204779c83124abdf8 
1package org.jf.dexlib.Code.Analysis;
2
3import org.jf.dexlib.*;
4import org.jf.dexlib.Code.*;
5import org.jf.dexlib.Code.Format.ArrayDataPseudoInstruction;
6import org.jf.dexlib.Code.Format.Format;
7import org.jf.dexlib.Util.*;
8
9import java.util.*;
10
11public class MethodAnalyzer {
12    private final ClassDataItem.EncodedMethod encodedMethod;
13
14    private SparseArray<AnalyzedInstruction> instructions;
15
16    private boolean analyzed = false;
17
18    private BitSet instructionsToVerify;
19
20    //This is a dummy instruction that occurs immediately before the first real instruction. We can initialize the
21    //register types for this instruction to the parameter types, in order to have them propagate to all of its
22    //successors, e.g. the first real instruction, the first instructions in any exception handlers covering the first
23    //instruction, etc.
24    private AnalyzedInstruction startOfMethod;
25
26    public MethodAnalyzer(ClassDataItem.EncodedMethod encodedMethod) {
27        if (encodedMethod == null) {
28            throw new IllegalArgumentException("encodedMethod cannot be null");
29        }
30        if (encodedMethod.codeItem == null || encodedMethod.codeItem.getInstructions().length == 0) {
31            throw new IllegalArgumentException("The method has no code");
32        }
33        this.encodedMethod = encodedMethod;
34        buildInstructionList();
35
36        //override AnalyzedInstruction and provide custom implementations of some of the methods, so that we don't
37        //have to handle the case this special case of instruction being null, in the main class
38        startOfMethod = new AnalyzedInstruction(null, -1, encodedMethod.codeItem.getRegisterCount()) {
39            public boolean setsRegister() {
40                return false;
41            }
42
43            @Override
44            public boolean setsWideRegister() {
45                return false;
46            }
47
48            @Override
49            public boolean setsRegister(int registerNumber) {
50                return false;
51            }
52
53            @Override
54            public int getDestinationRegister() {
55                assert false;
56                return -1;
57            };
58        };
59
60        instructionsToVerify = new BitSet(instructions.size());
61    }
62
63    public AnalyzedInstruction[] analyze() {
64        assert encodedMethod != null;
65        assert encodedMethod.codeItem != null;
66
67        if (analyzed) {
68            return makeInstructionArray();
69        }
70
71        CodeItem codeItem = encodedMethod.codeItem;
72        MethodIdItem methodIdItem = encodedMethod.method;
73
74        int totalRegisters = codeItem.getRegisterCount();
75        int parameterRegisters = methodIdItem.getPrototype().getParameterRegisterCount();
76
77        //if this isn't a static method, determine which register is the "this" register and set the type to the
78        //current class
79        if ((encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0) {
80            int thisRegister = totalRegisters - parameterRegisters - 1;
81
82            //if this is a constructor, then set the "this" register to an uninitialized reference of the current class
83            if ((encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0) {
84                //TODO: it would probably make more sense to validate this somewhere else, and just put an assert here. Also, need to do a similar check for static constructor
85                if (!encodedMethod.method.getMethodName().equals("<init>")) {
86                    throw new ValidationException("The constructor flag can only be used with an <init> method.");
87                }
88
89                setRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
90                        RegisterType.getRegisterType(RegisterType.Category.UninitRef,
91                            ClassPath.getClassDef(methodIdItem.getContainingClass())));
92            } else {
93                if (encodedMethod.method.getMethodName().equals("<init>")) {
94                    throw new ValidationException("An <init> method must have the \"constructor\" access flag");
95                }
96
97                setRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
98                        RegisterType.getRegisterType(RegisterType.Category.Reference,
99                            ClassPath.getClassDef(methodIdItem.getContainingClass())));
100            }
101        }
102
103        TypeListItem parameters = methodIdItem.getPrototype().getParameters();
104        if (parameters != null) {
105            RegisterType[] parameterTypes = getParameterTypes(parameters, parameterRegisters);
106            for (int i=0; i<parameterTypes.length; i++) {
107                RegisterType registerType = parameterTypes[i];
108                int registerNum = (totalRegisters - parameterRegisters) + i;
109                setRegisterTypeAndPropagateChanges(startOfMethod, registerNum, registerType);
110            }
111        }
112
113        BitSet analyzedInstructions = new BitSet(instructionsToVerify.size());
114
115        //make sure all of the "first instructions" are marked for processing
116        for (AnalyzedInstruction successor: startOfMethod.successors) {
117            instructionsToVerify.set(successor.instructionIndex);
118        }
119
120        while (!instructionsToVerify.isEmpty()) {
121            for(int i=instructionsToVerify.nextSetBit(0); i>=0; i=instructionsToVerify.nextSetBit(i+1)) {
122                analyzeInstruction(instructions.get(i));
123                instructionsToVerify.clear(i);
124            }
125        }
126
127        analyzed = true;
128        return makeInstructionArray();
129    }
130
131    private int getThisRegister() {
132        assert (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0;
133
134        CodeItem codeItem = encodedMethod.codeItem;
135        assert codeItem != null;
136
137        MethodIdItem methodIdItem = encodedMethod.method;
138        assert methodIdItem != null;
139
140        int totalRegisters = codeItem.getRegisterCount();
141        if (totalRegisters == 0) {
142            throw new ValidationException("A non-static method must have at least 1 register");
143        }
144
145        int parameterRegisters = methodIdItem.getPrototype().getParameterRegisterCount();
146
147        return totalRegisters - parameterRegisters - 1;
148    }
149
150    private boolean isInstanceConstructor() {
151        return (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0 &&
152               (encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0;
153    }
154
155    private boolean isStaticConstructor() {
156        return (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) != 0 &&
157               (encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0;
158    }
159
160    public AnalyzedInstruction[] makeInstructionArray() {
161        AnalyzedInstruction[] instructionArray = new AnalyzedInstruction[instructions.size()];
162        for (int i=0; i<instructions.size(); i++) {
163            instructionArray[i] = instructions.valueAt(i);
164        }
165        return instructionArray;
166    }
167
168    private static RegisterType[] getParameterTypes(TypeListItem typeListItem, int parameterRegisterCount) {
169        assert typeListItem != null;
170        assert parameterRegisterCount == typeListItem.getRegisterCount();
171
172        RegisterType[] registerTypes = new RegisterType[parameterRegisterCount];
173
174        int registerNum = 0;
175        for (TypeIdItem type: typeListItem.getTypes()) {
176            if (type.getRegisterCount() == 2) {
177                registerTypes[registerNum++] = RegisterType.getWideRegisterTypeForTypeIdItem(type, true);
178                registerTypes[registerNum++] = RegisterType.getWideRegisterTypeForTypeIdItem(type, false);
179            } else {
180                registerTypes[registerNum] = RegisterType.getRegisterTypeForTypeIdItem(type);
181            }
182        }
183
184        return registerTypes;
185    }
186
187    private int getInstructionAddress(AnalyzedInstruction instruction) {
188        return instructions.keyAt(instruction.instructionIndex);
189    }
190
191    private void setDestinationRegisterTypeAndPropagateChanges(AnalyzedInstruction analyzedInstruction,
192                                                               RegisterType registerType) {
193        setRegisterTypeAndPropagateChanges(analyzedInstruction, analyzedInstruction.getDestinationRegister(),
194                registerType);
195    }
196
197    private void setRegisterTypeAndPropagateChanges(AnalyzedInstruction analyzedInstruction, int registerNumber,
198                                                RegisterType registerType) {
199
200        BitSet changedInstructions = new BitSet(instructions.size());
201
202        boolean changed = analyzedInstruction.setPostRegisterType(registerNumber, registerType);
203
204        if (!changed || analyzedInstruction.setsRegister(registerNumber)) {
205            return;
206        }
207
208        propagateRegisterToSuccessors(analyzedInstruction, registerNumber, changedInstructions);
209
210        //using a for loop inside the while loop optimizes for the common case of the successors of an instruction
211        //occurring after the instruction. Any successors that occur prior to the instruction will be picked up on
212        //the next iteration of the while loop.
213        //this could also be done recursively, but in large methods it would likely cause very deep recursion,
214        //which would requires the user to specify a larger stack size. This isn't really a problem, but it is
215        //slightly annoying.
216        while (!changedInstructions.isEmpty()) {
217            for (int instructionIndex=changedInstructions.nextSetBit(0);
218                     instructionIndex>=0;
219                     instructionIndex=changedInstructions.nextSetBit(instructionIndex)) {
220
221                changedInstructions.clear(instructionIndex);
222
223                propagateRegisterToSuccessors(instructions.valueAt(instructionIndex), registerNumber,
224                        changedInstructions);
225            }
226        }
227
228        if (registerType.category == RegisterType.Category.LongLo) {
229            checkWidePair(registerNumber, analyzedInstruction);
230            setRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1,
231                    RegisterType.getRegisterType(RegisterType.Category.LongHi, null));
232        } else if (registerType.category == RegisterType.Category.DoubleLo) {
233            checkWidePair(registerNumber, analyzedInstruction);
234            setRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1,
235                    RegisterType.getRegisterType(RegisterType.Category.DoubleHi, null));
236        }
237    }
238
239    private void propagateRegisterToSuccessors(AnalyzedInstruction instruction, int registerNumber,
240                                               BitSet changedInstructions) {
241        for (AnalyzedInstruction successor: instruction.successors) {
242            if (!successor.setsRegister(registerNumber)) {
243                RegisterType registerType = successor.getMergedRegisterTypeFromPredecessors(registerNumber);
244
245                if (registerType.category == RegisterType.Category.UninitRef && instruction.isInvokeInit()) {
246                    continue;
247                }
248
249                if (successor.setPostRegisterType(registerNumber, registerType)) {
250                    changedInstructions.set(successor.instructionIndex);
251                    instructionsToVerify.set(successor.instructionIndex);
252                }
253            }
254        }
255    }
256
257
258
259    private void buildInstructionList() {
260        assert encodedMethod != null;
261        assert encodedMethod.codeItem != null;
262        int registerCount = encodedMethod.codeItem.getRegisterCount();
263
264        startOfMethod = new AnalyzedInstruction(null, -1, registerCount);
265
266        Instruction[] insns = encodedMethod.codeItem.getInstructions();
267
268        instructions = new SparseArray<AnalyzedInstruction>(insns.length);
269
270        //first, create all the instructions and populate the instructionAddresses array
271        int currentCodeAddress = 0;
272        for (int i=0; i<insns.length; i++) {
273            instructions.append(currentCodeAddress, new AnalyzedInstruction(insns[i], i, registerCount));
274            assert instructions.indexOfKey(currentCodeAddress) == i;
275            currentCodeAddress += insns[i].getSize(currentCodeAddress);
276        }
277
278        //next, populate the exceptionHandlers array. The array item for each instruction that can throw an exception
279        //and is covered by a try block should be set to a list of the first instructions of each exception handler
280        //for the try block covering the instruction
281        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
282        int triesIndex = 0;
283        CodeItem.TryItem currentTry = null;
284        AnalyzedInstruction[] currentExceptionHandlers = null;
285        AnalyzedInstruction[][] exceptionHandlers = new AnalyzedInstruction[insns.length][];
286
287        for (int i=0; i<instructions.size(); i++) {
288            AnalyzedInstruction instruction = instructions.valueAt(i);
289            Opcode instructionOpcode = instruction.instruction.opcode;
290
291            //check if we have gone past the end of the current try
292            if (currentTry != null) {
293                if (currentTry.getStartCodeAddress() + currentTry.getTryLength() <= currentCodeAddress) {
294                    currentTry = null;
295                    triesIndex++;
296                }
297            }
298
299            //check if the next try is applicable yet
300            if (currentTry == null && triesIndex < tries.length) {
301                CodeItem.TryItem tryItem = tries[triesIndex];
302                if (tryItem.getStartCodeAddress() <= currentCodeAddress) {
303                    assert(tryItem.getStartCodeAddress() + tryItem.getTryLength() > currentCodeAddress);
304
305                    currentTry = tryItem;
306
307                    currentExceptionHandlers = buildExceptionHandlerArray(tryItem);
308                }
309            }
310
311            //if we're inside a try block, and the instruction can throw an exception, then add the exception handlers
312            //for the current instruction
313            if (currentTry != null && instructionOpcode.canThrow()) {
314                exceptionHandlers[i] = currentExceptionHandlers;
315            }
316        }
317
318        //finally, populate the successors and predecessors for each instruction
319        assert instructions.size() > 0;
320        addPredecessorSuccessor(startOfMethod, instructions.valueAt(0), exceptionHandlers);
321        startOfMethod.addSuccessor(instructions.valueAt(0));
322
323        for (int i=0; i<instructions.size(); i++) {
324            AnalyzedInstruction instruction = instructions.valueAt(i);
325            Opcode instructionOpcode = instruction.instruction.opcode;
326            int instructionCodeAddress = getInstructionAddress(instruction);
327
328            if (instruction.instruction.opcode.canContinue()) {
329                if (i == instructions.size() - 1) {
330                    throw new ValidationException("Execution can continue past the last instruction");
331                }
332                AnalyzedInstruction nextInstruction = instructions.valueAt(i+1);
333                addPredecessorSuccessor(instruction, nextInstruction, exceptionHandlers);
334            }
335
336            if (instruction instanceof OffsetInstruction) {
337                OffsetInstruction offsetInstruction = (OffsetInstruction)instruction;
338
339                if (instructionOpcode == Opcode.PACKED_SWITCH || instructionOpcode == Opcode.SPARSE_SWITCH) {
340                    MultiOffsetInstruction switchDataInstruction =
341                            (MultiOffsetInstruction)instructions.get(instructionCodeAddress +
342                                    offsetInstruction.getTargetAddressOffset()).instruction;
343                    for (int targetAddressOffset: switchDataInstruction.getTargets()) {
344                        AnalyzedInstruction targetInstruction = instructions.get(instructionCodeAddress +
345                                targetAddressOffset);
346
347                        addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers);
348                    }
349                } else {
350                    int targetAddressOffset = offsetInstruction.getTargetAddressOffset();
351                    AnalyzedInstruction targetInstruction = instructions.get(instructionCodeAddress +
352                            targetAddressOffset);
353                    addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers);
354                }
355            }
356        }
357    }
358
359    private void addPredecessorSuccessor(AnalyzedInstruction predecessor, AnalyzedInstruction successor,
360                                                AnalyzedInstruction[][] exceptionHandlers) {
361        addPredecessorSuccessor(predecessor, successor, exceptionHandlers, false);
362    }
363
364    private void addPredecessorSuccessor(AnalyzedInstruction predecessor, AnalyzedInstruction successor,
365                                                AnalyzedInstruction[][] exceptionHandlers, boolean allowMoveException) {
366
367        if (!allowMoveException && successor.instruction.opcode == Opcode.MOVE_EXCEPTION) {
368            throw new ValidationException("Execution can pass from the " + predecessor.instruction.opcode.name +
369                    " instruction at code address 0x" + Integer.toHexString(getInstructionAddress(predecessor)) +
370                    " to the move-exception instruction at address 0x" +
371                    Integer.toHexString(getInstructionAddress(successor)));
372        }
373
374        if (!predecessor.addSuccessor(successor)) {
375            //if predecessor already had successor as a successor, then there's nothing else to do
376            return;
377        }
378
379        successor.addPredecessor(predecessor);
380
381        //TODO: need to handle the case of monitor-exit as a special case - the exception is thrown *after* the instruction executes
382        //if the successor can throw an instruction, then we need to add the exception handlers as additional
383        //successors to the predecessor (and then apply this same logic recursively if needed)
384        AnalyzedInstruction[] exceptionHandlersForSuccessor = exceptionHandlers[successor.instructionIndex];
385        if (exceptionHandlersForSuccessor != null) {
386            //the item for this instruction in exceptionHandlersForSuccessor should only be set if this instruction
387            //can throw an exception
388            assert predecessor.instruction.opcode.canThrow();
389
390            for (AnalyzedInstruction exceptionHandler: exceptionHandlersForSuccessor) {
391                addPredecessorSuccessor(predecessor, exceptionHandler, exceptionHandlers, true);
392            }
393        }
394    }
395
396    private AnalyzedInstruction[] buildExceptionHandlerArray(CodeItem.TryItem tryItem) {
397        int exceptionHandlerCount = tryItem.encodedCatchHandler.handlers.length;
398        int catchAllHandler = tryItem.encodedCatchHandler.getCatchAllHandlerAddress();
399        if (catchAllHandler != -1) {
400            exceptionHandlerCount++;
401        }
402
403        AnalyzedInstruction[] exceptionHandlers = new AnalyzedInstruction[exceptionHandlerCount];
404        for (int i=0; i<tryItem.encodedCatchHandler.handlers.length; i++) {
405            exceptionHandlers[i] = instructions.get(tryItem.encodedCatchHandler.handlers[i].getHandlerAddress());
406        }
407
408        if (catchAllHandler != -1) {
409            exceptionHandlers[exceptionHandlers.length - 1] = instructions.get(catchAllHandler);
410        }
411
412        return exceptionHandlers;
413    }
414
415    private void analyzeInstruction(AnalyzedInstruction analyzedInstruction) {
416        Instruction instruction = analyzedInstruction.instruction;
417
418        switch (instruction.opcode) {
419            case NOP:
420                return;
421            case MOVE:
422            case MOVE_FROM16:
423            case MOVE_16:
424                handleMove(analyzedInstruction, Primitive32BitCategories);
425                return;
426            case MOVE_WIDE:
427            case MOVE_WIDE_FROM16:
428            case MOVE_WIDE_16:
429                handleMove(analyzedInstruction, WideLowCategories);
430                return;
431            case MOVE_OBJECT:
432            case MOVE_OBJECT_FROM16:
433            case MOVE_OBJECT_16:
434                handleMove(analyzedInstruction, ReferenceCategories);
435                return;
436            case MOVE_RESULT:
437                handleMoveResult(analyzedInstruction, Primitive32BitCategories);
438                return;
439            case MOVE_RESULT_WIDE:
440                handleMoveResult(analyzedInstruction, WideLowCategories);
441                return;
442            case MOVE_RESULT_OBJECT:
443                handleMoveResult(analyzedInstruction, ReferenceCategories);
444                return;
445            case MOVE_EXCEPTION:
446                handleMoveException(analyzedInstruction);
447                return;
448            case RETURN_VOID:
449                handleReturnVoid(analyzedInstruction);
450                return;
451            case RETURN:
452                handleReturn(analyzedInstruction, Primitive32BitCategories);
453                return;
454            case RETURN_WIDE:
455                handleReturn(analyzedInstruction, WideLowCategories);
456                return;
457            case RETURN_OBJECT:
458                handleReturn(analyzedInstruction, ReferenceCategories);
459                return;
460            case CONST_4:
461            case CONST_16:
462            case CONST:
463                handleConst(analyzedInstruction);
464                return;
465            case CONST_HIGH16:
466                handleConstHigh16(analyzedInstruction);
467                return;
468            case CONST_WIDE_16:
469            case CONST_WIDE_32:
470            case CONST_WIDE:
471            case CONST_WIDE_HIGH16:
472                handleWideConst(analyzedInstruction);
473                return;
474            case CONST_STRING:
475            case CONST_STRING_JUMBO:
476                handleConstString(analyzedInstruction);
477                return;
478            case CONST_CLASS:
479                handleConstClass(analyzedInstruction);
480                return;
481            case MONITOR_ENTER:
482            case MONITOR_EXIT:
483                handleMonitor(analyzedInstruction);
484                return;
485            case CHECK_CAST:
486                handleCheckCast(analyzedInstruction);
487                return;
488            case INSTANCE_OF:
489                handleInstanceOf(analyzedInstruction);
490                return;
491            case ARRAY_LENGTH:
492                handleArrayLength(analyzedInstruction);
493                return;
494            case NEW_INSTANCE:
495                handleNewInstance(analyzedInstruction);
496                return;
497            case NEW_ARRAY:
498                handleNewArray(analyzedInstruction);
499                return;
500            case FILLED_NEW_ARRAY:
501                handleFilledNewArray(analyzedInstruction);
502                return;
503            case FILLED_NEW_ARRAY_RANGE:
504                handleFilledNewArrayRange(analyzedInstruction);
505                return;
506            case FILL_ARRAY_DATA:
507                handleFillArrayData(analyzedInstruction);
508                return;
509            case THROW:
510                handleThrow(analyzedInstruction);
511                return;
512            case GOTO:
513            case GOTO_16:
514            case GOTO_32:
515                //nothing to do
516                return;
517            case PACKED_SWITCH:
518                handleSwitch(analyzedInstruction, Format.PackedSwitchData);
519                return;
520            case SPARSE_SWITCH:
521                handleSwitch(analyzedInstruction, Format.SparseSwitchData);
522                return;
523            case CMPL_FLOAT:
524            case CMPG_FLOAT:
525                handleFloatWideCmp(analyzedInstruction, Primitive32BitCategories);
526                return;
527            case CMPL_DOUBLE:
528            case CMPG_DOUBLE:
529            case CMP_LONG:
530                handleFloatWideCmp(analyzedInstruction, WideLowCategories);
531                return;
532            case IF_EQ:
533            case IF_NE:
534                handleIfEqNe(analyzedInstruction);
535                return;
536            case IF_LT:
537            case IF_GE:
538            case IF_GT:
539            case IF_LE:
540                handleIf(analyzedInstruction);
541                return;
542            case IF_EQZ:
543            case IF_NEZ:
544                handleIfEqzNez(analyzedInstruction);
545                return;
546            case IF_LTZ:
547            case IF_GEZ:
548            case IF_GTZ:
549            case IF_LEZ:
550                handleIfz(analyzedInstruction);
551                return;
552            case AGET:
553                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Integer);
554                return;
555            case AGET_BOOLEAN:
556                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Boolean);
557                return;
558            case AGET_BYTE:
559                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Byte);
560                return;
561            case AGET_CHAR:
562                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Char);
563                return;
564            case AGET_SHORT:
565                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Short);
566                return;
567            case AGET_WIDE:
568                handleAgetWide(analyzedInstruction);
569                return;
570            case AGET_OBJECT:
571                handleAgetObject(analyzedInstruction);
572                return;
573            case APUT:
574                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Integer);
575                return;
576            case APUT_BOOLEAN:
577                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Boolean);
578                return;
579            case APUT_BYTE:
580                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Byte);
581                return;
582            case APUT_CHAR:
583                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Char);
584                return;
585            case APUT_SHORT:
586                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Short);
587                return;
588            case APUT_WIDE:
589                handleAputWide(analyzedInstruction);
590                return;
591            case APUT_OBJECT:
592                handleAputObject(analyzedInstruction);
593                return;
594            case IGET:
595                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Integer);
596                return;
597            case IGET_BOOLEAN:
598                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Boolean);
599                return;
600            case IGET_BYTE:
601                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Byte);
602                return;
603            case IGET_CHAR:
604                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Char);
605                return;
606            case IGET_SHORT:
607                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Short);
608                return;
609            case IGET_WIDE:
610                handleIgetWide(analyzedInstruction);
611                return;
612            case IGET_OBJECT:
613                handleIgetObject(analyzedInstruction);
614                return;
615            case IPUT:
616                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Integer);
617                return;
618            case IPUT_BOOLEAN:
619                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Boolean);
620                return;
621            case IPUT_BYTE:
622                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Byte);
623                return;
624            case IPUT_CHAR:
625                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Char);
626                return;
627            case IPUT_SHORT:
628                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Short);
629                return;
630            case IPUT_WIDE:
631                handleIputWide(analyzedInstruction);
632                return;
633            case IPUT_OBJECT:
634                handleIputObject(analyzedInstruction);
635                return;
636            case SGET:
637                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Integer);
638                return;
639            case SGET_BOOLEAN:
640                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Boolean);
641                return;
642            case SGET_BYTE:
643                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Byte);
644                return;
645            case SGET_CHAR:
646                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Char);
647                return;
648            case SGET_SHORT:
649                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Short);
650                return;
651            case SGET_WIDE:
652                handleSgetWide(analyzedInstruction);
653                return;
654            case SGET_OBJECT:
655                handleSgetObject(analyzedInstruction);
656                return;
657            case SPUT:
658                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Integer);
659                return;
660            case SPUT_BOOLEAN:
661                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Boolean);
662                return;
663            case SPUT_BYTE:
664                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Byte);
665                return;
666            case SPUT_CHAR:
667                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Char);
668                return;
669            case SPUT_SHORT:
670                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Short);
671                return;
672            case SPUT_WIDE:
673                handleSputWide(analyzedInstruction);
674                return;
675            case SPUT_OBJECT:
676                handleSputObject(analyzedInstruction);
677                return;
678            case INVOKE_VIRTUAL:
679                handleInvoke(analyzedInstruction, INVOKE_VIRTUAL);
680                return;
681            case INVOKE_SUPER:
682                handleInvoke(analyzedInstruction, INVOKE_SUPER);
683                return;
684            case INVOKE_DIRECT:
685                handleInvoke(analyzedInstruction, INVOKE_DIRECT);
686                return;
687            case INVOKE_STATIC:
688                handleInvoke(analyzedInstruction, INVOKE_STATIC);
689                return;
690            case INVOKE_INTERFACE:
691                handleInvoke(analyzedInstruction, INVOKE_INTERFACE);
692                return;
693            case INVOKE_VIRTUAL_RANGE:
694                handleInvokeRange(analyzedInstruction, INVOKE_VIRTUAL);
695                return;
696            case INVOKE_SUPER_RANGE:
697                handleInvokeRange(analyzedInstruction, INVOKE_SUPER);
698                return;
699            case INVOKE_DIRECT_RANGE:
700                handleInvokeRange(analyzedInstruction, INVOKE_DIRECT);
701                return;
702            case INVOKE_STATIC_RANGE:
703                handleInvokeRange(analyzedInstruction, INVOKE_STATIC);
704                return;
705            case INVOKE_INTERFACE_RANGE:
706                handleInvokeRange(analyzedInstruction, INVOKE_INTERFACE);
707                return;
708            case NEG_INT:
709            case NOT_INT:
710                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer);
711                return;
712            case NEG_LONG:
713            case NOT_LONG:
714                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.LongLo);
715                return;
716            case NEG_FLOAT:
717                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Float);
718                return;
719            case NEG_DOUBLE:
720                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.DoubleLo);
721                return;
722            case INT_TO_LONG:
723                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.LongLo);
724                return;
725            case INT_TO_FLOAT:
726                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Float);
727                return;
728            case INT_TO_DOUBLE:
729                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.DoubleLo);
730                return;
731            case LONG_TO_INT:
732            case DOUBLE_TO_INT:
733                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.Integer);
734                return;
735            case LONG_TO_FLOAT:
736            case DOUBLE_TO_FLOAT:
737                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.Float);
738                return;
739            case LONG_TO_DOUBLE:
740                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.DoubleLo);
741                return;
742            case FLOAT_TO_INT:
743                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer);
744                return;
745            case FLOAT_TO_LONG:
746                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.LongLo);
747                return;
748            case FLOAT_TO_DOUBLE:
749                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.DoubleLo);
750                return;
751            case DOUBLE_TO_LONG:
752                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.LongLo);
753                return;
754            case INT_TO_BYTE:
755                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Byte);
756                return;
757            case INT_TO_CHAR:
758                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Char);
759                return;
760            case INT_TO_SHORT:
761                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Short);
762                return;
763            case ADD_INT:
764            case SUB_INT:
765            case MUL_INT:
766            case DIV_INT:
767            case REM_INT:
768            case SHL_INT:
769            case SHR_INT:
770            case USHR_INT:
771                handleBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
772                        RegisterType.Category.Integer, false);
773                return;
774            case AND_INT:
775            case OR_INT:
776            case XOR_INT:
777                handleBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
778                        RegisterType.Category.Integer, true);
779
780            case ADD_LONG:
781            case SUB_LONG:
782            case MUL_LONG:
783            case DIV_LONG:
784            case REM_LONG:
785            case AND_LONG:
786            case OR_LONG:
787            case XOR_LONG:
788                handleBinaryOp(analyzedInstruction, WideLowCategories, WideLowCategories, RegisterType.Category.LongLo,
789                        false);
790                return;
791            case SHL_LONG:
792            case SHR_LONG:
793            case USHR_LONG:
794                handleBinaryOp(analyzedInstruction, WideLowCategories, Primitive32BitCategories,
795                        RegisterType.Category.LongLo, false);
796                return;
797            case ADD_FLOAT:
798            case SUB_FLOAT:
799            case MUL_FLOAT:
800            case DIV_FLOAT:
801            case REM_FLOAT:
802                handleBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
803                        RegisterType.Category.Float, false);
804                return;
805            case ADD_DOUBLE:
806            case SUB_DOUBLE:
807            case MUL_DOUBLE:
808            case DIV_DOUBLE:
809            case REM_DOUBLE:
810                handleBinaryOp(analyzedInstruction, WideLowCategories, WideLowCategories,
811                        RegisterType.Category.DoubleLo, false);
812                return;
813            case ADD_INT_2ADDR:
814            case SUB_INT_2ADDR:
815            case MUL_INT_2ADDR:
816            case DIV_INT_2ADDR:
817            case REM_INT_2ADDR:
818            case SHL_INT_2ADDR:
819            case SHR_INT_2ADDR:
820            case USHR_INT_2ADDR:
821                handleBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
822                        RegisterType.Category.Integer, false);
823                return;
824            case AND_INT_2ADDR:
825            case OR_INT_2ADDR:
826            case XOR_INT_2ADDR:
827                handleBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
828                        RegisterType.Category.Integer, true);
829                return;
830            case ADD_LONG_2ADDR:
831            case SUB_LONG_2ADDR:
832            case MUL_LONG_2ADDR:
833            case DIV_LONG_2ADDR:
834            case REM_LONG_2ADDR:
835            case AND_LONG_2ADDR:
836            case OR_LONG_2ADDR:
837            case XOR_LONG_2ADDR:
838                handleBinary2AddrOp(analyzedInstruction, WideLowCategories, WideLowCategories,
839                        RegisterType.Category.LongLo, false);
840                return;
841            case SHL_LONG_2ADDR:
842            case SHR_LONG_2ADDR:
843            case USHR_LONG_2ADDR:
844                handleBinary2AddrOp(analyzedInstruction, WideLowCategories, Primitive32BitCategories,
845                        RegisterType.Category.LongLo, false);
846                return;
847            case ADD_FLOAT_2ADDR:
848            case SUB_FLOAT_2ADDR:
849            case MUL_FLOAT_2ADDR:
850            case DIV_FLOAT_2ADDR:
851            case REM_FLOAT_2ADDR:
852                handleBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
853                        RegisterType.Category.Float, false);
854                return;
855            case ADD_DOUBLE_2ADDR:
856            case SUB_DOUBLE_2ADDR:
857            case MUL_DOUBLE_2ADDR:
858            case DIV_DOUBLE_2ADDR:
859            case REM_DOUBLE_2ADDR:
860                handleBinary2AddrOp(analyzedInstruction, WideLowCategories, WideLowCategories,
861                        RegisterType.Category.DoubleLo, false);
862                return;
863        }
864    }
865
866    private static final EnumSet<RegisterType.Category> Primitive32BitCategories = EnumSet.of(
867            RegisterType.Category.Null,
868            RegisterType.Category.Boolean,
869            RegisterType.Category.Byte,
870            RegisterType.Category.Short,
871            RegisterType.Category.Char,
872            RegisterType.Category.Integer,
873            RegisterType.Category.Float);
874
875    private static final EnumSet<RegisterType.Category> WideLowCategories = EnumSet.of(
876            RegisterType.Category.LongLo,
877            RegisterType.Category.DoubleLo);
878
879    private static final EnumSet<RegisterType.Category> WideHighCategories = EnumSet.of(
880            RegisterType.Category.LongHi,
881            RegisterType.Category.DoubleHi);
882
883    private static final EnumSet<RegisterType.Category> ReferenceCategories = EnumSet.of(
884            RegisterType.Category.Null,
885            RegisterType.Category.Reference);
886
887    private static final EnumSet<RegisterType.Category> ReferenceAndPrimitive32BitCategories = EnumSet.of(
888            RegisterType.Category.Null,
889            RegisterType.Category.Boolean,
890            RegisterType.Category.Byte,
891            RegisterType.Category.Short,
892            RegisterType.Category.Char,
893            RegisterType.Category.Integer,
894            RegisterType.Category.Float,
895            RegisterType.Category.Reference);
896
897    private static final EnumSet<RegisterType.Category> BooleanCategories = EnumSet.of(
898            RegisterType.Category.Null,
899            RegisterType.Category.One,
900            RegisterType.Category.Boolean);
901
902    private void handleMove(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
903        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
904
905        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
906                validCategories);
907
908        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
909    }
910
911    private void handleMoveResult(AnalyzedInstruction analyzedInstruction,
912                                     EnumSet<RegisterType.Category> allowedCategories) {
913
914        //TODO: handle the case when the previous instruction is an odexed instruction
915
916        if (analyzedInstruction.instructionIndex == 0) {
917            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " cannot be the first " +
918                    "instruction in a method. It must occur after an invoke-*/fill-new-array instruction");
919        }
920
921        AnalyzedInstruction previousInstruction = instructions.valueAt(analyzedInstruction.instructionIndex-1);
922
923        if (!previousInstruction.instruction.opcode.setsResult()) {
924            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " must occur after an " +
925                    "invoke-*/fill-new-array instruction");
926        }
927
928        //TODO: does dalvik allow a move-result after an invoke with a void return type?
929        RegisterType resultRegisterType;
930
931        InstructionWithReference invokeInstruction = (InstructionWithReference)previousInstruction.instruction;
932        Item item = invokeInstruction.getReferencedItem();
933
934        if (item instanceof MethodIdItem) {
935            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem(
936                    ((MethodIdItem)item).getPrototype().getReturnType());
937        } else {
938            assert item instanceof TypeIdItem;
939            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
940        }
941
942        if (!allowedCategories.contains(resultRegisterType.category)) {
943            throw new ValidationException(String.format("Wrong move-result* instruction for return value %s",
944                    resultRegisterType.toString()));
945        }
946
947        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, resultRegisterType);
948    }
949
950    private void handleMoveException(AnalyzedInstruction analyzedInstruction) {
951        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
952        int instructionAddress = getInstructionAddress(analyzedInstruction);
953
954        if (tries == null) {
955            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
956        }
957
958        RegisterType exceptionType = null;
959
960        for (CodeItem.TryItem tryItem: encodedMethod.codeItem.getTries()) {
961            if (tryItem.encodedCatchHandler.getCatchAllHandlerAddress() == instructionAddress) {
962                exceptionType = RegisterType.getRegisterType(RegisterType.Category.Reference,
963                        ClassPath.getClassDef("Ljava/lang/Throwable;"));
964                break;
965            }
966            for (CodeItem.EncodedTypeAddrPair handler: tryItem.encodedCatchHandler.handlers) {
967                if (handler.getHandlerAddress() == instructionAddress) {
968                    exceptionType = RegisterType.getRegisterTypeForTypeIdItem(handler.exceptionType)
969                            .merge(exceptionType);
970                }
971            }
972        }
973
974        if (exceptionType == null) {
975            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
976        }
977
978        //TODO: check if the type is a throwable. Should we throw a ValidationException or print a warning? (does dalvik validate that it's a throwable? It doesn't in CodeVerify.c, but it might check in DexSwapVerify.c)
979        if (exceptionType.category != RegisterType.Category.Reference) {
980            throw new ValidationException(String.format("Exception type %s is not a reference type",
981                    exceptionType.toString()));
982        }
983
984        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, exceptionType);
985    }
986
987    private void checkConstructorReturn(AnalyzedInstruction analyzedInstruction) {
988        assert this.isInstanceConstructor();
989
990        //if we're in an instance constructor (an <init> method), then the superclass <init> must have been called.
991        //When execution enters the method, the "this" register is set as an uninitialized reference to the containing
992        //class. Once the superclass' <init> is called, the "this" register is upgraded to a full-blown reference type,
993        //so we need to ensure that the "this" register isn't an uninitialized reference
994
995        int thisRegister = getThisRegister();
996        RegisterType thisRegisterType = analyzedInstruction.postRegisterMap[thisRegister];
997
998        if (thisRegisterType.category == RegisterType.Category.UninitRef) {
999            throw new ValidationException("Returning from constructor without calling the superclass' <init>");
1000        }
1001        assert thisRegisterType.category == RegisterType.Category.Reference;
1002        assert thisRegisterType.type == ClassPath.getClassDef(encodedMethod.method.getContainingClass());
1003    }
1004
1005    private void handleReturnVoid(AnalyzedInstruction analyzedInstruction) {
1006        if (this.isInstanceConstructor()) {
1007            checkConstructorReturn(analyzedInstruction);
1008        }
1009
1010        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
1011        if (returnType.getTypeDescriptor().charAt(0) != 'V') {
1012            //TODO: could add which return-* variation should be used instead
1013            throw new ValidationException("Cannot use return-void with a non-void return type (" +
1014                returnType.getTypeDescriptor() + ")");
1015        }
1016    }
1017
1018    private void handleReturn(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
1019        if (this.isInstanceConstructor()) {
1020            checkConstructorReturn(analyzedInstruction);
1021        }
1022
1023        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1024        int returnRegister = instruction.getRegisterA();
1025        RegisterType returnRegisterType = getAndCheckSourceRegister(analyzedInstruction, returnRegister,
1026                validCategories);
1027
1028        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
1029        if (returnType.getTypeDescriptor().charAt(0) == 'V') {
1030            throw new ValidationException("Cannot use return with a void return type. Use return-void instead");
1031        }
1032
1033        RegisterType methodReturnRegisterType = RegisterType.getRegisterTypeForTypeIdItem(returnType);
1034
1035        if (!validCategories.contains(methodReturnRegisterType.category)) {
1036            //TODO: could add which return-* variation should be used instead
1037            throw new ValidationException(String.format("Cannot use %s with return type %s",
1038                    analyzedInstruction.instruction.opcode.name, returnType.getTypeDescriptor()));
1039        }
1040
1041        if (validCategories == ReferenceCategories) {
1042            if (methodReturnRegisterType.type.isInterface()) {
1043                if (!returnRegisterType.type.implementsInterface(methodReturnRegisterType.type)) {
1044                    //TODO: how to handle warnings?
1045                }
1046            } else {
1047                if (!returnRegisterType.type.extendsClass(methodReturnRegisterType.type)) {
1048                    throw new ValidationException(String.format("The return value in register v%d (%s) is not " +
1049                            "compatible with the method's return type %s", returnRegister,
1050                            returnRegisterType.type.getClassType(), methodReturnRegisterType.type.getClassType()));
1051                }
1052            }
1053        }
1054    }
1055
1056    private void handleConst(AnalyzedInstruction analyzedInstruction) {
1057        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
1058
1059        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(instruction.getLiteral());
1060
1061        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
1062        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
1063        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
1064    }
1065
1066    private void handleConstHigh16(AnalyzedInstruction analyzedInstruction) {
1067        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
1068
1069        //TODO: test this
1070        long literalValue = instruction.getLiteral() << 16;
1071        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(literalValue);
1072
1073        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
1074        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
1075        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
1076    }
1077
1078    private void handleWideConst(AnalyzedInstruction analyzedInstruction) {
1079        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1080                RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1081    }
1082
1083    private void handleConstString(AnalyzedInstruction analyzedInstruction) {
1084        ClassPath.ClassDef stringClassDef = ClassPath.getClassDef("Ljava/lang/String;");
1085        RegisterType stringType = RegisterType.getRegisterType(RegisterType.Category.Reference, stringClassDef);
1086        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, stringType);
1087    }
1088
1089    private void handleConstClass(AnalyzedInstruction analyzedInstruction) {
1090        ClassPath.ClassDef classClassDef = ClassPath.getClassDef("Ljava/lang/Class;");
1091        RegisterType classType = RegisterType.getRegisterType(RegisterType.Category.Reference, classClassDef);
1092
1093        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1094        Item item = instruction.getReferencedItem();
1095        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1096
1097        //make sure the referenced class is resolvable
1098        //TODO: need to check class access
1099        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
1100    }
1101
1102    private void handleMonitor(AnalyzedInstruction analyzedInstruction) {
1103        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1104        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), ReferenceCategories);
1105    }
1106
1107    private void handleCheckCast(AnalyzedInstruction analyzedInstruction) {
1108        {
1109            //ensure the "source" register is a reference type
1110            SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1111
1112            RegisterType registerType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
1113                    ReferenceCategories);
1114        }
1115
1116        {
1117            //resolve and verify the class that we're casting to
1118            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1119
1120            Item item = instruction.getReferencedItem();
1121            assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1122
1123            //TODO: need to check class access
1124            RegisterType castRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1125            if (castRegisterType.category != RegisterType.Category.Reference) {
1126                //TODO: verify that dalvik allows a non-reference type..
1127                //TODO: print a warning, but don't re-throw the exception. dalvik allows a non-reference type during validation (but throws an exception at runtime)
1128            }
1129
1130            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, castRegisterType);
1131        }
1132    }
1133
1134    private void handleInstanceOf(AnalyzedInstruction analyzedInstruction) {
1135        {
1136            //ensure the register that is being checks is a reference type
1137            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1138
1139            getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), ReferenceCategories);
1140        }
1141
1142        {
1143            //resolve and verify the class that we're checking against
1144            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1145
1146            Item item = instruction.getReferencedItem();
1147            assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1148            RegisterType registerType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1149            if (registerType.category != RegisterType.Category.Reference) {
1150                throw new ValidationException(String.format("Cannot use instance-of with a non-reference type %s",
1151                        registerType.toString()));
1152            }
1153
1154            //TODO: is it valid to use an array type?
1155
1156            //TODO: could probably do an even more sophisticated check, where we check the possible register types against the specified type. In some cases, we could determine that it always fails, and print a warning to that effect.
1157            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1158                    RegisterType.getRegisterType(RegisterType.Category.Boolean, null));
1159        }
1160    }
1161
1162    private void handleArrayLength(AnalyzedInstruction analyzedInstruction) {
1163        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1164
1165        int arrayRegisterNumber = instruction.getRegisterB();
1166        RegisterType arrayRegisterType = getAndCheckSourceRegister(analyzedInstruction, arrayRegisterNumber,
1167                ReferenceCategories);
1168
1169        if (arrayRegisterType.type != null) {
1170            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1171                throw new ValidationException(String.format("Cannot use array-length with non-array type %s",
1172                        arrayRegisterType.type.getClassType()));
1173            }
1174        }
1175
1176        assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1177
1178        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1179                RegisterType.getRegisterType(RegisterType.Category.Integer, null));
1180    }
1181
1182    private void handleNewInstance(AnalyzedInstruction analyzedInstruction) {
1183        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1184
1185        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1186        RegisterType destRegisterType = analyzedInstruction.postRegisterMap[register];
1187        if (destRegisterType.category != RegisterType.Category.Unknown) {
1188            assert destRegisterType.category == RegisterType.Category.UninitRef;
1189
1190            //the "post-instruction" destination register will only be set if we've gone over
1191            //this instruction at least once before. If this is the case, then we need to check
1192            //all the other registers, and make sure that none of them contain the same
1193            //uninitialized reference that is in the destination register.
1194
1195            for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) {
1196                if (i==register) {
1197                    continue;
1198                }
1199
1200                if (analyzedInstruction.getPreInstructionRegisterType(i) == destRegisterType) {
1201                    throw new ValidationException(String.format("Register v%d contains an uninitialized reference " +
1202                            "that was created by this new-instance instruction.", i));
1203                }
1204            }
1205        }
1206
1207        Item item = instruction.getReferencedItem();
1208        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1209
1210        //TODO: need to check class access
1211        RegisterType classType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1212        if (classType.category != RegisterType.Category.Reference) {
1213            throw new ValidationException(String.format("Cannot use new-instance with a non-reference type %s",
1214                    classType.toString()));
1215        }
1216
1217        if (((TypeIdItem)item).getTypeDescriptor().charAt(0) == '[') {
1218            throw new ValidationException("Cannot use array type \"" + ((TypeIdItem)item).getTypeDescriptor() +
1219                    "\" with new-instance. Use new-array instead.");
1220        }
1221
1222        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1223                RegisterType.getUnitializedReference(classType.type));
1224    }
1225
1226    private void handleNewArray(AnalyzedInstruction analyzedInstruction) {
1227        {
1228            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1229            getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), Primitive32BitCategories);
1230        }
1231
1232        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1233
1234        Item item = instruction.getReferencedItem();
1235        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1236
1237        RegisterType arrayType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1238        assert arrayType.type instanceof ClassPath.ArrayClassDef;
1239
1240        if (arrayType.category != RegisterType.Category.Reference) {
1241            throw new ValidationException(String.format("Cannot use new-array with a non-reference type %s",
1242                    arrayType.toString()));
1243        }
1244        if (arrayType.type.getClassType().charAt(0) != '[') {
1245            throw new ValidationException("Cannot use non-array type \"" + arrayType.type.getClassType() +
1246                    "\" with new-array. Use new-instance instead.");
1247        }
1248
1249        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1250    }
1251
1252    private static interface RegisterIterator {
1253        int getRegister();
1254        boolean moveNext();
1255        int getCount();
1256        boolean pastEnd();
1257    }
1258
1259    private static class Format35cRegisterIterator implements RegisterIterator {
1260        private final int registerCount;
1261        private final int[] registers;
1262        private int currentRegister = 0;
1263
1264        public Format35cRegisterIterator(FiveRegisterInstruction instruction) {
1265            registerCount = instruction.getRegCount();
1266            registers = new int[]{instruction.getRegisterD(), instruction.getRegisterE(),
1267                                  instruction.getRegisterF(), instruction.getRegisterG(),
1268                                  instruction.getRegisterA()};
1269        }
1270
1271        public int getRegister() {
1272            return registers[currentRegister];
1273        }
1274
1275        public boolean moveNext() {
1276            currentRegister++;
1277            return pastEnd();
1278        }
1279
1280        public int getCount() {
1281            return registerCount;
1282        }
1283
1284        public boolean pastEnd() {
1285            return currentRegister >= registerCount;
1286        }
1287    }
1288
1289    private static class Format3rcRegisterIterator implements RegisterIterator {
1290        private final int startRegister;
1291        private final int registerCount;
1292        private int currentRegister = 0;
1293
1294        public Format3rcRegisterIterator(RegisterRangeInstruction instruction) {
1295            startRegister = instruction.getStartRegister();
1296            registerCount = instruction.getRegCount();
1297        }
1298
1299        public int getRegister() {
1300            return startRegister + currentRegister;
1301        }
1302
1303        public boolean moveNext() {
1304            currentRegister++;
1305            return pastEnd();
1306        }
1307
1308        public int getCount() {
1309            return registerCount;
1310        }
1311
1312        public boolean pastEnd() {
1313            return currentRegister >= registerCount;
1314        }
1315    }
1316
1317    private void handleFilledNewArrayCommon(AnalyzedInstruction analyzedInstruction,
1318                                               RegisterIterator registerIterator) {
1319        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1320
1321        RegisterType arrayType;
1322        RegisterType arrayImmediateElementType;
1323
1324        Item item = instruction.getReferencedItem();
1325        assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1326
1327        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
1328
1329        if (classDef.getClassType().charAt(0) != '[') {
1330            throw new ValidationException("Cannot use non-array type \"" + classDef.getClassType() +
1331                "\" with new-array. Use new-instance instead.");
1332        }
1333
1334        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)classDef;
1335        arrayType = RegisterType.getRegisterType(RegisterType.Category.Reference, classDef);
1336        arrayImmediateElementType = RegisterType.getRegisterTypeForType(
1337                arrayClassDef.getImmediateElementClass().getClassType());
1338        String baseElementType = arrayClassDef.getBaseElementClass().getClassType();
1339        if (baseElementType.charAt(0) == 'J' || baseElementType.charAt(0) == 'D') {
1340            throw new ValidationException("Cannot use filled-new-array to create an array of wide values " +
1341                    "(long or double)");
1342        }
1343
1344        do {
1345            int register = registerIterator.getRegister();
1346            RegisterType elementType = analyzedInstruction.getPreInstructionRegisterType(register);
1347            assert elementType != null;
1348
1349            if (!elementType.canBeAssignedTo(arrayImmediateElementType)) {
1350                throw new ValidationException("Register v" + Integer.toString(register) + " is of type " +
1351                        elementType.toString() + " and is incompatible with the array type " +
1352                        arrayType.type.getClassType());
1353            }
1354        } while (registerIterator.moveNext());
1355
1356        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1357    }
1358
1359    private void handleFilledNewArray(AnalyzedInstruction analyzedInstruction) {
1360        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
1361        handleFilledNewArrayCommon(analyzedInstruction, new Format35cRegisterIterator(instruction));
1362    }
1363
1364    private void handleFilledNewArrayRange(AnalyzedInstruction analyzedInstruction) {
1365        RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
1366
1367        //instruction.getStartRegister() and instruction.getRegCount() both return an int value, but are actually
1368        //unsigned 16 bit values, so we don't have to worry about overflowing an int when adding them together
1369        if (instruction.getStartRegister() + instruction.getRegCount() >= 1<<16) {
1370            throw new ValidationException(String.format("Invalid register range {v%d .. v%d}. The ending register " +
1371                    "is larger than the largest allowed register of v65535.",
1372                    instruction.getStartRegister(),
1373                    instruction.getStartRegister() + instruction.getRegCount() - 1));
1374        }
1375
1376        handleFilledNewArrayCommon(analyzedInstruction, new Format3rcRegisterIterator(instruction));
1377    }
1378
1379    private void handleFillArrayData(AnalyzedInstruction analyzedInstruction) {
1380        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1381
1382        int register = instruction.getRegisterA();
1383        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1384        assert registerType != null;
1385
1386        if (registerType.category == RegisterType.Category.Null) {
1387            return;
1388        }
1389
1390        if (registerType.category != RegisterType.Category.Reference) {
1391            throw new ValidationException(String.format("Cannot use fill-array-data with non-array register v%d of " +
1392                    "type %s", register, registerType.toString()));
1393        }
1394
1395        assert registerType.type instanceof ClassPath.ArrayClassDef;
1396        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)registerType.type;
1397
1398        if (arrayClassDef.getArrayDimensions() != 1) {
1399            throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can only " +
1400                    "be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1401        }
1402
1403        int elementWidth;
1404        switch (arrayClassDef.getBaseElementClass().getClassType().charAt(0)) {
1405            case 'Z':
1406            case 'B':
1407                elementWidth = 1;
1408                break;
1409            case 'C':
1410            case 'S':
1411                elementWidth = 2;
1412                break;
1413            case 'I':
1414            case 'F':
1415                elementWidth = 4;
1416                break;
1417            case 'J':
1418            case 'D':
1419                elementWidth = 8;
1420                break;
1421            default:
1422                throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can " +
1423                        "only be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1424        }
1425
1426
1427        int arrayDataAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1428        int arrayDataCodeAddress = getInstructionAddress(analyzedInstruction) + arrayDataAddressOffset;
1429        AnalyzedInstruction arrayDataInstruction = this.instructions.get(arrayDataCodeAddress);
1430        if (arrayDataInstruction == null || arrayDataInstruction.instruction.getFormat() != Format.ArrayData) {
1431            throw new ValidationException(String.format("Could not find an array data structure at code address 0x%x",
1432                    arrayDataCodeAddress));
1433        }
1434
1435        ArrayDataPseudoInstruction arrayDataPseudoInstruction =
1436                (ArrayDataPseudoInstruction)arrayDataInstruction.instruction;
1437
1438        if (elementWidth != arrayDataPseudoInstruction.getElementWidth()) {
1439            throw new ValidationException(String.format("The array data at code address 0x%x does not have the " +
1440                    "correct element width for array type %s. Expecting element width %d, got element width %d.",
1441                    arrayDataCodeAddress, arrayClassDef.getClassType(), elementWidth,
1442                    arrayDataPseudoInstruction.getElementWidth()));
1443        }
1444    }
1445
1446    private void handleThrow(AnalyzedInstruction analyzedInstruction) {
1447        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1448
1449        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1450        assert registerType != null;
1451
1452        if (registerType.category == RegisterType.Category.Null) {
1453            return;
1454        }
1455
1456        if (registerType.category != RegisterType.Category.Reference) {
1457            throw new ValidationException(String.format("Cannot use throw with non-reference type %s in register v%d",
1458                    registerType.toString(), register));
1459        }
1460
1461        assert registerType.type != null;
1462
1463        if (!registerType.type.extendsClass(ClassPath.getClassDef("Ljava/lang/Throwable;"))) {
1464            throw new ValidationException(String.format("Cannot use throw with non-throwable type %s in register v%d",
1465                    registerType.type.getClassType(), register));
1466        }
1467    }
1468
1469    private void handleSwitch(AnalyzedInstruction analyzedInstruction, Format expectedSwitchDataFormat) {
1470        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1471        int switchCodeAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1472
1473        getAndCheckSourceRegister(analyzedInstruction, register, Primitive32BitCategories);
1474
1475        int switchDataCodeAddress = this.getInstructionAddress(analyzedInstruction) + switchCodeAddressOffset;
1476        AnalyzedInstruction switchDataAnalyzedInstruction = instructions.get(switchDataCodeAddress);
1477
1478        if (switchDataAnalyzedInstruction == null ||
1479            switchDataAnalyzedInstruction.instruction.getFormat() != expectedSwitchDataFormat) {
1480            throw new ValidationException(String.format("There is no %s structure at code address 0x%x",
1481                    expectedSwitchDataFormat.name(), switchDataCodeAddress));
1482        }
1483    }
1484
1485    private void handleFloatWideCmp(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
1486        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1487
1488        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validCategories);
1489        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), validCategories);
1490
1491        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1492                RegisterType.getRegisterType(RegisterType.Category.Byte, null));
1493    }
1494
1495    private void handleIfEqNe(AnalyzedInstruction analyzedInstruction) {
1496        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1497
1498        RegisterType registerType1 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1499        assert registerType1 != null;
1500
1501        RegisterType registerType2 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1502        assert registerType2 != null;
1503
1504        if (!(
1505                (ReferenceCategories.contains(registerType1.category) &&
1506                ReferenceCategories.contains(registerType2.category))
1507                    ||
1508                (Primitive32BitCategories.contains(registerType1.category) &&
1509                Primitive32BitCategories.contains(registerType2.category))
1510              )) {
1511
1512            throw new ValidationException(String.format("%s cannot be used on registers of dissimilar types %s and " +
1513                    "%s. They must both be a reference type or a primitive 32 bit type.",
1514                    analyzedInstruction.instruction.opcode.name, registerType1.toString(), registerType2.toString()));
1515        }
1516    }
1517
1518    private void handleIf(AnalyzedInstruction analyzedInstruction) {
1519        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1520
1521        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), Primitive32BitCategories);
1522        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), Primitive32BitCategories);
1523    }
1524
1525    private void handleIfEqzNez(AnalyzedInstruction analyzedInstruction) {
1526        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1527
1528        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
1529                ReferenceAndPrimitive32BitCategories);
1530    }
1531
1532    private void handleIfz(AnalyzedInstruction analyzedInstruction) {
1533        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1534
1535        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), Primitive32BitCategories);
1536    }
1537
1538    private void handle32BitPrimitiveAget(AnalyzedInstruction analyzedInstruction,
1539                                             RegisterType.Category instructionCategory) {
1540        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1541
1542        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1543
1544        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1545        assert arrayRegisterType != null;
1546
1547        if (arrayRegisterType.category != RegisterType.Category.Null) {
1548            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1549                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1550                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
1551            }
1552
1553            assert arrayRegisterType.type != null;
1554            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1555                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1556                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1557            }
1558
1559            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1560            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1561
1562            if (arrayClassDef.getArrayDimensions() != 1) {
1563                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
1564                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1565            }
1566
1567            RegisterType arrayBaseType =
1568                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
1569            if (checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
1570                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
1571                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1572                        arrayRegisterType.type.getClassType()));
1573            }
1574        }
1575
1576        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1577                RegisterType.getRegisterType(instructionCategory, null));
1578    }
1579
1580    private void handleAgetWide(AnalyzedInstruction analyzedInstruction) {
1581        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1582
1583        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1584
1585        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1586        assert arrayRegisterType != null;
1587
1588        if (arrayRegisterType.category != RegisterType.Category.Null) {
1589            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1590                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
1591                        arrayRegisterType.category.toString()));
1592            }
1593
1594            assert arrayRegisterType.type != null;
1595            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1596                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
1597                        arrayRegisterType.type.getClassType()));
1598            }
1599
1600            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1601            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1602
1603            if (arrayClassDef.getArrayDimensions() != 1) {
1604                throw new ValidationException(String.format("Cannot use aget-wide with multi-dimensional array type %s",
1605                        arrayRegisterType.type.getClassType()));
1606            }
1607
1608            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
1609            if (arrayBaseType == 'J') {
1610                setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1611                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1612            } else if (arrayBaseType == 'D') {
1613                setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1614                        RegisterType.getRegisterType(RegisterType.Category.DoubleLo, null));
1615            } else {
1616                throw new ValidationException(String.format("Cannot use aget-wide with array type %s. Incorrect " +
1617                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1618            }
1619        } else {
1620            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1621                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1622        }
1623    }
1624
1625    private void handleAgetObject(AnalyzedInstruction analyzedInstruction) {
1626        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1627
1628        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1629
1630        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1631        assert arrayRegisterType != null;
1632
1633        if (arrayRegisterType.category != RegisterType.Category.Null) {
1634            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1635                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1636                        arrayRegisterType.category.toString()));
1637            }
1638
1639            assert arrayRegisterType.type != null;
1640            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1641                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1642                        arrayRegisterType.type.getClassType()));
1643            }
1644
1645            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1646            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1647
1648            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
1649            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
1650            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
1651                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
1652                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1653            }
1654
1655            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1656                    RegisterType.getRegisterType(RegisterType.Category.Reference, elementClassDef));
1657        } else {
1658            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1659                    RegisterType.getRegisterType(RegisterType.Category.Null, null));
1660        }
1661    }
1662
1663    private void handle32BitPrimitiveAput(AnalyzedInstruction analyzedInstruction,
1664                                             RegisterType.Category instructionCategory) {
1665        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1666
1667        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1668
1669        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1670        assert sourceRegisterType != null;
1671        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
1672        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
1673            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
1674                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
1675        }
1676
1677
1678        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1679        assert arrayRegisterType != null;
1680
1681        if (arrayRegisterType.category != RegisterType.Category.Null) {
1682            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1683                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1684                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
1685            }
1686
1687            assert arrayRegisterType.type != null;
1688            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1689                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1690                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1691            }
1692
1693            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1694            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1695
1696            if (arrayClassDef.getArrayDimensions() != 1) {
1697                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
1698                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1699            }
1700
1701            RegisterType arrayBaseType =
1702                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
1703            if (checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
1704                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
1705                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1706                        arrayRegisterType.type.getClassType()));
1707            }
1708        }
1709    }
1710
1711    private void handleAputWide(AnalyzedInstruction analyzedInstruction) {
1712        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1713
1714        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1715        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
1716
1717        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1718        assert arrayRegisterType != null;
1719
1720        if (arrayRegisterType.category != RegisterType.Category.Null) {
1721            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1722                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
1723                        arrayRegisterType.category.toString()));
1724            }
1725
1726            assert arrayRegisterType.type != null;
1727            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1728                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
1729                        arrayRegisterType.type.getClassType()));
1730            }
1731
1732            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1733            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1734
1735            if (arrayClassDef.getArrayDimensions() != 1) {
1736                throw new ValidationException(String.format("Cannot use aput-wide with multi-dimensional array type %s",
1737                        arrayRegisterType.type.getClassType()));
1738            }
1739
1740            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
1741            if (arrayBaseType != 'J' && arrayBaseType != 'D') {
1742                throw new ValidationException(String.format("Cannot use aput-wide with array type %s. Incorrect " +
1743                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1744            }
1745        }
1746    }
1747
1748    private void handleAputObject(AnalyzedInstruction analyzedInstruction) {
1749        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1750
1751        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1752
1753        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1754        assert sourceRegisterType != null;
1755
1756        //TODO: ensure sourceRegisterType is a Reference type?
1757
1758        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1759        assert arrayRegisterType != null;
1760
1761        if (arrayRegisterType.category != RegisterType.Category.Null) {
1762            //don't check the source type against the array type, just make sure it is an array of reference types
1763
1764            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1765                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1766                        arrayRegisterType.category.toString()));
1767            }
1768
1769            assert arrayRegisterType.type != null;
1770            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1771                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1772                        arrayRegisterType.type.getClassType()));
1773            }
1774
1775            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1776            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1777
1778            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
1779            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
1780            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
1781                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
1782                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1783            }
1784        }
1785    }
1786
1787    private void handle32BitPrimitiveIget(AnalyzedInstruction analyzedInstruction,
1788                                             RegisterType.Category instructionCategory) {
1789        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1790
1791        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1792                ReferenceCategories);
1793
1794        //TODO: check access
1795        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1796        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1797        assert referencedItem instanceof FieldIdItem;
1798        FieldIdItem field = (FieldIdItem)referencedItem;
1799
1800        if (objectRegisterType.category != RegisterType.Category.Null &&
1801            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1802            throw new ValidationException(String.format("Cannot access field %s through type %s",
1803                    field.getFieldString(), objectRegisterType.type.getClassType()));
1804        }
1805
1806        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1807
1808        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
1809                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1810                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1811                        field.getFieldString()));
1812        }
1813
1814        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1815                RegisterType.getRegisterType(instructionCategory, null));
1816    }
1817
1818    private void handleIgetWide(AnalyzedInstruction analyzedInstruction) {
1819        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1820
1821        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1822                ReferenceCategories);
1823
1824        //TODO: check access
1825        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1826        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1827        assert referencedItem instanceof FieldIdItem;
1828        FieldIdItem field = (FieldIdItem)referencedItem;
1829
1830        if (objectRegisterType.category != RegisterType.Category.Null &&
1831            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1832            throw new ValidationException(String.format("Cannot access field %s through type %s",
1833                    field.getFieldString(), objectRegisterType.type.getClassType()));
1834        }
1835
1836        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1837
1838        if (!WideLowCategories.contains(fieldType.category)) {
1839            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1840                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
1841                    field.getFieldString()));
1842        }
1843
1844        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
1845    }
1846
1847    private void handleIgetObject(AnalyzedInstruction analyzedInstruction) {
1848        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1849
1850        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1851                ReferenceCategories);
1852
1853        //TODO: check access
1854        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1855        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1856        assert referencedItem instanceof FieldIdItem;
1857        FieldIdItem field = (FieldIdItem)referencedItem;
1858
1859        if (objectRegisterType.category != RegisterType.Category.Null &&
1860            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1861            throw new ValidationException(String.format("Cannot access field %s through type %s",
1862                    field.getFieldString(), objectRegisterType.type.getClassType()));
1863        }
1864
1865        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1866
1867        if (fieldType.category != RegisterType.Category.Reference) {
1868            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1869                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1870                        field.getFieldString()));
1871        }
1872
1873        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
1874    }
1875
1876    private void handle32BitPrimitiveIput(AnalyzedInstruction analyzedInstruction,
1877                                             RegisterType.Category instructionCategory) {
1878        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1879
1880        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1881                ReferenceCategories);
1882
1883        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1884        assert sourceRegisterType != null;
1885
1886        //per CodeVerify.c in dalvik:
1887        //java generates synthetic functions that write byte values into boolean fields
1888        if (sourceRegisterType.category == RegisterType.Category.Byte &&
1889            instructionCategory == RegisterType.Category.Boolean) {
1890
1891            sourceRegisterType = RegisterType.getRegisterType(RegisterType.Category.Boolean, null);
1892        }
1893
1894        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
1895        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
1896            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
1897                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
1898        }
1899
1900
1901        //TODO: check access
1902        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1903        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1904        assert referencedItem instanceof FieldIdItem;
1905        FieldIdItem field = (FieldIdItem)referencedItem;
1906
1907        if (objectRegisterType.category != RegisterType.Category.Null &&
1908            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1909            throw new ValidationException(String.format("Cannot access field %s through type %s",
1910                    field.getFieldString(), objectRegisterType.type.getClassType()));
1911        }
1912
1913        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1914
1915        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
1916                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1917                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1918                        field.getFieldString()));
1919        }
1920    }
1921
1922    private void handleIputWide(AnalyzedInstruction analyzedInstruction) {
1923        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1924
1925        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1926                ReferenceCategories);
1927
1928        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
1929
1930        //TODO: check access
1931        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1932        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1933        assert referencedItem instanceof FieldIdItem;
1934        FieldIdItem field = (FieldIdItem)referencedItem;
1935
1936        if (objectRegisterType.category != RegisterType.Category.Null &&
1937                !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1938            throw new ValidationException(String.format("Cannot access field %s through type %s",
1939                    field.getFieldString(), objectRegisterType.type.getClassType()));
1940        }
1941
1942        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1943
1944        if (!WideLowCategories.contains(fieldType.category)) {
1945            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1946                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
1947                    field.getFieldString()));
1948        }
1949    }
1950
1951    private void handleIputObject(AnalyzedInstruction analyzedInstruction) {
1952        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1953
1954        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1955                ReferenceCategories);
1956
1957        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1958                ReferenceCategories);
1959
1960        //TODO: check access
1961        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1962        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1963        assert referencedItem instanceof FieldIdItem;
1964        FieldIdItem field = (FieldIdItem)referencedItem;
1965
1966        if (objectRegisterType.category != RegisterType.Category.Null &&
1967            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1968            throw new ValidationException(String.format("Cannot access field %s through type %s",
1969                    field.getFieldString(), objectRegisterType.type.getClassType()));
1970        }
1971
1972        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1973
1974        if (fieldType.category != RegisterType.Category.Reference) {
1975            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1976                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1977                        field.getFieldString()));
1978        }
1979
1980        if (sourceRegisterType.category != RegisterType.Category.Null &&
1981            !fieldType.type.isInterface() &&
1982            !sourceRegisterType.type.extendsClass(fieldType.type)) {
1983
1984            throw new ValidationException(String.format("Cannot store a value of type %s into a field of type %s",
1985                    sourceRegisterType.type.getClassType(), fieldType.type.getClassType()));
1986        }
1987    }
1988
1989    private void handle32BitPrimitiveSget(AnalyzedInstruction analyzedInstruction,
1990                                             RegisterType.Category instructionCategory) {
1991        //TODO: check access
1992        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1993        assert referencedItem instanceof FieldIdItem;
1994        FieldIdItem field = (FieldIdItem)referencedItem;
1995
1996        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1997
1998        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
1999                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2000                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2001                        field.getFieldString()));
2002        }
2003
2004        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2005                RegisterType.getRegisterType(instructionCategory, null));
2006    }
2007
2008    private void handleSgetWide(AnalyzedInstruction analyzedInstruction) {
2009        //TODO: check access
2010        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2011        assert referencedItem instanceof FieldIdItem;
2012        FieldIdItem field = (FieldIdItem)referencedItem;
2013
2014        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2015
2016
2017        if (fieldType.category != RegisterType.Category.LongLo &&
2018            fieldType.category != RegisterType.Category.DoubleLo) {
2019
2020            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2021                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
2022                    field.getFieldString()));
2023        }
2024
2025        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2026    }
2027
2028    private void handleSgetObject(AnalyzedInstruction analyzedInstruction) {
2029        //TODO: check access
2030        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2031        assert referencedItem instanceof FieldIdItem;
2032        FieldIdItem field = (FieldIdItem)referencedItem;
2033
2034        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2035
2036        if (fieldType.category != RegisterType.Category.Reference) {
2037                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2038                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2039                        field.getFieldString()));
2040        }
2041
2042        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2043    }
2044
2045    private void handle32BitPrimitiveSput(AnalyzedInstruction analyzedInstruction,
2046                                             RegisterType.Category instructionCategory) {
2047        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2048
2049        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2050        assert sourceRegisterType != null;
2051
2052        //per CodeVerify.c in dalvik:
2053        //java generates synthetic functions that write byte values into boolean fields
2054        if (sourceRegisterType.category == RegisterType.Category.Byte &&
2055            instructionCategory == RegisterType.Category.Boolean) {
2056
2057            sourceRegisterType = RegisterType.getRegisterType(RegisterType.Category.Boolean, null);
2058        }
2059
2060        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
2061        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
2062            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
2063                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
2064        }
2065
2066        //TODO: check access
2067        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2068        assert referencedItem instanceof FieldIdItem;
2069        FieldIdItem field = (FieldIdItem)referencedItem;
2070
2071        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2072
2073        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2074                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2075                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2076                        field.getFieldString()));
2077        }
2078    }
2079
2080    private void handleSputWide(AnalyzedInstruction analyzedInstruction) {
2081        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2082
2083
2084        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
2085
2086        //TODO: check access
2087        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2088        assert referencedItem instanceof FieldIdItem;
2089        FieldIdItem field = (FieldIdItem)referencedItem;
2090
2091        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2092
2093        if (!WideLowCategories.contains(fieldType.category)) {
2094                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2095                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2096                        field.getFieldString()));
2097        }
2098
2099        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2100    }
2101
2102    private void handleSputObject(AnalyzedInstruction analyzedInstruction) {
2103        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2104
2105        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2106                ReferenceCategories);
2107
2108        //TODO: check access
2109        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2110        assert referencedItem instanceof FieldIdItem;
2111        FieldIdItem field = (FieldIdItem)referencedItem;
2112
2113        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2114
2115        if (fieldType.category != RegisterType.Category.Reference) {
2116            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2117                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2118                        field.getFieldString()));
2119        }
2120
2121        if (sourceRegisterType.category != RegisterType.Category.Null &&
2122            !fieldType.type.isInterface() &&
2123            !sourceRegisterType.type.extendsClass(fieldType.type)) {
2124
2125            throw new ValidationException(String.format("Cannot store a value of type %s into a field of type %s",
2126                    sourceRegisterType.type.getClassType(), fieldType.type.getClassType()));
2127        }
2128    }
2129
2130    private void handleInvoke(AnalyzedInstruction analyzedInstruction, int invokeType) {
2131        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
2132        handleInvokeCommon(analyzedInstruction, false, invokeType, new Format35cRegisterIterator(instruction));
2133    }
2134
2135    private void handleInvokeRange(AnalyzedInstruction analyzedInstruction, int invokeType) {
2136        RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
2137        handleInvokeCommon(analyzedInstruction, true, invokeType, new Format3rcRegisterIterator(instruction));
2138    }
2139
2140    private static final int INVOKE_VIRTUAL = 0x01;
2141    private static final int INVOKE_SUPER = 0x02;
2142    private static final int INVOKE_DIRECT = 0x04;
2143    private static final int INVOKE_INTERFACE = 0x08;
2144    private static final int INVOKE_STATIC = 0x10;
2145
2146    private void handleInvokeCommon(AnalyzedInstruction analyzedInstruction, boolean isRange, int invokeType,
2147                                       RegisterIterator registers) {
2148        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
2149
2150        //TODO: check access
2151        //TODO: allow uninitialized reference if this in an <init> method
2152
2153        Item item = instruction.getReferencedItem();
2154        assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM;
2155        MethodIdItem methodIdItem = (MethodIdItem)item;
2156
2157        TypeIdItem methodClass = methodIdItem.getContainingClass();
2158        boolean isInit = false;
2159
2160        if (methodIdItem.getMethodName().getStringValue().charAt(0) == '<') {
2161            if ((invokeType & INVOKE_DIRECT) != 0) {
2162                isInit = true;
2163            } else {
2164                throw new ValidationException(String.format("Cannot call constructor %s with %s",
2165                        methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name));
2166            }
2167        }
2168
2169        ClassPath.ClassDef methodClassDef = ClassPath.getClassDef(methodClass);
2170        if ((invokeType & INVOKE_INTERFACE) != 0) {
2171            if (!methodClassDef.isInterface()) {
2172                throw new ValidationException(String.format("Cannot call method %s with %s. %s is not an interface " +
2173                        "class.", methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name,
2174                        methodClassDef.getClassType()));
2175            }
2176        } else {
2177            if (methodClassDef.isInterface()) {
2178                throw new ValidationException(String.format("Cannot call method %s with %s. %s is an interface class." +
2179                        " Use invoke-interface or invoke-interface/range instead.", methodIdItem.getMethodString(),
2180                        analyzedInstruction.instruction.opcode.name, methodClassDef.getClassType()));
2181            }
2182        }
2183
2184        if ((invokeType & INVOKE_SUPER) != 0) {
2185            if (methodClassDef.getSuperclass() == null) {
2186                throw new ValidationException(String.format("Cannot call method %s with %s. %s has no superclass",
2187                        methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name,
2188                        methodClassDef.getSuperclass().getClassType()));
2189            }
2190
2191            if (!methodClassDef.getSuperclass().hasVirtualMethod(methodIdItem.getMethodString())) {
2192                throw new ValidationException(String.format("Cannot call method %s with %s. The superclass %s has" +
2193                        "no such method", methodIdItem.getMethodString(),
2194                        analyzedInstruction.instruction.opcode.name, methodClassDef.getSuperclass().getClassType()));
2195            }
2196        }
2197
2198        assert isRange || registers.getCount() <= 5;
2199
2200        TypeListItem typeListItem = methodIdItem.getPrototype().getParameters();
2201        int methodParameterRegisterCount;
2202        if (typeListItem == null) {
2203            methodParameterRegisterCount = 0;
2204        } else {
2205            methodParameterRegisterCount = typeListItem.getRegisterCount();
2206        }
2207
2208        if ((invokeType & INVOKE_STATIC) == 0) {
2209            methodParameterRegisterCount++;
2210        }
2211
2212        if (methodParameterRegisterCount != registers.getCount()) {
2213            throw new ValidationException(String.format("The number of registers does not match the number of " +
2214                    "parameters for method %s. Expecting %d registers, got %d.", methodIdItem.getMethodString(),
2215                    methodParameterRegisterCount + 1, registers.getCount()));
2216        }
2217
2218        RegisterType objectRegisterType = null;
2219        int objectRegister = 0;
2220        if ((invokeType & INVOKE_STATIC) == 0) {
2221            objectRegister = registers.getRegister();
2222            registers.moveNext();
2223
2224            objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(objectRegister);
2225            assert objectRegisterType != null;
2226            if (objectRegisterType.category == RegisterType.Category.UninitRef) {
2227                if (!isInit) {
2228                    throw new ValidationException(String.format("Cannot invoke non-<init> method %s on uninitialized " +
2229                            "reference type %s", methodIdItem.getMethodString(),
2230                            objectRegisterType.type.getClassType()));
2231                }
2232            } else if (objectRegisterType.category == RegisterType.Category.Reference) {
2233                if (isInit) {
2234                    throw new ValidationException(String.format("Cannot invoke %s on initialized reference type %s",
2235                            methodIdItem.getMethodString(), objectRegisterType.type.getClassType()));
2236                }
2237            } else if (objectRegisterType.category == RegisterType.Category.Null) {
2238                if (isInit) {
2239                    throw new ValidationException(String.format("Cannot invoke %s on a null reference",
2240                            methodIdItem.getMethodString()));
2241                }
2242            }
2243            else {
2244                throw new ValidationException(String.format("Cannot invoke %s on non-reference type %s",
2245                        methodIdItem.getMethodString(), objectRegisterType.toString()));
2246            }
2247
2248            if (isInit) {
2249                if (objectRegisterType.type == methodClassDef.getSuperclass()) {
2250                    if (!encodedMethod.method.getMethodName().equals("<init>")) {
2251                        throw new ValidationException(String.format("Cannot call %s on type %s. The object type must " +
2252                                "match the method type exactly", methodIdItem.getMethodString(),
2253                                objectRegisterType.type.getClassType()));
2254                    }
2255                }
2256            }
2257
2258
2259            if ((invokeType & INVOKE_INTERFACE) == 0 && !objectRegisterType.type.extendsClass(methodClassDef)) {
2260               throw new ValidationException(String.format("Cannot call method %s on an object of type %s, which " +
2261                       "does not extend %s.", methodIdItem.getMethodString(), objectRegisterType.type.getClassType(),
2262                        methodClassDef.getClassType()));
2263            }
2264        }
2265
2266        List<TypeIdItem> parameterTypes = typeListItem.getTypes();
2267        int parameterTypeIndex = 0;
2268        while (!registers.pastEnd()) {
2269            assert parameterTypeIndex < parameterTypes.size();
2270            RegisterType parameterType =
2271                    RegisterType.getRegisterTypeForTypeIdItem(parameterTypes.get(parameterTypeIndex));
2272
2273            int register = registers.getRegister();
2274
2275            RegisterType parameterRegisterType;
2276            if (WideLowCategories.contains(parameterType.category)) {
2277                parameterRegisterType = getAndCheckSourceRegister(analyzedInstruction, register, WideLowCategories);
2278
2279                if (!registers.moveNext()) {
2280                    throw new ValidationException(String.format("No 2nd register specified for wide register pair v%d",
2281                            parameterTypeIndex+1));
2282                }
2283                int nextRegister = registers.getRegister();
2284
2285                if (nextRegister != register + 1) {
2286                    throw new ValidationException(String.format("Invalid wide register pair (v%d, v%d). Registers " +
2287                            "must be consecutive.", register, nextRegister));
2288                }
2289            } else {
2290                parameterRegisterType = analyzedInstruction.getPreInstructionRegisterType(register);
2291            }
2292
2293            assert parameterRegisterType != null;
2294
2295            if (!parameterRegisterType.canBeAssignedTo(parameterType)) {
2296                throw new ValidationException(
2297                        String.format("Invalid register type %s for parameter %d %s.",
2298                                parameterRegisterType.toString(), parameterTypeIndex+1,
2299                                parameterType.toString()));
2300            }
2301
2302            parameterTypeIndex++;
2303            registers.moveNext();
2304        }
2305
2306
2307        //TODO: need to ensure the "this" register is initialized, in a constructor method
2308        if (isInit) {
2309            setRegisterTypeAndPropagateChanges(analyzedInstruction, objectRegister,
2310                    RegisterType.getRegisterType(RegisterType.Category.Reference, objectRegisterType.type));
2311
2312            for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) {
2313                RegisterType postInstructionRegisterType = analyzedInstruction.postRegisterMap[i];
2314                if (postInstructionRegisterType.category == RegisterType.Category.Unknown) {
2315                    RegisterType preInstructionRegisterType =
2316                            analyzedInstruction.getMergedRegisterTypeFromPredecessors(i);
2317
2318                    if (preInstructionRegisterType.category == RegisterType.Category.UninitRef) {
2319                        RegisterType registerType = null;
2320                        if (preInstructionRegisterType == objectRegisterType) {
2321                            registerType = analyzedInstruction.postRegisterMap[objectRegister];
2322                        } else {
2323                            registerType = preInstructionRegisterType;
2324                        }
2325
2326                        setRegisterTypeAndPropagateChanges(analyzedInstruction, i, registerType);
2327                    }
2328                }
2329            }
2330        }
2331    }
2332
2333    private void handleUnaryOp(AnalyzedInstruction analyzedInstruction, EnumSet validSourceCategories,
2334                            RegisterType.Category destRegisterCategory) {
2335        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2336
2337        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validSourceCategories);
2338
2339        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2340                RegisterType.getRegisterType(destRegisterCategory, null));
2341    }
2342
2343    private void handleBinaryOp(AnalyzedInstruction analyzedInstruction, EnumSet validSource1Categories,
2344                                EnumSet validSource2Categories, RegisterType.Category destRegisterCategory,
2345                                boolean checkForBoolean) {
2346        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2347
2348        RegisterType source1RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2349                validSource1Categories);
2350        RegisterType source2RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(),
2351                validSource2Categories);
2352
2353        if (checkForBoolean) {
2354            if (BooleanCategories.contains(source1RegisterType.category) &&
2355                BooleanCategories.contains(source2RegisterType.category)) {
2356
2357                destRegisterCategory = RegisterType.Category.Boolean;
2358            }
2359        }
2360
2361        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2362                RegisterType.getRegisterType(destRegisterCategory, null));
2363    }
2364
2365    private void handleBinary2AddrOp(AnalyzedInstruction analyzedInstruction, EnumSet validSource1Categories,
2366                                EnumSet validSource2Categories, RegisterType.Category destRegisterCategory,
2367                                boolean checkForBoolean) {
2368        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2369
2370        RegisterType source1RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2371                validSource1Categories);
2372        RegisterType source2RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2373                validSource2Categories);
2374
2375        if (checkForBoolean) {
2376            if (BooleanCategories.contains(source1RegisterType.category) &&
2377                BooleanCategories.contains(source2RegisterType.category)) {
2378
2379                destRegisterCategory = RegisterType.Category.Boolean;
2380            }
2381        }
2382
2383        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2384                RegisterType.getRegisterType(destRegisterCategory, null));
2385    }
2386
2387    private static boolean checkArrayFieldAssignment(RegisterType.Category arrayFieldCategory,
2388                                                  RegisterType.Category instructionCategory) {
2389        if (arrayFieldCategory == instructionCategory) {
2390            return true;
2391        }
2392
2393        if ((arrayFieldCategory == RegisterType.Category.Integer &&
2394             instructionCategory == RegisterType.Category.Float) ||
2395            (arrayFieldCategory == RegisterType.Category.Float &&
2396             instructionCategory == RegisterType.Category.Integer)) {
2397            return true;
2398        }
2399        return false;
2400    }
2401
2402    private static RegisterType getAndCheckSourceRegister(AnalyzedInstruction analyzedInstruction, int registerNumber,
2403                                            EnumSet validCategories) {
2404        assert registerNumber >= 0 && registerNumber < analyzedInstruction.postRegisterMap.length;
2405
2406        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(registerNumber);
2407        assert registerType != null;
2408
2409        checkRegister(registerType, registerNumber, validCategories);
2410
2411        if (validCategories == WideLowCategories) {
2412            checkRegister(registerType, registerNumber, WideLowCategories);
2413            checkWidePair(registerNumber, analyzedInstruction);
2414
2415            RegisterType secondRegisterType = analyzedInstruction.getPreInstructionRegisterType(registerNumber + 1);
2416            assert secondRegisterType != null;
2417            checkRegister(secondRegisterType, registerNumber+1, WideHighCategories);
2418        }
2419
2420        return registerType;
2421    }
2422
2423    private static void checkRegister(RegisterType registerType, int registerNumber, EnumSet validCategories) {
2424        if (!validCategories.contains(registerType.category)) {
2425            //TODO: add expected categories to error message
2426            throw new ValidationException(String.format("Invalid register type for register v%d. Expecting one of: " +
2427                    "but got %s", registerNumber, registerType.toString()));
2428        }
2429    }
2430
2431    private static void checkWidePair(int registerNumber, AnalyzedInstruction analyzedInstruction) {
2432        if (registerNumber + 1 >= analyzedInstruction.postRegisterMap.length) {
2433            throw new ValidationException(String.format("v%d is the last register and not a valid wide register " +
2434                    "pair.", registerNumber));
2435        }
2436    }
2437}
2438