// 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.conversion;

import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
import static com.android.tools.r8.naming.IdentifierNameStringUtils.isClassNameValue;

import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.ir.analysis.type.ClassTypeElement;
import com.android.tools.r8.ir.analysis.type.PrimitiveTypeElement;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.ConstString;
import com.android.tools.r8.ir.code.Goto;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.If.Type;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.IntSwitch;
import com.android.tools.r8.ir.code.InvokeVirtual;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.StringSwitch;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.naming.IdentifierNameStringMarker;
import com.android.tools.r8.utils.ArrayUtils;
import com.android.tools.r8.utils.SetUtils;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
import com.google.common.collect.Streams;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceRBTreeMap;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
import java.io.UTFDataFormatException;
import java.util.LinkedHashMap;
import java.util.ListIterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class StringSwitchRemover {

  private final AppView<?> appView;
  private final IdentifierNameStringMarker identifierNameStringMarker;
  private final ClassTypeElement stringType;

  StringSwitchRemover(AppView<?> appView, IdentifierNameStringMarker identifierNameStringMarker) {
    this.appView = appView;
    this.identifierNameStringMarker = identifierNameStringMarker;
    this.stringType = TypeElement.stringClassType(appView, definitelyNotNull());
  }

  public void run(IRCode code) {
    if (!code.metadata().mayHaveStringSwitch()) {
      assert Streams.stream(code.instructions()).noneMatch(Instruction::isStringSwitch);
      return;
    }

    if (!prepareForStringSwitchRemoval(code)) {
      return;
    }

    Set<BasicBlock> newBlocksWithStrings = Sets.newIdentityHashSet();

    ListIterator<BasicBlock> blockIterator = code.listIterator();
    while (blockIterator.hasNext()) {
      BasicBlock block = blockIterator.next();
      StringSwitch theSwitch = block.exit().asStringSwitch();
      if (theSwitch != null) {
        try {
          SingleStringSwitchRemover remover;
          if (theSwitch.numberOfKeys() < appView.options().minimumStringSwitchSize
              || hashCodeOfKeysMayChangeAfterMinification(theSwitch)) {
            remover =
                new SingleEqualityBasedStringSwitchRemover(
                    code, blockIterator, block, theSwitch, newBlocksWithStrings);
          } else {
            remover =
                new SingleHashBasedStringSwitchRemover(
                    code, blockIterator, block, theSwitch, newBlocksWithStrings);
          }
          remover.removeStringSwitch();
        } catch (UTFDataFormatException e) {
          // The keys of a string-switch should never fail to decode.
          throw new Unreachable();
        }
      }
    }

    if (identifierNameStringMarker != null) {
      identifierNameStringMarker.decoupleIdentifierNameStringsInBlocks(code, newBlocksWithStrings);
    }

    assert code.isConsistentSSA(appView);
  }

  // Returns true if minification is enabled and the switch value is guaranteed to be a class name.
  // In this case, we can't use the hash codes of the keys before minification, because they will
  // (potentially) change as a result of minification. Therefore, we currently emit a sequence of
  // if-equals checks for such switches.
  //
  // TODO(b/154483187): This should also use the hash-based string switch elimination.
  private boolean hashCodeOfKeysMayChangeAfterMinification(StringSwitch theSwitch) {
    return appView.options().isMinifying()
        && isClassNameValue(theSwitch.value(), appView.dexItemFactory());
  }

  private boolean prepareForStringSwitchRemoval(IRCode code) {
    boolean hasStringSwitch = false;
    ListIterator<BasicBlock> blockIterator = code.listIterator();
    while (blockIterator.hasNext()) {
      BasicBlock block = blockIterator.next();
      for (BasicBlock predecessor : block.getNormalPredecessors()) {
        StringSwitch exit = predecessor.exit().asStringSwitch();
        if (exit != null) {
          hasStringSwitch = true;
          if (block == exit.fallthroughBlock()) {
            // After the elimination of this string-switch instruction, there will be two
            // fallthrough blocks: one for the instruction that switches on the hash value and one
            // for the instruction that switches on the string id value.
            //
            // The existing fallthrough block will be the fallthrough block for the switch on the
            // hash value. Note that we can't use this block for the switch on the id value since
            // that would lead to critical edges.
            BasicBlock hashSwitchFallthroughBlock = block;

            // The `hashSwitchFallthroughBlock` will jump to the switch on the string id value.
            // This block will have multiple predecessors, hence the need for the split-edge
            // block.
            BasicBlock idSwitchBlock =
                hashSwitchFallthroughBlock.listIterator(code).split(code, blockIterator);

            // Split again such that `idSwitchBlock` becomes a block consisting of a single goto
            // instruction that targets a block that is identical to the original fallthrough
            // block of the string-switch instruction.
            BasicBlock idSwitchFallthroughBlock =
                idSwitchBlock.listIterator(code).split(code, blockIterator);
            break;
          }
        }
      }
    }

    return hasStringSwitch;
  }

  private abstract static class SingleStringSwitchRemover {

    final IRCode code;
    final ListIterator<BasicBlock> blockIterator;
    final Set<BasicBlock> newBlocksWithStrings;

    final Position position;
    final Value stringValue;

    private SingleStringSwitchRemover(
        IRCode code,
        ListIterator<BasicBlock> blockIterator,
        StringSwitch theSwitch,
        Set<BasicBlock> newBlocksWithStrings) {
      this.code = code;
      this.blockIterator = blockIterator;
      this.newBlocksWithStrings = newBlocksWithStrings;
      this.position = theSwitch.getPosition();
      this.stringValue = theSwitch.value();
    }

    abstract void removeStringSwitch();
  }

  private class SingleEqualityBasedStringSwitchRemover extends SingleStringSwitchRemover {

    private final BasicBlock block;
    private final BasicBlock fallthroughBlock;

    private final Map<DexString, BasicBlock> structure;

    private SingleEqualityBasedStringSwitchRemover(
        IRCode code,
        ListIterator<BasicBlock> blockIterator,
        BasicBlock block,
        StringSwitch theSwitch,
        Set<BasicBlock> newBlocksWithStrings) {
      super(code, blockIterator, theSwitch, newBlocksWithStrings);
      this.block = block;
      this.fallthroughBlock = theSwitch.fallthroughBlock();
      this.structure = createStructure(theSwitch);
    }

    private Map<DexString, BasicBlock> createStructure(StringSwitch theSwitch) {
      Map<DexString, BasicBlock> result = new LinkedHashMap<>();
      theSwitch.forEachCase(result::put);
      return result;
    }

    @Override
    void removeStringSwitch() {
      // Remove outgoing control flow edges from the block containing the string switch.
      for (BasicBlock successor : block.getNormalSuccessors()) {
        successor.removePredecessor(block, null);
      }
      block.removeAllNormalSuccessors();
      Set<BasicBlock> blocksTargetedByMultipleSwitchCases = Sets.newIdentityHashSet();
      {
        Set<BasicBlock> seenBefore = SetUtils.newIdentityHashSet(structure.size());
        for (BasicBlock targetBlock : structure.values()) {
          if (!seenBefore.add(targetBlock)) {
            blocksTargetedByMultipleSwitchCases.add(targetBlock);
          }
        }
      }
      // Create a String.equals() check for each case in the string-switch instruction.
      BasicBlock previous = null;
      for (Entry<DexString, BasicBlock> entry : structure.entrySet()) {
        ConstString constStringInstruction =
            new ConstString(code.createValue(stringType), entry.getKey());
        constStringInstruction.setPosition(position);
        InvokeVirtual invokeInstruction =
            new InvokeVirtual(
                appView.dexItemFactory().stringMembers.equals,
                code.createValue(PrimitiveTypeElement.getInt()),
                ImmutableList.of(stringValue, constStringInstruction.outValue()));
        invokeInstruction.setPosition(position);
        If ifInstruction = new If(If.Type.NE, invokeInstruction.outValue());
        ifInstruction.setPosition(Position.none());
        BasicBlock targetBlock = entry.getValue();
        if (blocksTargetedByMultipleSwitchCases.contains(targetBlock)) {
          // Need an intermediate block to avoid critical edges.
          BasicBlock intermediateBlock =
              BasicBlock.createGotoBlock(
                  code.getNextBlockNumber(), Position.none(), code.metadata());
          intermediateBlock.link(targetBlock);
          blockIterator.add(intermediateBlock);
          newBlocksWithStrings.add(intermediateBlock);
          targetBlock = intermediateBlock;
        }
        BasicBlock newBlock =
            BasicBlock.createIfBlock(
                code.getNextBlockNumber(),
                ifInstruction,
                code.metadata(),
                constStringInstruction,
                invokeInstruction);
        newBlock.link(targetBlock);
        blockIterator.add(newBlock);
        newBlocksWithStrings.add(newBlock);
        if (previous == null) {
          // Replace the string-switch instruction by a goto instruction.
          block.exit().replace(new Goto(newBlock), code);
          block.link(newBlock);
        } else {
          // Set the fallthrough block for the previously added if-instruction.
          previous.link(newBlock);
        }
        previous = newBlock;
      }
      assert previous != null;
      // Set the fallthrough block for the last if-instruction.
      previous.link(fallthroughBlock);
    }
  }

  private class SingleHashBasedStringSwitchRemover extends SingleStringSwitchRemover {

    private final BasicBlock hashSwitchBlock;
    private final BasicBlock hashSwitchFallthroughBlock;
    private final BasicBlock idSwitchBlock;
    private final BasicBlock idSwitchFallthroughBlock;

    Int2ReferenceMap<Map<DexString, BasicBlock>> structure;

    private int nextStringId;

    private SingleHashBasedStringSwitchRemover(
        IRCode code,
        ListIterator<BasicBlock> blockIterator,
        BasicBlock hashSwitchBlock,
        StringSwitch theSwitch,
        Set<BasicBlock> newBlocksWithStrings)
        throws UTFDataFormatException {
      super(code, blockIterator, theSwitch, newBlocksWithStrings);
      this.hashSwitchBlock = hashSwitchBlock;
      this.hashSwitchFallthroughBlock = theSwitch.fallthroughBlock();
      this.idSwitchBlock = theSwitch.fallthroughBlock().getUniqueNormalSuccessor();
      this.idSwitchFallthroughBlock = idSwitchBlock.getUniqueNormalSuccessor();
      this.structure = createStructure(theSwitch);
    }

    private int getAndIncrementNextBlockNumber() {
      return code.getNextBlockNumber();
    }

    private Int2ReferenceMap<Map<DexString, BasicBlock>> createStructure(StringSwitch theSwitch)
        throws UTFDataFormatException {
      Int2ReferenceMap<Map<DexString, BasicBlock>> result = new Int2ReferenceRBTreeMap<>();
      theSwitch.forEachCase(
          (key, target) -> {
            int hashCode = key.decodedHashCode();
            if (result.containsKey(hashCode)) {
              result.get(hashCode).put(key, target);
            } else {
              Map<DexString, BasicBlock> cases = new LinkedHashMap<>();
              cases.put(key, target);
              result.put(hashCode, cases);
            }
          });
      return result;
    }

    @Override
    void removeStringSwitch() {
      // Remove outgoing control flow edges from the block containing the string switch.
      for (BasicBlock successor : hashSwitchBlock.getNormalSuccessors()) {
        successor.removePredecessor(hashSwitchBlock, null);
      }
      hashSwitchBlock.removeAllNormalSuccessors();

      // 1. Insert `int id = -1`.
      InstructionListIterator instructionIterator =
          hashSwitchBlock.listIterator(code, hashSwitchBlock.size());
      instructionIterator.previous();

      Phi idPhi = code.createPhi(idSwitchBlock, TypeElement.getInt());
      Value notFoundIdValue =
          instructionIterator.insertConstIntInstruction(code, appView.options(), -1);
      idPhi.appendOperand(notFoundIdValue);

      // 2. Insert `int hashCode = stringValue.hashCode()`.
      InvokeVirtual hashInvoke =
          new InvokeVirtual(
              appView.dexItemFactory().stringMembers.hashCode,
              code.createValue(TypeElement.getInt()),
              ImmutableList.of(stringValue));
      hashInvoke.setPosition(position);
      instructionIterator.add(hashInvoke);

      // 3. Create all the target blocks of the hash switch.
      //
      // Say that the string switch instruction contains the keys "X" and "Y" and assume that "X"
      // and "Y" have the same hash code. Then this will create code that looks like:
      //
      //   Block N:
      //     boolean equalsX = stringValue.equals("X")
      //     if equalsX then goto block N+1 else goto block N+2
      //   Block N+1:
      //     id = 0
      //     goto <id-switch-block>
      //   Block N+2:
      //     boolean equalsY = stringValue.equals("Y")
      //     if equalsY then goto block N+3 else goto block N+4
      //   Block N+3:
      //     id = 1
      //     goto <id-switch-block>
      //   Block N+4:
      //     goto <id-switch-block>
      createHashSwitchTargets(idPhi, notFoundIdValue);
      hashSwitchBlock.link(hashSwitchFallthroughBlock);

      // 4. Insert `switch (hashValue)`.
      IntSwitch hashSwitch = createHashSwitch(hashInvoke.outValue());
      instructionIterator.next();
      instructionIterator.replaceCurrentInstruction(hashSwitch);

      // 5. Link `idSwitchBlock` with all of its target blocks.
      Reference2IntMap<BasicBlock> targetBlockIndices = new Reference2IntOpenHashMap<>();
      targetBlockIndices.defaultReturnValue(-1);
      idSwitchBlock.getMutableSuccessors().clear();
      for (Map<DexString, BasicBlock> cases : structure.values()) {
        for (BasicBlock target : cases.values()) {
          int targetIndex = targetBlockIndices.getInt(target);
          if (targetIndex == -1) {
            targetBlockIndices.put(target, idSwitchBlock.getSuccessors().size());
            idSwitchBlock.link(target);
          }
        }
      }
      idSwitchBlock.getMutableSuccessors().add(idSwitchFallthroughBlock);

      // 6. Insert `switch (idValue)`.
      IntSwitch idSwitch = createIdSwitch(idPhi, targetBlockIndices);
      InstructionListIterator idSwitchBlockInstructionIterator = idSwitchBlock.listIterator(code);
      idSwitchBlockInstructionIterator.next();
      idSwitchBlockInstructionIterator.replaceCurrentInstruction(idSwitch);
    }

    private IntSwitch createHashSwitch(Value hashValue) {
      int[] hashSwitchKeys = structure.keySet().toArray(new int[0]);
      int[] hashSwitchTargetIndices = new int[hashSwitchKeys.length];
      for (int i = 0, offset = hashSwitchBlock.numberOfExceptionalSuccessors();
          i < hashSwitchTargetIndices.length;
          i++) {
        hashSwitchTargetIndices[i] = i + offset;
      }
      int hashSwitchFallthroughIndex = hashSwitchBlock.getSuccessors().size() - 1;
      return new IntSwitch(
          hashValue, hashSwitchKeys, hashSwitchTargetIndices, hashSwitchFallthroughIndex);
    }

    private void createHashSwitchTargets(Phi idPhi, Value notFoundIdValue) {
      for (Map<DexString, BasicBlock> cases : structure.values()) {
        // Create the target block for the hash switch.
        BasicBlock hashBlock =
            BasicBlock.createGotoBlock(getAndIncrementNextBlockNumber(), position, code.metadata());
        blockIterator.add(hashBlock);
        hashSwitchBlock.link(hashBlock);

        // Position the block iterator at the newly created block.
        BasicBlock previous = blockIterator.previous();
        assert previous == hashBlock;
        blockIterator.next();

        BasicBlock current = hashBlock;
        for (Entry<DexString, BasicBlock> entry : cases.entrySet()) {
          current.getMutableSuccessors().clear();

          // Insert `String key = <entry.getKey()>`.
          InstructionListIterator instructionIterator = current.listIterator(code);
          Value keyValue =
              instructionIterator.insertConstStringInstruction(appView, code, entry.getKey());
          newBlocksWithStrings.add(current);

          // Insert `boolean equalsKey = stringValue.equals(key)`.
          InvokeVirtual equalsInvoke =
              new InvokeVirtual(
                  appView.dexItemFactory().stringMembers.equals,
                  code.createValue(TypeElement.getInt()),
                  ImmutableList.of(stringValue, keyValue));
          equalsInvoke.setPosition(position);
          instructionIterator.add(equalsInvoke);

          // Create a new block for the success case.
          BasicBlock equalsKeyBlock =
              BasicBlock.createGotoBlock(
                  getAndIncrementNextBlockNumber(), position, code.metadata(), idSwitchBlock);
          idSwitchBlock.getMutablePredecessors().add(equalsKeyBlock);
          blockIterator.add(equalsKeyBlock);
          current.link(equalsKeyBlock);

          // Insert `int id = <nextStringId++>`.
          Value idValue =
              equalsKeyBlock
                  .listIterator(code)
                  .insertConstIntInstruction(code, appView.options(), nextStringId++);
          idPhi.appendOperand(idValue);

          // Create a new block for the failure case.
          BasicBlock continuationBlock =
              BasicBlock.createGotoBlock(
                  getAndIncrementNextBlockNumber(), position, code.metadata(), idSwitchBlock);
          blockIterator.add(continuationBlock);
          current.link(continuationBlock);

          // Insert `if (equalsKey) goto <id-switch-block> else goto <continuation-block>`.
          instructionIterator.next();
          instructionIterator.replaceCurrentInstruction(new If(Type.NE, equalsInvoke.outValue()));

          current = continuationBlock;
        }
        idPhi.appendOperand(notFoundIdValue);
        idSwitchBlock.getMutablePredecessors().add(current);
      }
    }

    private IntSwitch createIdSwitch(Phi idPhi, Reference2IntMap<BasicBlock> targetBlockIndices) {
      int numberOfCases = nextStringId;
      int[] keys = ArrayUtils.createIdentityArray(numberOfCases);
      int[] targetIndices = new int[numberOfCases];
      int i = 0;
      for (Map<DexString, BasicBlock> cases : structure.values()) {
        for (Entry<DexString, BasicBlock> entry : cases.entrySet()) {
          targetIndices[i++] = targetBlockIndices.getInt(entry.getValue());
        }
      }
      int fallthroughIndex = targetBlockIndices.size();
      return new IntSwitch(idPhi, keys, targetIndices, fallthroughIndex);
    }
  }
}