// Copyright 2019 The Bazel Authors. All rights reserved.
//
// 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.google.devtools.build.lib.bazel.repository;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.base.Splitter;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.devtools.build.lib.vfs.FileSystemUtils;
import com.google.devtools.build.lib.vfs.Path;
import difflib.Chunk;
import difflib.Delta;
import difflib.DeltaComparator;
import difflib.DiffUtils;
import difflib.Patch;
import difflib.PatchFailedException;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/** Implementation of native patch. */
public class PatchUtil {

  private static final Pattern CHUNK_HEADER_RE =
      Pattern.compile("^@@\\s+-(?:(\\d+)(?:,(\\d+))?)\\s+\\+(?:(\\d+)(?:,(\\d+))?)\\s+@@$");

  /** The possible results of ChunkHeader.check. */
  public enum Result {
    COMPLETE, // The entire chunk is read
    CONTINUE, // Should continue reading the chunk
    ERROR, // The chunk body doesn't match the chunk header's size description
  }

  private static class ChunkHeader {
    private final int oldSize;
    private final int newSize;

    public Result check(int oldLineCnt, int newLineCnt) {
      if (oldLineCnt == oldSize && newLineCnt == newSize) {
        return Result.COMPLETE;
      }
      if (oldLineCnt <= oldSize && newLineCnt <= newSize) {
        return Result.CONTINUE;
      }
      return Result.ERROR;
    }

    ChunkHeader(String header) throws PatchFailedException {
      Matcher m = CHUNK_HEADER_RE.matcher(header);
      if (m.find()) {
        String size;
        size = m.group(2);
        oldSize = (size == null) ? 1 : Integer.parseInt(size);
        size = m.group(4);
        newSize = (size == null) ? 1 : Integer.parseInt(size);
      } else {
        throw new PatchFailedException("Wrong chunk header: " + header);
      }
    }
  }

  /**
   * Sometimes the line number in patch file is not completely correct, but we might still be able
   * to find a content match with an offset.
   */
  private static class OffsetPatch {

    public static List<String> applyTo(Patch<String> patch, List<String> target)
        throws PatchFailedException {
      List<Delta<String>> deltas = patch.getDeltas();
      List<String> result = new ArrayList<>(target);
      deltas.sort(DeltaComparator.INSTANCE);
      for (Delta<String> item : Lists.reverse(deltas)) {
        Delta<String> delta = item;
        applyTo(delta, result);
      }

      return result;
    }

    /**
     * This function first tries to apply the Delta without any offset, if that fails, then it tries
     * to apply the Delta with an offset, starting from 1, up to the total lines in the original
     * content. For every offset, we try both forwards and backwards.
     */
    private static void applyTo(Delta<String> delta, List<String> result)
        throws PatchFailedException {
      PatchFailedException e = applyDelta(delta, result);
      if (e == null) {
        return;
      }

      Chunk<String> original = delta.getOriginal();
      Chunk<String> revised = delta.getRevised();
      int[] direction = {1, -1};
      int maxOffset = result.size();
      for (int i = 1; i < maxOffset; i++) {
        for (int j = 0; j < 2; j++) {
          int offset = i * direction[j];
          if (offset + original.getPosition() < 0 || offset + revised.getPosition() < 0) {
            continue;
          }
          delta.setOriginal(new Chunk<>(original.getPosition() + offset, original.getLines()));
          delta.setRevised(new Chunk<>(revised.getPosition() + offset, revised.getLines()));
          PatchFailedException exception = applyDelta(delta, result);
          if (exception == null) {
            return;
          }
        }
      }

      throw e;
    }

    private static PatchFailedException applyDelta(Delta<String> delta, List<String> result) {
      try {
        delta.applyTo(result);
        return null;
      } catch (PatchFailedException e) {
        String msg =
            String.join(
                "\n",
                "**Original Position**: " + (delta.getOriginal().getPosition() + 1) + "\n",
                "**Original Content**:",
                String.join("\n", delta.getOriginal().getLines()) + "\n",
                "**Revised Content**:",
                String.join("\n", delta.getRevised().getLines()) + "\n");
        return new PatchFailedException(e.getMessage() + "\n" + msg);
      }
    }
  }

  private enum LineType {
    OLD_FILE,
    NEW_FILE,
    CHUNK_HEAD,
    CHUNK_ADD,
    CHUNK_DEL,
    CHUNK_EQL,
    GIT_HEADER,
    RENAME_FROM,
    RENAME_TO,
    GIT_LINE,
    UNKNOWN
  }

