ancestor.py
255 lines
| 7.4 KiB
| text/x-python
|
PythonLexer
/ mercurial / ancestor.py
Matt Mackall
|
r3135 | # ancestor.py - generic DAG ancestor algorithm for mercurial | ||
# | ||||
# Copyright 2006 Matt Mackall <mpm@selenic.com> | ||||
# | ||||
Martin Geisler
|
r8225 | # This software may be used and distributed according to the terms of the | ||
Matt Mackall
|
r10263 | # GNU General Public License version 2 or any later version. | ||
Matt Mackall
|
r3135 | |||
import heapq | ||||
Siddharth Agarwal
|
r17970 | from node import nullrev | ||
Matt Mackall
|
r3135 | |||
def ancestor(a, b, pfunc): | ||||
""" | ||||
Matt Mackall
|
r13554 | Returns the common ancestor of a and b that is furthest from a | ||
root (as measured by longest path) or None if no ancestor is | ||||
found. If there are multiple common ancestors at the same | ||||
distance, the first one found is returned. | ||||
Matt Mackall
|
r3135 | |||
Sune Foldager
|
r9915 | pfunc must return a list of parent vertices for a given vertex | ||
Matt Mackall
|
r3135 | """ | ||
if a == b: | ||||
return a | ||||
Matt Mackall
|
r11418 | a, b = sorted([a, b]) | ||
Matt Mackall
|
r3135 | # find depth from root of all ancestors | ||
Matt Mackall
|
r13554 | # depth is stored as a negative for heapq | ||
Nicolas Dumazet
|
r7882 | parentcache = {} | ||
Matt Mackall
|
r3135 | visit = [a, b] | ||
depth = {} | ||||
while visit: | ||||
vertex = visit[-1] | ||||
pl = pfunc(vertex) | ||||
Nicolas Dumazet
|
r7882 | parentcache[vertex] = pl | ||
Matt Mackall
|
r3135 | if not pl: | ||
depth[vertex] = 0 | ||||
visit.pop() | ||||
else: | ||||
for p in pl: | ||||
Matt Mackall
|
r12401 | if p == a or p == b: # did we find a or b as a parent? | ||
Matt Mackall
|
r3135 | return p # we're done | ||
if p not in depth: | ||||
visit.append(p) | ||||
if visit[-1] == vertex: | ||||
Matt Mackall
|
r13554 | # -(maximum distance of parents + 1) | ||
Matt Mackall
|
r3135 | depth[vertex] = min([depth[p] for p in pl]) - 1 | ||
visit.pop() | ||||
# traverse ancestors in order of decreasing distance from root | ||||
def ancestors(vertex): | ||||
h = [(depth[vertex], vertex)] | ||||
Benoit Boissinot
|
r8465 | seen = set() | ||
Matt Mackall
|
r3135 | while h: | ||
d, n = heapq.heappop(h) | ||||
if n not in seen: | ||||
Benoit Boissinot
|
r8465 | seen.add(n) | ||
Matt Mackall
|
r3135 | yield (d, n) | ||
Nicolas Dumazet
|
r7882 | for p in parentcache[n]: | ||
Matt Mackall
|
r3135 | heapq.heappush(h, (depth[p], p)) | ||
def generations(vertex): | ||||
Benoit Boissinot
|
r8465 | sg, s = None, set() | ||
Thomas Arendsen Hein
|
r3673 | for g, v in ancestors(vertex): | ||
Matt Mackall
|
r3135 | if g != sg: | ||
if sg: | ||||
yield sg, s | ||||
Benoit Boissinot
|
r8465 | sg, s = g, set((v,)) | ||
Matt Mackall
|
r3135 | else: | ||
Benoit Boissinot
|
r8465 | s.add(v) | ||
Matt Mackall
|
r3135 | yield sg, s | ||
x = generations(a) | ||||
y = generations(b) | ||||
gx = x.next() | ||||
gy = y.next() | ||||
# increment each ancestor list until it is closer to root than | ||||
# the other, or they match | ||||
try: | ||||
Martin Geisler
|
r14494 | while True: | ||
Matt Mackall
|
r3135 | if gx[0] == gy[0]: | ||
for v in gx[1]: | ||||
if v in gy[1]: | ||||
return v | ||||
gy = y.next() | ||||
gx = x.next() | ||||
elif gx[0] > gy[0]: | ||||
gy = y.next() | ||||
else: | ||||
gx = x.next() | ||||
except StopIteration: | ||||
return None | ||||
Siddharth Agarwal
|
r17970 | |||
def missingancestors(revs, bases, pfunc): | ||||
"""Return all the ancestors of revs that are not ancestors of bases. | ||||
This may include elements from revs. | ||||
Equivalent to the revset (::revs - ::bases). Revs are returned in | ||||
revision number order, which is a topological order. | ||||
revs and bases should both be iterables. pfunc must return a list of | ||||
parent revs for a given revs. | ||||
graph is a dict of child->parent adjacency lists for this graph: | ||||
o 13 | ||||
| | ||||
| o 12 | ||||
| | | ||||
| | o 11 | ||||
| | |\ | ||||
| | | | o 10 | ||||
| | | | | | ||||
| o---+ | 9 | ||||
| | | | | | ||||
o | | | | 8 | ||||
/ / / / | ||||
| | o | 7 | ||||
| | | | | ||||
o---+ | 6 | ||||
/ / / | ||||
| | o 5 | ||||
| |/ | ||||
| o 4 | ||||
| | | ||||
o | 3 | ||||
| | | ||||
| o 2 | ||||
|/ | ||||
o 1 | ||||
| | ||||
o 0 | ||||
>>> graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4], | ||||
... 7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9], | ||||
... 13: [8]} | ||||
>>> pfunc = graph.get | ||||
Empty revs | ||||
>>> missingancestors([], [1], pfunc) | ||||
[] | ||||
>>> missingancestors([], [], pfunc) | ||||
[] | ||||
If bases is empty, it's the same as if it were [nullrev] | ||||
>>> missingancestors([12], [], pfunc) | ||||
[0, 1, 2, 4, 6, 7, 9, 12] | ||||
Trivial case: revs == bases | ||||
>>> missingancestors([0], [0], pfunc) | ||||
[] | ||||
>>> missingancestors([4, 5, 6], [6, 5, 4], pfunc) | ||||
[] | ||||
With nullrev | ||||
>>> missingancestors([-1], [12], pfunc) | ||||
[] | ||||
>>> missingancestors([12], [-1], pfunc) | ||||
[0, 1, 2, 4, 6, 7, 9, 12] | ||||
9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an | ||||
ancestor of 12 but not of 7. | ||||
>>> missingancestors([12], [9], pfunc) | ||||
[12] | ||||
>>> missingancestors([9], [12], pfunc) | ||||
[] | ||||
>>> missingancestors([12, 9], [7], pfunc) | ||||
[6, 9, 12] | ||||
>>> missingancestors([7, 6], [12], pfunc) | ||||
[] | ||||
More complex cases | ||||
>>> missingancestors([10], [11, 12], pfunc) | ||||
[5, 10] | ||||
>>> missingancestors([11], [10], pfunc) | ||||
[3, 7, 11] | ||||
>>> missingancestors([11], [10, 12], pfunc) | ||||
[3, 11] | ||||
>>> missingancestors([12], [10], pfunc) | ||||
[6, 7, 9, 12] | ||||
>>> missingancestors([12], [11], pfunc) | ||||
[6, 9, 12] | ||||
>>> missingancestors([10, 11, 12], [13], pfunc) | ||||
[0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12] | ||||
>>> missingancestors([13], [10, 11, 12], pfunc) | ||||
[8, 13] | ||||
""" | ||||
revsvisit = set(revs) | ||||
basesvisit = set(bases) | ||||
if not revsvisit: | ||||
return [] | ||||
if not basesvisit: | ||||
basesvisit.add(nullrev) | ||||
start = max(max(revsvisit), max(basesvisit)) | ||||
bothvisit = revsvisit.intersection(basesvisit) | ||||
revsvisit.difference_update(bothvisit) | ||||
basesvisit.difference_update(bothvisit) | ||||
# At this point, we hold the invariants that: | ||||
# - revsvisit is the set of nodes we know are an ancestor of at least one | ||||
# of the nodes in revs | ||||
# - basesvisit is the same for bases | ||||
# - bothvisit is the set of nodes we know are ancestors of at least one of | ||||
# the nodes in revs and one of the nodes in bases | ||||
# - a node may be in none or one, but not more, of revsvisit, basesvisit | ||||
# and bothvisit at any given time | ||||
# Now we walk down in reverse topo order, adding parents of nodes already | ||||
# visited to the sets while maintaining the invariants. When a node is | ||||
# found in both revsvisit and basesvisit, it is removed from them and | ||||
# added to bothvisit instead. When revsvisit becomes empty, there are no | ||||
# more ancestors of revs that aren't also ancestors of bases, so exit. | ||||
missing = [] | ||||
for curr in xrange(start, nullrev, -1): | ||||
if not revsvisit: | ||||
break | ||||
if curr in bothvisit: | ||||
bothvisit.remove(curr) | ||||
# curr's parents might have made it into revsvisit or basesvisit | ||||
# through another path | ||||
for p in pfunc(curr): | ||||
revsvisit.discard(p) | ||||
basesvisit.discard(p) | ||||
bothvisit.add(p) | ||||
continue | ||||
# curr will never be in both revsvisit and basesvisit, since if it | ||||
# were it'd have been pushed to bothvisit | ||||
if curr in revsvisit: | ||||
missing.append(curr) | ||||
thisvisit = revsvisit | ||||
othervisit = basesvisit | ||||
elif curr in basesvisit: | ||||
thisvisit = basesvisit | ||||
othervisit = revsvisit | ||||
else: | ||||
Siddharth Agarwal
|
r17976 | # not an ancestor of revs or bases: ignore | ||
Siddharth Agarwal
|
r17970 | continue | ||
thisvisit.remove(curr) | ||||
for p in pfunc(curr): | ||||
if p == nullrev: | ||||
pass | ||||
elif p in othervisit or p in bothvisit: | ||||
# p is implicitly in thisvisit. This means p is or should be | ||||
# in bothvisit | ||||
revsvisit.discard(p) | ||||
basesvisit.discard(p) | ||||
bothvisit.add(p) | ||||
else: | ||||
# visit later | ||||
thisvisit.add(p) | ||||
missing.reverse() | ||||
return missing | ||||