D441: revset: optimize "draft() & ::x" pattern

quark (Jun Wu) phabricator at mercurial-scm.org
Sat Sep 2 01:24:23 UTC 2017


quark updated this revision to Diff 1570.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D441?vs=1075&id=1570

REVISION DETAIL
  https://phab.mercurial-scm.org/D441

AFFECTED FILES
  mercurial/dagop.py
  mercurial/revset.py
  mercurial/revsetlang.py
  tests/test-revset.t

CHANGE DETAILS

diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -4321,3 +4321,147 @@
 
   $ hg log -r 'successors(B+A)-contentdivergent()-obsolete()' -T '{desc}\n'
   Z
+
+Test `draft() & ::x` optimization
+
+  $ hg init $TESTTMP/repo2
+  $ cd $TESTTMP/repo2
+  $ hg debugdrawdag <<'EOS'
+  >   P5 S1
+  >    |  |
+  > S2 | D3
+  >   \|/
+  >   P4
+  >    |
+  >   P3 D2
+  >    |  |
+  >   P2 D1
+  >    |/
+  >   P1
+  >    |
+  >   P0
+  > EOS
+  $ hg phase --public -r P5
+  $ hg phase --force --secret -r S1+S2
+  $ hg log -G -T '{rev} {desc} {phase}' -r 'sort(all(), topo, topo.firstbranch=P5)'
+  o  8 P5 public
+  |
+  | o  10 S1 secret
+  | |
+  | o  7 D3 draft
+  |/
+  | o  9 S2 secret
+  |/
+  o  6 P4 public
+  |
+  o  5 P3 public
+  |
+  o  3 P2 public
+  |
+  | o  4 D2 draft
+  | |
+  | o  2 D1 draft
+  |/
+  o  1 P1 public
+  |
+  o  0 P0 public
+  
+  $ hg debugrevspec --verify -p analyzed -p optimized 'draft() & ::(((S1+D1+P5)-D3)+S2)'
+  * analyzed:
+  (and
+    (func
+      ('symbol', 'draft')
+      None)
+    (func
+      ('symbol', 'ancestors')
+      (or
+        (list
+          (and
+            (or
+              (list
+                ('symbol', 'S1')
+                ('symbol', 'D1')
+                ('symbol', 'P5')))
+            (not
+              ('symbol', 'D3')))
+          ('symbol', 'S2')))))
+  * optimized:
+  (func
+    ('symbol', '_phaseandancestors')
+    (list
+      ('symbol', 'draft')
+      (or
+        (list
+          (difference
+            (func
+              ('symbol', '_list')
+              ('string', 'S1\x00D1\x00P5'))
+            ('symbol', 'D3'))
+          ('symbol', 'S2')))))
+  $ hg debugrevspec --verify -p analyzed -p optimized 'secret() & ::9'
+  * analyzed:
+  (and
+    (func
+      ('symbol', 'secret')
+      None)
+    (func
+      ('symbol', 'ancestors')
+      ('symbol', '9')))
+  * optimized:
+  (func
+    ('symbol', '_phaseandancestors')
+    (list
+      ('symbol', 'secret')
+      ('symbol', '9')))
+  $ hg debugrevspec --verify -p analyzed -p optimized '7 & ( (not public()) & ::(tag()) )'
+  * analyzed:
+  (and
+    ('symbol', '7')
+    (and
+      (not
+        (func
+          ('symbol', 'public')
+          None))
+      (func
+        ('symbol', 'ancestors')
+        (func
+          ('symbol', 'tag')
+          None))))
+  * optimized:
+  (and
+    ('symbol', '7')
+    (func
+      ('symbol', '_phaseandancestors')
+      (list
+        ('symbol', '_notpublic')
+        (func
+          ('symbol', 'tag')
+          None))))
+  $ hg debugrevspec --verify -p optimized '(not public()) & ancestors(S1+D2+P5, 1)'
+  * optimized:
+  (and
+    (func
+      ('symbol', '_notpublic')
+      None)
+    (func
+      ('symbol', 'ancestors')
+      (list
+        (func
+          ('symbol', '_list')
+          ('string', 'S1\x00D2\x00P5'))
+        ('symbol', '1'))))
+  $ hg debugrevspec --verify -p optimized '(not public()) & ancestors(S1+D2+P5, depth=1)'
+  * optimized:
+  (and
+    (func
+      ('symbol', '_notpublic')
+      None)
+    (func
+      ('symbol', 'ancestors')
+      (list
+        (func
+          ('symbol', '_list')
+          ('string', 'S1\x00D2\x00P5'))
+        (keyvalue
+          ('symbol', 'depth')
+          ('symbol', '1')))))
diff --git a/mercurial/revsetlang.py b/mercurial/revsetlang.py
--- a/mercurial/revsetlang.py
+++ b/mercurial/revsetlang.py
@@ -273,6 +273,49 @@
 def _matchonly(revs, bases):
     return _match('ancestors(_) and not ancestors(_)', ('and', revs, bases))
 
