D21: rebase: rewrite core algorithm (issue5578) (issue5630)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

D21: rebase: rewrite core algorithm (issue5578) (issue5630)

dsp (David Soria Parra)
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
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Loading...