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