D21: rebase: rewrite core algorithm (issue5578) (issue5630)
quark (Jun Wu)
phabricator at mercurial-scm.org
Fri Aug 11 01:41:45 EDT 2017
quark updated this revision to Diff 765.
quark edited the summary of this revision.
This revision is now accepted and ready to land.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D21?vs=754&id=765
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
@@ -1096,13 +1105,14 @@
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
+
+Rebased F should have one parent, just like in the test case above
+
$ 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
@@ -284,18 +284,7 @@
rebasing 6:4c5f12f25ebe "merge rebase ancestors" (tip)
resolving manifests
removing other
- note: merging f9daf77ffe76+ and 4c5f12f25ebe using bids from ancestors a60552eb93fb and f59da8fc0fcf
-
- calculating bids for ancestor a60552eb93fb
resolving manifests
-
- calculating bids for ancestor f59da8fc0fcf
- resolving manifests
-
- auction for merging merge bids
- other: consensus for g
- end of auction
-
getting other
committing files:
other
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,121 @@
"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 ancestor(rev1, rev2):
+ # take revision numbers instead of nodes
+ return cl.rev(cl.ancestor(cl.node(rev1), cl.node(rev2)))
- 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()))
+ oldps = repo.changelog.parentrevs(rev) # old parents
+ newps = list(oldps) # new parents
+ bases = set() # merge base candidates
+ dests = adjustdest(repo, rev, dest, state)
+
+ for i, p in enumerate(oldps):
+ # Do not skip nullrev for p1. Otherwise root node cannot be rebased.
+ if p == nullrev and i != 0:
+ continue
+
+ # For non-merge changeset, just move p to adjusted dest as requested.
+ if oldps[1] == nullrev:
+ newps[i] = dests[i]
+
+ # 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):
+ # - use dest, if dest is a descendent of (p or one of p's successors)
+ # - use p's rebased result, if p is rebased (state[p] > 0)
+ #
+ # That also means, we might ignore user's dest for a merge sometimes.
+ elif any(ancestor(x, dests[i]) == x for x in successorrevs(repo, p)):
+ newps[i] = dests[i]
+ elif p in state and state[p] > 0:
+ newps[i] = 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 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.
- #
- # 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
+ # The old parent is a merge base candidate (if parent changes)
+ if newps[i] != oldps[i]:
+ bases.add(p)
+
+ # Remove duplicated parent
+ if newps[1] == newps[0]:
+ newps[1] = nullrev
+
+ # Extra checks for merge changesets
+ if newps[1] != nullrev:
+ # If one parent becomes an ancestor of the other, drop the ancestor
+ anc = ancestor(*newps)
+ newps = [p for p in newps if p != anc]
+ assert newps
+ if len(newps) == 1:
+ newps.append(nullrev)
+ elif oldps[0] == newps[0]:
+ # 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.
+ newps.reverse()
- # 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
+ # 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 -s 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))
+
+ # Merge base
+ base = None
+ # Prefer merge base candidates which are not a changelog ancestor of
+ # rev and its destination. 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 "state"
+ # | B edges are merged (so there will be an edge from B to B'),
+ # |/ the merge base is still ancestor(C, B') in the merged graph.
+ # A
+ #
+ # Also see https://bz.mercurial-scm.org/show_bug.cgi?id=1950#c8 which
+ # uses "virtual null merge" to explain this situation in another way.
+ if len(bases) > 1:
+ bases.difference_update(ancestor(rev, d) for d in set(dests))
+
+ # Only pick the merge base if we have a unique candidate
+ if len(bases) == 1:
+ base = next(iter(bases))
+
+ 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: durin42, mercurial-devel
More information about the Mercurial-devel
mailing list