Reland "gclient_scm: Use cherry-picking instead of rebasing."

The failures were caused by:
 1 - When one change (call it #2) has been uploaded on top of another (#1),
     and (#1) has already landed, git cherry-pick complains that the range
     '<merge-base>..<change #2>' contains empty commits, since the contents
     of (#1) are already present in the tree.
 2 - We did not abort the cherry-picking when 'git cherry-pick' failed,
     so a failure made all further CLs in that bot fail.

This CL fixes it and prevents further regressions.

Original change's description:
> gclient_scm: Use cherry-picking instead of rebasing.
>
> Currently gclient might include extra commits when applying patches.
> For example, in this case we checkout |patch| and rebase it on top of |base|,
> thus including an |extra commit| that we shouldn't.
>
> o master
> |
> . o patch
> |/
> o extra commit
> |
> o base (what gclient synced src at)
>
> This change uses the merge-base between |patch| and |master| to cherry-pick only
> the changes belonging to the patch.
>
> Bug: 850812
> Change-Id: I138192f96bc62b1bb19b0e1ad952c8f8c67631c4
> Reviewed-on: https://chromium-review.googlesource.com/1137052
> Commit-Queue: Edward Lesmes <ehmaldonado@chromium.org>
> Reviewed-by: Aaron Gable <agable@chromium.org>

Bug: 850812
Change-Id: I83f38d0a258df3f5cd89e277f0d648badff29a22
Reviewed-on: https://chromium-review.googlesource.com/1139554
Reviewed-by: Aaron Gable <agable@chromium.org>
Commit-Queue: Edward Lesmes <ehmaldonado@chromium.org>
diff --git a/gclient_scm.py b/gclient_scm.py
index 76b1fb5..f1a7862 100644
--- a/gclient_scm.py
+++ b/gclient_scm.py
@@ -345,29 +345,71 @@
               self.Print('FAILED to break lock: %s: %s' % (to_break, ex))
               raise
 
+  def _GetBranchForCommit(self, commit):
+    """Get the remote branch a commit is part of."""
+    if scm.GIT.IsAncestor(self.checkout_path, commit,
+                          'refs/remotes/origin/master'):
+      return 'refs/remotes/origin/master'
+    remote_refs = self._Capture(
+        ['for-each-ref', 'refs/remotes/%s/*' % self.remote,
+         '--format=%(refname)']).splitlines()
+    for ref in remote_refs:
+      if scm.GIT.IsAncestor(self.checkout_path, commit, ref):
+        return ref
+    self.Print('Failed to find a remote ref that contains %s. '
+               'Candidate refs were %s.' % (commit, remote_refs))
+    # Fallback to the commit we got.
+    # This means that apply_path_ref will try to find the merge-base between the
+    # patch and the commit (which is most likely the commit) and cherry-pick
+    # everything in between.
+    return commit
+
   def apply_patch_ref(self, patch_repo, patch_ref, options, file_list):
     base_rev = self._Capture(['rev-parse', 'HEAD'])
+    branch_rev = self._GetBranchForCommit(base_rev)
     self.Print('===Applying patch ref===')
-    self.Print('Repo is %r @ %r, ref is %r, root is %r' % (
-        patch_repo, patch_ref, base_rev, self.checkout_path))
+    self.Print('Repo is %r @ %r, ref is %r (%r), root is %r' % (
+        patch_repo, patch_ref, base_rev, branch_rev, self.checkout_path))
     self._Capture(['reset', '--hard'])
     self._Capture(['fetch', patch_repo, patch_ref])
-    if file_list is not None:
-      file_list.extend(self._GetDiffFilenames('FETCH_HEAD'))
-    self._Capture(['checkout', 'FETCH_HEAD'])
+    patch_rev = self._Capture(['rev-parse', 'FETCH_HEAD'])
 
-    if options.rebase_patch_ref:
-      try:
-        # TODO(ehmaldonado): Look into cherry-picking to avoid an expensive
-        # checkout + rebase.
-        self._Capture(['rebase', base_rev])
-      except subprocess2.CalledProcessError as e:
-        self.Print('Failed to apply %r @ %r to %r at %r' % (
-                patch_repo, patch_ref, base_rev, self.checkout_path))
-        self.Print('git returned non-zero exit status %s:\n%s' % (
-            e.returncode, e.stderr))
-        self._Capture(['rebase', '--abort'])
-        raise
+    try:
+      if not options.rebase_patch_ref:
+        self._Capture(['checkout', patch_rev])
+      else:
+        # Find the merge-base between the branch_rev and patch_rev to find out
+        # the changes we need to cherry-pick on top of base_rev.
+        merge_base = self._Capture(['merge-base', branch_rev, patch_rev])
+        self.Print('Merge base of %s and %s is %s' % (
+            branch_rev, patch_rev, merge_base))
+        if merge_base == patch_rev:
+          # If the merge-base is patch_rev, it means patch_rev is already part
+          # of the history, so just check it out.
+          self._Capture(['checkout', patch_rev])
+        else:
+          # If a change was uploaded on top of another change, which has already
+          # landed, one of the commits in the cherry-pick range will be
+          # redundant, since it has already landed and its changes incorporated
+          # in the tree.
+          # We pass '--keep-redundant-commits' to ignore those changes.
+          self._Capture(['cherry-pick', merge_base + '..' + patch_rev,
+                         '--keep-redundant-commits'])
+
+      if file_list is not None:
+        file_list.extend(self._GetDiffFilenames(base_rev))
+
+    except subprocess2.CalledProcessError as e:
+      self.Print('Failed to apply %r @ %r to %r at %r' % (
+              patch_repo, patch_ref, base_rev, self.checkout_path))
+      self.Print('git returned non-zero exit status %s:\n%s' % (
+          e.returncode, e.stderr))
+      # Print the current status so that developers know what changes caused the
+      # patch failure, since git cherry-pick doesn't show that information.
+      self.Print(self._Capture(['status']))
+      self._Capture(['cherry-pick', '--abort'])
+      raise
+
     if options.reset_patch_ref:
       self._Capture(['reset', '--soft', base_rev])