// Copyright (c) 2022, 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.optimize.string;

import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.optimize.string.StringBuilderAction.AppendWithNewConstantString;
import com.android.tools.r8.ir.optimize.string.StringBuilderAction.RemoveStringBuilderAction;
import com.android.tools.r8.ir.optimize.string.StringBuilderAction.ReplaceByConstantString;
import com.android.tools.r8.ir.optimize.string.StringBuilderAction.ReplaceByExistingString;
import com.android.tools.r8.ir.optimize.string.StringBuilderAction.ReplaceByStringConcat;
import com.android.tools.r8.ir.optimize.string.StringBuilderNode.AppendNode;
import com.android.tools.r8.ir.optimize.string.StringBuilderNode.ImplicitToStringNode;
import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitNode;
import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitOrAppendNode;
import com.android.tools.r8.ir.optimize.string.StringBuilderNode.NewInstanceNode;
import com.android.tools.r8.ir.optimize.string.StringBuilderNode.StringBuilderInstruction;
import com.android.tools.r8.ir.optimize.string.StringBuilderNode.ToStringNode;
import com.android.tools.r8.utils.WorkList;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * StringBuilderNodeMuncher is a classic munching algorithm that will try to remove nodes on string
 * builders by looking at small view of it {@link PeepholePattern}. If a pattern can be optimized
 * the graph will be updated in place and if the IR needs to be updated, an action will be added.
 */
class StringBuilderNodeMuncher {

  static class MunchingState {

    private final Map<Instruction, StringBuilderAction> actions;
    private final StringBuilderOracle oracle;

    // The below state can all be computed by searching the graph but are tracked here to improve
    // performance.
    private final Set<StringBuilderNode> escaping;
    private final Set<StringBuilderNode> inspectingCapacity;
    private final Set<StringBuilderNode> looping;
    private final Map<StringBuilderNode, Set<StringBuilderNode>> materializingInstructions;
    private final Map<StringBuilderNode, NewInstanceNode> newInstances;
    private final Map<Value, String> optimizedStrings = new IdentityHashMap<>();

    MunchingState(
        Map<Instruction, StringBuilderAction> actions,
        Set<StringBuilderNode> escaping,
        Set<StringBuilderNode> inspectingCapacity,
        Set<StringBuilderNode> looping,
        Map<StringBuilderNode, Set<StringBuilderNode>> materializingInstructions,
        Map<StringBuilderNode, NewInstanceNode> newInstances,
        StringBuilderOracle oracle) {
      this.actions = actions;
      this.escaping = escaping;
      this.inspectingCapacity = inspectingCapacity;
      this.looping = looping;
      this.materializingInstructions = materializingInstructions;
      this.newInstances = newInstances;
      this.oracle = oracle;
    }

    public NewInstanceNode getNewInstanceNode(StringBuilderNode root) {
      return newInstances.get(root);
    }

    public boolean isLooping(StringBuilderNode root) {
      return looping.contains(root);
    }

    public boolean isEscaping(StringBuilderNode root) {
      return escaping.contains(root);
    }

    public boolean isInspecting(StringBuilderNode root) {
      return inspectingCapacity.contains(root);
    }
  }

  private interface PeepholePattern {

    boolean optimize(
        StringBuilderNode root, StringBuilderNode currentNode, MunchingState munchingState);
  }

  /**
   * This peephole will try to optimize two sequential appends:
   *
   * <pre>
   * append("foo") -> append("bar") =>
   * append("foobar")
   *
   * or
   *
   * init("foo") -> append("bar") =>
   * init("foobar")
   * </pre>
   */
  private static class MunchAppends implements PeepholePattern {

