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