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