View Javadoc

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