diff --git a/src/main/java/com/google/devtools/build/lib/BUILD b/src/main/java/com/google/devtools/build/lib/BUILD
index e724b46..a777b7b 100644
--- a/src/main/java/com/google/devtools/build/lib/BUILD
+++ b/src/main/java/com/google/devtools/build/lib/BUILD
@@ -984,6 +984,7 @@
         "//third_party:aether",
         "//third_party:apache_commons_compress",
         "//third_party:auto_value",
+        "//third_party:diffutils",
         "//third_party:guava",
         "//third_party:jsr305",
         "//third_party:maven",
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/repository/PatchUtil.java b/src/main/java/com/google/devtools/build/lib/bazel/repository/PatchUtil.java
new file mode 100644
index 0000000..e9ffee0
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/bazel/repository/PatchUtil.java
@@ -0,0 +1,581 @@
+// 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()) {
+        oldSize = Integer.parseInt(m.group(2));
+        newSize = Integer.parseInt(m.group(4));
+      } 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) {
+        return new PatchFailedException(e.getMessage() + "\nFailed to apply delta:\n    " + delta);
+      }
+    }
+  }
+
+  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;
+      }
+    }
+  }
+}
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/repository/BUILD b/src/test/java/com/google/devtools/build/lib/bazel/repository/BUILD
index 623bb3f..e91b284 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/repository/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/bazel/repository/BUILD
@@ -53,6 +53,7 @@
         "//src/test/java/com/google/devtools/build/lib:packages_testutil",
         "//src/test/java/com/google/devtools/build/lib:test_runner",
         "//src/test/java/com/google/devtools/build/lib:testutil",
