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