revset: add depth limit to ancestors()
This is proposed by the issue5374, and will be a building block of set{gen}
(set subscript) operator.
https://www.mercurial-scm.org/wiki/RevsetOperatorPlan#ideas_from_mpm
# reverse(ancestors(tip)) using hg repo
2) 0.075408
3) 0.075951
--- a/mercurial/dagop.py Sun Jun 18 00:11:48 2017 +0900
+++ b/mercurial/dagop.py Sun Jun 18 00:22:41 2017 +0900
@@ -20,11 +20,19 @@
baseset = smartset.baseset
generatorset = smartset.generatorset
-def _genrevancestors(repo, revs, followfirst):
+# possible maximum depth between null and wdir()
+_maxlogdepth = 0x80000000
+
+def _genrevancestors(repo, revs, followfirst, stopdepth):
if followfirst:
cut = 1
else:
cut = None
+ if stopdepth is None:
+ stopdepth = _maxlogdepth
+ if stopdepth <= 0:
+ return
+
cl = repo.changelog
# load input revs lazily to heap so earlier revisions can be yielded
@@ -45,10 +53,12 @@
inputrev = next(irevs, None)
if inputrev is not None:
heapq.heappush(pendingheap, (-inputrev, 0))
- if currev != lastrev:
+ foundnew = (currev != lastrev)
+ if foundnew:
lastrev = currev
yield currev
- pdepth = curdepth + 1
+ pdepth = curdepth + 1
+ if foundnew and pdepth < stopdepth:
try:
for prev in cl.parentrevs(currev)[:cut]:
if prev != node.nullrev:
@@ -58,9 +68,13 @@
if pctx.rev() != node.nullrev:
heapq.heappush(pendingheap, (-pctx.rev(), pdepth))
-def revancestors(repo, revs, followfirst):
- """Like revlog.ancestors(), but supports followfirst."""
- gen = _genrevancestors(repo, revs, followfirst)
+def revancestors(repo, revs, followfirst, stopdepth=None):
+ """Like revlog.ancestors(), but supports additional options, includes
+ the given revs themselves, and returns a smartset
+
+ Scan ends at the stopdepth (exlusive) if specified.
+ """
+ gen = _genrevancestors(repo, revs, followfirst, stopdepth)
return generatorset(gen, iterasc=False)
def revdescendants(repo, revs, followfirst):
--- a/mercurial/revset.py Sun Jun 18 00:11:48 2017 +0900
+++ b/mercurial/revset.py Sun Jun 18 00:22:41 2017 +0900
@@ -238,23 +238,33 @@
return baseset([anc.rev()])
return baseset()
-def _ancestors(repo, subset, x, followfirst=False):
+def _ancestors(repo, subset, x, followfirst=False, stopdepth=None):
heads = getset(repo, fullreposet(repo), x)
if not heads:
return baseset()
- s = dagop.revancestors(repo, heads, followfirst)
+ s = dagop.revancestors(repo, heads, followfirst, stopdepth)
return subset & s
-@predicate('ancestors(set)', safe=True)
+@predicate('ancestors(set[, depth])', safe=True)
def ancestors(repo, subset, x):
"""Changesets that are ancestors of changesets in set, including the
given changesets themselves.
+
+ If depth is specified, the result only includes changesets up to
+ the specified generation.
"""
- args = getargsdict(x, 'ancestors', 'set')
+ args = getargsdict(x, 'ancestors', 'set depth')
if 'set' not in args:
# i18n: "ancestors" is a keyword
raise error.ParseError(_('ancestors takes at least 1 argument'))
- return _ancestors(repo, subset, args['set'])
+ stopdepth = None
+ if 'depth' in args:
+ # i18n: "ancestors" is a keyword
+ n = getinteger(args['depth'], _("ancestors expects an integer depth"))
+ if n < 0:
+ raise error.ParseError(_("negative depth"))
+ stopdepth = n + 1
+ return _ancestors(repo, subset, args['set'], stopdepth=stopdepth)
@predicate('_firstancestors', safe=True)
def _firstancestors(repo, subset, x):
--- a/tests/test-revset.t Sun Jun 18 00:11:48 2017 +0900
+++ b/tests/test-revset.t Sun Jun 18 00:22:41 2017 +0900
@@ -842,6 +842,20 @@
test ancestors
+ $ hg log -G -T '{rev}\n' --config experimental.graphshorten=True
+ @ 9
+ o 8
+ | o 7
+ | o 6
+ |/|
+ | o 5
+ o | 4
+ | o 3
+ o | 2
+ |/
+ o 1
+ o 0
+
$ log 'ancestors(5)'
0
1
@@ -855,6 +869,51 @@
2
3
+test ancestors with depth limit
+
+ (depth=0 selects the node itself)
+
+ $ log 'reverse(ancestors(9, depth=0))'
+ 9
+
+ (interleaved: '4' would be missing if heap queue were higher depth first)
+
+ $ log 'reverse(ancestors(8:9, depth=1))'
+ 9
+ 8
+ 4
+
+ (interleaved: '2' would be missing if heap queue were higher depth first)
+
+ $ log 'reverse(ancestors(7+8, depth=2))'
+ 8
+ 7
+ 6
+ 5
+ 4
+ 2
+
+ (walk example above by separate queries)
+
+ $ log 'reverse(ancestors(8, depth=2)) + reverse(ancestors(7, depth=2))'
+ 8
+ 4
+ 2
+ 7
+ 6
+ 5
+
+test bad arguments passed to ancestors()
+
+ $ log 'ancestors(., depth=-1)'
+ hg: parse error: negative depth
+ [255]
+ $ log 'ancestors(., depth=foo)'
+ hg: parse error: ancestors expects an integer depth
+ [255]
+
+test author
+
$ log 'author(bob)'
2
$ log 'author("re:bob|test")'
@@ -2996,8 +3055,11 @@
('symbol', '1'))
any)
define)
- hg: parse error: ancestors takes at most 1 positional arguments
- [255]
+ 0
+ 1
+ 3
+ 5
+ 6
$ hg debugrevspec -p optimized 'ancestors(6, 1) - ancestors(4)'
* optimized:
(difference
@@ -3012,8 +3074,8 @@
('symbol', '4')
any)
define)
- hg: parse error: ancestors takes at most 1 positional arguments
- [255]
+ 5
+ 6
optimization disabled if keyword arguments passed (because we're too lazy
to support it)