// Copyright (c) 2019, 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.analysis;

import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;

import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.ir.analysis.environmentdependence.ValueGraph;
import com.android.tools.r8.ir.analysis.environmentdependence.ValueGraph.Node;
import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.ir.code.ArrayPut;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InvokeDirect;
import com.android.tools.r8.ir.code.InvokeNewArray;
import com.android.tools.r8.ir.code.InvokeVirtual;
import com.android.tools.r8.ir.code.LogicalBinop;
import com.android.tools.r8.ir.code.NewArrayEmpty;
import com.android.tools.r8.ir.code.NewArrayFilledData;
import com.android.tools.r8.ir.code.NewInstance;
import com.android.tools.r8.ir.code.StaticPut;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.optimize.info.initializer.InstanceInitializerInfo;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.SetUtils;
import com.android.tools.r8.utils.WorkList;
import com.google.common.collect.Sets;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * An analysis that is used to determine if a value may depend on the runtime environment. The
 * primary use case of this analysis is to determine if a class initializer can safely be postponed:
 *
 * <p>If a class initializer does not have any other side effects than the field assignments to the
 * static fields of the enclosing class, and all the values that are being stored into the static
 * fields do not depend on the runtime environment (i.e., the heap, which can be accessed via
 * static-get instructions), then the class initializer can safely be postponed.
 *
 * <p>All compile time constants are independent of the runtime environment. Furthermore, all newly
 * instantiated arrays and objects are independent of the environment, as long as their content
 * (i.e., array elements and field values) does not depend on the runtime environment.
 *
 * <p>Example: Values that are considered to be independent of the runtime environment:
 *
 * <ul>
 *   <li>{@code true}
 *   <li>{@code 42}
 *   <li>{@code "Hello world!"}
 *   <li>{@code new Object()}
 *   <li>{@code new MyClassWithTrivialInitializer("ABC")}
 *   <li>{@code new MyStandardEnum(42, "A")}
 *   <li>{@code new int[] {0, 1, 2}}
 *   <li>{@code new Object[] {new Object(), new MyClassWithTrivialInitializer()}}
 * </ul>
 *
 * <p>Example: Values that are considered to be dependent on the runtime environment:
 *
 * <ul>
 *   <li>{@code argX} (for methods with arguments)
 *   <li>{@code OtherClass.STATIC_FIELD} (reads a value from the runtime environment)
 *   <li>{@code new MyClassWithTrivialInitializer(OtherClass.FIELD)}
 * </ul>
 */
public class ValueMayDependOnEnvironmentAnalysis {

  private final AppView<?> appView;
  private final ProgramMethod context;
  private final DexItemFactory dexItemFactory;
  private final InternalOptions options;

  public ValueMayDependOnEnvironmentAnalysis(AppView<?> appView, IRCode code) {
    this.appView = appView;
    this.context = code.context();
    this.dexItemFactory = appView.dexItemFactory();
    this.options = appView.options();
  }

  public boolean anyValueMayDependOnEnvironment(Iterable<Value> values) {
    ValueGraph graph = new ValueGraph();
    Set<Instruction> consumedInstructions = Sets.newIdentityHashSet();
    Set<Value> mutableValues = Sets.newIdentityHashSet();
    WorkList<Value> worklist = WorkList.newIdentityWorkList(values);
    while (worklist.hasNext()) {
      Value value = worklist.next();
      Value root = value.getAliasedValue();
      Node node = graph.createNodeIfAbsent(root);
      if (root != value) {
        // An alias depends on the environment if the aliased value depends on the environment, thus
        // an edge is added from the alias to the aliased value.
        graph.addDirectedEdge(graph.createNodeIfAbsent(value), node);
      }
      if (!addValueToValueGraph(root, node, graph, consumedInstructions, mutableValues, worklist)) {
        return true;
      }
    }

    // At this point, the graph has been populated with a node for each value of interest, and edges
    // have been added to reflect the dependency. We now attempt to prove that no values depend on
    // environment, starting from the leaves of the graph.
    //
    // First we collapse strongly connected components in the graph. By doing so we will attempt to
    // prove that all values in a strongly connected component are independent of the environment at
    // once.
    graph.mergeStronglyConnectedComponents();

    Set<Node> nodesDependentOnEnvironment = SetUtils.newIdentityHashSet(graph.getNodes());
    while (!nodesDependentOnEnvironment.isEmpty()) {
      Set<Node> newNodesIndependentOfEnvironment = Sets.newIdentityHashSet();
      for (Node node : nodesDependentOnEnvironment) {
        boolean isDependentOfEnvironment =
            node.hasSuccessorThatMatches(
                successor ->
                    nodesDependentOnEnvironment.contains(successor)
                        && !newNodesIndependentOfEnvironment.contains(successor));
        if (!isDependentOfEnvironment) {
          newNodesIndependentOfEnvironment.add(node);
        }
      }
      if (newNodesIndependentOfEnvironment.isEmpty()) {
        return true;
      }
      nodesDependentOnEnvironment.removeAll(newNodesIndependentOfEnvironment);
    }

    // At this point, we have proved that all values in the graph are independent on the
    // environment. However, we still need to prove that they are not mutated between the point
    // where they are defined and all normal exits.
    return anyValueMayBeMutatedBeforeMethodExit(mutableValues, consumedInstructions);
  }

