D21: rebase: rewrite core algorithm (issue5578) (issue5630)
quark (Jun Wu)
phabricator at mercurial-scm.org
Fri Aug 11 03:30:42 UTC 2017
quark updated this revision to Diff 753.
quark marked an inline comment as done.
quark edited the summary of this revision.
quark retitled this revision from "rebase: rewrite defineparents" to "rebase: rewrite core algorithm (issue5578) (issue5630)".
This revision is now accepted and ready to land.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D21?vs=161&id=753
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,33 @@
> 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]
+ $ hg log -G
+ @ 8:1971b36cbe4e D
+ |
+ | o 7:f7e03ec6c148 B
+ |/
+ | o 6:f15c3adaf214 F
+ | |\
+ | | o 5:4b61ff5c62e2 E
+ | | |
+ | o | 4:26805aba1e60 C
+ | | |
+ o | | 3:6fa3874a3b67 G
+ | | |
+ +---o 2:b18e25de2cf5 D
+ | |
+ | o 1:112478962961 B
+ |/
+ o 0:426bada5c675 A
+
$ cd ..
@@ -962,17 +986,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 +1020,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 +1051,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 +1088,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 +1123,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,131 @@
"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]
+
+ # The old parent is a merge base candidate (if parent changes)
+ if newps[i] != oldps[i]:
+ bases.add(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()
+ # 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()
+
+ # 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)
+
+ # Source should not be ancestor of dest. The check here guarantees it's
+ # impossible. Checks in other places might catch some cases. But this is a
+ # double check that guarantees it's strictly impossible.
+ if any(p != nullrev and ancestor(p, rev) == rev for p in newps):
+ raise error.Abort(_('source is ancestor of destination'))
+
+ repo.ui.debug(" future parents are %d and %d\n" % tuple(newps))
+
+ # Merge base
+ base = None
+ if len(bases) == 1:
+ base = next(iter(bases))
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.
+ # Prefer merge base candidates which are not a changelog ancestor of
+ # rev and its destination. 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.
+ # 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
#
- # 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
+ # 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.
+ bases.difference_update(ancestor(rev, d) for d in set(dests))
+ if len(bases) >= 1:
+ if len(bases) > 1:
+ repo.ui.debug(
+ 'warning: cannot decide best merge base for %d '
+ '(candidates: %r)\n' % (rev, sorted(bases)))
+ base = max(bases)
- # 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
+ 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