[PATCH] revset: introduce optional 'while' predicate for ancestors()

[Pierre-Yves David]

On 10/07/2014 05:22 PM, Mads Kiilerich wrote:
> # HG changeset patch
> # User Mads Kiilerich <madski at unity3d.com>
> # Date 1412727753 -7200
> #      Wed Oct 08 02:22:33 2014 +0200
> # Node ID 7c48c97a07b865c86a75562f94656a64a8506273
> # Parent  564ae7d2ec9bee86b00a6ba817271ac0b19deca7
> revset: introduce optional 'while' predicate for ancestors()
>
> When specifying a 'while' set, ancestors() will now only visit parents that are
> in that set. This makes it possible to prune while doing an ancestor traversal
> and reduce the number of membership tests.  Such a pruning is very convenient
> when expensive checks are involved.

Good feature, not really possible to achieve the same result easily (and 
definitely not with the same perf)

>
> The primary initial use case for this feature is that filtering on branch name
> is so expensive. Often it is just as relevant to prune everything not on the
> branch.
>
> Example:
>
>    $ hg --time debugrevspec 'branch(.)' | wc -l
>    time: real 9.380 secs (user 9.200+0.000 sys 0.180+0.000)
>    119
>
>    $ hg --time debugrevspec 'ancestors(.)&branch(.)' | wc -l
>    time: real 10.070 secs (user 9.940+0.000 sys 0.110+0.000)
>    119
>
>    $ hg --time debugrevspec 'ancestors(., branch(.))' | wc -l
>    time: real 0.160 secs (user 0.140+0.000 sys 0.020+0.000)
>    119

Would be interested in output from the perf extension. Probably not 
worth adding an entry in the official benchmark. But I may be wrong.

Also please retry to the latest state of revset the code (pushed in the 
clowncopter 1h ago). Feel encourage to peek at the code path and 
optimize silly things you could find.

> diff --git a/mercurial/revset.py b/mercurial/revset.py
> --- a/mercurial/revset.py
> +++ b/mercurial/revset.py
> @@ -17,7 +17,7 @@ import obsolete as obsmod
>   import pathutil
>   import repoview
>
> -def _revancestors(repo, revs, followfirst):
> +def _revancestors(repo, revs, followfirst, while_=None):
>       """Like revlog.ancestors(), but supports followfirst."""
>       cut = followfirst and 1 or None
>       cl = repo.changelog
> @@ -41,10 +41,11 @@ def _revancestors(repo, revs, followfirs
>                           revsnode = revqueue.popleft()
>                           heapq.heappush(h, -revsnode)
>                   seen.add(current)
> -                yield current
> -                for parent in cl.parentrevs(current)[:cut]:
> -                    if parent != node.nullrev:
> -                        heapq.heappush(h, -parent)
> +                if while_ is None or current in while_:
> +                    yield current
> +                    for parent in cl.parentrevs(current)[:cut]:
> +                        if parent != node.nullrev:
> +                            heapq.heappush(h, -parent)
>
>       return _generatorset(iterate(), iterasc=False)
>
> @@ -344,15 +345,22 @@ def ancestor(repo, subset, x):
>       return baseset([])
>
>   def _ancestors(repo, subset, x, followfirst=False):
> -    args = getset(repo, spanset(repo), x)
> +    args = getargs(x, 0, 2, _('ancestors takes no, one or two arguments'))
>       if not args:
>           return baseset([])
> -    s = _revancestors(repo, args, followfirst)
> +    heads = getset(repo, _spanset(repo), args[0])
> +    if not heads:
> +        return baseset([])
> +    while_ = None
> +    if len(args) > 1:
> +        while_ = getset(repo, _spanset(repo), args[1])

_spanset(repo) is very very wrong. Should be spanset(repo) (or 
fullreposet(repo) as returned by the spanset call)

> +    s = _revancestors(repo, heads, followfirst, while_=while_)
>       return subset.filter(s.__contains__)

Unrelated, but should be `subset && s`. I'll do a series about those.

>   def ancestors(repo, subset, x):
> -    """``ancestors(set)``
> +    """``ancestors(set, [while])``
>       Changesets that are ancestors of a changeset in set.
> +    If a while set is specified, only follow ancestors in that set.
>       """
>       return _ancestors(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
> @@ -246,6 +246,16 @@ ancestor can accept 0 or more arguments
>     5
>     $ log 'ancestor(ancestors(5))'
>     0
> +
> +ancestors can prune using the optional while expression
> +
> +  $ hg log -T'{rev}\n' -r 'ancestors(5+9,1:7)'
> +  1
> +  3
> +  5
> +
> +other expressions ...
> +
>     $ log 'author(bob)'
>     2
>     $ log 'author("re:bob|test")'
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel at selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
>

-- 
Pierre-Yves David