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

[Yuya Nishihara]

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().