    @Override
    public boolean optimize(
        StringBuilderNode root, StringBuilderNode currentNode, MunchingState munchingState) {
      AppendNode appendNode = currentNode.asAppendNode();
      if (appendNode == null || !appendNode.hasSinglePredecessor()) {
        return false;
      }
      InitOrAppendNode previous = currentNode.getSinglePredecessor().asInitOrAppend();
      if (previous == null || !previous.hasSingleSuccessor()) {
        return false;
      }
      // The capacity changes based on the init call (on JVM it adds 16 to length of input).
      if (previous.isInitNode() && munchingState.inspectingCapacity.contains(root)) {
        return false;
      }
      String currentConstantArgument = getConstantArgumentForNode(appendNode, munchingState);
      if (currentConstantArgument == null) {
        return false;
      }
      String previousConstantArgument = getConstantArgumentForNode(previous, munchingState);
      if (previousConstantArgument == null) {
        return false;
      }
      String newConstant = previousConstantArgument + currentConstantArgument;
      previous.setConstantArgument(newConstant);
      munchingState.actions.put(
          previous.getInstruction(), new AppendWithNewConstantString(newConstant));
      munchingState.actions.put(
          appendNode.getInstruction(), RemoveStringBuilderAction.getInstance());
      currentNode.removeNode();
      return true;
    }
  }

  /**
   * This peephole will try to remove toString nodes and replace by a constant string:
   *
   * <pre>
   * newInstance -> init("foo") -> toString() => newInstance -> init("foo") -> append("bar")
   * actions: [toString() => ReplaceByConstantString("foo")]
   * </pre>
   *
   * <p>If the node is an implicitToString, we update the append of another builder to have the new
   * constant value directly. If not, we keep track of the outValue toString() being replaced by a
   * constant by updating {@code MunchingState.optimizedStrings}
   */
  private static class MunchToString implements PeepholePattern {

    @Override
    public boolean optimize(
        StringBuilderNode originalRoot,
        StringBuilderNode currentNode,
        MunchingState munchingState) {
      if (munchingState.isEscaping(originalRoot) || munchingState.isInspecting(originalRoot)) {
        return false;
      }
      if (!currentNode.isToStringNode() && !currentNode.isImplicitToStringNode()) {
        return false;
      }
      NewInstanceNode newInstanceNode = munchingState.getNewInstanceNode(originalRoot);
      if (newInstanceNode == null || !newInstanceNode.hasSingleSuccessor()) {
        return false;
      }
      InitNode init = newInstanceNode.getSingleSuccessor().asInitNode();
      if (init == null || !init.hasSingleSuccessor()) {
        return false;
      }
      if (!currentNode.hasSinglePredecessor() || currentNode.getSinglePredecessor() != init) {
        return false;
      }
      String initConstantArgument = getConstantArgumentForNode(init, munchingState);
      if (initConstantArgument == null) {
        return false;
      }
      // If the string builder dependency is directly given to another string builder, there is
      // no toString() but an append with this string builder as argument.
      if (currentNode.isToStringNode()) {
        ToStringNode toStringNode = currentNode.asToStringNode();
        munchingState.actions.put(
            toStringNode.getInstruction(), new ReplaceByConstantString(initConstantArgument));
        String oldValue =
            munchingState.optimizedStrings.put(
                toStringNode.getInstruction().outValue(), initConstantArgument);
        assert oldValue == null;
      } else {
        assert currentNode.isImplicitToStringNode();
        ImplicitToStringNode implicitToStringNode = currentNode.asImplicitToStringNode();
        InitOrAppendNode initOrAppend = implicitToStringNode.getInitOrAppend();
        initOrAppend.setConstantArgument(initConstantArgument);
        munchingState.actions.put(
            initOrAppend.getInstruction(), new AppendWithNewConstantString(initConstantArgument));
      }
      munchingState.materializingInstructions.get(originalRoot).remove(currentNode);
      currentNode.removeNode();
      return true;
    }
  }

  /**
   * This peephole will try to remove toString nodes and replace by an invoke to String.concat:
   *
   * <pre>
   * newInstance -> init(notNull(string)) -> append(notNull(otherString)) -> toString() =>
   * newInstance -> init(notNull(string)) -> append(otherString)
   * actions: [toString() => string.concat(otherString)]
   * </pre>
   *
   * <p>This pattern only triggers when a constant munching of toString could happen.
   */
  private static class MunchToStringIntoStringConcat implements PeepholePattern {

