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

[Yuya Nishihara]

# 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)
+
 def _iterordered(ascending, iter1, iter2):
     """produce an ordered iteration from two iterators with the same order