Mercurial > hg
view mercurial/ancestor.py @ 17976:09d5681d5b72
ancestor: fix a comment (followup to 0b03454abae7)
author | Siddharth Agarwal <sid0@fb.com> |
---|---|
date | Wed, 28 Nov 2012 10:35:12 -0800 |
parents | 0b03454abae7 |
children | b3ba69692f8a |
line wrap: on
line source
# ancestor.py - generic DAG ancestor algorithm for mercurial # # Copyright 2006 Matt Mackall <mpm@selenic.com> # # This software may be used and distributed according to the terms of the # GNU General Public License version 2 or any later version. import heapq from node import nullrev def ancestor(a, b, pfunc): """ 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. pfunc must return a list of parent vertices for a given vertex """ if a == b: return a a, b = sorted([a, b]) # find depth from root of all ancestors # depth is stored as a negative for heapq parentcache = {} visit = [a, b] depth = {} while visit: vertex = visit[-1] pl = pfunc(vertex) parentcache[vertex] = pl if not pl: depth[vertex] = 0 visit.pop() else: for p in pl: if p == a or p == b: # did we find a or b as a parent? return p # we're done if p not in depth: visit.append(p) if visit[-1] == vertex: # -(maximum distance of parents + 1) 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)] seen = set() while h: d, n = heapq.heappop(h) if n not in seen: seen.add(n) yield (d, n) for p in parentcache[n]: heapq.heappush(h, (depth[p], p)) def generations(vertex): sg, s = None, set() for g, v in ancestors(vertex): if g != sg: if sg: yield sg, s sg, s = g, set((v,)) else: s.add(v) 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: while True: 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 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: # not an ancestor of revs or bases: ignore 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