    @Override
    public boolean optimize(
        StringBuilderNode originalRoot,
        StringBuilderNode currentNode,
        MunchingState munchingState) {
      if (munchingState.isEscaping(originalRoot) || munchingState.isInspecting(originalRoot)) {
        return false;
      }
      // TODO(b/129200243): Handle implicit tostring nodes.
      if (!currentNode.isToStringNode() || !currentNode.hasSinglePredecessor()) {
        return false;
      }
      StringBuilderNode root = findFirstNonSentinelRoot(originalRoot);
      if (!root.isNewInstanceNode() || !root.hasSingleSuccessor()) {
        return false;
      }
      InitOrAppendNode firstNode = root.getSingleSuccessor().asInitNode();
      if (firstNode == null || !firstNode.hasSingleSuccessor()) {
        return false;
      }
      if (firstNode.asInitNode().isConstructorInvokeSideEffectFree(munchingState.oracle)
          && "".equals(firstNode.getConstantArgument())
          && firstNode.hasSingleSuccessor()) {
        firstNode = firstNode.getSingleSuccessor().asAppendNode();
        if (firstNode == null
            || !firstNode.hasSinglePredecessor()
            || !firstNode.hasSingleSuccessor()) {
          return false;
        }
      }
      // We cannot String.concat or return the string safely when it is not constant and maybe null.
      if (!firstNode.hasConstantOrNonConstantArgument()) {
        return false;
      }
      List<InitOrAppendNode> initOrAppends = Lists.newArrayList(firstNode);
      if (currentNode.getSinglePredecessor() != firstNode) {
        AppendNode appendAfterFirstNode = firstNode.getSingleSuccessor().asAppendNode();
        AppendNode appendBeforeToString = currentNode.getSinglePredecessor().asAppendNode();
        if (appendAfterFirstNode == null
            || appendAfterFirstNode != appendBeforeToString
            || !appendAfterFirstNode.hasConstantOrNonConstantArgument()) {
          return false;
        }
        initOrAppends.add(appendAfterFirstNode);
      }
      // Check that all values are not constant otherwise we can compute the constant value and
      // replace all entirely.
      if (Iterables.all(initOrAppends, InitOrAppendNode::hasConstantArgument)) {
        return false;
      }
      // Replace with the string itself.
      Instruction currentInstruction = currentNode.asToStringNode().getInstruction();
      InitOrAppendNode first = initOrAppends.get(0);
      if (initOrAppends.size() == 1) {
        munchingState.actions.put(
            currentInstruction, new ReplaceByExistingString(first.getNonConstantArgument()));
      } else {
        InitOrAppendNode second = initOrAppends.get(1);
        ReplaceByStringConcat concatAction;
        if (first.hasConstantArgument()) {
          concatAction =
              ReplaceByStringConcat.replaceByNewConstantConcatValue(
                  first.getConstantArgument(), second.getNonConstantArgument());
        } else if (second.hasConstantArgument()) {
          concatAction =
              ReplaceByStringConcat.replaceByValueConcatNewConstant(
                  first.getNonConstantArgument(), second.getConstantArgument());
        } else {
          concatAction =
              ReplaceByStringConcat.replaceByValues(
                  first.getNonConstantArgument(), second.getNonConstantArgument());
        }
        munchingState.actions.put(currentInstruction, concatAction);
      }
      munchingState.materializingInstructions.get(originalRoot).remove(currentNode);
      currentNode.removeNode();
      return true;
    }
  }

  private static String getConstantArgumentForNode(
      InitOrAppendNode node, MunchingState munchingState) {
    if (node.hasConstantArgument()) {
      return node.getConstantArgument();
    }
    return getOptimizedConstantArgument(node, munchingState);
  }

  private static String getOptimizedConstantArgument(
      StringBuilderInstruction node, MunchingState munchingState) {
    List<Value> inValues = node.getInstruction().inValues();
    if (inValues.size() != 2) {
      return null;
    }
    return munchingState.optimizedStrings.get(inValues.get(1).getAliasedValue());
  }

