[PATCH 1 of 2 v6] graft: support grafting across move/copy (issue4028)

Gábor Stefanik gabor.stefanik at nng.com
Thu Aug 25 20:32:48 UTC 2016


# HG changeset patch
# User Gábor Stefanik <gabor.stefanik at nng.com>
# Date 1472156862 -7200
#      Thu Aug 25 22:27:42 2016 +0200
# Node ID a887e7516d5b37c0b55202fa1ec9db6909a03ce0
# Parent  b1809f5d7630a3fff0fa715bbd30dba0f07672a8
graft: support grafting across move/copy (issue4028)

Graft performs a merge with a false common ancestor, which must be taken into
account when tracking copies. Explicitly pass the real common ancestor in this
case, and track copies between the real and false common ancestors in reverse.

With this change, when grafting a commit with a change to a file moved earlier
on the graft's source branch, the change is merged as expected into the original
(unmoved) file, rather than recreating it under its new name.
It should also make it possible to eventually enable cross-branch updates with
merge.

v2: handle the case when target branch also has a rename
v3: address review comments
v4: move ancestry check to mergecopies, split tests to separate commit
v5: split out parameter change, address review comments, re-include tests
v6: fix reversed logic
v7: partial rewrite to correctly handle divergent renames, address review
    comments, adjust more tests, and polish up some edge cases

diff --git a/mercurial/copies.py b/mercurial/copies.py
--- a/mercurial/copies.py
+++ b/mercurial/copies.py
@@ -321,6 +321,20 @@
     if repo.ui.configbool('experimental', 'disablecopytrace'):
         return {}, {}, {}, {}
 
+    # In certain scenarios (e.g. graft, update or rebase), ca can be overridden
+    # We still need to know a real common ancestor in this case
+    # We can't just compute _c1.ancestor(_c2) and compare it to ca, because
+    # there can be multiple common ancestors, e.g. in case of bidmerge.
+    cta = ca
+    # ca.descendant(wc) and ca.descendant(ca) are False, work around that
+    _c1 = c1.p1() if c1.rev() is None else c1
+    _c2 = c2.p1() if c2.rev() is None else c2
+    dirty_c1 = not (ca == _c1 or ca.descendant(_c1))
+    dirty_c2 = not (ca == _c2 or ca.descendant(_c2))
+    graft = dirty_c1 or dirty_c2
+    if graft:
+        cta = _c1.ancestor(_c2)
+
     limit = _findlimit(repo, c1.rev(), c2.rev())
     if limit is None:
         # no common ancestor, no copies
@@ -330,28 +344,54 @@
     m1 = c1.manifest()
     m2 = c2.manifest()
     ma = ca.manifest()
+    mta = cta.manifest()
 
-    copy1, copy2, = {}, {}
+    # see checkcopies documentation below for these dicts
+    copy1, copy2 = {}, {}
+    incomplete1, incomplete2 = {}, {}
     movewithdir1, movewithdir2 = {}, {}
     fullcopy1, fullcopy2 = {}, {}
-    diverge = {}
+    diverge, incompletediverge = {}, {}
 
     # find interesting file sets from manifests
+    if graft:
+        repo.ui.debug("  computing unmatched files in rotated DAG\n")
     addedinm1 = m1.filesnotin(ma)
     addedinm2 = m2.filesnotin(ma)
-    u1, u2 = _computenonoverlap(repo, c1, c2, addedinm1, addedinm2)
+    _u1, _u2 = _computenonoverlap(repo, c1, c2, addedinm1, addedinm2)
+    if not graft:
+        u1, u2 = _u1, _u2
+    else: # need to recompute this for directory move handling when grafting
+        repo.ui.debug("  computing unmatched files in unrotated DAG\n")
+        u1, u2 = _computenonoverlap(repo, c1, c2, m1.filesnotin(mta),
+                                                  m2.filesnotin(mta))
+
     bothnew = sorted(addedinm1 & addedinm2)
 
     for f in u1:
