# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 1299534283 21600
# Node ID 7ab85fec60c33207d402a6b762725e21829fc870
# Parent  bbfae32f178ee8614f51d86d5f683fab77e059f6
ancestor: rewrite to deal with crossed linkrevs (issue2682)

This version is about 10% slower, possibly because it visits some
revisions in a different topological order than what's in the revlog.

diff -r bbfae32f178e -r 7ab85fec60c3 mercurial/context.py
--- a/mercurial/context.py	Sun Mar 06 11:30:57 2011 +0100
+++ b/mercurial/context.py	Mon Mar 07 15:44:43 2011 -0600
@@ -466,39 +466,40 @@
         else:
             base = self
 
-        # find all ancestors
+        # This algorithm would prefer to be recursive, but Python is a
+        # bit recursion-hostile. Instead we do an iterative
+        # depth-first search.
+
+        visit = [base]
+        hist = {}
+        pcache = {}
         needed = {base: 1}
-        visit = [base]
-        files = [base._path]
         while visit:
-            f = visit.pop(0)
-            for p in parents(f):
-                if p not in needed:
-                    needed[p] = 1
-                    visit.append(p)
-                    if p._path not in files:
-                        files.append(p._path)
-                else:
-                    # count how many times we'll use this
-                    needed[p] += 1
+            f = visit[-1]
+            if f not in pcache:
+                pcache[f] = parents(f)
 
-        # sort by revision (per file) which is a topological order
-        visit = []
-        for f in files:
-            visit.extend(n for n in needed if n._path == f)
+            ready = True
+            pl = pcache[f]
+            for p in pl:
+                if p not in hist:
+                    ready = False
+                    visit.append(p)
+                    needed[p] = needed.get(p, 0) + 1
+            if ready:
+                visit.pop()
+                curr = decorate(f.data(), f)
+                for p in pl:
+                    curr = pair(hist[p], curr)
+                    if needed[p] == 1:
+                        del hist[p]
+                    else:
+                        needed[p] -= 1
 
-        hist = {}
-        for f in sorted(visit, key=lambda x: x.rev()):
-            curr = decorate(f.data(), f)
-            for p in parents(f):
-                curr = pair(hist[p], curr)
-                # trim the history of unneeded revs
-                needed[p] -= 1
-                if not needed[p]:
-                    del hist[p]
-            hist[f] = curr
+                hist[f] = curr
+                pcache[f] = []
 
-        return zip(hist[f][0], hist[f][1].splitlines(True))
+        return zip(hist[base][0], hist[base][1].splitlines(True))
 
     def ancestor(self, fc2, actx=None):
         """