comparison mercurial/dagop.py @ 42446:055c3e2c44f0

revlog: speed up isancestor

Currently, it is implemented on top of commonancestorsheads.
Implement it on top of reachableroots instead, as reachableroots could
stop walking the graph much sooner than commonancestorsheads.

Measuring repo.changelog.isancestorrev on two revisions in a private repository:
before: ! wall 0.005175 comb 0.010000 user 0.010000 sys 0.000000 (best of 550)
after : ! wall 0.000072 comb 0.000000 user 0.000000 sys 0.000000 (best of 36199)

When hg does this kind of operations 1500 times in pull ->
bookmarks.comparebookmarks -> bookmarks.validdest, that's 11s that
drop from the --profile output.

Differential Revision: https://phab.mercurial-scm.org/D6506

42445:3e42fc243741

            if prev != nullrev and prev in seen:
                seen.add(rev)
                yield rev
                break

def _reachablerootspure(repo, minroot, roots, heads, includepath):
    """See reachableroots"""
    if not roots:
        return []
    parentrevs = repo.changelog.parentrevs
    roots = set(roots)
    visit = list(heads)
    reachable = set()
    seen = {}
    # prefetch all the things! (because python is slow)

        rev = nextvisit()
        if rev in roots:
            reached(rev)
            if not includepath:
                continue
        parents = parentrevs(rev)
        seen[rev] = parents
        for parent in parents:
            if parent >= minroot and parent not in seen:
                dovisit(parent)
    if not reachable:

            if parent in reachable:
                reached(rev)
    return reachable

def reachableroots(repo, roots, heads, includepath=False):
    """return (heads(::<roots> and <roots>::<heads>))

    If includepath is True, return (<roots>::<heads>)."""
    if not roots:
        return baseset()
    minroot = roots.min()
    roots = list(roots)
    heads = list(heads)
    try:
        revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
    except AttributeError:
        revs = _reachablerootspure(repo, minroot, roots, heads, includepath)
    revs = baseset(revs)
    revs.sort()
    return revs

def _changesrange(fctx1, fctx2, linerange2, diffopts):

42446:055c3e2c44f0

            if prev != nullrev and prev in seen:
                seen.add(rev)
                yield rev
                break

def _reachablerootspure(pfunc, minroot, roots, heads, includepath):
    """See revlog.reachableroots"""
    if not roots:
        return []
    roots = set(roots)
    visit = list(heads)
    reachable = set()
    seen = {}
    # prefetch all the things! (because python is slow)

        rev = nextvisit()
        if rev in roots:
            reached(rev)
            if not includepath:
                continue
        parents = pfunc(rev)
        seen[rev] = parents
        for parent in parents:
            if parent >= minroot and parent not in seen:
                dovisit(parent)
    if not reachable:

            if parent in reachable:
                reached(rev)
    return reachable

def reachableroots(repo, roots, heads, includepath=False):
    """See revlog.reachableroots"""
    if not roots:
        return baseset()
    minroot = roots.min()
    roots = list(roots)
    heads = list(heads)
    revs = repo.changelog.reachableroots(minroot, heads, roots, includepath)
    revs = baseset(revs)
    revs.sort()
    return revs

def _changesrange(fctx1, fctx2, linerange2, diffopts):