5 # This software may be used and distributed according to the terms |
5 # This software may be used and distributed according to the terms |
6 # of the GNU General Public License, incorporated herein by reference. |
6 # of the GNU General Public License, incorporated herein by reference. |
7 |
7 |
8 from node import * |
8 from node import * |
9 from i18n import _ |
9 from i18n import _ |
10 import errno, util, os, tempfile, context |
10 import errno, util, os, tempfile, context, heapq |
11 |
11 |
12 def filemerge(repo, fw, fd, fo, wctx, mctx): |
12 def filemerge(repo, fw, fd, fo, wctx, mctx): |
13 """perform a 3-way merge in the working directory |
13 """perform a 3-way merge in the working directory |
14 |
14 |
15 fw = original filename in the working directory |
15 fw = original filename in the working directory |
250 copy[f] = dirmove[d] + f[len(d):] |
250 copy[f] = dirmove[d] + f[len(d):] |
251 break |
251 break |
252 |
252 |
253 return copy, diverge |
253 return copy, diverge |
254 |
254 |
|
255 def symmetricdifference(repo, rev1, rev2): |
|
256 """symmetric difference of the sets of ancestors of rev1 and rev2 |
|
257 |
|
258 I.e. revisions that are ancestors of rev1 or rev2, but not both. |
|
259 """ |
|
260 # basic idea: |
|
261 # - mark rev1 and rev2 with different colors |
|
262 # - walk the graph in topological order with the help of a heap; |
|
263 # for each revision r: |
|
264 # - if r has only one color, we want to return it |
|
265 # - add colors[r] to its parents |
|
266 # |
|
267 # We keep track of the number of revisions in the heap that |
|
268 # we may be interested in. We stop walking the graph as soon |
|
269 # as this number reaches 0. |
|
270 WHITE = 1 |
|
271 BLACK = 2 |
|
272 ALLCOLORS = WHITE | BLACK |
|
273 colors = {rev1: WHITE, rev2: BLACK} |
|
274 |
|
275 cl = repo.changelog |
|
276 |
|
277 visit = [-rev1, -rev2] |
|
278 heapq.heapify(visit) |
|
279 n_wanted = len(visit) |
|
280 ret = [] |
|
281 |
|
282 while n_wanted: |
|
283 r = -heapq.heappop(visit) |
|
284 wanted = colors[r] != ALLCOLORS |
|
285 n_wanted -= wanted |
|
286 if wanted: |
|
287 ret.append(r) |
|
288 |
|
289 for p in cl.parentrevs(r): |
|
290 if p == nullrev: |
|
291 continue |
|
292 if p not in colors: |
|
293 # first time we see p; add it to visit |
|
294 n_wanted += wanted |
|
295 colors[p] = colors[r] |
|
296 heapq.heappush(visit, -p) |
|
297 elif colors[p] != ALLCOLORS and colors[p] != colors[r]: |
|
298 # at first we thought we wanted p, but now |
|
299 # we know we don't really want it |
|
300 n_wanted -= 1 |
|
301 colors[p] |= colors[r] |
|
302 |
|
303 del colors[r] |
|
304 |
|
305 return ret |
|
306 |
255 def manifestmerge(repo, p1, p2, pa, overwrite, partial): |
307 def manifestmerge(repo, p1, p2, pa, overwrite, partial): |
256 """ |
308 """ |
257 Merge p1 and p2 with ancestor ma and generate merge action list |
309 Merge p1 and p2 with ancestor ma and generate merge action list |
258 |
310 |
259 overwrite = whether we clobber working files |
311 overwrite = whether we clobber working files |
288 def act(msg, m, f, *args): |
340 def act(msg, m, f, *args): |
289 repo.ui.debug(" %s: %s -> %s\n" % (f, msg, m)) |
341 repo.ui.debug(" %s: %s -> %s\n" % (f, msg, m)) |
290 action.append((f, m) + args) |
342 action.append((f, m) + args) |
291 |
343 |
292 if not (backwards or overwrite): |
344 if not (backwards or overwrite): |
293 copy, diverge = findcopies(repo, m1, m2, ma, pa.rev()) |
345 rev1 = p1.rev() |
|
346 if rev1 is None: |
|
347 # p1 is a workingctx |
|
348 rev1 = p1.parents()[0].rev() |
|
349 limit = min(symmetricdifference(repo, rev1, p2.rev())) |
|
350 copy, diverge = findcopies(repo, m1, m2, ma, limit) |
294 |
351 |
295 for of, fl in diverge.items(): |
352 for of, fl in diverge.items(): |
296 act("divergent renames", "dr", of, fl) |
353 act("divergent renames", "dr", of, fl) |
297 |
354 |
298 copied = dict.fromkeys(copy.values()) |
355 copied = dict.fromkeys(copy.values()) |