D441: revset: optimize "draft() & ::x" pattern
quark (Jun Wu)
phabricator at mercurial-scm.org
Fri Aug 18 00:57:04 EDT 2017
quark updated this revision to Diff 1057.
REPOSITORY
rHG Mercurial
CHANGES SINCE LAST UPDATE
https://phab.mercurial-scm.org/D441?vs=1056&id=1057
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
@@ -4511,3 +4511,165 @@
$ 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)'
+ * analyzed:
+ (and
+ (func
+ ('symbol', 'draft')
+ None
+ define)
+ (func
+ ('symbol', 'ancestors')
+ (and
+ (or
+ (list
+ ('symbol', 'S1')
+ ('symbol', 'D1')
+ ('symbol', 'P5'))
+ define)
+ (not
+ ('symbol', 'D3')
+ follow)
+ define)
+ follow)
+ define)
+ * optimized:
+ (func
+ ('symbol', '_phaseandancestors')
+ (list
+ ('string', 'draft')
+ (difference
+ (func
+ ('symbol', '_list')
+ ('string', 'S1\x00D1\x00P5')
+ define)
+ ('symbol', 'D3')
+ define))
+ define)
+ $ hg debugrevspec --verify -p analyzed -p optimized 'secret() & ::(7::)'
+ * analyzed:
+ (and
+ (func
+ ('symbol', 'secret')
+ None
+ define)
+ (func
+ ('symbol', 'ancestors')
+ (func
+ ('symbol', 'descendants')
+ ('symbol', '7')
+ define)
+ follow)
+ define)
+ * optimized:
+ (func
+ ('symbol', '_phaseandancestors')
+ (list
+ ('string', 'secret')
+ (func
+ ('symbol', 'descendants')
+ ('symbol', '7')
+ define))
+ define)
+ $ hg debugrevspec --verify -p analyzed -p optimized '(not public()) & ::(S1)'
+ * analyzed:
+ (and
+ (not
+ (func
+ ('symbol', 'public')
+ None
+ any)
+ define)
+ (func
+ ('symbol', 'ancestors')
+ ('symbol', 'S1')
+ follow)
+ define)
+ * optimized:
+ (func
+ ('symbol', '_phaseandancestors')
+ (list
+ ('string', '_notpublic')
+ ('symbol', 'S1'))
+ 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,32 @@
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.
+ """
+ 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 +462,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)
+ at predicate('_phaseandancestors(phasename, set)', safe=True)
+def _phaseandancestors(repo, subset, x):
+ """Equivalent to (phasename() & ancestors(set)) but faster.
+ 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, secret),
+ 'draft': (draft, secret), # follow secret's parents
+ 'secret': (secret,),
+ }
+ if phasename not in phasenamemap:
+ raise error.ParseError(_('%r is not a valid phasename') % phasename)
+
+ selectedphases = phasenamemap[phasename]
+ getphase = repo._phasecache.phase
+
+ def keepfunc(rev):
+ return getphase(repo, rev) in selectedphases
+
+ 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):
To: quark, #hg-reviewers
Cc: mercurial-devel
More information about the Mercurial-devel
mailing list