MethodAnalyzer.java revision f1a74cea19f10e9059e05f1cee6ae45baf118108 
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        }
488        assert false;
489        return false;
490    }
491
492    private static final EnumSet<RegisterType.Category> Primitive32BitCategories = EnumSet.of(
493            RegisterType.Category.Null,
494            RegisterType.Category.Boolean,
495            RegisterType.Category.Byte,
496            RegisterType.Category.Short,
497            RegisterType.Category.Char,
498            RegisterType.Category.Integer,
499            RegisterType.Category.Float);
500
501    private static final EnumSet<RegisterType.Category> WideLowCategories = EnumSet.of(
502            RegisterType.Category.LongLo,
503            RegisterType.Category.DoubleLo);
504
505    private static final EnumSet<RegisterType.Category> WideHighCategories = EnumSet.of(
506            RegisterType.Category.LongHi,
507            RegisterType.Category.DoubleHi);
508
509    private static final EnumSet<RegisterType.Category> ReferenceCategories = EnumSet.of(
510            RegisterType.Category.Null,
511            RegisterType.Category.Reference);
512
513    private boolean handleMove(AnalyzedInstruction analyzedInstruction,
514                               EnumSet<RegisterType.Category> allowedCategories) {
515        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
516
517        //get the "pre-instruction" register type for the source register
518        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
519        assert sourceRegisterType != null;
520
521        if (sourceRegisterType.category == RegisterType.Category.Unknown) {
522            //we don't know the source register type yet, so we can't verify it. Return false, and we'll come back later
523            return false;
524        }
525
526        checkRegister(sourceRegisterType, allowedCategories);
527
528        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
529        return true;
530    }
531
532    private boolean handleMoveWide(AnalyzedInstruction analyzedInstruction) {
533        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
534
535        RegisterType sourceRegisterType = getAndCheckWideSourcePair(analyzedInstruction,
536                instruction.getRegisterB());
537        assert sourceRegisterType != null;
538
539        if (sourceRegisterType.category == RegisterType.Category.Unknown) {
540            //we don't know the source register type yet, so we can't verify it. Return false, and we'll come back later
541            return false;
542        }
543
544        checkWideDestinationPair(analyzedInstruction);
545
546        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
547        return true;
548    }
549
550    private boolean handleMoveResult(AnalyzedInstruction analyzedInstruction,
551                                     EnumSet<RegisterType.Category> allowedCategories) {
552
553        //TODO: handle the case when the previous instruction is an odexed instruction
554
555        if (analyzedInstruction.instructionIndex == 0) {
556            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " cannot be the first " +
557                    "instruction in a method. It must occur after an invoke-*/fill-new-array instruction");
558        }
559
560        AnalyzedInstruction previousInstruction = instructions.valueAt(analyzedInstruction.instructionIndex-1);
561
562        if (!previousInstruction.instruction.opcode.setsResult()) {
563            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " must occur after an " +
564                    "invoke-*/fill-new-array instruction");
565        }
566
567        if (analyzedInstruction.instruction.opcode.setsWideRegister()) {
568            checkWideDestinationPair(analyzedInstruction);
569        }
570
571        //TODO: does dalvik allow a move-result after an invoke with a void return type?
572        RegisterType destinationRegisterType;
573
574        InstructionWithReference invokeInstruction = (InstructionWithReference)previousInstruction.instruction;
575        Item item = invokeInstruction.getReferencedItem();
576
577        if (item instanceof MethodIdItem) {
578            destinationRegisterType = RegisterType.getRegisterTypeForTypeIdItem(
579                    ((MethodIdItem)item).getPrototype().getReturnType());
580        } else {
581            assert item instanceof TypeIdItem;
582            destinationRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
583        }
584
585        checkRegister(destinationRegisterType, allowedCategories);
586        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destinationRegisterType);
587        return true;
588    }
589
590    private boolean handleMoveException(AnalyzedInstruction analyzedInstruction) {
591        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
592        int instructionAddress = getInstructionAddress(analyzedInstruction);
593
594        if (tries == null) {
595            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
596        }
597
598        RegisterType exceptionType = null;
599
600        for (CodeItem.TryItem tryItem: encodedMethod.codeItem.getTries()) {
601            if (tryItem.encodedCatchHandler.getCatchAllHandlerAddress() == instructionAddress) {
602                exceptionType = RegisterType.getRegisterType(RegisterType.Category.Reference,
603                        ClassPath.getClassDef("Ljava/lang/Throwable;"));
604                break;
605            }
606            for (CodeItem.EncodedTypeAddrPair handler: tryItem.encodedCatchHandler.handlers) {
607                if (handler.getHandlerAddress() == instructionAddress) {
608                    exceptionType = RegisterType.getRegisterTypeForTypeIdItem(handler.exceptionType)
609                            .merge(exceptionType);
610                }
611            }
612        }
613
614        //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)
615        checkRegister(exceptionType, ReferenceCategories);
616        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, exceptionType);
617        return true;
618    }
619
620    private boolean checkConstructorReturn(AnalyzedInstruction analyzedInstruction) {
621        assert this.isInstanceConstructor();
622
623        //if we're in an instance constructor (an <init> method), then the superclass <init> must have been called.
624        //When execution enters the method, the "this" register is set as an uninitialized reference to the containing
625        //class. Once the superclass' <init> is called, the "this" register is upgraded to a full-blown reference type,
626        //so we need to ensure that the "this" register isn't an uninitialized reference
627
628        int thisRegister = getThisRegister();
629        RegisterType thisRegisterType = analyzedInstruction.postRegisterMap[thisRegister];
630
631        if (thisRegisterType.category == RegisterType.Category.Unknown) {
632            //we don't have enough information yet, so return false. We'll come back later
633            return false;
634        }
635        if (thisRegisterType.category == RegisterType.Category.UninitRef) {
636            throw new ValidationException("Returning from constructor without calling the superclass' <init>");
637        }
638        assert thisRegisterType.category == RegisterType.Category.Reference;
639        assert thisRegisterType.type == ClassPath.getClassDef(encodedMethod.method.getContainingClass());
640        return true;
641    }
642
643    private boolean handleReturnVoid(AnalyzedInstruction analyzedInstruction) {
644        if (this.isInstanceConstructor()) {
645            if (!checkConstructorReturn(analyzedInstruction)) {
646                return false;
647            }
648        }
649
650        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
651        if (returnType.getTypeDescriptor().charAt(0) != 'V') {
652            //TODO: could add which return-* variation should be used instead
653            throw new ValidationException("Cannot use return-void with a non-void return type (" +
654                returnType.getTypeDescriptor() + ")");
655        }
656        return true;
657    }
658
659    private boolean handleReturn(AnalyzedInstruction analyzedInstruction) {
660        if (this.isInstanceConstructor()) {
661            if (!checkConstructorReturn(analyzedInstruction)) {
662                return false;
663            }
664        }
665
666        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
667        RegisterType returnRegisterType = analyzedInstruction.postRegisterMap[instruction.getRegisterA()];
668
669        if (returnRegisterType.category == RegisterType.Category.Unknown) {
670            return false;
671        }
672
673        checkRegister(returnRegisterType, Primitive32BitCategories);
674
675        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
676        if (returnType.getTypeDescriptor().charAt(0) == 'V') {
677            throw new ValidationException("Cannot use return with a void return type. Use return-void instead");
678        }
679
680        RegisterType registerType = RegisterType.getRegisterTypeForTypeIdItem(returnType);
681
682        if (!Primitive32BitCategories.contains(registerType.category)) {
683            //TODO: could add which return-* variation should be used instead
684            throw new ValidationException("Cannot use return with return type " + returnType.getTypeDescriptor());
685        }
686
687
688        return true;
689    }
690
691    private boolean handleReturnWide(AnalyzedInstruction analyzedInstruction) {
692        if (this.isInstanceConstructor()) {
693            if (!checkConstructorReturn(analyzedInstruction)) {
694                return false;
695            }
696        }
697
698        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
699        RegisterType returnType = getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterA());
700
701        if (returnType.category == RegisterType.Category.Unknown) {
702            return false;
703        }
704
705
706        TypeIdItem returnTypeIdItem = encodedMethod.method.getPrototype().getReturnType();
707        if (returnTypeIdItem.getTypeDescriptor().charAt(0) == 'V') {
708            throw new ValidationException("Cannot use return-wide with a void return type. Use return-void instead");
709        }
710
711        returnType = RegisterType.getRegisterTypeForTypeIdItem(returnTypeIdItem);
712        if (!WideLowCategories.contains(returnType.category)) {
713            //TODO: could add which return-* variation should be used instead
714            throw new ValidationException("Cannot use return-wide with return type " +
715                    returnTypeIdItem.getTypeDescriptor());
716        }
717
718        return true;
719    }
720
721    private boolean handleReturnObject(AnalyzedInstruction analyzedInstruction) {
722        if (this.isInstanceConstructor()) {
723            if (!checkConstructorReturn(analyzedInstruction)) {
724                return false;
725            }
726        }
727
728        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
729        int returnRegister = instruction.getRegisterA();
730        RegisterType returnRegisterType = analyzedInstruction.postRegisterMap[returnRegister];
731
732        if (returnRegisterType.category == RegisterType.Category.Unknown) {
733            return false;
734        }
735
736        checkRegister(returnRegisterType, ReferenceCategories);
737
738
739        TypeIdItem returnTypeIdItem = encodedMethod.method.getPrototype().getReturnType();
740        if (returnTypeIdItem.getTypeDescriptor().charAt(0) == 'V') {
741            throw new ValidationException("Cannot use return with a void return type. Use return-void instead");
742        }
743
744        RegisterType returnType = RegisterType.getRegisterTypeForTypeIdItem(returnTypeIdItem);
745
746        if (!ReferenceCategories.contains(returnType.category)) {
747            //TODO: could add which return-* variation should be used instead
748            throw new ValidationException("Cannot use " + analyzedInstruction + " with return type " +
749                    returnTypeIdItem.getTypeDescriptor());
750        }
751
752        if (returnType.type.isInterface()) {
753            if (!returnRegisterType.type.implementsInterface(returnType.type)) {
754                //TODO: how to handle warnings?
755            }
756        } else {
757            if (!returnRegisterType.type.extendsClass(returnType.type)) {
758                throw new ValidationException("The return value in register v" + Integer.toString(returnRegister) +
759                        "(" + returnRegisterType.type.getClassType() + ") is not compatible with the method's return " +
760                        "type (" + returnType.type.getClassType() + ")");
761            }
762        }
763
764        return true;
765    }
766
767    private boolean handleConst(AnalyzedInstruction analyzedInstruction) {
768        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
769
770        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(instruction.getLiteral());
771
772        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
773        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
774        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
775        return true;
776    }
777
778    private boolean handleConstHigh16(AnalyzedInstruction analyzedInstruction) {
779        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
780
781        //TODO: test this
782        long literalValue = instruction.getLiteral() << 16;
783        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(literalValue);
784
785        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
786        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
787        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
788        return true;
789    }
790
791    private boolean handleWideConst(AnalyzedInstruction analyzedInstruction) {
792        setWideDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
793                RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
794        return true;
795    }
796
797    private boolean handleConstString(AnalyzedInstruction analyzedInstruction) {
798        ClassPath.ClassDef stringClassDef = ClassPath.getClassDef("Ljava/lang/String;");
799        RegisterType stringType = RegisterType.getRegisterType(RegisterType.Category.Reference, stringClassDef);
800        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, stringType);
801        return true;
802    }
803
804    private boolean handleConstClass(AnalyzedInstruction analyzedInstruction) {
805        ClassPath.ClassDef classClassDef = ClassPath.getClassDef("Ljava/lang/Class;");
806        RegisterType classType = RegisterType.getRegisterType(RegisterType.Category.Reference, classClassDef);
807
808        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
809        Item item = instruction.getReferencedItem();
810        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
811
812        //make sure the referenced class is resolvable
813        //TODO: need to check class access
814        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
815        return false;
816    }
817
818    private boolean handleMonitor(AnalyzedInstruction analyzedInstruction) {
819        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction;
820
821        RegisterType registerType = analyzedInstruction.postRegisterMap[instruction.getRegisterA()];
822        assert registerType != null;
823        if (registerType.category == RegisterType.Category.Unknown) {
824            return false;
825        }
826
827        checkRegister(registerType, ReferenceCategories);
828        return true;
829    }
830
831    private boolean handleCheckCast(AnalyzedInstruction analyzedInstruction) {
832        {
833            //ensure the "source" register is a reference type
834            SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
835
836            RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
837            assert registerType != null;
838            if (registerType.category == RegisterType.Category.Unknown) {
839                return false;
840            }
841
842            checkRegister(registerType, ReferenceCategories);
843        }
844
845        {
846            //resolve and verify the class that we're casting to
847            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
848
849            Item item = instruction.getReferencedItem();
850            assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
851
852            //TODO: need to check class access
853            RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
854            try {
855                checkRegister(newDestinationRegisterType, ReferenceCategories);
856            } catch (ValidationException ex) {
857                //TODO: verify that dalvik allows a non-reference type..
858                //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)
859            }
860
861            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
862            return true;
863        }
864    }
865
866    private boolean handleInstanceOf(AnalyzedInstruction analyzedInstruction) {
867        {
868            //ensure the register that is being checks is a reference type
869            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction;
870
871            RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
872            assert registerType != null;
873            if (registerType.category == RegisterType.Category.Unknown) {
874                return false;
875            }
876
877            checkRegister(registerType, ReferenceCategories);
878        }
879
880        {
881            //resolve and verify the class that we're checking against
882            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
883
884            Item item = instruction.getReferencedItem();
885            assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
886            RegisterType registerType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
887            checkRegister(registerType, ReferenceCategories);
888
889            //TODO: is it valid to use an array type?
890
891            //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.
892            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
893                    RegisterType.getRegisterType(RegisterType.Category.Boolean, null));
894            return true;
895        }
896    }
897
898    private boolean handleArrayLength(AnalyzedInstruction analyzedInstruction) {
899        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction;
900
901        int arrayRegisterNumber = instruction.getRegisterB();
902        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(arrayRegisterNumber);
903        assert arrayRegisterType != null;
904        if (arrayRegisterType.category == RegisterType.Category.Unknown) {
905            return false;
906        }
907
908        assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
909
910        checkRegister(arrayRegisterType, ReferenceCategories);
911        if (arrayRegisterType.type != null) {
912            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
913                throw new ValidationException("Cannot use array-length with non-array type " +
914                        arrayRegisterType.type.getClassType());
915            }
916        }
917
918        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
919                RegisterType.getRegisterType(RegisterType.Category.Integer, null));
920        return true;
921    }
922
923    private boolean handleNewInstance(AnalyzedInstruction analyzedInstruction) {
924        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
925
926        Item item = instruction.getReferencedItem();
927        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
928
929        //TODO: need to check class access
930        RegisterType classType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
931        checkRegister(classType, ReferenceCategories);
932        if (((TypeIdItem)item).getTypeDescriptor().charAt(0) == '[') {
933            throw new ValidationException("Cannot use array type \"" + ((TypeIdItem)item).getTypeDescriptor() +
934                    "\" with new-instance. Use new-array instead.");
935        }
936
937        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
938                RegisterType.getRegisterType(RegisterType.Category.UninitRef, classType.type));
939        return true;
940    }
941
942    private boolean handleNewArray(AnalyzedInstruction analyzedInstruction) {
943        {
944            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
945
946            int sizeRegister = instruction.getRegisterB();
947            RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(sizeRegister);
948            assert registerType != null;
949
950            if (registerType.category == RegisterType.Category.Unknown) {
951                return false;
952            }
953
954            checkRegister(registerType, Primitive32BitCategories);
955        }
956
957        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
958
959        Item item = instruction.getReferencedItem();
960        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
961
962        RegisterType arrayType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
963        assert arrayType.type instanceof ClassPath.ArrayClassDef;
964
965        checkRegister(arrayType, ReferenceCategories);
966        if (arrayType.type.getClassType().charAt(0) != '[') {
967            throw new ValidationException("Cannot use non-array type \"" + arrayType.type.getClassType() +
968                    "\" with new-array. Use new-instance instead.");
969        }
970
971        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
972        return true;
973    }
974
975    private static interface RegisterIterator {
976        int getRegister();
977        boolean moveNext();
978    }
979
980    private boolean handleFilledNewArrayCommon(AnalyzedInstruction analyzedInstruction,
981                                               RegisterIterator registerIterator) {
982        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
983
984        RegisterType arrayType;
985        RegisterType arrayImmediateElementType;
986
987        Item item = instruction.getReferencedItem();
988        assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
989
990        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
991
992        if (classDef.getClassType().charAt(0) != '[') {
993            throw new ValidationException("Cannot use non-array type \"" + classDef.getClassType() +
994                "\" with new-array. Use new-instance instead.");
995        }
996
997        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)classDef;
998        arrayType = RegisterType.getRegisterType(RegisterType.Category.Reference, classDef);
999        arrayImmediateElementType = RegisterType.getRegisterTypeForType(
1000                arrayClassDef.getImmediateElementClass().getClassType());
1001        String baseElementType = arrayClassDef.getBaseElementClass().getClassType();
1002        if (baseElementType.charAt(0) == 'J' || baseElementType.charAt(0) == 'D') {
1003            throw new ValidationException("Cannot use filled-new-array to create an array of wide values " +
1004                    "(long or double)");
1005        }
1006
1007        do {
1008            int register = registerIterator.getRegister();
1009            RegisterType elementType = analyzedInstruction.getPreInstructionRegisterType(register);
1010            assert elementType != null;
1011
1012            if (elementType.category == RegisterType.Category.Unknown) {
1013                return false;
1014            }
1015
1016            if (!elementType.canBeAssignedTo(arrayImmediateElementType)) {
1017                throw new ValidationException("Register v" + Integer.toString(register) + " is of type " +
1018                        elementType.toString() + " and is incompatible with the array type " +
1019                        arrayType.type.getClassType());
1020            }
1021        } while (registerIterator.moveNext());
1022
1023        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1024        return true;
1025    }
1026
1027    private boolean handleFilledNewArray(AnalyzedInstruction analyzedInstruction) {
1028        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
1029        final int registerCount = instruction.getRegCount();
1030        final int[] registers = new int[]{instruction.getRegisterD(), instruction.getRegisterE(),
1031                                          instruction.getRegisterF(), instruction.getRegisterG(),
1032                                          instruction.getRegisterA()};
1033
1034        return handleFilledNewArrayCommon(analyzedInstruction,
1035                new RegisterIterator() {
1036                    private int currentRegister = 0;
1037                    public int getRegister() {
1038                        return registers[currentRegister];
1039                    }
1040
1041                    public boolean moveNext() {
1042                        currentRegister++;
1043                        if (currentRegister >= registerCount) {
1044                            return false;
1045                        }
1046                        return true;
1047                    }
1048                });
1049    }
1050
1051    private boolean handleFilledNewArrayRange(AnalyzedInstruction analyzedInstruction) {
1052        final RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
1053
1054        //instruction.getStartRegister() and instruction.getRegCount() both return an int value, but are actually
1055        //unsigned 16 bit values, so we don't have to worry about overflowing an int when adding them together
1056        if (instruction.getStartRegister() + instruction.getRegCount() >= 1<<16) {
1057            throw new ValidationException(String.format("Invalid register range {v%d .. v%d}. The ending register " +
1058                    "is larger than the largest allowed register of v65535.",
1059                    instruction.getStartRegister(),
1060                    instruction.getStartRegister() + instruction.getRegCount() - 1));
1061        }
1062
1063        return handleFilledNewArrayCommon(analyzedInstruction,
1064                new RegisterIterator() {
1065                    private int currentRegister = 0;
1066                    private final int startRegister = instruction.getStartRegister();
1067                    private final int registerCount = instruction.getRegCount();
1068
1069                    public int getRegister() {
1070                        return startRegister + currentRegister;
1071                    }
1072
1073                    public boolean moveNext() {
1074                        currentRegister++;
1075                        if (currentRegister >= registerCount) {
1076                            return false;
1077                        }
1078                        return true;
1079                    }
1080                });
1081    }
1082
1083    private boolean handleFillArrayData(AnalyzedInstruction analyzedInstruction) {
1084        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1085
1086        int register = instruction.getRegisterA();
1087        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1088        assert registerType != null;
1089
1090        if (registerType.category == RegisterType.Category.Unknown ||
1091            registerType.category == RegisterType.Category.Null) {
1092            return false;
1093        }
1094
1095        if (registerType.category != RegisterType.Category.Reference) {
1096            throw new ValidationException(String.format("Cannot use fill-array-data with non-array register v%d of " +
1097                    "type %s", register, registerType.toString()));
1098        }
1099
1100        assert registerType.type instanceof ClassPath.ArrayClassDef;
1101        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)registerType.type;
1102
1103        if (arrayClassDef.getArrayDimensions() != 1) {
1104            throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can only " +
1105                    "be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1106        }
1107
1108        int elementWidth;
1109        switch (arrayClassDef.getBaseElementClass().getClassType().charAt(0)) {
1110            case 'Z':
1111            case 'B':
1112                elementWidth = 1;
1113                break;
1114            case 'C':
1115            case 'S':
1116                elementWidth = 2;
1117                break;
1118            case 'I':
1119            case 'F':
1120                elementWidth = 4;
1121                break;
1122            case 'J':
1123            case 'D':
1124                elementWidth = 8;
1125                break;
1126            default:
1127                throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can " +
1128                        "only be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1129        }
1130
1131
1132        int arrayDataAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1133        int arrayDataCodeAddress = getInstructionAddress(analyzedInstruction) + arrayDataAddressOffset;
1134        AnalyzedInstruction arrayDataInstruction = this.instructions.get(arrayDataCodeAddress);
1135        if (arrayDataInstruction == null || arrayDataInstruction.instruction.getFormat() != Format.ArrayData) {
1136            throw new ValidationException(String.format("Could not find an array data structure at code address 0x%x",
1137                    arrayDataCodeAddress));
1138        }
1139
1140        ArrayDataPseudoInstruction arrayDataPseudoInstruction =
1141                (ArrayDataPseudoInstruction)arrayDataInstruction.instruction;
1142
1143        if (elementWidth != arrayDataPseudoInstruction.getElementWidth()) {
1144            throw new ValidationException(String.format("The array data at code address 0x%x does not have the " +
1145                    "correct element width for array type %s. Expecting element width %d, got element width %d.",
1146                    arrayDataCodeAddress, arrayClassDef.getClassType(), elementWidth,
1147                    arrayDataPseudoInstruction.getElementWidth()));
1148        }
1149
1150        return true;
1151    }
1152
1153    private boolean handleThrow(AnalyzedInstruction analyzedInstruction) {
1154        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1155
1156        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1157        assert registerType != null;
1158
1159        if (registerType.category == RegisterType.Category.Unknown) {
1160            return false;
1161        }
1162
1163        if (registerType.category == RegisterType.Category.Null) {
1164            return true;
1165        }
1166
1167        if (registerType.category != RegisterType.Category.Reference) {
1168            throw new ValidationException(String.format("Cannot use throw with non-reference type %s in register v%d",
1169                    registerType.toString(), register));
1170        }
1171
1172        assert registerType.type != null;
1173
1174        if (!registerType.type.extendsClass(ClassPath.getClassDef("Ljava/lang/Throwable;"))) {
1175            throw new ValidationException(String.format("Cannot use throw with non-throwable type %s in register v%d",
1176                    registerType.type.getClassType(), register));
1177        }
1178
1179        return true;
1180    }
1181
1182    private boolean handleSwitch(AnalyzedInstruction analyzedInstruction, Format expectedSwitchDataFormat) {
1183        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1184        int switchCodeAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1185
1186        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1187        assert registerType != null;
1188
1189        if (registerType.category == RegisterType.Category.Unknown) {
1190            return false;
1191        }
1192
1193        checkRegister(registerType, Primitive32BitCategories);
1194
1195        int switchDataCodeAddress = this.getInstructionAddress(analyzedInstruction) + switchCodeAddressOffset;
1196        AnalyzedInstruction switchDataAnalyzedInstruction = instructions.get(switchDataCodeAddress);
1197
1198        if (switchDataAnalyzedInstruction == null ||
1199            switchDataAnalyzedInstruction.instruction.getFormat() != expectedSwitchDataFormat) {
1200            throw new ValidationException(String.format("There is no %s structure at code address 0x%x",
1201                    expectedSwitchDataFormat.name(), switchDataCodeAddress));
1202        }
1203
1204        return true;
1205    }
1206
1207    private boolean handleFloatCmp(AnalyzedInstruction analyzedInstruction) {
1208        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1209
1210        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1211        assert registerType != null;
1212
1213        if (registerType.category == RegisterType.Category.Unknown) {
1214            return false;
1215        }
1216        checkRegister(registerType, Primitive32BitCategories);
1217
1218        registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1219        assert registerType != null;
1220
1221        if (registerType.category == RegisterType.Category.Unknown) {
1222            return false;
1223        }
1224        checkRegister(registerType, Primitive32BitCategories);
1225
1226        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1227                RegisterType.getRegisterType(RegisterType.Category.Byte, null));
1228        return true;
1229    }
1230
1231    private boolean handleWideCmp(AnalyzedInstruction analyzedInstruction) {
1232        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1233
1234        RegisterType registerType = getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterB());
1235        assert registerType != null;
1236        if (registerType.category == RegisterType.Category.Unknown) {
1237            return false;
1238        }
1239
1240        registerType = getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterC());
1241        assert registerType != null;
1242        if (registerType.category == RegisterType.Category.Unknown) {
1243            return false;
1244        }
1245
1246        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1247                RegisterType.getRegisterType(RegisterType.Category.Byte, null));
1248        return true;
1249    }
1250
1251    private static void checkRegister(RegisterType registerType, EnumSet validCategories) {
1252        if (!validCategories.contains(registerType.category)) {
1253            //TODO: add expected categories to error message
1254            throw new ValidationException("Invalid register type. Expecting one of: " + " but got \"" +
1255                    registerType.category + "\"");
1256        }
1257    }
1258
1259    private static void checkWideDestinationPair(AnalyzedInstruction analyzedInstruction) {
1260        int register = analyzedInstruction.getDestinationRegister();
1261
1262        if (register == (analyzedInstruction.postRegisterMap.length - 1)) {
1263            throw new ValidationException("v" + register + " is the last register and not a valid wide register " +
1264                    "pair.");
1265        }
1266    }
1267
1268    private static RegisterType getAndCheckWideSourcePair(AnalyzedInstruction analyzedInstruction, int firstRegister) {
1269        assert firstRegister >= 0 && firstRegister < analyzedInstruction.postRegisterMap.length;
1270
1271        if (firstRegister == analyzedInstruction.postRegisterMap.length - 1) {
1272            throw new ValidationException("v" + firstRegister + " is the last register and not a valid wide register " +
1273                    "pair.");
1274        }
1275
1276        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(firstRegister);
1277        assert registerType != null;
1278        if (registerType.category == RegisterType.Category.Unknown) {
1279            return registerType;
1280        }
1281        checkRegister(registerType, WideLowCategories);
1282
1283        RegisterType secondRegisterType = analyzedInstruction.getPreInstructionRegisterType(firstRegister + 1);
1284        assert secondRegisterType != null;
1285        checkRegister(secondRegisterType, WideHighCategories);
1286
1287        if ((       registerType.category == RegisterType.Category.LongLo &&
1288                    secondRegisterType.category == RegisterType.Category.DoubleHi)
1289            ||  (   registerType.category == RegisterType.Category.DoubleLo &&
1290                    secondRegisterType.category == RegisterType.Category.LongHi)) {
1291            assert false;
1292            throw new ValidationException("The first register in the wide register pair isn't the same type (long " +
1293                    "vs. double) as the second register in the pair");
1294        }
1295
1296        return registerType;
1297    }
1298}
1299