-        checkcopies(c1, f, m1, m2, ca, limit, diverge, copy1, fullcopy1)
+        checkcopies(c1, f, m1, m2, ca, cta, dirty_c1, limit, diverge, copy1,
+                    fullcopy1, incomplete1, incompletediverge)
 
     for f in u2:
-        checkcopies(c2, f, m2, m1, ca, limit, diverge, copy2, fullcopy2)
+        checkcopies(c2, f, m2, m1, ca, cta, dirty_c2, limit, diverge, copy2,
+                    fullcopy2, incomplete2, incompletediverge)
 
     copy = dict(copy1.items() + copy2.items())
     movewithdir = dict(movewithdir1.items() + movewithdir2.items())
     fullcopy = dict(fullcopy1.items() + fullcopy2.items())
 
+    # combine partial copy paths discovered in the previous step
+    copyfrom, copyto = incomplete1, incomplete2
+    if dirty_c1:
+        copyfrom, copyto = incomplete2, incomplete1
+    for f in copyfrom:
+        copy[copyto[f]] = copyfrom[f]
+        del copyto[f]
+    for f in incompletediverge:
+        ic = incompletediverge[f]
+        assert f not in diverge
+        diverge[f] = [copyto[ic[0]], ic[1]]
+
     renamedelete = {}
     renamedeleteset = set()
     divergeset = set()
@@ -369,10 +409,25 @@
     if bothnew:
         repo.ui.debug("  unmatched files new in both:\n   %s\n"
                       % "\n   ".join(bothnew))
-    bothdiverge, _copy, _fullcopy = {}, {}, {}
+    bothdiverge = {}
+    _copy, _fullcopy = {}, {} # dummy dicts
+    _incomplete1, _incomplete2, _diverge = {}, {}, {}
     for f in bothnew:
-        checkcopies(c1, f, m1, m2, ca, limit, bothdiverge, _copy, _fullcopy)
-        checkcopies(c2, f, m2, m1, ca, limit, bothdiverge, _copy, _fullcopy)
+        checkcopies(c1, f, m1, m2, ca, cta, dirty_c1, limit, bothdiverge,
+                    _copy, _fullcopy, _incomplete1, _diverge)
+        checkcopies(c2, f, m2, m1, ca, cta, dirty_c2, limit, bothdiverge,
+                    _copy, _fullcopy, _incomplete2, _diverge)
+    _incomplete = _incomplete2
+    if dirty_c1:
+        _incomplete = _incomplete1
+        assert _incomplete2 == {}
+    else:
+        assert _incomplete1 == {}
+    for f in _diverge:
+        ic = _diverge[f]
+        assert f not in bothdiverge
+        bothdiverge[f] = [_incomplete.get(ic[0], ic[0]), ic[1]]
+
     for of, fl in bothdiverge.items():
         if len(fl) == 2 and fl[0] == fl[1]:
             copy[fl[0]] = of # not actually divergent, just matching renames
@@ -438,7 +493,7 @@
                       (d, dirmove[d]))
 
     # check unaccounted nonoverlapping files against directory moves
-    for f in u1 + u2:
+    for f in _u1 + _u2:
         if f not in fullcopy:
             for d in dirmove:
                 if f.startswith(d):
@@ -452,7 +507,8 @@
 
     return copy, movewithdir, diverge, renamedelete
 
-def checkcopies(ctx, f, m1, m2, ca, limit, diverge, copy, fullcopy):
+def checkcopies(ctx, f, m1, m2, ca, cta, remote_ca, limit, diverge, copy,
+                fullcopy, incomplete, incompletediverge):
     """
     check possible copies of f from m1 to m2
 
@@ -460,14 +516,20 @@
     f = the filename to check
     m1 = the source manifest
     m2 = the destination manifest
-    ca = the changectx of the common ancestor
+    ca = the changectx of the common ancestor, overridden on graft
+    cta = topological common ancestor for graft-like scenarios
+    remote_ca = True if ca is outside cta::m1, False otherwise
     limit = the rev number to not search beyond
     diverge = record all diverges in this dict
     copy = record all non-divergent copies in this dict
     fullcopy = record all copies in this dict
+    incomplete = record non-divergent partial copies here
+    incompletediverge = record divergent partial copies here
     """
 
     ma = ca.manifest()
