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): 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 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/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'), ('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) + [('symbol', 'A')] + >>> _matchtree(parse('A'), (t, lambda x: x == 'A')) + ['symbol', 'A'] + >>> _matchtree(parse('A'), (t, lambda x: x == 'B')) + >>> _matchtree(parse('A+B'), ('or', ('list', t, ('symbol', t)))) + [('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/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)