// Copyright (c) 2016, the R8 project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.code;

import com.android.tools.r8.cf.TypeVerificationHelper;
import com.android.tools.r8.errors.CompilationError;
import com.android.tools.r8.errors.InvalidDebugInfoException;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.BasicBlock.EdgeType;
import com.android.tools.r8.ir.conversion.IRBuilder;
import com.android.tools.r8.ir.conversion.TypeConstraintResolver;
import com.android.tools.r8.origin.Origin;
import com.android.tools.r8.utils.CfgPrinter;
import com.android.tools.r8.utils.DequeUtils;
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.Reporter;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.StringUtils;
import com.google.common.collect.Sets;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.function.Predicate;

public class Phi extends Value implements InstructionOrPhi {

  public enum RegisterReadType {
    NORMAL,
    DEBUG,
  }

  private final BasicBlock block;
  private final List<Value> operands = new ArrayList<>();
  private RegisterReadType readType;
  private boolean isStackPhi;

  // Trivial phis are eliminated during IR construction. When a trivial phi is eliminated
  // we need to update all references to it. A phi can be referenced from phis, instructions
  // and current definition mappings. This list contains the current definitions mappings that
  // contain this phi.
  private List<Map<Integer, Value>> definitionUsers = new ArrayList<>();

  public Phi(
      int number,
      BasicBlock block,
      TypeElement type,
      DebugLocalInfo local,
      RegisterReadType readType) {
    super(number, type, local);
    this.block = block;
    this.readType = readType;
    block.addPhi(this);
  }

  @Override
  public boolean isDefinedByInstructionSatisfying(Predicate<Instruction> predicate) {
    return false;
  }

  @Override
  public boolean isPhi() {
    return true;
  }

  @Override
  public Phi asPhi() {
    return this;
  }

  @Override
  public BasicBlock getBlock() {
    return block;
  }

  @Override
  public void constrainType(
      ValueTypeConstraint constraint, DexMethod method, Origin origin, Reporter reporter) {
    if (readType == RegisterReadType.DEBUG) {
      abortOnInvalidDebugInfo(constraint);
    }
    super.constrainType(constraint, method, origin, reporter);
  }

  private void abortOnInvalidDebugInfo(ValueTypeConstraint constraint) {
    if (constrainedType(constraint) == null) {
      // If the phi has been requested from local info, throw out locals and retry compilation.
      throw new InvalidDebugInfoException(
          "Type information in locals-table is inconsistent."
              + " Cannot constrain type: "
              + type
              + " for value: "
              + this
              + " by constraint "
              + constraint
              + ".");
    }
  }

  public void addOperands(IRBuilder builder, int register) {
    // Phi operands are only filled in once to complete the phi. Some phis are incomplete for a
    // period of time to break cycles. When the cycle has been resolved they are completed
    // exactly once by adding the operands.
    assert operands.isEmpty();
    if (block.getPredecessors().size() == 0) {
      throwUndefinedValueError();
    }

    ValueTypeConstraint readConstraint = TypeConstraintResolver.constraintForType(type);
    List<Value> operands = new ArrayList<>(block.getPredecessors().size());
    for (BasicBlock pred : block.getPredecessors()) {
      EdgeType edgeType = pred.getEdgeType(block);
      Value operand = builder.readRegister(register, readConstraint, pred, edgeType, readType);
      operands.add(operand);
    }

    if (readType == RegisterReadType.DEBUG) {
      for (Value operand : operands) {
        TypeElement type = operand.getType();
        ValueTypeConstraint constraint = TypeConstraintResolver.constraintForType(type);
        abortOnInvalidDebugInfo(constraint);
      }
    }

    for (Value operand : operands) {
      builder.constrainType(operand, readConstraint);
      appendOperand(operand);
    }
    removeTrivialPhi(builder, null);
  }

  public void addOperands(List<Value> operands) {
    addOperands(operands, true);
  }

  public void addOperands(List<Value> operands, boolean removeTrivialPhi) {
    // Phi operands are only filled in once to complete the phi. Some phis are incomplete for a
    // period of time to break cycles. When the cycle has been resolved they are completed
    // exactly once by adding the operands.
    assert this.operands.isEmpty();
    if (operands.size() == 0) {
      throwUndefinedValueError();
    }
    for (Value operand : operands) {
      appendOperand(operand);
    }
    if (removeTrivialPhi) {
      removeTrivialPhi();
    }
  }

  @Override
  public void markNonDebugLocalRead() {
    readType = RegisterReadType.NORMAL;
  }

  private void throwUndefinedValueError() {
    throw new CompilationError(
        "Undefined value encountered during compilation. "
            + "This is typically caused by invalid dex input that uses a register "
            + "that is not defined on all control-flow paths leading to the use.");
  }

  public void appendOperand(Value operand) {
    operands.add(operand);
    operand.addPhiUser(this);
  }

  public Value getOperand(int predIndex) {
    return operands.get(predIndex);
  }

  public List<Value> getOperands() {
    return operands;
  }

  public void removeOperand(int index) {
    operands.get(index).removePhiUser(this);
    operands.remove(index);
  }

  public void removeOperandsByIndex(List<Integer> operandsToRemove) {
    if (operandsToRemove.isEmpty()) {
      return;
    }
    List<Value> copy = new ArrayList<>(operands);
    operands.clear();
    int current = 0;
    for (int i : operandsToRemove) {
      operands.addAll(copy.subList(current, i));
      copy.get(i).removePhiUser(this);
      current = i + 1;
    }
    operands.addAll(copy.subList(current, copy.size()));
  }

  public void replaceOperandAt(int predIndex, Value newValue) {
    Value current = operands.get(predIndex);
    operands.set(predIndex, newValue);
    newValue.addPhiUser(this);
    current.removePhiUser(this);
  }

  void replaceOperand(Value current, Value newValue) {
    for (int i = 0; i < operands.size(); i++) {
      if (operands.get(i) == current) {
        operands.set(i, newValue);
        newValue.addPhiUser(this);
      }
    }
  }

  public boolean isTrivialPhi() {
    Value same = null;
    for (Value op : operands) {
      if (op == same || op == this) {
        // Have only seen one value other than this.
        continue;
      }
      if (same != null) {
        // Merged at least two values and is therefore not trivial.
        return false;
      }
      same = op;
    }
    return true;
  }

  public boolean removeTrivialPhi() {
    return removeTrivialPhi(null, null);
  }

  public boolean removeTrivialPhi(IRBuilder builder, Set<Value> affectedValues) {
    Value same = null;
    for (Value op : operands) {
      if (op == same || op == this) {
        // Have only seen one value other than this.
        continue;
      }
      if (same != null) {
        // Merged at least two values and is therefore not trivial.
        assert !isTrivialPhi();
        return false;
      }
      same = op;
    }
    assert isTrivialPhi();
    if (same == null) {
      // When doing if-simplification we remove blocks and we can end up with cyclic phis
      // of the form v1 = phi(v1, v1) in dead blocks. If we encounter that case we just
      // leave the phi in there and check at the end that there are no trivial phis.
      return false;
    }
    if (getLocalInfo() != same.getLocalInfo()) {
      if (getLocalInfo() == null) {
        // The to-be replaced phi has no local info, so all is OK.
      } else if (same.getLocalInfo() == null) {
        // Move the local info to the replacement phi.
        same.setLocalInfo(getLocalInfo());
      } else {
        // The phi's define distinct locals and are not trivially the same.
        assert hasLocalInfo() && same.hasLocalInfo();
        return false;
      }
    }
    // Ensure that the value that replaces this phi is constrained to the type of this phi.
    if (builder != null && type.isPreciseType() && !type.isBottom()) {
      builder.constrainType(same, ValueTypeConstraint.fromTypeLattice(type));
    }
    if (affectedValues != null) {
      affectedValues.addAll(this.affectedValues());
    }
    // Removing this phi, so get rid of it as a phi user from all of the operands to avoid
    // recursively getting back here with the same phi. If the phi has itself as an operand
    // that also removes the self-reference.
    for (Value op : operands) {
      op.removePhiUser(this);
    }
    // If IR construction is taking place, update the definition users.
    if (definitionUsers != null) {
      for (Map<Integer, Value> user : definitionUsers) {
        for (Entry<Integer, Value> entry : user.entrySet()) {
          if (entry.getValue() == this) {
            entry.setValue(same);
            if (same.isPhi()) {
              same.asPhi().addDefinitionsUser(user);
            }
          }
        }
      }
    }
    {
      Set<Phi> phiUsersToSimplify = uniquePhiUsers();
      // Replace this phi with the unique value in all users.
      replaceUsers(same);
      // Try to simplify phi users that might now have become trivial.
      for (Phi user : phiUsersToSimplify) {
        user.removeTrivialPhi(builder, affectedValues);
      }
    }
    // Get rid of the phi itself.
    block.removePhi(this);
    return true;
  }

  public void removeDeadPhi() {
    // First, make sure it is indeed dead, i.e., no non-phi users.
    assert !hasUsers();
    // Then, manually clean up this from all of the operands.
    for (Value operand : getOperands()) {
      operand.removePhiUser(this);
    }
    // And remove it from the containing block.
    getBlock().removePhi(this);
  }

  public String printPhi() {
    StringBuilder builder = new StringBuilder();
    builder.append("v");
    builder.append(number);
    if (hasLocalInfo()) {
      builder.append("(").append(getLocalInfo()).append(")");
    }
    builder.append(" <- phi");
    StringUtils.append(builder, ListUtils.map(operands, Value::toString));
    builder.append(" : ").append(getType());
    return builder.toString();
  }

