Show More
@@ -1,307 +1,315 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 | import util |
|
10 | 10 | from node import nullrev |
|
11 | 11 | |
|
12 | 12 | def commonancestorsheads(pfunc, *nodes): |
|
13 | 13 | """Returns a set with the heads of all common ancestors of all nodes, |
|
14 | 14 | heads(::nodes[0] and ::nodes[1] and ...) . |
|
15 | 15 | |
|
16 | 16 | pfunc must return a list of parent vertices for a given vertex. |
|
17 | 17 | """ |
|
18 | 18 | if not isinstance(nodes, set): |
|
19 | 19 | nodes = set(nodes) |
|
20 | 20 | if nullrev in nodes: |
|
21 | 21 | return set() |
|
22 | 22 | if len(nodes) <= 1: |
|
23 | 23 | return nodes |
|
24 | 24 | |
|
25 | 25 | allseen = (1 << len(nodes)) - 1 |
|
26 | 26 | seen = [0] * (max(nodes) + 1) |
|
27 | 27 | for i, n in enumerate(nodes): |
|
28 | 28 | seen[n] = 1 << i |
|
29 | 29 | poison = 1 << (i + 1) |
|
30 | 30 | |
|
31 | 31 | gca = set() |
|
32 | 32 | interesting = len(nodes) |
|
33 | 33 | nv = len(seen) - 1 |
|
34 | 34 | while nv >= 0 and interesting: |
|
35 | 35 | v = nv |
|
36 | 36 | nv -= 1 |
|
37 | 37 | if not seen[v]: |
|
38 | 38 | continue |
|
39 | 39 | sv = seen[v] |
|
40 | 40 | if sv < poison: |
|
41 | 41 | interesting -= 1 |
|
42 | 42 | if sv == allseen: |
|
43 | 43 | gca.add(v) |
|
44 | 44 | sv |= poison |
|
45 | 45 | if v in nodes: |
|
46 | 46 | # history is linear |
|
47 | 47 | return set([v]) |
|
48 | 48 | if sv < poison: |
|
49 | 49 | for p in pfunc(v): |
|
50 | 50 | sp = seen[p] |
|
51 | 51 | if p == nullrev: |
|
52 | 52 | continue |
|
53 | 53 | if sp == 0: |
|
54 | 54 | seen[p] = sv |
|
55 | 55 | interesting += 1 |
|
56 | 56 | elif sp != sv: |
|
57 | 57 | seen[p] |= sv |
|
58 | 58 | else: |
|
59 | 59 | for p in pfunc(v): |
|
60 | 60 | if p == nullrev: |
|
61 | 61 | continue |
|
62 | 62 | sp = seen[p] |
|
63 | 63 | if sp and sp < poison: |
|
64 | 64 | interesting -= 1 |
|
65 | 65 | seen[p] = sv |
|
66 | 66 | return gca |
|
67 | 67 | |
|
68 | 68 | def ancestors(pfunc, *orignodes): |
|
69 | 69 | """ |
|
70 | 70 | Returns the common ancestors of a and b that are furthest from a |
|
71 | 71 | root (as measured by longest path). |
|
72 | 72 | |
|
73 | 73 | pfunc must return a list of parent vertices for a given vertex. |
|
74 | 74 | """ |
|
75 | 75 | def deepest(nodes): |
|
76 | 76 | interesting = {} |
|
77 | 77 | count = max(nodes) + 1 |
|
78 | 78 | depth = [0] * count |
|
79 | 79 | seen = [0] * count |
|
80 | 80 | mapping = [] |
|
81 | 81 | for (i, n) in enumerate(sorted(nodes)): |
|
82 | 82 | depth[n] = 1 |
|
83 | 83 | b = 1 << i |
|
84 | 84 | seen[n] = b |
|
85 | 85 | interesting[b] = 1 |
|
86 | 86 | mapping.append((b, n)) |
|
87 | 87 | nv = count - 1 |
|
88 | 88 | while nv >= 0 and len(interesting) > 1: |
|
89 | 89 | v = nv |
|
90 | 90 | nv -= 1 |
|
91 | 91 | dv = depth[v] |
|
92 | 92 | if dv == 0: |
|
93 | 93 | continue |
|
94 | 94 | sv = seen[v] |
|
95 | 95 | for p in pfunc(v): |
|
96 | 96 | if p == nullrev: |
|
97 | 97 | continue |
|
98 | 98 | dp = depth[p] |
|
99 | 99 | nsp = sp = seen[p] |
|
100 | 100 | if dp <= dv: |
|
101 | 101 | depth[p] = dv + 1 |
|
102 | 102 | if sp != sv: |
|
103 | 103 | interesting[sv] += 1 |
|
104 | 104 | nsp = seen[p] = sv |
|
105 | 105 | if sp: |
|
106 | 106 | interesting[sp] -= 1 |
|
107 | 107 | if interesting[sp] == 0: |
|
108 | 108 | del interesting[sp] |
|
109 | 109 | elif dv == dp - 1: |
|
110 | 110 | nsp = sp | sv |
|
111 | 111 | if nsp == sp: |
|
112 | 112 | continue |
|
113 | 113 | seen[p] = nsp |
|
114 | 114 | interesting.setdefault(nsp, 0) |
|
115 | 115 | interesting[nsp] += 1 |
|
116 | 116 | interesting[sp] -= 1 |
|
117 | 117 | if interesting[sp] == 0: |
|
118 | 118 | del interesting[sp] |
|
119 | 119 | interesting[sv] -= 1 |
|
120 | 120 | if interesting[sv] == 0: |
|
121 | 121 | del interesting[sv] |
|
122 | 122 | |
|
123 | 123 | if len(interesting) != 1: |
|
124 | 124 | return [] |
|
125 | 125 | |
|
126 | 126 | k = 0 |
|
127 | 127 | for i in interesting: |
|
128 | 128 | k |= i |
|
129 | 129 | return set(n for (i, n) in mapping if k & i) |
|
130 | 130 | |
|
131 | 131 | gca = commonancestorsheads(pfunc, *orignodes) |
|
132 | 132 | |
|
133 | 133 | if len(gca) <= 1: |
|
134 | 134 | return gca |
|
135 | 135 | return deepest(gca) |
|
136 | 136 | |
|
137 | 137 | def missingancestors(revs, bases, pfunc): |
|
138 | 138 | """Return all the ancestors of revs that are not ancestors of bases. |
|
139 | 139 | |
|
140 | 140 | This may include elements from revs. |
|
141 | 141 | |
|
142 | 142 | Equivalent to the revset (::revs - ::bases). Revs are returned in |
|
143 | 143 | revision number order, which is a topological order. |
|
144 | 144 | |
|
145 | 145 | revs and bases should both be iterables. pfunc must return a list of |
|
146 | 146 | parent revs for a given revs. |
|
147 | 147 | """ |
|
148 | 148 | |
|
149 | 149 | revsvisit = set(revs) |
|
150 | 150 | basesvisit = set(bases) |
|
151 | 151 | if not revsvisit: |
|
152 | 152 | return [] |
|
153 | 153 | if not basesvisit: |
|
154 | 154 | basesvisit.add(nullrev) |
|
155 | 155 | start = max(max(revsvisit), max(basesvisit)) |
|
156 | 156 | bothvisit = revsvisit.intersection(basesvisit) |
|
157 | 157 | revsvisit.difference_update(bothvisit) |
|
158 | 158 | basesvisit.difference_update(bothvisit) |
|
159 | 159 | # At this point, we hold the invariants that: |
|
160 | 160 | # - revsvisit is the set of nodes we know are an ancestor of at least one |
|
161 | 161 | # of the nodes in revs |
|
162 | 162 | # - basesvisit is the same for bases |
|
163 | 163 | # - bothvisit is the set of nodes we know are ancestors of at least one of |
|
164 | 164 | # the nodes in revs and one of the nodes in bases |
|
165 | 165 | # - a node may be in none or one, but not more, of revsvisit, basesvisit |
|
166 | 166 | # and bothvisit at any given time |
|
167 | 167 | # Now we walk down in reverse topo order, adding parents of nodes already |
|
168 | 168 | # visited to the sets while maintaining the invariants. When a node is |
|
169 | 169 | # found in both revsvisit and basesvisit, it is removed from them and |
|
170 | 170 | # added to bothvisit instead. When revsvisit becomes empty, there are no |
|
171 | 171 | # more ancestors of revs that aren't also ancestors of bases, so exit. |
|
172 | 172 | |
|
173 | 173 | missing = [] |
|
174 | 174 | for curr in xrange(start, nullrev, -1): |
|
175 | 175 | if not revsvisit: |
|
176 | 176 | break |
|
177 | 177 | |
|
178 | 178 | if curr in bothvisit: |
|
179 | 179 | bothvisit.remove(curr) |
|
180 | 180 | # curr's parents might have made it into revsvisit or basesvisit |
|
181 | 181 | # through another path |
|
182 | 182 | for p in pfunc(curr): |
|
183 | 183 | revsvisit.discard(p) |
|
184 | 184 | basesvisit.discard(p) |
|
185 | 185 | bothvisit.add(p) |
|
186 | 186 | continue |
|
187 | 187 | |
|
188 | 188 | # curr will never be in both revsvisit and basesvisit, since if it |
|
189 | 189 | # were it'd have been pushed to bothvisit |
|
190 | 190 | if curr in revsvisit: |
|
191 | 191 | missing.append(curr) |
|
192 | 192 | thisvisit = revsvisit |
|
193 | 193 | othervisit = basesvisit |
|
194 | 194 | elif curr in basesvisit: |
|
195 | 195 | thisvisit = basesvisit |
|
196 | 196 | othervisit = revsvisit |
|
197 | 197 | else: |
|
198 | 198 | # not an ancestor of revs or bases: ignore |
|
199 | 199 | continue |
|
200 | 200 | |
|
201 | 201 | thisvisit.remove(curr) |
|
202 | 202 | for p in pfunc(curr): |
|
203 | 203 | if p == nullrev: |
|
204 | 204 | pass |
|
205 | 205 | elif p in othervisit or p in bothvisit: |
|
206 | 206 | # p is implicitly in thisvisit. This means p is or should be |
|
207 | 207 | # in bothvisit |
|
208 | 208 | revsvisit.discard(p) |
|
209 | 209 | basesvisit.discard(p) |
|
210 | 210 | bothvisit.add(p) |
|
211 | 211 | else: |
|
212 | 212 | # visit later |
|
213 | 213 | thisvisit.add(p) |
|
214 | 214 | |
|
215 | 215 | missing.reverse() |
|
216 | 216 | return missing |
|
217 | 217 | |
|
218 | 218 | class lazyancestors(object): |
|
219 | 219 | def __init__(self, cl, revs, stoprev=0, inclusive=False): |
|
220 | 220 | """Create a new object generating ancestors for the given revs. Does |
|
221 | 221 | not generate revs lower than stoprev. |
|
222 | 222 | |
|
223 | 223 | This is computed lazily starting from revs. The object supports |
|
224 | 224 | iteration and membership. |
|
225 | 225 | |
|
226 | 226 | cl should be a changelog and revs should be an iterable. inclusive is |
|
227 | 227 | a boolean that indicates whether revs should be included. Revs lower |
|
228 | 228 | than stoprev will not be generated. |
|
229 | 229 | |
|
230 | 230 | Result does not include the null revision.""" |
|
231 | 231 | self._parentrevs = cl.parentrevs |
|
232 | 232 | self._initrevs = revs |
|
233 | 233 | self._stoprev = stoprev |
|
234 | 234 | self._inclusive = inclusive |
|
235 | 235 | |
|
236 | 236 | # Initialize data structures for __contains__. |
|
237 | 237 | # For __contains__, we use a heap rather than a deque because |
|
238 | 238 | # (a) it minimizes the number of parentrevs calls made |
|
239 | 239 | # (b) it makes the loop termination condition obvious |
|
240 | 240 | # Python's heap is a min-heap. Multiply all values by -1 to convert it |
|
241 | 241 | # into a max-heap. |
|
242 | 242 | self._containsvisit = [-rev for rev in revs] |
|
243 | 243 | heapq.heapify(self._containsvisit) |
|
244 | 244 | if inclusive: |
|
245 | 245 | self._containsseen = set(revs) |
|
246 | 246 | else: |
|
247 | 247 | self._containsseen = set() |
|
248 | 248 | |
|
249 | def __nonzero__(self): | |
|
250 | """False if the set is empty, True otherwise.""" | |
|
251 | try: | |
|
252 | iter(self).next() | |
|
253 | return True | |
|
254 | except StopIteration: | |
|
255 | return False | |
|
256 | ||
|
249 | 257 | def __iter__(self): |
|
250 | 258 | """Generate the ancestors of _initrevs in reverse topological order. |
|
251 | 259 | |
|
252 | 260 | If inclusive is False, yield a sequence of revision numbers starting |
|
253 | 261 | with the parents of each revision in revs, i.e., each revision is *not* |
|
254 | 262 | considered an ancestor of itself. Results are in breadth-first order: |
|
255 | 263 | parents of each rev in revs, then parents of those, etc. |
|
256 | 264 | |
|
257 | 265 | If inclusive is True, yield all the revs first (ignoring stoprev), |
|
258 | 266 | then yield all the ancestors of revs as when inclusive is False. |
|
259 | 267 | If an element in revs is an ancestor of a different rev it is not |
|
260 | 268 | yielded again.""" |
|
261 | 269 | seen = set() |
|
262 | 270 | revs = self._initrevs |
|
263 | 271 | if self._inclusive: |
|
264 | 272 | for rev in revs: |
|
265 | 273 | yield rev |
|
266 | 274 | seen.update(revs) |
|
267 | 275 | |
|
268 | 276 | parentrevs = self._parentrevs |
|
269 | 277 | stoprev = self._stoprev |
|
270 | 278 | visit = util.deque(revs) |
|
271 | 279 | |
|
272 | 280 | while visit: |
|
273 | 281 | for parent in parentrevs(visit.popleft()): |
|
274 | 282 | if parent >= stoprev and parent not in seen: |
|
275 | 283 | visit.append(parent) |
|
276 | 284 | seen.add(parent) |
|
277 | 285 | yield parent |
|
278 | 286 | |
|
279 | 287 | def __contains__(self, target): |
|
280 | 288 | """Test whether target is an ancestor of self._initrevs.""" |
|
281 | 289 | # Trying to do both __iter__ and __contains__ using the same visit |
|
282 | 290 | # heap and seen set is complex enough that it slows down both. Keep |
|
283 | 291 | # them separate. |
|
284 | 292 | seen = self._containsseen |
|
285 | 293 | if target in seen: |
|
286 | 294 | return True |
|
287 | 295 | |
|
288 | 296 | parentrevs = self._parentrevs |
|
289 | 297 | visit = self._containsvisit |
|
290 | 298 | stoprev = self._stoprev |
|
291 | 299 | heappop = heapq.heappop |
|
292 | 300 | heappush = heapq.heappush |
|
293 | 301 | |
|
294 | 302 | targetseen = False |
|
295 | 303 | |
|
296 | 304 | while visit and -visit[0] > target and not targetseen: |
|
297 | 305 | for parent in parentrevs(-heappop(visit)): |
|
298 | 306 | if parent < stoprev or parent in seen: |
|
299 | 307 | continue |
|
300 | 308 | # We need to make sure we push all parents into the heap so |
|
301 | 309 | # that we leave it in a consistent state for future calls. |
|
302 | 310 | heappush(visit, -parent) |
|
303 | 311 | seen.add(parent) |
|
304 | 312 | if parent == target: |
|
305 | 313 | targetseen = True |
|
306 | 314 | |
|
307 | 315 | return targetseen |
General Comments 0
You need to be logged in to leave comments.
Login now