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