Patchwork [2,of,2,v2] revset: introduce optional 'while' predicate for descendants()

login
register
mail settings
Submitter Mads Kiilerich
Date Oct. 16, 2014, 9:54 p.m.
Message ID <7bc4f239ad267b2a8c54.1413496440@ssl.google-analytics.com>
Download mbox | patch
Permalink /patch/6350/
State Deferred
Headers show

Comments

Mads Kiilerich - Oct. 16, 2014, 9:54 p.m.
# HG changeset patch
# User Mads Kiilerich <madski@unity3d.com>
# Date 1413496421 -7200
#      Thu Oct 16 23:53:41 2014 +0200
# Node ID 7bc4f239ad267b2a8c54478ffa6a9d11c9cfc5c2
# Parent  1cd08d67e748ca66a270ea5f67346ef262f39c58
revset: introduce optional 'while' predicate for descendants()

When specifying a 'while' set, descendants() will now only consider children
that are in that set. That will make it possible to make some queries that it
not would be possible to make in other ways.

The while expression makes it possible to prune early while traversing
descendants and thus minimize the workload.  Descendants itself will however
(currently) still have to iterate all later changesets to see if other
un-pruned changesets will show up.

The primary motivation for this feature is to keep descendants() similar to
ancestors(). I do not have a very good use case for this and it will
(currently) not prune as efficiently as ancestors will.

Some numbers on the hg repo:

descendants(0) & branch(default)
  wall 1.178284 comb 1.180000 user 1.180000 sys 0.000000 (best of 9)
descendants(0, branch(default))
  wall 1.030509 comb 1.030000 user 1.030000 sys 0.000000 (best of 10)

descendants(0) & branch(stable) & branch(default)
  wall 1.279140 comb 1.280000 user 1.280000 sys 0.000000 (best of 8)
descendants(0, branch(stable) & branch(default))
  wall 0.000242 comb 0.000000 user 0.000000 sys 0.000000 (best of 11915)

With this feature, X::Y could be implemented as descendants(X, ::Y). It do
however seem like this generic code - despite using pruning - has a higher
overhead than the handcoded one and is twice as slow.

descendants("1.0",!::"2.0")
  wall 0.021089 comb 0.020000 user 0.020000 sys 0.000000 (best of 137)

"1.0"::"2.0"
  wall 0.011560 comb 0.010000 user 0.010000 sys 0.000000 (best of 251)

Patch

diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -49,7 +49,7 @@  def _revancestors(repo, revs, followfirs
 
     return generatorset(iterate(), iterasc=False)
 
-def _revdescendants(repo, revs, followfirst):
+def _revdescendants(repo, revs, followfirst, while_=None):
     """Like revlog.descendants() but supports followfirst."""
     cut = followfirst and 1 or None
 
@@ -57,7 +57,7 @@  def _revdescendants(repo, revs, followfi
         cl = repo.changelog
         first = min(revs)
         nullrev = node.nullrev
-        if first == nullrev:
+        if first == nullrev and while_ is None:
             # Are there nodes with a null first parent and a non-null
             # second one? Maybe. Do we care? Probably not.
             for i in cl:
@@ -66,7 +66,8 @@  def _revdescendants(repo, revs, followfi
             seen = set(revs)
             for i in cl.revs(first + 1):
                 for x in cl.parentrevs(i)[:cut]:
-                    if x != nullrev and x in seen:
+                    if x != nullrev and x in seen and (while_ is None or
+                                                       i in while_):
                         seen.add(i)
                         yield i
                         break
@@ -664,10 +665,17 @@  def desc(repo, subset, x):
     return subset.filter(matches)
 
 def _descendants(repo, subset, x, followfirst=False):
-    roots = getset(repo, spanset(repo), x)
+    args = getargs(x, 0, 2, _('descendants takes no, one or two arguments'))
+    if not args:
+        return baseset()
+    roots = getset(repo, spanset(repo), args[0])
+    while_ = None
+    if len(args) > 1:
+        while_ = getset(repo, spanset(repo), args[1])
+        roots = roots & while_
     if not roots:
         return baseset()
-    s = _revdescendants(repo, roots, followfirst)
+    s = _revdescendants(repo, roots, followfirst, while_=while_)
 
     # Both sets need to be ascending in order to lazily return the union
     # in the correct order.
@@ -683,8 +691,9 @@  def _descendants(repo, subset, x, follow
     return result
 
 def descendants(repo, subset, x):
-    """``descendants(set)``
+    """``descendants(set, [while])``
     Changesets which are descendants of changesets in set.
+    If a while set is specified, only follow descendants in that set.
     """
     return _descendants(repo, subset, x)
 
diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -301,6 +301,10 @@  ancestor can accept 0 or more arguments
   7
   8
   9
+  $ log 'descendants(1+4, 3:6+8)'
+  4
+  6
+  8
   $ log 'file("b*")'
   1
   4