# HG changeset patch # User Bryan O'Sullivan # Date 1338591022 25200 # Node ID b6efeb27e7338a3ac362af59b076f9518ff263c6 # Parent 76bcd3eac67e3b1628a463926b59809be4daa424 revset: introduce and use _revsbetween This is similar in spirit to revlog.nodesbetween, but less ambitious, much simpler, and ~2x faster. diff -r 76bcd3eac67e -r b6efeb27e733 mercurial/revset.py --- a/mercurial/revset.py Fri Jun 01 15:50:22 2012 -0700 +++ b/mercurial/revset.py Fri Jun 01 15:50:22 2012 -0700 @@ -47,6 +47,36 @@ yield i break +def _revsbetween(repo, roots, heads): + """Return all paths between roots and heads, inclusive of both endpoint + sets.""" + if not roots: + return [] + parentrevs = repo.changelog.parentrevs + visit = heads[:] + reachable = set() + seen = {} + minroot = min(roots) + roots = set(roots) + # open-code the post-order traversal due to the tiny size of + # sys.getrecursionlimit() + while visit: + rev = visit.pop() + if rev in roots: + reachable.add(rev) + parents = parentrevs(rev) + seen[rev] = parents + for parent in parents: + if parent >= minroot and parent not in seen: + visit.append(parent) + if not reachable: + return [] + for rev in sorted(seen): + for parent in seen[rev]: + if parent in reachable: + reachable.add(rev) + return sorted(reachable) + elements = { "(": (20, ("group", 1, ")"), ("func", 1, ")")), "~": (18, None, ("ancestor", 18)), @@ -194,10 +224,7 @@ def dagrange(repo, subset, x, y): if subset: r = range(len(repo)) - m = getset(repo, r, x) - n = getset(repo, r, y) - cl = repo.changelog - xs = map(cl.rev, cl.nodesbetween(map(cl.node, m), map(cl.node, n))[0]) + xs = _revsbetween(repo, getset(repo, r, x), getset(repo, r, y)) s = set(subset) return [r for r in xs if r in s] return []