+    mta = cta.manifest()
+    backwards = ca != cta and not remote_ca and f in ma
     getfctx = _makegetfctx(ctx)
 
     def _related(f1, f2, limit):
@@ -502,31 +564,57 @@
             return False
 
     of = None
-    seen = set([f])
-    for oc in getfctx(f, m1[f]).ancestors():
+    seen = {f: [getfctx(f, m1[f])]}
+    for oc in seen[f][0].ancestors():
         ocr = oc.linkrev()
         of = oc.path()
         if of in seen:
+            seen[of].append(oc)
             # check limit late - grab last rename before
             if ocr < limit:
                 break
             continue
-        seen.add(of)
+        seen[of] = [oc]
 
-        fullcopy[f] = of # remember for dir rename detection
+        # remember for dir rename detection
+        if backwards:
+            fullcopy[of] = f # grafting backwards through renames
+        else:
+            fullcopy[f] = of
         if of not in m2:
             continue # no match, keep looking
         if m2[of] == ma.get(of):
-            break # no merge needed, quit early
+            return # no merge needed, quit early
         c2 = getfctx(of, m2[of])
-        cr = _related(oc, c2, ca.rev())
+        cr = _related(oc, c2, cta.rev())
         if cr and (of == f or of == c2.path()): # non-divergent
-            copy[f] = of
-            of = None
-            break
+            if backwards:
+                copy[of] = f
+            elif of in ma:
+                copy[f] = of
+            elif remote_ca: # special case: a <- b <- a -> b "ping-pong" rename
+                copy[of] = f
+                del fullcopy[f]
+                fullcopy[of] = f
+            else: # divergence w.r.t. graft CA on one side of topological CA
+                for sf in seen:
+                    if sf in ma and getfctx(sf, ma[sf]) in seen[sf]:
+                        assert sf not in diverge
+                        diverge[sf] = [f, of]
+                        break
+            return
 
