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