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.

tests/test-issue672

@@ -0,0 +1,35 b''
+#!/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
+

tests/test-issue672.out

@@ -0,0 +1,33 b''
+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)

mercurial/merge.py

@@ -7,7 +7,7 b''
 
 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 b' def findcopies(repo, m1, m2, ma, limit):'
 
     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 b' def manifestmerge(repo, p1, p2, pa, over'
         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)