D470: rebase: sort destmap topologically
quark (Jun Wu)
phabricator at mercurial-scm.org
Wed Aug 30 02:02:19 EDT 2017
This revision was automatically updated to reflect the committed changes.
Closed by commit rHG32528419db64: rebase: sort destmap topologically (authored by quark).
CHANGED PRIOR TO COMMIT
https://phab.mercurial-scm.org/D470?vs=1419&id=1427#toc
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D470?vs=1419&id=1427
REVISION DETAIL
https://phab.mercurial-scm.org/D470
AFFECTED FILES
hgext/rebase.py
tests/test-rebase-dest.t
tests/test-rebase-named-branches.t
tests/test-rebase-scenario-global.t
CHANGE DETAILS
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
@@ -264,7 +264,7 @@
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:
diff --git a/tests/test-rebase-named-branches.t b/tests/test-rebase-named-branches.t
--- a/tests/test-rebase-named-branches.t
+++ b/tests/test-rebase-named-branches.t
@@ -245,7 +245,7 @@
@ 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
diff --git a/tests/test-rebase-dest.t b/tests/test-rebase-dest.t
--- a/tests/test-rebase-dest.t
+++ b/tests/test-rebase-dest.t
@@ -204,7 +204,7 @@
> |
> Z
> EOS
- abort: source is ancestor of destination
+ abort: source and destination form a cycle
[255]
Switch roots:
@@ -291,22 +291,163 @@
|/
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
+
diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -361,7 +361,7 @@
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 @@
# 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 @@
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 | ...
|/ |/
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 @@
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 @@
'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 @@
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 @@
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)
To: quark, #hg-reviewers
Cc: martinvonz, mercurial-devel
More information about the Mercurial-devel
mailing list