Mercurial > evolve
changeset 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)).
author | Pierre-Yves David <pierre-yves.david@fb.com> |
---|---|
date | Tue, 23 Jun 2015 00:00:03 -0700 |
parents | c868a69c29c5 |
children | 6db55f28c965 |
files | hgext/evolve.py |
diffstat | 1 files changed, 13 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- 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,