# HG changeset patch
# User Pierre-Yves David <pierre-yves.david@fb.com>
# Date 1435042803 25200
# Node ID ecd669c36c12134c558fae21a79b484daab2e5ab
# Parent  c868a69c29c50e9e7313a5d94f4cc3378a159316
evolve: non recursive implementation for _aspiringdescendants

We switch from a N squared recursive implementation for _aspiringdescendants
to a more efficient algorithm in O(len(unstable)).

diff -r c868a69c29c5 -r ecd669c36c12 hgext/evolve.py
--- a/hgext/evolve.py	Mon Jun 22 21:01:30 2015 -0700
+++ b/hgext/evolve.py	Tue Jun 23 00:00:03 2015 -0700
@@ -1632,10 +1632,19 @@
     one of its descendants recursively. Empty list if none can be found."""
     target = set(revs)
     result = set(target)
-    sizeresult = 0
-    while sizeresult != len(result):
-        sizeresult = len(result)
-        result.update(_aspiringchildren(repo, result))
+    paths = collections.defaultdict(set)
+    for r in repo.revs('unstable() - %ld', revs):
+        for d in _possibledestination(repo, r):
+            paths[d].add(r)
+
+    result = set(target)
+    tovisit = list(revs)
+    while tovisit:
+        base = tovisit.pop()
+        for unstable in paths[base]:
+            if unstable not in result:
+                tovisit.append(unstable)
+                result.add(unstable)
     return sorted(result - target)
 
 def _solveunstable(ui, repo, orig, dryrun=False, confirm=False,