rebase: choose merge base without unwanted revisions

Previously, when there are 2 merge base candidates, we choose p1 blindly,
which may make the merge result to have "unwanted content". This patch makes
rebase smarter - choose a merge base that does not have "unwanted revs" if
possible. Since we don't really have a good solution when there are
"unwanted revs", abort in that case.

Differential Revision: https://phab.mercurial-scm.org/D340

hgext/rebase.py

@@ -1041,11 +1041,14 b' def defineparents(repo, rev, dest, state'
             for j, x in enumerate(newps[:i]):
                 if x == nullrev:
                     continue
-                if isancestor(np, x):
+                if isancestor(np, x): # CASE-1
                     np = nullrev
-                elif isancestor(x, np):
+                elif isancestor(x, np): # CASE-2
                     newps[j] = np
                     np = nullrev
+                    # New parents forming an ancestor relationship does not
+                    # mean the old parents have a similar relationship. Do not
+                    # set bases[x] to nullrev.
                     bases[j], bases[i] = bases[i], bases[j]
 
             newps[i] = np
@@ -1069,8 +1072,6 b' def defineparents(repo, rev, dest, state'
                                 'moving at least one of its parents')
                               % (rev, repo[rev]))
 
-    repo.ui.debug(" future parents are %d and %d\n" % tuple(newps))
-
     # "rebasenode" updates to new p1, use the corresponding merge base.
     if bases[0] != nullrev:
         base = bases[0]
@@ -1093,28 +1094,47 b' def defineparents(repo, rev, dest, state'
     # better than the default (ancestor(F, Z) == null). Therefore still
     # pick one (so choose p1 above).
     if sum(1 for b in bases if b != nullrev) > 1:
-        assert base is not None
+        unwanted = [None, None] # unwanted[i]: unwanted revs if choose bases[i]
+        for i, base in enumerate(bases):
+            if base == nullrev:
+                continue
+            # 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))
 
-        # 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))
+            # If those revisions are covered by rebaseset, the result is good.
+            # 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]
+                unwanted[i] = list(repo.revs('%ld - (::%ld) - %ld',
+                                             siderevs, merges, rebaseset))
 
-        # If those revisions are covered by rebaseset, the result is good.
-        # 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]
-            unwantedrevs = list(repo.revs('%ld - (::%ld) - %ld',
-                                          siderevs, merges, rebaseset))
+        # Choose a merge base that has a minimal number of unwanted revs.
+        l, i = min((len(revs), i)
+                   for i, revs in enumerate(unwanted) if revs is not None)
+        base = bases[i]
+
+        # newps[0] should match merge base if possible. Currently, if newps[i]
+        # is nullrev, the only case is newps[i] and newps[j] (j < i), one is
+        # the other's ancestor. In that case, it's fine to not swap newps here.
+        # (see CASE-1 and CASE-2 above)
+        if i != 0 and newps[i] != nullrev:
+            newps[0], newps[i] = newps[i], newps[0]
 
-            # For revs not covered, it is worth a warning.
-            if unwantedrevs:
-                repo.ui.warn(
-                    _('warning: rebasing %d:%s may include unwanted changes '
-                      'from %s\n')
-                    % (rev, repo[rev], ', '.join('%d:%s' % (r, repo[r])
-                                                 for r in unwantedrevs)))
+        # The merge will include unwanted revisions. Abort now. Revisit this if
+        # we have a more advanced merge algorithm that handles multiple bases.
+        if l > 0:
+            unwanteddesc = _(' or ').join(
+                (', '.join('%d:%s' % (r, repo[r]) for r in revs)
+                 for revs in unwanted if revs is not None))
+            raise error.Abort(
+                _('rebasing %d:%s will include unwanted changes from %s')
+                % (rev, repo[rev], unwanteddesc))
+
+    repo.ui.debug(" future parents are %d and %d\n" % tuple(newps))
 
     return newps[0], newps[1], base
 

tests/test-rebase-newancestor.t

@@ -354,16 +354,8 b' may include unwanted content:'
   rebasing 5:5f2c926dfecf "D" (D)
   rebasing 6:b296604d9846 "E" (E)
   rebasing 7:caa9781e507d "F" (F tip)
