revset: add startdepth limit to ancestors() as internal option

revset: add startdepth limit to ancestors() as internal option

This is necessary to implement the set{gen} (set subscript) operator. For
example, set{-n} will be translated to ancestors(set, depth=n, startdepth=n).

https://www.mercurial-scm.org/wiki/RevsetOperatorPlan#ideas_from_mpm

The UI is undecided and I doubt if the startdepth option would be actually
useful, so the option is hidden for now. 'depth' could be extended to take
min:max range, in which case, integer depth should select a single generation.

  ancestors(set, depth=:y)  # scan up to y-th generation
  ancestors(set, depth=x:)  # skip until (x-1)-th generation
  ancestors(set, depth=x)   # select only x-th generation

Any ideas are welcomed.

  # reverse(ancestors(tip)) using hg repo
  3) 0.075951
  4) 0.076175

--- a/mercurial/dagop.py	Sun Jun 18 00:22:41 2017 +0900
+++ b/mercurial/dagop.py	Sun Jun 18 00:40:58 2017 +0900
@@ -23,11 +23,13 @@
 # possible maximum depth between null and wdir()
 _maxlogdepth = 0x80000000
 
-def _genrevancestors(repo, revs, followfirst, stopdepth):
+def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth):
     if followfirst:
         cut = 1
     else:
         cut = None
+    if startdepth is None:
+        startdepth = 0
     if stopdepth is None:
         stopdepth = _maxlogdepth
     if stopdepth <= 0:
@@ -53,8 +55,10 @@
             inputrev = next(irevs, None)
             if inputrev is not None:
                 heapq.heappush(pendingheap, (-inputrev, 0))
+        # rescan parents until curdepth >= startdepth because queued entries
+        # of the same revision are iterated from the lowest depth
         foundnew = (currev != lastrev)
-        if foundnew:
+        if foundnew and curdepth >= startdepth:
             lastrev = currev
             yield currev
         pdepth = curdepth + 1
@@ -68,13 +72,14 @@
                     if pctx.rev() != node.nullrev:
                         heapq.heappush(pendingheap, (-pctx.rev(), pdepth))
 
-def revancestors(repo, revs, followfirst, stopdepth=None):
+def revancestors(repo, revs, followfirst, startdepth=None, 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.
+    Scan ends at the stopdepth (exlusive) if specified. Revisions found
+    earlier than the startdepth are omitted.
     """
-    gen = _genrevancestors(repo, revs, followfirst, stopdepth)
+    gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth)
     return generatorset(gen, iterasc=False)
 
 def revdescendants(repo, revs, followfirst):

--- a/mercurial/revset.py	Sun Jun 18 00:22:41 2017 +0900
+++ b/mercurial/revset.py	Sun Jun 18 00:40:58 2017 +0900
@@ -238,11 +238,12 @@
         return baseset([anc.rev()])
     return baseset()
 
-def _ancestors(repo, subset, x, followfirst=False, stopdepth=None):
+def _ancestors(repo, subset, x, followfirst=False, startdepth=None,
+               stopdepth=None):
     heads = getset(repo, fullreposet(repo), x)
     if not heads:
         return baseset()
-    s = dagop.revancestors(repo, heads, followfirst, stopdepth)
+    s = dagop.revancestors(repo, heads, followfirst, startdepth, stopdepth)
     return subset & s
 
 @predicate('ancestors(set[, depth])', safe=True)
@@ -253,18 +254,26 @@
     If depth is specified, the result only includes changesets up to
     the specified generation.
     """
-    args = getargsdict(x, 'ancestors', 'set depth')
+    # startdepth is for internal use only until we can decide the UI
+    args = getargsdict(x, 'ancestors', 'set depth startdepth')
     if 'set' not in args:
         # i18n: "ancestors" is a keyword
         raise error.ParseError(_('ancestors takes at least 1 argument'))
-    stopdepth = None
+    startdepth = stopdepth = None
+    if 'startdepth' in args:
+        n = getinteger(args['startdepth'],
+                       "ancestors expects an integer startdepth")
+        if n < 0:
+            raise error.ParseError("negative startdepth")
+        startdepth = n
     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)
+    return _ancestors(repo, subset, args['set'],
+                      startdepth=startdepth, stopdepth=stopdepth)
 
 @predicate('_firstancestors', safe=True)
 def _firstancestors(repo, subset, x):

--- a/tests/test-revset.t	Sun Jun 18 00:22:41 2017 +0900
+++ b/tests/test-revset.t	Sun Jun 18 00:40:58 2017 +0900
@@ -903,6 +903,29 @@
   6
   5
 
+ (walk 2nd and 3rd ancestors)
+
+  $ log 'reverse(ancestors(7, depth=3, startdepth=2))'
+  5
+  4
+  3
+  2
+
+ (interleaved: '4' would be missing if higher-depth ancestors weren't scanned)
+
+  $ log 'reverse(ancestors(7+8, depth=2, startdepth=2))'
+  5
+  4
+  2
+
+ (note that 'ancestors(x, depth=y, startdepth=z)' does not identical to
+ 'ancestors(x, depth=y) - ancestors(x, depth=z-1)' because a node may have
+ multiple depths)
+
+  $ log 'reverse(ancestors(7+8, depth=2) - ancestors(7+8, depth=1))'
+  5
+  2
+
 test bad arguments passed to ancestors()
 
   $ log 'ancestors(., depth=-1)'