LLVM tools: Added support for bisection of patches

Changed 'get_google3_llvm_version.py' and 'get_llvm_hash.py' to use the
subprocess module instead of the command executer because the patch
manager script uses some methods for bisection (retrieving the good and
bad hash). They were also changed because the ebuilds will not have
access to the command executer when invoking the patch manager script.

BUG=None
TEST=Ran the script on SVN version of 367622 without continuing
bisection and successfully bisected the failed patch and terminated the
script. Then moved HEAD of source tree to the bisected SVN version and
applied the patch manually to test correctness and also moved HEAD to
the SVN version one above it and one below it and also manually applied
the patch.

Change-Id: I2367b76e9bb4d0c95d651ec7b3f66e582155d2c7
Reviewed-on: https://chromium-review.googlesource.com/c/chromiumos/third_party/toolchain-utils/+/1752526
Tested-by: Salud Lemus <saludlemus@google.com>
Reviewed-by: Manoj Gupta <manojgupta@chromium.org>

1 files changed, 333 insertions, 21 deletions

diff --git a/llvm_tools/patch_manager.py b/llvm_tools/patch_manager.py
index eae8d5e2..14e5058d 100755
--- a/llvm_tools/patch_manager.py
+++ b/llvm_tools/patch_manager.py
@@ -12,9 +12,11 @@ import argparse
 import json
 import os
 import subprocess
+import sys
 
 from collections import namedtuple
 from failure_modes import FailureModes
+from get_llvm_hash import LLVMHash
 
 
 def is_directory(dir_path):
@@ -40,18 +42,64 @@ def is_patch_metadata_file(patch_metadata_file):
   return patch_metadata_file
 
 
+def is_valid_failure_mode(failure_mode):
+  """Validates that the failure mode passed in is correct."""
+
+  cur_failure_modes = [mode.value for mode in FailureModes]
+
+  if failure_mode not in cur_failure_modes:
+    raise ValueError('Invalid failure mode provided: %s' % failure_mode)
+
+  return failure_mode
+
+
+def EnsureBisectModeAndSvnVersionAreSpecifiedTogether(failure_mode,
+                                                      good_svn_version):
+  """Validates that 'good_svn_version' is passed in only for bisection."""
+
+  if failure_mode != FailureModes.BISECT_PATCHES.value and good_svn_version:
+    raise ValueError('\'good_svn_version\' is only available for bisection.')
+  elif failure_mode == FailureModes.BISECT_PATCHES.value and \
+      not good_svn_version:
+    raise ValueError('A good SVN version is required for bisection (used by'
+                     '\'git bisect start\'.')
+
+
 def GetCommandLineArgs():
   """Get the required arguments from the command line."""
 
   # Create parser and add optional command-line arguments.
   parser = argparse.ArgumentParser(description='A manager for patches.')
 