  private boolean addValueToValueGraph(
      Value value,
      Node node,
      ValueGraph graph,
      Set<Instruction> consumedInstructions,
      Set<Value> mutableValues,
      WorkList<Value> worklist) {
    return addConstantValueToValueGraph(value)
        || addArrayValueToValueGraph(
            value, node, graph, consumedInstructions, mutableValues, worklist)
        || addInvokeVirtualValueToValueGraph(
            value, node, graph, consumedInstructions, mutableValues, worklist)
        || addLogicalBinopValueToValueGraph(
            value, node, graph, consumedInstructions, mutableValues, worklist)
        || addNewInstanceValueToValueGraph(
            value, node, graph, consumedInstructions, mutableValues, worklist);
  }

  private boolean addConstantValueToValueGraph(Value value) {
    // Constants do not depend on any other values, thus no edges are added to the graph.
    if (value.isConstant()) {
      return true;
    }
    assert !value.getAliasedValue().isConstant();
    AbstractValue abstractValue = value.getAbstractValue(appView, context);
    if (abstractValue.isSingleConstValue()) {
      return true;
    }
    if (abstractValue.isSingleFieldValue()) {
      DexField fieldReference = abstractValue.asSingleFieldValue().getField();
      DexClass holder = appView.definitionForHolder(fieldReference);
      DexEncodedField field = fieldReference.lookupOnClass(holder);
      if (field != null && field.isEnum()) {
        return true;
      }
    }
    return false;
  }

  private boolean addArrayValueToValueGraph(
      Value value,
      Node node,
      ValueGraph graph,
      Set<Instruction> consumedInstructions,
      Set<Value> mutableValues,
      WorkList<Value> worklist) {
    if (value.isPhi()) {
      // Would need to track the aliases, just give up.
      return false;
    }

    Instruction definition = value.definition;

    // Check that it is a constant array with a known size at this point in the IR.
    if (definition.isInvokeNewArray()) {
      InvokeNewArray invokeNewArray = definition.asInvokeNewArray();
      for (Value argument : invokeNewArray.arguments()) {
        graph.addDirectedEdge(node, graph.createNodeIfAbsent(argument));
        worklist.addIfNotSeen(argument);
      }
    } else if (definition.isNewArrayEmpty()) {
      NewArrayEmpty newArrayEmpty = definition.asNewArrayEmpty();
      Value sizeValue = newArrayEmpty.size();
      graph.addDirectedEdge(node, graph.createNodeIfAbsent(sizeValue));
      worklist.addIfNotSeen(sizeValue);
    } else {
      // Some other array creation.
      return false;
    }

    // Allow array-put and new-array-filled-data instructions that immediately follow the array
    // creation.
    for (Instruction instruction : definition.getBlock().instructionsAfter(definition)) {
      if (instruction.isArrayPut()) {
        ArrayPut arrayPut = instruction.asArrayPut();
        Value array = arrayPut.array().getAliasedValue();
        if (array != value) {
          // This ends the chain of array-put instructions that are allowed immediately after the
          // array creation.
          break;
        }
        graph.addDirectedEdge(node, graph.createNodeIfAbsent(arrayPut.index()));
        worklist.addIfNotSeen(arrayPut.index());
        graph.addDirectedEdge(node, graph.createNodeIfAbsent(arrayPut.value()));
        worklist.addIfNotSeen(arrayPut.value());
      } else if (instruction.isNewArrayFilledData()) {
        NewArrayFilledData newArrayFilledData = instruction.asNewArrayFilledData();
        Value array = newArrayFilledData.src();
        if (array != value) {
          // This ends the chain of array-put instructions that are allowed immediately after the
          // array creation.
          break;
        }
        consumedInstructions.add(instruction);
      } else if (instruction.instructionMayHaveSideEffects(appView, context)) {
        // This ends the chain of array-put instructions that are allowed immediately after the
        // array creation.
        break;
      }
      consumedInstructions.add(instruction);
    }
    mutableValues.add(value);
    return true;
  }

