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 instructions must be converted last, so that any switch statements that refer to them have
100        // 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
217        instructionList.add(index, new MethodLocation(instruction, codeAddress, index));
218        codeAddress += instruction.getCodeUnits();
219
220        for (int i=index+1; i<instructionList.size(); i++) {
221            MethodLocation location = instructionList.get(i);
222            location.index++;
223            location.codeAddress = codeAddress;
224            if (location.instruction != null) {
225                codeAddress += location.instruction.getCodeUnits();
226            } else {
227                // only the last MethodLocation should have a null instruction
228                assert i == instructionList.size()-1;
229            }
230        }
231
232        this.fixInstructions = true;
233    }
234
235    public void addInstruction(@Nonnull BuilderInstruction instruction) {
236        MethodLocation last = instructionList.get(instructionList.size()-1);
237        last.instruction = instruction;
238        instruction.location = last;
239
240        int nextCodeAddress = last.codeAddress + instruction.getCodeUnits();
241        instructionList.add(new MethodLocation(null, nextCodeAddress, instructionList.size()));
242
243        this.fixInstructions = true;
244    }
245
246    public void replaceInstruction(int index, @Nonnull BuilderInstruction replacementInstruction) {
247        if (index >= instructionList.size() - 1) {
248            throw new IndexOutOfBoundsException();
249        }
250
251        MethodLocation replaceLocation = instructionList.get(index);
252        replacementInstruction.location = replaceLocation;
253        BuilderInstruction old = replaceLocation.instruction;
254        assert old != null;
255        old.location = null;
256        replaceLocation.instruction = replacementInstruction;
257
258        // TODO: factor out index/address fix up loop
259        int codeAddress = replaceLocation.codeAddress + replaceLocation.instruction.getCodeUnits();
260        for (int i=index+1; i<instructionList.size(); i++) {
261            MethodLocation location = instructionList.get(i);
262            location.codeAddress = codeAddress;
263
264            Instruction instruction = location.getInstruction();
265            if (instruction != null) {
266                codeAddress += instruction.getCodeUnits();
267            } else {
268                assert i == instructionList.size() - 1;
269            }
270        }
271
272        this.fixInstructions = true;
273    }
274
275    public void removeInstruction(int index) {
276        if (index >= instructionList.size() - 1) {
277            throw new IndexOutOfBoundsException();
278        }
279
280        MethodLocation toRemove = instructionList.get(index);
281        toRemove.instruction = null;
282        MethodLocation next = instructionList.get(index+1);
283        toRemove.mergeInto(next);
284
285        instructionList.remove(index);
286        int codeAddress = toRemove.codeAddress;
287        for (int i=index; i<instructionList.size(); i++) {
288            MethodLocation location = instructionList.get(i);
289            location.index = i;
290            location.codeAddress = codeAddress;
291
292            Instruction instruction = location.getInstruction();
293            if (instruction != null) {
294                codeAddress += instruction.getCodeUnits();
295            } else {
296                assert i == instructionList.size() - 1;
297            }
298        }
299
300        this.fixInstructions = true;
301    }
302
303    public void swapInstructions(int index1, int index2) {
304        if (index1 >= instructionList.size() - 1 || index2 >= instructionList.size() - 1) {
305            throw new IndexOutOfBoundsException();
306        }
307        MethodLocation first = instructionList.get(index1);
308        MethodLocation second = instructionList.get(index2);
309
310        // only the last MethodLocation may have a null instruction
311        assert first.instruction != null;
312        assert second.instruction != null;
313
314        first.instruction.location = second;
315        second.instruction.location = first;
316
317        {
318            BuilderInstruction tmp = second.instruction;
319            second.instruction = first.instruction;
320            first.instruction = tmp;
321        }
322
323        if (index2 < index1) {
324            int tmp = index2;
325            index2 = index1;
326            index1 = tmp;
327        }
328
329        int codeAddress = first.codeAddress + first.instruction.getCodeUnits();
330        for (int i=index1+1; i<=index2; i++) {
331            MethodLocation location = instructionList.get(i);
332            location.codeAddress = codeAddress;
333
334            Instruction instruction = location.instruction;
335            assert instruction != null;
336            codeAddress += location.instruction.getCodeUnits();
337        }
338
339        this.fixInstructions = true;
340    }
341
342    @Nullable
343    private BuilderInstruction getFirstNonNop(int startIndex) {
344
345        for (int i=startIndex; i<instructionList.size()-1; i++) {
346            BuilderInstruction instruction = instructionList.get(i).instruction;
347            assert instruction != null;
348            if (instruction.getOpcode() != Opcode.NOP) {
349                return instruction;
350            }
351        }
352        return null;
353    }
354
355    private void fixInstructions() {
356        HashSet<MethodLocation> payloadLocations = Sets.newHashSet();
357
358        for (MethodLocation location: instructionList) {
359            BuilderInstruction instruction = location.instruction;
360            if (instruction != null) {
361                switch (instruction.getOpcode()) {
362                    case SPARSE_SWITCH:
363                    case PACKED_SWITCH: {
364                        MethodLocation targetLocation =
365                                ((BuilderOffsetInstruction)instruction).getTarget().getLocation();
366                        BuilderInstruction targetInstruction = targetLocation.instruction;
367                        if (targetInstruction == null) {
368                            throw new IllegalStateException(String.format("Switch instruction at address/index " +
369                                    "0x%x/%d points to the end of the method.", location.codeAddress, location.index));
370                        }
371
372                        if (targetInstruction.getOpcode() == Opcode.NOP) {
373                            targetInstruction = getFirstNonNop(targetLocation.index+1);
374                        }
375                        if (targetInstruction == null || !(targetInstruction instanceof BuilderSwitchPayload)) {
376                            throw new IllegalStateException(String.format("Switch instruction at address/index " +
377                                    "0x%x/%d does not refer to a payload instruction.",
378                                    location.codeAddress, location.index));
379                        }
380                        if ((instruction.opcode == Opcode.PACKED_SWITCH &&
381                                targetInstruction.getOpcode() != Opcode.PACKED_SWITCH_PAYLOAD) ||
382                            (instruction.opcode == Opcode.SPARSE_SWITCH &&
383                                targetInstruction.getOpcode() != Opcode.SPARSE_SWITCH_PAYLOAD)) {
384                            throw new IllegalStateException(String.format("Switch instruction at address/index " +
385                                    "0x%x/%d refers to the wrong type of payload instruction.",
386                                    location.codeAddress, location.index));
387                        }
388
389                        if (!payloadLocations.add(targetLocation)) {
390                            throw new IllegalStateException("Multiple switch instructions refer to the same payload. " +
391                                    "This is not currently supported. Please file a bug :)");
392                        }
393
394                        ((BuilderSwitchPayload)targetInstruction).referrer = location;
395                        break;
396                    }
397                }
398            }
399        }
400
401        boolean madeChanges;
402        do {
403            madeChanges = false;
404
405            for (int index=0; index<instructionList.size(); index++) {
406                MethodLocation location = instructionList.get(index);
407                BuilderInstruction instruction = location.instruction;
408                if (instruction != null) {
409                    switch (instruction.getOpcode()) {
410                        case GOTO: {
411                            int offset = ((BuilderOffsetInstruction)instruction).internalGetCodeOffset();
412                            if (offset < Byte.MIN_VALUE || offset > Byte.MAX_VALUE) {
413                                BuilderOffsetInstruction replacement;
414                                if (offset < Short.MIN_VALUE || offset > Short.MAX_VALUE) {
415                                    replacement = new BuilderInstruction30t(Opcode.GOTO_32,
416                                            ((BuilderOffsetInstruction)instruction).getTarget());
417                                } else {
418                                    replacement = new BuilderInstruction20t(Opcode.GOTO_16,
419                                            ((BuilderOffsetInstruction)instruction).getTarget());
420                                }
421                                replaceInstruction(location.index, replacement);
422                                madeChanges = true;
423                            }
424                            break;
425                        }
426                        case GOTO_16: {
427                            int offset = ((BuilderOffsetInstruction)instruction).internalGetCodeOffset();
428                            if (offset < Short.MIN_VALUE || offset > Short.MAX_VALUE) {
429                                BuilderOffsetInstruction replacement =  new BuilderInstruction30t(Opcode.GOTO_32,
430                                            ((BuilderOffsetInstruction)instruction).getTarget());
431                                replaceInstruction(location.index, replacement);
432                                madeChanges = true;
433                            }
434                            break;
435                        }
436                        case SPARSE_SWITCH_PAYLOAD:
437                        case PACKED_SWITCH_PAYLOAD:
438                            if (((BuilderSwitchPayload)instruction).referrer == null) {
439                                // if the switch payload isn't referenced, just remove it
440                                removeInstruction(index);
441                                index--;
442                                madeChanges = true;
443                                break;
444                            }
445                            // intentional fall-through
446                        case ARRAY_PAYLOAD: {
447                            if ((location.codeAddress & 0x01) != 0) {
448                                int previousIndex = location.index - 1;
449                                MethodLocation previousLocation = instructionList.get(previousIndex);
450                                Instruction previousInstruction = previousLocation.instruction;
451                                assert previousInstruction != null;
452                                if (previousInstruction.getOpcode() == Opcode.NOP) {
453                                    removeInstruction(previousIndex);
454                                    index--;
455                                } else {
456                                    addInstruction(location.index, new BuilderInstruction10x(Opcode.NOP));
457                                    index++;
458                                }
459                                madeChanges = true;
460                            }
461                            break;
462                        }
463                    }
464                }
465            }
466        } while (madeChanges);
467
468        fixInstructions = false;
469    }
470
471    private int mapCodeAddressToIndex(@Nonnull int[] codeAddressToIndex, int codeAddress) {
472        int index;
473        do {
474            index = codeAddressToIndex[codeAddress];
475            if (index < 0) {
476                codeAddress--;
477            } else {
478                return index;
479            }
480        } while (true);
481    }
482
483    @Nonnull
484    private Label newLabel(@Nonnull int[] codeAddressToIndex, int codeAddress) {
485        MethodLocation referent = instructionList.get(mapCodeAddressToIndex(codeAddressToIndex, codeAddress));
486        return referent.addNewLabel();
487    }
488
489    private static class SwitchPayloadReferenceLabel extends Label {
490        @Nonnull public MethodLocation switchLocation;
491    }
492
493    @Nonnull
494    public Label newSwitchPayloadReferenceLabel(@Nonnull MethodLocation switchLocation,
495                                                @Nonnull int[] codeAddressToIndex, int codeAddress) {
496        MethodLocation referent = instructionList.get(mapCodeAddressToIndex(codeAddressToIndex, codeAddress));
497        SwitchPayloadReferenceLabel label = new SwitchPayloadReferenceLabel();
498        label.switchLocation = switchLocation;
499        referent.getLabels().add(label);
500        return label;
501    }
502
503    private void setInstruction(@Nonnull MethodLocation location, @Nonnull BuilderInstruction instruction) {
504        location.instruction = instruction;
505        instruction.location = location;
506    }
507
508    private void convertAndSetInstruction(@Nonnull MethodLocation location, int[] codeAddressToIndex,
509                                          @Nonnull Instruction instruction) {
510        switch (instruction.getOpcode().format) {
511            case Format10t:
512                setInstruction(location, newBuilderInstruction10t(location.codeAddress, codeAddressToIndex,
513                        (Instruction10t)instruction));
514                return;
515            case Format10x:
516                setInstruction(location, newBuilderInstruction10x((Instruction10x)instruction));
517                return;
518            case Format11n:
519                setInstruction(location, newBuilderInstruction11n((Instruction11n)instruction));
520                return;
521            case Format11x:
522                setInstruction(location, newBuilderInstruction11x((Instruction11x)instruction));
523                return;
524            case Format12x:
525                setInstruction(location, newBuilderInstruction12x((Instruction12x)instruction));
526                return;
527            case Format20bc:
528                setInstruction(location, newBuilderInstruction20bc((Instruction20bc)instruction));
529                return;
530            case Format20t:
531                setInstruction(location, newBuilderInstruction20t(location.codeAddress, codeAddressToIndex,
532                        (Instruction20t)instruction));
533                return;
534            case Format21c:
535                setInstruction(location, newBuilderInstruction21c((Instruction21c)instruction));
536                return;
537            case Format21ih:
538                setInstruction(location, newBuilderInstruction21ih((Instruction21ih)instruction));
539                return;
540            case Format21lh:
541                setInstruction(location, newBuilderInstruction21lh((Instruction21lh)instruction));
542                return;
543            case Format21s:
544                setInstruction(location, newBuilderInstruction21s((Instruction21s)instruction));
545                return;
546            case Format21t:
547                setInstruction(location, newBuilderInstruction21t(location.codeAddress, codeAddressToIndex,
548                        (Instruction21t)instruction));
549                return;
550            case Format22b:
551                setInstruction(location, newBuilderInstruction22b((Instruction22b)instruction));
552                return;
553            case Format22c:
554                setInstruction(location, newBuilderInstruction22c((Instruction22c)instruction));
555                return;
556            case Format22s:
557                setInstruction(location, newBuilderInstruction22s((Instruction22s)instruction));
558                return;
559            case Format22t:
560                setInstruction(location, newBuilderInstruction22t(location.codeAddress, codeAddressToIndex,
561                        (Instruction22t)instruction));
562                return;
563            case Format22x:
564                setInstruction(location, newBuilderInstruction22x((Instruction22x)instruction));
565                return;
566            case Format23x:
567                setInstruction(location, newBuilderInstruction23x((Instruction23x)instruction));
568                return;
569            case Format30t:
570                setInstruction(location, newBuilderInstruction30t(location.codeAddress, codeAddressToIndex,
571                        (Instruction30t)instruction));
572                return;
573            case Format31c:
574                setInstruction(location, newBuilderInstruction31c((Instruction31c)instruction));
575                return;
576            case Format31i:
577                setInstruction(location, newBuilderInstruction31i((Instruction31i)instruction));
578                return;
579            case Format31t:
580                setInstruction(location, newBuilderInstruction31t(location, codeAddressToIndex,
581                        (Instruction31t)instruction));
582                return;
583            case Format32x:
584                setInstruction(location, newBuilderInstruction32x((Instruction32x)instruction));
585                return;
586            case Format35c:
587                setInstruction(location, newBuilderInstruction35c((Instruction35c)instruction));
588                return;
589            case Format3rc:
590                setInstruction(location, newBuilderInstruction3rc((Instruction3rc)instruction));
591                return;
592            case Format51l:
593                setInstruction(location, newBuilderInstruction51l((Instruction51l)instruction));
594                return;
595            case PackedSwitchPayload:
596                setInstruction(location,
597                        newBuilderPackedSwitchPayload(location, codeAddressToIndex, (PackedSwitchPayload)instruction));
598                return;
599            case SparseSwitchPayload:
600                setInstruction(location,
601                        newBuilderSparseSwitchPayload(location, codeAddressToIndex, (SparseSwitchPayload)instruction));
602                return;
603            case ArrayPayload:
604                setInstruction(location, newBuilderArrayPayload((ArrayPayload)instruction));
605                return;
606            default:
607                throw new ExceptionWithContext("Instruction format %s not supported", instruction.getOpcode().format);
608        }
609    }
610
611    @Nonnull
612    private BuilderInstruction10t newBuilderInstruction10t(int codeAddress, int[] codeAddressToIndex,
613                                                           @Nonnull Instruction10t instruction) {
614        return new BuilderInstruction10t(
615                instruction.getOpcode(),
616                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
617    }
618
619    @Nonnull
620    private BuilderInstruction10x newBuilderInstruction10x(@Nonnull Instruction10x instruction) {
621        return new BuilderInstruction10x(
622                instruction.getOpcode());
623    }
624
625    @Nonnull
626    private BuilderInstruction11n newBuilderInstruction11n(@Nonnull Instruction11n instruction) {
627        return new BuilderInstruction11n(
628                instruction.getOpcode(),
629                instruction.getRegisterA(),
630                instruction.getNarrowLiteral());
631    }
632
633    @Nonnull
634    private BuilderInstruction11x newBuilderInstruction11x(@Nonnull Instruction11x instruction) {
635        return new BuilderInstruction11x(
636                instruction.getOpcode(),
637                instruction.getRegisterA());
638    }
639
640    @Nonnull
641    private BuilderInstruction12x newBuilderInstruction12x(@Nonnull Instruction12x instruction) {
642        return new BuilderInstruction12x(
643                instruction.getOpcode(),
644                instruction.getRegisterA(),
645                instruction.getRegisterB());
646    }
647
648    @Nonnull
649    private BuilderInstruction20bc newBuilderInstruction20bc(@Nonnull Instruction20bc instruction) {
650        return new BuilderInstruction20bc(
651                instruction.getOpcode(),
652                instruction.getVerificationError(),
653                instruction.getReference());
654    }
655
656    @Nonnull
657    private BuilderInstruction20t newBuilderInstruction20t(int codeAddress, int[] codeAddressToIndex,
658                                                           @Nonnull Instruction20t instruction) {
659        return new BuilderInstruction20t(
660                instruction.getOpcode(),
661                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
662    }
663
664    @Nonnull
665    private BuilderInstruction21c newBuilderInstruction21c(@Nonnull Instruction21c instruction) {
666        return new BuilderInstruction21c(
667                instruction.getOpcode(),
668                instruction.getRegisterA(),
669                instruction.getReference());
670    }
671
672    @Nonnull
673    private BuilderInstruction21ih newBuilderInstruction21ih(@Nonnull Instruction21ih instruction) {
674        return new BuilderInstruction21ih(
675                instruction.getOpcode(),
676                instruction.getRegisterA(),
677                instruction.getNarrowLiteral());
678    }
679
680    @Nonnull
681    private BuilderInstruction21lh newBuilderInstruction21lh(@Nonnull Instruction21lh instruction) {
682        return new BuilderInstruction21lh(
683                instruction.getOpcode(),
684                instruction.getRegisterA(),
685                instruction.getWideLiteral());
686    }
687
688    @Nonnull
689    private BuilderInstruction21s newBuilderInstruction21s(@Nonnull Instruction21s instruction) {
690        return new BuilderInstruction21s(
691                instruction.getOpcode(),
692                instruction.getRegisterA(),
693                instruction.getNarrowLiteral());
694    }
695
696    @Nonnull
697    private BuilderInstruction21t newBuilderInstruction21t(int codeAddress, int[] codeAddressToIndex,
698                                                           @Nonnull Instruction21t instruction) {
699        return new BuilderInstruction21t(
700                instruction.getOpcode(),
701                instruction.getRegisterA(),
702                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
703    }
704
705    @Nonnull
706    private BuilderInstruction22b newBuilderInstruction22b(@Nonnull Instruction22b instruction) {
707        return new BuilderInstruction22b(
708                instruction.getOpcode(),
709                instruction.getRegisterA(),
710                instruction.getRegisterB(),
711                instruction.getNarrowLiteral());
712    }
713
714    @Nonnull
715    private BuilderInstruction22c newBuilderInstruction22c(@Nonnull Instruction22c instruction) {
716        return new BuilderInstruction22c(
717                instruction.getOpcode(),
718                instruction.getRegisterA(),
719                instruction.getRegisterB(),
720                instruction.getReference());
721    }
722
723    @Nonnull
724    private BuilderInstruction22s newBuilderInstruction22s(@Nonnull Instruction22s instruction) {
725        return new BuilderInstruction22s(
726                instruction.getOpcode(),
727                instruction.getRegisterA(),
728                instruction.getRegisterB(),
729                instruction.getNarrowLiteral());
730    }
731
732    @Nonnull
733    private BuilderInstruction22t newBuilderInstruction22t(int codeAddress, int[] codeAddressToIndex,
734                                                           @Nonnull Instruction22t instruction) {
735        return new BuilderInstruction22t(
736                instruction.getOpcode(),
737                instruction.getRegisterA(),
738                instruction.getRegisterB(),
739                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
740    }
741
742    @Nonnull
743    private BuilderInstruction22x newBuilderInstruction22x(@Nonnull Instruction22x instruction) {
744        return new BuilderInstruction22x(
745                instruction.getOpcode(),
746                instruction.getRegisterA(),
747                instruction.getRegisterB());
748    }
749
750    @Nonnull
751    private BuilderInstruction23x newBuilderInstruction23x(@Nonnull Instruction23x instruction) {
752        return new BuilderInstruction23x(
753                instruction.getOpcode(),
754                instruction.getRegisterA(),
755                instruction.getRegisterB(),
756                instruction.getRegisterC());
757    }
758
759    @Nonnull
760    private BuilderInstruction30t newBuilderInstruction30t(int codeAddress, int[] codeAddressToIndex,
761                                                           @Nonnull Instruction30t instruction) {
762        return new BuilderInstruction30t(
763                instruction.getOpcode(),
764                newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset()));
765    }
766
767    @Nonnull
768    private BuilderInstruction31c newBuilderInstruction31c(@Nonnull Instruction31c instruction) {
769        return new BuilderInstruction31c(
770                instruction.getOpcode(),
771                instruction.getRegisterA(),
772                instruction.getReference());
773    }
774
775    @Nonnull
776    private BuilderInstruction31i newBuilderInstruction31i(@Nonnull Instruction31i instruction) {
777        return new BuilderInstruction31i(
778                instruction.getOpcode(),
779                instruction.getRegisterA(),
780                instruction.getNarrowLiteral());
781    }
782
783    @Nonnull
784    private BuilderInstruction31t newBuilderInstruction31t(@Nonnull MethodLocation location , int[] codeAddressToIndex,
785                                                           @Nonnull Instruction31t instruction) {
786        int codeAddress = location.getCodeAddress();
787        Label newLabel;
788        if (instruction.getOpcode() != Opcode.FILL_ARRAY_DATA) {
789            // if it's a sparse switch or packed switch
790            newLabel = newSwitchPayloadReferenceLabel(location, codeAddressToIndex, codeAddress + instruction.getCodeOffset());
791        } else {
792            newLabel = newLabel(codeAddressToIndex, codeAddress + instruction.getCodeOffset());
793        }
794        return new BuilderInstruction31t(
795                instruction.getOpcode(),
796                instruction.getRegisterA(),
797                newLabel);
798    }
799
800    @Nonnull
801    private BuilderInstruction32x newBuilderInstruction32x(@Nonnull Instruction32x instruction) {
802        return new BuilderInstruction32x(
803                instruction.getOpcode(),
804                instruction.getRegisterA(),
805                instruction.getRegisterB());
806    }
807
808    @Nonnull
809    private BuilderInstruction35c newBuilderInstruction35c(@Nonnull Instruction35c instruction) {
810        return new BuilderInstruction35c(
811                instruction.getOpcode(),
812                instruction.getRegisterCount(),
813                instruction.getRegisterC(),
814                instruction.getRegisterD(),
815                instruction.getRegisterE(),
816                instruction.getRegisterF(),
817                instruction.getRegisterG(),
818                instruction.getReference());
819    }
820
821    @Nonnull
822    private BuilderInstruction3rc newBuilderInstruction3rc(@Nonnull Instruction3rc instruction) {
823        return new BuilderInstruction3rc(
824                instruction.getOpcode(),
825                instruction.getStartRegister(),
826                instruction.getRegisterCount(),
827                instruction.getReference());
828    }
829
830    @Nonnull
831    private BuilderInstruction51l newBuilderInstruction51l(@Nonnull Instruction51l instruction) {
832        return new BuilderInstruction51l(
833                instruction.getOpcode(),
834                instruction.getRegisterA(),
835                instruction.getWideLiteral());
836    }
837
838    @Nullable
839    private MethodLocation findSwitchForPayload(@Nonnull MethodLocation payloadLocation) {
840        MethodLocation location = payloadLocation;
841        MethodLocation switchLocation = null;
842        do {
843            for (Label label: location.getLabels()) {
844                if (label instanceof SwitchPayloadReferenceLabel) {
845                    if (switchLocation != null) {
846                        throw new IllegalStateException("Multiple switch instructions refer to the same payload. " +
847                                "This is not currently supported. Please file a bug :)");
848                    }
849                    switchLocation = ((SwitchPayloadReferenceLabel)label).switchLocation;
850                }
851            }
852
853            // A switch instruction can refer to the payload instruction itself, or to a nop before the payload
854            // instruction.
855            // We need to search for all occurrences of a switch reference, so we can detect when multiple switch
856            // statements refer to the same payload
857            // TODO: confirm that it could refer to the first NOP in a series of NOPs preceding the payload
858            if (location.index == 0) {
859                return switchLocation;
860            }
861            location = instructionList.get(location.index - 1);
862            if (location.instruction == null || location.instruction.getOpcode() != Opcode.NOP) {
863                return switchLocation;
864            }
865        } while (true);
866    }
867
868    @Nonnull
869    private BuilderPackedSwitchPayload newBuilderPackedSwitchPayload(@Nonnull MethodLocation location,
870                                                                     @Nonnull int[] codeAddressToIndex,
871                                                                     @Nonnull PackedSwitchPayload instruction) {
872        List<? extends SwitchElement> switchElements = instruction.getSwitchElements();
873        if (switchElements.size() == 0) {
874            return new BuilderPackedSwitchPayload(0, null);
875        }
876
877        MethodLocation switchLocation = findSwitchForPayload(location);
878        int baseAddress;
879        if (switchLocation == null) {
880            baseAddress = 0;
881        } else {
882            baseAddress = switchLocation.codeAddress;
883        }
884
885        List<Label> labels = Lists.newArrayList();
886        for (SwitchElement element: switchElements) {
887            labels.add(newLabel(codeAddressToIndex, element.getOffset() + baseAddress));
888        }
889
890        return new BuilderPackedSwitchPayload(switchElements.get(0).getKey(), labels);
891    }
892
893    @Nonnull
894    private BuilderSparseSwitchPayload newBuilderSparseSwitchPayload(@Nonnull MethodLocation location,
895                                                                     @Nonnull int[] codeAddressToIndex,
896                                                                     @Nonnull SparseSwitchPayload instruction) {
897        List<? extends SwitchElement> switchElements = instruction.getSwitchElements();
898        if (switchElements.size() == 0) {
899            return new BuilderSparseSwitchPayload(null);
900        }
901
902        MethodLocation switchLocation = findSwitchForPayload(location);
903        int baseAddress;
904        if (switchLocation == null) {
905            baseAddress = 0;
906        } else {
907            baseAddress = switchLocation.codeAddress;
908        }
909
910        List<SwitchLabelElement> labelElements = Lists.newArrayList();
911        for (SwitchElement element: switchElements) {
912            labelElements.add(new SwitchLabelElement(element.getKey(),
913                    newLabel(codeAddressToIndex, element.getOffset() + baseAddress)));
914        }
915
916        return new BuilderSparseSwitchPayload(labelElements);
917    }
918
919    @Nonnull
920    private BuilderArrayPayload newBuilderArrayPayload(@Nonnull ArrayPayload instruction) {
921        return new BuilderArrayPayload(instruction.getElementWidth(), instruction.getArrayElements());
922    }
923
924    @Nonnull
925    private BuilderDebugItem convertDebugItem(@Nonnull DebugItem debugItem) {
926        switch (debugItem.getDebugItemType()) {
927            case DebugItemType.START_LOCAL: {
928                StartLocal startLocal = (StartLocal)debugItem;
929                return new BuilderStartLocal(startLocal.getRegister(), startLocal.getNameReference(),
930                        startLocal.getTypeReference(), startLocal.getSignatureReference());
931            }
932            case DebugItemType.END_LOCAL: {
933                EndLocal endLocal = (EndLocal)debugItem;
934                return new BuilderEndLocal(endLocal.getRegister());
935            }
936            case DebugItemType.RESTART_LOCAL: {
937                RestartLocal restartLocal = (RestartLocal)debugItem;
938                return new BuilderRestartLocal(restartLocal.getRegister());
939            }
940            case DebugItemType.PROLOGUE_END:
941                return new BuilderPrologueEnd();
942            case DebugItemType.EPILOGUE_BEGIN:
943                return new BuilderEpilogueBegin();
944            case DebugItemType.LINE_NUMBER: {
945                LineNumber lineNumber = (LineNumber)debugItem;
946                return new BuilderLineNumber(lineNumber.getLineNumber());
947            }
948            case DebugItemType.SET_SOURCE_FILE: {
949                SetSourceFile setSourceFile = (SetSourceFile)debugItem;
950                return new BuilderSetSourceFile(setSourceFile.getSourceFileReference());
951            }
952            default:
953                throw new ExceptionWithContext("Invalid debug item type: " + debugItem.getDebugItemType());
954        }
955    }
956}
957