Mercurial > hg
comparison mercurial/revset.py @ 33080:a53bfc2845f2
revset: add depth limit to descendants() (issue5374)
This is naive implementation using two-pass scanning. Tracking descendants
isn't an easy problem if both start and stop depths are specified. It's
impractical to remember all possible depths of each node while scanning from
roots to descendants because the number of depths explodes. Instead, we could
cache (min, max) depths as a good approximation and track ancestors back when
needed, but that's likely to have off-by-one bug.
Since this implementation appears not significantly slower, and is quite
straightforward, I think it's good enough for practical use cases. The time
and space complexity is O(n) ish.
revisions:
0) 1-pass scanning with (min, max)-depth cache (worst-case quadratic)
1) 2-pass scanning (this version)
repository:
mozilla-central
# descendants(0) (for reference)
*) 0.430353
# descendants(0, depth=1000)
0) 0.264889
1) 0.398289
# descendants(limit(tip:0, 1, offset=10000), depth=1000)
0) 0.025478
1) 0.029099
# descendants(0, depth=2000, startdepth=1000)
0) painfully slow (due to quadratic backtracking of ancestors)
1) 1.531138
author | Yuya Nishihara <yuya@tcha.org> |
---|---|
date | Sat, 24 Jun 2017 23:05:57 +0900 |
parents | d83b189aef83 |
children | 4672db164c98 |
comparison
equal
deleted
inserted
replaced
33079:550c390cd9b2 | 33080:a53bfc2845f2 |
---|---|
593 kind, pattern, matcher = _substringmatcher(ds, casesensitive=False) | 593 kind, pattern, matcher = _substringmatcher(ds, casesensitive=False) |
594 | 594 |
595 return subset.filter(lambda r: matcher(repo[r].description()), | 595 return subset.filter(lambda r: matcher(repo[r].description()), |
596 condrepr=('<desc %r>', ds)) | 596 condrepr=('<desc %r>', ds)) |
597 | 597 |
598 def _descendants(repo, subset, x, followfirst=False): | 598 def _descendants(repo, subset, x, followfirst=False, startdepth=None, |
599 stopdepth=None): | |
599 roots = getset(repo, fullreposet(repo), x) | 600 roots = getset(repo, fullreposet(repo), x) |
600 if not roots: | 601 if not roots: |
601 return baseset() | 602 return baseset() |
602 s = dagop.revdescendants(repo, roots, followfirst) | 603 s = dagop.revdescendants(repo, roots, followfirst, startdepth, stopdepth) |
603 return subset & s | 604 return subset & s |
604 | 605 |
605 @predicate('descendants(set)', safe=True) | 606 @predicate('descendants(set[, depth])', safe=True) |
606 def descendants(repo, subset, x): | 607 def descendants(repo, subset, x): |
607 """Changesets which are descendants of changesets in set, including the | 608 """Changesets which are descendants of changesets in set, including the |
608 given changesets themselves. | 609 given changesets themselves. |
609 """ | 610 |
610 args = getargsdict(x, 'descendants', 'set') | 611 If depth is specified, the result only includes changesets up to |
612 the specified generation. | |
613 """ | |
614 # startdepth is for internal use only until we can decide the UI | |
615 args = getargsdict(x, 'descendants', 'set depth startdepth') | |
611 if 'set' not in args: | 616 if 'set' not in args: |
612 # i18n: "descendants" is a keyword | 617 # i18n: "descendants" is a keyword |
613 raise error.ParseError(_('descendants takes at least 1 argument')) | 618 raise error.ParseError(_('descendants takes at least 1 argument')) |
614 return _descendants(repo, subset, args['set']) | 619 startdepth = stopdepth = None |
620 if 'startdepth' in args: | |
621 n = getinteger(args['startdepth'], | |
622 "descendants expects an integer startdepth") | |
623 if n < 0: | |
624 raise error.ParseError("negative startdepth") | |
625 startdepth = n | |
626 if 'depth' in args: | |
627 # i18n: "descendants" is a keyword | |
628 n = getinteger(args['depth'], _("descendants expects an integer depth")) | |
629 if n < 0: | |
630 raise error.ParseError(_("negative depth")) | |
631 stopdepth = n + 1 | |
632 return _descendants(repo, subset, args['set'], | |
633 startdepth=startdepth, stopdepth=stopdepth) | |
615 | 634 |
616 @predicate('_firstdescendants', safe=True) | 635 @predicate('_firstdescendants', safe=True) |
617 def _firstdescendants(repo, subset, x): | 636 def _firstdescendants(repo, subset, x): |
618 # ``_firstdescendants(set)`` | 637 # ``_firstdescendants(set)`` |
619 # Like ``descendants(set)`` but follows only the first parents. | 638 # Like ``descendants(set)`` but follows only the first parents. |