  private boolean addInvokeVirtualValueToValueGraph(
      Value value,
      Node node,
      ValueGraph graph,
      Set<Instruction> consumedInstructions,
      Set<Value> mutableValues,
      WorkList<Value> worklist) {
    if (!value.isDefinedByInstructionSatisfying(Instruction::isInvokeVirtual)) {
      return false;
    }

    InvokeVirtual invoke = value.getDefinition().asInvokeVirtual();
    if (invoke.getInvokedMethod() == dexItemFactory.classMethods.desiredAssertionStatus) {
      // We treat the value from calling MyClass.class.desiredAssertionStatus() as being independent
      // of the environment if MyClass is not pinned.
      return isNonPinnedClassConstant(invoke.getReceiver());
    }

    return false;
  }

  private boolean isNonPinnedClassConstant(Value value) {
    Value root = value.getAliasedValue();
    return root.isDefinedByInstructionSatisfying(Instruction::isConstClass)
        && !appView
            .getKeepInfo()
            .isPinned(root.getDefinition().asConstClass().getType(), appView, options);
  }

  private boolean addLogicalBinopValueToValueGraph(
      Value value,
      Node node,
      ValueGraph graph,
      Set<Instruction> consumedInstructions,
      Set<Value> mutableValues,
      WorkList<Value> worklist) {
    if (!value.isDefinedByInstructionSatisfying(Instruction::isLogicalBinop)) {
      return false;
    }

    // The result of a logical binop depends on the environment if any of the operands does.
    LogicalBinop logicalBinop = value.getDefinition().asLogicalBinop();
    for (Value inValue : logicalBinop.inValues()) {
      graph.addDirectedEdge(node, graph.createNodeIfAbsent(inValue));
      worklist.addIfNotSeen(inValue);
    }

    return true;
  }

  private boolean addNewInstanceValueToValueGraph(
      Value value,
      Node node,
      ValueGraph graph,
      Set<Instruction> consumedInstructions,
      Set<Value> mutableValues,
      WorkList<Value> worklist) {
    if (!value.isDefinedByInstructionSatisfying(Instruction::isNewInstance)) {
      return false;
    }

    NewInstance newInstance = value.definition.asNewInstance();
    DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(newInstance.clazz));
    if (clazz == null) {
      return false;
    }

    // Find the single constructor invocation.
    InvokeDirect constructorInvoke = newInstance.getUniqueConstructorInvoke(dexItemFactory);
    if (constructorInvoke == null || constructorInvoke.getInvokedMethod().holder != clazz.type) {
      // Didn't find a (valid) constructor invocation, give up.
      return false;
    }

    // Check that it is a trivial initializer (otherwise, the constructor could do anything).
    DexEncodedMethod constructor = clazz.lookupMethod(constructorInvoke.getInvokedMethod());
    if (constructor == null) {
      return false;
    }

    InstanceInitializerInfo initializerInfo =
        constructor.getOptimizationInfo().getInstanceInitializerInfo(constructorInvoke);

