[PATCH 2 of 2] rebase: rebase changesets in topo order (issue5370) (BC)

[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 ab4345ac56a1c05de048e677dc4af38ff0e8ff79
# Parent  9e8aeaddddf3bf6e61b351a738f5cadbbf4815f3
rebase: rebase changesets in topo order (issue5370) (BC)

There are two reasons that rebase should be done this way:
1. This would make rebasing faster because it would minimize the total
   number of files to be checked out in the process, as it don't need
   to switch back and forth between branches.
2. It makes resolving conflicts easier as user has a better context.

diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -330,18 +330,39 @@ 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 repo.revs('sort(%ld, -topo, topo.revsonly=1)',
+                              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/tests/test-rebase-scenario-global.t b/tests/test-rebase-scenario-global.t
--- a/tests/test-rebase-scenario-global.t
+++ b/tests/test-rebase-scenario-global.t
@@ -756,16 +756,79 @@ Test that rebase is not confused by $CWD
   $ touch subfile
   $ hg add subfile
   $ hg commit -m 'second source with subdir'
   $ hg rebase -b . -d 1 --traceback
   rebasing 2:779a07b1b7a0 "first source commit"
   rebasing 3:a7d6f3a00bf3 "second source with subdir" (tip)
   saved backup bundle to $TESTTMP/cwd-vanish/.hg/strip-backup/779a07b1b7a0-853e0073-backup.hg (glob)
 
+Test that rebase is done in topo order (issue5370)
+
+  $ cd ..
+  $ hg init order
+  $ cd order
+  $ touch a && hg add a && hg ci -m A
+  $ touch b && hg add b && hg ci -m B
+  $ touch c && hg add c && hg ci -m C
+  $ hg up 1
+  0 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ touch d && hg add d && hg ci -m D
+  created new head
+  $ hg up 2
+  1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+  $ touch e && hg add e && hg ci -m E
+  $ hg up 3
+  1 files updated, 0 files merged, 2 files removed, 0 files unresolved
+  $ touch f && hg add f && hg ci -m F
+  $ hg up 0
+  0 files updated, 0 files merged, 3 files removed, 0 files unresolved
+  $ touch g && hg add g && hg ci -m G
+  created new head
+
+  $ hg tglog
+  @  6: 'G'
+  |
+  | o  5: 'F'
+  | |
+  | | o  4: 'E'
+  | | |
+  | o |  3: 'D'
+  | | |
+  | | o  2: 'C'
+  | |/
+  | o  1: 'B'
+  |/
+  o  0: 'A'
+  
+
+  $ 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/cwd-vanish/order/.hg/strip-backup/76035bbd54bd-e341bc99-backup.hg (glob)
+
+  $ hg tglog
+  o  6: 'F'
+  |
+  o  5: 'D'
+  |
+  | o  4: 'E'
+  | |
+  | o  3: 'C'
+  |/
+  o  2: 'B'
+  |
+  @  1: 'G'
+  |
+  o  0: 'A'
+  
+
 Test experimental revset
 ========================
 
   $ cd ..
 
 Make the repo a bit more interresting
 
   $ hg up 1