merge: fix a copy detection bug (issue672)
authorAlexis S. L. Carvalho <alexis@cecm.usp.br>
Sun, 12 Aug 2007 12:15:10 -0300
changeset 5096 ad6b97132b81
parent 5095 f3f033def181
child 5097 f4f2baf7dc8a
child 5161 4ed58fe4fe13
merge: fix a copy detection bug (issue672) When merging rev1 and rev2, we want to search for copies that happened in rev1 but not in rev2 and vice-versa. We were starting the search at rev1/rev2 and then going back, stopping as soon as we reached the revno of the ancestor, but that can miss some cases (see the new test-issue672). Now we calculate the revisions that are ancestors of rev1 or rev2 (but not both) and make sure the search doesn't stop too early. Simplified test provided by mpm, based on a test case provided by Edward Lee.
mercurial/merge.py
tests/test-issue672
tests/test-issue672.out
--- a/mercurial/merge.py	Sat Aug 11 13:34:19 2007 +0200
+++ b/mercurial/merge.py	Sun Aug 12 12:15:10 2007 -0300
@@ -7,7 +7,7 @@
 
 from node import *
 from i18n import _
-import errno, util, os, tempfile, context
+import errno, util, os, tempfile, context, heapq
 
 def filemerge(repo, fw, fd, fo, wctx, mctx):
     """perform a 3-way merge in the working directory
@@ -252,6 +252,58 @@
 
     return copy, diverge
 
+def symmetricdifference(repo, rev1, rev2):
+    """symmetric difference of the sets of ancestors of rev1 and rev2
+    
+    I.e. revisions that are ancestors of rev1 or rev2, but not both.
+    """
+    # basic idea:
+    # - mark rev1 and rev2 with different colors
+    # - walk the graph in topological order with the help of a heap;
+    #   for each revision r:
+    #     - if r has only one color, we want to return it
+    #     - add colors[r] to its parents
+    #
+    # We keep track of the number of revisions in the heap that
+    # we may be interested in.  We stop walking the graph as soon
+    # as this number reaches 0.
+    WHITE = 1
+    BLACK = 2
+    ALLCOLORS = WHITE | BLACK
+    colors = {rev1: WHITE, rev2: BLACK}
+
+    cl = repo.changelog
+
+    visit = [-rev1, -rev2]
+    heapq.heapify(visit)
+    n_wanted = len(visit)
+    ret = []
+
+    while n_wanted:
+        r = -heapq.heappop(visit)
+        wanted = colors[r] != ALLCOLORS
+        n_wanted -= wanted
+        if wanted:
+            ret.append(r)
+
+        for p in cl.parentrevs(r):
+            if p == nullrev:
+                continue
+            if p not in colors:
+                # first time we see p; add it to visit
+                n_wanted += wanted
+                colors[p] = colors[r]
+                heapq.heappush(visit, -p)
+            elif colors[p] != ALLCOLORS and colors[p] != colors[r]:
+                # at first we thought we wanted p, but now
+                # we know we don't really want it
+                n_wanted -= 1
+                colors[p] |= colors[r]
+
+        del colors[r]
+
+    return ret
+
 def manifestmerge(repo, p1, p2, pa, overwrite, partial):
     """
     Merge p1 and p2 with ancestor ma and generate merge action list
@@ -290,7 +342,12 @@
         action.append((f, m) + args)
 
     if not (backwards or overwrite):
-        copy, diverge = findcopies(repo, m1, m2, ma, pa.rev())
+        rev1 = p1.rev()
+        if rev1 is None:
+            # p1 is a workingctx
+            rev1 = p1.parents()[0].rev()
+        limit = min(symmetricdifference(repo, rev1, p2.rev()))
+        copy, diverge = findcopies(repo, m1, m2, ma, limit)
 
     for of, fl in diverge.items():
         act("divergent renames", "dr", of, fl)
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-issue672	Sun Aug 12 12:15:10 2007 -0300
@@ -0,0 +1,35 @@
+#!/bin/sh
+
+# 0-2-4
+#  \ \ \
+#   1-3-5
+#
+# rename in #1, content change in #4.
+
+hg init t
+cd t
+
+touch 1
+touch 2
+hg commit -Am init -d "0 0"  # 0
+
+hg rename 1 1a
+hg commit -m rename -d "0 0" # 1
+
+hg co -C 0
+echo unrelated >> 2
+hg ci -m unrelated1 -d "0 0"  # 2
+
+hg merge --debug 1
+hg ci -m merge1 -d "0 0" # 3
+
+hg co -C 2
+echo hello >> 1
+hg ci -m unrelated2 -d "0 0" # 4
+
+hg co -C 3
+hg merge -y --debug 4
+
+hg co -C 4
+hg merge -y --debug 3
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tests/test-issue672.out	Sun Aug 12 12:15:10 2007 -0300
@@ -0,0 +1,33 @@
+adding 1
+adding 2
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+resolving manifests
+ overwrite None partial False
+ ancestor 81f4b099af3d local c64f439569a9+ remote 2f8037f47a5c
+ 1: other deleted -> r
+ 1a: remote created -> g
+removing 1
+getting 1a
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+(branch merge, don't forget to commit)
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+resolving manifests
+ overwrite None partial False
+ ancestor c64f439569a9 local ac7575e3c052+ remote 746e9549ea96
+ 1a: local moved to 1 -> m
+merging 1a and 1
+my 1a@ac7575e3c052+ other 1@746e9549ea96 ancestor 1@81f4b099af3d
+0 files updated, 1 files merged, 0 files removed, 0 files unresolved
+(branch merge, don't forget to commit)
+1 files updated, 0 files merged, 1 files removed, 0 files unresolved
+resolving manifests
+ overwrite None partial False
+ ancestor c64f439569a9 local 746e9549ea96+ remote ac7575e3c052
+ 1: remote moved to 1a -> m
+copying 1 to 1a
+merging 1 and 1a
+my 1@746e9549ea96+ other 1a@2f8037f47a5c ancestor 1@81f4b099af3d
+removing 1
+0 files updated, 1 files merged, 0 files removed, 0 files unresolved
+(branch merge, don't forget to commit)