/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed 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.android.jack.dx.rop.code;

import com.android.jack.dx.rop.type.StdTypeList;
import com.android.jack.dx.rop.type.TypeList;
import com.android.jack.dx.util.Hex;
import com.android.jack.dx.util.IntList;
import com.android.jack.dx.util.LabeledList;

/**
 * List of {@link BasicBlock} instances.
 */
public final class BasicBlockList extends LabeledList {
  /**
   * {@code >= -1;} the count of registers required by this method or
   * {@code -1} if not yet calculated
   */
  private int regCount;

  /**
   * Constructs an instance. All indices initially contain {@code null},
   * and the first-block label is initially {@code -1}.
   *
   * @param size the size of the list
   */
  public BasicBlockList(int size) {
    super(size);

    regCount = -1;
  }

  /**
   * Constructs a mutable copy for {@code getMutableCopy()}.
   *
   * @param old block to copy
   */
  private BasicBlockList(BasicBlockList old) {
    super(old);
    regCount = old.regCount;
  }


  /**
   * Gets the element at the given index. It is an error to call
   * this with the index for an element which was never set; if you
   * do that, this will throw {@code NullPointerException}.
   *
   * @param n {@code >= 0, < size();} which index
   * @return {@code non-null;} element at that index
   */
  public BasicBlock get(int n) {
    return (BasicBlock) get0(n);
  }

  /**
   * Sets the basic block at the given index.
   *
   * @param n {@code >= 0, < size();} which index
   * @param bb {@code null-ok;} the element to set at {@code n}
   */
  public void set(int n, BasicBlock bb) {
    super.set(n, bb);

    // Reset regCount, since it will need to be recalculated.
    regCount = -1;
  }

  /**
   * Returns how many registers this method requires. This is simply
   * the maximum of register-number-plus-category referred to by this
   * instance's instructions (indirectly through {@link BasicBlock}
   * instances).
   *
   * @return {@code >= 0;} the register count
   */
  public int getRegCount() {
    if (regCount == -1) {
      RegCountVisitor visitor = new RegCountVisitor();
      forEachInsn(visitor);
      regCount = visitor.getRegCount();
    }

    return regCount;
  }

  /**
   * Gets the total instruction count for this instance. This is the
   * sum of the instruction counts of each block.
   *
   * @return {@code >= 0;} the total instruction count
   */
  public int getInstructionCount() {
    int sz = size();
    int result = 0;

    for (int i = 0; i < sz; i++) {
      BasicBlock one = (BasicBlock) getOrNull0(i);
      if (one != null) {
        result += one.getInsns().size();
      }
    }

    return result;
  }

  /**
   * Gets the total instruction count for this instance, ignoring
   * mark-local instructions which are not actually emitted.
   *
   * @return {@code >= 0;} the total instruction count
   */
  public int getEffectiveInstructionCount() {
    int sz = size();
    int result = 0;

    for (int i = 0; i < sz; i++) {
      BasicBlock one = (BasicBlock) getOrNull0(i);
      if (one != null) {
        InsnList insns = one.getInsns();
        int insnsSz = insns.size();

        for (int j = 0; j < insnsSz; j++) {
          Insn insn = insns.get(j);

          if (insn.getOpcode().getOpcode() != RegOps.MARK_LOCAL) {
            result++;
          }
        }
      }
    }

    return result;
  }

  /**
   * Gets the first block in the list with the given label, if any.
   *
   * @param label {@code >= 0;} the label to look for
   * @return {@code non-null;} the so-labelled block
   * @throws IllegalArgumentException thrown if the label isn't found
   */
  public BasicBlock labelToBlock(int label) {
    int idx = indexOfLabel(label);

    if (idx < 0) {
      throw new IllegalArgumentException("no such label: " + Hex.u2(label));
    }

    return get(idx);
  }

  /**
   * Visits each instruction of each block in the list, in order.
   *
   * @param visitor {@code non-null;} visitor to use
   */
  public void forEachInsn(Insn.Visitor visitor) {
    int sz = size();

    for (int i = 0; i < sz; i++) {
      BasicBlock one = get(i);
      InsnList insns = one.getInsns();
      insns.forEach(visitor);
    }
  }

  /**
   * Returns an instance that is identical to this one, except that
   * the registers in each instruction are offset by the given
   * amount. Mutability of the result is inherited from the
   * original.
   *
   * @param delta the amount to offset register numbers by
   * @return {@code non-null;} an appropriately-constructed instance
   */
  public BasicBlockList withRegisterOffset(int delta) {
    int sz = size();
    BasicBlockList result = new BasicBlockList(sz);

    for (int i = 0; i < sz; i++) {
      BasicBlock one = (BasicBlock) get0(i);
      if (one != null) {
        result.set(i, one.withRegisterOffset(delta));
      }
    }

    if (isImmutable()) {
      result.setImmutable();
    }

    return result;
  }

