[PATCH 07 of 13] revset: introduce a _revinterval type and revsubset function

Bryan O'Sullivan bos at serpentine.com
Fri Jun 1 17:52:05 CDT 2012


# HG changeset patch
# User Bryan O'Sullivan <bryano at fb.com>
# Date 1338591022 25200
# Node ID 4b56ee070f13b26662ed848ed1c4cfaa6f4bf904
# Parent  63833bb69bcaf02fec27610e8b3e11f56ae64031
revset: introduce a _revinterval type and revsubset function

Very often, the set against which an intermediate revset is filtered
is a contiguous sequence of revision numbers.  A _revinterval is
far cheaper for this purpose than a set or list, as the amount of
data to allocate is small and constant.

If a _revinterval is not appropriate, revsubset falls back to a
set.  It also avoids duplication of an existing set if possible.

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -13,6 +13,77 @@ import match as matchmod
 from i18n import _
 import encoding
 
+class _revinterval(object):
+    """Half-closed revision interval: [start, stop)"""
+    # can't use xrange instead, as it doesn't support slicing or cheap
+    # __contains__ when reversed
+
+    def __init__(self, what=None, start=None, stop=None, reverse=False):
+        if what is None:
+            self._start, self._stop, self._reversed = start, stop, reverse
+            return
+        try:
+            if isinstance(what, xrange):
+                a, b = what[0], what[-1]
+                self._start, self._stop = sorted((a, b))
+                self._reversed = a > b
+            else:
+                # avoid localrepository.__getitem__
+                self._start = iter(what).next()
+                self._stop = self._start + len(what)
+                self._reversed = False
+        except (IndexError, StopIteration):
+            self._start, self._stop, self._reversed = 0, 0, False
+
+    def __contains__(self, rev):
+        return rev >= self._start and rev < self._stop
+
+    def __len__(self):
+        return self._stop - self._start
+
+    def reverse(self):
+        self._reversed = not self._reversed
+
+    def _iter(self, reverse):
+        if reverse:
+            return iter(xrange(self._stop - 1, self._start - 1, -1))
+        return iter(xrange(self._start, self._stop))
+
+    def __iter__(self):
+        return self._iter(self._reversed)
+
+    def __reversed__(self):
+        return self._iter(not self._reversed)
+
+    def __getitem__(self, i):
+        l = len(self)
+        if isinstance(i, slice):
+            start, stop, step = i.indices(l)
+            if abs(step) != 1:
+                raise ValueError('non-unit step not supported')
+            if self._reversed:
+                start, stop = self._stop - stop, self._stop - start
+            else:
+                start += self._start
+                stop += self._start
+            return _revinterval(start=start, stop=stop, reverse=step < 0)
+        if i < 0:
+            i += l
+        if 0 <= i <= l:
+            if self._reversed:
+                return self._stop - i - 1
+            return self._start + i
+        raise IndexError('interval index out of range')
+
+def revsubset(subset):
+    """Convert to a type that supports fast membership checking"""
+    if isinstance(subset, (set, _revinterval)):
+        return subset
+    if isinstance(subset, list):
+        # can't be assumed to be contiguous
+        return set(subset)
+    return _revinterval(subset)
+
 def _revancestors(repo, revs, followfirst):
     """Like revlog.ancestors(), but supports followfirst."""
     cut = followfirst and 1 or None
@@ -58,23 +129,25 @@ def _revsbetween(repo, roots, heads):
     seen = {}
     minroot = min(roots)
     roots = set(roots)
+    addvisit = visit.append
+    addreachable = reachable.add
     # 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)
+            addreachable(rev)
         parents = parentrevs(rev)
         seen[rev] = parents
         for parent in parents:
             if parent >= minroot and parent not in seen:
-                visit.append(parent)
+                addvisit(parent)
     if not reachable:
         return []
     for rev in sorted(seen):
         for parent in seen[rev]:
             if parent in reachable:
-                reachable.add(rev)
+                addreachable(rev)
     return sorted(reachable)
 
 elements = {
diff --git a/mercurial/scmutil.py b/mercurial/scmutil.py
--- a/mercurial/scmutil.py
+++ b/mercurial/scmutil.py
@@ -586,7 +586,7 @@ def revrange(repo, revs):
 
         # fall through to new-style queries if old-style fails
         m = revset.match(repo.ui, spec)
-        for r in m(repo, range(len(repo))):
+        for r in m(repo, revset.revsubset(repo)):
             if r not in seen:
                 l.append(r)
         seen.update(l)


More information about the Mercurial-devel mailing list