+        "//third_party:diffutils",
         "//third_party:guava",
         "//third_party:guava-testlib",
         "//third_party:jsr305",
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/repository/PatchUtilTest.java b/src/test/java/com/google/devtools/build/lib/bazel/repository/PatchUtilTest.java
new file mode 100644
index 0000000..1c85989
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/bazel/repository/PatchUtilTest.java
@@ -0,0 +1,549 @@
+// 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 static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.testutil.MoreAsserts.assertThrows;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.testutil.Scratch;
+import com.google.devtools.build.lib.vfs.FileSystem;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
+import difflib.PatchFailedException;
+import java.io.IOException;
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+/** Tests for {@link PatchUtil}. */
+@RunWith(JUnit4.class)
+public class PatchUtilTest {
+
+  private FileSystem fs;
+  private Scratch scratch;
+  private Path root;
+
+  @Before
+  public final void initializeFileSystemAndDirectories() throws Exception {
+    fs = new InMemoryFileSystem();
+    scratch = new Scratch(fs, "/root");
+    root = scratch.dir("/root");
+  }
+
+  @Test
+  public void testAddFile() throws IOException, PatchFailedException {
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/newfile b/newfile",
+            "new file mode 100644",
+            "index 0000000..f742c88",
+            "--- /dev/null",
+            "+++ b/newfile",
+            "@@ -0,0 +1,2 @@",
+            "+I'm a new file",
+            "+hello, world",
+            "-- ",
+            "2.21.0.windows.1");
+    PatchUtil.apply(patchFile, 1, root);
+    Path newFile = root.getRelative("newfile");
+    ImmutableList<String> newFileContent = ImmutableList.of("I'm a new file", "hello, world");
+    assertThat(PatchUtil.readFile(newFile)).containsExactlyElementsIn(newFileContent);
+  }
+
+  @Test
+  public void testDeleteFile() throws IOException, PatchFailedException {
+    Path oldFile = scratch.file("/root/oldfile", "I'm an old file", "bye, world");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "--- a/oldfile",
+            "+++ /dev/null",
+            "@@ -1,2 +0,0 @@",
+            "-I'm an old file",
+            "-bye, world");
+    PatchUtil.apply(patchFile, 1, root);
+    assertThat(oldFile.exists()).isFalse();
+  }
+
+  @Test
+  public void testDeleteAllContentButNotFile() throws IOException, PatchFailedException {
+    // If newfile is not /dev/null, we don't delete the file even it's empty after patching,
+    // this is the behavior of patch command line tool.
+    Path oldFile = scratch.file("/root/oldfile", "I'm an old file", "bye, world");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "--- a/oldfile",
+            "+++ b/oldfile",
+            "@@ -1,2 +0,0 @@",
+            "-I'm an old file",
+            "-bye, world");
+    PatchUtil.apply(patchFile, 1, root);
+    assertThat(oldFile.exists()).isTrue();
+    assertThat(PatchUtil.readFile(oldFile)).isEmpty();
+  }
+
+  @Test
+  public void testApplyToOldFile() throws IOException, PatchFailedException {
+    // If both oldfile and newfile exist, we should patch the old file.
+    Path oldFile = scratch.file("/root/oldfile", "line one");
+    Path newFile = scratch.file("/root/newfile", "line one");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "--- oldfile",
+            "+++ newfile",
+            "@@ -1,1 +1,2 @@",
+            " line one",
+            "+line two");
+    PatchUtil.apply(patchFile, 0, root);
+    ImmutableList<String> newContent = ImmutableList.of("line one", "line two");
+    assertThat(PatchUtil.readFile(oldFile)).containsExactlyElementsIn(newContent);
+    // new file should not change
+    assertThat(PatchUtil.readFile(newFile)).containsExactly("line one");
+  }
+
+  @Test
+  public void testApplyToNewFile() throws IOException, PatchFailedException {
+    // If only newfile exists, we should patch the new file.
+    Path newFile = scratch.file("/root/newfile", "line one");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "--- oldfile",
+            "+++ newfile",
+            "@@ -1,1 +1,2 @@",
+            " line one",
+            "+line two");
+    PatchUtil.apply(patchFile, 0, root);
+    ImmutableList<String> newContent = ImmutableList.of("line one", "line two");
+    assertThat(PatchUtil.readFile(newFile)).containsExactlyElementsIn(newContent);
+  }
+
+  @Test
+  public void testGitFormatPatching() throws IOException, PatchFailedException {
+    Path foo =
+        scratch.file(
+            "/root/foo.cc",
+            "#include <stdio.h>",
+            "",
+            "void main(){",
+            "  printf(\"Hello foo\");",
+            "}");
+    Path bar = scratch.file("/root/bar.cc", "void lib(){", "  printf(\"Hello bar\");", "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "From d205551eab3350afdb380f90ef83442ffcc0e22b Mon Sep 17 00:00:00 2001",
+            "From: Yun Peng <pcloudy@google.com>",
+            "Date: Thu, 6 Jun 2019 11:34:08 +0200",
+            "Subject: [PATCH] 2",
+            "",
+            "---",
+            " bar.cc | 2 +-",
+            " foo.cc | 1 +",
+            " 2 files changed, 2 insertions(+), 1 deletion(-)",
+            "",
+            "diff --git a/bar.cc b/bar.cc",
+            "index e77137b..36dc9ab 100644",
+            "--- a/bar.cc",
+            "+++ b/bar.cc",
+            "@@ -1,3 +1,3 @@",
+            " void lib(){",
+            "-  printf(\"Hello bar\");",
+            "+  printf(\"Hello patch\");",
+            " }",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ b/foo.cc",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            " }",
+            "-- ",
+            "2.21.0.windows.1",
+            "",
+            "");
+    PatchUtil.apply(patchFile, 1, root);
+    ImmutableList<String> newFoo =
+        ImmutableList.of(
+            "#include <stdio.h>",
+            "",
+            "void main(){",
+            "  printf(\"Hello foo\");",
+            "  printf(\"Hello from patch\");",
+            "}");
+    ImmutableList<String> newBar =
+        ImmutableList.of("void lib(){", "  printf(\"Hello patch\");", "}");
+    assertThat(PatchUtil.readFile(foo)).containsExactlyElementsIn(newFoo);
+    assertThat(PatchUtil.readFile(bar)).containsExactlyElementsIn(newBar);
+  }
+
+  @Test
+  public void testGitFormatRenaming() throws IOException, PatchFailedException {
+    Path foo =
+        scratch.file(
+            "/root/foo.cc",
+            "#include <stdio.h>",
+            "",
+            "void main(){",
+            "  printf(\"Hello foo\");",
+            "}");
+    Path bar = scratch.file("/root/bar.cc", "void lib(){", "  printf(\"Hello bar\");", "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/bar.cc b/bar.cpp",
+            "similarity index 61%",
+            "rename from bar.cc",
+            "rename to bar.cpp",
+            "index e77137b..9e35ee4 100644",
+            "--- a/bar.cc",
+            "+++ b/bar.cpp",
+            "@@ -1,3 +1,4 @@",
+            " void lib(){",
+            "   printf(\"Hello bar\");",
+            "+  printf(\"Hello cpp\");",
+            " }",
+            "diff --git a/foo.cc b/foo.cpp",
+            "similarity index 100%",
+            "rename from foo.cc",
+            "rename to foo.cpp");
+    PatchUtil.apply(patchFile, 1, root);
+    ImmutableList<String> newFoo =
+        ImmutableList.of("#include <stdio.h>", "", "void main(){", "  printf(\"Hello foo\");", "}");
+    ImmutableList<String> newBar =
+        ImmutableList.of(
+            "void lib(){", "  printf(\"Hello bar\");", "  printf(\"Hello cpp\");", "}");
+    Path fooCpp = root.getRelative("foo.cpp");
+    Path barCpp = root.getRelative("bar.cpp");
+    assertThat(foo.exists()).isFalse();
+    assertThat(bar.exists()).isFalse();
+    assertThat(PatchUtil.readFile(fooCpp)).containsExactlyElementsIn(newFoo);
+    assertThat(PatchUtil.readFile(barCpp)).containsExactlyElementsIn(newBar);
+  }
+
+  @Test
+  public void testMatchWithOffset() throws IOException, PatchFailedException {
+    Path foo =
+        scratch.file(
+            "/root/foo.cc",
+            "#include <stdio.h>",
+            "",
+            "void main(){",
+            "  printf(\"Hello foo\");",
+            "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ b/foo.cc",
+            "@@ -6,4 +6,5 @@", // Should match with offset -4, original is "@@ -2,4 +2,5 @@"
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            " }");
+    PatchUtil.apply(patchFile, 1, root);
+    ImmutableList<String> newFoo =
+        ImmutableList.of(
+            "#include <stdio.h>",
+            "",
+            "void main(){",
+            "  printf(\"Hello foo\");",
+            "  printf(\"Hello from patch\");",
+            "}");
+    assertThat(PatchUtil.readFile(foo)).containsExactlyElementsIn(newFoo);
+  }
+
+  @Test
+  public void testMultipleChunksWithDifferentOffset() throws IOException, PatchFailedException {
+    Path foo =
+        scratch.file("/root/foo", "1", "3", "4", "5", "6", "7", "8", "9", "10", "11", "13", "14");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo b/foo",
+            "index c20ab12..b83bdb1 100644",
+            "--- a/foo",
+            "+++ b/foo",
+            "@@ -3,4 +3,5 @@", // Should match with offset -2, original is "@@ -1,4 +1,5 @@"
+            " 1",
+            "+2",
+            " 3",
+            " 4",
+            " 5",
+            "@@ -4,5 +5,6 @@", // Should match with offset 4, original is "@@ -8,4 +9,5 @@"
+            " 9",
+            " 10",
+            " 11",
+            "+12",
+            " 13",
+            " 14");
+    PatchUtil.apply(patchFile, 1, root);
+    ImmutableList<String> newFoo =
+        ImmutableList.of("1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14");
+    assertThat(PatchUtil.readFile(foo)).containsExactlyElementsIn(newFoo);
+  }
+
+  @Test
+  public void testFailedToGetFileName() throws IOException {
+    scratch.file(
+        "/root/foo.cc", "#include <stdio.h>", "", "void main(){", "  printf(\"Hello foo\");", "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ b/foo.cc",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            " }");
+    PatchFailedException expected =
+        assertThrows(
+            PatchFailedException.class,
+            () -> PatchUtil.apply(patchFile, 2, root)); // strip=2 is wrong
+    assertThat(expected)
+        .hasMessageThat()
+        .contains("Cannot determine file name with strip = 2 at line 3:\n--- a/foo.cc");
+  }
+
+  @Test
+  public void testPatchFileNotFound() {
+    PatchFailedException expected =
+        assertThrows(
+            PatchFailedException.class,
+            () -> PatchUtil.apply(root.getRelative("patchfile"), 1, root));
+    assertThat(expected).hasMessageThat().contains("Cannot find patch file: /root/patchfile");
+  }
+
+  @Test
+  public void testMissingBothOldAndNewFile() throws IOException {
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            " }");
+    PatchFailedException expected =
+        assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains("Wrong patch format near line 3, neither new file or old file are specified.");
+  }
+
+  @Test
+  public void testCannotFindFileToPatch() throws IOException {
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ /dev/null",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            " }");
+    PatchFailedException expected =
+        assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains(
+            "Cannot find file to patch (near line 3), old file name (foo.cc) doesn't exist, "
+                + "new file name is not specified.");
+  }
+
+  @Test
+  public void testCannotRenameFile() throws IOException {
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/bar.cc b/bar.cpp",
+            "similarity index 61%",
+            "rename from bar.cc",
+            "rename to bar.cpp",
+            "index e77137b..9e35ee4 100644",
+            "--- a/bar.cc",
+            "+++ b/bar.cpp",
+            "@@ -1,3 +1,4 @@",
+            " void lib(){",
+            "   printf(\"Hello bar\");",
+            "+  printf(\"Hello cpp\");",
+            " }",
+            "diff --git a/foo.cc b/foo.cpp",
+            "similarity index 100%",
+            "rename from foo.cc",
+            "rename to foo.cpp");
+
+    PatchFailedException expected;
+    expected = assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains("Cannot rename file (near line 6), old file name (bar.cc) doesn't exist.");
+
+    scratch.file("/root/bar.cc", "void lib(){", "  printf(\"Hello bar\");", "}");
+    scratch.file("/root/foo.cc");
+    scratch.file("/root/foo.cpp");
+
+    expected = assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains("Cannot rename file (near line 17), new file name (foo.cpp) already exists.");
+  }
+
+  @Test
+  public void testPatchOutsideOfRepository() throws IOException {
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/../other_root/foo.cc",
+            "+++ b/../other_root/foo.cc",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            " }");
+    PatchFailedException expected =
+        assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains(
+            "Cannot patch file outside of external repository (/root), "
+                + "file path = \"../other_root/foo.cc\" at line 3");
+  }
+
+  @Test
+  public void testChunkDoesNotMatch() throws IOException {
+    scratch.file(
+        "/root/foo.cc", "#include <stdio.h>", "", "void main(){", "  printf(\"Hello foo\");", "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ b/foo.cc",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello bar\");", // Should be "Hello foo"
+            "+  printf(\"Hello from patch\");",
+            " }");
+    PatchFailedException expected =
+        assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains(
+            "Incorrect Chunk: the chunk content doesn't match the target\n"
+                + "Failed to apply delta:\n"
+                + "    [ChangeDelta, position: 1, lines: [, void main(){,   printf(\"Hello"
+                + " bar\");, }] to [, void main(){,   printf(\"Hello bar\");,   printf(\"Hello"
+                + " from patch\");, }]]");
+  }
+
+  @Test
+  public void testWrongChunkFormat1() throws IOException {
+    scratch.file(
+        "/root/foo.cc", "#include <stdio.h>", "", "void main(){", "  printf(\"Hello foo\");", "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ b/foo.cc",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            "+", // Adding this line will cause the chunk body not matching the header "@@ -2,4 +2,5
+            // @@"
+            " }");
+    PatchFailedException expected =
+        assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains("Wrong chunk detected near line 11:  }, does not expect a context line here.");
+  }
+
+  @Test
+  public void testWrongChunkFormat2() throws IOException {
+    scratch.file(
+        "/root/foo.cc", "#include <stdio.h>", "", "void main(){", "  printf(\"Hello foo\");", "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ b/foo.cc",
+            "@@ -2,4 +2,5 @@",
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");");
+    PatchFailedException expected =
+        assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected).hasMessageThat().contains("Expecting more chunk line at line 10");
+  }
+
+  @Test
+  public void testWrongChunkFormat3() throws IOException {
+    scratch.file(
+        "/root/foo.cc", "#include <stdio.h>", "", "void main(){", "  printf(\"Hello foo\");", "}");
+    Path patchFile =
+        scratch.file(
+            "/root/patchfile",
+            "diff --git a/foo.cc b/foo.cc",
+            "index f3008f9..ec4aaa0 100644",
+            "--- a/foo.cc",
+            "+++ b/foo.cc",
+            // Missing @@ -l,s +l,s @@ line
+            " ",
+            " void main(){",
+            "   printf(\"Hello foo\");",
+            "+  printf(\"Hello from patch\");",
+            " }");
+    PatchFailedException expected =
+        assertThrows(PatchFailedException.class, () -> PatchUtil.apply(patchFile, 1, root));
+    assertThat(expected)
+        .hasMessageThat()
+        .contains("Looks like a unified diff at line 3, but no patch chunk was found.");
+  }
+}