Mercurial > hg > mercurial-crew-with-dirclash
diff mercurial/merge.py @ 5149:ad6b97132b81
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.
author | Alexis S. L. Carvalho <alexis@cecm.usp.br> |
---|---|
date | Sun, 12 Aug 2007 12:15:10 -0300 |
parents | 8d9bdcbb2b18 |
children | 4ed58fe4fe13 f9b0e4f023c4 |
line wrap: on
line diff
--- a/mercurial/merge.py +++ b/mercurial/merge.py @@ -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 @@ 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 @@ 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)