Show More
@@ -0,0 +1,74 b'' | |||
|
1 | from mercurial import ancestor | |
|
2 | ||
|
3 | # graph is a dict of child->parent adjacency lists for this graph: | |
|
4 | # o 13 | |
|
5 | # | | |
|
6 | # | o 12 | |
|
7 | # | | | |
|
8 | # | | o 11 | |
|
9 | # | | |\ | |
|
10 | # | | | | o 10 | |
|
11 | # | | | | | | |
|
12 | # | o---+ | 9 | |
|
13 | # | | | | | | |
|
14 | # o | | | | 8 | |
|
15 | # / / / / | |
|
16 | # | | o | 7 | |
|
17 | # | | | | | |
|
18 | # o---+ | 6 | |
|
19 | # / / / | |
|
20 | # | | o 5 | |
|
21 | # | |/ | |
|
22 | # | o 4 | |
|
23 | # | | | |
|
24 | # o | 3 | |
|
25 | # | | | |
|
26 | # | o 2 | |
|
27 | # |/ | |
|
28 | # o 1 | |
|
29 | # | | |
|
30 | # o 0 | |
|
31 | ||
|
32 | graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], | |
|
33 | 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], | |
|
34 | 13: [8]} | |
|
35 | pfunc = graph.get | |
|
36 | ||
|
37 | def runmissingancestors(revs, bases): | |
|
38 | print "%% ancestors of %s and not of %s" % (revs, bases) | |
|
39 | print ancestor.missingancestors(revs, bases, pfunc) | |
|
40 | ||
|
41 | def test_missingancestors(): | |
|
42 | # Empty revs | |
|
43 | runmissingancestors([], [1]) | |
|
44 | runmissingancestors([], []) | |
|
45 | ||
|
46 | # If bases is empty, it's the same as if it were [nullrev] | |
|
47 | runmissingancestors([12], []) | |
|
48 | ||
|
49 | # Trivial case: revs == bases | |
|
50 | runmissingancestors([0], [0]) | |
|
51 | runmissingancestors([4, 5, 6], [6, 5, 4]) | |
|
52 | ||
|
53 | # With nullrev | |
|
54 | runmissingancestors([-1], [12]) | |
|
55 | runmissingancestors([12], [-1]) | |
|
56 | ||
|
57 | # 9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an | |
|
58 | # ancestor of 12 but not of 7. | |
|
59 | runmissingancestors([12], [9]) | |
|
60 | runmissingancestors([9], [12]) | |
|
61 | runmissingancestors([12, 9], [7]) | |
|
62 | runmissingancestors([7, 6], [12]) | |
|
63 | ||
|
64 | # More complex cases | |
|
65 | runmissingancestors([10], [11, 12]) | |
|
66 | runmissingancestors([11], [10]) | |
|
67 | runmissingancestors([11], [10, 12]) | |
|
68 | runmissingancestors([12], [10]) | |
|
69 | runmissingancestors([12], [11]) | |
|
70 | runmissingancestors([10, 11, 12], [13]) | |
|
71 | runmissingancestors([13], [10, 11, 12]) | |
|
72 | ||
|
73 | if __name__ == '__main__': | |
|
74 | test_missingancestors() |
@@ -0,0 +1,36 b'' | |||
|
1 | % ancestors of [] and not of [1] | |
|
2 | [] | |
|
3 | % ancestors of [] and not of [] | |
|
4 | [] | |
|
5 | % ancestors of [12] and not of [] | |
|
6 | [0, 1, 2, 4, 6, 7, 9, 12] | |
|
7 | % ancestors of [0] and not of [0] | |
|
8 | [] | |
|
9 | % ancestors of [4, 5, 6] and not of [6, 5, 4] | |
|
10 | [] | |
|
11 | % ancestors of [-1] and not of [12] | |
|
12 | [] | |
|
13 | % ancestors of [12] and not of [-1] | |
|
14 | [0, 1, 2, 4, 6, 7, 9, 12] | |
|
15 | % ancestors of [12] and not of [9] | |
|
16 | [12] | |
|
17 | % ancestors of [9] and not of [12] | |
|
18 | [] | |
|
19 | % ancestors of [12, 9] and not of [7] | |
|
20 | [6, 9, 12] | |
|
21 | % ancestors of [7, 6] and not of [12] | |
|
22 | [] | |
|
23 | % ancestors of [10] and not of [11, 12] | |
|
24 | [5, 10] | |
|
25 | % ancestors of [11] and not of [10] | |
|
26 | [3, 7, 11] | |
|
27 | % ancestors of [11] and not of [10, 12] | |
|
28 | [3, 11] | |
|
29 | % ancestors of [12] and not of [10] | |
|
30 | [6, 7, 9, 12] | |
|
31 | % ancestors of [12] and not of [11] | |
|
32 | [6, 9, 12] | |
|
33 | % ancestors of [10, 11, 12] and not of [13] | |
|
34 | [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12] | |
|
35 | % ancestors of [13] and not of [10, 11, 12] | |
|
36 | [8, 13] |
@@ -1,255 +1,173 b'' | |||
|
1 | 1 | # ancestor.py - generic DAG ancestor algorithm for mercurial |
|
2 | 2 | # |
|
3 | 3 | # Copyright 2006 Matt Mackall <mpm@selenic.com> |
|
4 | 4 | # |
|
5 | 5 | # This software may be used and distributed according to the terms of the |
|
6 | 6 | # GNU General Public License version 2 or any later version. |
|
7 | 7 | |
|
8 | 8 | import heapq |
|
9 | 9 | from node import nullrev |
|
10 | 10 | |
|
11 | 11 | def ancestor(a, b, pfunc): |
|
12 | 12 | """ |
|
13 | 13 | Returns the common ancestor of a and b that is furthest from a |
|
14 | 14 | root (as measured by longest path) or None if no ancestor is |
|
15 | 15 | found. If there are multiple common ancestors at the same |
|
16 | 16 | distance, the first one found is returned. |
|
17 | 17 | |
|
18 | 18 | pfunc must return a list of parent vertices for a given vertex |
|
19 | 19 | """ |
|
20 | 20 | |
|
21 | 21 | if a == b: |
|
22 | 22 | return a |
|
23 | 23 | |
|
24 | 24 | a, b = sorted([a, b]) |
|
25 | 25 | |
|
26 | 26 | # find depth from root of all ancestors |
|
27 | 27 | # depth is stored as a negative for heapq |
|
28 | 28 | parentcache = {} |
|
29 | 29 | visit = [a, b] |
|
30 | 30 | depth = {} |
|
31 | 31 | while visit: |
|
32 | 32 | vertex = visit[-1] |
|
33 | 33 | pl = pfunc(vertex) |
|
34 | 34 | parentcache[vertex] = pl |
|
35 | 35 | if not pl: |
|
36 | 36 | depth[vertex] = 0 |
|
37 | 37 | visit.pop() |
|
38 | 38 | else: |
|
39 | 39 | for p in pl: |
|
40 | 40 | if p == a or p == b: # did we find a or b as a parent? |
|
41 | 41 | return p # we're done |
|
42 | 42 | if p not in depth: |
|
43 | 43 | visit.append(p) |
|
44 | 44 | if visit[-1] == vertex: |
|
45 | 45 | # -(maximum distance of parents + 1) |
|
46 | 46 | depth[vertex] = min([depth[p] for p in pl]) - 1 |
|
47 | 47 | visit.pop() |
|
48 | 48 | |
|
49 | 49 | # traverse ancestors in order of decreasing distance from root |
|
50 | 50 | def ancestors(vertex): |
|
51 | 51 | h = [(depth[vertex], vertex)] |
|
52 | 52 | seen = set() |
|
53 | 53 | while h: |
|
54 | 54 | d, n = heapq.heappop(h) |
|
55 | 55 | if n not in seen: |
|
56 | 56 | seen.add(n) |
|
57 | 57 | yield (d, n) |
|
58 | 58 | for p in parentcache[n]: |
|
59 | 59 | heapq.heappush(h, (depth[p], p)) |
|
60 | 60 | |
|
61 | 61 | def generations(vertex): |
|
62 | 62 | sg, s = None, set() |
|
63 | 63 | for g, v in ancestors(vertex): |
|
64 | 64 | if g != sg: |
|
65 | 65 | if sg: |
|
66 | 66 | yield sg, s |
|
67 | 67 | sg, s = g, set((v,)) |
|
68 | 68 | else: |
|
69 | 69 | s.add(v) |
|
70 | 70 | yield sg, s |
|
71 | 71 | |
|
72 | 72 | x = generations(a) |
|
73 | 73 | y = generations(b) |
|
74 | 74 | gx = x.next() |
|
75 | 75 | gy = y.next() |
|
76 | 76 | |
|
77 | 77 | # increment each ancestor list until it is closer to root than |
|
78 | 78 | # the other, or they match |
|
79 | 79 | try: |
|
80 | 80 | while True: |
|
81 | 81 | if gx[0] == gy[0]: |
|
82 | 82 | for v in gx[1]: |
|
83 | 83 | if v in gy[1]: |
|
84 | 84 | return v |
|
85 | 85 | gy = y.next() |
|
86 | 86 | gx = x.next() |
|
87 | 87 | elif gx[0] > gy[0]: |
|
88 | 88 | gy = y.next() |
|
89 | 89 | else: |
|
90 | 90 | gx = x.next() |
|
91 | 91 | except StopIteration: |
|
92 | 92 | return None |
|
93 | 93 | |
|
94 | 94 | def missingancestors(revs, bases, pfunc): |
|
95 | 95 | """Return all the ancestors of revs that are not ancestors of bases. |
|
96 | 96 | |
|
97 | 97 | This may include elements from revs. |
|
98 | 98 | |
|
99 | 99 | Equivalent to the revset (::revs - ::bases). Revs are returned in |
|
100 | 100 | revision number order, which is a topological order. |
|
101 | 101 | |
|
102 | 102 | revs and bases should both be iterables. pfunc must return a list of |
|
103 | 103 | parent revs for a given revs. |
|
104 | ||
|
105 | graph is a dict of child->parent adjacency lists for this graph: | |
|
106 | o 13 | |
|
107 | | | |
|
108 | | o 12 | |
|
109 | | | | |
|
110 | | | o 11 | |
|
111 | | | |\ | |
|
112 | | | | | o 10 | |
|
113 | | | | | | | |
|
114 | | o---+ | 9 | |
|
115 | | | | | | | |
|
116 | o | | | | 8 | |
|
117 | / / / / | |
|
118 | | | o | 7 | |
|
119 | | | | | | |
|
120 | o---+ | 6 | |
|
121 | / / / | |
|
122 | | | o 5 | |
|
123 | | |/ | |
|
124 | | o 4 | |
|
125 | | | | |
|
126 | o | 3 | |
|
127 | | | | |
|
128 | | o 2 | |
|
129 | |/ | |
|
130 | o 1 | |
|
131 | | | |
|
132 | o 0 | |
|
133 | >>> graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], | |
|
134 | ... 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], | |
|
135 | ... 13: [8]} | |
|
136 | >>> pfunc = graph.get | |
|
137 | ||
|
138 | Empty revs | |
|
139 | >>> missingancestors([], [1], pfunc) | |
|
140 | [] | |
|
141 | >>> missingancestors([], [], pfunc) | |
|
142 | [] | |
|
143 | ||
|
144 | If bases is empty, it's the same as if it were [nullrev] | |
|
145 | >>> missingancestors([12], [], pfunc) | |
|
146 | [0, 1, 2, 4, 6, 7, 9, 12] | |
|
147 | ||
|
148 | Trivial case: revs == bases | |
|
149 | >>> missingancestors([0], [0], pfunc) | |
|
150 | [] | |
|
151 | >>> missingancestors([4, 5, 6], [6, 5, 4], pfunc) | |
|
152 | [] | |
|
153 | ||
|
154 | With nullrev | |
|
155 | >>> missingancestors([-1], [12], pfunc) | |
|
156 | [] | |
|
157 | >>> missingancestors([12], [-1], pfunc) | |
|
158 | [0, 1, 2, 4, 6, 7, 9, 12] | |
|
159 | ||
|
160 | 9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an | |
|
161 | ancestor of 12 but not of 7. | |
|
162 | >>> missingancestors([12], [9], pfunc) | |
|
163 | [12] | |
|
164 | >>> missingancestors([9], [12], pfunc) | |
|
165 | [] | |
|
166 | >>> missingancestors([12, 9], [7], pfunc) | |
|
167 | [6, 9, 12] | |
|
168 | >>> missingancestors([7, 6], [12], pfunc) | |
|
169 | [] | |
|
170 | ||
|
171 | More complex cases | |
|
172 | >>> missingancestors([10], [11, 12], pfunc) | |
|
173 | [5, 10] | |
|
174 | >>> missingancestors([11], [10], pfunc) | |
|
175 | [3, 7, 11] | |
|
176 | >>> missingancestors([11], [10, 12], pfunc) | |
|
177 | [3, 11] | |
|
178 | >>> missingancestors([12], [10], pfunc) | |
|
179 | [6, 7, 9, 12] | |
|
180 | >>> missingancestors([12], [11], pfunc) | |
|
181 | [6, 9, 12] | |
|
182 | >>> missingancestors([10, 11, 12], [13], pfunc) | |
|
183 | [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12] | |
|
184 | >>> missingancestors([13], [10, 11, 12], pfunc) | |
|
185 | [8, 13] | |
|
186 | 104 | """ |
|
187 | 105 | |
|
188 | 106 | revsvisit = set(revs) |
|
189 | 107 | basesvisit = set(bases) |
|
190 | 108 | if not revsvisit: |
|
191 | 109 | return [] |
|
192 | 110 | if not basesvisit: |
|
193 | 111 | basesvisit.add(nullrev) |
|
194 | 112 | start = max(max(revsvisit), max(basesvisit)) |
|
195 | 113 | bothvisit = revsvisit.intersection(basesvisit) |
|
196 | 114 | revsvisit.difference_update(bothvisit) |
|
197 | 115 | basesvisit.difference_update(bothvisit) |
|
198 | 116 | # At this point, we hold the invariants that: |
|
199 | 117 | # - revsvisit is the set of nodes we know are an ancestor of at least one |
|
200 | 118 | # of the nodes in revs |
|
201 | 119 | # - basesvisit is the same for bases |
|
202 | 120 | # - bothvisit is the set of nodes we know are ancestors of at least one of |
|
203 | 121 | # the nodes in revs and one of the nodes in bases |
|
204 | 122 | # - a node may be in none or one, but not more, of revsvisit, basesvisit |
|
205 | 123 | # and bothvisit at any given time |
|
206 | 124 | # Now we walk down in reverse topo order, adding parents of nodes already |
|
207 | 125 | # visited to the sets while maintaining the invariants. When a node is |
|
208 | 126 | # found in both revsvisit and basesvisit, it is removed from them and |
|
209 | 127 | # added to bothvisit instead. When revsvisit becomes empty, there are no |
|
210 | 128 | # more ancestors of revs that aren't also ancestors of bases, so exit. |
|
211 | 129 | |
|
212 | 130 | missing = [] |
|
213 | 131 | for curr in xrange(start, nullrev, -1): |
|
214 | 132 | if not revsvisit: |
|
215 | 133 | break |
|
216 | 134 | |
|
217 | 135 | if curr in bothvisit: |
|
218 | 136 | bothvisit.remove(curr) |
|
219 | 137 | # curr's parents might have made it into revsvisit or basesvisit |
|
220 | 138 | # through another path |
|
221 | 139 | for p in pfunc(curr): |
|
222 | 140 | revsvisit.discard(p) |
|
223 | 141 | basesvisit.discard(p) |
|
224 | 142 | bothvisit.add(p) |
|
225 | 143 | continue |
|
226 | 144 | |
|
227 | 145 | # curr will never be in both revsvisit and basesvisit, since if it |
|
228 | 146 | # were it'd have been pushed to bothvisit |
|
229 | 147 | if curr in revsvisit: |
|
230 | 148 | missing.append(curr) |
|
231 | 149 | thisvisit = revsvisit |
|
232 | 150 | othervisit = basesvisit |
|
233 | 151 | elif curr in basesvisit: |
|
234 | 152 | thisvisit = basesvisit |
|
235 | 153 | othervisit = revsvisit |
|
236 | 154 | else: |
|
237 | 155 | # not an ancestor of revs or bases: ignore |
|
238 | 156 | continue |
|
239 | 157 | |
|
240 | 158 | thisvisit.remove(curr) |
|
241 | 159 | for p in pfunc(curr): |
|
242 | 160 | if p == nullrev: |
|
243 | 161 | pass |
|
244 | 162 | elif p in othervisit or p in bothvisit: |
|
245 | 163 | # p is implicitly in thisvisit. This means p is or should be |
|
246 | 164 | # in bothvisit |
|
247 | 165 | revsvisit.discard(p) |
|
248 | 166 | basesvisit.discard(p) |
|
249 | 167 | bothvisit.add(p) |
|
250 | 168 | else: |
|
251 | 169 | # visit later |
|
252 | 170 | thisvisit.add(p) |
|
253 | 171 | |
|
254 | 172 | missing.reverse() |
|
255 | 173 | return missing |
General Comments 0
You need to be logged in to leave comments.
Login now