# HG changeset patch
# User mpm@selenic.com
# Date 1115714097 28800
# Node ID f2b2d5daec30981e6757a6e4c5a4ac497ae0bc10
# Parent  e825a68d72272076fae6a12990d8feaf50fc0d61
Fix recursion depth trouble with ancestor algorithm



diff -r e825a68d7227 -r f2b2d5daec30 mercurial/revlog.py
--- 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"""