mercurial-scm/hg: mercurial/revlog.py comparison

Fix recursion depth trouble with ancestor algorithm

comparison

equal deleted inserted replaced

-:e825a68d7227
+:f2b2d5daec30
 self.cache = (node, n, text)
 return node
 def ancestor(self, a, b):
-def expand(e1, e2, a1, a2):
+def expand(list, map):
-ne = []
+a = []
-for n in e1:
+while list:
-(p1, p2) = self.parents(n)
+n = list.pop(0)
-if p1 in a2: return p1
+map[n] = 1
-if p2 in a2: return p2
+yield n
-if p1 != nullid and p1 not in a1:
+for p in self.parents(n):
-a1[p1] = 1
+if p != nullid and p not in map:
-ne.append(p1)
+list.append(p)
-if p2 != nullid and p2 not in a1:
+yield nullid
-a1[p2] = 1
-ne.append(p2)
+amap = {}
-return expand(e2, ne, a2, a1)
+bmap = {}
-return expand([a], [b], {a:1}, {b:1})
+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"""
 old = self.tip()
 i = self.count()

Mercurial > public > mercurial-scm > hg