  private static final String[] GIT_LINE_PREFIXES = {
    "old mode ",
    "new mode ",
    "deleted file mode ",
    "new file mode ",
    "copy from ",
    "copy to ",
    "rename old ",
    "rename new ",
    "similarity index ",
    "dissimilarity index ",
    "index "
  };

  private static LineType getLineType(String line, boolean isReadingChunk, boolean isGitDiff) {
    if (isReadingChunk) {
      if (line.startsWith("+")) {
        return LineType.CHUNK_ADD;
      }
      if (line.startsWith("-")) {
        return LineType.CHUNK_DEL;
      }
      if (line.startsWith(" ") || line.isEmpty()) {
        return LineType.CHUNK_EQL;
      }
    } else {
      if (line.startsWith("--- ")) {
        return LineType.OLD_FILE;
      }
      if (line.startsWith("+++ ")) {
        return LineType.NEW_FILE;
      }
      if (line.startsWith("diff --git ")) {
        return LineType.GIT_HEADER;
      }
      if (isGitDiff) {
        // Only recognize the following when we saw "diff --git " before.
        if (line.startsWith("rename from ")) {
          return LineType.RENAME_FROM;
        }
        if (line.startsWith("rename to ")) {
          return LineType.RENAME_TO;
        }
        for (String prefix : GIT_LINE_PREFIXES) {
          if (line.startsWith(prefix)) {
            return LineType.GIT_LINE;
          }
        }
      }
    }
    if (line.startsWith("@@") && line.lastIndexOf("@@") != 0) {
      int pos = line.indexOf("@@", 2);
      Matcher m = CHUNK_HEADER_RE.matcher(line.substring(0, pos + 2));
      if (m.find()) {
        return LineType.CHUNK_HEAD;
      }
    }
    return LineType.UNKNOWN;
  }

  @VisibleForTesting
  public static List<String> readFile(Path file) throws IOException {
    return Lists.newArrayList(FileSystemUtils.readLines(file, StandardCharsets.UTF_8));
  }

  private static void writeFile(Path file, List<String> content) throws IOException {
    FileSystemUtils.writeLinesAs(file, StandardCharsets.UTF_8, content);
  }

  private static void applyPatchToFile(
      Patch<String> patch, Path oldFile, Path newFile, boolean isRenaming)
      throws IOException, PatchFailedException {
    // The file we should read oldContent from.
    Path inputFile = null;
    if (oldFile != null && oldFile.exists()) {
      inputFile = oldFile;
    } else if (newFile != null && newFile.exists()) {
      inputFile = newFile;
    }

    List<String> oldContent;
    if (inputFile == null) {
      oldContent = new ArrayList<>();
    } else {
      oldContent = readFile(inputFile);
    }

    List<String> newContent = OffsetPatch.applyTo(patch, oldContent);

    // The file we should write newContent to.
    Path outputFile;
    if (oldFile != null && oldFile.exists() && !isRenaming) {
      outputFile = oldFile;
    } else {
      outputFile = newFile;
    }

    // The old file should always change, therefore we can just delete the original file.
    // If the output file name is the same as the old file, we'll just recreate it later.
    if (oldFile != null) {
      oldFile.delete();
    }

    // Does this patch look like deleting a file.
    boolean isDeleteFile = newFile == null && newContent.isEmpty();

    if (outputFile != null && !isDeleteFile) {
      writeFile(outputFile, newContent);
    }
  }

  /**
   * Strip a number of leading components from a path
   *
   * @param path the original path
   * @param strip the number of leading components to strip
   * @return The stripped path
   */
  private static String stripPath(String path, int strip) {
    int pos = 0;
    while (pos < path.length() && strip > 0) {
      if (path.charAt(pos) == '/') {
        strip--;
      }
      pos++;
    }
    return path.substring(pos);
  }

  /**
   * Extract the file path from a patch line starting with "--- " or "+++ " Returns null if the path
   * is /dev/null, otherwise returns the extracted path if succeeded or throw an exception if
   * failed.
   */
  private static String extractPath(String line, int strip, int loc) throws PatchFailedException {
    // The line could look like:
    // --- a/foo/bar.txt   2019-05-27 17:19:37.054593200 +0200
    // +++ b/foo/bar.txt   2019-05-27 17:19:37.054593200 +0200
    // If strip is 1, we want extract the file path as foo/bar.txt
    Preconditions.checkArgument(line.startsWith("+++ ") || line.startsWith("--- "));
    line = Iterables.get(Splitter.on('\t').split(line), 0);
    if (line.length() > 4) {
      String path = line.substring(4).trim();
      if (path.equals("/dev/null")) {
        return null;
      }
      path = stripPath(path, strip);
      if (!path.isEmpty()) {
        return path;
      }
    }
    throw new PatchFailedException(
        String.format(
            "Cannot determine file name with strip = %d at line %d:\n%s", strip, loc, line));
  }

