MethodAnalyzer.java revision 9971346f4ce431e103c900cfdc14299ea25c685d 
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        }
556
557        assert false;
558        return false;
559    }
560
561    private static final EnumSet<RegisterType.Category> Primitive32BitCategories = EnumSet.of(
562            RegisterType.Category.Null,
563            RegisterType.Category.Boolean,
564            RegisterType.Category.Byte,
565            RegisterType.Category.Short,
566            RegisterType.Category.Char,
567            RegisterType.Category.Integer,
568            RegisterType.Category.Float);
569
570    private static final EnumSet<RegisterType.Category> WideLowCategories = EnumSet.of(
571            RegisterType.Category.LongLo,
572            RegisterType.Category.DoubleLo);
573
574    private static final EnumSet<RegisterType.Category> WideHighCategories = EnumSet.of(
575            RegisterType.Category.LongHi,
576            RegisterType.Category.DoubleHi);
577
578    private static final EnumSet<RegisterType.Category> ReferenceCategories = EnumSet.of(
579            RegisterType.Category.Null,
580            RegisterType.Category.Reference);
581
582    private boolean handleMove(AnalyzedInstruction analyzedInstruction,
583                               EnumSet<RegisterType.Category> allowedCategories) {
584        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
585
586        //get the "pre-instruction" register type for the source register
587        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
588        assert sourceRegisterType != null;
589
590        if (sourceRegisterType.category == RegisterType.Category.Unknown) {
591            //we don't know the source register type yet, so we can't verify it. Return false, and we'll come back later
592            return false;
593        }
594
595        checkRegister(sourceRegisterType, allowedCategories);
596
597        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
598        return true;
599    }
600
601    private boolean handleMoveWide(AnalyzedInstruction analyzedInstruction) {
602        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
603
604        RegisterType sourceRegisterType = getAndCheckWideSourcePair(analyzedInstruction,
605                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        checkWideDestinationPair(analyzedInstruction);
614
615        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
616        return true;
617    }
618
619    private boolean handleMoveResult(AnalyzedInstruction analyzedInstruction,
620                                     EnumSet<RegisterType.Category> allowedCategories) {
621
622        //TODO: handle the case when the previous instruction is an odexed instruction
623
624        if (analyzedInstruction.instructionIndex == 0) {
625            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " cannot be the first " +
626                    "instruction in a method. It must occur after an invoke-*/fill-new-array instruction");
627        }
628
629        AnalyzedInstruction previousInstruction = instructions.valueAt(analyzedInstruction.instructionIndex-1);
630
631        if (!previousInstruction.instruction.opcode.setsResult()) {
632            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " must occur after an " +
633                    "invoke-*/fill-new-array instruction");
634        }
635
636        if (analyzedInstruction.instruction.opcode.setsWideRegister()) {
637            checkWideDestinationPair(analyzedInstruction);
638        }
639
640        //TODO: does dalvik allow a move-result after an invoke with a void return type?
641        RegisterType destinationRegisterType;
642
643        InstructionWithReference invokeInstruction = (InstructionWithReference)previousInstruction.instruction;
644        Item item = invokeInstruction.getReferencedItem();
645
646        if (item instanceof MethodIdItem) {
647            destinationRegisterType = RegisterType.getRegisterTypeForTypeIdItem(
648                    ((MethodIdItem)item).getPrototype().getReturnType());
649        } else {
650            assert item instanceof TypeIdItem;
651            destinationRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
652        }
653
654        checkRegister(destinationRegisterType, allowedCategories);
655        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destinationRegisterType);
656        return true;
657    }
658
659    private boolean handleMoveException(AnalyzedInstruction analyzedInstruction) {
660        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
661        int instructionAddress = getInstructionAddress(analyzedInstruction);
662
663        if (tries == null) {
664            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
665        }
666
667        RegisterType exceptionType = null;
668
669        for (CodeItem.TryItem tryItem: encodedMethod.codeItem.getTries()) {
670            if (tryItem.encodedCatchHandler.getCatchAllHandlerAddress() == instructionAddress) {
671                exceptionType = RegisterType.getRegisterType(RegisterType.Category.Reference,
672                        ClassPath.getClassDef("Ljava/lang/Throwable;"));
673                break;
674            }
675            for (CodeItem.EncodedTypeAddrPair handler: tryItem.encodedCatchHandler.handlers) {
676                if (handler.getHandlerAddress() == instructionAddress) {
677                    exceptionType = RegisterType.getRegisterTypeForTypeIdItem(handler.exceptionType)
678                            .merge(exceptionType);
679                }
680            }
681        }
682
683        //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)
684        checkRegister(exceptionType, ReferenceCategories);
685        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, exceptionType);
686        return true;
687    }
688
689    private boolean checkConstructorReturn(AnalyzedInstruction analyzedInstruction) {
690        assert this.isInstanceConstructor();
691
692        //if we're in an instance constructor (an <init> method), then the superclass <init> must have been called.
693        //When execution enters the method, the "this" register is set as an uninitialized reference to the containing
694        //class. Once the superclass' <init> is called, the "this" register is upgraded to a full-blown reference type,
695        //so we need to ensure that the "this" register isn't an uninitialized reference
696
697        int thisRegister = getThisRegister();
698        RegisterType thisRegisterType = analyzedInstruction.postRegisterMap[thisRegister];
699
700        if (thisRegisterType.category == RegisterType.Category.Unknown) {
701            //we don't have enough information yet, so return false. We'll come back later
702            return false;
703        }
704        if (thisRegisterType.category == RegisterType.Category.UninitRef) {
705            throw new ValidationException("Returning from constructor without calling the superclass' <init>");
706        }
707        assert thisRegisterType.category == RegisterType.Category.Reference;
708        assert thisRegisterType.type == ClassPath.getClassDef(encodedMethod.method.getContainingClass());
709        return true;
710    }
711
712    private boolean handleReturnVoid(AnalyzedInstruction analyzedInstruction) {
713        if (this.isInstanceConstructor()) {
714            if (!checkConstructorReturn(analyzedInstruction)) {
715                return false;
716            }
717        }
718
719        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
720        if (returnType.getTypeDescriptor().charAt(0) != 'V') {
721            //TODO: could add which return-* variation should be used instead
722            throw new ValidationException("Cannot use return-void with a non-void return type (" +
723                returnType.getTypeDescriptor() + ")");
724        }
725        return true;
726    }
727
728    private boolean handleReturn(AnalyzedInstruction analyzedInstruction) {
729        if (this.isInstanceConstructor()) {
730            if (!checkConstructorReturn(analyzedInstruction)) {
731                return false;
732            }
733        }
734
735        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
736        RegisterType returnRegisterType = analyzedInstruction.postRegisterMap[instruction.getRegisterA()];
737
738        if (returnRegisterType.category == RegisterType.Category.Unknown) {
739            return false;
740        }
741
742        checkRegister(returnRegisterType, Primitive32BitCategories);
743
744        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
745        if (returnType.getTypeDescriptor().charAt(0) == 'V') {
746            throw new ValidationException("Cannot use return with a void return type. Use return-void instead");
747        }
748
749        RegisterType registerType = RegisterType.getRegisterTypeForTypeIdItem(returnType);
750
751        if (!Primitive32BitCategories.contains(registerType.category)) {
752            //TODO: could add which return-* variation should be used instead
753            throw new ValidationException("Cannot use return with return type " + returnType.getTypeDescriptor());
754        }
755
756
757        return true;
758    }
759
760    private boolean handleReturnWide(AnalyzedInstruction analyzedInstruction) {
761        if (this.isInstanceConstructor()) {
762            if (!checkConstructorReturn(analyzedInstruction)) {
763                return false;
764            }
765        }
766
767        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
768        RegisterType returnType = getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterA());
769
770        if (returnType.category == RegisterType.Category.Unknown) {
771            return false;
772        }
773
774
775        TypeIdItem returnTypeIdItem = encodedMethod.method.getPrototype().getReturnType();
776        if (returnTypeIdItem.getTypeDescriptor().charAt(0) == 'V') {
777            throw new ValidationException("Cannot use return-wide with a void return type. Use return-void instead");
778        }
779
780        returnType = RegisterType.getRegisterTypeForTypeIdItem(returnTypeIdItem);
781        if (!WideLowCategories.contains(returnType.category)) {
782            //TODO: could add which return-* variation should be used instead
783            throw new ValidationException("Cannot use return-wide with return type " +
784                    returnTypeIdItem.getTypeDescriptor());
785        }
786
787        return true;
788    }
789
790    private boolean handleReturnObject(AnalyzedInstruction analyzedInstruction) {
791        if (this.isInstanceConstructor()) {
792            if (!checkConstructorReturn(analyzedInstruction)) {
793                return false;
794            }
795        }
796
797        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
798        int returnRegister = instruction.getRegisterA();
799        RegisterType returnRegisterType = analyzedInstruction.postRegisterMap[returnRegister];
800
801        if (returnRegisterType.category == RegisterType.Category.Unknown) {
802            return false;
803        }
804
805        checkRegister(returnRegisterType, ReferenceCategories);
806
807
808        TypeIdItem returnTypeIdItem = encodedMethod.method.getPrototype().getReturnType();
809        if (returnTypeIdItem.getTypeDescriptor().charAt(0) == 'V') {
810            throw new ValidationException("Cannot use return with a void return type. Use return-void instead");
811        }
812
813        RegisterType returnType = RegisterType.getRegisterTypeForTypeIdItem(returnTypeIdItem);
814
815        if (!ReferenceCategories.contains(returnType.category)) {
816            //TODO: could add which return-* variation should be used instead
817            throw new ValidationException("Cannot use " + analyzedInstruction + " with return type " +
818                    returnTypeIdItem.getTypeDescriptor());
819        }
820
821        if (returnType.type.isInterface()) {
822            if (!returnRegisterType.type.implementsInterface(returnType.type)) {
823                //TODO: how to handle warnings?
824            }
825        } else {
826            if (!returnRegisterType.type.extendsClass(returnType.type)) {
827                throw new ValidationException("The return value in register v" + Integer.toString(returnRegister) +
828                        "(" + returnRegisterType.type.getClassType() + ") is not compatible with the method's return " +
829                        "type (" + returnType.type.getClassType() + ")");
830            }
831        }
832
833        return true;
834    }
835
836    private boolean handleConst(AnalyzedInstruction analyzedInstruction) {
837        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
838
839        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(instruction.getLiteral());
840
841        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
842        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
843        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
844        return true;
845    }
846
847    private boolean handleConstHigh16(AnalyzedInstruction analyzedInstruction) {
848        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
849
850        //TODO: test this
851        long literalValue = instruction.getLiteral() << 16;
852        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(literalValue);
853
854        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
855        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
856        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
857        return true;
858    }
859
860    private boolean handleWideConst(AnalyzedInstruction analyzedInstruction) {
861        setWideDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
862                RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
863        return true;
864    }
865
866    private boolean handleConstString(AnalyzedInstruction analyzedInstruction) {
867        ClassPath.ClassDef stringClassDef = ClassPath.getClassDef("Ljava/lang/String;");
868        RegisterType stringType = RegisterType.getRegisterType(RegisterType.Category.Reference, stringClassDef);
869        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, stringType);
870        return true;
871    }
872
873    private boolean handleConstClass(AnalyzedInstruction analyzedInstruction) {
874        ClassPath.ClassDef classClassDef = ClassPath.getClassDef("Ljava/lang/Class;");
875        RegisterType classType = RegisterType.getRegisterType(RegisterType.Category.Reference, classClassDef);
876
877        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
878        Item item = instruction.getReferencedItem();
879        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
880
881        //make sure the referenced class is resolvable
882        //TODO: need to check class access
883        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
884        return false;
885    }
886
887    private boolean handleMonitor(AnalyzedInstruction analyzedInstruction) {
888        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction;
889
890        RegisterType registerType = analyzedInstruction.postRegisterMap[instruction.getRegisterA()];
891        assert registerType != null;
892        if (registerType.category == RegisterType.Category.Unknown) {
893            return false;
894        }
895
896        checkRegister(registerType, ReferenceCategories);
897        return true;
898    }
899
900    private boolean handleCheckCast(AnalyzedInstruction analyzedInstruction) {
901        {
902            //ensure the "source" register is a reference type
903            SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
904
905            RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
906            assert registerType != null;
907            if (registerType.category == RegisterType.Category.Unknown) {
908                return false;
909            }
910
911            checkRegister(registerType, ReferenceCategories);
912        }
913
914        {
915            //resolve and verify the class that we're casting to
916            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
917
918            Item item = instruction.getReferencedItem();
919            assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
920
921            //TODO: need to check class access
922            RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
923            try {
924                checkRegister(newDestinationRegisterType, ReferenceCategories);
925            } catch (ValidationException ex) {
926                //TODO: verify that dalvik allows a non-reference type..
927                //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)
928            }
929
930            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
931            return true;
932        }
933    }
934
935    private boolean handleInstanceOf(AnalyzedInstruction analyzedInstruction) {
936        {
937            //ensure the register that is being checks is a reference type
938            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction;
939
940            RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
941            assert registerType != null;
942            if (registerType.category == RegisterType.Category.Unknown) {
943                return false;
944            }
945
946            checkRegister(registerType, ReferenceCategories);
947        }
948
949        {
950            //resolve and verify the class that we're checking against
951            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
952
953            Item item = instruction.getReferencedItem();
954            assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
955            RegisterType registerType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
956            checkRegister(registerType, ReferenceCategories);
957
958            //TODO: is it valid to use an array type?
959
960            //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.
961            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
962                    RegisterType.getRegisterType(RegisterType.Category.Boolean, null));
963            return true;
964        }
965    }
966
967    private boolean handleArrayLength(AnalyzedInstruction analyzedInstruction) {
968        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction;
969
970        int arrayRegisterNumber = instruction.getRegisterB();
971        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(arrayRegisterNumber);
972        assert arrayRegisterType != null;
973        if (arrayRegisterType.category == RegisterType.Category.Unknown) {
974            return false;
975        }
976
977        assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
978
979        checkRegister(arrayRegisterType, ReferenceCategories);
980        if (arrayRegisterType.type != null) {
981            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
982                throw new ValidationException("Cannot use array-length with non-array type " +
983                        arrayRegisterType.type.getClassType());
984            }
985        }
986
987        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
988                RegisterType.getRegisterType(RegisterType.Category.Integer, null));
989        return true;
990    }
991
992    private boolean handleNewInstance(AnalyzedInstruction analyzedInstruction) {
993        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
994
995        Item item = instruction.getReferencedItem();
996        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
997
998        //TODO: need to check class access
999        RegisterType classType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1000        checkRegister(classType, ReferenceCategories);
1001        if (((TypeIdItem)item).getTypeDescriptor().charAt(0) == '[') {
1002            throw new ValidationException("Cannot use array type \"" + ((TypeIdItem)item).getTypeDescriptor() +
1003                    "\" with new-instance. Use new-array instead.");
1004        }
1005
1006        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1007                RegisterType.getRegisterType(RegisterType.Category.UninitRef, classType.type));
1008        return true;
1009    }
1010
1011    private boolean handleNewArray(AnalyzedInstruction analyzedInstruction) {
1012        {
1013            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1014
1015            int sizeRegister = instruction.getRegisterB();
1016            RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(sizeRegister);
1017            assert registerType != null;
1018
1019            if (registerType.category == RegisterType.Category.Unknown) {
1020                return false;
1021            }
1022
1023            checkRegister(registerType, Primitive32BitCategories);
1024        }
1025
1026        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1027
1028        Item item = instruction.getReferencedItem();
1029        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1030
1031        RegisterType arrayType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1032        assert arrayType.type instanceof ClassPath.ArrayClassDef;
1033
1034        checkRegister(arrayType, ReferenceCategories);
1035        if (arrayType.type.getClassType().charAt(0) != '[') {
1036            throw new ValidationException("Cannot use non-array type \"" + arrayType.type.getClassType() +
1037                    "\" with new-array. Use new-instance instead.");
1038        }
1039
1040        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1041        return true;
1042    }
1043
1044    private static interface RegisterIterator {
1045        int getRegister();
1046        boolean moveNext();
1047    }
1048
1049    private boolean handleFilledNewArrayCommon(AnalyzedInstruction analyzedInstruction,
1050                                               RegisterIterator registerIterator) {
1051        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1052
1053        RegisterType arrayType;
1054        RegisterType arrayImmediateElementType;
1055
1056        Item item = instruction.getReferencedItem();
1057        assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1058
1059        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
1060
1061        if (classDef.getClassType().charAt(0) != '[') {
1062            throw new ValidationException("Cannot use non-array type \"" + classDef.getClassType() +
1063                "\" with new-array. Use new-instance instead.");
1064        }
1065
1066        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)classDef;
1067        arrayType = RegisterType.getRegisterType(RegisterType.Category.Reference, classDef);
1068        arrayImmediateElementType = RegisterType.getRegisterTypeForType(
1069                arrayClassDef.getImmediateElementClass().getClassType());
1070        String baseElementType = arrayClassDef.getBaseElementClass().getClassType();
1071        if (baseElementType.charAt(0) == 'J' || baseElementType.charAt(0) == 'D') {
1072            throw new ValidationException("Cannot use filled-new-array to create an array of wide values " +
1073                    "(long or double)");
1074        }
1075
1076        do {
1077            int register = registerIterator.getRegister();
1078            RegisterType elementType = analyzedInstruction.getPreInstructionRegisterType(register);
1079            assert elementType != null;
1080
1081            if (elementType.category == RegisterType.Category.Unknown) {
1082                return false;
1083            }
1084
1085            if (!elementType.canBeAssignedTo(arrayImmediateElementType)) {
1086                throw new ValidationException("Register v" + Integer.toString(register) + " is of type " +
1087                        elementType.toString() + " and is incompatible with the array type " +
1088                        arrayType.type.getClassType());
1089            }
1090        } while (registerIterator.moveNext());
1091
1092        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1093        return true;
1094    }
1095
1096    private boolean handleFilledNewArray(AnalyzedInstruction analyzedInstruction) {
1097        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
1098        final int registerCount = instruction.getRegCount();
1099        final int[] registers = new int[]{instruction.getRegisterD(), instruction.getRegisterE(),
1100                                          instruction.getRegisterF(), instruction.getRegisterG(),
1101                                          instruction.getRegisterA()};
1102
1103        return handleFilledNewArrayCommon(analyzedInstruction,
1104                new RegisterIterator() {
1105                    private int currentRegister = 0;
1106                    public int getRegister() {
1107                        return registers[currentRegister];
1108                    }
1109
1110                    public boolean moveNext() {
1111                        currentRegister++;
1112                        if (currentRegister >= registerCount) {
1113                            return false;
1114                        }
1115                        return true;
1116                    }
1117                });
1118    }
1119
1120    private boolean handleFilledNewArrayRange(AnalyzedInstruction analyzedInstruction) {
1121        final RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
1122
1123        //instruction.getStartRegister() and instruction.getRegCount() both return an int value, but are actually
1124        //unsigned 16 bit values, so we don't have to worry about overflowing an int when adding them together
1125        if (instruction.getStartRegister() + instruction.getRegCount() >= 1<<16) {
1126            throw new ValidationException(String.format("Invalid register range {v%d .. v%d}. The ending register " +
1127                    "is larger than the largest allowed register of v65535.",
1128                    instruction.getStartRegister(),
1129                    instruction.getStartRegister() + instruction.getRegCount() - 1));
1130        }
1131
1132        return handleFilledNewArrayCommon(analyzedInstruction,
1133                new RegisterIterator() {
1134                    private int currentRegister = 0;
1135                    private final int startRegister = instruction.getStartRegister();
1136                    private final int registerCount = instruction.getRegCount();
1137
1138                    public int getRegister() {
1139                        return startRegister + currentRegister;
1140                    }
1141
1142                    public boolean moveNext() {
1143                        currentRegister++;
1144                        if (currentRegister >= registerCount) {
1145                            return false;
1146                        }
1147                        return true;
1148                    }
1149                });
1150    }
1151
1152    private boolean handleFillArrayData(AnalyzedInstruction analyzedInstruction) {
1153        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1154
1155        int register = instruction.getRegisterA();
1156        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1157        assert registerType != null;
1158
1159        if (registerType.category == RegisterType.Category.Unknown ||
1160            registerType.category == RegisterType.Category.Null) {
1161            return false;
1162        }
1163
1164        if (registerType.category != RegisterType.Category.Reference) {
1165            throw new ValidationException(String.format("Cannot use fill-array-data with non-array register v%d of " +
1166                    "type %s", register, registerType.toString()));
1167        }
1168
1169        assert registerType.type instanceof ClassPath.ArrayClassDef;
1170        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)registerType.type;
1171
1172        if (arrayClassDef.getArrayDimensions() != 1) {
1173            throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can only " +
1174                    "be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1175        }
1176
1177        int elementWidth;
1178        switch (arrayClassDef.getBaseElementClass().getClassType().charAt(0)) {
1179            case 'Z':
1180            case 'B':
1181                elementWidth = 1;
1182                break;
1183            case 'C':
1184            case 'S':
1185                elementWidth = 2;
1186                break;
1187            case 'I':
1188            case 'F':
1189                elementWidth = 4;
1190                break;
1191            case 'J':
1192            case 'D':
1193                elementWidth = 8;
1194                break;
1195            default:
1196                throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can " +
1197                        "only be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1198        }
1199
1200
1201        int arrayDataAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1202        int arrayDataCodeAddress = getInstructionAddress(analyzedInstruction) + arrayDataAddressOffset;
1203        AnalyzedInstruction arrayDataInstruction = this.instructions.get(arrayDataCodeAddress);
1204        if (arrayDataInstruction == null || arrayDataInstruction.instruction.getFormat() != Format.ArrayData) {
1205            throw new ValidationException(String.format("Could not find an array data structure at code address 0x%x",
1206                    arrayDataCodeAddress));
1207        }
1208
1209        ArrayDataPseudoInstruction arrayDataPseudoInstruction =
1210                (ArrayDataPseudoInstruction)arrayDataInstruction.instruction;
1211
1212        if (elementWidth != arrayDataPseudoInstruction.getElementWidth()) {
1213            throw new ValidationException(String.format("The array data at code address 0x%x does not have the " +
1214                    "correct element width for array type %s. Expecting element width %d, got element width %d.",
1215                    arrayDataCodeAddress, arrayClassDef.getClassType(), elementWidth,
1216                    arrayDataPseudoInstruction.getElementWidth()));
1217        }
1218
1219        return true;
1220    }
1221
1222    private boolean handleThrow(AnalyzedInstruction analyzedInstruction) {
1223        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1224
1225        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1226        assert registerType != null;
1227
1228        if (registerType.category == RegisterType.Category.Unknown) {
1229            return false;
1230        }
1231
1232        if (registerType.category == RegisterType.Category.Null) {
1233            return true;
1234        }
1235
1236        if (registerType.category != RegisterType.Category.Reference) {
1237            throw new ValidationException(String.format("Cannot use throw with non-reference type %s in register v%d",
1238                    registerType.toString(), register));
1239        }
1240
1241        assert registerType.type != null;
1242
1243        if (!registerType.type.extendsClass(ClassPath.getClassDef("Ljava/lang/Throwable;"))) {
1244            throw new ValidationException(String.format("Cannot use throw with non-throwable type %s in register v%d",
1245                    registerType.type.getClassType(), register));
1246        }
1247
1248        return true;
1249    }
1250
1251    private boolean handleSwitch(AnalyzedInstruction analyzedInstruction, Format expectedSwitchDataFormat) {
1252        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1253        int switchCodeAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1254
1255        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1256        assert registerType != null;
1257
1258        if (registerType.category == RegisterType.Category.Unknown) {
1259            return false;
1260        }
1261
1262        checkRegister(registerType, Primitive32BitCategories);
1263
1264        int switchDataCodeAddress = this.getInstructionAddress(analyzedInstruction) + switchCodeAddressOffset;
1265        AnalyzedInstruction switchDataAnalyzedInstruction = instructions.get(switchDataCodeAddress);
1266
1267        if (switchDataAnalyzedInstruction == null ||
1268            switchDataAnalyzedInstruction.instruction.getFormat() != expectedSwitchDataFormat) {
1269            throw new ValidationException(String.format("There is no %s structure at code address 0x%x",
1270                    expectedSwitchDataFormat.name(), switchDataCodeAddress));
1271        }
1272
1273        return true;
1274    }
1275
1276    private boolean handleFloatCmp(AnalyzedInstruction analyzedInstruction) {
1277        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1278
1279        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1280        assert registerType != null;
1281
1282        if (registerType.category == RegisterType.Category.Unknown) {
1283            return false;
1284        }
1285        checkRegister(registerType, Primitive32BitCategories);
1286
1287        registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1288        assert registerType != null;
1289
1290        if (registerType.category == RegisterType.Category.Unknown) {
1291            return false;
1292        }
1293        checkRegister(registerType, Primitive32BitCategories);
1294
1295        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1296                RegisterType.getRegisterType(RegisterType.Category.Byte, null));
1297        return true;
1298    }
1299
1300    private boolean handleWideCmp(AnalyzedInstruction analyzedInstruction) {
1301        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1302
1303        RegisterType registerType = getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterB());
1304        assert registerType != null;
1305        if (registerType.category == RegisterType.Category.Unknown) {
1306            return false;
1307        }
1308
1309        registerType = getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterC());
1310        assert registerType != null;
1311        if (registerType.category == RegisterType.Category.Unknown) {
1312            return false;
1313        }
1314
1315        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1316                RegisterType.getRegisterType(RegisterType.Category.Byte, null));
1317        return true;
1318    }
1319
1320    private boolean handleIfEqNe(AnalyzedInstruction analyzedInstruction) {
1321        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1322
1323        RegisterType registerType1 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1324        assert registerType1 != null;
1325        if (registerType1.category == RegisterType.Category.Unknown) {
1326            return false;
1327        }
1328
1329        RegisterType registerType2 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1330        assert registerType2 != null;
1331        if (registerType2.category == RegisterType.Category.Unknown) {
1332            return false;
1333        }
1334
1335        if (!(
1336                (ReferenceCategories.contains(registerType1.category) &&
1337                ReferenceCategories.contains(registerType2.category))
1338                    ||
1339                (Primitive32BitCategories.contains(registerType1.category) &&
1340                Primitive32BitCategories.contains(registerType2.category))
1341              )) {
1342
1343            throw new ValidationException(String.format("%s cannot be used on registers of dissimilar types %s and " +
1344                    "%s. They must both be a reference type or a primitive 32 bit type.",
1345                    analyzedInstruction.instruction.opcode.name, registerType1.toString(), registerType2.toString()));
1346        }
1347
1348        return true;
1349    }
1350
1351    private boolean handleIf(AnalyzedInstruction analyzedInstruction) {
1352        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1353
1354        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1355        assert registerType != null;
1356
1357        if (registerType.category == RegisterType.Category.Unknown) {
1358            return false;
1359        }
1360        checkRegister(registerType, Primitive32BitCategories);
1361
1362        registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1363        assert registerType != null;
1364
1365        if (registerType.category == RegisterType.Category.Unknown) {
1366            return false;
1367        }
1368        checkRegister(registerType, Primitive32BitCategories);
1369
1370        return true;
1371    }
1372
1373    private boolean handleIfEqzNez(AnalyzedInstruction analyzedInstruction) {
1374        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1375
1376        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1377        assert registerType != null;
1378        if (registerType.category == RegisterType.Category.Unknown) {
1379            return false;
1380        }
1381
1382        if (!ReferenceCategories.contains(registerType.category) &&
1383            !Primitive32BitCategories.contains(registerType.category)) {
1384            throw new ValidationException(String.format("%s cannot be used with register type %s. Expecting 32-bit " +
1385                    "primitive type or reference type.", analyzedInstruction.instruction.opcode));
1386        }
1387
1388        return true;
1389    }
1390
1391    private boolean handleIfz(AnalyzedInstruction analyzedInstruction) {
1392        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1393
1394        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1395        assert registerType != null;
1396
1397        if (registerType.category == RegisterType.Category.Unknown) {
1398            return false;
1399        }
1400        checkRegister(registerType, Primitive32BitCategories);
1401
1402        return true;
1403    }
1404
1405    private boolean handle32BitPrimitiveAget(AnalyzedInstruction analyzedInstruction,
1406                                             RegisterType.Category instructionCategory) {
1407        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1408
1409        RegisterType indexRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1410        assert indexRegisterType != null;
1411        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1412            return false;
1413        }
1414        checkRegister(indexRegisterType, Primitive32BitCategories);
1415
1416        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1417        assert arrayRegisterType != null;
1418        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1419            return false;
1420        }
1421
1422        if (arrayRegisterType.category != RegisterType.Category.Null) {
1423            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1424                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1425                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
1426            }
1427
1428            assert arrayRegisterType.type != null;
1429            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1430                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1431                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1432            }
1433
1434            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1435            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1436
1437            if (arrayClassDef.getArrayDimensions() != 1) {
1438                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
1439                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1440            }
1441
1442            RegisterType arrayBaseType =
1443                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
1444            if (checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
1445                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
1446                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1447                        arrayRegisterType.type.getClassType()));
1448            }
1449        }
1450
1451        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1452                RegisterType.getRegisterType(instructionCategory, null));
1453
1454        return true;
1455    }
1456
1457    private boolean handleAgetWide(AnalyzedInstruction analyzedInstruction) {
1458        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1459
1460        RegisterType indexRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1461        assert indexRegisterType != null;
1462        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1463            return false;
1464        }
1465        checkRegister(indexRegisterType, Primitive32BitCategories);
1466
1467        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1468        assert arrayRegisterType != null;
1469        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1470            return false;
1471        }
1472
1473        if (arrayRegisterType.category != RegisterType.Category.Null) {
1474            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1475                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
1476                        arrayRegisterType.category.toString()));
1477            }
1478
1479            assert arrayRegisterType.type != null;
1480            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1481                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
1482                        arrayRegisterType.type.getClassType()));
1483            }
1484
1485            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1486            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1487
1488            if (arrayClassDef.getArrayDimensions() != 1) {
1489                throw new ValidationException(String.format("Cannot use aget-wide with multi-dimensional array type %s",
1490                        arrayRegisterType.type.getClassType()));
1491            }
1492
1493            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
1494            if (arrayBaseType == 'J') {
1495                setWideDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1496                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1497            } else if (arrayBaseType == 'D') {
1498                setWideDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1499                        RegisterType.getRegisterType(RegisterType.Category.DoubleLo, null));
1500            } else {
1501                throw new ValidationException(String.format("Cannot use aget-wide with array type %s. Incorrect " +
1502                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1503            }
1504        } else {
1505            setWideDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1506                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1507        }
1508
1509        return true;
1510    }
1511
1512    private boolean handleAgetObject(AnalyzedInstruction analyzedInstruction) {
1513        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1514
1515        RegisterType indexRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1516        assert indexRegisterType != null;
1517        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1518            return false;
1519        }
1520        checkRegister(indexRegisterType, Primitive32BitCategories);
1521
1522        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1523        assert arrayRegisterType != null;
1524        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1525            return false;
1526        }
1527
1528        if (arrayRegisterType.category != RegisterType.Category.Null) {
1529            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1530                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1531                        arrayRegisterType.category.toString()));
1532            }
1533
1534            assert arrayRegisterType.type != null;
1535            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1536                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1537                        arrayRegisterType.type.getClassType()));
1538            }
1539
1540            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1541            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1542
1543            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
1544            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
1545            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
1546                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
1547                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1548            }
1549
1550            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1551                    RegisterType.getRegisterType(RegisterType.Category.Reference, elementClassDef));
1552        } else {
1553            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1554                    RegisterType.getRegisterType(RegisterType.Category.Null, null));
1555        }
1556
1557        return true;
1558    }
1559
1560    private boolean handle32BitPrimitiveAput(AnalyzedInstruction analyzedInstruction,
1561                                             RegisterType.Category instructionCategory) {
1562        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1563
1564        RegisterType indexRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1565        assert indexRegisterType != null;
1566        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1567            return false;
1568        }
1569        checkRegister(indexRegisterType, Primitive32BitCategories);
1570
1571
1572        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1573        assert sourceRegisterType != null;
1574        if (sourceRegisterType.category == RegisterType.Category.Unknown) {
1575            return false;
1576        }
1577        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
1578        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
1579            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
1580                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
1581        }
1582
1583
1584        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1585        assert arrayRegisterType != null;
1586        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1587            return false;
1588        }
1589
1590        if (arrayRegisterType.category != RegisterType.Category.Null) {
1591            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1592                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1593                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
1594            }
1595
1596            assert arrayRegisterType.type != null;
1597            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1598                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1599                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1600            }
1601
1602            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1603            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1604
1605            if (arrayClassDef.getArrayDimensions() != 1) {
1606                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
1607                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1608            }
1609
1610            RegisterType arrayBaseType =
1611                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
1612            if (checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
1613                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
1614                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1615                        arrayRegisterType.type.getClassType()));
1616            }
1617        }
1618
1619        return true;
1620    }
1621
1622    private boolean handleAputWide(AnalyzedInstruction analyzedInstruction) {
1623        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1624
1625        RegisterType indexRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1626        assert indexRegisterType != null;
1627        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1628            return false;
1629        }
1630        checkRegister(indexRegisterType, Primitive32BitCategories);
1631
1632        RegisterType sourceRegisterType = getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterA());
1633        if (sourceRegisterType.category == RegisterType.Category.Unknown) {
1634            return false;
1635        }
1636
1637        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1638        assert arrayRegisterType != null;
1639        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1640            return false;
1641        }
1642
1643        if (arrayRegisterType.category != RegisterType.Category.Null) {
1644            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1645                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
1646                        arrayRegisterType.category.toString()));
1647            }
1648
1649            assert arrayRegisterType.type != null;
1650            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1651                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
1652                        arrayRegisterType.type.getClassType()));
1653            }
1654
1655            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1656            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1657
1658            if (arrayClassDef.getArrayDimensions() != 1) {
1659                throw new ValidationException(String.format("Cannot use aput-wide with multi-dimensional array type %s",
1660                        arrayRegisterType.type.getClassType()));
1661            }
1662
1663            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
1664            if (arrayBaseType != 'J' && arrayBaseType != 'D') {
1665                throw new ValidationException(String.format("Cannot use aput-wide with array type %s. Incorrect " +
1666                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1667            }
1668        }
1669
1670        return true;
1671    }
1672
1673    private boolean handleAputObject(AnalyzedInstruction analyzedInstruction) {
1674        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1675
1676        RegisterType indexRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1677        assert indexRegisterType != null;
1678        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1679            return false;
1680        }
1681        checkRegister(indexRegisterType, Primitive32BitCategories);
1682
1683        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1684        assert sourceRegisterType != null;
1685        if (sourceRegisterType.category == RegisterType.Category.Unknown) {
1686            return false;
1687        }
1688
1689        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1690        assert arrayRegisterType != null;
1691        if (indexRegisterType.category == RegisterType.Category.Unknown) {
1692            return false;
1693        }
1694
1695        if (arrayRegisterType.category != RegisterType.Category.Null) {
1696            //don't check the source type against the array type, just make sure it is an array of reference types
1697
1698            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1699                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1700                        arrayRegisterType.category.toString()));
1701            }
1702
1703            assert arrayRegisterType.type != null;
1704            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1705                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1706                        arrayRegisterType.type.getClassType()));
1707            }
1708
1709            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1710            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1711
1712            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
1713            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
1714            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
1715                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
1716                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1717            }
1718        }
1719
1720        return true;
1721    }
1722
1723    private boolean handle32BitPrimitiveIget(AnalyzedInstruction analyzedInstruction,
1724                                             RegisterType.Category instructionCategory) {
1725        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1726
1727        RegisterType objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1728        assert objectRegisterType != null;
1729        if (objectRegisterType.category == RegisterType.Category.Unknown) {
1730            return false;
1731        }
1732        checkRegister(objectRegisterType, ReferenceCategories);
1733
1734        //TODO: check access
1735        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1736        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1737        assert referencedItem instanceof FieldIdItem;
1738        FieldIdItem field = (FieldIdItem)referencedItem;
1739
1740        if (objectRegisterType.category != RegisterType.Category.Null &&
1741            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1742            throw new ValidationException(String.format("Cannot access field %s through type %s",
1743                    field.getFieldString(), objectRegisterType.type.getClassType()));
1744        }
1745
1746        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1747
1748        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
1749                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1750                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1751                        field.getFieldString()));
1752        }
1753
1754        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1755                RegisterType.getRegisterType(instructionCategory, null));
1756
1757        return true;
1758    }
1759
1760    private boolean handleIgetWide(AnalyzedInstruction analyzedInstruction) {
1761        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1762
1763        RegisterType objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1764        assert objectRegisterType != null;
1765        if (objectRegisterType.category == RegisterType.Category.Unknown) {
1766            return false;
1767        }
1768        checkRegister(objectRegisterType, ReferenceCategories);
1769
1770        getAndCheckWideSourcePair(analyzedInstruction, instruction.getRegisterB());
1771
1772        //TODO: check access
1773        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1774        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1775        assert referencedItem instanceof FieldIdItem;
1776        FieldIdItem field = (FieldIdItem)referencedItem;
1777
1778        if (objectRegisterType.category != RegisterType.Category.Null &&
1779            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1780            throw new ValidationException(String.format("Cannot access field %s through type %s",
1781                    field.getFieldString(), objectRegisterType.type.getClassType()));
1782        }
1783
1784        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1785
1786        try {
1787            checkRegister(fieldType, WideLowCategories);
1788        } catch (ValidationException ex) {
1789            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1790                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1791                        field.getFieldString()));
1792        }
1793
1794        setWideDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
1795
1796        return true;
1797    }
1798
1799    private boolean handleIgetObject(AnalyzedInstruction analyzedInstruction) {
1800        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1801
1802        RegisterType objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1803        assert objectRegisterType != null;
1804        if (objectRegisterType.category == RegisterType.Category.Unknown) {
1805            return false;
1806        }
1807        checkRegister(objectRegisterType, ReferenceCategories);
1808
1809        //TODO: check access
1810        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1811        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1812        assert referencedItem instanceof FieldIdItem;
1813        FieldIdItem field = (FieldIdItem)referencedItem;
1814
1815        if (objectRegisterType.category != RegisterType.Category.Null &&
1816            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1817            throw new ValidationException(String.format("Cannot access field %s through type %s",
1818                    field.getFieldString(), objectRegisterType.type.getClassType()));
1819        }
1820
1821        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1822
1823        if (fieldType.category != RegisterType.Category.Reference) {
1824            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1825                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1826                        field.getFieldString()));
1827        }
1828
1829        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
1830
1831        return true;
1832    }
1833
1834    private boolean handle32BitPrimitiveIput(AnalyzedInstruction analyzedInstruction,
1835                                             RegisterType.Category instructionCategory) {
1836        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1837
1838        RegisterType objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1839        assert objectRegisterType != null;
1840        if (objectRegisterType.category == RegisterType.Category.Unknown) {
1841            return false;
1842        }
1843        checkRegister(objectRegisterType, ReferenceCategories);
1844
1845        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1846        assert sourceRegisterType != null;
1847        if (sourceRegisterType.category == RegisterType.Category.Unknown) {
1848            return false;
1849        }
1850
1851        //per CodeVerify.c in dalvik:
1852        //java generates synthetic functions that write byte values into boolean fields
1853        if (sourceRegisterType.category == RegisterType.Category.Byte &&
1854            instructionCategory == RegisterType.Category.Boolean) {
1855
1856            sourceRegisterType = RegisterType.getRegisterType(RegisterType.Category.Boolean, null);
1857        }
1858
1859        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
1860        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
1861            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
1862                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
1863        }
1864
1865
1866        //TODO: check access
1867        //TODO: allow an uninitialized "this" reference, if the current method is an <init> method
1868        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
1869        assert referencedItem instanceof FieldIdItem;
1870        FieldIdItem field = (FieldIdItem)referencedItem;
1871
1872        if (objectRegisterType.category != RegisterType.Category.Null &&
1873            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
1874            throw new ValidationException(String.format("Cannot access field %s through type %s",
1875                    field.getFieldString(), objectRegisterType.type.getClassType()));
1876        }
1877
1878        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
1879
1880        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
1881                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
1882                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1883                        field.getFieldString()));
1884        }
1885
1886        return true;
1887    }
1888
1889    private static boolean checkArrayFieldAssignment(RegisterType.Category arrayFieldCategory,
1890                                                  RegisterType.Category instructionCategory) {
1891        if (arrayFieldCategory == instructionCategory) {
1892            return true;
1893        }
1894
1895        if ((arrayFieldCategory == RegisterType.Category.Integer &&
1896             instructionCategory == RegisterType.Category.Float) ||
1897            (arrayFieldCategory == RegisterType.Category.Float &&
1898             instructionCategory == RegisterType.Category.Integer)) {
1899            return true;
1900        }
1901        return false;
1902    }
1903
1904    private static void checkRegister(RegisterType registerType, EnumSet validCategories) {
1905        if (!validCategories.contains(registerType.category)) {
1906            //TODO: add expected categories to error message
1907            throw new ValidationException("Invalid register type. Expecting one of: " + " but got \"" +
1908                    registerType.category + "\"");
1909        }
1910    }
1911
1912    private static void checkWideDestinationPair(AnalyzedInstruction analyzedInstruction) {
1913        int register = analyzedInstruction.getDestinationRegister();
1914
1915        if (register == (analyzedInstruction.postRegisterMap.length - 1)) {
1916            throw new ValidationException("v" + register + " is the last register and not a valid wide register " +
1917                    "pair.");
1918        }
1919    }
1920
1921    private static RegisterType getAndCheckWideSourcePair(AnalyzedInstruction analyzedInstruction, int firstRegister) {
1922        assert firstRegister >= 0 && firstRegister < analyzedInstruction.postRegisterMap.length;
1923
1924        if (firstRegister == analyzedInstruction.postRegisterMap.length - 1) {
1925            throw new ValidationException("v" + firstRegister + " is the last register and not a valid wide register " +
1926                    "pair.");
1927        }
1928
1929        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(firstRegister);
1930        assert registerType != null;
1931        if (registerType.category == RegisterType.Category.Unknown) {
1932            return registerType;
1933        }
1934        checkRegister(registerType, WideLowCategories);
1935
1936        RegisterType secondRegisterType = analyzedInstruction.getPreInstructionRegisterType(firstRegister + 1);
1937        assert secondRegisterType != null;
1938        checkRegister(secondRegisterType, WideHighCategories);
1939
1940        if ((       registerType.category == RegisterType.Category.LongLo &&
1941                    secondRegisterType.category == RegisterType.Category.DoubleHi)
1942            ||  (   registerType.category == RegisterType.Category.DoubleLo &&
1943                    secondRegisterType.category == RegisterType.Category.LongHi)) {
1944            assert false;
1945            throw new ValidationException("The first register in the wide register pair isn't the same type (long " +
1946                    "vs. double) as the second register in the pair");
1947        }
1948
1949        return registerType;
1950    }
1951}
1952