[PATCH] rebase: rebase changesets with branch grouped

[Xidorn Quan]

# HG changeset patch
# User Xidorn Quan <me at upsuper.org>
# Date 1474095776 -36000
#      Sat Sep 17 17:02:56 2016 +1000
# Node ID 88184dc23ccacfc8ae450abc5d574b8b028bca79
# Parent  285a8c3e53f2183438f0cdbc238e4ab851d0d110
rebase: rebase changesets with branch grouped

diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -330,18 +330,38 @@ class rebaseruntime(object):
                                                                inclusive=True)
 
         # Keep track of the current bookmarks in order to reset them later
         self.currentbookmarks = repo._bookmarks.copy()
         self.activebookmark = self.activebookmark or repo._activebookmark
         if self.activebookmark:
             bookmarks.deactivate(repo)
 
-        sortedrevs = sorted(self.state)
+        # Sort revisions with branches grouped
         cands = [k for k, v in self.state.iteritems() if v == revtodo]
+        remainrevs = set(self.state.iterkeys())
+        sortedrevs = []
+        # Sort based on candidates and put their ancestors with them
+        for cand in util.branchsorted(repo, cands):
+            ancestors = [cand]
+            remainrevs.remove(cand)
+            i = 0
+            while i < len(ancestors):
+                ctx = repo[ancestors[i]]
+                for p in ctx.parents():
+                    prev = p.rev()
+                    if prev in remainrevs:
+                        remainrevs.remove(prev)
+                        ancestors.append(prev)
+                i += 1
+            ancestors.reverse()
+            sortedrevs.extend(ancestors)
+        # Finally, descendents which are not rebased
+        sortedrevs.extend(sorted(remainrevs))
+
         total = len(cands)
         pos = 0
         for rev in sortedrevs:
             ctx = repo[rev]
             desc = '%d:%s "%s"' % (ctx.rev(), ctx,
                                    ctx.description().split('\n', 1)[0])
             names = repo.nodetags(ctx.node()) + repo.nodebookmarks(ctx.node())
             if names:
diff --git a/mercurial/util.py b/mercurial/util.py
--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -2897,8 +2897,33 @@ decompressors = {None: lambda fh: fh,
                  'BZ': _makedecompressor(lambda: bz2.BZ2Decompressor()),
                  'GZ': _makedecompressor(lambda: zlib.decompressobj()),
                  }
 # also support the old form by courtesies
 decompressors['UN'] = decompressors[None]
 
 # convenient shortcut
 dst = debugstacktrace
+
+def branchsorted(repo, revs, sortrevs=None):
+    '''Returns a sorted list of revisions in a order that branches are
+    grouped together.'''
+    remainrevs = set(revs)
+    stack = [sorted(revs, reverse=True)]
+    result = []
+    while stack:
+        stacktop = stack[-1]
+        if not stacktop:
+            stack.pop()
+            continue
+        nextrev = stacktop.pop()
+        if nextrev not in remainrevs:
+            continue
+        ctx = repo[nextrev]
+        # If any of its parents is still in remainrevs, we can not put
+        # the changeset into result. We would traverse to it again when
+        # we resolve all its parents.
+        if any(p.rev() in remainrevs for p in ctx.parents()):
+            continue
+        remainrevs.remove(nextrev)
+        result.append(nextrev)
+        stack.append(sorted((c.rev() for c in ctx.children()), reverse=True))
+    return result
diff --git a/tests/test-rebase-branch-order.t b/tests/test-rebase-branch-order.t
new file mode 100644
--- /dev/null
+++ b/tests/test-rebase-branch-order.t
@@ -0,0 +1,89 @@
+  $ cat >> $HGRCPATH <<EOF
+  > [extensions]
+  > rebase=
+  > [alias]
+  > tglog=log -G --template "{rev}:{node|short} {desc}"
+  > EOF
+
+  $ hg init repo
+  $ cd repo
+
+  $ touch a
+  $ hg ci -Am A
+  adding a
+
+  $ touch b
+  $ hg ci -Am B
+  adding b
+
+  $ touch c
+  $ hg ci -Am C
+  adding c
+
+  $ hg up 1
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ touch d
+  $ hg ci -Am D
+  adding d
+  created new head
+
+  $ hg up 2
+  1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ touch e
+  $ hg ci -Am E
+  adding e
+
+  $ hg up 3
+  1 files updated, 0 files merged, 2 files removed, 0 files unresolved
+  $ touch f
+  $ hg ci -Am F
+  adding f
+
+  $ hg up 0
+  0 files updated, 0 files merged, 3 files removed, 0 files unresolved
+  $ touch g
+  $ hg ci -Am G
+  adding g
+  created new head
+
+  $ hg tglog
+  @  6:124bb27b6f28 G
+  |
+  | o  5:412b391de760 F
+  | |
+  | | o  4:82ae8dc7a9b7 E
+  | | |
+  | o |  3:ab709c9f7171 D
+  | | |
+  | | o  2:d84f5cfaaf14 C
+  | |/
+  | o  1:76035bbd54bd B
+  |/
+  o  0:216878401574 A
+  
+
+Test rebasing is done with commits in branch grouped together.
+
+  $ hg rebase -s 1 -d 6
+  rebasing 1:76035bbd54bd "B"
+  rebasing 2:d84f5cfaaf14 "C"
+  rebasing 4:82ae8dc7a9b7 "E"
+  rebasing 3:ab709c9f7171 "D"
+  rebasing 5:412b391de760 "F"
+  saved backup bundle to $TESTTMP/repo/.hg/strip-backup/76035bbd54bd-e341bc99-backup.hg (glob)
+
+  $ hg tglog
+  o  6:31884cfb735e F
+  |
+  o  5:6d89fa5b0909 D
+  |
+  | o  4:de64d97c697b E
+  | |
+  | o  3:b18e4d2d0aa1 C
+  |/
+  o  2:0983daf9ff6a B
+  |
+  @  1:124bb27b6f28 G
+  |
+  o  0:216878401574 A
+