/*

 * reserved comment block

 * DO NOT REMOVE OR ALTER!

 */

package com.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 com.sun.org.apache.bcel.internal.Constants;

import com.sun.org.apache.bcel.internal.classfile.Constant;

import com.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);

  }