Mercurial > hg > mercurial-crew-with-dirclash
view mercurial/ancestor.py @ 5440:f9b0e4f023c4
findcopies: fix rename bug
We've fiddled with this line several times, and an old bug has
reappeared from it. Let's take a peek at the history.
The original "or" (rev 3674, in 0.9.2 and 0.9.3):
http://www.selenic.com/hg/rev/9103dab96093
Then I changed it to an "and" to fix a bug (rev 4304):
http://www.selenic.com/hg/rev/4787e2b0dd03
Then for reasons now lost in the mists of time, I dropped half (rev 4399):
http://www.selenic.com/hg/rev/93652499bed3
Then we added back the "or" (rev 4416, in 0.9.4):
http://www.selenic.com/hg/rev/bb1800a7d7e1
So it seems it ought to be "and".
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Mon, 08 Oct 2007 18:47:22 -0500 |
parents | eb0b4a2d70a9 |
children |
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, incorporated herein by reference. import heapq def ancestor(a, b, pfunc): """ return the least common ancestor of nodes a and b or None if there is no such ancestor. pfunc must return a list of parent vertices """ if a == b: return a # find depth from root of all ancestors visit = [a, b] depth = {} while visit: vertex = visit[-1] pl = pfunc(vertex) 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: 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 = {} while h: d, n = heapq.heappop(h) if n not in seen: seen[n] = 1 yield (d, n) for p in pfunc(n): heapq.heappush(h, (depth[p], p)) def generations(vertex): sg, s = None, {} for g, v in ancestors(vertex): if g != sg: if sg: yield sg, s sg, s = g, {v:1} else: s[v] = 1 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 1: 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