Patchwork [3,of,4] revrange: build balanced tree of addsets from revisions (issue4565)

login
register
mail settings
Submitter Yuya Nishihara
Date June 1, 2015, 3:21 p.m.
Message ID <61d50109a9e85bcd4e23.1433172066@mimosa>
Download mbox | patch
Permalink /patch/9422/
State Accepted
Headers show

Comments

Yuya Nishihara - June 1, 2015, 3:21 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1432458693 -32400
#      Sun May 24 18:11:33 2015 +0900
# Node ID 61d50109a9e85bcd4e23954f2eebe6d513aa04e3
# Parent  da102f9b19e6bd1a6143e070cc5152c6d00ea4da
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 ?

Patch

diff --git a/mercurial/scmutil.py b/mercurial/scmutil.py
--- a/mercurial/scmutil.py
+++ b/mercurial/scmutil.py
@@ -709,7 +709,7 @@  def revrange(repo, revs):
             return defval
         return repo[val].rev()
 
-    l = revset.baseset([])
+    subsets = []
 
     revsetaliases = [alias for (alias, _) in
                      repo.ui.configitems("revsetalias")]
@@ -725,7 +725,7 @@  def revrange(repo, revs):
                 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 @@  def revrange(repo, revs):
                 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.
diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -1084,6 +1084,13 @@  test that chained `or` operations never 
   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