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