--- a/mercurial/copies.py Sat Mar 29 12:39:47 2008 -0500
+++ b/mercurial/copies.py Sat Mar 29 12:39:47 2008 -0500
@@ -7,7 +7,7 @@
from node import nullid, nullrev
from i18n import _
-import util, ancestor
+import util, heapq
def _nonoverlap(d1, d2, d3):
"Return list of elements in d1 not in d2 or d3"
@@ -53,6 +53,43 @@
old.sort()
return [o[1] for o in old]
+def _symmetricdifference(a, b, pfunc):
+ """find revisions that are ancestors of a or b, but not both"""
+ # basic idea:
+ # - mark a and b with different sides
+ # - if a parent's children are all on the same side, the parent is
+ # on that side, otherwise it is on no side
+ # - walk the graph in topological order with the help of a heap;
+ # - add unseen parents to side map
+ # - clear side of any parent that has children on different sides
+ # - track number of unvisited nodes that might still be on a side
+ # - quit when interesting nodes is zero
+ if a == b:
+ return [a]
+
+ side = {a: -1, b: 1}
+ visit = [-a, -b]
+ heapq.heapify(visit)
+ interesting = len(visit)
+
+ while interesting:
+ r = -heapq.heappop(visit)
+ if side[r]:
+ interesting -= 1
+ for p in pfunc(r):
+ if p not in side:
+ # first time we see p; add it to visit
+ side[p] = side[r]
+ if side[p]:
+ interesting += 1
+ heapq.heappush(visit, -p)
+ elif side[p] and side[p] != side[r]:
+ # p was interesting but now we know better
+ side[p] = 0
+ interesting -= 1
+
+ return [r for r in side if side[r]]
+
def copies(repo, c1, c2, ca, checkdirs=False):
"""
Find moves and copies between context c1 and c2
@@ -69,7 +106,7 @@
pr = repo.changelog.parentrevs
def parents(rev):
return [p for p in pr(rev) if p != nullrev]
- limit = min(ancestor.symmetricdifference(rev1, rev2, parents))
+ limit = min(_symmetricdifference(rev1, rev2, parents))
m1 = c1.manifest()
m2 = c2.manifest()
ma = ca.manifest()