### changeset 45:f2b2d5daec30

Fix recursion depth trouble with ancestor algorithm
author mpm@selenic.com Tue, 10 May 2005 00:34:57 -0800 e825a68d7227 93e868fa0db8 mercurial/revlog.py 1 files changed, 32 insertions(+), 14 deletions(-) [+]
line wrap: on
line diff
```--- 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:
+                an = ag.next()
+                if an == nullid: