[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