changeset 25385:a26a55406c0a

revrange: build balanced tree of addsets from revisions (issue4565)

This reduces the stack depth from O(n) to O(log(n)). Therefore, repeated
-rREV options will never exceed the Python stack limit.

Currently it depends on private revset._combinesets() function. But at some
point, we'll be able to drop the old-style parser, and revrange() can be
completely rewritten without using _combinesets():

  trees = [parse(s) for s in revs]
  optimize(('or',) + trees)  # combine trees and optimize at once
  ...

Blockers that prevent eliminating old-style parser:

 - nullary ":" operator
 - revrange(repo, [intrev, ...]), can be mapped to 'rev(%d)' ?
 - revrange(repo, [binnode, ...]), should be banned ?

--- a/mercurial/scmutil.py	Sun May 24 17:59:55 2015 +0900
+++ b/mercurial/scmutil.py	Sun May 24 18:11:33 2015 +0900
@@ -709,7 +709,7 @@
             return defval
         return repo[val].rev()
 
-    l = revset.baseset([])
+    subsets = []
 
     revsetaliases = [alias for (alias, _) in
                      repo.ui.configitems("revsetalias")]
@@ -725,7 +725,7 @@
                 raise error.RepoLookupError
 
             if isinstance(spec, int):
-                l = l + revset.baseset([spec])
+                subsets.append(revset.baseset([spec]))
                 continue
 
             if _revrangesep in spec:
@@ -738,27 +738,21 @@
                 if end == nullrev and start < 0:
                     start = nullrev
                 rangeiter = repo.changelog.revs(start, end)
-                if not l:
-                    # by far the most common case: revs = ["-1:0"]
-                    l = revset.baseset(rangeiter)
-                    continue
-                l = l + revset.baseset(rangeiter)
+                l = revset.baseset(rangeiter)
+                subsets.append(l)
                 continue
             elif spec and spec in repo: # single unquoted rev
                 rev = revfix(repo, spec, None)
-                l = l + revset.baseset([rev])
+                subsets.append(revset.baseset([rev]))
                 continue
         except error.RepoLookupError:
             pass
 
         # fall through to new-style queries if old-style fails
         m = revset.match(repo.ui, spec, repo)
-        if l:
-            l = l + m(repo)
-        else:
-            l = m(repo)
+        subsets.append(m(repo))
 
-    return l
+    return revset._combinesets(subsets)
 
 def expandpats(pats):
     '''Expand bare globs when running on windows.

--- a/tests/test-revset.t	Sun May 24 17:59:55 2015 +0900
+++ b/tests/test-revset.t	Sun May 24 18:11:33 2015 +0900
@@ -1084,6 +1084,13 @@
   0
   1
 
+test that repeated `-r` options never eat up stack (issue4565)
+(uses `-r 0::1` to avoid possible optimization at old-style parser)
+
+  $ hg log -T '{rev}\n' `python -c "for i in xrange(500): print '-r 0::1 ',"`
+  0
+  1
+
 check that conversion to only works
   $ try --optimize '::3 - ::1'
   (minus