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