content: /*
   *  This file is part of AndroidIDE.
   *
   *  AndroidIDE is free software: you can redistribute it and/or modify
   *  it under the terms of the GNU General Public License as published by
   *  the Free Software Foundation, either version 3 of the License, or
   *  (at your option) any later version.
   *
   *  AndroidIDE is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
   *   along with AndroidIDE.  If not, see <https://www.gnu.org/licenses/>.
   */
  
  /*
   * reserved comment block
   * DO NOT REMOVE OR ALTER!
   */
  package jaxp.sun.org.apache.bcel.internal.generic;
  
  /* ====================================================================
   * The Apache Software License, Version 1.1
   *
   * Copyright (c) 2001 The Apache Software Foundation.  All rights
   * reserved.
   *
   * Redistribution and use in source and binary forms, with or without
   * modification, are permitted provided that the following conditions
   * are met:
   *
   * 1. Redistributions of source code must retain the above copyright
   *    notice, this list of conditions and the following disclaimer.
   *
   * 2. Redistributions in binary form must reproduce the above copyright
   *    notice, this list of conditions and the following disclaimer in
   *    the documentation and/or other materials provided with the
   *    distribution.
   *
   * 3. The end-user documentation included with the redistribution,
   *    if any, must include the following acknowledgment:
   *       "This product includes software developed by the
   *        Apache Software Foundation (http://www.apache.org/)."
   *    Alternately, this acknowledgment may appear in the software itself,
   *    if and wherever such third-party acknowledgments normally appear.
   *
   * 4. The names "Apache" and "Apache Software Foundation" and
   *    "Apache BCEL" must not be used to endorse or promote products
   *    derived from this software without prior written permission. For
   *    written permission, please contact apache@apache.org.
   *
   * 5. Products derived from this software may not be called "Apache",
   *    "Apache BCEL", nor may "Apache" appear in their name, without
   *    prior written permission of the Apache Software Foundation.
   *
   * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
   * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
   * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
   * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
   * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
   * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
   * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   * SUCH DAMAGE.
   * ====================================================================
   *
   * This software consists of voluntary contributions made by many
   * individuals on behalf of the Apache Software Foundation.  For more
   * information on the Apache Software Foundation, please see
   * <http://www.apache.org/>.
   */
  
  import jaxp.sun.org.apache.bcel.internal.Constants;
  import jaxp.sun.org.apache.bcel.internal.classfile.Constant;
  import jaxp.sun.org.apache.bcel.internal.util.ByteSequence;
  
  import java.io.*;
  import java.util.Iterator;
  import java.util.HashMap;
  import java.util.ArrayList;
  
  /**
   * This class is a container for a list of <a
   * href="Instruction.html">Instruction</a> objects. Instructions can
   * be appended, inserted, moved, deleted, etc.. Instructions are being
   * wrapped into <a
   * href="InstructionHandle.html">InstructionHandles</a> objects that
   * are returned upon append/insert operations. They give the user
   * (read only) access to the list structure, such that it can be traversed and
   * manipulated in a controlled way.
   *
   * A list is finally dumped to a byte code array with <a
   * href="#getByteCode()">getByteCode</a>.
   *
   * @author  <A HREF="mailto:markus.dahm@berlin.de">M. Dahm</A>
   * @see     Instruction
   * @see     InstructionHandle
   * @see BranchHandle
   */
  public class InstructionList implements Serializable {
    private InstructionHandle start  = null, end = null;
    private int               length = 0; // number of elements in list
    private int[]             byte_positions; // byte code offsets corresponding to instructions
  
    /**
     * Create (empty) instruction list.
     */
    public InstructionList() {}
  
    /**
     * Create instruction list containing one instruction.
     * @param i initial instruction
     */
    public InstructionList(Instruction i) {
      append(i);
    }
  
    /**
     * Create instruction list containing one instruction.
     * @param i initial instruction
     */
    public InstructionList(BranchInstruction i) {
      append(i);
    }
  
    /**
     * Initialize list with (nonnull) compound instruction. Consumes argument
     * list, i.e., it becomes empty.
     *
     * @param c compound instruction (list)
     */
    public InstructionList(CompoundInstruction c) {
      append(c.getInstructionList());
    }
  
    /**
     * Test for empty list.
     */
    public boolean isEmpty() { return start == null; } // && end == null
  
    /**
     * Find the target instruction (handle) that corresponds to the given target
     * position (byte code offset).
     *
     * @param ihs array of instruction handles, i.e. il.getInstructionHandles()
     * @param pos array of positions corresponding to ihs, i.e. il.getInstructionPositions()
     * @param count length of arrays
     * @param target target position to search for
     * @return target position's instruction handle if available
     */
    public static InstructionHandle findHandle(InstructionHandle[] ihs,
                                               int[] pos, int count,
                                               int target) {
      int l=0, r = count - 1;
  
      /* Do a binary search since the pos array is orderd.
       */
      do {
        int i = (l + r) / 2;
        int j = pos[i];
  
        if(j == target) // target found
          return ihs[i];
        else if(target < j) // else constrain search area
          r = i - 1;
        else // target > j
          l = i + 1;
      } while(l <= r);
  
      return null;
    }
  
    /**
     * 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
     * setPositions() has been called before this method.
     *
     * @param pos byte code position to search for
     * @return target position's instruction handle if available
     */
    public InstructionHandle findHandle(int pos) {
      InstructionHandle[] ihs = getInstructionHandles();
      return findHandle(ihs, byte_positions, length, pos);
    }
  
    /**
     * Initialize instruction list from byte array.
     *
     * @param code byte array containing the instructions
     */
    public InstructionList(byte[] code) {
      ByteSequence bytes = new ByteSequence(code);
      InstructionHandle[] ihs   = new InstructionHandle[code.length];
      int[]               pos   = new int[code.length]; // Can't be more than that
      int                 count = 0; // Contains actual length
  
      /* Pass 1: Create an object for each byte code and append them
       * to the list.
       */
      try {
        while(bytes.available() > 0) {
          // Remember byte offset and associate it with the instruction
          int off =  bytes.getIndex();
          pos[count] = off;
  
          /* Read one instruction from the byte stream, the byte position is set
           * accordingly.
           */
          Instruction       i = Instruction.readInstruction(bytes);
          InstructionHandle ih;
          if(i instanceof BranchInstruction) // Use proper append() method
            ih = append((BranchInstruction)i);
          else
            ih = append(i);
  
          ih.setPosition(off);
          ihs[count] = ih;
  
          count++;
        }
      } catch(IOException e) { throw new ClassGenException(e.toString()); }
  
      byte_positions = new int[count]; // Trim to proper size
      System.arraycopy(pos, 0, byte_positions, 0, count);
  
      /* Pass 2: Look for BranchInstruction and update their targets, i.e.,
       * convert offsets to instruction handles.
       */
      for(int i=0; i < count; i++) {
        if(ihs[i] instanceof BranchHandle) {
          BranchInstruction bi = (BranchInstruction)ihs[i].instruction;
          int target = bi.position + bi.getIndex(); /* Byte code position:
                                                     * relative -> absolute. */
          // Search for target position
          InstructionHandle ih = findHandle(ihs, pos, count, target);
  
          if(ih == null) // Search failed
            throw new ClassGenException("Couldn't find target for branch: " + bi);
  
          bi.setTarget(ih); // Update target
  
          // If it is a Select instruction, update all branch targets
          if(bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
            Select s       = (Select)bi;
            int[]  indices = s.getIndices();
  
            for(int j=0; j < indices.length; j++) {
              target = bi.position + indices[j];
              ih     = findHandle(ihs, pos, count, target);
  
              if(ih == null) // Search failed
                throw new ClassGenException("Couldn't find target for switch: " + bi);
  
              s.setTarget(j, ih); // Update target
            }
          }
        }
      }
    }
  
    /**
     * Append another list after instruction (handle) ih contained in this list.
     * Consumes argument list, i.e., it becomes empty.
     *
     * @param ih where to append the instruction list
     * @param il Instruction list to append to this one
     * @return instruction handle pointing to the <B>first</B> appended instruction
     */
    public InstructionHandle append(InstructionHandle ih, InstructionList il) {
      if(il == null)
        throw new ClassGenException("Appending null InstructionList");
  
      if(il.isEmpty()) // Nothing to do
        return ih;
  
      InstructionHandle next = ih.next, ret = il.start;
  
      ih.next = il.start;
      il.start.prev = ih;
  
      il.end.next = next;
  
      if(next != null) // i == end ?
        next.prev = il.end;
      else
        end = il.end; // Update end ...
  
      length += il.length; // Update length
  
      il.clear();
  
      return ret;
    }
  
    /**
     * Append another list after instruction i contained in this list.
     * Consumes argument list, i.e., it becomes empty.
     *
     * @param i  where to append the instruction list
     * @param il Instruction list to append to this one
     * @return instruction handle pointing to the <B>first</B> appended instruction
     */
    public InstructionHandle append(Instruction i, InstructionList il) {
      InstructionHandle ih;
  
      if((ih = findInstruction2(i)) == null) // Also applies for empty list
        throw new ClassGenException("Instruction " + i +
                                    " is not contained in this list.");
  
      return append(ih, il);
    }
  
    /**
     * Append another list to this one.
     * Consumes argument list, i.e., it becomes empty.
     *
     * @param il list to append to end of this list
     * @return instruction handle of the <B>first</B> appended instruction
     */
    public InstructionHandle append(InstructionList il) {
      if(il == null)
        throw new ClassGenException("Appending null InstructionList");
  
      if(il.isEmpty()) // Nothing to do
        return null;
  
      if(isEmpty()) {
        start  = il.start;
        end    = il.end;
        length = il.length;
  
        il.clear();
  
        return start;
      } else
        return append(end, il);  // was end.instruction
    }
  
    /**
     * Append an instruction to the end of this list.
     *
     * @param ih instruction to append
     */
    private void append(InstructionHandle ih) {
      if(isEmpty()) {
        start = end = ih;
        ih.next = ih.prev = null;
      }
      else {
        end.next = ih;
        ih.prev  = end;
        ih.next  = null;
        end      = ih;
      }
  
      length++; // Update length
    }
  
    /**
     * Append an instruction to the end of this list.
     *
     * @param i instruction to append
     * @return instruction handle of the appended instruction
     */
    public InstructionHandle append(Instruction i) {
      InstructionHandle ih = InstructionHandle.getInstructionHandle(i);
      append(ih);
  
      return ih;
    }
  
    /**
     * Append a branch instruction to the end of this list.
     *
     * @param i branch instruction to append
     * @return branch instruction handle of the appended instruction
     */
    public BranchHandle append(BranchInstruction i) {
      BranchHandle ih = BranchHandle.getBranchHandle(i);
      append(ih);
  
      return ih;
    }
  
    /**
     * Append a single instruction j after another instruction i, which
     * must be in this list of course!
     *
     * @param i Instruction in list
     * @param j Instruction to append after i in list
     * @return instruction handle of the first appended instruction
     */
    public InstructionHandle append(Instruction i, Instruction j) {
      return append(i, new InstructionList(j));
    }
  
    /**
     * Append a compound instruction, after instruction i.
     *
     * @param i Instruction in list
     * @param c The composite instruction (containing an InstructionList)
     * @return instruction handle of the first appended instruction
     */
    public InstructionHandle append(Instruction i, CompoundInstruction c) {
      return append(i, c.getInstructionList());
    }
  
    /**
     * Append a compound instruction.
     *
     * @param c The composite instruction (containing an InstructionList)
     * @return instruction handle of the first appended instruction
     */
    public InstructionHandle append(CompoundInstruction c) {
      return append(c.getInstructionList());
    }
  
    /**
     * Append a compound instruction.
     *
     * @param ih where to append the instruction list
     * @param c The composite instruction (containing an InstructionList)
     * @return instruction handle of the first appended instruction
     */
    public InstructionHandle append(InstructionHandle ih, CompoundInstruction c) {
      return append(ih, c.getInstructionList());
    }
  
    /**
     * Append an instruction after instruction (handle) ih contained in this list.
     *
     * @param ih where to append the instruction list
     * @param i Instruction to append
     * @return instruction handle pointing to the <B>first</B> appended instruction
     */
    public InstructionHandle append(InstructionHandle ih, Instruction i) {
      return append(ih, new InstructionList(i));
    }
  
    /**
     * Append an instruction after instruction (handle) ih contained in this list.
     *
     * @param ih where to append the instruction list
     * @param i Instruction to append
     * @return instruction handle pointing to the <B>first</B> appended instruction
     */
    public BranchHandle append(InstructionHandle ih, BranchInstruction i) {
      BranchHandle    bh = BranchHandle.getBranchHandle(i);
      InstructionList il = new InstructionList();
      il.append(bh);
  
      append(ih, il);
  
      return bh;
    }
  
    /**
     * Insert another list before Instruction handle ih contained in this list.
     * Consumes argument list, i.e., it becomes empty.
     *
     * @param i  where to append the instruction list
     * @param il Instruction list to insert
     * @return instruction handle of the first inserted instruction
     */
    public InstructionHandle insert(InstructionHandle ih, InstructionList il) {
      if(il == null)
        throw new ClassGenException("Inserting null InstructionList");
  
      if(il.isEmpty()) // Nothing to do
        return ih;
  
      InstructionHandle prev = ih.prev, ret = il.start;
  
      ih.prev = il.end;
      il.end.next = ih;
  
      il.start.prev = prev;
  
      if(prev != null) // ih == start ?
        prev.next = il.start;
      else
        start = il.start; // Update start ...
  
      length += il.length; // Update length
  
      il.clear();
  
      return ret;
    }
  
    /**
     * Insert another list.
     *
     * @param il list to insert before start of this list
     * @return instruction handle of the first inserted instruction
     */
    public InstructionHandle insert(InstructionList il) {
      if(isEmpty()) {
        append(il); // Code is identical for this case
        return start;
      }
      else
        return insert(start, il);
    }
  
    /**
     * Insert an instruction at start of this list.
     *
     * @param ih instruction to insert
     */
    private void insert(InstructionHandle ih) {
      if(isEmpty()) {
        start = end = ih;
        ih.next = ih.prev = null;
      } else {
        start.prev = ih;
        ih.next    = start;
        ih.prev    = null;
        start      = ih;
      }
  
      length++;
    }
  
    /**
     * Insert another list before Instruction i contained in this list.
     * Consumes argument list, i.e., it becomes empty.
     *
     * @param i  where to append the instruction list
     * @param il Instruction list to insert
     * @return instruction handle pointing to the first inserted instruction,
     * i.e., il.getStart()
     */
    public InstructionHandle insert(Instruction i, InstructionList il) {
      InstructionHandle ih;
  
      if((ih = findInstruction1(i)) == null)
        throw new ClassGenException("Instruction " + i +
                                    " is not contained in this list.");
  
      return insert(ih, il);
    }
  
    /**
     * Insert an instruction at start of this list.
     *
     * @param i instruction to insert
     * @return instruction handle of the inserted instruction
     */
    public InstructionHandle insert(Instruction i) {
      InstructionHandle ih = InstructionHandle.getInstructionHandle(i);
      insert(ih);
  
      return ih;
    }
  
    /**
     * Insert a branch instruction at start of this list.
     *
     * @param i branch instruction to insert
     * @return branch instruction handle of the appended instruction
     */
    public BranchHandle insert(BranchInstruction i) {
      BranchHandle ih = BranchHandle.getBranchHandle(i);
      insert(ih);
      return ih;
    }
  
    /**
     * Insert a single instruction j before another instruction i, which
     * must be in this list of course!
     *
     * @param i Instruction in list
     * @param j Instruction to insert before i in list
     * @return instruction handle of the first inserted instruction
     */
    public InstructionHandle insert(Instruction i, Instruction j) {
      return insert(i, new InstructionList(j));
    }
  
    /**
     * Insert a compound instruction before instruction i.
     *
     * @param i Instruction in list
     * @param c The composite instruction (containing an InstructionList)
     * @return instruction handle of the first inserted instruction
     */
    public InstructionHandle insert(Instruction i, CompoundInstruction c) {
      return insert(i, c.getInstructionList());
    }
  
    /**
     * Insert a compound instruction.
     *
     * @param c The composite instruction (containing an InstructionList)
     * @return instruction handle of the first inserted instruction
     */
    public InstructionHandle insert(CompoundInstruction c) {
      return insert(c.getInstructionList());
    }
  
    /**
     * Insert an instruction before instruction (handle) ih contained in this list.
     *
     * @param ih where to insert to the instruction list
     * @param i Instruction to insert
     * @return instruction handle of the first inserted instruction
     */
    public InstructionHandle insert(InstructionHandle ih, Instruction i) {
      return insert(ih, new InstructionList(i));
    }
  
    /**
     * Insert a compound instruction.
     *
     * @param ih where to insert the instruction list
     * @param c The composite instruction (containing an InstructionList)
     * @return instruction handle of the first inserted instruction
     */
    public InstructionHandle insert(InstructionHandle ih, CompoundInstruction c) {
      return insert(ih, c.getInstructionList());
    }
  
    /**
     * Insert an instruction before instruction (handle) ih contained in this list.
     *
     * @param ih where to insert to the instruction list
     * @param i Instruction to insert
     * @return instruction handle of the first inserted instruction
     */
    public BranchHandle insert(InstructionHandle ih, BranchInstruction i) {
      BranchHandle    bh = BranchHandle.getBranchHandle(i);
      InstructionList il = new InstructionList();
      il.append(bh);
  
      insert(ih, il);
  
      return bh;
    }
  
    /**
     * 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 must
     * not be located withing this range. If you want to move something to the start of
     * the list use null as value for target.<br>
     * Any instruction targeters pointing to handles within the block, keep their targets.
     *
     * @param start  of moved block
     * @param end    of moved block
     * @param target of moved block
     */
    public void move(InstructionHandle start, InstructionHandle end, InstructionHandle target) {
      // Step 1: Check constraints
  
      if((start == null) || (end == null))
        throw new ClassGenException("Invalid null handle: From " + start + " to " + end);
  
      if((target == start) || (target == end))
        throw new ClassGenException("Invalid range: From " + start + " to " + end +
                                    " contains target " + target);
  
      for(InstructionHandle ih = start; ih != end.next; ih = ih.next) {
        if(ih == null) // At end of list, end not found yet
          throw new ClassGenException("Invalid range: From " + start + " to " + end);
        else if(ih == target) // target may be null
          throw new ClassGenException("Invalid range: From " + start + " to " + end +
                                      " contains target " + target);
      }
  
      // Step 2: Temporarily remove the given instructions from the list
  
      InstructionHandle prev = start.prev, next = end.next;
  
      if(prev != null)
        prev.next = next;
      else // start == this.start!
        this.start = next;
  
      if(next != null)
        next.prev = prev;
      else // end == this.end!
        this.end = prev;
  
      start.prev = end.next = null;
  
      // Step 3: append after target
  
      if(target == null) { // append to start of list
        end.next = this.start;
        this.start = start;
      } else {
        next = target.next;
  
        target.next = start;
        start.prev  = target;
        end.next    = next;
  
        if(next != null)
          next.prev = end;
      }
    }
  
    /**
     * Move a single instruction (handle) to a new location.
     *
     * @param ih     moved instruction
     * @param target new location of moved instruction
     */
    public void move(InstructionHandle ih, InstructionHandle target) {
      move(ih, ih, target);
    }
  
    /**
     * Remove from instruction `prev' to instruction `next' both contained
     * in this list. Throws TargetLostException when one of the removed instruction handles
     * is still being targeted.
     *
     * @param prev where to start deleting (predecessor, exclusive)
     * @param next where to end deleting (successor, exclusive)
     */
    private void remove(InstructionHandle prev, InstructionHandle next)
      throws TargetLostException
    {
      InstructionHandle first, last; // First and last deleted instruction
  
      if((prev == null) && (next == null)) { // singleton list
        first = last = start;
        start = end = null;
      } else {
        if(prev == null) { // At start of list
          first = start;
          start = next;
        } else {
          first     = prev.next;
          prev.next = next;
        }
  
        if(next == null) { // At end of list
          last = end;
          end  = prev;
        } else {
          last      = next.prev;
          next.prev = prev;
        }
      }
  
      first.prev = null; // Completely separated from rest of list
      last.next  = null;
  
      ArrayList target_vec = new ArrayList();
  
      for(InstructionHandle ih=first; ih != null; ih = ih.next)
        ih.getInstruction().dispose(); // e.g. BranchInstructions release their targets
  
      StringBuffer buf = new StringBuffer("{ ");
      for(InstructionHandle ih=first; ih != null; ih = next) {
        next = ih.next;
        length--;
  
        if(ih.hasTargeters()) { // Still got targeters?
          target_vec.add(ih);
          buf.append(ih.toString(true) + " ");
          ih.next = ih.prev = null;
        } else
          ih.dispose();
      }
  
      buf.append("}");
  
      if(!target_vec.isEmpty()) {
        InstructionHandle[] targeted = new InstructionHandle[target_vec.size()];
        target_vec.toArray(targeted);
        throw new TargetLostException(targeted, buf.toString());
      }
    }
  
    /**
     * Remove instruction from this list. The corresponding Instruction
     * handles must not be reused!
     *
     * @param ih instruction (handle) to remove
     */
    public void delete(InstructionHandle ih) throws TargetLostException {
      remove(ih.prev, ih.next);
    }
  
    /**
     * Remove instruction from this list. The corresponding Instruction
     * handles must not be reused!
     *
     * @param i instruction to remove
     */
    public void delete(Instruction i) throws TargetLostException {
      InstructionHandle ih;
  
      if((ih = findInstruction1(i)) == null)
        throw new ClassGenException("Instruction " + i +
                                    " is not contained in this list.");
      delete(ih);
    }
  
    /**
     * Remove instructions from instruction `from' to instruction `to' contained
     * in this list. The user must ensure that `from' is an instruction before
     * `to', or risk havoc. The corresponding Instruction handles must not be reused!
     *
     * @param from where to start deleting (inclusive)
     * @param to   where to end deleting (inclusive)
     */
    public void delete(InstructionHandle from, InstructionHandle to)
      throws TargetLostException
    {
      remove(from.prev, to.next);
    }
  
    /**
     * Remove instructions from instruction `from' to instruction `to' contained
     * in this list. The user must ensure that `from' is an instruction before
     * `to', or risk havoc. The corresponding Instruction handles must not be reused!
     *
     * @param from where to start deleting (inclusive)
     * @param to   where to end deleting (inclusive)
     */
    public void delete(Instruction from, Instruction to) throws TargetLostException {
      InstructionHandle from_ih, to_ih;
  
      if((from_ih = findInstruction1(from)) == null)
        throw new ClassGenException("Instruction " + from +
                                    " is not contained in this list.");
  
      if((to_ih = findInstruction2(to)) == null)
        throw new ClassGenException("Instruction " + to +
                                    " is not contained in this list.");
      delete(from_ih, to_ih);
    }
  
    /**
     * Search for given Instruction reference, start at beginning of list.
     *
     * @param i instruction to search for
     * @return instruction found on success, null otherwise
     */
    private InstructionHandle findInstruction1(Instruction i) {
      for(InstructionHandle ih=start; ih != null; ih = ih.next)
        if(ih.instruction == i)
          return ih;
  
      return null;
    }
  
    /**
     * Search for given Instruction reference, start at end of list
     *
     * @param i instruction to search for
     * @return instruction found on success, null otherwise
     */
    private InstructionHandle findInstruction2(Instruction i) {
      for(InstructionHandle ih=end; ih != null; ih = ih.prev)
        if(ih.instruction == i)
          return ih;
  
      return null;
    }
  
    public boolean contains(InstructionHandle i) {
      if(i == null)
        return false;
  
      for(InstructionHandle ih=start; ih != null; ih = ih.next)
        if(ih == i)
          return true;
  
      return false;
    }
  
    public boolean contains(Instruction i) {
      return findInstruction1(i) != null;
    }
  
    public void setPositions() {
      setPositions(false);
    }
  
    /**
     * Give all instructions their position number (offset in byte stream), i.e.,
     * make the list ready to be dumped.
     *
     * @param check Perform sanity checks, e.g. if all targeted instructions really belong
     * to this list
     */
    public void setPositions(boolean check) {
      int max_additional_bytes = 0, additional_bytes = 0;
      int index = 0, count = 0;
      int[] pos = new int[length];
  
      /* Pass 0: Sanity checks
       */
      if(check) {
        for(InstructionHandle ih=start; ih != null; ih = ih.next) {
          Instruction i = ih.instruction;
  
          if(i instanceof BranchInstruction) { // target instruction within list?
            Instruction inst = ((BranchInstruction)i).getTarget().instruction;
            if(!contains(inst))
              throw new ClassGenException("Branch target of " +
                                          Constants.OPCODE_NAMES[i.opcode] + ":" +
                                          inst + " not in instruction list");
  
            if(i instanceof Select) {
              InstructionHandle[] targets = ((Select)i).getTargets();
  
              for(int j=0; j < targets.length; j++) {
                inst = targets[j].instruction;
                if(!contains(inst))
                  throw new ClassGenException("Branch target of " +
                                              Constants.OPCODE_NAMES[i.opcode] + ":" +
                                              inst + " not in instruction list");
              }
            }
  
            if(!(ih instanceof BranchHandle))
              throw new ClassGenException("Branch instruction " +
                                          Constants.OPCODE_NAMES[i.opcode] + ":" +
                                          inst + " not contained in BranchHandle.");
  
          }
        }
      }
  
      /* Pass 1: Set position numbers and sum up the maximum number of bytes an
       * instruction may be shifted.
       */
      for(InstructionHandle ih=start; ih != null; ih = ih.next) {
        Instruction i = ih.instruction;
  
        ih.setPosition(index);
        pos[count++] = index;
  
        /* Get an estimate about how many additional bytes may be added, because
         * BranchInstructions may have variable length depending on the target
         * offset (short vs. int) or alignment issues (TABLESWITCH and
         * LOOKUPSWITCH).
         */
        switch(i.getOpcode()) {
        case Constants.JSR: case Constants.GOTO:
          max_additional_bytes += 2;
          break;
  
        case Constants.TABLESWITCH: case Constants.LOOKUPSWITCH:
          max_additional_bytes += 3;
          break;
        }
  
        index += i.getLength();
      }
  
      /* Pass 2: Expand the variable-length (Branch)Instructions depending on
       * the target offset (short or int) and ensure that branch targets are
       * within this list.
       */
      for(InstructionHandle ih=start; ih != null; ih = ih.next)
        additional_bytes += ih.updatePosition(additional_bytes, max_additional_bytes);
  
      /* Pass 3: Update position numbers (which may have changed due to the
       * preceding expansions), like pass 1.
       */
      index=count=0;
      for(InstructionHandle ih=start; ih != null; ih = ih.next) {
        Instruction i = ih.instruction;
  
        ih.setPosition(index);
        pos[count++] = index;
        index += i.getLength();
      }
  
      byte_positions = new int[count]; // Trim to proper size
      System.arraycopy(pos, 0, byte_positions, 0, count);
    }
  
    /**
     * When everything is finished, use this method to convert the instruction
     * list into an array of bytes.
     *
     * @return the byte code ready to be dumped
     */
    public byte[] getByteCode() {
      // Update position indices of instructions
      setPositions();
  
      ByteArrayOutputStream b   = new ByteArrayOutputStream();
      DataOutputStream      out = new DataOutputStream(b);
  
      try {
        for(InstructionHandle ih=start; ih != null; ih = ih.next) {
          Instruction i = ih.instruction;
          i.dump(out); // Traverse list
        }
      } catch(IOException e) {
        System.err.println(e);
        return null;
      }
  
      return b.toByteArray();
    }
  
    /**
     * @return an array of instructions without target information for branch instructions.
     */
    public Instruction[] getInstructions() {
      ByteSequence  bytes        = new ByteSequence(getByteCode());
      ArrayList     instructions = new ArrayList();
  
      try {
        while(bytes.available() > 0) {
          instructions.add(Instruction.readInstruction(bytes));
        }
      } catch(IOException e) { throw new ClassGenException(e.toString()); }
  
      Instruction[] result = new Instruction[instructions.size()];
      instructions.toArray(result);
      return result;
    }
  
    public String toString() {
      return toString(true);
    }
  
    /**
     * @param verbose toggle output format
     * @return String containing all instructions in this list.
     */
    public String toString(boolean verbose) {
      StringBuffer buf = new StringBuffer();
  
      for(InstructionHandle ih=start; ih != null; ih = ih.next) {
        buf.append(ih.toString(verbose) + "\n");
      }
  
      return buf.toString();
    }
  
    /**
     * @return Enumeration that lists all instructions (handles)
     */
    public Iterator iterator() {
      return new Iterator() {
        private InstructionHandle ih = start;
  
        public Object next() {
          InstructionHandle i = ih;
          ih = ih.next;
          return i;
        }
  
        public void remove() {
          throw new UnsupportedOperationException();
        }
  
        public boolean hasNext() { return ih != null; }
      };
    }
  
    /**
     * @return array containing all instructions (handles)
     */
    public InstructionHandle[] getInstructionHandles() {
      InstructionHandle[] ihs = new InstructionHandle[length];
      InstructionHandle   ih  = start;
  
      for(int i=0; i < length; i++) {
        ihs[i] = ih;
        ih = ih.next;
      }
  
      return ihs;
    }
  
    /**
     * 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 setPositions()
     * has been called. Otherwise this may be inaccurate.
     *
     * @return array containing all instruction's offset in byte code
     */
    public int[] getInstructionPositions() { return byte_positions; }
  
    /**
     * @return complete, i.e., deep copy of this list
     */
    public InstructionList copy() {
      HashMap         map = new HashMap();
      InstructionList il  = new InstructionList();
  
      /* 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.
       */
      for(InstructionHandle ih=start; ih != null; ih = ih.next) {
        Instruction i = ih.instruction;
        Instruction c = i.copy(); // Use clone for shallow copy
  
        if(c instanceof BranchInstruction)
          map.put(ih, il.append((BranchInstruction)c));
        else
          map.put(ih, il.append(c));
      }
  
      /* Pass 2: Update branch targets.
       */
      InstructionHandle ih=start;
      InstructionHandle ch=il.start;
  
      while(ih != null) {
        Instruction i = ih.instruction;
        Instruction c = ch.instruction;
  
        if(i instanceof BranchInstruction) {
          BranchInstruction bi      = (BranchInstruction)i;
          BranchInstruction bc      = (BranchInstruction)c;
          InstructionHandle itarget = bi.getTarget(); // old target
  
          // New target is in hash map
          bc.setTarget((InstructionHandle)map.get(itarget));
  
          if(bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
            InstructionHandle[] itargets = ((Select)bi).getTargets();
            InstructionHandle[] ctargets = ((Select)bc).getTargets();
  
            for(int j=0; j < itargets.length; j++) { // Update all targets
              ctargets[j] = (InstructionHandle)map.get(itargets[j]);
            }
          }
        }
  
        ih = ih.next;
        ch = ch.next;
      }
  
      return il;
    }
  
    /** Replace all references to the old constant pool with references to the new
     *  constant pool
     */
    public void replaceConstantPool(ConstantPoolGen old_cp, ConstantPoolGen new_cp) {
      for(InstructionHandle ih=start; ih != null; ih = ih.next) {
        Instruction i = ih.instruction;
  
        if(i instanceof CPInstruction) {
          CPInstruction ci = (CPInstruction)i;
          Constant c  = old_cp.getConstant(ci.getIndex());
          ci.setIndex(new_cp.addConstant(c, old_cp));
        }
      }
    }
  
    private void clear() {
      start = end = null;
      length = 0;
    }
  
    /**
     * Delete contents of list. Provides besser memory utilization,
     * because the system then may reuse the instruction handles. This
     * method is typically called right after
     * <href="MethodGen.html#getMethod()">MethodGen.getMethod()</a>.
     */
    public void dispose() {
      // Traverse in reverse order, because ih.next is overwritten
      for(InstructionHandle ih=end; ih != null; ih = ih.prev)
        /* Causes BranchInstructions to release target and targeters, because it
         * calls dispose() on the contained instruction.
         */
        ih.dispose();
  
      clear();
    }
  
    /**
     * @return start of list
     */
    public InstructionHandle getStart() { return start; }
  
    /**
     * @return end of list
     */
    public InstructionHandle getEnd()   { return end; }
  
    /**
     * @return length of list (Number of instructions, not bytes)
     */
    public int getLength() { return length; }
  
    /**
     * @return length of list (Number of instructions, not bytes)
     */
    public int size() { return length; }
  
    /**
     * Redirect all references from old_target to new_target, i.e., update targets
     * of branch instructions.
     *
     * @param old_target the old target instruction handle
     * @param new_target the new target instruction handle
     */
    public void redirectBranches(InstructionHandle old_target,
                                 InstructionHandle new_target) {
      for(InstructionHandle ih = start; ih != null; ih = ih.next) {
        Instruction i  = ih.getInstruction();
  
        if(i instanceof BranchInstruction) {
          BranchInstruction b      = (BranchInstruction)i;
          InstructionHandle target = b.getTarget();
  
          if(target == old_target)
            b.setTarget(new_target);
  
          if(b instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
            InstructionHandle[] targets = ((Select)b).getTargets();
  
            for(int j=0; j < targets.length; j++) // Update targets
              if(targets[j] == old_target)
                ((Select)b).setTarget(j, new_target);
          }
        }
      }
    }
  
    /**
     * Redirect all references of local variables from old_target to new_target.
     *
     * @param lg array of local variables
     * @param old_target the old target instruction handle
     * @param new_target the new target instruction handle
     * @see MethodGen
     */
    public void redirectLocalVariables(LocalVariableGen[] lg,
                                       InstructionHandle old_target,
                                       InstructionHandle new_target) {
      for(int i=0; i < lg.length; i++) {
        InstructionHandle start = lg[i].getStart();
        InstructionHandle end   = lg[i].getEnd();
  
        if(start == old_target)
          lg[i].setStart(new_target);
  
        if(end == old_target)
          lg[i].setEnd(new_target);
      }
    }
  
    /**
     * Redirect all references of exception handlers from old_target to new_target.
     *
     * @param exceptions array of exception handlers
     * @param old_target the old target instruction handle
     * @param new_target the new target instruction handle
     * @see MethodGen
     */
    public void redirectExceptionHandlers(CodeExceptionGen[] exceptions,
                                          InstructionHandle old_target,
                                          InstructionHandle new_target) {
      for(int i=0; i < exceptions.length; i++) {
        if(exceptions[i].getStartPC() == old_target)
          exceptions[i].setStartPC(new_target);
  
        if(exceptions[i].getEndPC() == old_target)
          exceptions[i].setEndPC(new_target);
  
        if(exceptions[i].getHandlerPC() == old_target)
          exceptions[i].setHandlerPC(new_target);
      }
    }
  
    private ArrayList observers;
  
    /** Add observer for this object.
     */
    public void addObserver(InstructionListObserver o) {
      if(observers == null)
        observers = new ArrayList();
  
      observers.add(o);
    }
  
    /** Remove observer for this object.
     */
    public void removeObserver(InstructionListObserver o) {
      if(observers != null)
        observers.remove(o);
    }
  
    /** 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 has finished editing the object.
     */
    public void update() {
      if(observers != null)
        for(Iterator e = observers.iterator(); e.hasNext(); )
          ((InstructionListObserver)e.next()).notify(this);
    }
  }
  