Mercurial > public > mercurial-scm > hg-stable

diff mercurial/revset.py @ 33092:a53bfc2845f2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
line wrap: on
line diff
--- a/mercurial/revset.py	Sat Jun 24 23:35:03 2017 +0900
+++ b/mercurial/revset.py	Sat Jun 24 23:05:57 2017 +0900
@@ -595,23 +595,42 @@
     return subset.filter(lambda r: matcher(repo[r].description()),
                          condrepr=('<desc %r>', ds))
 
-def _descendants(repo, subset, x, followfirst=False):
+def _descendants(repo, subset, x, followfirst=False, startdepth=None,
+                 stopdepth=None):
     roots = getset(repo, fullreposet(repo), x)
     if not roots:
         return baseset()
-    s = dagop.revdescendants(repo, roots, followfirst)
+    s = dagop.revdescendants(repo, roots, followfirst, startdepth, stopdepth)
     return subset & s
 
-@predicate('descendants(set)', safe=True)
+@predicate('descendants(set[, depth])', safe=True)
 def descendants(repo, subset, x):
     """Changesets which are descendants 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, 'descendants', 'set')
+    # startdepth is for internal use only until we can decide the UI
+    args = getargsdict(x, 'descendants', 'set depth startdepth')
     if 'set' not in args:
         # i18n: "descendants" is a keyword
         raise error.ParseError(_('descendants takes at least 1 argument'))
-    return _descendants(repo, subset, args['set'])
+    startdepth = stopdepth = None
+    if 'startdepth' in args:
+        n = getinteger(args['startdepth'],
+                       "descendants expects an integer startdepth")
+        if n < 0:
+            raise error.ParseError("negative startdepth")
+        startdepth = n
+    if 'depth' in args:
+        # i18n: "descendants" is a keyword
+        n = getinteger(args['depth'], _("descendants expects an integer depth"))
+        if n < 0:
+            raise error.ParseError(_("negative depth"))
+        stopdepth = n + 1
+    return _descendants(repo, subset, args['set'],
+                        startdepth=startdepth, stopdepth=stopdepth)
 
 @predicate('_firstdescendants', safe=True)
 def _firstdescendants(repo, subset, x):