Patchwork [2,of,6,V5] revset: rename revsbetween to reachableroots and add an argument

mail settings
Submitter Pierre-Yves David
Date Aug. 7, 2015, 9:06 p.m.
Message ID <>
Download mbox | patch
Permalink /patch/10153/
State Accepted
Headers show


Pierre-Yves David - Aug. 7, 2015, 9:06 p.m.
# HG changeset patch
# User Laurent Charignon <>
# Date 1434770334 25200
#      Fri Jun 19 20:18:54 2015 -0700
# Node ID 5f55544d6c5187bbf31ab4cc851f094867421430
# Parent  a82e03945c19bd8796b68d1f36faec73642b6e9f
revset: rename revsbetween to reachableroots and add an argument

This patch is part of a series of patches to speed up the computation of
revset.revsbetween by introducing a C implementation. The main motivation is to
speed up smartlog on big repositories. At the end of the series, on our big
repositories the computation of revsbetween is 10-50x faster and smartlog on is
2x-5x faster.

This patch rename 'revsbetween' to 'reachableroots' and makes the computation of
the full path optional. This will allow graphlog to compute grandparents using
'reachableroots' and remove the need for a dedicated grandparent function.


diff --git a/mercurial/ b/mercurial/
--- a/mercurial/
+++ b/mercurial/
@@ -76,13 +76,14 @@  def _revdescendants(repo, revs, followfi
                         yield i
     return generatorset(iterate(), iterasc=True)
-def revsbetween(repo, roots, heads):
-    """Return all paths between roots and heads, inclusive of both endpoint
-    sets."""
+def reachableroots(repo, roots, heads, includepath=False):
+    """return (heads(::<roots> and ::<heads>))
+    If includepath is True, return (<roots>::<heads>)."""
     if not roots:
         return baseset()
     parentrevs = repo.changelog.parentrevs
     visit = list(heads)
     reachable = set()
@@ -99,17 +100,21 @@  def revsbetween(repo, roots, heads):
     # sys.getrecursionlimit()
     while visit:
         rev = nextvisit()
         if rev in roots:
+            if not includepath:
+                continue
         parents = parentrevs(rev)
         seen[rev] = parents
         for parent in parents:
             if parent >= minroot and parent not in seen:
     if not reachable:
         return baseset()
+    if not includepath:
+        return reachable
     for rev in sorted(seen):
         for parent in seen[rev]:
             if parent in reachable:
     return baseset(sorted(reachable))
@@ -395,11 +400,12 @@  def rangeset(repo, subset, x, y):
     # would be more efficient.
     return r & subset
 def dagrange(repo, subset, x, y):
     r = fullreposet(repo)
-    xs = revsbetween(repo, getset(repo, r, x), getset(repo, r, y))
+    xs = reachableroots(repo, getset(repo, r, x), getset(repo, r, y),
+                         includepath=True)
     # XXX We should combine with subset first: 'subset & baseset(...)'. This is
     # necessary to ensure we preserve the order in subset.
     return xs & subset
 def andset(repo, subset, x, y):