[PATCH 07 of 13] revset: introduce a _revinterval type and revsubset function
Bryan O'Sullivan
bos at serpentine.com
Fri Jun 1 22:52:05 UTC 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