rebase: sort destmap topologically

Previously rebase source and destination could not overlap. But with the
multi-destination support, source and destination could reasonably partially
overlap. That requires another topological sort on `{sourcerev: destrev}`
graph (destmap). This patch implements that.

If a revision's destination is itself, the error message gets changed from
"source is ancestor of destination" to "source and destination form a
cycle". Not marking as BC since automation should depend on exit code, not
error message.

Differential Revision: https://phab.mercurial-scm.org/D470

hgext/rebase.py

@@ -361,7 +361,7 b' class rebaseruntime(object):'
                 self.ui.status(_('reopening closed branch head %s\n') % dest)
 
     def _performrebase(self, tr):
-        repo, ui, opts = self.repo, self.ui, self.opts
+        repo, ui = self.repo, self.ui
         if self.keepbranchesf:
             # insert _savebranch at the start of extrafns so if
             # there's a user-provided extrafn it can clobber branch if
@@ -384,10 +384,17 b' class rebaseruntime(object):'
         # if we fail before the transaction closes.
         self.storestatus()
 
-        sortedrevs = repo.revs('sort(%ld, -topo)', self.state)
         cands = [k for k, v in self.state.iteritems() if v == revtodo]
         total = len(cands)
         pos = 0
+        for subset in sortsource(self.destmap):
+            pos = self._performrebasesubset(tr, subset, pos, total)
+        ui.progress(_('rebasing'), None)
+        ui.note(_('rebase merging completed\n'))
+
+    def _performrebasesubset(self, tr, subset, pos, total):
+        repo, ui, opts = self.repo, self.ui, self.opts
+        sortedrevs = repo.revs('sort(%ld, -topo)', subset)
         for rev in sortedrevs:
             dest = self.destmap[rev]
             ctx = repo[rev]
@@ -449,9 +456,7 b' class rebaseruntime(object):'
             else:
                 ui.status(_('already rebased %s as %s\n') %
                           (desc, repo[self.state[rev]]))
-
-        ui.progress(_('rebasing'), None)
-        ui.note(_('rebase merging completed\n'))
+        return pos
 
     def _finishrebase(self):
         repo, ui, opts = self.repo, self.ui, self.opts
@@ -969,6 +974,18 b' def adjustdest(repo, rev, destmap, state'
         | B         | ...
         |/          |/
         A           A