    List<DexEncodedField> fields = clazz.getDirectAndIndirectInstanceFields(appView);
    if (!fields.isEmpty()) {
      if (initializerInfo.instanceFieldInitializationMayDependOnEnvironment()) {
        return false;
      }

      // Check that none of the arguments to the constructor depend on the environment.
      for (int i = 1; i < constructorInvoke.arguments().size(); i++) {
        Value argument = constructorInvoke.getArgument(i);
        graph.addDirectedEdge(node, graph.createNodeIfAbsent(argument));
        worklist.addIfNotSeen(argument);
      }

      // Mark this value as mutable if it has a non-final field.
      boolean hasNonFinalField = false;
      for (DexEncodedField field : fields) {
        if (!field.isFinal()) {
          hasNonFinalField = true;
          break;
        }
      }
      if (hasNonFinalField) {
        mutableValues.add(value);
      }
    }

    if (!initializerInfo.mayHaveOtherSideEffectsThanInstanceFieldAssignments()) {
      consumedInstructions.add(constructorInvoke);
    }

    return true;
  }

  private boolean anyValueMayBeMutatedBeforeMethodExit(
      Set<Value> values, Set<Instruction> whitelist) {
    Set<BasicBlock> initialBlocks = Sets.newIdentityHashSet();
    for (Value value : values) {
      assert !value.isPhi();
      initialBlocks.add(value.definition.getBlock());
    }
    Map<BasicBlock, TrackedValuesState> blockExitStates = new IdentityHashMap<>();
    Deque<BasicBlock> worklist = new ArrayDeque<>(initialBlocks);
    while (!worklist.isEmpty()) {
      BasicBlock block = worklist.removeFirst();
      TrackedValuesState state = computeBlockEntryState(block, blockExitStates);
      boolean changed = false;
      for (Instruction instruction : block.getInstructions()) {
        if (whitelist.contains(instruction)) {
          continue;
        }
        if (instruction.isStaticPut()) {
          StaticPut staticPut = instruction.asStaticPut();
          if (state.isTrackingValue(staticPut.value())) {
            changed |= state.recordTrackedValueHasEscaped();
          }
          if (state.hasTrackedValueEscaped()) {
            DexType holder = staticPut.getField().holder;
            if (holder.classInitializationMayHaveSideEffectsInContext(appView, context)) {
              return true;
            }
          }
          continue;
        }
        if (instruction.instructionMayTriggerMethodInvocation(appView, context)) {
          if (instruction.hasInValueThatMatches(state::isTrackingValue)) {
            changed |= state.recordTrackedValueHasEscaped();
          }
          if (state.hasTrackedValueEscaped()
              && instruction.instructionMayHaveSideEffects(appView, context)) {
            return true;
          }
        }
        if (instruction.hasOutValue() && values.contains(instruction.outValue())) {
          changed |= state.startTrackingValue(instruction.outValue());
        }
      }
      blockExitStates.put(block, state);
      if (changed) {
        worklist.addAll(block.getSuccessors());
      }
    }
    return false;
  }

  private TrackedValuesState computeBlockEntryState(
      BasicBlock block, Map<BasicBlock, TrackedValuesState> states) {
    TrackedValuesState state = new TrackedValuesState();
    for (BasicBlock predecessor : block.getPredecessors()) {
      state.add(states.getOrDefault(predecessor, TrackedValuesState.empty()));
    }
    return state;
  }

  static class TrackedValuesState {

    private static final TrackedValuesState EMPTY = new TrackedValuesState();

    boolean hasTrackedValueEscaped;
    Set<Value> trackedValues = Sets.newIdentityHashSet();

    public static TrackedValuesState empty() {
      return EMPTY;
    }

    public void add(TrackedValuesState state) {
      hasTrackedValueEscaped |= state.hasTrackedValueEscaped;
      trackedValues.addAll(state.trackedValues);
    }

    public boolean hasTrackedValueEscaped() {
      return hasTrackedValueEscaped;
    }

    public boolean isTrackingValue(Value value) {
      return trackedValues.contains(value);
    }

    public boolean recordTrackedValueHasEscaped() {
      if (hasTrackedValueEscaped) {
        return false;
      }
      hasTrackedValueEscaped = true;
      return true;
    }

    public boolean startTrackingValue(Value value) {
      return trackedValues.add(value);
    }
  }
}