  private static Path getFilePath(String path, Path outputDirectory, int loc)
      throws PatchFailedException {
    if (path == null) {
      return null;
    }
    Path filePath = outputDirectory.getRelative(path);
    if (!filePath.startsWith(outputDirectory)) {
      throw new PatchFailedException(
          String.format(
              "Cannot patch file outside of external repository (%s), file path = \"%s\" at line"
                  + " %d",
              outputDirectory.getPathString(), path, loc));
    }
    return filePath;
  }

  private static void checkPatchContentIsComplete(
      List<String> patchContent, ChunkHeader header, int oldLineCount, int newLineCount, int loc)
      throws PatchFailedException {
    // If the patchContent is not empty, it should have correct format.
    if (!patchContent.isEmpty()) {
      if (header == null) {
        throw new PatchFailedException(
            String.format(
                "Looks like a unified diff at line %d, but no patch chunk was found.", loc));
      }
      Result result = header.check(oldLineCount, newLineCount);
      // result will never be Result.Error here because it would have been throw in previous
      // line already.
      if (result == Result.CONTINUE) {
        throw new PatchFailedException(
            String.format("Expecting more chunk line at line %d", loc + patchContent.size()));
      }
    }
  }

  private static void checkFilesStatusForRenaming(
      Path oldFile, Path newFile, String oldFileStr, String newFileStr, int loc)
      throws PatchFailedException {
    // If we're doing a renaming,
    // old file should be specified and exists,
    // new file should be specified but doesn't exist yet.
    String oldFileError = "";
    String newFileError = "";
    if (oldFile == null) {
      oldFileError = ", old file name (%s) is not specified";
    } else if (!oldFile.exists()) {
      oldFileError = String.format(", old file name (%s) doesn't exist", oldFileStr);
    }
    if (newFile == null) {
      newFileError = ", new file name is not specified";
    } else if (newFile.exists()) {
      newFileError = String.format(", new file name (%s) already exists", newFileStr);
    }
    if (!oldFileError.isEmpty() || !newFileError.isEmpty()) {
      throw new PatchFailedException(
          String.format("Cannot rename file (near line %d)%s%s.", loc, oldFileError, newFileError));
    }
  }

  private static void checkFilesStatusForPatching(
      Patch<String> patch,
      Path oldFile,
      Path newFile,
      String oldFileStr,
      String newFileStr,
      int loc)
      throws PatchFailedException {
    // At least one of oldFile or newFile should be specified.
    if (oldFile == null && newFile == null) {
      throw new PatchFailedException(
          String.format(
              "Wrong patch format near line %d, neither new file or old file are specified.", loc));
    }

    // Does this patch look like adding a new file.
    boolean isAddFile =
        patch.getDeltas().size() == 1
            && patch.getDeltas().get(0).getOriginal().getLines().isEmpty();

    // If this patch is not adding a new file,
    // then either old file or new file should be specified and exists,
    // if not we throw an error.
    if (!isAddFile
        && (oldFile == null || !oldFile.exists())
        && (newFile == null || !newFile.exists())) {
      String oldFileError;
      String newFileError;
      if (oldFile == null) {
        oldFileError = ", old file name (%s) is not specified";
      } else {
        oldFileError = String.format(", old file name (%s) doesn't exist", oldFileStr);
      }
      if (newFile == null) {
        newFileError = ", new file name is not specified";
      } else {
        newFileError = String.format(", new file name (%s) doesn't exist", newFileStr);
      }
      throw new PatchFailedException(
          String.format(
              "Cannot find file to patch (near line %d)%s%s.", loc, oldFileError, newFileError));
    }
  }

