--- a/mercurial/revlog.py Tue May 10 00:33:48 2005 -0800
+++ b/mercurial/revlog.py Tue May 10 00:34:57 2005 -0800
@@ -170,20 +170,38 @@
return node
def ancestor(self, a, b):
- def expand(e1, e2, a1, a2):
- ne = []
- for n in e1:
- (p1, p2) = self.parents(n)
- if p1 in a2: return p1
- if p2 in a2: return p2
- if p1 != nullid and p1 not in a1:
- a1[p1] = 1
- ne.append(p1)
- if p2 != nullid and p2 not in a1:
- a1[p2] = 1
- ne.append(p2)
- return expand(e2, ne, a2, a1)
- return expand([a], [b], {a:1}, {b:1})
+ def expand(list, map):
+ a = []
+ while list:
+ n = list.pop(0)
+ map[n] = 1
+ yield n
+ for p in self.parents(n):
+ if p != nullid and p not in map:
+ list.append(p)
+ yield nullid
+
+ amap = {}
+ bmap = {}
+ ag = expand([a], amap)
+ bg = expand([b], bmap)
+ adone = bdone = 0
+
+ while not adone or not bdone:
+ if not adone:
+ an = ag.next()
+ if an == nullid:
+ adone = 1
+ elif an in bmap:
+ return an
+ if not bdone:
+ bn = bg.next()
+ if bn == nullid:
+ bdone = 1
+ elif bn in amap:
+ return bn
+
+ return nullid
def mergedag(self, other, transaction, linkseq, accumulate = None):
"""combine the nodes from other's DAG into ours"""