--- a/mercurial/merge.py Sat Aug 11 13:35:25 2007 +0200
+++ b/mercurial/merge.py Sun Aug 12 12:43:52 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:43:52 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:43:52 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)