[PATCH 05 of 13] revset: introduce and use _revsbetween
Bryan O'Sullivan
bos at serpentine.com
Fri Jun 1 17:52:03 CDT 2012
# HG changeset patch
# User Bryan O'Sullivan <bryano at fb.com>
# Date 1338591022 25200
# Node ID 97c0bc8104500242fed39983d1f24b10131be1ee
# Parent 7cc07c4cc88f377cee98668f4d077c357f9b9499
revset: introduce and use _revsbetween
This is similar in spirit to revlog.nodesbetween, but less ambitious,
much simpler, and ~2x faster.
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -47,6 +47,36 @@ def _revdescendants(repo, revs, followfi
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 rangeset(repo, subset, x, y):
def dagrangenew(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 []
More information about the Mercurial-devel
mailing list