+  # Add argument for the last good SVN version which is required by
+  # `git bisect start` (only valid for bisection mode).
+  parser.add_argument(
+      '--good_svn_version',
+      type=int,
+      help='INTERNAL USE ONLY... (used for bisection.)')
+
+  # Add argument for the number of patches it iterate. Only used when performing
+  # `git bisect run`.
+  parser.add_argument(
+      '--num_patches_to_iterate', type=int, help=argparse.SUPPRESS)
+
+  # Add argument for whether bisection should continue. Only used for
+  # 'bisect_patches.'
+  parser.add_argument(
+      '--continue_bisection',
+      type=bool,
+      default=False,
+      help='Determines whether bisection should continue after successfully '
+      'bisecting a patch (default: %(default)s) - only used for '
+      '\'bisect_patches\'')
+
   # Add argument for the LLVM version to use for patch management.
   parser.add_argument(
       '--svn_version',
       type=int,
       required=True,
-      help='the LLVM svn version to use for patch management')
+      help='the LLVM svn version to use for patch management (determines '
+      'whether a patch is applicable)')
 
   # Add argument for the patch metadata file that is in $FILESDIR.
   parser.add_argument(
@@ -81,16 +129,43 @@ def GetCommandLineArgs():
   parser.add_argument(
       '--failure_mode',
       default=FailureModes.FAIL.value,
-      choices=[mode.value for mode in FailureModes],
+      type=is_valid_failure_mode,
       help='the mode of the patch manager when handling failed patches ' \
           '(default: %(default)s)')
 
   # Parse the command line.
   args_output = parser.parse_args()
 
+  EnsureBisectModeAndSvnVersionAreSpecifiedTogether(
+      args_output.failure_mode, args_output.good_svn_version)
+
   return args_output
 
 
+def GetHEADSVNVersion(src_path):
+  """Gets the SVN version of HEAD in the src tree."""
+
+  get_head_cmd = ['git', '-C', src_path, 'log', '-1', '--pretty=%B']
+
+  head_commit_message = subprocess.check_output(get_head_cmd)
+
+  head_svn_version = LLVMHash().GetSVNVersionFromCommitMessage(
+      head_commit_message)
+
+  return head_svn_version
+
+
+def VerifyHEADIsTheSameAsSVNVersion(src_path, svn_version):
+  """Verifies that HEAD's SVN version matches 'svn_version'."""
+
+  head_svn_version = GetHEADSVNVersion(src_path)
+
+  if head_svn_version != svn_version:
+    raise ValueError('HEAD\'s SVN version %d does not match \'svn_version\''
+                     ' %d, please move HEAD to \'svn_version\'s\' git hash.' %
+                     (head_svn_version, svn_version))
+
+
 def GetPathToPatch(filesdir_path, rel_patch_path):
   """Gets the absolute path to a patch in $FILESDIR.
 
@@ -215,8 +290,101 @@ def _ConvertToASCII(obj):
   return obj
 
 
-def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
-                  mode):
+def GetCommitHashesForBisection(src_path, good_svn_version, bad_svn_version):
+  """Gets the good and bad commit hashes required by `git bisect start`."""
+
+  new_llvm_hash = LLVMHash()
+
+  bad_commit_hash = new_llvm_hash.GetGitHashForVersion(src_path,
+                                                       bad_svn_version)
+
+  good_commit_hash = new_llvm_hash.GetGitHashForVersion(src_path,
+                                                        good_svn_version)
+
+  return good_commit_hash, bad_commit_hash
+
+
+def PerformBisection(src_path, good_commit, bad_commit, svn_version,
+                     patch_metadata_file, filesdir_path, num_patches):
+  """Performs bisection to determine where a patch stops applying."""
+
+  bisect_start_cmd = [
+      'git', '-C', src_path, 'bisect', 'start', bad_commit, good_commit
+  ]
+
+  subprocess.check_output(bisect_start_cmd)
+
+  bisect_run_cmd = [
+      'git', '-C', src_path, 'bisect', 'run',
+      os.path.abspath(__file__), '--svn_version',
+      '%d' % svn_version, '--patch_metadata_file', patch_metadata_file,
+      '--filesdir_path', filesdir_path, '--src_path', src_path,
+      '--failure_mode', 'internal_bisection', '--num_patches_to_iterate',
+      '%d' % num_patches
+  ]
+
+  subprocess.check_call(bisect_run_cmd)
+
+  # Successfully bisected the patch, so retrieve the SVN version from the
+  # commit message.
+  get_bad_commit_from_bisect_run_cmd = [
+      'git', '-C', src_path, 'show', 'refs/bisect/bad'
+  ]
+
+  bad_commit_message = subprocess.check_output(
+      get_bad_commit_from_bisect_run_cmd)
+
+  end_bisection_cmd = ['git', '-C', src_path, 'bisect', 'reset']
+
+  subprocess.check_output(end_bisection_cmd)
+
+  # `git bisect run` returns the bad commit hash and the commit message.
+  bad_version = LLVMHash().GetSVNVersionFromCommitMessage(
+      bad_commit_message.rstrip())
+
+  return bad_version
+
+
+def CleanSrcTree(src_path):
+  """Cleans the source tree of the changes made in 'src_path'."""
+
+  reset_src_tree_cmd = ['git', '-C', src_path, 'reset', 'HEAD', '--hard']
+
+  subprocess.check_output(reset_src_tree_cmd)
+
+  clean_src_tree_cmd = ['git', '-C', src_path, 'clean', '-fd']
+
+  subprocess.check_output(clean_src_tree_cmd)
+
+
+def SaveSrcTreeState(src_path):
+  """Stashes the changes made so far to the source tree."""
+
+  save_src_tree_cmd = ['git', '-C', src_path, 'stash', '-a']
+
+  subprocess.check_output(save_src_tree_cmd)
+
+
+def RestoreSrcTreeState(src_path, bad_commit_hash):
+  """Restores the changes made to the source tree."""
+
+  checkout_cmd = ['git', '-C', src_path, 'checkout', bad_commit_hash]
+
+  subprocess.check_output(checkout_cmd)
+
+  get_changes_cmd = ['git', '-C', src_path, 'stash', 'pop']
+
+  subprocess.check_output(get_changes_cmd)
+
+
+def HandlePatches(svn_version,
+                  patch_metadata_file,
+                  filesdir_path,
+                  src_path,
+                  mode,
+                  good_svn_version=None,
+                  num_patches_to_iterate=None,
+                  continue_bisection=False):
   """Handles the patches in the .json file for the package.
 
   Args:
@@ -227,6 +395,13 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
     src_path: The absolute path to the unpacked destination of the package.
     mode: The action to take when an applicable patch failed to apply.
       Ex: 'FailureModes.FAIL'
+    good_svn_version: Only used by 'bisect_patches' which tells
+    `git bisect start` the good version.
+    num_patches_to_iterate: The number of patches to iterate in the .JSON file
+    (internal use). Only used by `git bisect run`.
+    continue_bisection: Only used for 'bisect_patches' mode. If flag is set,
+    then bisection will continue to the next patch when successfully bisected a
+    patch.
 
   Returns:
     Depending on the mode, 'None' would be returned if everything went well or
@@ -261,6 +436,9 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
   # A list of patches that were disabled.
   disabled_patches = []
 
+  # A list of bisected patches.
+  bisected_patches = []
+
   # A list of non applicable patches.
   non_applicable_patches = []
 
@@ -278,6 +456,11 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
   with open(patch_metadata_file) as patch_file:
     patch_file_contents = _ConvertToASCII(json.load(patch_file))
 
+    if mode == FailureModes.BISECT_PATCHES:
+      # A good and bad commit are required by `git bisect start`.
+      good_commit, bad_commit = GetCommitHashesForBisection(
+          src_path, good_svn_version, svn_version)
+
     # Patch format:
     # {
     #   "rel_patch_path" : "[REL_PATCH_PATH_FROM_$FILESDIR]"
@@ -286,7 +469,13 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
     #
     # For each patch, find the path to it in $FILESDIR and get its metadata if
     # available, then check if the patch is applicable.
-    for cur_patch_dict in patch_file_contents:
+    for patch_dict_index, cur_patch_dict in enumerate(patch_file_contents):
+      # Used by the internal bisection. All the patches in the interval [0, N]
+      # have been iterated.
+      if num_patches_to_iterate and \
+          (patch_dict_index + 1) > num_patches_to_iterate:
+        break
+
       # Get the absolute path to the patch in $FILESDIR.
       path_to_patch = GetPathToPatch(filesdir_path,
                                      cur_patch_dict['rel_patch_path'])
@@ -328,7 +517,9 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
       if not patch_applicable:
         non_applicable_patches.append(os.path.basename(path_to_patch))
 
-      # There is no need to apply patches in 'remove_patches' mode.
+      # There is no need to apply patches in 'remove_patches' mode because the
+      # mode removes patches that do not apply anymore based off of
+      # 'svn_version.'
       if patch_applicable and mode != FailureModes.REMOVE_PATCHES:
         patch_applied = ApplyPatch(src_path, path_to_patch)
 
@@ -354,10 +545,60 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
 
               modified_metadata = patch_metadata_file
           elif mode == FailureModes.BISECT_PATCHES:
-            # TODO (saludlemus): Complete this mode.
             # Figure out where the patch's stops applying and set the patch's
             # 'end_version' to that version.
-            pass
+
+            # Do not want to overwrite the changes to the current progress of
+            # 'bisect_patches' on the source tree.
+            SaveSrcTreeState(src_path)
+
+            # Need a clean source tree for `git bisect run` to avoid unnecessary
+            # fails for patches.
+            CleanSrcTree(src_path)
+
+            print('\nStarting to bisect patch %s for SVN version %d:\n' %
+                  (os.path.basename(cur_patch_dict['rel_patch_path']),
+                   svn_version))
+
+            # Performs the bisection: calls `git bisect start` and
+            # `git bisect run`, where `git bisect run` is going to call this
+            # script as many times as needed with specific arguments.
+            bad_svn_version = PerformBisection(
+                src_path, good_commit, bad_commit, svn_version,
+                patch_metadata_file, filesdir_path, patch_dict_index + 1)
+
+            print('\nSuccessfully bisected patch %s, starts to fail to apply '
+                  'at %d\n' % (os.path.basename(
+                      cur_patch_dict['rel_patch_path']), bad_svn_version))
+
+            # Overwrite the .JSON file with the new 'end_version' for the
+            # current failed patch so that if there are other patches that
+            # fail to apply, then the 'end_version' for the current patch could
+            # be applicable when `git bisect run` is performed on the next
+            # failed patch because the same .JSON file is used for `git bisect
+            # run`.
+            patch_file_contents[patch_dict_index][
+                'end_version'] = bad_svn_version
+            UpdatePatchMetadataFile(patch_metadata_file, patch_file_contents)
+
+            # Clear the changes made to the source tree by `git bisect run`.
+            CleanSrcTree(src_path)
+
+            if not continue_bisection:
+              # Exiting program early because 'continue_bisection' is not set.
+              sys.exit(0)
+
+            bisected_patches.append(
+                '%s starts to fail to apply at %d' % (os.path.basename(
+                    cur_patch_dict['rel_patch_path']), bad_svn_version))
+
+            # Continue where 'bisect_patches' left off.
+            RestoreSrcTreeState(src_path, bad_commit)
+
+            if not modified_metadata:
+              # At least one patch's 'end_version' has been updated.
+              modified_metadata = patch_metadata_file
+
           elif mode == FailureModes.FAIL:
             if applied_patches:
               print('The following patches applied successfully up to the '
@@ -367,9 +608,55 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
             # Throw an exception on the first patch that failed to apply.
             raise ValueError(
                 'Failed to apply patch: %s' % os.path.basename(path_to_patch))
+          elif mode == FailureModes.INTERNAL_BISECTION:
+            # Determine the exit status for `git bisect run` because of the
+            # failed patch in the interval [0, N].
+            #
+            # NOTE: `git bisect run` exit codes are as follows:
+            #   130: Terminates the bisection.
+            #   1: Similar as `git bisect bad`.
+
+            # Some patch in the interval [0, N) failed, so terminate bisection
+            # (the patch stack is broken).
+            if (patch_dict_index + 1) != num_patches_to_iterate:
+              print('\nTerminating bisection due to patch %s failed to apply '
+                    'on SVN version %d.\n' % (os.path.basename(
+                        cur_patch_dict['rel_patch_path']), svn_version))
+
+              # Man page for `git bisect run` states that any value over 127
+              # terminates it.
+              sys.exit(130)
+
+            # Changes to the source tree need to be removed, otherwise some
+            # patches may fail when applying the patch to the source tree when
+            # `git bisect run` calls this script again.
+            CleanSrcTree(src_path)
+
+            # The last patch in the interval [0, N] failed to apply, so let
+            # `git bisect run` know that the last patch (the patch that failed
+            # originally which led to `git bisect run` to be invoked) is bad
+            # with exit code 1.
+            sys.exit(1)
         else:  # Successfully applied patch
           applied_patches.append(os.path.basename(path_to_patch))
 
+  # All patches in the interval [0, N] applied successfully, so let
+  # `git bisect run` know that the program exited with exit code 0 (good).
+  if mode == FailureModes.INTERNAL_BISECTION:
+    # Changes to the source tree need to be removed, otherwise some
+    # patches may fail when applying the patch to the source tree when
+    # `git bisect run` calls this script again.
+    #
+    # Also, if `git bisect run` will NOT call this script again (terminated) and
+    # if the source tree changes are not removed, `git bisect reset` will
+    # complain that the changes would need to be 'stashed' or 'removed' in
+    # order to reset HEAD back to the bad commit's git hash, so HEAD will remain
+    # on the last git hash used by `git bisect run`.
+    CleanSrcTree(src_path)
+
+    # NOTE: Exit code 0 is similar to `git bisect good`.
+    sys.exit(0)
+
   # Create a namedtuple of the patch results.
   PatchInfo = namedtuple('PatchInfo', [
       'applied_patches', 'failed_patches', 'non_applicable_patches',
@@ -388,10 +675,19 @@ def HandlePatches(svn_version, patch_metadata_file, filesdir_path, src_path,
   if mode == FailureModes.REMOVE_PATCHES:
     if removed_patches:
       UpdatePatchMetadataFile(patch_metadata_file, applicable_patches)
-  elif mode == FailureModes.DISABLE_PATCHES or \
-      mode == FailureModes.BISECT_PATCHES:
+  elif mode == FailureModes.DISABLE_PATCHES:
     if updated_patch:
       UpdatePatchMetadataFile(patch_metadata_file, applicable_patches)
+  elif mode == FailureModes.BISECT_PATCHES:
+    PrintPatchResults(patch_info)
+    if modified_metadata:
+      print('\nThe following patches have been bisected:')
+      print('\n'.join(bisected_patches))
+
+    # Exiting early because 'bisect_patches' will not be called from other
+    # scripts, only this script uses 'bisect_patches'. The intent is to provide
+    # bisection information on the patches and aid in the bisection process.
+    sys.exit(0)
 
   return patch_info
 
@@ -404,41 +700,57 @@ def PrintPatchResults(patch_info):
   """
 
   if patch_info.applied_patches:
-    print('The following patches applied successfully:')
+    print('\nThe following patches applied successfully:')
     print('\n'.join(patch_info.applied_patches))
 
   if patch_info.failed_patches:
-    print('The following patches failed to apply:')
+    print('\nThe following patches failed to apply:')
     print('\n'.join(patch_info.failed_patches))
 
   if patch_info.non_applicable_patches:
-    print('The following patches were not applicable:')
+    print('\nThe following patches were not applicable:')
     print('\n'.join(patch_info.non_applicable_patches))
 
   if patch_info.modified_metadata:
-    print('The patch metadata file %s has been modified' % os.path.basename(
+    print('\nThe patch metadata file %s has been modified' % os.path.basename(
         patch_info.modified_metadata))
 
   if patch_info.disabled_patches:
-    print('The following patches were disabled:')
+    print('\nThe following patches were disabled:')
     print('\n'.join(patch_info.disabled_patches))
 
   if patch_info.removed_patches:
-    print('The following patches were removed from the patch metadata file:')
+    print('\nThe following patches were removed from the patch metadata file:')
     for cur_patch_path in patch_info.removed_patches:
       print('%s' % os.path.basename(cur_patch_path))
 
 
 def main():
-  """Applies the patches based off of the command line arguments."""
+  """Applies patches to the source tree and takes action on a failed patch."""
 
   args_output = GetCommandLineArgs()
 
+  if args_output.failure_mode != FailureModes.INTERNAL_BISECTION.value:
+    # If the SVN version of HEAD is not the same as 'svn_version', then some
+    # patches that fail to apply could successfully apply if HEAD's SVN version
+    # was the same as 'svn_version'. In other words, HEAD's git hash should be
+    # what is being updated to (e.g. LLVM_NEXT_HASH).
+    VerifyHEADIsTheSameAsSVNVersion(args_output.src_path,
+                                    args_output.svn_version)
+  else:
+    # `git bisect run` called this script.
+    #
+    # `git bisect run` moves HEAD each time it invokes this script, so set the
+    # 'svn_version' to be current HEAD's SVN version so that the previous
+    # SVN version is not used in determining whether a patch is applicable.
+    args_output.svn_version = GetHEADSVNVersion(args_output.src_path)
+
   # Get the results of handling the patches of the package.
-  patch_info = HandlePatches(args_output.svn_version,
-                             args_output.patch_metadata_file,
-                             args_output.filesdir_path, args_output.src_path,
-                             FailureModes(args_output.failure_mode))
+  patch_info = HandlePatches(
+      args_output.svn_version, args_output.patch_metadata_file,
+      args_output.filesdir_path, args_output.src_path,
+      FailureModes(args_output.failure_mode), args_output.good_svn_version,
+      args_output.num_patches_to_iterate, args_output.continue_bisection)
 
   PrintPatchResults(patch_info)