-  warning: rebasing 7:caa9781e507d may include unwanted changes from 4:d6003a550c2c
-  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
+  abort: rebasing 7:caa9781e507d will include unwanted changes from 4:d6003a550c2c or 3:c1e6b162678d
+  [255]
 
 The warning does not get printed if there is no unwanted change detected:
 

tests/test-rebase-obsolete.t

@@ -1065,10 +1065,8 b' Rebase merge where successor of one pare'
   note: not rebasing 3:7fb047a69f22 "E" (E), already in destination as 1:112478962961 "B"
   rebasing 2:b18e25de2cf5 "D" (D)
   rebasing 5:66f1a38021c9 "F" (F tip)
-  warning: rebasing 5:66f1a38021c9 may include unwanted changes from 3:7fb047a69f22
+  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
@@ -1102,11 +1100,9 b' Rebase merge where successor of other pa'
   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)
-  warning: rebasing 5:66f1a38021c9 may include unwanted changes from 2:b18e25de2cf5
+  note: rebase of 5:66f1a38021c9 created no changes to commit
 
   $ hg log -G
-  o  7:502540f44880 F
-  |
   o  6:533690786a86 E
   |
   | x    5:66f1a38021c9 F
@@ -1123,6 +1119,88 b' Rebase merge where successor of other pa'
   
   $ cd ..
 
+Rebase merge where both parents have successors in destination
+
+  $ hg init p12-succ-in-dest
+  $ cd p12-succ-in-dest
+  $ hg debugdrawdag <<'EOS'
+  >   E   F
+  >  /|  /|  # replace: A -> C
+  > A B C D  # replace: B -> D
+  > | |
+  > X Y
+  > EOS
+  $ hg rebase -r A+B+E -d F
+  note: not rebasing 4:a3d17304151f "A" (A), already in destination as 0:96cc3511f894 "C"
+  note: not rebasing 5:b23a2cc00842 "B" (B), already in destination as 1:058c1e1fb10a "D"
+  rebasing 7:dac5d11c5a7d "E" (E tip)
+  abort: rebasing 7:dac5d11c5a7d will include unwanted changes from 3:59c792af609c, 5:b23a2cc00842 or 2:ba2b7fa7166d, 4:a3d17304151f
+  [255]
+  $ cd ..
+
+Rebase a non-clean merge. One parent has successor in destination, the other
+parent moves as requested.
+
+  $ hg init p1-succ-p2-move
+  $ cd p1-succ-p2-move
+  $ hg debugdrawdag <<'EOS'
+  >   D Z
+  >  /| | # replace: A -> C
+  > A B C # D/D = D
+  > EOS
+  $ hg rebase -r A+B+D -d Z
+  note: not rebasing 0:426bada5c675 "A" (A), already in destination as 2:96cc3511f894 "C"
+  rebasing 1:fc2b737bb2e5 "B" (B)
+  rebasing 3:b8ed089c80ad "D" (D)
+
+  $ rm .hg/localtags
+  $ hg log -G
+  o  6:e4f78693cc88 D
+  |
+  o  5:76840d832e98 B
+  |
+  o  4:50e41c1f3950 Z
+  |
+  o  2:96cc3511f894 C
+  
+  $ hg files -r tip
+  B
+  C
+  D
+  Z
+
+  $ cd ..
+
+  $ hg init p1-move-p2-succ
+  $ cd p1-move-p2-succ
+  $ hg debugdrawdag <<'EOS'
+  >   D Z
+  >  /| |  # replace: B -> C
+  > A B C  # D/D = D
+  > EOS
+  $ hg rebase -r B+A+D -d Z
+  note: not rebasing 1:fc2b737bb2e5 "B" (B), already in destination as 2:96cc3511f894 "C"
+  rebasing 0:426bada5c675 "A" (A)
+  rebasing 3:b8ed089c80ad "D" (D)
+
+  $ rm .hg/localtags
+  $ hg log -G
+  o  6:1b355ed94d82 D
+  |
+  o  5:a81a74d764a6 A
+  |
+  o  4:50e41c1f3950 Z
+  |
+  o  2:96cc3511f894 C
+  
+  $ hg files -r tip
+  A
+  C
+  D
+  Z
+
+  $ cd ..
+
 Test that bookmark is moved and working dir is updated when all changesets have
 equivalents in destination
   $ hg init rbsrepo && cd rbsrepo