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