    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            // Causes BranchInstructions to release target and targeters, because it calls dispose() on the contained instruction.
    507            ih.dispose();
    508        }
    509        clear();
    510    }
    511
    512    /**
    513     * Gets instruction handle for instruction at byte code position pos. This only works properly, if the list is freshly
    514     * initialized from a byte array or setPositions() has been called before this method.
    515     *
    516     * @param pos byte code position to search for
    517     * @return target position's instruction handle if available
    518     */
    519    public InstructionHandle findHandle(final int pos) {
    520        final int[] positions = bytePositions;
    521        InstructionHandle ih = start;
    522        for (int i = 0; i < length; i++) {
    523            if (positions[i] == pos) {
    524                return ih;
    525            }
    526            ih = ih.getNext();
    527        }
    528        return null;
    529    }
    530
    531    /**
    532     * Search for given Instruction reference, start at beginning of list.
    533     *
    534     * @param i instruction to search for
    535     * @return instruction found on success, null otherwise
    536     */
    537    private InstructionHandle findInstruction1(final Instruction i) {
    538        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    539            if (ih.getInstruction() == i) {
    540                return ih;
    541            }
    542        }
    543        return null;
    544    }
    545
    546    /**
    547     * Search for given Instruction reference, start at end of list
    548     *
    549     * @param i instruction to search for
    550     * @return instruction found on success, null otherwise
    551     */
    552    private InstructionHandle findInstruction2(final Instruction i) {
    553        for (InstructionHandle ih = end; ih != null; ih = ih.getPrev()) {
    554            if (ih.getInstruction() == i) {
    555                return ih;
    556            }
    557        }
    558        return null;
    559    }
    560
    561    /**
    562     * When everything is finished, use this method to convert the instruction list into an array of bytes.
    563     *
    564     * @return the byte code ready to be dumped
    565     */
    566    public byte[] getByteCode() {
    567        // Update position indices of instructions
    568        setPositions();
    569        final ByteArrayOutputStream b = new ByteArrayOutputStream();
    570        final DataOutputStream out = new DataOutputStream(b);
    571        try {
    572            for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    573                final Instruction i = ih.getInstruction();
    574                i.dump(out); // Traverse list
    575            }
    576            out.flush();
    577        } catch (final IOException e) {
    578            System.err.println(e);
    579            return ArrayUtils.EMPTY_BYTE_ARRAY;
    580        }
    581        return b.toByteArray();
    582    }
    583
    584    /**
    585     * @return end of list
    586     */
    587    public InstructionHandle getEnd() {
    588        return end;
    589    }
    590
    591    /**
    592     * @return array containing all instructions (handles)
    593     */
    594    public InstructionHandle[] getInstructionHandles() {
    595        final InstructionHandle[] ihs = new InstructionHandle[length];
    596        InstructionHandle ih = start;
    597        for (int i = 0; i < length; i++) {
    598            ihs[i] = ih;
    599            ih = ih.getNext();
    600        }
    601        return ihs;
    602    }
    603
    604    /**
    605     * Gets positions (offsets) of all instructions in the list. This relies on that the list has been freshly created from
    606     * an byte code array, or that setPositions() has been called. Otherwise this may be inaccurate.
    607     *
    608     * @return array containing all instruction's offset in byte code
    609     */
    610    public int[] getInstructionPositions() {
    611        return bytePositions;
    612    }
    613
    614    /**
    615     * @return an array of instructions without target information for branch instructions.
    616     */
    617    public Instruction[] getInstructions() {
    618        final List<Instruction> instructions = new ArrayList<>();
    619        try (ByteSequence bytes = new ByteSequence(getByteCode())) {
    620            while (bytes.available() > 0) {
    621                instructions.add(Instruction.readInstruction(bytes));
    622            }
    623        } catch (final IOException e) {
    624            throw new ClassGenException(e.toString(), e);
    625        }
    626        return instructions.toArray(Instruction.EMPTY_ARRAY);
    627    }
    628
    629    /**
    630     * @return length of list (Number of instructions, not bytes)
    631     */
    632    public int getLength() {
    633        return length;
    634    }
    635
    636    /**
    637     * @return start of list
    638     */
    639    public InstructionHandle getStart() {
    640        return start;
    641    }
    642
    643    /**
    644     * Insert a branch instruction at start of this list.
    645     *
    646     * @param i branch instruction to insert
    647     * @return branch instruction handle of the appended instruction
    648     */
    649    public BranchHandle insert(final BranchInstruction i) {
    650        final BranchHandle ih = BranchHandle.getBranchHandle(i);
    651        insert(ih);
    652        return ih;
    653    }
    654
    655    /**
    656     * Insert a compound instruction.
    657     *
    658     * @param c The composite instruction (containing an InstructionList)
    659     * @return instruction handle of the first inserted instruction
    660     */
    661    public InstructionHandle insert(final CompoundInstruction c) {
    662        return insert(c.getInstructionList());
    663    }
    664
    665    /**
    666     * Insert an instruction at start of this list.
    667     *
    668     * @param i instruction to insert
    669     * @return instruction handle of the inserted instruction
    670     */
    671    public InstructionHandle insert(final Instruction i) {
    672        final InstructionHandle ih = InstructionHandle.getInstructionHandle(i);
    673        insert(ih);
    674        return ih;
    675    }
    676
    677    /**
    678     * Insert a compound instruction before instruction i.
    679     *
    680     * @param i Instruction in list
    681     * @param c The composite instruction (containing an InstructionList)
    682     * @return instruction handle of the first inserted instruction
    683     */
    684    public InstructionHandle insert(final Instruction i, final CompoundInstruction c) {
    685        return insert(i, c.getInstructionList());
    686    }
    687
    688    /**
    689     * Insert a single instruction j before another instruction i, which must be in this list of course!
    690     *
    691     * @param i Instruction in list
    692     * @param j Instruction to insert before i in list
    693     * @return instruction handle of the first inserted instruction
    694     */
    695    public InstructionHandle insert(final Instruction i, final Instruction j) {
    696        return insert(i, new InstructionList(j));
    697    }
    698
    699    /**
    700     * Insert another list before Instruction i contained in this list. Consumes argument list, i.e., it becomes empty.
    701     *
    702     * @param i where to append the instruction list
    703     * @param il Instruction list to insert
    704     * @return instruction handle pointing to the first inserted instruction, i.e., il.getStart()
    705     */
    706    public InstructionHandle insert(final Instruction i, final InstructionList il) {
    707        InstructionHandle ih;
    708        if ((ih = findInstruction1(i)) == null) {
    709            throw new ClassGenException("Instruction " + i + " is not contained in this list.");
    710        }
    711        return insert(ih, il);
    712    }
    713
    714    /**
    715     * Insert an instruction at start of this list.
    716     *
    717     * @param ih instruction to insert
    718     */
    719    private void insert(final InstructionHandle ih) {
    720        if (isEmpty()) {
    721            start = end = ih;
    722            ih.setNext(ih.setPrev(null));
    723        } else {
    724            start.setPrev(ih);
    725            ih.setNext(start);
    726            ih.setPrev(null);
    727            start = ih;
    728        }
    729        length++;
    730    }
    731
    732    /**
    733     * Insert an instruction before instruction (handle) ih contained in this list.
    734     *
    735     * @param ih where to insert to the instruction list
    736     * @param i Instruction to insert
    737     * @return instruction handle of the first inserted instruction
    738     */
    739    public BranchHandle insert(final InstructionHandle ih, final BranchInstruction i) {
    740        final BranchHandle bh = BranchHandle.getBranchHandle(i);
    741        final InstructionList il = new InstructionList();
    742        il.append(bh);
    743        insert(ih, il);
    744        return bh;
    745    }
    746
    747    /**
    748     * Insert a compound instruction.
    749     *
    750     * @param ih where to insert the instruction list
    751     * @param c The composite instruction (containing an InstructionList)
    752     * @return instruction handle of the first inserted instruction
    753     */
    754    public InstructionHandle insert(final InstructionHandle ih, final CompoundInstruction c) {
    755        return insert(ih, c.getInstructionList());
    756    }
    757
    758    /**
    759     * Insert an instruction before instruction (handle) ih contained in this list.
    760     *
    761     * @param ih where to insert to the instruction list
    762     * @param i Instruction to insert
    763     * @return instruction handle of the first inserted instruction
    764     */
    765    public InstructionHandle insert(final InstructionHandle ih, final Instruction i) {
    766        return insert(ih, new InstructionList(i));
    767    }
    768
    769    /**
    770     * Insert another list before Instruction handle ih contained in this list. Consumes argument list, i.e., it becomes
    771     * empty.
    772     *
    773     * @param ih where to append the instruction list
    774     * @param il Instruction list to insert
    775     * @return instruction handle of the first inserted instruction
    776     */
    777    public InstructionHandle insert(final InstructionHandle ih, final InstructionList il) {
    778        if (il == null) {
    779            throw new ClassGenException("Inserting null InstructionList");
    780        }
    781        if (il.isEmpty()) {
    782            return ih;
    783        }
    784        final InstructionHandle prev = ih.getPrev();
    785        final InstructionHandle ret = il.start;
    786        ih.setPrev(il.end);
    787        il.end.setNext(ih);
    788        il.start.setPrev(prev);
    789        if (prev != null) {
    790            prev.setNext(il.start);
    791        } else {
    792            start = il.start; // Update start ...
    793        }
    794        length += il.length; // Update length
    795        il.clear();
    796        return ret;
    797    }
    798
    799    /**
    800     * Insert another list.
    801     *
    802     * @param il list to insert before start of this list
    803     * @return instruction handle of the first inserted instruction
    804     */
    805    public InstructionHandle insert(final InstructionList il) {
    806        if (isEmpty()) {
    807            append(il); // Code is identical for this case
    808            return start;
    809        }
    810        return insert(start, il);
    811    }
    812
    813    /**
    814     * Test for empty list.
    815     */
    816    public boolean isEmpty() {
    817        return start == null;
    818    } // && end == null
    819
    820    /**
    821     * @return iterator that lists all instructions (handles)
    822     */
    823    @Override
    824    public Iterator<InstructionHandle> iterator() {
    825        return new Iterator<InstructionHandle>() {
    826
    827            private InstructionHandle ih = start;
    828
    829            @Override
    830            public boolean hasNext() {
    831                return ih != null;
    832            }
    833
    834            @Override
    835            public InstructionHandle next() throws NoSuchElementException {
    836                if (ih == null) {
    837                    throw new NoSuchElementException();
    838                }
    839                final InstructionHandle i = ih;
    840                ih = ih.getNext();
    841                return i;
    842            }
    843
    844            @Override
    845            public void remove() {
    846                throw new UnsupportedOperationException();
    847            }
    848        };
    849    }
    850
    851    /**
    852     * Move a single instruction (handle) to a new location.
    853     *
    854     * @param ih moved instruction
    855     * @param target new location of moved instruction
    856     */
    857    public void move(final InstructionHandle ih, final InstructionHandle target) {
    858        move(ih, ih, target);
    859    }
    860
    861    /**
    862     * Take all instructions (handles) from "start" to "end" and append them after the new location "target". Of course,
    863     * "end" must be after "start" and target must not be located withing this range. If you want to move something to the
    864     * start of the list use null as value for target.
    865     * <p>
    866     * Any instruction targeters pointing to handles within the block, keep their targets.
    867     * </p>
    868     *
    869     * @param start of moved block
    870     * @param end of moved block
    871     * @param target of moved block
    872     */
    873    public void move(final InstructionHandle start, final InstructionHandle end, final InstructionHandle target) {
    874        // Step 1: Check constraints
    875        if (start == null || end == null) {
    876            throw new ClassGenException("Invalid null handle: From " + start + " to " + end);
    877        }
    878        if (target == start || target == end) {
    879            throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target);
    880        }
    881        for (InstructionHandle ih = start; ih != end.getNext(); ih = ih.getNext()) {
    882            if (ih == null) {
    883                throw new ClassGenException("Invalid range: From " + start + " to " + end);
    884            }
    885            if (ih == target) {
    886                throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target);
    887            }
    888        }
    889        // Step 2: Temporarily remove the given instructions from the list
    890        final InstructionHandle prev = start.getPrev();
    891        InstructionHandle next = end.getNext();
    892        if (prev != null) {
    893            prev.setNext(next);
    894        } else {
    895            this.start = next;
    896        }
    897        if (next != null) {
    898            next.setPrev(prev);
    899        } else {
    900            this.end = prev;
    901        }
    902        start.setPrev(end.setNext(null));
    903        // Step 3: append after target
    904        if (target == null) { // append to start of list
    905            if (this.start != null) {
    906                this.start.setPrev(end);
    907            }
    908            end.setNext(this.start);
    909            this.start = start;
    910        } else {
    911            next = target.getNext();
    912            target.setNext(start);
    913            start.setPrev(target);
    914            end.setNext(next);
    915            if (next != null) {
    916                next.setPrev(end);
    917            } else {
    918                this.end = end;
    919            }
    920        }
    921    }
    922
    923    /**
    924     * Redirect all references from oldTarget to newTarget, i.e., update targets of branch instructions.
    925     *
    926     * @param oldTarget the old target instruction handle
    927     * @param newTarget the new target instruction handle
    928     */
    929    public void redirectBranches(final InstructionHandle oldTarget, final InstructionHandle newTarget) {
    930        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    931            final Instruction i = ih.getInstruction();
    932            if (i instanceof BranchInstruction) {
    933                final BranchInstruction b = (BranchInstruction) i;
    934                final InstructionHandle target = b.getTarget();
    935                if (target == oldTarget) {
    936                    b.setTarget(newTarget);
    937                }
    938                if (b instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
    939                    final InstructionHandle[] targets = ((Select) b).getTargets();
    940                    for (int j = 0; j < targets.length; j++) {
    941                        if (targets[j] == oldTarget) {
    942                            ((Select) b).setTarget(j, newTarget);
    943                        }
    944                    }
    945                }
    946            }
    947        }
    948    }
    949
    950    /**
    951     * Redirect all references of exception handlers from oldTarget to newTarget.
    952     *
    953     * @param exceptions array of exception handlers
    954     * @param oldTarget the old target instruction handle
    955     * @param newTarget the new target instruction handle
    956     * @see MethodGen
    957     */
    958    public void redirectExceptionHandlers(final CodeExceptionGen[] exceptions, final InstructionHandle oldTarget, final InstructionHandle newTarget) {
    959        for (final CodeExceptionGen exception : exceptions) {
    960            if (exception.getStartPC() == oldTarget) {
    961                exception.setStartPC(newTarget);
    962            }
    963            if (exception.getEndPC() == oldTarget) {
    964                exception.setEndPC(newTarget);
    965            }
    966            if (exception.getHandlerPC() == oldTarget) {
    967                exception.setHandlerPC(newTarget);
    968            }
    969        }
    970    }
    971
    972    /**
    973     * Redirect all references of local variables from oldTarget to newTarget.
    974     *
    975     * @param lg array of local variables
    976     * @param oldTarget the old target instruction handle
    977     * @param newTarget the new target instruction handle
    978     * @see MethodGen
    979     */
    980    public void redirectLocalVariables(final LocalVariableGen[] lg, final InstructionHandle oldTarget, final InstructionHandle newTarget) {
    981        for (final LocalVariableGen element : lg) {
    982            final InstructionHandle start = element.getStart();
    983            final InstructionHandle end = element.getEnd();
    984            if (start == oldTarget) {
    985                element.setStart(newTarget);
    986            }
    987            if (end == oldTarget) {
    988                element.setEnd(newTarget);
    989            }
    990        }
    991    }
    992
    993    /**
    994     * Remove from instruction 'prev' to instruction 'next' both contained in this list. Throws TargetLostException when one
    995     * of the removed instruction handles is still being targeted.
    996     *
    997     * @param prev where to start deleting (predecessor, exclusive)
    998     * @param next where to end deleting (successor, exclusive)
    999     */
    1000    private void remove(final InstructionHandle prev, InstructionHandle next) throws TargetLostException {
    1001        InstructionHandle first;
    1002        InstructionHandle last; // First and last deleted instruction
    1003        if (prev == null && next == null) {
    1004            first = start;
    1005            last = end;
    1006            start = end = null;
    1007        } else {
    1008            if (prev == null) { // At start of list
    1009                first = start;
    1010                start = next;
    1011            } else {
    1012                first = prev.getNext();
    1013                prev.setNext(next);
    1014            }
    1015            if (next == null) { // At end of list
    1016                last = end;
    1017                end = prev;
    1018            } else {
    1019                last = next.getPrev();
    1020                next.setPrev(prev);
    1021            }
    1022        }
    1023        first.setPrev(null); // Completely separated from rest of list
    1024        last.setNext(null);
    1025        final List<InstructionHandle> targetList = new ArrayList<>();
    1026        for (InstructionHandle ih = first; ih != null; ih = ih.getNext()) {
    1027            ih.getInstruction().dispose(); // e.g. BranchInstructions release their targets
    1028        }
    1029        final StringBuilder buf = new StringBuilder("{ ");
    1030        for (InstructionHandle ih = first; ih != null; ih = next) {
    1031            next = ih.getNext();
    1032            length--;
    1033            if (ih.hasTargeters()) { // Still got targeters?
    1034                targetList.add(ih);
    1035                buf.append(ih.toString(true)).append(" ");
    1036                ih.setNext(ih.setPrev(null));
    1037            } else {
    1038                ih.dispose();
    1039            }
    1040        }
    1041        buf.append("}");
    1042        if (!targetList.isEmpty()) {
    1043            throw new TargetLostException(targetList.toArray(InstructionHandle.EMPTY_ARRAY), buf.toString());
    1044        }
    1045    }
    1046
    1047    /**
    1048     * Remove observer for this object.
    1049     */
    1050    public void removeObserver(final InstructionListObserver o) {
    1051        if (observers != null) {
    1052            observers.remove(o);
    1053        }
    1054    }
    1055
    1056    /**
    1057     * Replace all references to the old constant pool with references to the new constant pool
    1058     */
    1059    public void replaceConstantPool(final ConstantPoolGen oldCp, final ConstantPoolGen newCp) {
    1060        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1061            final Instruction i = ih.getInstruction();
    1062            if (i instanceof CPInstruction) {
    1063                final CPInstruction ci = (CPInstruction) i;
    1064                final Constant c = oldCp.getConstant(ci.getIndex());
    1065                ci.setIndex(newCp.addConstant(c, oldCp));
    1066            }
    1067        }
    1068    }
    1069
    1070    public void setPositions() { // TODO could be package-protected? (some test code would need to be repackaged)
    1071        setPositions(false);
    1072    }
    1073
    1074    /**
    1075     * Give all instructions their position number (offset in byte stream), i.e., make the list ready to be dumped.
    1076     *
    1077     * @param check Perform sanity checks, e.g. if all targeted instructions really belong to this list
    1078     */
    1079    public void setPositions(final boolean check) { // called by code in other packages
    1080        int maxAdditionalBytes = 0;
    1081        int additionalBytes = 0;
    1082        int index = 0;
    1083        int count = 0;
    1084        final int[] pos = new int[length];
    1085        /*
    1086         * Pass 0: Sanity checks
    1087         */
    1088        if (check) {
    1089            for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1090                final Instruction i = ih.getInstruction();
    1091                if (i instanceof BranchInstruction) { // target instruction within list?
    1092                    Instruction inst = ((BranchInstruction) i).getTarget().getInstruction();
    1093                    if (!contains(inst)) {
    1094                        throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list");
    1095                    }
    1096                    if (i instanceof Select) {
    1097                        final InstructionHandle[] targets = ((Select) i).getTargets();
    1098                        for (final InstructionHandle target : targets) {
    1099                            inst = target.getInstruction();
    1100                            if (!contains(inst)) {
    1101                                throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list");
    1102                            }
    1103                        }
    1104                    }
    1105                    if (!(ih instanceof BranchHandle)) {
    1106                        throw new ClassGenException(
    1107                            "Branch instruction " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not contained in BranchHandle.");
    1108                    }
    1109                }
    1110            }
    1111        }
    1112        /*
    1113         * Pass 1: Set position numbers and sum up the maximum number of bytes an instruction may be shifted.
    1114         */
    1115        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
    1116            final Instruction i = ih.getInstruction();
    1117            ih.setPosition(index);
    1118            pos[count++] = index;
    1119            /*
    1120             * Gets an estimate about how many additional bytes may be added, because BranchInstructions may have variable length
    1121             * depending on the target offset (short vs. int) or alignment issues (TABLESWITCH and LOOKUPSWITCH).
    1122             */
    1123            switch (i.getOpcode()) {
    1124            case Const.JSR:
    1125            case Const.GOTO:
    1126                maxAdditionalBytes += 2;
    1127                break;
    1128            case Const.TABLESWITCH:
    1129            case Const.LOOKUPSWITCH:
    1130                maxAdditionalBytes += 3;
    1131                break;
    1132            default:
    1133                // TODO should this be an error?
    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            additionalBytes += ih.updatePosition(additionalBytes, maxAdditionalBytes);
    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 = Arrays.copyOfRange(pos, 0, count); // Trim to proper size
    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}