+
+    Besides, adjust dest according to existing rebase information. For example,
+
+      B C D    B needs to be rebased on top of C, C needs to be rebased on top
+       \|/     of D. We will rebase C first.
+        A
+
+          C'   After rebasing C, when considering B's destination, use C'
+          |    instead of the original C.
+      B   D
+       \ /
+        A
     """
     # pick already rebased revs with same dest from state as interesting source
     dest = destmap[rev]
@@ -981,6 +998,12 b' def adjustdest(repo, rev, destmap, state'
             candidate = repo.revs('max(%ld and (::%d))', source, prev).first()
             if candidate is not None:
                 adjusted = state[candidate]
+        if adjusted == dest and dest in state:
+            adjusted = state[dest]
+            if adjusted == revtodo:
+                # sortsource should produce an order that makes this impossible
+                raise error.ProgrammingError(
+                    'rev %d should be rebased already at this time' % dest)
         result.append(adjusted)
     return result
 
@@ -1128,6 +1151,12 b' def defineparents(repo, rev, destmap, st'
                                 'moving at least one of its parents')
                               % (rev, repo[rev]))
 
+    # Source should not be ancestor of dest. The check here guarantees it's
+    # impossible. With multi-dest, the initial check does not cover complex
+    # cases since we don't have abstractions to dry-run rebase cheaply.
+    if any(p != nullrev and isancestor(rev, p) for p in newps):
+        raise error.Abort(_('source is ancestor of destination'))
+
     # "rebasenode" updates to new p1, use the corresponding merge base.
     if bases[0] != nullrev:
         base = bases[0]
@@ -1354,6 +1383,31 b' def abort(repo, originalwd, destmap, sta'
         repo.ui.warn(_('rebase aborted\n'))
     return 0
 
+def sortsource(destmap):
+    """yield source revisions in an order that we only rebase things once
+
+    If source and destination overlaps, we should filter out revisions
+    depending on other revisions which hasn't been rebased yet.
+
+    Yield a sorted list of revisions each time.
+
+    For example, when rebasing A to B, B to C. This function yields [B], then
+    [A], indicating B needs to be rebased first.
+
+    Raise if there is a cycle so the rebase is impossible.
+    """
+    srcset = set(destmap)
+    while srcset:
+        srclist = sorted(srcset)
+        result = []
+        for r in srclist:
+            if destmap[r] not in srcset:
+                result.append(r)
+        if not result:
+            raise error.Abort(_('source and destination form a cycle'))
+        srcset -= set(result)
+        yield result
+
 def buildstate(repo, destmap, collapse, obsoletenotrebased):
     '''Define which revisions are going to be rebased and where
 
@@ -1372,12 +1426,21 b' def buildstate(repo, destmap, collapse, '
         if set(destmap.values()) & mqapplied:
             raise error.Abort(_('cannot rebase onto an applied mq patch'))
 
-    roots = list(repo.set('roots(%ld)', rebaseset))
+    # Get "cycle" error early by exhausting the generator.
+    sortedsrc = list(sortsource(destmap)) # a list of sorted revs
+    if not sortedsrc:
+        raise error.Abort(_('no matching revisions'))
+
+    # Only check the first batch of revisions to rebase not depending on other
+    # rebaseset. This means "source is ancestor of destination" for the second
+    # (and following) batches of revisions are not checked here. We rely on
+    # "defineparents" to do that check.
+    roots = list(repo.set('roots(%ld)', sortedsrc[0]))
     if not roots:
         raise error.Abort(_('no matching revisions'))
     roots.sort()
     state = dict.fromkeys(rebaseset, revtodo)
-    emptyrebase = True
+    emptyrebase = (len(sortedsrc) == 1)
     for root in roots:
         dest = repo[destmap[root.rev()]]
         commonbase = root.ancestor(dest)

tests/test-rebase-dest.t

@@ -204,7 +204,7 b' Destination is an ancestor of source:'
   > |
   > Z
   > EOS
-  abort: source is ancestor of destination
+  abort: source and destination form a cycle
   [255]
 
 Switch roots:
@@ -291,22 +291,163 b' Move to a previous parent:'
   |/
   o  0: A
   
-Source overlaps with destination (not handled well currently):
+Source overlaps with destination:
 
   $ rebasewithdag -s 'B+C+D' -d 'map(SRC, "B:C,C:D")' <<'EOS'
   > B C D
   >  \|/
   >   A
   > EOS
+  rebasing 2:dc0947a82db8 "C" (C)
   rebasing 1:112478962961 "B" (B)
-  rebasing 2:dc0947a82db8 "C" (C)
-  o  5: C
+  o  5: B
+  |
+  o  4: C
+  |
+  o  3: D
+  |
+  o  0: A
+  
+Detect cycles early:
+
+  $ rebasewithdag -r 'all()-Z' -d 'map(SRC, "A:B,B:C,C:D,D:B")' <<'EOS'
+  > A B C
+  >  \|/
+  >   | D
+  >   |/
+  >   Z
+  > EOS
+  abort: source and destination form a cycle
+  [255]
+
+Detect source is ancestor of dest in runtime:
+
+  $ rebasewithdag -r 'C+B' -d 'map(SRC, "C:B,B:D")' -q <<'EOS'
+  >   D
+  >   |
+  > B C
+  >  \|
+  >   A
+  > EOS
+  abort: source is ancestor of destination
+  [255]
+
+"Already rebased" fast path still works:
+
+  $ rebasewithdag -r 'all()' -d 'SRC^' <<'EOS'
+  >   E F
+  >  /| |
+  > B C D
+  >  \|/
+  >   A
+  > EOS
+  already rebased 1:112478962961 "B" (B)
+  already rebased 2:dc0947a82db8 "C" (C)
+  already rebased 3:b18e25de2cf5 "D" (D)
+  already rebased 4:312782b8f06e "E" (E)
+  already rebased 5:ad6717a6a58e "F" (F tip)
+  o  5: F
   |
   o  3: D
   |
-  | o  4: B orphan
+  | o    4: E
+  | |\
+  +---o  2: C
   | |
-  | x  2: C
+  | o  1: B
   |/
   o  0: A
   
+Massively rewrite the DAG:
+
+  $ rebasewithdag -r 'all()' -d 'map(SRC, "A:I,I:null,H:A,B:J,J:C,C:H,D:E,F:G,G:K,K:D,E:B")' <<'EOS'
+  > D G K
+  > | | |
+  > C F J
+  > | | |
+  > B E I
+  >  \| |
+  >   A H
+  > EOS
+  rebasing 4:701514e1408d "I" (I)
+  rebasing 0:426bada5c675 "A" (A)
+  rebasing 1:e7050b6e5048 "H" (H)
+  rebasing 5:26805aba1e60 "C" (C)
+  rebasing 7:cf89f86b485b "J" (J)
+  rebasing 2:112478962961 "B" (B)
+  rebasing 3:7fb047a69f22 "E" (E)
+  rebasing 8:f585351a92f8 "D" (D)
+  rebasing 10:ae41898d7875 "K" (K tip)
+  rebasing 9:711f53bbef0b "G" (G)
+  rebasing 6:64a8289d2492 "F" (F)
+  o  21: F
+  |
+  o  20: G
+  |
+  o  19: K
+  |
+  o  18: D
+  |
+  o  17: E
+  |
+  o  16: B
+  |
+  o  15: J
+  |
+  o  14: C
+  |
+  o  13: H
+  |
+  o  12: A
+  |
+  o  11: I
+  
+Resolve instability:
+
+  $ rebasewithdag <<'EOF' -r 'orphan()-obsolete()' -d 'max((successors(max(roots(ALLSRC) & ::SRC)^)-obsolete())::)'
+  >      F2
+  >      |
+  >    J E E2
+  >    | |/
+  > I2 I | E3
+  >   \| |/
+  >    H | G
+  >    | | |
+  >   B2 D F
+  >    | |/         # rebase: B -> B2
+  >    N C          # amend: E -> E2
+  >    | |          # amend: E2 -> E3
+  >    M B          # rebase: F -> F2
+  >     \|          # amend: I -> I2
+  >      A
+  > EOF
+  rebasing 16:5c432343bf59 "J" (J tip)
+  rebasing 3:26805aba1e60 "C" (C)
+  rebasing 6:f585351a92f8 "D" (D)
+  rebasing 10:ffebc37c5d0b "E3" (E3)
+  rebasing 13:fb184bcfeee8 "F2" (F2)
+  rebasing 11:dc838ab4c0da "G" (G)
+  o  22: G
+  |
+  o  21: F2
+  |
+  o  20: E3
+  |
+  o  19: D
+  |
+  o  18: C
+  |
+  o  17: J
+  |
+  o  15: I2
+  |
+  o  12: H
+  |
+  o  5: B2
+  |
+  o  4: N
+  |
+  o  2: M
+  |
+  o  0: A
+  

tests/test-rebase-named-branches.t

@@ -245,7 +245,7 b' Rebasing descendant onto ancestor across'
   @  0: 'A'
   
   $ hg rebase -s 5 -d 6
-  abort: source is ancestor of destination
+  abort: source and destination form a cycle
   [255]
 
   $ hg rebase -s 6 -d 5

tests/test-rebase-scenario-global.t

@@ -264,7 +264,7 b' G onto F - rebase onto an ancestor:'
 F onto G - rebase onto a descendant:
 
   $ hg rebase -s 5 -d 6
-  abort: source is ancestor of destination
+  abort: source and destination form a cycle
   [255]
 
 G onto B - merge revision with both parents not in ancestors of target: