[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