[PATCH 3 of 4] revset: add helper to build balanced addsets from chained 'or' operations
Pierre-Yves David
pierre-yves.david at ens-lyon.org
Tue May 26 12:59:27 CDT 2015
On 05/26/2015 08:00 AM, Yuya Nishihara wrote:
> # HG changeset patch
> # User Yuya Nishihara <yuya at tcha.org>
> # Date 1432444252 -32400
> # Sun May 24 14:10:52 2015 +0900
> # Node ID f8cd0e0ceea631cb6d22b324bfeeb7fecee426fb
> # Parent 70591283d99dcc442f0e7bdb9afa603eb18bfac1
> revset: add helper to build balanced addsets from chained 'or' operations
>
> This function will be used to reduce the stack depth from O(n) to O(log(n)).
> It is public function because we'll use it later to fix stack overflow at
> scmutil.revrange().
>
> diff --git a/mercurial/revset.py b/mercurial/revset.py
> --- a/mercurial/revset.py
> +++ b/mercurial/revset.py
> @@ -2940,6 +2940,17 @@ class filteredset(abstractsmartset):
> def __repr__(self):
> return '<%s %r>' % (type(self).__name__, self._subset)
>
> +def combinesets(subsets):
> + """Create balanced tree of addsets representing union of given sets"""
> + if not subsets:
> + return baseset()
> + if len(subsets) == 1:
> + return subsets[0]
> + p = len(subsets) // 2
> + xs = combinesets(subsets[:p])
> + ys = combinesets(subsets[p:])
> + return addset(xs, ys)
> +
My idea for this was to include that directly into the addset
constructor. The main motivation for it is to keep a single interface
for adding stuff.
class addset(…):
def __init__(self, *subsets, ascending=None): #has to be **kwargs
assert 1< len(subsets)
if 2 < len(subsets):
p = len(subsets) // 2
revs1 = addset(*subsets[:p])
revs2 = subsets[p:]
if len(revs2) == 1:
revs2 = revs2[0]
else:
revs2 = addset(revs2)
self._r1 = revs1
self._r2 = revs2
--
Pierre-Yves David
More information about the Mercurial-devel
mailing list