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

1422:c868a69c29c5

def _aspiringdescendant(repo, revs):
    """Return a list of changectx which can be stabilized on top of pctx or
    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))
    return sorted(result - target)

def _solveunstable(ui, repo, orig, dryrun=False, confirm=False,
                   progresscb=None):
    """Stabilize a unstable changeset"""

1423:ecd669c36c12

def _aspiringdescendant(repo, revs):
    """Return a list of changectx which can be stabilized on top of pctx or
    one of its descendants recursively. Empty list if none can be found."""
    target = set(revs)
    result = set(target)
    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,
                   progresscb=None):
    """Stabilize a unstable changeset"""