1/*
2 * Copyright 2013, Google Inc.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 *     * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *     * Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following disclaimer
13 * in the documentation and/or other materials provided with the
14 * distribution.
15 *     * Neither the name of Google Inc. nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32package org.jf.dexlib2.builder;
33
34import com.google.common.base.Function;
35import com.google.common.collect.Iterables;
36import com.google.common.collect.Lists;
37import com.google.common.collect.Sets;
38import org.jf.dexlib2.DebugItemType;
39import org.jf.dexlib2.Opcode;
40import org.jf.dexlib2.builder.debug.*;
41import org.jf.dexlib2.builder.instruction.*;
42import org.jf.dexlib2.iface.ExceptionHandler;
43import org.jf.dexlib2.iface.MethodImplementation;
44import org.jf.dexlib2.iface.TryBlock;
45import org.jf.dexlib2.iface.debug.*;
46import org.jf.dexlib2.iface.instruction.Instruction;
47import org.jf.dexlib2.iface.instruction.SwitchElement;
48import org.jf.dexlib2.iface.instruction.formats.*;
49import org.jf.dexlib2.iface.reference.TypeReference;
50import org.jf.util.ExceptionWithContext;
51
52import javax.annotation.Nonnull;
53import javax.annotation.Nullable;
54import java.util.*;
55
56public class MutableMethodImplementation implements MethodImplementation {
57    private final int registerCount;
58    final ArrayList<MethodLocation> instructionList = Lists.newArrayList(new MethodLocation(null, 0, 0));
59    private final ArrayList<BuilderTryBlock> tryBlocks = Lists.newArrayList();
60    private boolean fixInstructions = true;
61
62    public MutableMethodImplementation(@Nonnull MethodImplementation methodImplementation) {
63        this.registerCount = methodImplementation.getRegisterCount();
64
65        int codeAddress = 0;
66        int index = 0;
67
68        for (Instruction instruction: methodImplementation.getInstructions()) {
69            codeAddress += instruction.getCodeUnits();
70            index++;
71
72            instructionList.add(new MethodLocation(null, codeAddress, index));
73        }
74
75        final int[] codeAddressToIndex = new int[codeAddress+1];
76        Arrays.fill(codeAddressToIndex, -1);
77
78        for (int i=0; i<instructionList.size(); i++) {
79            codeAddressToIndex[instructionList.get(i).codeAddress] = i;
80        }
81
82        List<Task> switchPayloadTasks = Lists.newArrayList();
83        index = 0;
84        for (final Instruction instruction: methodImplementation.getInstructions()) {
85            final MethodLocation location = instructionList.get(index);
86            final Opcode opcode = instruction.getOpcode();
87            if (opcode == Opcode.PACKED_SWITCH_PAYLOAD || opcode == Opcode.SPARSE_SWITCH_PAYLOAD) {
88                switchPayloadTasks.add(new Task() {
89                    @Override public void perform() {
90                        convertAndSetInstruction(location, codeAddressToIndex, instruction);
91                    }
92                });
93            } else {
94                convertAndSetInstruction(location, codeAddressToIndex, instruction);
95            }
96            index++;
97        }
98
99        // the switch payload instructions must be converted last, so that any switch statements that refer to them
100        // have created the referring labels that we look for
101        for (Task switchPayloadTask: switchPayloadTasks) {
102            switchPayloadTask.perform();
103        }
104
105        for (DebugItem debugItem: methodImplementation.getDebugItems()) {
106            int debugCodeAddress = debugItem.getCodeAddress();
107            int locationIndex = mapCodeAddressToIndex(codeAddressToIndex, debugCodeAddress);
108            MethodLocation debugLocation = instructionList.get(locationIndex);
109            BuilderDebugItem builderDebugItem = convertDebugItem(debugItem);
110            debugLocation.getDebugItems().add(builderDebugItem);
111            builderDebugItem.location = debugLocation;
112        }
113
114        for (TryBlock<? extends ExceptionHandler> tryBlock: methodImplementation.getTryBlocks()) {
115            Label startLabel = newLabel(codeAddressToIndex, tryBlock.getStartCodeAddress());
116            Label endLabel = newLabel(codeAddressToIndex, tryBlock.getStartCodeAddress() + tryBlock.getCodeUnitCount());
117
118            for (ExceptionHandler exceptionHandler: tryBlock.getExceptionHandlers()) {
119                tryBlocks.add(new BuilderTryBlock(startLabel, endLabel,
120                        exceptionHandler.getExceptionTypeReference(),
121                        newLabel(codeAddressToIndex, exceptionHandler.getHandlerCodeAddress())));
122            }
123        }
124    }
125
126    private interface Task {
127        void perform();
128    }
129
130    public MutableMethodImplementation(int registerCount) {
131        this.registerCount = registerCount;
132    }
133
134    @Override public int getRegisterCount() {
135        return registerCount;
136    }
137
138    @Nonnull
139    public List<BuilderInstruction> getInstructions() {
140        if (fixInstructions) {
141            fixInstructions();
142        }
143
144        return new AbstractList<BuilderInstruction>() {
145            @Override public BuilderInstruction get(int i) {
146                if (i >= size()) {
147                    throw new IndexOutOfBoundsException();
148                }
149                if (fixInstructions) {
150                    fixInstructions();
151                }
152                return instructionList.get(i).instruction;
153            }
154
155            @Override public int size() {
156                if (fixInstructions) {
157                    fixInstructions();
158                }
159                // don't include the last MethodLocation, which always has a null instruction
160                return instructionList.size() - 1;
161            }
162        };
163    }
164
165    @Nonnull @Override public List<BuilderTryBlock> getTryBlocks() {
166        if (fixInstructions) {
167            fixInstructions();
168        }
169        return Collections.unmodifiableList(tryBlocks);
170    }
171
172    @Nonnull @Override public Iterable<? extends DebugItem> getDebugItems() {
173        if (fixInstructions) {
174            fixInstructions();
175        }
176        return Iterables.concat(
177                Iterables.transform(instructionList, new Function<MethodLocation, Iterable<? extends DebugItem>>() {
178                    @Nullable @Override public Iterable<? extends DebugItem> apply(@Nullable MethodLocation input) {
179                        assert input != null;
180                        if (fixInstructions) {
181                            throw new IllegalStateException("This iterator was invalidated by a change to" +
182                                    " this MutableMethodImplementation.");
183                        }
184                        return input.getDebugItems();
185                    }
186                }));
187    }
188
189    public void addCatch(@Nullable TypeReference type, @Nonnull Label from,
190                         @Nonnull Label to, @Nonnull Label handler) {
191        tryBlocks.add(new BuilderTryBlock(from, to, type, handler));
192    }
193
194    public void addCatch(@Nullable String type, @Nonnull Label from, @Nonnull Label to,
195                         @Nonnull Label handler) {
196        tryBlocks.add(new BuilderTryBlock(from, to, type, handler));
197    }
198
199    public void addCatch(@Nonnull Label from, @Nonnull Label to, @Nonnull Label handler) {
200        tryBlocks.add(new BuilderTryBlock(from, to, handler));
201    }
202
203    public void addInstruction(int index, BuilderInstruction instruction) {
204        // the end check here is intentially >= rather than >, because the list always includes an "empty"
205        // (null instruction) MethodLocation at the end. To add an instruction to the end of the list, the user would
206        // provide the index of this empty item, which would be size() - 1.
207        if (index >= instructionList.size()) {
208            throw new IndexOutOfBoundsException();
209        }
210
211        if (index == instructionList.size() - 1) {
212            addInstruction(instruction);
213            return;
214        }
215        int codeAddress = instructionList.get(index).getCodeAddress();
216        MethodLocation newLoc = new MethodLocation(instruction, codeAddress, index);
217        instructionList.add(index, newLoc);
218        instruction.location = newLoc;
219
220        codeAddress += instruction.getCodeUnits();
221
222        for (int i=index+1; i<instructionList.size(); i++) {
223            MethodLocation location = instructionList.get(i);
224            location.index++;
225            location.codeAddress = codeAddress;
226            if (location.instruction != null) {
227                codeAddress += location.instruction.getCodeUnits();
228            } else {
229                // only the last MethodLocation should have a null instruction
230                assert i == instructionList.size()-1;
231            }
232        }
233
234        this.fixInstructions = true;
235    }
236
237    public void addInstruction(@Nonnull BuilderInstruction instruction) {
238        MethodLocation last = instructionList.get(instructionList.size()-1);
239        last.instruction = instruction;
240        instruction.location = last;
241
242        int nextCodeAddress = last.codeAddress + instruction.getCodeUnits();
243        instructionList.add(new MethodLocation(null, nextCodeAddress, instructionList.size()));
244
245        this.fixInstructions = true;
246    }
247
248    public void replaceInstruction(int index, @Nonnull BuilderInstruction replacementInstruction) {
249        if (index >= instructionList.size() - 1) {
250            throw new IndexOutOfBoundsException();
251        }
252
253        MethodLocation replaceLocation = instructionList.get(index);
254        replacementInstruction.location = replaceLocation;
255        BuilderInstruction old = replaceLocation.instruction;
256        assert old != null;
257        old.location = null;
258        replaceLocation.instruction = replacementInstruction;
259
260        // TODO: factor out index/address fix up loop
261        int codeAddress = replaceLocation.codeAddress + replaceLocation.instruction.getCodeUnits();
262        for (int i=index+1; i<instructionList.size(); i++) {
263            MethodLocation location = instructionList.get(i);
264            location.codeAddress = codeAddress;
265
266            Instruction instruction = location.getInstruction();
267            if (instruction != null) {
268                codeAddress += instruction.getCodeUnits();
269            } else {
270                assert i == instructionList.size() - 1;
271            }
272        }
273
274        this.fixInstructions = true;
275    }
276
277    public void removeInstruction(int index) {
278        if (index >= instructionList.size() - 1) {
279            throw new IndexOutOfBoundsException();
280        }
281
282        MethodLocation toRemove = instructionList.get(index);
283        toRemove.instruction = null;
284        MethodLocation next = instructionList.get(index+1);
285        toRemove.mergeInto(next);
286
287        instructionList.remove(index);
288        int codeAddress = toRemove.codeAddress;
289        for (int i=index; i<instructionList.size(); i++) {
290            MethodLocation location = instructionList.get(i);
291            location.index = i;
292            location.codeAddress = codeAddress;
293
294            Instruction instruction = location.getInstruction();
295            if (instruction != null) {
296                codeAddress += instruction.getCodeUnits();
297            } else {
298                assert i == instructionList.size() - 1;
299            }
300        }
301
302        this.fixInstructions = true;
303    }
304
305    public void swapInstructions(int index1, int index2) {
306        if (index1 >= instructionList.size() - 1 || index2 >= instructionList.size() - 1) {
307            throw new IndexOutOfBoundsException();
308        }
309        MethodLocation first = instructionList.get(index1);
310        MethodLocation second = instructionList.get(index2);
311
312        // only the last MethodLocation may have a null instruction
313        assert first.instruction != null;
314        assert second.instruction != null;
315
316        first.instruction.location = second;
317        second.instruction.location = first;
318
319        {
320            BuilderInstruction tmp = second.instruction;
321            second.instruction = first.instruction;
322            first.instruction = tmp;
323        }
324
325        if (index2 < index1) {
326            int tmp = index2;
327            index2 = index1;
328            index1 = tmp;
329        }
330
331        int codeAddress = first.codeAddress + first.instruction.getCodeUnits();
332        for (int i=index1+1; i<=index2; i++) {
333            MethodLocation location = instructionList.get(i);
334            location.codeAddress = codeAddress;
335
336            Instruction instruction = location.instruction;
337            assert instruction != null;
338            codeAddress += location.instruction.getCodeUnits();
339        }
340
341        this.fixInstructions = true;
342    }
343
344    @Nullable
345    private BuilderInstruction getFirstNonNop(int startIndex) {
346
347        for (int i=startIndex; i<instructionList.size()-1; i++) {
348            BuilderInstruction instruction = instructionList.get(i).instruction;
349            assert instruction != null;
350            if (instruction.getOpcode() != Opcode.NOP) {
351                return instruction;
352            }
353        }
354        return null;
355    }
356
357    private void fixInstructions() {
358        HashSet<MethodLocation> payloadLocations = Sets.newHashSet();
359
360        for (MethodLocation location: instructionList) {
361            BuilderInstruction instruction = location.instruction;
362            if (instruction != null) {
363                switch (instruction.getOpcode()) {
364                    case SPARSE_SWITCH:
365                    case PACKED_SWITCH: {
366                        MethodLocation targetLocation =
367                                ((BuilderOffsetInstruction)instruction).getTarget().getLocation();
368                        BuilderInstruction targetInstruction = targetLocation.instruction;
369                        if (targetInstruction == null) {
370                            throw new IllegalStateException(String.format("Switch instruction at address/index " +
371                                    "0x%x/%d points to the end of the method.", location.codeAddress, location.index));
372                        }
373
374                        if (targetInstruction.getOpcode() == Opcode.NOP) {
375                            targetInstruction = getFirstNonNop(targetLocation.index+1);
376                        }
377                        if (targetInstruction == null || !(targetInstruction instanceof BuilderSwitchPayload)) {
378                            throw new IllegalStateException(String.format("Switch instruction at address/index " +
379                                    "0x%x/%d does not refer to a payload instruction.",
380                                    location.codeAddress, location.index));
381                        }
382                        if ((instruction.opcode == Opcode.PACKED_SWITCH &&
383                                targetInstruction.getOpcode() != Opcode.PACKED_SWITCH_PAYLOAD) ||
384                            (instruction.opcode == Opcode.SPARSE_SWITCH &&
385                                targetInstruction.getOpcode() != Opcode.SPARSE_SWITCH_PAYLOAD)) {
386                            throw new IllegalStateException(String.format("Switch instruction at address/index " +
387                                    "0x%x/%d refers to the wrong type of payload instruction.",
388                                    location.codeAddress, location.index));
389                        }
390
391                        if (!payloadLocations.add(targetLocation)) {
392                            throw new IllegalStateException("Multiple switch instructions refer to the same payload. " +
393                                    "This is not currently supported. Please file a bug :)");
394                        }
395
396                        ((BuilderSwitchPayload)targetInstruction).referrer = location;
397                        break;
398                    }
399                }
400            }
401        }
402
403        boolean madeChanges;
404        do {
405            madeChanges = false;
406
407            for (int index=0; index<instructionList.size(); index++) {
408                MethodLocation location = instructionList.get(index);
409                BuilderInstruction instruction = location.instruction;
410                if (instruction != null) {
411                    switch (instruction.getOpcode()) {
412                        case GOTO: {
413                            int offset = ((BuilderOffsetInstruction)instruction).internalGetCodeOffset();
414                            if (offset < Byte.MIN_VALUE || offset > Byte.MAX_VALUE) {
415                                BuilderOffsetInstruction replacement;
416                                if (offset < Short.MIN_VALUE || offset > Short.MAX_VALUE) {
417                                    replacement = new BuilderInstruction30t(Opcode.GOTO_32,
418                                            ((BuilderOffsetInstruction)instruction).getTarget());
419                                } else {
420                                    replacement = new BuilderInstruction20t(Opcode.GOTO_16,
421                                            ((BuilderOffsetInstruction)instruction).getTarget());
422                                }
423                                replaceInstruction(location.index, replacement);
424                                madeChanges = true;
425                            }
426                            break;
427                        }
428                        case GOTO_16: {
429                            int offset = ((BuilderOffsetInstruction)instruction).internalGetCodeOffset();
430                            if (offset < Short.MIN_VALUE || offset > Short.MAX_VALUE) {
431                                BuilderOffsetInstruction replacement =  new BuilderInstruction30t(Opcode.GOTO_32,
432                                            ((BuilderOffsetInstruction)instruction).getTarget());
433                                replaceInstruction(location.index, replacement);
434                                madeChanges = true;
435                            }
436                            break;
437                        }
438                        case SPARSE_SWITCH_PAYLOAD:
439                        case PACKED_SWITCH_PAYLOAD:
440                            if (((BuilderSwitchPayload)instruction).referrer == null) {
441                                // if the switch payload isn't referenced, just remove it
442                                removeInstruction(index);
443                                index--;
444                                madeChanges = true;
445                                break;
446                            }
447                            // intentional fall-through
448                        case ARRAY_PAYLOAD: {
449                            if ((location.codeAddress & 0x01) != 0) {
450                                int previousIndex = location.index - 1;
451                                MethodLocation previousLocation = instructionList.get(previousIndex);
452                                Instruction previousInstruction = previousLocation.instruction;
453                                assert previousInstruction != null;
454                                if (previousInstruction.getOpcode() == Opcode.NOP) {
455                                    removeInstruction(previousIndex);
456                                    index--;
457                                } else {
458                                    addInstruction(location.index, new BuilderInstruction10x(Opcode.NOP));
459                                    index++;
460                                }
461                                madeChanges = true;
462                            }
463                            break;
464                        }
465                    }
466                }
467            }
468        } while (madeChanges);
469
470        fixInstructions = false;
471    }
472
473    private int mapCodeAddressToIndex(@Nonnull int[] codeAddressToIndex, int codeAddress) {
474        int index;
475        do {
476            index = codeAddressToIndex[codeAddress];
477            if (index < 0) {
478                codeAddress--;
479            } else {
480                return index;
481            }
482        } while (true);
483    }
484
485    @Nonnull
486    private Label newLabel(@Nonnull int[] codeAddressToIndex, int codeAddress) {
487        MethodLocation referent = instructionList.get(mapCodeAddressToIndex(codeAddressToIndex, codeAddress));
488        return referent.addNewLabel();
489    }
490
491    private static class SwitchPayloadReferenceLabel extends Label {
492        @Nonnull public MethodLocation switchLocation;
493    }
494
495    @Nonnull
496    public Label newSwitchPayloadReferenceLabel(@Nonnull MethodLocation switchLocation,
497                                                @Nonnull int[] codeAddressToIndex, int codeAddress) {
498        MethodLocation referent = instructionList.get(mapCodeAddressToIndex(codeAddressToIndex, codeAddress));
499        SwitchPayloadReferenceLabel label = new SwitchPayloadReferenceLabel();
500        label.switchLocation = switchLocation;
501        referent.getLabels().add(label);
502        return label;
503    }
504
505    private void setInstruction(@Nonnull MethodLocation location, @Nonnull BuilderInstruction instruction) {
506        location.instruction = instruction;
507        instruction.location = location;
508    }
509
510    private void convertAndSetInstruction(@Nonnull MethodLocation location, int[] codeAddressToIndex,
511                                          @Nonnull Instruction instruction) {
512        switch (instruction.getOpcode().format) {
513            case Format10t:
514                setInstruction(location, newBuilderInstruction10t(location.codeAddress, codeAddressToIndex,
515                        (Instruction10t)instruction));
516                return;
517            case Format10x:
518                setInstruction(location, newBuilderInstruction10x((Instruction10x)instruction));
519                return;
520            case Format11n:
521                setInstruction(location, newBuilderInstruction11n((Instruction11n)instruction));
522                return;
523            case Format11x:
524                setInstruction(location, newBuilderInstruction11x((Instruction11x)instruction));
525                return;
526            case Format12x:
527                setInstruction(location, newBuilderInstruction12x((Instruction12x)instruction));
528                return;
529            case Format20bc:
530                setInstruction(location, newBuilderInstruction20bc((Instruction20bc)instruction));
531                return;
532            case Format20t:
533                setInstruction(location, newBuilderInstruction20t(location.codeAddress, codeAddressToIndex,
534                        (Instruction20t)instruction));
535                return;
536            case Format21c:
537                setInstruction(location, newBuilderInstruction21c((Instruction21c)instruction));
538                return;
539            case Format21ih:
540                setInstruction(location, newBuilderInstruction21ih((Instruction21ih)instruction));
541                return;
542            case Format21lh:
543                setInstruction(location, newBuilderInstruction21lh((Instruction21lh)instruction));
544                return;
545            case Format21s:
546                setInstruction(location, newBuilderInstruction21s((Instruction21s)instruction));
547                return;
548            case Format21t:
549                setInstruction(location, newBuilderInstruction21t(location.codeAddress, codeAddressToIndex,
550                        (Instruction21t)instruction));
551                return;
552            case Format22b:
553                setInstruction(location, newBuilderInstruction22b((Instruction22b)instruction));
554                return;
555            case Format22c:
556                setInstruction(location, newBuilderInstruction22c((Instruction22c)instruction));
557                return;
558            case Format22s:
559                setInstruction(location, newBuilderInstruction22s((Instruction22s)instruction));
560                return;
561            case Format22t:
562                setInstruction(location, newBuilderInstruction22t(location.codeAddress, codeAddressToIndex,
563                        (Instruction22t)instruction));
564                return;
565            case Format22x:
566                setInstruction(location, newBuilderInstruction22x((Instruction22x)instruction));
567                return;
568            case Format23x:
569                setInstruction(location, newBuilderInstruction23x((Instruction23x)instruction));
570                return;
571            case Format30t:
572                setInstruction(location, newBuilderInstruction30t(location.codeAddress, codeAddressToIndex,
573                        (Instruction30t)instruction));
574                return;
575            case Format31c:
576                setInstruction(location, newBuilderInstruction31c((Instruction31c)instruction));
577                return;
578            case Format31i:
579                setInstruction(location, newBuilderInstruction31i((Instruction31i)instruction));
580                return;
581            case Format31t:
582                setInstruction(location, newBuilderInstruction31t(location, codeAddressToIndex,
583                        (Instruction31t)instruction));
584                return;
585            case Format32x:
586                setInstruction(location, newBuilderInstruction32x((Instruction32x)instruction));
587                return;
588            case Format35c:
589                setInstruction(location, newBuilderInstruction35c((Instruction35c)instruction));
590                return;
591            case Format3rc:
592                setInstruction(location, newBuilderInstruction3rc((Instruction3rc)instruction));
593                return;
594            case Format51l:
595                setInstruction(location, newBuilderInstruction51l((Instruction51l)instruction));
596                return;
597            case PackedSwitchPayload:
598                setInstruction(location,
599                        newBuilderPackedSwitchPayload(location, codeAddressToIndex, (PackedSwitchPayload)instruction));
600                return;
601            case SparseSwitchPayload:
602                setInstruction(location,
603                        newBuilderSparseSwitchPayload(location, codeAddressToIndex, (SparseSwitchPayload)instruction));
604                return;
605            case ArrayPayload:
606                setInstruction(location, newBuilderArrayPayload((ArrayPayload)instruction));
607                return;
608            default:
609                throw new ExceptionWithContext("Instruction format %s not supported", instruction.getOpcode().format);
610        }
611    }
612
613    @Nonnull
614    private BuilderInstruction10t newBuilderInstruction10t(int codeAddress, int[] codeAddressToIndex,
615                                                           @Nonnull Instruction10t instruction) {
616        return new BuilderInstruction10t(
617                instruction.getOpcode(),
618                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
619    }
620
621    @Nonnull
622    private BuilderInstruction10x newBuilderInstruction10x(@Nonnull Instruction10x instruction) {
623        return new BuilderInstruction10x(
624                instruction.getOpcode());
625    }
626
627    @Nonnull
628    private BuilderInstruction11n newBuilderInstruction11n(@Nonnull Instruction11n instruction) {
629        return new BuilderInstruction11n(
630                instruction.getOpcode(),
631                instruction.getRegisterA(),
632                instruction.getNarrowLiteral());
633    }
634
635    @Nonnull
636    private BuilderInstruction11x newBuilderInstruction11x(@Nonnull Instruction11x instruction) {
637        return new BuilderInstruction11x(
638                instruction.getOpcode(),
639                instruction.getRegisterA());
640    }
641
642    @Nonnull
643    private BuilderInstruction12x newBuilderInstruction12x(@Nonnull Instruction12x instruction) {
644        return new BuilderInstruction12x(
645                instruction.getOpcode(),
646                instruction.getRegisterA(),
647                instruction.getRegisterB());
648    }
649
650    @Nonnull
651    private BuilderInstruction20bc newBuilderInstruction20bc(@Nonnull Instruction20bc instruction) {
652        return new BuilderInstruction20bc(
653                instruction.getOpcode(),
654                instruction.getVerificationError(),
655                instruction.getReference());
656    }
657
658    @Nonnull
659    private BuilderInstruction20t newBuilderInstruction20t(int codeAddress, int[] codeAddressToIndex,
660                                                           @Nonnull Instruction20t instruction) {
661        return new BuilderInstruction20t(
662                instruction.getOpcode(),
663                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
664    }
665
666    @Nonnull
667    private BuilderInstruction21c newBuilderInstruction21c(@Nonnull Instruction21c instruction) {
668        return new BuilderInstruction21c(
669                instruction.getOpcode(),
670                instruction.getRegisterA(),
671                instruction.getReference());
672    }
673
674    @Nonnull
675    private BuilderInstruction21ih newBuilderInstruction21ih(@Nonnull Instruction21ih instruction) {
676        return new BuilderInstruction21ih(
677                instruction.getOpcode(),
678                instruction.getRegisterA(),
679                instruction.getNarrowLiteral());
680    }
681
682    @Nonnull
683    private BuilderInstruction21lh newBuilderInstruction21lh(@Nonnull Instruction21lh instruction) {
684        return new BuilderInstruction21lh(
685                instruction.getOpcode(),
686                instruction.getRegisterA(),
687                instruction.getWideLiteral());
688    }
689
690    @Nonnull
691    private BuilderInstruction21s newBuilderInstruction21s(@Nonnull Instruction21s instruction) {
692        return new BuilderInstruction21s(
693                instruction.getOpcode(),
694                instruction.getRegisterA(),
695                instruction.getNarrowLiteral());
696    }
697
698    @Nonnull
699    private BuilderInstruction21t newBuilderInstruction21t(int codeAddress, int[] codeAddressToIndex,
700                                                           @Nonnull Instruction21t instruction) {
701        return new BuilderInstruction21t(
702                instruction.getOpcode(),
703                instruction.getRegisterA(),
704                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
705    }
706
707    @Nonnull
708    private BuilderInstruction22b newBuilderInstruction22b(@Nonnull Instruction22b instruction) {
709        return new BuilderInstruction22b(
710                instruction.getOpcode(),
711                instruction.getRegisterA(),
712                instruction.getRegisterB(),
713                instruction.getNarrowLiteral());
714    }
715
716    @Nonnull
717    private BuilderInstruction22c newBuilderInstruction22c(@Nonnull Instruction22c instruction) {
718        return new BuilderInstruction22c(
719                instruction.getOpcode(),
720                instruction.getRegisterA(),
721                instruction.getRegisterB(),
722                instruction.getReference());
723    }
724
725    @Nonnull
726    private BuilderInstruction22s newBuilderInstruction22s(@Nonnull Instruction22s instruction) {
727        return new BuilderInstruction22s(
728                instruction.getOpcode(),
729                instruction.getRegisterA(),
730                instruction.getRegisterB(),
731                instruction.getNarrowLiteral());
732    }
733
734    @Nonnull
735    private BuilderInstruction22t newBuilderInstruction22t(int codeAddress, int[] codeAddressToIndex,
736                                                           @Nonnull Instruction22t instruction) {
737        return new BuilderInstruction22t(
738                instruction.getOpcode(),
739                instruction.getRegisterA(),
740                instruction.getRegisterB(),
741                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
742    }
743
744    @Nonnull
745    private BuilderInstruction22x newBuilderInstruction22x(@Nonnull Instruction22x instruction) {
746        return new BuilderInstruction22x(
747                instruction.getOpcode(),
748                instruction.getRegisterA(),
749                instruction.getRegisterB());
750    }
751
752    @Nonnull
753    private BuilderInstruction23x newBuilderInstruction23x(@Nonnull Instruction23x instruction) {
754        return new BuilderInstruction23x(
755                instruction.getOpcode(),
756                instruction.getRegisterA(),
757                instruction.getRegisterB(),
758                instruction.getRegisterC());
759    }
760
761    @Nonnull
762    private BuilderInstruction30t newBuilderInstruction30t(int codeAddress, int[] codeAddressToIndex,
763                                                           @Nonnull Instruction30t instruction) {
764        return new BuilderInstruction30t(
765                instruction.getOpcode(),
766                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
767    }
768
769    @Nonnull
770    private BuilderInstruction31c newBuilderInstruction31c(@Nonnull Instruction31c instruction) {
771        return new BuilderInstruction31c(
772                instruction.getOpcode(),
773                instruction.getRegisterA(),
774                instruction.getReference());
775    }
776
777    @Nonnull
778    private BuilderInstruction31i newBuilderInstruction31i(@Nonnull Instruction31i instruction) {
779        return new BuilderInstruction31i(
780                instruction.getOpcode(),
781                instruction.getRegisterA(),
782                instruction.getNarrowLiteral());
783    }
784
785    @Nonnull
786    private BuilderInstruction31t newBuilderInstruction31t(@Nonnull MethodLocation location , int[] codeAddressToIndex,
787                                                           @Nonnull Instruction31t instruction) {
788        int codeAddress = location.getCodeAddress();
789        Label newLabel;
790        if (instruction.getOpcode() != Opcode.FILL_ARRAY_DATA) {
791            // if it's a sparse switch or packed switch
792            newLabel = newSwitchPayloadReferenceLabel(location, codeAddressToIndex, codeAddress + instruction.getCodeOffset());
793        } else {
794            newLabel = newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset());
795        }
796        return new BuilderInstruction31t(
797                instruction.getOpcode(),
798                instruction.getRegisterA(),
799                newLabel);
800    }
801
802    @Nonnull
803    private BuilderInstruction32x newBuilderInstruction32x(@Nonnull Instruction32x instruction) {
804        return new BuilderInstruction32x(
805                instruction.getOpcode(),
806                instruction.getRegisterA(),
807                instruction.getRegisterB());
808    }
809
810    @Nonnull
811    private BuilderInstruction35c newBuilderInstruction35c(@Nonnull Instruction35c instruction) {
812        return new BuilderInstruction35c(
813                instruction.getOpcode(),
814                instruction.getRegisterCount(),
815                instruction.getRegisterC(),
816                instruction.getRegisterD(),
817                instruction.getRegisterE(),
818                instruction.getRegisterF(),
819                instruction.getRegisterG(),
820                instruction.getReference());
821    }
822
823    @Nonnull
824    private BuilderInstruction3rc newBuilderInstruction3rc(@Nonnull Instruction3rc instruction) {
825        return new BuilderInstruction3rc(
826                instruction.getOpcode(),
827                instruction.getStartRegister(),
828                instruction.getRegisterCount(),
829                instruction.getReference());
830    }
831
832    @Nonnull
833    private BuilderInstruction51l newBuilderInstruction51l(@Nonnull Instruction51l instruction) {
834        return new BuilderInstruction51l(
835                instruction.getOpcode(),
836                instruction.getRegisterA(),
837                instruction.getWideLiteral());
838    }
839
840    @Nullable
841    private MethodLocation findSwitchForPayload(@Nonnull MethodLocation payloadLocation) {
842        MethodLocation location = payloadLocation;
843        MethodLocation switchLocation = null;
844        do {
845            for (Label label: location.getLabels()) {
846                if (label instanceof SwitchPayloadReferenceLabel) {
847                    if (switchLocation != null) {
848                        throw new IllegalStateException("Multiple switch instructions refer to the same payload. " +
849                                "This is not currently supported. Please file a bug :)");
850                    }
851                    switchLocation = ((SwitchPayloadReferenceLabel)label).switchLocation;
852                }
853            }
854
855            // A switch instruction can refer to the payload instruction itself, or to a nop before the payload
856            // instruction.
857            // We need to search for all occurrences of a switch reference, so we can detect when multiple switch
858            // statements refer to the same payload
859            // TODO: confirm that it could refer to the first NOP in a series of NOPs preceding the payload
860            if (location.index == 0) {
861                return switchLocation;
862            }
863            location = instructionList.get(location.index - 1);
864            if (location.instruction == null || location.instruction.getOpcode() != Opcode.NOP) {
865                return switchLocation;
866            }
867        } while (true);
868    }
869
870    @Nonnull
871    private BuilderPackedSwitchPayload newBuilderPackedSwitchPayload(@Nonnull MethodLocation location,
872                                                                     @Nonnull int[] codeAddressToIndex,
873                                                                     @Nonnull PackedSwitchPayload instruction) {
874        List<? extends SwitchElement> switchElements = instruction.getSwitchElements();
875        if (switchElements.size() == 0) {
876            return new BuilderPackedSwitchPayload(0, null);
877        }
878
879        MethodLocation switchLocation = findSwitchForPayload(location);
880        int baseAddress;
881        if (switchLocation == null) {
882            baseAddress = 0;
883        } else {
884            baseAddress = switchLocation.codeAddress;
885        }
886
887        List<Label> labels = Lists.newArrayList();
888        for (SwitchElement element: switchElements) {
889            labels.add(newLabel(codeAddressToIndex, element.getOffset() + baseAddress));
890        }
891
892        return new BuilderPackedSwitchPayload(switchElements.get(0).getKey(), labels);
893    }
894
895    @Nonnull
896    private BuilderSparseSwitchPayload newBuilderSparseSwitchPayload(@Nonnull MethodLocation location,
897                                                                     @Nonnull int[] codeAddressToIndex,
898                                                                     @Nonnull SparseSwitchPayload instruction) {
899        List<? extends SwitchElement> switchElements = instruction.getSwitchElements();
900        if (switchElements.size() == 0) {
901            return new BuilderSparseSwitchPayload(null);
902        }
903
904        MethodLocation switchLocation = findSwitchForPayload(location);
905        int baseAddress;
906        if (switchLocation == null) {
907            baseAddress = 0;
908        } else {
909            baseAddress = switchLocation.codeAddress;
910        }
911
912        List<SwitchLabelElement> labelElements = Lists.newArrayList();
913        for (SwitchElement element: switchElements) {
914            labelElements.add(new SwitchLabelElement(element.getKey(),
915                    newLabel(codeAddressToIndex, element.getOffset() + baseAddress)));
916        }
917
918        return new BuilderSparseSwitchPayload(labelElements);
919    }
920
921    @Nonnull
922    private BuilderArrayPayload newBuilderArrayPayload(@Nonnull ArrayPayload instruction) {
923        return new BuilderArrayPayload(instruction.getElementWidth(), instruction.getArrayElements());
924    }
925
926    @Nonnull
927    private BuilderDebugItem convertDebugItem(@Nonnull DebugItem debugItem) {
928        switch (debugItem.getDebugItemType()) {
929            case DebugItemType.START_LOCAL: {
930                StartLocal startLocal = (StartLocal)debugItem;
931                return new BuilderStartLocal(startLocal.getRegister(), startLocal.getNameReference(),
932                        startLocal.getTypeReference(), startLocal.getSignatureReference());
933            }
934            case DebugItemType.END_LOCAL: {
935                EndLocal endLocal = (EndLocal)debugItem;
936                return new BuilderEndLocal(endLocal.getRegister());
937            }
938            case DebugItemType.RESTART_LOCAL: {
939                RestartLocal restartLocal = (RestartLocal)debugItem;
940                return new BuilderRestartLocal(restartLocal.getRegister());
941            }
942            case DebugItemType.PROLOGUE_END:
943                return new BuilderPrologueEnd();
944            case DebugItemType.EPILOGUE_BEGIN:
945                return new BuilderEpilogueBegin();
946            case DebugItemType.LINE_NUMBER: {
947                LineNumber lineNumber = (LineNumber)debugItem;
948                return new BuilderLineNumber(lineNumber.getLineNumber());
949            }
950            case DebugItemType.SET_SOURCE_FILE: {
951                SetSourceFile setSourceFile = (SetSourceFile)debugItem;
952                return new BuilderSetSourceFile(setSourceFile.getSourceFileReference());
953            }
954            default:
955                throw new ExceptionWithContext("Invalid debug item type: " + debugItem.getDebugItemType());
956        }
957    }
958}
959