diff hgext/evolve.py @ 1423:ecd669c36c12

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)).

--- 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,