  public void print(CfgPrinter printer) {
    int uses = numberOfPhiUsers() + numberOfUsers();
    printer
        .print("0 ")                 // bci
        .append(uses)                // use
        .append(" v").append(number) // tid
        .append(" Phi");
    for (Value operand : operands) {
      printer.append(" v").append(operand.number);
    }
  }

  public void addDefinitionsUser(Map<Integer, Value> currentDefinitions) {
    definitionUsers.add(currentDefinitions);
  }

  public void removeDefinitionsUser(Map<Integer, Value> currentDefinitions) {
    definitionUsers.remove(currentDefinitions);
  }

  public void clearDefinitionsUsers() {
    definitionUsers = null;
  }

  @Override
  public boolean isConstant() {
    return false;
  }

  @Override
  public boolean isValueOnStack() {
    assert verifyIsStackPhi(Sets.newIdentityHashSet());
    return isStackPhi;
  }

  public void setIsStackPhi(boolean isStackPhi) {
    this.isStackPhi = isStackPhi;
  }

  private boolean verifyIsStackPhi(Set<Phi> seenPhis) {
    seenPhis.add(this);
    operands.forEach(
        v -> {
          if (v.isPhi()) {
            assert seenPhis.contains(v) || v.asPhi().verifyIsStackPhi(seenPhis);
          } else {
            assert v.isValueOnStack() == isStackPhi;
          }
        });
    return true;
  }

  @Override
  public boolean needsRegister() {
    return !isValueOnStack();
  }

  public boolean usesValueOneTime(Value usedValue) {
    return operands.indexOf(usedValue) == operands.lastIndexOf(usedValue);
  }

  public DexType computeVerificationType(AppView<?> appView, TypeVerificationHelper helper) {
    assert outType().isObject();
    Set<DexType> operandTypes = new HashSet<>(operands.size());
    for (Value operand : operands) {
      DexType operandType = helper.getDexType(operand);
      if (operandType != null) {
        operandTypes.add(operandType);
      }
    }
    return helper.join(operandTypes);
  }

  // Type of phi(v1, v2, ..., vn) is the least upper bound of all those n operands.
  public TypeElement computePhiType(AppView<?> appView) {
    TypeElement result = TypeElement.getBottom();
    for (Value operand : getOperands()) {
      result = result.join(operand.getType(), appView);
    }
    return result;
  }

  @Override
  public TypeElement getDynamicUpperBoundType(
      AppView<? extends AppInfoWithClassHierarchy> appView) {
    Set<Phi> reachablePhis = SetUtils.newIdentityHashSet(this);
    Deque<Phi> worklist = DequeUtils.newArrayDeque(this);
    while (!worklist.isEmpty()) {
      Phi phi = worklist.removeFirst();
      assert reachablePhis.contains(phi);
      for (Value operand : phi.getOperands()) {
        Phi candidate = operand.getAliasedValue().asPhi();
        if (candidate != null && reachablePhis.add(candidate)) {
          worklist.addLast(candidate);
        }
      }
    }
    Set<Value> visitedOperands = Sets.newIdentityHashSet();
    TypeElement result = TypeElement.getBottom();
    for (Phi phi : reachablePhis) {
      for (Value operand : phi.getOperands()) {
        if (!operand.getAliasedValue().isPhi() && visitedOperands.add(operand)) {
          result = result.join(operand.getDynamicUpperBoundType(appView), appView);
        }
      }
    }
    if (getType().isReferenceType() && getType().isDefinitelyNotNull()) {
      return result.asReferenceType().asMeetWithNotNull();
    }
    return result;
  }

  // TODO(b/169120386) This class is added to ensure we do not narrow or widen the type of phi's
  //  in D8 when having stack map information. We do allow for narrowing on nullable information.
  //  It should be removed when we are certain to never widen or narrowing phi's in D8.
  public static class StackMapPhi extends Phi {

    public StackMapPhi(
        int number,
        BasicBlock block,
        TypeElement type,
        DebugLocalInfo local,
        RegisterReadType readType) {
      super(number, block, type, local, readType);
    }

    @Override
    public DexType computeVerificationType(AppView<?> appView, TypeVerificationHelper helper) {
      assert !appView.enableWholeProgramOptimizations();
      if (type.isPrimitiveType()) {
        return type.asPrimitiveType().toDexType(appView.dexItemFactory());
      } else if (type.isArrayType()) {
        return type.asArrayType().toDexType(appView.dexItemFactory());
      } else {
        assert type.isClassType();
        return type.asClassType().getClassType();
      }
    }

    @Override
    public TypeElement computePhiType(AppView<?> appView) {
      assert !appView.enableWholeProgramOptimizations();
      if (type.isPrimitiveType()) {
        return type;
      }
      assert type.isReferenceType();
      Nullability nullability = Nullability.bottom();
      for (Value operand : getOperands()) {
        nullability = nullability.join(operand.type.nullability());
      }
      return type.asReferenceType().getOrCreateVariant(nullability);
    }

    @Override
    public boolean isStackMapPhi() {
      return true;
    }
  }
}