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