[PATCH 1 of 7] revset: introduce a _revinterval type and revsubset function
Bryan O'Sullivan
bos at serpentine.com
Mon Jun 4 17:25:07 CDT 2012
# HG changeset patch
# User Bryan O'Sullivan <bryano at fb.com>
# Date 1338848634 25200
# Node ID 4f118bc8e20a571cf283695269a625d013f19eb4
# Parent 3b266a181a5826e3c4b19bab142d1b208bafa7cc
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
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