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,