[PATCH 3 of 4] revset: add helper to build balanced addsets from chained 'or' operations

[Pierre-Yves David]

On 05/26/2015 04:00 PM, Yuya Nishihara wrote:
> On Tue, 26 May 2015 10:59:27 -0700, Pierre-Yves David wrote:
>> 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
>
> It could, but "combinesets([]) -> baseset()" is somewhat useful in revrange().

I think we will need a generic "promote this object to a baseset in 
place because we have soaked all the lazyness out of it" anyway. (yes 
this wil be black magic…)

We can also easily turn addset into an factory function if we have 
smarter code.

My main objective here is to reduce the official API surface.

If is likely we'lll a C version of addset that does not needs the 
balanced tree approach, we may even get a Python version for it. Keeping 
all this "balanced tree" magic behuind the simple "addset(…)" API seems 
simpler here.

> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at selenic.com
> https://selenic.com/mailman/listinfo/mercurial-devel
>

-- 
Pierre-Yves David