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

login
register
mail settings
Submitter phabricator
Date Aug. 18, 2017, 2:50 p.m.
Message ID <5e882340e5ec47716aace35c94550902@localhost.localdomain>
Download mbox | patch
Permalink /patch/23118/
State Not Applicable
Headers show

Comments

phabricator - Aug. 18, 2017, 2:50 p.m.
quark updated this revision to Diff 1071.

REPOSITORY
  rHG Mercurial

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

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




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

Patch

diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -4511,3 +4511,173 @@ 
 
   $ 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 P4+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
+      define)
+    (func
+      ('symbol', 'ancestors')
+      (or
+        (list
+          (and
+            (or
+              (list
+                ('symbol', 'S1')
+                ('symbol', 'D1')
+                ('symbol', 'P5'))
+              define)
+            (not
+              ('symbol', 'D3')
+              follow)
+            define)
+          ('symbol', 'S2'))
+        define)
+      follow)
+    define)
+  * optimized:
+  (func
+    ('symbol', '_phaseandancestors')
+    (list
+      ('string', 'draft')
+      (or
+        (list
+          (difference
+            (func
+              ('symbol', '_list')
+              ('string', 'S1\x00D1\x00P5')
+              define)
+            ('symbol', 'D3')
+            define)
+          ('symbol', 'S2'))
+        define))
+    define)
+  $ hg debugrevspec --verify -p analyzed -p optimized 'secret() & ::9'
+  * analyzed:
+  (and
+    (func
+      ('symbol', 'secret')
+      None
+      define)
+    (func
+      ('symbol', 'ancestors')
+      ('symbol', '9')
+      follow)
+    define)
+  * optimized:
+  (func
+    ('symbol', '_phaseandancestors')
+    (list
+      ('string', 'secret')
+      ('symbol', '9'))
+    define)
+  $ hg debugrevspec --verify -p analyzed -p optimized '(not public()) & ::(tag())'
+  * analyzed:
+  (and
+    (not
+      (func
+        ('symbol', 'public')
+        None
+        any)
+      define)
+    (func
+      ('symbol', 'ancestors')
+      (func
+        ('symbol', 'tag')
+        None
+        define)
+      follow)
+    define)
+  * optimized:
+  (func
+    ('symbol', '_phaseandancestors')
+    (list
+      ('string', '_notpublic')
+      (func
+        ('symbol', 'tag')
+        None
+        define))
+    define)
+  $ hg debugrevspec --verify -p optimized '(not public()) & ancestors(S1+D2+P5, 1)'
+  * optimized:
+  (and
+    (func
+      ('symbol', '_notpublic')
+      None
+      any)
+    (func
+      ('symbol', 'ancestors')
+      (list
+        (func
+          ('symbol', '_list')
+          ('string', 'S1\x00D2\x00P5')
+          define)
+        ('symbol', '1'))
+      follow)
+    define)
+  $ hg debugrevspec --verify -p optimized '(not public()) & ancestors(S1+D2+P5, depth=1)'
+  * optimized:
+  (and
+    (func
+      ('symbol', '_notpublic')
+      None
+      any)
+    (func
+      ('symbol', 'ancestors')
+      (list
+        (func
+          ('symbol', '_list')
+          ('string', 'S1\x00D2\x00P5')
+          define)
+        (keyvalue
+          ('symbol', 'depth')
+          ('symbol', '1')))
+      follow)
+    define)
diff --git a/mercurial/revsetlang.py b/mercurial/revsetlang.py
--- a/mercurial/revsetlang.py
+++ b/mercurial/revsetlang.py
@@ -313,6 +313,49 @@ 
     if _isposargs(ta, 1) and _isposargs(tb, 1):
         return ('list', ta, tb)
 
+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"""
@@ -436,6 +479,20 @@ 
         if tb is not None and tb[0] == 'not':
             return wa, ('difference', ta, tb[1], order)
 
+        # (draft/secret/_notpublic() & ::x) has a fast path
+        _fastphases = {'draft', 'secret', '_notpublic'}
+        matched = _matchtree(
+            (ta, tb),
+            (('func', ('symbol', _fastphases.__contains__), None,
+                      ('define', 'any').__contains__),
+             ('func', ('symbol', 'ancestors'),
+                      # do not match if "depth" is set for "ancestors"
+                      lambda x: not (x[0] == 'list' and len(x) >= 3),
+                      'follow')))
+        if matched:
+            return w, ('func', ('symbol', '_phaseandancestors'),
+                       ('list', ('string', matched[0]), matched[2]), 'define')
+
         if wa > wb:
             return w, (op, tb, ta, order)
         return w, (op, ta, tb, order)
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -1528,6 +1528,38 @@ 
     getargs(x, 0, 0, "_notpublic takes no arguments")
     return _phase(repo, subset, phases.draft, phases.secret)
 
+@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 = getstring(args[0], _("phasename needs to be a string"))
+    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 keepfunc(rev):
+        return getphase(repo, rev) >= minimalphase
+
+    revs = dagop.revancestors(repo, s, keepfunc=keepfunc)
+
+    if phasename == 'draft': # need to remove secret changesets
+        return revs.filter(lambda r: getphase(repo, r) == draft)
+    else:
+        return 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,38 @@ 
                 if prev != node.nullrev:
                     heapq.heappush(pendingheap, (heapsign * prev, pdepth))
 
-def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth):
+def _genrevancestors(repo, revs, followfirst, startdepth, stopdepth, keepfunc):
     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 keepfunc is None:
+        pfunc = plainpfunc
+    else:
+        pfunc = lambda rev: filter(keepfunc, plainpfunc(rev))
+        revs = smartset.filteredset(revs, keepfunc)
     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, keepfunc=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 keepfunc is provided, it will be used to cut the traversal of the DAG.
+    When keepfunc(X) returns False, the DAG traversal stops - revision X and
+    X's ancestors in the traversal path will be skipped.
     """
-    gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth)
+    gen = _genrevancestors(repo, revs, followfirst, startdepth, stopdepth,
+                           keepfunc)
     return generatorset(gen, iterasc=False)
 
 def _genrevdescendants(repo, revs, followfirst):