  /**
   * This pattern tries to remove nodes that are no longer needed. An example is when a toString is
   * materialized, and append may now not be observable and can be removed. This pattern tries to
   * remove as many nodes as possibly by continuing to remove predecessor nodes. This is not
   * necessary for correctness but since the overall munching algorithm runs over successors,
   * removing predecessors directly here saves cycles.
   */
  private static class MunchNonMaterializing implements PeepholePattern {

    @Override
    public boolean optimize(
        StringBuilderNode root, StringBuilderNode currentNode, MunchingState munchingState) {
      boolean removedAnyNodes = false;
      boolean removeNode;
      boolean isEscaping = munchingState.escaping.contains(root);
      while (currentNode != null) {
        // Remove appends if the string builder do not escape, is not inspected or materialized
        // and if it is not part of a loop.
        removeNode = false;
        if (currentNode.isSplitReferenceNode() && !munchingState.isLooping(root)) {
          removeNode = currentNode.getSuccessors().isEmpty() || currentNode.hasSinglePredecessor();
        } else if (currentNode.isAppendNode() && !isEscaping) {
          AppendNode appendNode = currentNode.asAppendNode();
          boolean canRemoveIfNoInspectionOrMaterializing =
              !munchingState.inspectingCapacity.contains(root)
                  && munchingState.materializingInstructions.get(root).isEmpty();
          boolean canRemoveIfLastAndNoLoop =
              !isLoopingOnPath(root, currentNode, munchingState)
                  && currentNode.getSuccessors().isEmpty();
          if (canRemoveIfNoInspectionOrMaterializing
              && canRemoveIfLastAndNoLoop
              && !munchingState.oracle.canObserveStringBuilderCall(
                  currentNode.asAppendNode().getInstruction())) {
            munchingState.actions.put(
                appendNode.getInstruction(), RemoveStringBuilderAction.getInstance());
            removeNode = true;
          }
        } else if (currentNode.isInitNode()
            && currentNode.hasSinglePredecessor()
            && currentNode.getSinglePredecessor().isNewInstanceNode()
            && currentNode.getSuccessors().isEmpty()
            && !isEscaping
            && !munchingState.oracle.canObserveStringBuilderCall(
                currentNode.asInitNode().getInstruction())) {
          removeNode = true;
        }
        if (!removeNode) {
          return false;
        } else {
          removedAnyNodes = true;
          currentNode.removeNode();
          if (currentNode.isStringBuilderInstructionNode()) {
            munchingState.actions.put(
                currentNode.asStringBuilderInstructionNode().getInstruction(),
                RemoveStringBuilderAction.getInstance());
          }
          currentNode =
              currentNode.hasSinglePredecessor() ? currentNode.getSinglePredecessor() : null;
        }
      }
      return removedAnyNodes;
    }

    private boolean isLoopingOnPath(
        StringBuilderNode root, StringBuilderNode currentNode, MunchingState munchingState) {
      if (!munchingState.looping.contains(root)) {
        return false;
      }
      WorkList<StringBuilderNode> workList = WorkList.newIdentityWorkList(currentNode);
      boolean seenNewInstance = false;
      while (workList.hasNext()) {
        StringBuilderNode next = workList.next();
        if (next.isNewInstanceNode()) {
          seenNewInstance = true;
        }
        if (next.isLoopNode()) {
          // If we have seen a new instance and there is only a single successor for the loop
          // the instance is always created inside the body.
          return !seenNewInstance || !next.hasSingleSuccessor();
        }
        workList.addIfNotSeen(next.getPredecessors());
      }
      return false;
    }
  }

  private static final PeepholePattern[] peepholePatterns =
      new PeepholePattern[] {
        new MunchAppends(),
        new MunchToString(),
        new MunchToStringIntoStringConcat(),
        new MunchNonMaterializing()
      };

  static boolean optimize(
      StringBuilderNode root, StringBuilderNode currentNode, MunchingState munchingState) {
    if (currentNode.isDead()) {
      return false;
    }
    for (PeepholePattern peepholePattern : peepholePatterns) {
      if (peepholePattern.optimize(root, currentNode, munchingState)) {
        return true;
      }
    }
    return false;
  }
}