  /**
   * Returns a mutable copy of this list.
   *
   * @return {@code non-null;} an appropriately-constructed instance
   */
  public BasicBlockList getMutableCopy() {
    return new BasicBlockList(this);
  }

  /**
   * Gets the preferred successor for the given block. If the block
   * only has one successor, then that is the preferred successor.
   * Otherwise, if the block has a primay successor, then that is
   * the preferred successor. If the block has no successors, then
   * this returns {@code null}.
   *
   * @param block {@code non-null;} the block in question
   * @return {@code null-ok;} the preferred successor, if any
   */
  public BasicBlock preferredSuccessorOf(BasicBlock block) {
    int primarySuccessor = block.getPrimarySuccessor();
    IntList successors = block.getSuccessors();
    int succSize = successors.size();

    switch (succSize) {
      case 0: {
        return null;
      }
      case 1: {
        return labelToBlock(successors.get(0));
      }
    }

    if (primarySuccessor != -1) {
      return labelToBlock(primarySuccessor);
    } else {
      return labelToBlock(successors.get(0));
    }
  }

  /**
   * Compares the catches of two blocks for equality. This includes
   * both the catch types and target labels.
   *
   * @param block1 {@code non-null;} one block to compare
   * @param block2 {@code non-null;} the other block to compare
   * @return {@code true} if the two blocks' non-primary successors
   * are identical
   */
  public boolean catchesEqual(BasicBlock block1, BasicBlock block2) {
    TypeList catches1 = block1.getExceptionHandlerTypes();
    TypeList catches2 = block2.getExceptionHandlerTypes();

    if (!StdTypeList.equalContents(catches1, catches2)) {
      return false;
    }

    IntList succ1 = block1.getSuccessors();
    IntList succ2 = block2.getSuccessors();
    int size = succ1.size(); // Both are guaranteed to be the same size.

    int primary1 = block1.getPrimarySuccessor();
    int primary2 = block2.getPrimarySuccessor();

    if (((primary1 == -1) || (primary2 == -1)) && (primary1 != primary2)) {
      /*
       * For the current purpose, both blocks in question must
       * either both have a primary or both not have a primary to
       * be considered equal, and it turns out here that that's not
       * the case.
       */
      return false;
    }

    for (int i = 0; i < size; i++) {
      int label1 = succ1.get(i);
      int label2 = succ2.get(i);

      if (label1 == primary1) {
        /*
         * It should be the case that block2's primary is at the
         * same index. If not, we consider the blocks unequal for
         * the current purpose.
         */
        if (label2 != primary2) {
          return false;
        }
        continue;
      }

      if (label1 != label2) {
        return false;
      }
    }

    return true;
  }

  /**
   * Instruction visitor class for counting registers used.
   */
  private static class RegCountVisitor implements Insn.Visitor {
    /** {@code >= 0;} register count in-progress */
    private int regCount;

    /**
     * Constructs an instance.
     */
    public RegCountVisitor() {
      regCount = 0;
    }

    /**
     * Gets the register count.
     *
     * @return {@code >= 0;} the count
     */
    public int getRegCount() {
      return regCount;
    }

    /** {@inheritDoc} */
    @Override
    public void visitPlainInsn(PlainInsn insn) {
      visit(insn);
    }

    /** {@inheritDoc} */
    @Override
    public void visitPlainCstInsn(PlainCstInsn insn) {
      visit(insn);
    }

    /** {@inheritDoc} */
    @Override
    public void visitSwitchInsn(SwitchInsn insn) {
      visit(insn);
    }

    /** {@inheritDoc} */
    @Override
    public void visitThrowingCstInsn(ThrowingCstInsn insn) {
      visit(insn);
    }

    /** {@inheritDoc} */
    @Override
    public void visitThrowingInsn(ThrowingInsn insn) {
      visit(insn);
    }

    /** {@inheritDoc} */
    @Override
    public void visitFillArrayDataInsn(FillArrayDataInsn insn) {
      visit(insn);
    }

    /**
     * Helper for all the {@code visit*} methods.
     *
     * @param insn {@code non-null;} instruction being visited
     */
    private void visit(Insn insn) {
      RegisterSpec result = insn.getResult();

      if (result != null) {
        processReg(result);
      }

      RegisterSpecList sources = insn.getSources();
      int sz = sources.size();

      for (int i = 0; i < sz; i++) {
        processReg(sources.get(i));
      }
    }

    /**
     * Processes the given register spec.
     *
     * @param spec {@code non-null;} the register spec
     */
    private void processReg(RegisterSpec spec) {
      int reg = spec.getNextReg();

      if (reg > regCount) {
        regCount = reg;
      }
    }
  }
}