Show More
@@ -81,3 +81,51 b' def ancestor(a, b, pfunc):' | |||
|
81 | 81 | gx = x.next() |
|
82 | 82 | except StopIteration: |
|
83 | 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 | 8 | from node import nullid, nullrev |
|
9 | 9 | from i18n import _ |
|
10 | import errno, util, os, heapq, filemerge | |
|
10 | import errno, util, os, heapq, filemerge, ancestor | |
|
11 | 11 | |
|
12 | 12 | def _checkunknown(wctx, mctx): |
|
13 | 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 | 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 | 231 | def manifestmerge(repo, p1, p2, pa, overwrite, partial): |
|
284 | 232 | """ |
|
285 | 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 | 280 | if rev1 is None: |
|
333 | 281 | # p1 is a workingctx |
|
334 | 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 | 287 | copy, diverge = findcopies(repo, m1, m2, ma, limit) |
|
337 | 288 | |
|
338 | 289 | for of, fl in diverge.items(): |
General Comments 0
You need to be logged in to leave comments.
Login now