  /**
   * Apply a patch file under a directory
   *
   * @param patchFile the patch file to apply
   * @param strip the number of leading components to strip from file path in the patch file
   * @param outputDirectory the repository directory to apply the patch file
   */
  public static void apply(Path patchFile, int strip, Path outputDirectory)
      throws IOException, PatchFailedException {
    if (!patchFile.exists()) {
      throw new PatchFailedException("Cannot find patch file: " + patchFile.getPathString());
    }
    List<String> patchFileLines = readFile(patchFile);
    // Adding an extra line to make sure last chunk also gets applied.
    patchFileLines.add("$");

    boolean isGitDiff = false;
    boolean hasRenameFrom = false;
    boolean hasRenameTo = false;
    boolean isReadingChunk = false;
    List<String> patchContent = new ArrayList<>();
    ChunkHeader header = null;
    String oldFileStr = null;
    String newFileStr = null;
    Path oldFile = null;
    Path newFile = null;
    int oldLineCount = 0;
    int newLineCount = 0;
    Result result;

    for (int i = 0; i < patchFileLines.size(); i++) {
      String line = patchFileLines.get(i);
      LineType type;
      switch (type = getLineType(line, isReadingChunk, isGitDiff)) {
        case OLD_FILE:
          patchContent.add(line);
          oldFileStr = extractPath(line, strip, i + 1);
          oldFile = getFilePath(oldFileStr, outputDirectory, i + 1);
          break;
        case NEW_FILE:
          patchContent.add(line);
          newFileStr = extractPath(line, strip, i + 1);
          newFile = getFilePath(newFileStr, outputDirectory, i + 1);
          break;
        case CHUNK_HEAD:
          int pos = line.indexOf("@@", 2);
          String headerStr = line.substring(0, pos + 2);
          patchContent.add(headerStr);
          header = new ChunkHeader(headerStr);
          oldLineCount = 0;
          newLineCount = 0;
          isReadingChunk = true;
          break;
        case CHUNK_ADD:
          newLineCount++;
          patchContent.add(line);
          result = header.check(oldLineCount, newLineCount);
          if (result == Result.COMPLETE) {
            isReadingChunk = false;
          } else if (result == Result.ERROR) {
            throw new PatchFailedException(
                "Wrong chunk detected near line "
                    + (i + 1)
                    + ": "
                    + line
                    + ", does not expect an added line here.");
          }
          break;
        case CHUNK_DEL:
          oldLineCount++;
          patchContent.add(line);
          result = header.check(oldLineCount, newLineCount);
          if (result == Result.COMPLETE) {
            isReadingChunk = false;
          } else if (result == Result.ERROR) {
            throw new PatchFailedException(
                "Wrong chunk detected near line "
                    + (i + 1)
                    + ": "
                    + line
                    + ", does not expect a deleted line here.");
          }
          break;
        case CHUNK_EQL:
          oldLineCount++;
          newLineCount++;
          patchContent.add(line);
          result = header.check(oldLineCount, newLineCount);
          if (result == Result.COMPLETE) {
            isReadingChunk = false;
          } else if (result == Result.ERROR) {
            throw new PatchFailedException(
                "Wrong chunk detected near line "
                    + (i + 1)
                    + ": "
                    + line
                    + ", does not expect a context line here.");
          }
          break;
        case RENAME_FROM:
          hasRenameFrom = true;
          if (oldFileStr == null) {
            // len("rename from ") == 12
            oldFileStr = line.substring(12).trim();
            if (oldFileStr.isEmpty()) {
              throw new PatchFailedException(
                  String.format("Cannot determine file name from line %d:\n%s", i + 1, line));
            }
            oldFile = getFilePath(oldFileStr, outputDirectory, i + 1);
          }
          break;
        case RENAME_TO:
          hasRenameTo = true;
          if (newFileStr == null) {
            // len("rename to ") == 10
            newFileStr = line.substring(10).trim();
            if (newFileStr.isEmpty()) {
              throw new PatchFailedException(
                  String.format("Cannot determine file name from line %d:\n%s", i + 1, line));
            }
            newFile = getFilePath(newFileStr, outputDirectory, i + 1);
          }
          break;
        case GIT_LINE:
          break;
        case GIT_HEADER:
        case UNKNOWN:
          // A git header line or an unknown line should trigger an action to apply collected
          // patch content to a file.

          // Renaming is a git only format
          boolean isRenaming = isGitDiff && hasRenameFrom && hasRenameTo;

          if (!patchContent.isEmpty() || isRenaming) {
            // We collected something useful, let's do some sanity checks before applying the patch.
            int patchStartLocation = i + 1 - patchContent.size();

            checkPatchContentIsComplete(
                patchContent, header, oldLineCount, newLineCount, patchStartLocation);

            if (isRenaming) {
              checkFilesStatusForRenaming(
                  oldFile, newFile, oldFileStr, newFileStr, patchStartLocation);
            }

            Patch<String> patch = DiffUtils.parseUnifiedDiff(patchContent);
            checkFilesStatusForPatching(
                patch, oldFile, newFile, oldFileStr, newFileStr, patchStartLocation);

            applyPatchToFile(patch, oldFile, newFile, isRenaming);
          }

          patchContent.clear();
          header = null;
          oldFileStr = null;
          newFileStr = null;
          oldFile = null;
          newFile = null;
          oldLineCount = 0;
          newLineCount = 0;
          isReadingChunk = false;
          // If the new patch starts with "diff --git " then it's a git diff.
          isGitDiff = type == LineType.GIT_HEADER;
          hasRenameFrom = false;
          hasRenameTo = false;
          break;
      }
    }
  }
}