Show More
@@ -81,43 +81,3 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 sides |
|
|||
92 | # - if a parent's children are all on the same side, the parent is |
|
|||
93 | # on that side, otherwise it is on no side |
|
|||
94 | # - walk the graph in topological order with the help of a heap; |
|
|||
95 | # - add unseen parents to side map |
|
|||
96 | # - clear side of any parent that has children on different sides |
|
|||
97 | # - track number of unvisited nodes that might still be on a side |
|
|||
98 | # - quit when interesting nodes is zero |
|
|||
99 | if a == b: |
|
|||
100 | return [a] |
|
|||
101 |
|
||||
102 | side = {a: -1, b: 1} |
|
|||
103 | visit = [-a, -b] |
|
|||
104 | heapq.heapify(visit) |
|
|||
105 | interesting = len(visit) |
|
|||
106 |
|
||||
107 | while interesting: |
|
|||
108 | r = -heapq.heappop(visit) |
|
|||
109 | if side[r]: |
|
|||
110 | interesting -= 1 |
|
|||
111 | for p in pfunc(r): |
|
|||
112 | if p not in side: |
|
|||
113 | # first time we see p; add it to visit |
|
|||
114 | side[p] = side[r] |
|
|||
115 | if side[p]: |
|
|||
116 | interesting += 1 |
|
|||
117 | heapq.heappush(visit, -p) |
|
|||
118 | elif side[p] and side[p] != side[r]: |
|
|||
119 | # p was interesting but now we know better |
|
|||
120 | side[p] = 0 |
|
|||
121 | interesting -= 1 |
|
|||
122 |
|
||||
123 | return [r for r in side if side[r]] |
|
@@ -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 util, |
|
10 | import util, heapq | |
11 |
|
11 | |||
12 | def _nonoverlap(d1, d2, d3): |
|
12 | def _nonoverlap(d1, d2, d3): | |
13 | "Return list of elements in d1 not in d2 or d3" |
|
13 | "Return list of elements in d1 not in d2 or d3" | |
@@ -53,6 +53,43 b' def _findoldnames(fctx, limit):' | |||||
53 | old.sort() |
|
53 | old.sort() | |
54 | return [o[1] for o in old] |
|
54 | return [o[1] for o in old] | |
55 |
|
55 | |||
|
56 | def _symmetricdifference(a, b, pfunc): | |||
|
57 | """find revisions that are ancestors of a or b, but not both""" | |||
|
58 | # basic idea: | |||
|
59 | # - mark a and b with different sides | |||
|
60 | # - if a parent's children are all on the same side, the parent is | |||
|
61 | # on that side, otherwise it is on no side | |||
|
62 | # - walk the graph in topological order with the help of a heap; | |||
|
63 | # - add unseen parents to side map | |||
|
64 | # - clear side of any parent that has children on different sides | |||
|
65 | # - track number of unvisited nodes that might still be on a side | |||
|
66 | # - quit when interesting nodes is zero | |||
|
67 | if a == b: | |||
|
68 | return [a] | |||
|
69 | ||||
|
70 | side = {a: -1, b: 1} | |||
|
71 | visit = [-a, -b] | |||
|
72 | heapq.heapify(visit) | |||
|
73 | interesting = len(visit) | |||
|
74 | ||||
|
75 | while interesting: | |||
|
76 | r = -heapq.heappop(visit) | |||
|
77 | if side[r]: | |||
|
78 | interesting -= 1 | |||
|
79 | for p in pfunc(r): | |||
|
80 | if p not in side: | |||
|
81 | # first time we see p; add it to visit | |||
|
82 | side[p] = side[r] | |||
|
83 | if side[p]: | |||
|
84 | interesting += 1 | |||
|
85 | heapq.heappush(visit, -p) | |||
|
86 | elif side[p] and side[p] != side[r]: | |||
|
87 | # p was interesting but now we know better | |||
|
88 | side[p] = 0 | |||
|
89 | interesting -= 1 | |||
|
90 | ||||
|
91 | return [r for r in side if side[r]] | |||
|
92 | ||||
56 | def copies(repo, c1, c2, ca, checkdirs=False): |
|
93 | def copies(repo, c1, c2, ca, checkdirs=False): | |
57 | """ |
|
94 | """ | |
58 | Find moves and copies between context c1 and c2 |
|
95 | Find moves and copies between context c1 and c2 | |
@@ -69,7 +106,7 b' def copies(repo, c1, c2, ca, checkdirs=F' | |||||
69 | pr = repo.changelog.parentrevs |
|
106 | pr = repo.changelog.parentrevs | |
70 | def parents(rev): |
|
107 | def parents(rev): | |
71 | return [p for p in pr(rev) if p != nullrev] |
|
108 | return [p for p in pr(rev) if p != nullrev] | |
72 |
limit = min( |
|
109 | limit = min(_symmetricdifference(rev1, rev2, parents)) | |
73 | m1 = c1.manifest() |
|
110 | m1 = c1.manifest() | |
74 | m2 = c2.manifest() |
|
111 | m2 = c2.manifest() | |
75 | ma = ca.manifest() |
|
112 | ma = ca.manifest() |
General Comments 0
You need to be logged in to leave comments.
Login now