ancestor.py
173 lines
| 5.5 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. | ||||
""" | ||||
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 | ||||