Show More
@@ -81,3 +81,51 b' def ancestor(a, b, pfunc):' | |||||
81 | gx = x.next() |
|
81 | gx = x.next() | |
82 | except StopIteration: |
|
82 | except StopIteration: | |
83 | return None |
|
83 | return None | |
|
84 | ||||
|
85 | def symmetricdifference(a, b, pfunc): | |||
|
86 | """symmetric difference of the sets of ancestors of a and b | |||
|
87 | ||||
|
88 | I.e. revisions that are ancestors of a or b, but not both. | |||
|
89 | """ | |||
|
90 | # basic idea: | |||
|
91 | # - mark a and b with different colors | |||
|
92 | # - walk the graph in topological order with the help of a heap; | |||
|
93 | # for each revision r: | |||
|
94 | # - if r has only one color, we want to return it | |||
|
95 | # - add colors[r] to its parents | |||
|
96 | # | |||
|
97 | # We keep track of the number of revisions in the heap that | |||
|
98 | # we may be interested in. We stop walking the graph as soon | |||
|
99 | # as this number reaches 0. | |||
|
100 | WHITE = 1 | |||
|
101 | BLACK = 2 | |||
|
102 | ALLCOLORS = WHITE | BLACK | |||
|
103 | colors = {a: WHITE, b: BLACK} | |||
|
104 | ||||
|
105 | visit = [-a, -b] | |||
|
106 | heapq.heapify(visit) | |||
|
107 | n_wanted = len(visit) | |||
|
108 | ret = [] | |||
|
109 | ||||
|
110 | while n_wanted: | |||
|
111 | r = -heapq.heappop(visit) | |||
|
112 | wanted = colors[r] != ALLCOLORS | |||
|
113 | n_wanted -= wanted | |||
|
114 | if wanted: | |||
|
115 | ret.append(r) | |||
|
116 | ||||
|
117 | for p in pfunc(r): | |||
|
118 | if p not in colors: | |||
|
119 | # first time we see p; add it to visit | |||
|
120 | n_wanted += wanted | |||
|
121 | colors[p] = colors[r] | |||
|
122 | heapq.heappush(visit, -p) | |||
|
123 | elif colors[p] != ALLCOLORS and colors[p] != colors[r]: | |||
|
124 | # at first we thought we wanted p, but now | |||
|
125 | # we know we don't really want it | |||
|
126 | n_wanted -= 1 | |||
|
127 | colors[p] |= colors[r] | |||
|
128 | ||||
|
129 | del colors[r] | |||
|
130 | ||||
|
131 | return ret |
@@ -7,7 +7,7 b'' | |||||
7 |
|
7 | |||
8 | from node import nullid, nullrev |
|
8 | from node import nullid, nullrev | |
9 | from i18n import _ |
|
9 | from i18n import _ | |
10 | import errno, util, os, heapq, filemerge |
|
10 | import errno, util, os, heapq, filemerge, ancestor | |
11 |
|
11 | |||
12 | def _checkunknown(wctx, mctx): |
|
12 | def _checkunknown(wctx, mctx): | |
13 | "check for collisions between unknown files and files in mctx" |
|
13 | "check for collisions between unknown files and files in mctx" | |
@@ -228,58 +228,6 b' def findcopies(repo, m1, m2, ma, limit):' | |||||
228 |
|
228 | |||
229 | return copy, diverge |
|
229 | return copy, diverge | |
230 |
|
230 | |||
231 | def _symmetricdifference(repo, rev1, rev2): |
|
|||
232 | """symmetric difference of the sets of ancestors of rev1 and rev2 |
|
|||
233 |
|
||||
234 | I.e. revisions that are ancestors of rev1 or rev2, but not both. |
|
|||
235 | """ |
|
|||
236 | # basic idea: |
|
|||
237 | # - mark rev1 and rev2 with different colors |
|
|||
238 | # - walk the graph in topological order with the help of a heap; |
|
|||
239 | # for each revision r: |
|
|||
240 | # - if r has only one color, we want to return it |
|
|||
241 | # - add colors[r] to its parents |
|
|||
242 | # |
|
|||
243 | # We keep track of the number of revisions in the heap that |
|
|||
244 | # we may be interested in. We stop walking the graph as soon |
|
|||
245 | # as this number reaches 0. |
|
|||
246 | WHITE = 1 |
|
|||
247 | BLACK = 2 |
|
|||
248 | ALLCOLORS = WHITE | BLACK |
|
|||
249 | colors = {rev1: WHITE, rev2: BLACK} |
|
|||
250 |
|
||||
251 | cl = repo.changelog |
|
|||
252 |
|
||||
253 | visit = [-rev1, -rev2] |
|
|||
254 | heapq.heapify(visit) |
|
|||
255 | n_wanted = len(visit) |
|
|||
256 | ret = [] |
|
|||
257 |
|
||||
258 | while n_wanted: |
|
|||
259 | r = -heapq.heappop(visit) |
|
|||
260 | wanted = colors[r] != ALLCOLORS |
|
|||
261 | n_wanted -= wanted |
|
|||
262 | if wanted: |
|
|||
263 | ret.append(r) |
|
|||
264 |
|
||||
265 | for p in cl.parentrevs(r): |
|
|||
266 | if p == nullrev: |
|
|||
267 | continue |
|
|||
268 | if p not in colors: |
|
|||
269 | # first time we see p; add it to visit |
|
|||
270 | n_wanted += wanted |
|
|||
271 | colors[p] = colors[r] |
|
|||
272 | heapq.heappush(visit, -p) |
|
|||
273 | elif colors[p] != ALLCOLORS and colors[p] != colors[r]: |
|
|||
274 | # at first we thought we wanted p, but now |
|
|||
275 | # we know we don't really want it |
|
|||
276 | n_wanted -= 1 |
|
|||
277 | colors[p] |= colors[r] |
|
|||
278 |
|
||||
279 | del colors[r] |
|
|||
280 |
|
||||
281 | return ret |
|
|||
282 |
|
||||
283 | def manifestmerge(repo, p1, p2, pa, overwrite, partial): |
|
231 | def manifestmerge(repo, p1, p2, pa, overwrite, partial): | |
284 | """ |
|
232 | """ | |
285 | Merge p1 and p2 with ancestor ma and generate merge action list |
|
233 | Merge p1 and p2 with ancestor ma and generate merge action list | |
@@ -332,7 +280,10 b' def manifestmerge(repo, p1, p2, pa, over' | |||||
332 | if rev1 is None: |
|
280 | if rev1 is None: | |
333 | # p1 is a workingctx |
|
281 | # p1 is a workingctx | |
334 | rev1 = p1.parents()[0].rev() |
|
282 | rev1 = p1.parents()[0].rev() | |
335 | limit = min(_symmetricdifference(repo, rev1, p2.rev())) |
|
283 | pr = repo.changelog.parentrevs | |
|
284 | def parents(rev): | |||
|
285 | return [p for p in pr(rev) if p != nullrev] | |||
|
286 | limit = min(ancestor.symmetricdifference(rev1, p2.rev(), parents)) | |||
336 | copy, diverge = findcopies(repo, m1, m2, ma, limit) |
|
287 | copy, diverge = findcopies(repo, m1, m2, ma, limit) | |
337 |
|
288 | |||
338 | for of, fl in diverge.items(): |
|
289 | for of, fl in diverge.items(): |
General Comments 0
You need to be logged in to leave comments.
Login now