+def _matchtree(tree, pattern):
+    """like re.match, return matched patterns or None if not matched
+
+    A fixed string matches a fixed string. A lambda matches and captures things
+    if it returns True. A tuple will trigger a recursive match on its elements.
+    Return a list of captured subtrees.
+
+    >>> t = lambda x: True
+    >>> _matchtree(parse('A'), ('symbol', 'A'))
+    []
+    >>> _matchtree(parse('A'), t)
+    [('symbol', 'A')]
+    >>> _matchtree(parse('A'), ('symbol', ('A',)))
+    >>> _matchtree(parse('A'), ('symbol', 'A', 'B'))
+    >>> _matchtree(parse('A'), ('func', 'A'))
+    >>> _matchtree(parse('A'), ('symbol'))
+    >>> _matchtree(parse('A'), 'A')
+    >>> _matchtree(parse('A'), (t, lambda x: x == 'A'))
+    ['symbol', 'A']
+    >>> _matchtree(parse('A'), (t, lambda x: x == 'B'))
+    >>> _matchtree(parse('A+B'), (t, ('list', t, ('symbol', t))))
+    ['or', ('symbol', 'A'), 'B']
+    """
+    matchedlist = []
+    if util.safehasattr(pattern, '__call__'):
+        matched = pattern(tree)
+        if matched:
+            return [tree]
+        else:
+            return None
+    else:
+        if isinstance(tree, tuple):
+            if not isinstance(pattern, tuple) or len(tree) != len(pattern):
+                return None
+            for i, t in enumerate(tree):
+                matched = _matchtree(t, pattern[i])
+                if matched is None:
+                    return None
+                matchedlist.extend(matched)
+        elif tree != pattern:
+            return None
+    return matchedlist
+
 def _fixops(x):
     """Rewrite raw parsed tree to resolve ambiguous syntax which cannot be
     handled well by our simple top-down parser"""
@@ -369,14 +412,20 @@
         wb, tb = _optimize(x[2], True)
         w = min(wa, wb)
 
+        # (draft/secret/_notpublic() & ::x) has a fast path
+        m = _match('_() & ancestors(_)', ('and', ta, tb))
+        if m and getsymbol(m[1]) in {'draft', 'secret', '_notpublic'}:
+            return w, _build('_phaseandancestors(_, _)', m[1], m[2])
+
         # (::x and not ::y)/(not ::y and ::x) have a fast path
         m = _matchonly(ta, tb) or _matchonly(tb, ta)
         if m:
             return w, _build('only(_, _)', *m[1:])
 
         m = _match('not _', tb)
         if m:
             return wa, ('difference', ta, m[1])
+
         if wa > wb:
             op = 'andsmally'
         return w, (op, ta, tb)
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1577,6 +1577,36 @@
     getargs(x, 0, 0, "_notpublic takes no arguments")
     return _phase(repo, subset, phases.draft, phases.secret)
 
+ at predicate('_phaseandancestors(phasename, set)', safe=True)
+def _phaseandancestors(repo, subset, x):
+    # equivalent to (phasename() & ancestors(set)) but more efficient
+    # phasename could be one of 'draft', 'secret', or '_notpublic'
+    args = getargs(x, 2, 2, _("_phaseandancestors requires two arguments"))
+    phasename = getsymbol(args[0])
+    s = getset(repo, fullreposet(repo), args[1])
+
+    draft = phases.draft
+    secret = phases.secret
+    phasenamemap = {
+        '_notpublic': draft,
+        'draft': draft, # follow secret's ancestors
+        'secret': secret,
+    }
+    if phasename not in phasenamemap:
+        raise error.ParseError(_('%r is not a valid phasename') % phasename)
+
+    minimalphase = phasenamemap[phasename]
+    getphase = repo._phasecache.phase
+
+    def cutfunc(rev):
+        return getphase(repo, rev) < minimalphase
+
+    revs = dagop.revancestors(repo, s, cutfunc=cutfunc)
+
+    if phasename == 'draft': # need to remove secret changesets
+        revs = revs.filter(lambda r: getphase(repo, r) == draft)
+    return subset & revs
+
 @predicate('public()', safe=True)
 def public(repo, subset, x):
     """Changeset in public phase."""
diff --git a/mercurial/dagop.py b/mercurial/dagop.py
--- a/mercurial/dagop.py
+++ b/mercurial/dagop.py
@@ -75,27 +75,49 @@
                 if prev != node.nullrev:
                     heapq.heappush(pendingheap, (heapsign * prev, pdepth))
 
-def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth):
+def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, cutfunc):
     if followfirst:
         cut = 1
     else:
         cut = None
     cl = repo.changelog
-    def pfunc(rev):
+    def plainpfunc(rev):
         try:
             return cl.parentrevs(rev)[:cut]
         except error.WdirUnsupported:
             return (pctx.rev() for pctx in repo[rev].parents()[:cut])
+    if cutfunc is None:
+        pfunc = plainpfunc
+    else:
+        pfunc = lambda rev: [r for r in plainpfunc(rev) if not cutfunc(r)]
+        revs = revs.filter(lambda rev: not cutfunc(rev))
     return _walkrevtree(pfunc, revs, startdepth, stopdepth, reverse=True)
 
-def revancestors(repo, revs, followfirst, startdepth=None, stopdepth=None):
+def revancestors(repo, revs, followfirst=False, startdepth=None,
+                 stopdepth=None, cutfunc=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. Revisions found
     earlier than the startdepth are omitted.
+
+    If cutfunc is provided, it will be used to cut the traversal of the DAG.
+    When cutfunc(X) returns False, the DAG traversal stops - revision X and
+    X's ancestors in the traversal path will be skipped. This could be an
+    optimization sometimes.
+
+    Note: if Y is an ancestor of X, cutfunc(X) returning True does not
+    necessarily mean Y will also be cut. Usually cutfunc(Y) also wants to
+    return True in this case. For example,
+
+        D     # revancestors(repo, D, cutfunc=lambda rev: rev == B)
+        |\    # will include "A", because the path D -> C -> A was not cut.
+        B C   # If "B" gets cut, "A" might want to be cut too.
+        |/
+        A
     """
-    gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth)
+    gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth,
+                           cutfunc)
     return generatorset(gen, iterasc=False)
 
 def _genrevdescendants(repo, revs, followfirst):



To: quark, #hg-reviewers
Cc: yuja, martinvonz, mercurial-devel


More information about the Mercurial-devel mailing list