D21: rebase: rewrite core algorithm (issue5578) (issue5630)
quark (Jun Wu)
phabricator at mercurial-scm.org
Sun Aug 13 00:10:33 EDT 2017
quark updated this revision to Diff 829.
quark edited the summary of this revision.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D21?vs=765&id=829
REVISION DETAIL
https://phab.mercurial-scm.org/D21
AFFECTED FILES
hgext/rebase.py
tests/test-rebase-brute-force.t
tests/test-rebase-newancestor.t
tests/test-rebase-obsolete.t
CHANGE DETAILS
diff --git a/tests/test-rebase-obsolete.t b/tests/test-rebase-obsolete.t
--- a/tests/test-rebase-obsolete.t
+++ b/tests/test-rebase-obsolete.t
@@ -488,9 +488,14 @@
> A
> EOF
-BROKEN: This raises an exception
- $ hg rebase -d G -r 'B + D + F' 2>&1 | grep '^AssertionError'
- AssertionError: no base found to rebase on (defineparents called wrong)
+ $ hg rebase -d G -r 'B + D + F'
+ rebasing 1:112478962961 "B" (B)
+ rebasing 2:b18e25de2cf5 "D" (D)
+ not rebasing ignored 4:26805aba1e60 "C" (C)
+ not rebasing ignored 5:4b61ff5c62e2 "E" (E)
+ rebasing 6:f15c3adaf214 "F" (F tip)
+ abort: cannot use revision 6 as base, result would have 3 parents
+ [255]
$ cd ..
@@ -962,17 +967,19 @@
> A
> EOF
-BROKEN: Raises an exception
- $ hg rebase -d B -s E 2>&1 | grep AssertionError:
- AssertionError: no base found to rebase on (defineparents called wrong)
+ $ hg rebase -d B -s E
+ note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
+ rebasing 4:66f1a38021c9 "F" (F tip)
$ hg log -G
- o 4:66f1a38021c9 F
+ o 5:aae1787dacee F
|\
- | x 3:7fb047a69f22 E
- | |
- o | 2:b18e25de2cf5 D
- |/
- | o 1:112478962961 B
+ | | x 4:66f1a38021c9 F
+ | |/|
+ | | x 3:7fb047a69f22 E
+ | | |
+ | o | 2:b18e25de2cf5 D
+ | |/
+ o / 1:112478962961 B
|/
o 0:426bada5c675 A
@@ -994,19 +1001,19 @@
$ hg rebase -d C -s D
note: not rebasing 2:b18e25de2cf5 "D" (D), already in destination as 1:112478962961 "B"
rebasing 5:66f1a38021c9 "F" (F tip)
-BROKEN: not rebased on top of requested destination (C)
+
$ hg log -G
- o 6:50e9d60b99c6 F
+ o 6:0913febf6439 F
|\
- | | x 5:66f1a38021c9 F
- | |/|
- +-----o 4:26805aba1e60 C
+ +---x 5:66f1a38021c9 F
+ | | |
+ | o | 4:26805aba1e60 C
| | |
- | o | 3:7fb047a69f22 E
+ o | | 3:7fb047a69f22 E
| | |
- | | x 2:b18e25de2cf5 D
- | |/
- o | 1:112478962961 B
+ +---x 2:b18e25de2cf5 D
+ | |
+ | o 1:112478962961 B
|/
o 0:426bada5c675 A
@@ -1025,19 +1032,21 @@
> A
> EOF
-BROKEN: Raises an exception
- $ hg rebase -d C -s E 2>&1 | grep AssertionError:
- AssertionError: no base found to rebase on (defineparents called wrong)
+ $ hg rebase -d C -s E
+ note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
+ rebasing 5:66f1a38021c9 "F" (F tip)
$ hg log -G
- o 5:66f1a38021c9 F
+ o 6:c6ab0cc6d220 F
|\
- | | o 4:26805aba1e60 C
+ +---x 5:66f1a38021c9 F
| | |
- | x | 3:7fb047a69f22 E
+ | o | 4:26805aba1e60 C
| | |
- o | | 2:b18e25de2cf5 D
- |/ /
- | o 1:112478962961 B
+ | | x 3:7fb047a69f22 E
+ | | |
+ o---+ 2:b18e25de2cf5 D
+ / /
+ o / 1:112478962961 B
|/
o 0:426bada5c675 A
@@ -1060,9 +1069,8 @@
rebasing 2:b18e25de2cf5 "D" (D)
note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
rebasing 5:66f1a38021c9 "F" (F tip)
+ note: rebase of 5:66f1a38021c9 created no changes to commit
$ hg log -G
- o 7:9ed45af61fa0 F
- |
o 6:8f47515dda15 D
|
| x 5:66f1a38021c9 F
@@ -1096,13 +1104,13 @@
note: not rebasing 2:b18e25de2cf5 "D" (D), already in destination as 1:112478962961 "B"
rebasing 3:7fb047a69f22 "E" (E)
rebasing 5:66f1a38021c9 "F" (F tip)
-BROKEN: This should have resulted in a rebased F with one parent, just like in
-the test case above
+ warning: rebasing 5:66f1a38021c9 may inlcude unwanted changes from revision 2
+
$ hg log -G
- o 7:c1e6f26e339d F
- |\
- | o 6:533690786a86 E
- |/
+ o 7:502540f44880 F
+ |
+ o 6:533690786a86 E
+ |
| x 5:66f1a38021c9 F
| |\
o | | 4:26805aba1e60 C
diff --git a/tests/test-rebase-newancestor.t b/tests/test-rebase-newancestor.t
--- a/tests/test-rebase-newancestor.t
+++ b/tests/test-rebase-newancestor.t
@@ -3,7 +3,7 @@
> usegeneraldelta=yes
> [extensions]
> rebase=
- >
+ > drawdag=$TESTDIR/drawdag.py
> [alias]
> tglog = log -G --template "{rev}: '{desc}' {branches}\n"
> EOF
@@ -334,3 +334,97 @@
|/
o 0: 'common'
+Due to the limitation of 3-way merge algorithm (1 merge base), rebasing a merge
+may include unwanted content:
+
+ $ hg init $TESTTMP/dual-merge-base1
+ $ cd $TESTTMP/dual-merge-base1
+ $ hg debugdrawdag <<'EOS'
+ > F
+ > /|
+ > D E
+ > | |
+ > B C
+ > |/
+ > A Z
+ > |/
+ > R
+ > EOS
+ $ hg rebase -r D+E+F -d Z
+ rebasing 5:5f2c926dfecf "D" (D)
+ rebasing 6:b296604d9846 "E" (E)
+ rebasing 7:caa9781e507d "F" (F tip)
+ warning: rebasing 7:caa9781e507d may inlcude unwanted changes from revision 4
+ saved backup bundle to $TESTTMP/dual-merge-base1/.hg/strip-backup/b296604d9846-0516f6d2-rebase.hg (glob)
+ $ hg log -r 4 -T '{files}\n'
+ C
+ $ hg manifest -r 'desc(F)'
+ C
+ D
+ E
+ R
+ Z
+
+The warning does not get printed if there is no unwanted change detected:
+
+ $ hg init $TESTTMP/dual-merge-base2
+ $ cd $TESTTMP/dual-merge-base2
+ $ hg debugdrawdag <<'EOS'
+ > D
+ > /|
+ > B C
+ > |/
+ > A Z
+ > |/
+ > R
+ > EOS
+ $ hg rebase -r B+C+D -d Z
+ rebasing 3:c1e6b162678d "B" (B)
+ rebasing 4:d6003a550c2c "C" (C)
+ rebasing 5:c8f78076273e "D" (D tip)
+ saved backup bundle to $TESTTMP/dual-merge-base2/.hg/strip-backup/d6003a550c2c-6f1424b6-rebase.hg (glob)
+ $ hg manifest -r 'desc(D)'
+ B
+ C
+ R
+ Z
+
+The merge base could be different from new p1:
+
+ $ hg init $TESTTMP/chosen-merge-base1
+ $ cd $TESTTMP/chosen-merge-base1
+ $ hg debugdrawdag <<'EOS'
+ > F
+ > /|
+ > D E
+ > | |
+ > B C Z
+ > EOS
+ $ hg rebase -r D+F -d Z
+ rebasing 3:004dc1679908 "D" (D)
+ rebasing 5:4be4cbf6f206 "F" (F tip)
+ saved backup bundle to $TESTTMP/chosen-merge-base1/.hg/strip-backup/004dc1679908-06a66a3c-rebase.hg (glob)
+ $ hg manifest -r 'desc(F)'
+ C
+ D
+ E
+ Z
+
+ $ hg init $TESTTMP/chosen-merge-base2
+ $ cd $TESTTMP/chosen-merge-base2
+ $ hg debugdrawdag <<'EOS'
+ > F
+ > /|
+ > D E
+ > | |
+ > B C Z
+ > EOS
+ $ hg rebase -r E+F -d Z
+ rebasing 4:974e4943c210 "E" (E)
+ rebasing 5:4be4cbf6f206 "F" (F tip)
+ saved backup bundle to $TESTTMP/chosen-merge-base2/.hg/strip-backup/974e4943c210-b2874da5-rebase.hg (glob)
+ $ hg manifest -r 'desc(F)'
+ B
+ D
+ E
+ Z
diff --git a/tests/test-rebase-brute-force.t b/tests/test-rebase-brute-force.t
--- a/tests/test-rebase-brute-force.t
+++ b/tests/test-rebase-brute-force.t
@@ -31,8 +31,8 @@
AD: A':Z D':Z
BD: B':Z D':B'
ABD: A':Z B':Z D':B'
- CD: CRASH: revlog index out of range
- ACD: A':Z C':A'A' D':Z
+ CD: ABORT: cannot use revision 3 as base, result would have 3 parents
+ ACD: A':Z C':A'B D':Z
BCD: B':Z C':B'A D':B'
ABCD: A':Z B':Z C':A'B' D':B'
@@ -52,4 +52,4 @@
C: ABORT: cannot use revision 3 as base, result would have 3 parents
BC: B':Z C':B'A
AC:
- BAC: ABORT: nothing to merge
+ BAC: B':Z C':B'A
diff --git a/hgext/rebase.py b/hgext/rebase.py
--- a/hgext/rebase.py
+++ b/hgext/rebase.py
@@ -66,7 +66,6 @@
revprecursor = -4
# plain prune (no successor)
revpruned = -5
-revskipped = (revignored, revprecursor, revpruned)
cmdtable = {}
command = registrar.command(cmdtable)
@@ -390,10 +389,7 @@
ui.status(_('rebasing %s\n') % desc)
ui.progress(_("rebasing"), pos, ("%d:%s" % (rev, ctx)),
_('changesets'), total)
- p1, p2, base = defineparents(repo, rev, self.dest,
- self.state,
- self.destancestors,
- self.obsoletenotrebased)
+ p1, p2, base = defineparents(repo, rev, self.dest, self.state)
self.storestatus(tr=tr)
storecollapsemsg(repo, self.collapsemsg)
if len(repo[None].parents()) == 2:
@@ -463,9 +459,7 @@
repo, ui, opts = self.repo, self.ui, self.opts
if self.collapsef and not self.keepopen:
p1, p2, _base = defineparents(repo, min(self.state),
- self.dest, self.state,
- self.destancestors,
- self.obsoletenotrebased)
+ self.dest, self.state)
editopt = opts.get('edit')
editform = 'rebase.collapse'
if self.collapsemsg:
@@ -960,15 +954,6 @@
result.append(adjusted)
return result
-def nearestrebased(repo, rev, state):
- """return the nearest ancestors of rev in the rebase result"""
- rebased = [r for r in state if state[r] > nullmerge]
- candidates = repo.revs('max(%ld and (::%d))', rebased, rev)
- if candidates:
- return state[candidates.first()]
- else:
- return None
-
def _checkobsrebase(repo, ui, rebaseobsrevs, rebasesetrevs, rebaseobsskipped):
"""
Abort if rebase will create divergence or rebase is noop because of markers
@@ -992,107 +977,167 @@
"experimental.allowdivergence=True")
raise error.Abort(msg % (",".join(divhashes),), hint=h)
-def defineparents(repo, rev, dest, state, destancestors,
- obsoletenotrebased):
- 'Return the new parent relationship of the revision that will be rebased'
- parents = repo[rev].parents()
- p1 = p2 = nullrev
- rp1 = None
+def successorrevs(repo, rev):
+ """yield revision numbers for successors of rev"""
+ unfi = repo.unfiltered()
+ nodemap = unfi.changelog.nodemap
+ for s in obsutil.allsuccessors(unfi.obsstore, [unfi[rev].node()]):
+ if s in nodemap:
+ yield nodemap[s]
+
+def defineparents(repo, rev, dest, state):
+ """Return new parents and optionally a merge base for rev being rebased
+
+ The destination specified by "dest" cannot always be used directly because
+ previously rebase result could affect destination. For example,
- p1n = parents[0].rev()
- if p1n in destancestors:
- p1 = dest
- elif p1n in state:
- if state[p1n] == nullmerge:
- p1 = dest
- elif state[p1n] in revskipped:
- p1 = nearestrebased(repo, p1n, state)
- if p1 is None:
- p1 = dest
- else:
- p1 = state[p1n]
- else: # p1n external
- p1 = dest
- p2 = p1n
+ D E rebase -r C+D+E -d B
+ |/ C will be rebased to C'
+ B C D's new destination will be C' instead of B
+ |/ E's new destination will be C' instead of B
+ A
+
+ The new parents of a merge is slightly more complicated. See the comment
+ block below.
+ """
+ cl = repo.changelog
+ def isancestor(a, b):
+ # take revision numbers instead of nodes
+ return cl.isancestor(cl.node(a), cl.node(b))
+
+ oldps = repo.changelog.parentrevs(rev) # old parents
+ newps = [nullrev, nullrev] # new parents
+ dests = adjustdest(repo, rev, dest, state) # adjusted destinations
+ bases = set() # merge base candidates
- if len(parents) == 2 and parents[1].rev() not in destancestors:
- p2n = parents[1].rev()
- # interesting second parent
- if p2n in state:
- if p1 == dest: # p1n in destancestors or external
- p1 = state[p2n]
- if p1 == revprecursor:
- rp1 = obsoletenotrebased[p2n]
- elif state[p2n] in revskipped:
- p2 = nearestrebased(repo, p2n, state)
- if p2 is None:
- # no ancestors rebased yet, detach
- p2 = dest
- else:
- p2 = state[p2n]
- else: # p2n external
- if p2 != nullrev: # p1n external too => rev is a merged revision
- raise error.Abort(_('cannot use revision %d as base, result '
- 'would have 3 parents') % rev)
- p2 = p2n
- repo.ui.debug(" future parents are %d and %d\n" %
- (repo[rp1 or p1].rev(), repo[p2].rev()))
+ if all(r == nullrev for r in oldps[1:]):
+ # For non-merge changeset, just move p to adjusted dest as requested.
+ newps[0] = dests[0]
+ bases.add(oldps[0])
+ else:
+ # For merge changeset, if we move p to dests[i] unconditionally, both
+ # parents may change and the end result looks like "the merge loses a
+ # parent", which is a surprise. This is a limit because "--dest" only
+ # accepts one dest per src.
+ #
+ # Therefore, only move p with reasonable conditions (in this order):
+ # 1. use dest, if dest is a descendent of (p or one of p's successors)
+ # 2. use p's rebased result, if p is rebased (state[p] > 0)
+ #
+ # Comparing with adjustdest, the logic here does some additional work:
+ # 1. decide which parents will not be moved towards dest
+ # 2. if the above decision is "no", should a parent still be moved
+ # because it was rebased?
+ #
+ # For example:
+ #
+ # C # "rebase -r C -d D" is an error since none of the parents
+ # /| # can be moved. "rebase -r B+C -d D" will move C's parent
+ # A B D # B (using rule "2."), since B will be rebased.
+ #
+ # The code tries to be not rely on the fact that a Mercurial node has
+ # at most 2 parents.
+ for i, p in enumerate(oldps):
+ np = p # new parent
+ if any(isancestor(x, dests[i]) for x in successorrevs(repo, p)):
+ np = dests[i]
+ elif p in state and state[p] > 0:
+ np = state[p]
- if not any(p.rev() in state for p in parents):
- # Case (1) root changeset of a non-detaching rebase set.
- # Let the merge mechanism find the base itself.
- base = None
- elif not repo[rev].p2():
- # Case (2) detaching the node with a single parent, use this parent
- base = repo[rev].p1().rev()
- else:
- # Assuming there is a p1, this is the case where there also is a p2.
- # We are thus rebasing a merge and need to pick the right merge base.
- #
- # Imagine we have:
- # - M: current rebase revision in this step
- # - A: one parent of M
- # - B: other parent of M
- # - D: destination of this merge step (p1 var)
- #
- # Consider the case where D is a descendant of A or B and the other is
- # 'outside'. In this case, the right merge base is the D ancestor.
- #
- # An informal proof, assuming A is 'outside' and B is the D ancestor:
- #
- # If we pick B as the base, the merge involves:
- # - changes from B to M (actual changeset payload)
- # - changes from B to D (induced by rebase) as D is a rebased
- # version of B)
- # Which exactly represent the rebase operation.
+ # If parent changed, the old parent is a merge base candidate.
+ #
+ # The merge code could figure out the merge base using changelog
+ # graph. Here, only record bases where changelog graph cannot
+ # desired result (i.e. isancestor(p, np) is Fales). For example,
+ #
+ # B' # rebase -s B -d D, when B was rebased to B'. dest for C
+ # | C # is B', but merge base for C is B, instead of
+ # D | # changelog.ancestor(C, B') == A. If changelog DAG and
+ # | B # "state" edges are merged (so there will be an edge from
+ # |/ # B to B'), the merge base is still ancestor(C, B') in
+ # A # the merged graph.
+ #
+ # Also see https://bz.mercurial-scm.org/show_bug.cgi?id=1950#c8
+ # which uses "virtual null merge" to explain this situation.
+ if np not in (p, nullrev) and not isancestor(p, np):
+ bases.add(p)
+
+ # If one parent becomes an ancestor of the other, drop the ancestor
+ for j, x in enumerate(newps[:i]):
+ if x == nullrev:
+ continue
+ if x == np or (x > np and isancestor(np, x)):
+ np = nullrev
+ elif x < np and isancestor(x, np):
+ newps[j] = np
+ np = nullrev
+
+ newps[i] = np
+
+ # Extra tweak related to how Mercurial works: The update code prefers
+ # updating to p1 blindly. If p1 is not changed, swap parents so update
+ # will be more likely to do the right thing.
+ if newps[1] != nullrev and oldps[0] == newps[0]:
+ newps.reverse()
+ oldps = list(reversed(oldps)) # for mergebase decision
+
+ # No parent change might be an error because we fail to make rev a
+ # descendent of requested dest. This can happen, for example:
+ #
+ # C # rebase -r C -d D
+ # /| # None of A and B will be changed to D and rebase fails.
+ # A B D
+ if set(newps) == set(oldps) and dest not in newps:
+ # The error message is for compatibility. It's a bit misleading since
+ # rebase is not supposed to add new parents.
+ raise error.Abort(_('cannot use revision %d as base, '
+ 'result would have 3 parents') % rev)
+
+ repo.ui.debug(" future parents are %d and %d\n" % tuple(newps))
+
+ # Decide a merge base
+ base = None
+ if len(bases) == 1:
+ base = next(iter(bases))
+ elif len(bases) > 1:
+ # We do not support multiple merge bases. For example,
#
- # If we pick A as the base, the merge involves:
- # - changes from A to M (actual changeset payload)
- # - changes from A to D (with include changes between unrelated A and B
- # plus changes induced by rebase)
- # Which does not represent anything sensible and creates a lot of
- # conflicts. A is thus not the right choice - B is.
+ # F
+ # /|
+ # D E # "rebase -r D+E+F -d Z", when rebasing F, if "D" was chosen
+ # | | # as merge base, the difference between D and F will include
+ # B C # C surprisingly. If "E" was chosen, then content in B will
+ # |/ # be included.
+ # A Z
#
- # Note: The base found in this 'proof' is only correct in the specified
- # case. This base does not make sense if is not D a descendant of A or B
- # or if the other is not parent 'outside' (especially not if the other
- # parent has been rebased). The current implementation does not
- # make it feasible to consider different cases separately. In these
- # other cases we currently just leave it to the user to correctly
- # resolve an impossible merge using a wrong ancestor.
- #
- # xx, p1 could be -4, and both parents could probably be -4...
- for p in repo[rev].parents():
- if state.get(p.rev()) == p1:
- base = p.rev()
- break
- else: # fallback when base not found
- base = None
+ # But our merge base candidates (D and E in above case) could still be
+ # better than the default (ancestor(F, Z) == null). Therefore still
+ # pick one. Since "rebasenode" updates to new p1, prefer old p1 as
+ # the merge base.
+ assert oldps[0] in bases
+ base = oldps[0]
+
+ # Revisions in the side (not chosen as merge base) branch that might
+ # contain "surprising" contents
+ siderevs = list(repo.revs('((%ld-%d) %% (%d+%d))',
+ bases, base, base, dest))
- # Raise because this function is called wrong (see issue 4106)
- raise AssertionError('no base found to rebase on '
- '(defineparents called wrong)')
- return rp1 or p1, p2, base
+ # If those revisions are covered by our rebaseset, things are okay.
+ # Note that a merge in rebaseset would be considered to cover its
+ # ancestors.
+ if siderevs:
+ rebaseset = [r for r, d in state.items() if d > 0]
+ merges = [r for r in rebaseset if cl.parentrevs(r)[1] != nullrev]
+ siderevs = list(repo.revs('%ld - (::%ld) - %ld',
+ siderevs, merges, rebaseset))
+
+ if siderevs:
+ repo.ui.warn(_('warning: rebasing %d:%s may inlcude unwanted '
+ 'changes from revision %s\n')
+ % (rev, repo[rev],
+ ', '.join(str(r) for r in siderevs)))
+
+ return newps[0], newps[1], base
def isagitpatch(repo, patchname):
'Return true if the given patch is in git format'
To: quark, durin42, #hg-reviewers
Cc: martinvonz, durin42, mercurial-devel
More information about the Mercurial-devel
mailing list