Add tools/find-commit-for-patch.py

tools/find-commit-for-patch.py

Index: tools/find-commit-for-patch.py
diff --git a/tools/find-commit-for-patch.py b/tools/find-commit-for-patch.py
new file mode 100755
index 0000000000000000000000000000000000000000..65e4cc1c120167b92193a67f7f71a7f5cff3d16a
--- /dev/null
+++ b/tools/find-commit-for-patch.py
@@ -0,0 +1,96 @@
+#!/usr/bin/env python
+# Copyright 2014 the V8 project authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+import argparse
+import subprocess
+import sys
+
+
+def GetArgs():
+  parser = argparse.ArgumentParser(
+      description="Finds a commit that a given patch can be applied to. "
+                  "Does not actually apply the patch or modify your checkout "
+                  "in any way.")
+  parser.add_argument("patch_file", help="Patch file to match")
+  parser.add_argument(
+      "--branch", "-b", default="origin/master", type=str,
+      help="Git tree-ish where to start searching for commits, "
+           "default: %(default)s")
+  parser.add_argument(
+      "--limit", "-l", default=500, type=int,
+      help="Maximum number of commits to search, default: %(default)s")
+  parser.add_argument(
+      "--verbose", "-v", default=False, action="store_true",

[Michael Achenbach, 2014/12/16 10:29:54]

nit: Could use python's logging module. Set it to log level info if verbose is
specified and use logging.info instead of print everywhere without the trailing
"if verbose:".

[Jakob Kummerow, 2014/12/16 13:51:31]

Acknowledged. IIUC this wouldn't provide observable improvement, though, so I'm
too lazy to do the change.

+      help="Print verbose output for your entertainment")
+  return parser.parse_args()
+
+
+def FindFilesInPatch(patch_file):
+  files = {}
+  next_file = ""
+  with open(patch_file) as patch:
+    for line in patch:
+      if line.startswith("diff --git "):

[Michael Achenbach, 2014/12/16 10:29:54]

Remark (no action required): This scans all lines - not only headers. It
wouldn't work if the text "diff --git" is included in the patched file's text
that surrounds a diff location. E.g. a file with test data for this script :)

[Jakob Kummerow, 2014/12/16 13:51:31]

Actually, I'm pretty sure it does work on all valid patch files, because the
check is for "startswith", and modified and context lines would start with "+",
"-", or " ".

[Michael Achenbach, 2014/12/16 13:56:18]

Ah - I didn't see the space in the beginning of the context lines... then it's
alright.

+        # diff --git a/src/objects.cc b/src/objects.cc

[Michael Achenbach, 2014/12/16 10:29:54]

The patch could have been made with the option --src-prefix or --dst-prefix
(e.g. to be patched into chromium/src/v8 or something). This script wouldn't
accept this. Maybe add a text to the assertion which explains the restriction.

[Jakob Kummerow, 2014/12/16 13:51:31]

I'd just say the first time someone encounters this limitation, they are welcome
to fix it. The script works for patches generated by "git cl upload" as well as
"git diff" (without special arguments).

+        words = line.split()
+        assert words[2].startswith("a/") and len(words[2]) > 2
+        next_file = words[2][2:]
+      elif line.startswith("index "):
+        # index add3e61..d1bbf6a 100644
+        hashes = line.split()[1]
+        old_hash = hashes.split("..")[0]
+        if old_hash.startswith("0000000"): continue  # Ignore new files.
+        files[next_file] = old_hash
+  return files
+
+
+def GetGitCommitHash(treeish):
+  cmd = ["git", "log", "-1", "--format=%H", treeish]
+  return subprocess.check_output(cmd).strip()
+
+
+def CountMatchingFiles(commit, files):
+  matched_files = 0
+  # Calling out to git once and parsing the result Python-side is faster
+  # than calling 'git ls-tree' for every file.
+  output = subprocess.check_output(["git", "ls-tree", "-r", commit])

[Michael Achenbach, 2014/12/16 10:29:54]

Possible improvement: This command accepts a list of paths. You could pass all
the paths in "files". Then all output must correspond to a file in files.

[Jakob Kummerow, 2014/12/16 13:51:31]

Done -- good idea!

+  for line in output.splitlines():
+    # 100644 blob c6d5daaa7d42e49a653f9861224aad0a0244b944      src/objects.cc
+    words = line.split()

[Michael Achenbach, 2014/12/16 10:29:54]

nit: You can assign more explicitely:
_, _, actual_hash, filename = line.split()

[Jakob Kummerow, 2014/12/16 13:51:31]

Done.

+    filename = words[3]
+    if filename in files:

[Michael Achenbach, 2014/12/16 10:29:54]

nit: possible optimization:
expected_hash = files.get(filename)
if expected_hash:
  ...

[Jakob Kummerow, 2014/12/16 13:51:31]

Acknowledged, but after your comment above, we don't need any check here any
more (filename is guaranteed to be in files).

+      expected_hash = files[filename]
+      actual_hash = words[2]
+      if actual_hash.startswith(expected_hash): matched_files += 1
+  return matched_files
+
+
+def FindFirstMatchingCommit(start, files, limit, verbose):
+  commit = GetGitCommitHash(start)
+  num_files = len(files)
+  if verbose: print(">>> Found %d files modified by patch." % num_files)
+  while limit > 0:

[Michael Achenbach, 2014/12/16 10:29:54]

nit: Maybe: for _ in range(limit):

[Jakob Kummerow, 2014/12/16 13:51:31]

Done.

+    limit -= 1
+    matched_files = CountMatchingFiles(commit, files)
+    if verbose: print("Commit %s matched %d files" % (commit, matched_files))
+    if matched_files == num_files:
+      return commit
+    commit = GetGitCommitHash("%s^" % commit)
+  print("Sorry, no matching commit found. "
+        "Try running 'git fetch', specifying the correct --branch, "
+        "and/or setting a higher --limit.")
+  sys.exit(1)
+
+
+if __name__ == "__main__":
+  args = GetArgs()
+  files = FindFilesInPatch(args.patch_file)
+  commit = FindFirstMatchingCommit(args.branch, files, args.limit, args.verbose)
+  if args.verbose:
+    print(">>> Matching commit: %s" % commit)
+    print(subprocess.check_output(["git", "log", "-1", commit]))
+    print(">>> Kthxbai.")
+  else:
+    print(commit)