-    if of in ma:
-        diverge.setdefault(of, []).append(f)
+    if of in mta:
+        if backwards or remote_ca:
+            incomplete[of] = f
+        else:
+            for sf in seen:
+                if sf in ma and getfctx(sf, ma[sf]) in seen[sf]:
+                    if cta == ca:
+                        diverge.setdefault(sf, []).append(f)
+                    else:
+                        incompletediverge[sf] = [of, f]
+                    return
 
 def duplicatecopies(repo, rev, fromrev, skiprev=None):
     '''reproduce copies from fromrev to rev in the dirstate
diff --git a/tests/test-graft.t b/tests/test-graft.t
--- a/tests/test-graft.t
+++ b/tests/test-graft.t
@@ -179,6 +179,13 @@
   committing changelog
   grafting 5:97f8bfe72746 "5"
     searching for copies back to rev 1
+    computing unmatched files in rotated DAG
+    computing unmatched files in unrotated DAG
+    unmatched files in other:
+     c
+    all copies found (* = to merge, ! = divergent, % = renamed and deleted):
+     src: 'c' -> dst: 'b' *
+    checking for directory renames
   resolving manifests
    branchmerge: True, force: True, partial: False
    ancestor: 4c60f11aa304, local: 6b9e5368ca4e+, remote: 97f8bfe72746
@@ -193,6 +200,13 @@
   scanning for duplicate grafts
   grafting 4:9c233e8e184d "4"
     searching for copies back to rev 1
+    computing unmatched files in rotated DAG
+    computing unmatched files in unrotated DAG
+    unmatched files in other:
+     c
+    all copies found (* = to merge, ! = divergent, % = renamed and deleted):
+     src: 'c' -> dst: 'b' *
+    checking for directory renames
   resolving manifests
    branchmerge: True, force: True, partial: False
    ancestor: 4c60f11aa304, local: 1905859650ec+, remote: 9c233e8e184d
@@ -427,8 +441,8 @@
   $ hg graft 3 --log -u foo
   grafting 3:4c60f11aa304 "3"
   warning: can't find ancestor for 'c' copied from 'b'!
-  $ hg log --template '{rev} {parents} {desc}\n' -r tip
-  14 1:5d205f8b35b6  3
+  $ hg log --template '{rev}:{node|short} {parents} {desc}\n' -r tip
+  14:0c921c65ef1e 1:5d205f8b35b6  3
   (grafted from 4c60f11aa304a54ae1c199feb94e7fc771e51ed8)
 
 Resolve conflicted graft
@@ -620,7 +634,7 @@
   date:        Thu Jan 01 00:00:00 1970 +0000
   summary:     2
   
-  changeset:   14:f64defefacee
+  changeset:   14:0c921c65ef1e
   parent:      1:5d205f8b35b6
   user:        foo
   date:        Thu Jan 01 00:00:00 1970 +0000
@@ -842,3 +856,290 @@
   |/
   o  0
   
+Graft from behind a move or rename
+NOTE: This is affected by bug 5343, and will need updating when it's fixed
+
+f50 tests a "ping-pong" rename case, where a file is renamed to the same name
+on both branches, then the rename is backed out on one branch, and the backout
+is grafted to the other branch. This creates a challenging b <- a <- b -> a
+rename sequence in the graft target, topological CA, graft CA and graft source,
+respectively. Since rename detection will run on the target side for such a
+sequence (as for technical reasons, we split the source and target sides not at
+the graft CA, but at the topological CA), it will pick up a false rename, and
+cause a spurious merge conflict. This false rename is always exactly the
+reverse of the true rename that would be detected on the source side, so deal
+with it by detecting this condition and reversing as necessary.
+
+  $ hg init ../graftmove
+  $ cd ../graftmove
+  $ echo c10 > f10
+  $ echo c20 > f20
+  $ echo c30 > f30
+  $ echo c40 > f40
+  $ echo c50 > f50
+  $ hg ci -qAm 0
+  $ hg mv f10 f11
+  $ hg mv f30 f31
+  $ hg mv f50 f51
+  $ hg ci -qAm 1
+  $ echo c12 > f11
+  $ hg mv f20 f22
+  $ hg mv f51 f50
+  $ hg ci -qAm 2
+  $ hg mv f31 f33
+  $ echo c43 > f40
+  $ hg ci -qAm 3
+  $ hg up -q 0
+  $ hg graft -r 2
+  grafting 2:52f80b3a6c3e "2"
+  merging f10 and f11 to f10
+  warning: can't find ancestor for 'f50' copied from 'f51'!
+  $ hg status --change .
+  M f10
+  A f22
+  R f20
+  $ hg cat f10
+  c12
+  $ hg cat f11
+  f11: no such file in rev 54f7d8995b01
+  [1]
+  $ hg graft -r 3
+  grafting 3:0f6524134ac0 "3"
+  note: possible conflict - f31 was renamed multiple times to:
+   f33
+   f30
+  warning: can't find ancestor for 'f33' copied from 'f31'!
+  $ hg up -q 0
+  $ hg mv f10 f16
+  $ echo c26 > f20
+  $ hg mv f30 f36
+  $ hg mv f40 f46
+  $ hg mv f50 f51
+  $ hg ci -qAm 6
+  $ hg graft -r 2
+  grafting 2:52f80b3a6c3e "2"
+  merging f16 and f11 to f16
+  merging f20 and f22 to f22
+  $ hg graft -r 3
+  grafting 3:0f6524134ac0 "3"
+  note: possible conflict - f31 was renamed multiple times to:
+   f36
+   f33
+  merging f46 and f40 to f46
+  warning: can't find ancestor for 'f33' copied from 'f31'!
+  $ hg log -CGv --patch --git
+  @  changeset:   8:db9925d9208e
+  |  tag:         tip
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  files:       f33 f46
+  |  description:
+  |  3
+  |
+  |
+  |  diff --git a/f33 b/f33
+  |  new file mode 100644
+  |  --- /dev/null
+  |  +++ b/f33
+  |  @@ -0,0 +1,1 @@
+  |  +c30
+  |  diff --git a/f46 b/f46
+  |  --- a/f46
+  |  +++ b/f46
+  |  @@ -1,1 +1,1 @@
+  |  -c40
+  |  +c43
+  |
+  o  changeset:   7:08113e8ff5c8
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  files:       f16 f20 f22 f50 f51
+  |  copies:      f22 (f20) f50 (f51)
+  |  description:
+  |  2
+  |
+  |
+  |  diff --git a/f16 b/f16
+  |  --- a/f16
+  |  +++ b/f16
+  |  @@ -1,1 +1,1 @@
+  |  -c10
+  |  +c12
+  |  diff --git a/f20 b/f22
+  |  rename from f20
+  |  rename to f22
+  |  diff --git a/f51 b/f50
+  |  rename from f51
+  |  rename to f50
+  |
+  o  changeset:   6:365d1fa57acb
+  |  parent:      0:1060512e332e
+  |  user:        test
+  |  date:        Thu Jan 01 00:00:00 1970 +0000
+  |  files:       f10 f16 f20 f30 f36 f40 f46 f50 f51
+  |  copies:      f16 (f10) f36 (f30) f46 (f40) f51 (f50)
+  |  description:
+  |  6
+  |
+  |
+  |  diff --git a/f10 b/f16
+  |  rename from f10
+  |  rename to f16
+  |  diff --git a/f20 b/f20
+  |  --- a/f20
+  |  +++ b/f20
+  |  @@ -1,1 +1,1 @@
+  |  -c20
+  |  +c26
+  |  diff --git a/f30 b/f36
+  |  rename from f30
+  |  rename to f36
+  |  diff --git a/f40 b/f46
+  |  rename from f40
+  |  rename to f46
+  |  diff --git a/f50 b/f51
+  |  rename from f50
+  |  rename to f51
+  |
+  | o  changeset:   5:d5015e1a1de5
+  | |  user:        test
+  | |  date:        Thu Jan 01 00:00:00 1970 +0000
+  | |  files:       f33 f40
+  | |  description:
+  | |  3
+  | |
+  | |
+  | |  diff --git a/f33 b/f33
+  | |  new file mode 100644
+  | |  --- /dev/null
+  | |  +++ b/f33
+  | |  @@ -0,0 +1,1 @@
+  | |  +c30
+  | |  diff --git a/f40 b/f40
+  | |  --- a/f40
+  | |  +++ b/f40
+  | |  @@ -1,1 +1,1 @@
+  | |  -c40
+  | |  +c43
+  | |
+  | o  changeset:   4:54f7d8995b01
+  |/   parent:      0:1060512e332e
+  |    user:        test
+  |    date:        Thu Jan 01 00:00:00 1970 +0000
+  |    files:       f10 f20 f22
+  |    copies:      f22 (f20)
+  |    description:
+  |    2
+  |
+  |
+  |    diff --git a/f10 b/f10
+  |    --- a/f10
+  |    +++ b/f10
+  |    @@ -1,1 +1,1 @@
+  |    -c10
+  |    +c12
+  |    diff --git a/f20 b/f22
+  |    rename from f20
+  |    rename to f22
+  |
+  | o  changeset:   3:0f6524134ac0
+  | |  user:        test
+  | |  date:        Thu Jan 01 00:00:00 1970 +0000
+  | |  files:       f31 f33 f40
+  | |  copies:      f33 (f31)
+  | |  description:
+  | |  3
+  | |
+  | |
+  | |  diff --git a/f31 b/f33
+  | |  rename from f31
+  | |  rename to f33
+  | |  diff --git a/f40 b/f40
+  | |  --- a/f40
+  | |  +++ b/f40
+  | |  @@ -1,1 +1,1 @@
+  | |  -c40
+  | |  +c43
+  | |
+  | o  changeset:   2:52f80b3a6c3e
+  | |  user:        test
+  | |  date:        Thu Jan 01 00:00:00 1970 +0000
+  | |  files:       f11 f20 f22 f50 f51
+  | |  copies:      f22 (f20) f50 (f51)
+  | |  description:
+  | |  2
+  | |
+  | |
+  | |  diff --git a/f11 b/f11
+  | |  --- a/f11
+  | |  +++ b/f11
+  | |  @@ -1,1 +1,1 @@
+  | |  -c10
+  | |  +c12
+  | |  diff --git a/f20 b/f22
+  | |  rename from f20
+  | |  rename to f22
+  | |  diff --git a/f51 b/f50
+  | |  rename from f51
+  | |  rename to f50
+  | |
+  | o  changeset:   1:7607a972f96d
+  |/   user:        test
+  |    date:        Thu Jan 01 00:00:00 1970 +0000
+  |    files:       f10 f11 f30 f31 f50 f51
+  |    copies:      f11 (f10) f31 (f30) f51 (f50)
+  |    description:
+  |    1
+  |
+  |
+  |    diff --git a/f10 b/f11
+  |    rename from f10
+  |    rename to f11
+  |    diff --git a/f30 b/f31
+  |    rename from f30
+  |    rename to f31
+  |    diff --git a/f50 b/f51
+  |    rename from f50
+  |    rename to f51
+  |
+  o  changeset:   0:1060512e332e
+     user:        test
+     date:        Thu Jan 01 00:00:00 1970 +0000
+     files:       f10 f20 f30 f40 f50
+     description:
+     0
+  
+  
+     diff --git a/f10 b/f10
+     new file mode 100644
+     --- /dev/null
+     +++ b/f10
+     @@ -0,0 +1,1 @@
+     +c10
+     diff --git a/f20 b/f20
+     new file mode 100644
+     --- /dev/null
+     +++ b/f20
+     @@ -0,0 +1,1 @@
+     +c20
+     diff --git a/f30 b/f30
+     new file mode 100644
+     --- /dev/null
+     +++ b/f30
+     @@ -0,0 +1,1 @@
+     +c30
+     diff --git a/f40 b/f40
+     new file mode 100644
+     --- /dev/null
+     +++ b/f40
+     @@ -0,0 +1,1 @@
+     +c40
+     diff --git a/f50 b/f50
+     new file mode 100644
+     --- /dev/null
+     +++ b/f50
+     @@ -0,0 +1,1 @@
+     +c50
+  
+  $ hg cat f22
+  c26
diff --git a/tests/test-rebase-conflicts.t b/tests/test-rebase-conflicts.t
--- a/tests/test-rebase-conflicts.t
+++ b/tests/test-rebase-conflicts.t
@@ -238,6 +238,10 @@
    merge against 9:e31216eec445
      detach base 8:8e4e2c1a07ae
     searching for copies back to rev 3
+    computing unmatched files in rotated DAG
+    computing unmatched files in unrotated DAG
+    unmatched files in other:
+     f2.txt
   resolving manifests
    branchmerge: True, force: True, partial: False
    ancestor: 8e4e2c1a07ae, local: 4bc80088dc6b+, remote: e31216eec445
@@ -255,6 +259,10 @@
    merge against 10:2f2496ddf49d
      detach base 9:e31216eec445
     searching for copies back to rev 3
+    computing unmatched files in rotated DAG
+    computing unmatched files in unrotated DAG
+    unmatched files in other:
+     f2.txt
   resolving manifests
    branchmerge: True, force: True, partial: False
    ancestor: e31216eec445, local: 19c888675e13+, remote: 2f2496ddf49d


More information about the Mercurial-devel mailing list