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

[Mads Kiilerich]

On 10/12/2014 03:43 AM, Pierre-Yves David wrote:
>
>
> On 10/11/2014 05:45 PM, Mads Kiilerich wrote:
>> On 10/11/2014 02:41 AM, Pierre-Yves David wrote:
>>>
>>>
>>> On 10/10/2014 07:12 AM, Mads Kiilerich wrote:
>>>> On 10/08/2014 03:27 AM, Pierre-Yves David wrote:
>>>>>
>>>>>
>>>>> 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.
>>>>>>
>>>>>> 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.
>>>>>
>>>>> Feature seems interresting. However ther is a massive refactoring on
>>>>> revset in progress. I'll look at the patch after the end of the
>>>>> refactoring landed (opfully tomorrow).
>>>>
>>>> Any news on this ... or general thoughts on it from others?
>>>>
>>>> Do you guys agree such ancestor pruning is relevant? Can you imagine
>>>> other kinds of pruning than when yielding ancestors?
>>>
>>> Could be useful for descendant too.
>>
>> For my primary use case of finding changesets on a branch, we don't need
>> it. We already have the branch head and do thus know up front that all
>> changesets after that can be pruned.
>
> Not that your revset fais to find all changeset in a branch if there 
> is any discontinuity in that branch.

Yes. And there is unfortunately no cheap way to find the "continuity heads".

>> That do not require new language
>> support. But yes, it should be added to descendeants too for
>> completeness and consistency.
>
> I'm confused, I'm reading you asking for other example could be useful 
> and then I read you complaining about my example being unrelated to 
> your patch… I must have misunderstood something ☺

Yes ;-) I am saying that I agree the kind of "while pruning" I add to 
ancestors also should be added to descendants too. But there is also 
workarounds that can be used for descendants, so it is not as essential 
for descendants as it is for ancestors.

>
>>> Seems related to `only()` so maybe the implementation could be joined
>>> or something.
>>
>> Hmm. Yes. only(X,Y) == ancestors(X,!::Y) . The computation of ::Y should
>> already be lazy and optimized ... but probably not as much as the
>> current implementation of only.
>
> You mean the currently non-lazy version of only ? :-p

? Afaics missingancestors is lazy. It could however be smarter in what 
it walks. I doubt the generic functionality I introduce can do any 
better for the special case of walking 2 ancestors sets and prune when 
they intersect.

>
>>> Seems also related to X::Y.
>>
>> That one requires backtracking or some kind of keeping track of traces
>> of multiple paths and merge or discard them while iterating the DAG. I
>> don't think there is anything to share with this feature.
>
> I'm not sure I follow you here.
>
> X::Y <==> X:: and :: Y <==> ancestors(Y, while=X::)

Right. There is something that could be shared. Now I don't know whether 
it would make X::Y any better.

Computing X::Y that way, it will start out computing the full set of 
X::&:Y and then compute ::Y inside that set. Finding X::&:Y is expensive 
and requires walking X:Y from Y to X while keeping track of all the 
parent relations reversed.

I guess it could be more efficient to compute it as descendants(X, 
while=::Y).

We could try to implement X::Y using this while expression and see how 
it works out ... but it must still be possible to implement it much more 
efficiently with an explicit implementation that collects and stores the 
relevant child relations while computing X:&::Y so it efficiently can 
compute X:: inside that set.

Thanks for the feedback.

/Mads