    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one
    003 * or more contributor license agreements.  See the NOTICE file
    004 * distributed with this work for additional information
    005 * regarding copyright ownership.  The ASF licenses this file
    006 * to you under the Apache License, Version 2.0 (the
    007 * "License"); you may not use this file except in compliance
    008 * with the License.  You may obtain a copy of the License at
    009 *
    010 *   https://www.apache.org/licenses/LICENSE-2.0
    011 *
    012 * Unless required by applicable law or agreed to in writing,
    013 * software distributed under the License is distributed on an
    014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    015 * KIND, either express or implied.  See the License for the
    016 * specific language governing permissions and limitations
    017 * under the License.
    018 */
    019package org.apache.bcel.generic;
    020
    021import java.io.ByteArrayOutputStream;
    022import java.io.DataOutputStream;
    023import java.io.IOException;
    024import java.util.ArrayList;
    025import java.util.Arrays;
    026import java.util.HashMap;
    027import java.util.Iterator;
    028import java.util.List;
    029import java.util.Map;
    030import java.util.NoSuchElementException;
    031
    032import org.apache.bcel.Const;
    033import org.apache.bcel.classfile.Constant;
    034import org.apache.bcel.util.ByteSequence;
    035import org.apache.commons.lang3.ArrayUtils;
    036import org.apache.commons.lang3.stream.Streams;
    037
    038/**
    039 * This class is a container for a list of <a href="Instruction.html">Instruction</a> objects. Instructions can be appended, inserted, moved, deleted, and so
    040 * on. Instructions are being wrapped into <a href="InstructionHandle.html">InstructionHandles</a> objects that are returned upon append/insert operations. They
    041 * give the user (read only) access to the list structure, such that it can be traversed and manipulated in a controlled way.
    042 * <p>
    043 * A list is finally dumped to a byte code array with <a href="#getByteCode()">getByteCode</a>.
    044 * </p>
    045 *
    046 * @see Instruction
    047 * @see InstructionHandle
    048 * @see BranchHandle
    049 */
    050public class InstructionList implements Iterable<InstructionHandle> {
    051
    052    /**
    053     * Find the target instruction (handle) that corresponds to the given target position (byte code offset).
    054     *
    055     * @param ihs array of instruction handles, for example il.getInstructionHandles().
    056     * @param pos array of positions corresponding to ihs, for example il.getInstructionPositions().
    057     * @param count length of arrays.
    058     * @param target target position to search for.
    059     * @return target position's instruction handle if available.
    060     */
    061    public static InstructionHandle findHandle(final InstructionHandle[] ihs, final int[] pos, final int count, final int target) {
    062        if (ihs != null && pos != null) {
    063            int l = 0;
    064            int r = count - 1;
    065            /*
    066             * Do a binary search since the pos array is orderd.
    067             */
    068            do {
    069                final int i = l + r >>> 1;
    070                final int j = pos[i];
    071                if (j == target) {
    072                    return ihs[i];
    073                }
    074                if (target < j) {
    075                    r = i - 1;
    076                } else {
    077                    l = i + 1;
    078                }
    079            } while (l <= r);
    080        }
    081        return null;
    082    }
    083
    084    private InstructionHandle start;
    085    private InstructionHandle end;
    086    private int length; // number of elements in list
    087
    088    private int[] bytePositions; // byte code offsets corresponding to instructions
    089
    090    private List<InstructionListObserver> observers;
    091
    092    /**
    093     * Create (empty) instruction list.
    094     */
    095    public InstructionList() {
    096    }
    097
    098    /**
    099     * Create instruction list containing one instruction.
    100     *
    101     * @param i initial instruction.
    102     */
    103    public InstructionList(final BranchInstruction i) {
    104        append(i);
    105    }
    106
    107    /**
    108     * Initialize instruction list from byte array.
    109     *
    110     * @param code byte array containing the instructions.
    111     */
    112    public InstructionList(final byte[] code) {
    113        int count = 0; // Contains actual length
    114        final int[] pos;
    115        final InstructionHandle[] ihs;
    116        try (ByteSequence bytes = new ByteSequence(code)) {
    117            ihs = new InstructionHandle[code.length];
    118            pos = new int[code.length]; // Can't be more than that
    119            /*
    120             * Pass 1: Create an object for each byte code and append them to the list.
    121             */
    122            while (bytes.available() > 0) {
    123                // Remember byte offset and associate it with the instruction
    124                final int off = bytes.getIndex();
    125                pos[count] = off;
    126                /*
    127                 * Reads one instruction from the byte stream, the byte position is set accordingly.
    128                 */
    129                final Instruction i = Instruction.readInstruction(bytes);
    130                final InstructionHandle ih;
    131                if (i instanceof BranchInstruction) {
    132                    ih = append((BranchInstruction) i);
    133                } else {
    134                    ih = append(i);
    135                }
    136                ih.setPosition(off);
    137                ihs[count] = ih;
    138                count++;
    139            }
    140        } catch (final IOException e) {
    141            throw new ClassGenException(e.toString(), e);
    142        }
    143        bytePositions = Arrays.copyOf(pos, count); // Trim to proper size
    144        /*
    145         * Pass 2: Look for BranchInstruction and update their targets, that is, convert offsets to instruction handles.
    146         */
    147        for (int i = 0; i < count; i++) {
    148            if (ihs[i] instanceof BranchHandle) {
    149                final BranchInstruction bi = (BranchInstruction) ihs[i].getInstruction();
    150                int target = bi.getPosition() + bi.getIndex(); /*
    151                                                                * Byte code position: relative -> absolute.
    152                                                                */
    153                // Search for target position
    154                InstructionHandle ih = findHandle(ihs, pos, count, target);
    155                if (ih == null) {
    156                    throw new ClassGenException("Couldn't find target for branch: " + bi);
    157                }
    158                bi.setTarget(ih); // Update target
    159                // If it is a Select instruction, update all branch targets
    160                if (bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
    161                    final Select s = (Select) bi;
    162                    final int[] indices = s.getIndices();
    163                    for (int j = 0; j < indices.length; j++) {
    164                        target = bi.getPosition() + indices[j];
    165                        ih = findHandle(ihs, pos, count, target);
    166                        if (ih == null) {
    167                            throw new ClassGenException("Couldn't find target for switch: " + bi);
    168                        }
    169                        s.setTarget(j, ih); // Update target
    170                    }
    171                }
    172            }
    173        }
    174    }
    175
    176    /**
    177     * Initialize list with (nonnull) compound instruction. Consumes argument list, that is, it becomes empty.
    178     *
    179     * @param c compound instruction (list).
    180     */
    181    public InstructionList(final CompoundInstruction c) {
    182        append(c.getInstructionList());
    183    }
    184
    185    /**
    186     * Create instruction list containing one instruction.
    187     *
    188     * @param i initial instruction.
    189     */
    190    public InstructionList(final Instruction i) {
    191        append(i);
    192    }
    193
    194    /**
    195     * Add observer for this object.
    196     *
    197     * @param o the observer to add.
    198     */
    199    public void addObserver(final InstructionListObserver o) {
    200        if (observers == null) {
    201            observers = new ArrayList<>();
    202        }
    203        observers.add(o);
    204    }
    205
    206    /**
    207     * Append a branch instruction to the end of this list.
    208     *
    209     * @param i branch instruction to append.
    210     * @return branch instruction handle of the appended instruction.
    211     */
    212    public BranchHandle append(final BranchInstruction i) {
    213        final BranchHandle ih = BranchHandle.getBranchHandle(i);
    214        append(ih);
    215        return ih;
    216    }
    217
    218    /**
    219     * Append a compound instruction.
    220     *
    221     * @param c The composite instruction (containing an InstructionList).
    222     * @return instruction handle of the first appended instruction.
    223     */
    224    public InstructionHandle append(final CompoundInstruction c) {
    225        return append(c.getInstructionList());
    226    }
    227
    228    /**
    229     * Append an instruction to the end of this list.
    230     *
    231     * @param i instruction to append.
    232     * @return instruction handle of the appended instruction.
    233     */
    234    public InstructionHandle append(final Instruction i) {
    235        final InstructionHandle ih = InstructionHandle.getInstructionHandle(i);
    236        append(ih);
    237        return ih;
    238    }
    239
    240    /**
    241     * Append a compound instruction, after instruction i.
    242     *
    243     * @param i Instruction in list.
    244     * @param c The composite instruction (containing an InstructionList).
    245     * @return instruction handle of the first appended instruction.
    246     */
    247    public InstructionHandle append(final Instruction i, final CompoundInstruction c) {
    248        return append(i, c.getInstructionList());
    249    }
    250
    251    /**
    252     * Append a single instruction j after another instruction i, which must be in this list of course!
    253     *
    254     * @param i Instruction in list.
    255     * @param j Instruction to append after i in list.
    256     * @return instruction handle of the first appended instruction.
    257     */
    258    public InstructionHandle append(final Instruction i, final Instruction j) {
    259        return append(i, new InstructionList(j));
    260    }
    261
    262    /**
    263     * Append another list after instruction i contained in this list. Consumes argument list, that is, it becomes empty.
    264     *
    265     * @param i where to append the instruction list.
    266     * @param il Instruction list to append to this one.
    267     * @return instruction handle pointing to the <strong>first</strong> appended instruction.
    268     */
    269    public InstructionHandle append(final Instruction i, final InstructionList il) {
    270        final InstructionHandle ih;
    271        if ((ih = findInstruction2(i)) == null) {
    272            throw new ClassGenException("Instruction " + i + " is not contained in this list.");
    273        }
    274        return append(ih, il);
    275    }
    276
    277    /**
    278     * Append an instruction to the end of this list.
    279     *
    280     * @param ih instruction to append.
    281     */
    282    private void append(final InstructionHandle ih) {
    283        if (isEmpty()) {
    284            start = end = ih;
    285            ih.setNext(ih.setPrev(null));
    286        } else {
    287            end.setNext(ih);
    288            ih.setPrev(end);
    289            ih.setNext(null);
    290            end = ih;
    291        }
    292        length++; // Update length
    293    }
    294
    295    /**
    296     * Append an instruction after instruction (handle) ih contained in this list.
    297     *
    298     * @param ih where to append the instruction list.
    299     * @param i Instruction to append.
    300     * @return instruction handle pointing to the <strong>first</strong> appended instruction.
    301     */
    302    public BranchHandle append(final InstructionHandle ih, final BranchInstruction i) {
    303        final BranchHandle bh = BranchHandle.getBranchHandle(i);
    304        final InstructionList il = new InstructionList();
    305        il.append(bh);
    306        append(ih, il);
    307        return bh;
    308    }
    309
    310    /**
    311     * Append a compound instruction.
    312     *
    313     * @param ih where to append the instruction list.
    314     * @param c The composite instruction (containing an InstructionList).
    315     * @return instruction handle of the first appended instruction.
    316     */
    317    public InstructionHandle append(final InstructionHandle ih, final CompoundInstruction c) {
    318        return append(ih, c.getInstructionList());
    319    }
    320
    321    /**
    322     * Append an instruction after instruction (handle) ih contained in this list.
    323     *
    324     * @param ih where to append the instruction list.
    325     * @param i Instruction to append.
    326     * @return instruction handle pointing to the <strong>first</strong> appended instruction.
    327     */
    328    public InstructionHandle append(final InstructionHandle ih, final Instruction i) {
    329        return append(ih, new InstructionList(i));
    330    }
    331
    332    /**
    333     * Append another list after instruction (handle) ih contained in this list. Consumes argument list, that is, it becomes
    334     * empty.
    335     *
    336     * @param ih where to append the instruction list.
    337     * @param il Instruction list to append to this one.
    338     * @return instruction handle pointing to the <strong>first</strong> appended instruction.
    339     */
    340    public InstructionHandle append(final InstructionHandle ih, final InstructionList il) {
    341        if (il == null) {
    342            throw new ClassGenException("Appending null InstructionList");
    343        }
    344        if (il.isEmpty()) {
    345            return ih;
    346        }
    347        final InstructionHandle next = ih.getNext();
    348        final InstructionHandle ret = il.start;
    349        ih.setNext(il.start);
    350        il.start.setPrev(ih);
    351        il.end.setNext(next);
    352        if (next != null) {
    353            next.setPrev(il.end);
    354        } else {
    355            end = il.end; // Update end ...
    356        }
    357        length += il.length; // Update length
    358        il.clear();
    359        return ret;
    360    }
    361
    362    /**
    363     * Append another list to this one. Consumes argument list, that is, it becomes empty.
    364     *
    365     * @param il list to append to end of this list.
    366     * @return instruction handle of the <strong>first</strong> appended instruction.
    367     */
    368    public InstructionHandle append(final InstructionList il) {
    369        if (il == null) {
    370            throw new ClassGenException("Appending null InstructionList");
    371        }
    372        if (il.isEmpty()) {
    373            return null;
    374        }
    375        if (isEmpty()) {
    376            start = il.start;
    377            end = il.end;
    378            length = il.length;
    379            il.clear();
    380            return start;
    381        }
    382        return append(end, il); // was end.instruction
    383    }
    384
    385    private void clear() {
    386        start = end = null;
    387        length = 0;
    388    }
    389
    390    /**
    391     * Checks if the list contains the given instruction.
    392     *
    393     * @param i the instruction to check.
    394     * @return true if the list contains the instruction.
    395     */
    396    public boolean contains(final Instruction i) {
    397        return findInstruction1(i) != null;
    398    }
    399
    400    /**
    401     * Checks if the list contains the given instruction handle.
    402     *
    403     * @param i the instruction handle to check.
    404     * @return true if the list contains the instruction handle.
    405     */
    406    public boolean contains(final InstructionHandle i) {
    407        if (i == null) {
    408            return false;
    409        }
    410        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    411            if (ih == i) {
    412                return true;
    413            }
    414        }
    415        return false;
    416    }
    417
    418    /**
    419     * Creates a complete deep copy of this list.
    420     *
    421     * @return complete, that is, deep copy of this list.
    422     */
    423    public InstructionList copy() {
    424        final Map<InstructionHandle, InstructionHandle> map = new HashMap<>();
    425        final InstructionList il = new InstructionList();
    426        /*
    427         * Pass 1: Make copies of all instructions, append them to the new list and associate old instruction references with
    428         * the new ones, that is, a 1:1 mapping.
    429         */
    430        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    431            final Instruction i = ih.getInstruction();
    432            final Instruction c = i.copy(); // Use clone for shallow copy
    433            if (c instanceof BranchInstruction) {
    434                map.put(ih, il.append((BranchInstruction) c));
    435            } else {
    436                map.put(ih, il.append(c));
    437            }
    438        }
    439        /*
    440         * Pass 2: Update branch targets.
    441         */
    442        InstructionHandle ih = start;
    443        InstructionHandle ch = il.start;
    444        while (ih != null) {
    445            final Instruction i = ih.getInstruction();
    446            final Instruction c = ch.getInstruction();
    447            if (i instanceof BranchInstruction) {
    448                final BranchInstruction bi = (BranchInstruction) i;
    449                final BranchInstruction bc = (BranchInstruction) c;
    450                final InstructionHandle itarget = bi.getTarget(); // old target
    451                // New target is in hash map
    452                bc.setTarget(map.get(itarget));
    453                if (bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
    454                    final InstructionHandle[] itargets = ((Select) bi).getTargets();
    455                    final InstructionHandle[] ctargets = ((Select) bc).getTargets();
    456                    for (int j = 0; j < itargets.length; j++) { // Update all targets
    457                        ctargets[j] = map.get(itargets[j]);
    458                    }
    459                }
    460            }
    461            ih = ih.getNext();
    462            ch = ch.getNext();
    463        }
    464        return il;
    465    }
    466
    467    /**
    468     * Remove instruction from this list. The corresponding Instruction handles must not be reused!
    469     *
    470     * @param i instruction to remove.
    471     * @throws TargetLostException if target is lost.
    472     */
    473    public void delete(final Instruction i) throws TargetLostException {
    474        final InstructionHandle ih;
    475        if ((ih = findInstruction1(i)) == null) {
    476            throw new ClassGenException("Instruction " + i + " is not contained in this list.");
    477        }
    478        delete(ih);
    479    }
    480
    481    /**
    482     * Remove instructions from instruction 'from' to instruction 'to' contained in this list. The user must ensure that
    483     * 'from' is an instruction before 'to', or risk havoc. The corresponding Instruction handles must not be reused!
    484     *
    485     * @param from where to start deleting (inclusive).
    486     * @param to where to end deleting (inclusive).
    487     * @throws TargetLostException if target is lost.
    488     */
    489    public void delete(final Instruction from, final Instruction to) throws TargetLostException {
    490        final InstructionHandle fromIh;
    491        final InstructionHandle toIh;
    492        if ((fromIh = findInstruction1(from)) == null) {
    493            throw new ClassGenException("Instruction " + from + " is not contained in this list.");
    494        }
    495        if ((toIh = findInstruction2(to)) == null) {
    496            throw new ClassGenException("Instruction " + to + " is not contained in this list.");
    497        }
    498        delete(fromIh, toIh);
    499    }
    500
    501    /**
    502     * Remove instruction from this list. The corresponding Instruction handles must not be reused!
    503     *
    504     * @param ih instruction (handle) to remove.
    505     * @throws TargetLostException if target is lost.
    506     */
    507    public void delete(final InstructionHandle ih) throws TargetLostException {
    508        remove(ih.getPrev(), ih.getNext());
    509    }
    510
    511    /**
    512     * Remove instructions from instruction 'from' to instruction 'to' contained in this list. The user must ensure that
    513     * 'from' is an instruction before 'to', or risk havoc. The corresponding Instruction handles must not be reused!
    514     *
    515     * @param from where to start deleting (inclusive).
    516     * @param to where to end deleting (inclusive).
    517     * @throws TargetLostException if target is lost.
    518     */
    519    public void delete(final InstructionHandle from, final InstructionHandle to) throws TargetLostException {
    520        remove(from.getPrev(), to.getNext());
    521    }
    522
    523    /**
    524     * Delete contents of list. Provides better memory utilization, because the system then may reuse the instruction
    525     * handles. This method is typically called right after {@link MethodGen#getMethod()}.
    526     */
    527    public void dispose() {
    528        // Traverse in reverse order, because ih.next is overwritten
    529        for (InstructionHandle ih = end; ih != null; ih = ih.getPrev()) {
    530            // Causes BranchInstructions to release target and targeters, because it calls dispose() on the contained instruction.
    531            ih.dispose();
    532        }
    533        clear();
    534    }
    535
    536    /**
    537     * Gets instruction handle for instruction at byte code position pos. This only works properly, if the list is freshly
    538     * initialized from a byte array or setPositions() has been called before this method.
    539     *
    540     * @param pos byte code position to search for.
    541     * @return target position's instruction handle if available.
    542     */
    543    public InstructionHandle findHandle(final int pos) {
    544        final int[] positions = bytePositions;
    545        InstructionHandle ih = start;
    546        for (int i = 0; i < length; i++) {
    547            if (positions[i] == pos) {
    548                return ih;
    549            }
    550            ih = ih.getNext();
    551        }
    552        return null;
    553    }
    554
    555    /**
    556     * Search for given Instruction reference, start at beginning of list.
    557     *
    558     * @param i instruction to search for.
    559     * @return instruction found on success, null otherwise.
    560     */
    561    private InstructionHandle findInstruction1(final Instruction i) {
    562        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    563            if (ih.getInstruction() == i) {
    564                return ih;
    565            }
    566        }
    567        return null;
    568    }
    569
    570    /**
    571     * Search for given Instruction reference, start at end of list
    572     *
    573     * @param i instruction to search for.
    574     * @return instruction found on success, null otherwise.
    575     */
    576    private InstructionHandle findInstruction2(final Instruction i) {
    577        for (InstructionHandle ih = end; ih != null; ih = ih.getPrev()) {
    578            if (ih.getInstruction() == i) {
    579                return ih;
    580            }
    581        }
    582        return null;
    583    }
    584
    585    /**
    586     * When everything is finished, use this method to convert the instruction list into an array of bytes.
    587     *
    588     * @return the byte code ready to be dumped.
    589     */
    590    public byte[] getByteCode() {
    591        // Update position indices of instructions
    592        setPositions();
    593        final ByteArrayOutputStream b = new ByteArrayOutputStream();
    594        final DataOutputStream out = new DataOutputStream(b);
    595        try {
    596            for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    597                final Instruction i = ih.getInstruction();
    598                i.dump(out); // Traverse list
    599            }
    600            out.flush();
    601        } catch (final IOException e) {
    602            System.err.println(e);
    603            return ArrayUtils.EMPTY_BYTE_ARRAY;
    604        }
    605        return b.toByteArray();
    606    }
    607
    608    /**
    609     * Gets the end of list.
    610     *
    611     * @return end of list.
    612     */
    613    public InstructionHandle getEnd() {
    614        return end;
    615    }
    616
    617    /**
    618     * Gets array containing all instructions.
    619     *
    620     * @return array containing all instructions (handles).
    621     */
    622    public InstructionHandle[] getInstructionHandles() {
    623        final InstructionHandle[] ihs = new InstructionHandle[length];
    624        InstructionHandle ih = start;
    625        for (int i = 0; i < length; i++) {
    626            ihs[i] = ih;
    627            ih = ih.getNext();
    628        }
    629        return ihs;
    630    }
    631
    632    /**
    633     * Gets positions (offsets) of all instructions in the list. This relies on that the list has been freshly created from
    634     * an byte code array, or that setPositions() has been called. Otherwise this may be inaccurate.
    635     *
    636     * @return array containing all instruction's offset in byte code.
    637     */
    638    public int[] getInstructionPositions() {
    639        return bytePositions;
    640    }
    641
    642    /**
    643     * Gets an array of instructions without target information for branch instructions.
    644     *
    645     * @return an array of instructions without target information for branch instructions.
    646     */
    647    public Instruction[] getInstructions() {
    648        final List<Instruction> instructions = new ArrayList<>();
    649        try (ByteSequence bytes = new ByteSequence(getByteCode())) {
    650            while (bytes.available() > 0) {
    651                instructions.add(Instruction.readInstruction(bytes));
    652            }
    653        } catch (final IOException e) {
    654            throw new ClassGenException(e.toString(), e);
    655        }
    656        return instructions.toArray(Instruction.EMPTY_ARRAY);
    657    }
    658
    659    /**
    660     * Gets the length of list.
    661     *
    662     * @return length of list (Number of instructions, not bytes).
    663     */
    664    public int getLength() {
    665        return length;
    666    }
    667
    668    /**
    669     * Gets the start of list.
    670     *
    671     * @return start of list.
    672     */
    673    public InstructionHandle getStart() {
    674        return start;
    675    }
    676
    677    /**
    678     * Insert a branch instruction at start of this list.
    679     *
    680     * @param i branch instruction to insert.
    681     * @return branch instruction handle of the appended instruction.
    682     */
    683    public BranchHandle insert(final BranchInstruction i) {
    684        final BranchHandle ih = BranchHandle.getBranchHandle(i);
    685        insert(ih);
    686        return ih;
    687    }
    688
    689    /**
    690     * Insert a compound instruction.
    691     *
    692     * @param c The composite instruction (containing an InstructionList).
    693     * @return instruction handle of the first inserted instruction.
    694     */
    695    public InstructionHandle insert(final CompoundInstruction c) {
    696        return insert(c.getInstructionList());
    697    }
    698
    699    /**
    700     * Insert an instruction at start of this list.
    701     *
    702     * @param i instruction to insert.
    703     * @return instruction handle of the inserted instruction.
    704     */
    705    public InstructionHandle insert(final Instruction i) {
    706        final InstructionHandle ih = InstructionHandle.getInstructionHandle(i);
    707        insert(ih);
    708        return ih;
    709    }
    710
    711    /**
    712     * Insert a compound instruction before instruction i.
    713     *
    714     * @param i Instruction in list.
    715     * @param c The composite instruction (containing an InstructionList).
    716     * @return instruction handle of the first inserted instruction.
    717     */
    718    public InstructionHandle insert(final Instruction i, final CompoundInstruction c) {
    719        return insert(i, c.getInstructionList());
    720    }
    721
    722    /**
    723     * Insert a single instruction j before another instruction i, which must be in this list of course!
    724     *
    725     * @param i Instruction in list.
    726     * @param j Instruction to insert before i in list.
    727     * @return instruction handle of the first inserted instruction.
    728     */
    729    public InstructionHandle insert(final Instruction i, final Instruction j) {
    730        return insert(i, new InstructionList(j));
    731    }
    732
    733    /**
    734     * Insert another list before Instruction i contained in this list. Consumes argument list, that is, it becomes empty.
    735     *
    736     * @param i where to append the instruction list.
    737     * @param il Instruction list to insert.
    738     * @return instruction handle pointing to the first inserted instruction, that is, il.getStart().
    739     */
    740    public InstructionHandle insert(final Instruction i, final InstructionList il) {
    741        final InstructionHandle ih;
    742        if ((ih = findInstruction1(i)) == null) {
    743            throw new ClassGenException("Instruction " + i + " is not contained in this list.");
    744        }
    745        return insert(ih, il);
    746    }
    747
    748    /**
    749     * Insert an instruction at start of this list.
    750     *
    751     * @param ih instruction to insert.
    752     */
    753    private void insert(final InstructionHandle ih) {
    754        if (isEmpty()) {
    755            start = end = ih;
    756            ih.setNext(ih.setPrev(null));
    757        } else {
    758            start.setPrev(ih);
    759            ih.setNext(start);
    760            ih.setPrev(null);
    761            start = ih;
    762        }
    763        length++;
    764    }
    765
    766    /**
    767     * Insert an instruction before instruction (handle) ih contained in this list.
    768     *
    769     * @param ih where to insert to the instruction list.
    770     * @param i Instruction to insert.
    771     * @return instruction handle of the first inserted instruction.
    772     */
    773    public BranchHandle insert(final InstructionHandle ih, final BranchInstruction i) {
    774        final BranchHandle bh = BranchHandle.getBranchHandle(i);
    775        final InstructionList il = new InstructionList();
    776        il.append(bh);
    777        insert(ih, il);
    778        return bh;
    779    }
    780
    781    /**
    782     * Insert a compound instruction.
    783     *
    784     * @param ih where to insert the instruction list.
    785     * @param c The composite instruction (containing an InstructionList).
    786     * @return instruction handle of the first inserted instruction.
    787     */
    788    public InstructionHandle insert(final InstructionHandle ih, final CompoundInstruction c) {
    789        return insert(ih, c.getInstructionList());
    790    }
    791
    792    /**
    793     * Insert an instruction before instruction (handle) ih contained in this list.
    794     *
    795     * @param ih where to insert to the instruction list.
    796     * @param i Instruction to insert.
    797     * @return instruction handle of the first inserted instruction.
    798     */
    799    public InstructionHandle insert(final InstructionHandle ih, final Instruction i) {
    800        return insert(ih, new InstructionList(i));
    801    }
    802
    803    /**
    804     * Insert another list before Instruction handle ih contained in this list. Consumes argument list, that is, it becomes
    805     * empty.
    806     *
    807     * @param ih where to append the instruction list.
    808     * @param il Instruction list to insert.
    809     * @return instruction handle of the first inserted instruction.
    810     */
    811    public InstructionHandle insert(final InstructionHandle ih, final InstructionList il) {
    812        if (il == null) {
    813            throw new ClassGenException("Inserting null InstructionList");
    814        }
    815        if (il.isEmpty()) {
    816            return ih;
    817        }
    818        final InstructionHandle prev = ih.getPrev();
    819        final InstructionHandle ret = il.start;
    820        ih.setPrev(il.end);
    821        il.end.setNext(ih);
    822        il.start.setPrev(prev);
    823        if (prev != null) {
    824            prev.setNext(il.start);
    825        } else {
    826            start = il.start; // Update start ...
    827        }
    828        length += il.length; // Update length
    829        il.clear();
    830        return ret;
    831    }
    832
    833    /**
    834     * Insert another list.
    835     *
    836     * @param il list to insert before start of this list.
    837     * @return instruction handle of the first inserted instruction.
    838     */
    839    public InstructionHandle insert(final InstructionList il) {
    840        if (isEmpty()) {
    841            append(il); // Code is identical for this case
    842            return start;
    843        }
    844        return insert(start, il);
    845    }
    846
    847    /**
    848     * Tests for empty list.
    849     */
    850    public boolean isEmpty() {
    851        return start == null;
    852    } // && end == null
    853
    854    /**
    855     * @return iterator that lists all instructions (handles).
    856     */
    857    @Override
    858    public Iterator<InstructionHandle> iterator() {
    859        return new Iterator<InstructionHandle>() {
    860
    861            private InstructionHandle ih = start;
    862
    863            @Override
    864            public boolean hasNext() {
    865                return ih != null;
    866            }
    867
    868            @Override
    869            public InstructionHandle next() throws NoSuchElementException {
    870                if (ih == null) {
    871                    throw new NoSuchElementException();
    872                }
    873                final InstructionHandle i = ih;
    874                ih = ih.getNext();
    875                return i;
    876            }
    877
    878            @Override
    879            public void remove() {
    880                throw new UnsupportedOperationException();
    881            }
    882        };
    883    }
    884
    885    /**
    886     * Move a single instruction (handle) to a new location.
    887     *
    888     * @param ih moved instruction.
    889     * @param target new location of moved instruction.
    890     */
    891    public void move(final InstructionHandle ih, final InstructionHandle target) {
    892        move(ih, ih, target);
    893    }
    894
    895    /**
    896     * Take all instructions (handles) from "start" to "end" and append them after the new location "target". Of course,
    897     * "end" must be after "start" and target must not be located withing this range. If you want to move something to the
    898     * start of the list use null as value for target.
    899     * <p>
    900     * Any instruction targeters pointing to handles within the block, keep their targets.
    901     * </p>
    902     *
    903     * @param start of moved block.
    904     * @param end of moved block.
    905     * @param target of moved block.
    906     */
    907    public void move(final InstructionHandle start, final InstructionHandle end, final InstructionHandle target) {
    908        // Step 1: Check constraints
    909        if (start == null || end == null) {
    910            throw new ClassGenException("Invalid null handle: From " + start + " to " + end);
    911        }
    912        if (target == start || target == end) {
    913            throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target);
    914        }
    915        for (InstructionHandle ih = start; ih != end.getNext(); ih = ih.getNext()) {
    916            if (ih == null) {
    917                throw new ClassGenException("Invalid range: From " + start + " to " + end);
    918            }
    919            if (ih == target) {
    920                throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target);
    921            }
    922        }
    923        // Step 2: Temporarily remove the given instructions from the list
    924        final InstructionHandle prev = start.getPrev();
    925        InstructionHandle next = end.getNext();
    926        if (prev != null) {
    927            prev.setNext(next);
    928        } else {
    929            this.start = next;
    930        }
    931        if (next != null) {
    932            next.setPrev(prev);
    933        } else {
    934            this.end = prev;
    935        }
    936        start.setPrev(end.setNext(null));
    937        // Step 3: append after target
    938        if (target == null) { // append to start of list
    939            if (this.start != null) {
    940                this.start.setPrev(end);
    941            }
    942            end.setNext(this.start);
    943            this.start = start;
    944        } else {
    945            next = target.getNext();
    946            target.setNext(start);
    947            start.setPrev(target);
    948            end.setNext(next);
    949            if (next != null) {
    950                next.setPrev(end);
    951            } else {
    952                this.end = end;
    953            }
    954        }
    955    }
    956
    957    /**
    958     * Redirect all references from oldTarget to newTarget, that is, update targets of branch instructions.
    959     *
    960     * @param oldTarget the old target instruction handle.
    961     * @param newTarget the new target instruction handle.
    962     */
    963    public void redirectBranches(final InstructionHandle oldTarget, final InstructionHandle newTarget) {
    964        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    965            final Instruction i = ih.getInstruction();
    966            if (i instanceof BranchInstruction) {
    967                final BranchInstruction b = (BranchInstruction) i;
    968                final InstructionHandle target = b.getTarget();
    969                if (target == oldTarget) {
    970                    b.setTarget(newTarget);
    971                }
    972                if (b instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
    973                    final InstructionHandle[] targets = ((Select) b).getTargets();
    974                    for (int j = 0; j < targets.length; j++) {
    975                        if (targets[j] == oldTarget) {
    976                            ((Select) b).setTarget(j, newTarget);
    977                        }
    978                    }
    979                }
    980            }
    981        }
    982    }
    983
    984    /**
    985     * Redirect all references of exception handlers from oldTarget to newTarget.
    986     *
    987     * @param exceptions array of exception handlers.
    988     * @param oldTarget the old target instruction handle.
    989     * @param newTarget the new target instruction handle.
    990     * @see MethodGen
    991     */
    992    public void redirectExceptionHandlers(final CodeExceptionGen[] exceptions, final InstructionHandle oldTarget, final InstructionHandle newTarget) {
    993        Streams.of(exceptions).forEach(exception -> {
    994            if (exception.getStartPC() == oldTarget) {
    995                exception.setStartPC(newTarget);
    996            }
    997            if (exception.getEndPC() == oldTarget) {
    998                exception.setEndPC(newTarget);
    999            }
    1000            if (exception.getHandlerPC() == oldTarget) {
    1001                exception.setHandlerPC(newTarget);
    1002            }
    1003        });
    1004    }
    1005
    1006    /**
    1007     * Redirect all references of local variables from oldTarget to newTarget.
    1008     *
    1009     * @param lg array of local variables.
    1010     * @param oldTarget the old target instruction handle.
    1011     * @param newTarget the new target instruction handle.
    1012     * @see MethodGen
    1013     */
    1014    public void redirectLocalVariables(final LocalVariableGen[] lg, final InstructionHandle oldTarget, final InstructionHandle newTarget) {
    1015        Streams.of(lg).forEach(element -> {
    1016            if (element.getStart() == oldTarget) {
    1017                element.setStart(newTarget);
    1018            }
    1019            if (element.getEnd() == oldTarget) {
    1020                element.setEnd(newTarget);
    1021            }
    1022        });
    1023    }
    1024
    1025    /**
    1026     * Remove from instruction 'prev' to instruction 'next' both contained in this list. Throws TargetLostException when one
    1027     * of the removed instruction handles is still being targeted.
    1028     *
    1029     * @param prev where to start deleting (predecessor, exclusive).
    1030     * @param next where to end deleting (successor, exclusive).
    1031     */
    1032    private void remove(final InstructionHandle prev, InstructionHandle next) throws TargetLostException {
    1033        final InstructionHandle first;
    1034        final InstructionHandle last; // First and last deleted instruction
    1035        if (prev == null && next == null) {
    1036            first = start;
    1037            last = end;
    1038            start = end = null;
    1039        } else {
    1040            if (prev == null) { // At start of list
    1041                first = start;
    1042                start = next;
    1043            } else {
    1044                first = prev.getNext();
    1045                prev.setNext(next);
    1046            }
    1047            if (next == null) { // At end of list
    1048                last = end;
    1049                end = prev;
    1050            } else {
    1051                last = next.getPrev();
    1052                next.setPrev(prev);
    1053            }
    1054        }
    1055        first.setPrev(null); // Completely separated from rest of list
    1056        last.setNext(null);
    1057        final List<InstructionHandle> targetList = new ArrayList<>();
    1058        for (InstructionHandle ih = first; ih != null; ih = ih.getNext()) {
    1059            ih.getInstruction().dispose(); // for example BranchInstructions release their targets
    1060        }
    1061        final StringBuilder buf = new StringBuilder("{ ");
    1062        for (InstructionHandle ih = first; ih != null; ih = next) {
    1063            next = ih.getNext();
    1064            length--;
    1065            if (ih.hasTargeters()) { // Still got targeters?
    1066                targetList.add(ih);
    1067                buf.append(ih.toString(true)).append(" ");
    1068                ih.setNext(ih.setPrev(null));
    1069            } else {
    1070                ih.dispose();
    1071            }
    1072        }
    1073        buf.append("}");
    1074        if (!targetList.isEmpty()) {
    1075            throw new TargetLostException(targetList.toArray(InstructionHandle.EMPTY_ARRAY), buf.toString());
    1076        }
    1077    }
    1078
    1079    /**
    1080     * Remove observer for this object.
    1081     *
    1082     * @param o the observer to remove.
    1083     */
    1084    public void removeObserver(final InstructionListObserver o) {
    1085        if (observers != null) {
    1086            observers.remove(o);
    1087        }
    1088    }
    1089
    1090    /**
    1091     * Replace all references to the old constant pool with references to the new constant pool.
    1092     *
    1093     * @param oldCp the old constant pool.
    1094     * @param newCp the new constant pool.
    1095     */
    1096    public void replaceConstantPool(final ConstantPoolGen oldCp, final ConstantPoolGen newCp) {
    1097        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1098            final Instruction i = ih.getInstruction();
    1099            if (i instanceof CPInstruction) {
    1100                final CPInstruction ci = (CPInstruction) i;
    1101                final Constant c = oldCp.getConstant(ci.getIndex());
    1102                ci.setIndex(newCp.addConstant(c, oldCp));
    1103            }
    1104        }
    1105    }
    1106
    1107    /**
    1108     * Sets positions with no sanity checks.
    1109     */
    1110    public void setPositions() { // TODO could be package-protected? (some test code would need to be repackaged)
    1111        setPositions(false);
    1112    }
    1113
    1114    /**
    1115     * Give all instructions their position number (offset in byte stream), that is, make the list ready to be dumped.
    1116     *
    1117     * @param check Perform sanity checks, for example if all targeted instructions really belong to this list.
    1118     */
    1119    public void setPositions(final boolean check) { // called by code in other packages
    1120        int maxAdditionalBytes = 0;
    1121        int additionalBytes = 0;
    1122        int index = 0;
    1123        int count = 0;
    1124        final int[] pos = new int[length];
    1125        /*
    1126         * Pass 0: Sanity checks
    1127         */
    1128        if (check) {
    1129            for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1130                final Instruction i = ih.getInstruction();
    1131                if (i instanceof BranchInstruction) { // target instruction within list?
    1132                    Instruction inst = ((BranchInstruction) i).getTarget().getInstruction();
    1133                    if (!contains(inst)) {
    1134                        throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list");
    1135                    }
    1136                    if (i instanceof Select) {
    1137                        final InstructionHandle[] targets = ((Select) i).getTargets();
    1138                        for (final InstructionHandle target : targets) {
    1139                            inst = target.getInstruction();
    1140                            if (!contains(inst)) {
    1141                                throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list");
    1142                            }
    1143                        }
    1144                    }
    1145                    if (!(ih instanceof BranchHandle)) {
    1146                        throw new ClassGenException(
    1147                            "Branch instruction " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not contained in BranchHandle.");
    1148                    }
    1149                }
    1150            }
    1151        }
    1152        /*
    1153         * Pass 1: Set position numbers and sum up the maximum number of bytes an instruction may be shifted.
    1154         */
    1155        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1156            final Instruction i = ih.getInstruction();
    1157            ih.setPosition(index);
    1158            pos[count++] = index;
    1159            /*
    1160             * Gets an estimate about how many additional bytes may be added, because BranchInstructions may have variable length
    1161             * depending on the target offset (short vs. int) or alignment issues (TABLESWITCH and LOOKUPSWITCH).
    1162             */
    1163            switch (i.getOpcode()) {
    1164            case Const.JSR:
    1165            case Const.GOTO:
    1166                maxAdditionalBytes += 2;
    1167                break;
    1168            case Const.TABLESWITCH:
    1169            case Const.LOOKUPSWITCH:
    1170                maxAdditionalBytes += 3;
    1171                break;
    1172            default:
    1173                // TODO should this be an error?
    1174                break;
    1175            }
    1176            index += i.getLength();
    1177        }
    1178        /*
    1179         * Pass 2: Expand the variable-length (Branch) Instructions depending on the target offset (short or int) and ensure that
    1180         * branch targets are within this list.
    1181         */
    1182        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1183            additionalBytes += ih.updatePosition(additionalBytes, maxAdditionalBytes);
    1184        }
    1185        /*
    1186         * Pass 3: Update position numbers (which may have changed due to the preceding expansions), like pass 1.
    1187         */
    1188        index = count = 0;
    1189        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1190            final Instruction i = ih.getInstruction();
    1191            ih.setPosition(index);
    1192            pos[count++] = index;
    1193            index += i.getLength();
    1194        }
    1195        bytePositions = Arrays.copyOfRange(pos, 0, count); // Trim to proper size
    1196    }
    1197
    1198    /**
    1199     * Gets the length of list.
    1200     *
    1201     * @return length of list (Number of instructions, not bytes).
    1202     */
    1203    public int size() {
    1204        return length;
    1205    }
    1206
    1207    @Override
    1208    public String toString() {
    1209        return toString(true);
    1210    }
    1211
    1212    /**
    1213     * Gets string containing all instructions in this list.
    1214     *
    1215     * @param verbose toggle output format.
    1216     * @return String containing all instructions in this list.
    1217     */
    1218    public String toString(final boolean verbose) {
    1219        final StringBuilder buf = new StringBuilder();
    1220        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1221            buf.append(ih.toString(verbose)).append("\n");
    1222        }
    1223        return buf.toString();
    1224    }
    1225
    1226    /**
    1227     * Call notify() method on all observers. This method is not called automatically whenever the state has changed, but
    1228     * has to be called by the user after he has finished editing the object.
    1229     */
    1230    public void update() {
    1231        if (observers != null) {
    1232            for (final InstructionListObserver observer : observers) {
    1233                observer.notify(this);
    1234            }
    1235        }
    1236    }
    1237}
    1238