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

mercurial/dagop.py

@@ -20,11 +20,19 b' from . import ('
 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 b' def _genrevancestors(repo, revs, followf'
             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 b' def _genrevancestors(repo, revs, followf'
                     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):

mercurial/revset.py

@@ -238,23 +238,33 b' def ancestor(repo, subset, x):'
         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):

tests/test-revset.t

@@ -842,6 +842,20 b' ancestor can accept 0 or more arguments'
 
 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 b' test ancestors'
   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 b' optimization to only() works only if anc'
         ('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 b' optimization to only() works only if anc'
       ('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)