/*

 */

 * Licensed to the Apache Software Foundation (ASF) under one or more

 * contributor license agreements.  See the NOTICE file distributed with

 * this work for additional information regarding copyright ownership.

 * The ASF licenses this file to You under the Apache License, Version 2.0

 * (the "License"); you may not use this file except in compliance with

 * the License.  You may obtain a copy of the License at

 *

 *      http://www.apache.org/licenses/LICENSE-2.0

 *

 * Unless required by applicable law or agreed to in writing, software

 * distributed under the License is distributed on an "AS IS" BASIS,

 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 * See the License for the specific language governing permissions and

 * limitations under the License.

 */

package com.sun.org.apache.bcel.internal.generic;

import com.sun.org.apache.bcel.internal.Const;

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

import com.sun.org.apache.bcel.internal.util.ByteSequence;

import java.io.ByteArrayOutputStream;

import java.io.DataOutputStream;

import java.io.IOException;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.NoSuchElementException;

/**

 * 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>.

 *

 * @see Instruction

 * @see InstructionHandle

 * @see BranchHandle

 */

public class InstructionList implements Iterable<InstructionHandle> {

    private InstructionHandle start = null;

    private InstructionHandle 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(final Instruction i) {

        append(i);

    }

    /**

     * Create instruction list containing one instruction.

     *

     * @param i initial instruction

     */

    public InstructionList(final 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(final 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(final InstructionHandle[] ihs, final int[] pos, final int count, final int target) {

        int l = 0;

        int r = count - 1;

        /*

         * Do a binary search since the pos array is orderd.

         */

        do {

            final int i = (l + r) / 2;

            final int j = pos[i];

            if (j == target) {

                return ihs[i];

            } else if (target < j) {

                r = i - 1;

            } else {

                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(final int pos) {

        final int[] positions = byte_positions;

        InstructionHandle ih = start;

        for (int i = 0; i < length; i++) {

            if (positions[i] == pos) {

                return ih;

            }

            ih = ih.getNext();

        }

        return null;

    }

    /**

     * Initialize instruction list from byte array.

     *

     * @param code byte array containing the instructions

     */

    public InstructionList(final byte[] code) {

        int count = 0; // Contains actual length

        int[] pos;

        InstructionHandle[] ihs;

        try (ByteSequence bytes = new ByteSequence(code)) {

            ihs = new InstructionHandle[code.length];

            pos = new int[code.length]; // Can't be more than that

            /*

             * Pass 1: Create an object for each byte code and append them to the list.

             */

            while (bytes.available() > 0) {

                // Remember byte offset and associate it with the instruction

                final int off = bytes.getIndex();

                pos[count] = off;

                /*

                 * Read one instruction from the byte stream, the byte position is set accordingly.

                 */

                final Instruction i = Instruction.readInstruction(bytes);

                InstructionHandle ih;

                if (i instanceof BranchInstruction) {

                    ih = append((BranchInstruction) i);

                } else {

                    ih = append(i);

                }

                ih.setPosition(off);

                ihs[count] = ih;

                count++;

            }

        } catch (final IOException e) {

            throw new ClassGenException(e.toString(), e);

        }

        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) {

                final BranchInstruction bi = (BranchInstruction) ihs[i].getInstruction();

                 */

                // Search for target position

                InstructionHandle ih = findHandle(ihs, pos, count, target);

                if (ih == null) {

                    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

                    final Select s = (Select) bi;

                    final int[] indices = s.getIndices();

                    for (int j = 0; j < indices.length; j++) {

                        target = bi.getPosition() + indices[j];

                        ih = findHandle(ihs, pos, count, target);

                        if (ih == null) {

                            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(final InstructionHandle ih, final InstructionList il) {

        if (il == null) {

            throw new ClassGenException("Appending null InstructionList");

        }

        if (il.isEmpty()) {

            return ih;

        }

        final InstructionHandle next = ih.getNext();

        final InstructionHandle ret = il.start;

        ih.setNext(il.start);

        il.start.setPrev(ih);

        il.end.setNext(next);

        if (next != null) {

            next.setPrev(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(final Instruction i, final InstructionList il) {

        InstructionHandle ih;

        if ((ih = findInstruction2(i)) == null) {

            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(final InstructionList il) {

        if (il == null) {

            throw new ClassGenException("Appending null InstructionList");

        }

        if (il.isEmpty()) {

            return null;

        }

        if (isEmpty()) {

            start = il.start;

            end = il.end;

            length = il.length;

            il.clear();

            return start;

        }

        return append(end, il); // was end.instruction

    }

    /**

     * Append an instruction to the end of this list.

     *

     * @param ih instruction to append

     */

    private void append(final InstructionHandle ih) {

        if (isEmpty()) {

            start = end = ih;

            ih.setNext(ih.setPrev(null));

        } else {

            end.setNext(ih);

            ih.setPrev(end);

            ih.setNext(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(final Instruction i) {

        final 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(final BranchInstruction i) {

        final 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(final Instruction i, final 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(final Instruction i, final 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(final 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(final InstructionHandle ih, final 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(final InstructionHandle ih, final 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(final InstructionHandle ih, final BranchInstruction i) {

        final BranchHandle bh = BranchHandle.getBranchHandle(i);

        final 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 ih where to append the instruction list

     * @param il Instruction list to insert

     * @return instruction handle of the first inserted instruction

     */

    public InstructionHandle insert(final InstructionHandle ih, final InstructionList il) {

        if (il == null) {

            throw new ClassGenException("Inserting null InstructionList");

        }

        if (il.isEmpty()) {

            return ih;

        }

        final InstructionHandle prev = ih.getPrev();

        final InstructionHandle ret = il.start;

        ih.setPrev(il.end);

        il.end.setNext(ih);

        il.start.setPrev(prev);

        if (prev != null) {

            prev.setNext(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(final InstructionList il) {

        if (isEmpty()) {

            append(il); // Code is identical for this case

            return start;

        }

        return insert(start, il);

    }

    /**

     * Insert an instruction at start of this list.

     *

     * @param ih instruction to insert

     */

    private void insert(final InstructionHandle ih) {

        if (isEmpty()) {

            start = end = ih;

            ih.setNext(ih.setPrev(null));

        } else {

            start.setPrev(ih);

            ih.setNext(start);

            ih.setPrev(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(final Instruction i, final 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