Mercurial > hg
changeset 33002:272a44cac57e
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
| author | Yuya Nishihara <yuya@tcha.org> |
|---|---|
| date | Sun, 18 Jun 2017 00:22:41 +0900 |
| parents | 92d0945a15e0 |
| children | f63d111258da |
| files | mercurial/dagop.py mercurial/revset.py tests/test-revset.t |
| diffstat | 3 files changed, 101 insertions(+), 15 deletions(-) [+] |
line wrap: on
line diff
--- 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)