comparison of bookmarks at incoming/outgoing

[Pierre-Yves David]

On 20 août 2012, at 23:40, Matt Mackall wrote:

> On Mon, 2012-08-20 at 11:49 -0500, Kevin Bullock wrote:
>> On Aug 20, 2012, at 5:21 AM, FUJIWARA Katsunori wrote:
>> 
>>> So, what about adding HINT information like below ?
>>> 
>>> - it is assumed that bookmarks points:
>>>   - REV-L on local side
>>>   - REV-R on remote side
>>> 
>>> - if local repo has REV-R:
>>> 
>>>   - if common ancestor of REV-L and REV-R is none of each:
>>>     show "divergent" as hint
>>> 
>>>   - otherwise:
>>>     - if common ancestor of them is REV-L:
>>>       show "advanced remotely" as hint
>>> 
>>>     - otherwise:
>>>       show "advanced locally" as hint
>> 
>> …which, to summarize, is the case where we *can* tell reliably whether
>> the remote bookmark is advanced remotely, advanced locally, or
>> divergent. So far so good. I gather that the common ancestor
>> calculation is O(n), where n <= count(ANC::REV1) + count(ANC::REV2).
>> Someone with more than passing knowledge of the algorithm can correct
>> me. In any case, I'm not sure it would make a huge difference relative
>> to the network communications time.
> 
>> *waits for Bryan to jump in*
> 
> I'll jump in instead. The question of whether X and Y are divergent is
> actually much simpler than actually finding a common ancestor, since we
> already have a topologically sorted DAG.
> 
> - pick the greater of X and Y as start, smaller as target
> - iterate back through its ancestors
>  - stop if target is encountered -> linear
>  - recurse on parents > target
> - if we run out of things to visit -> divergent
> 
> The run time here is limited by the distance between X and Y in
> revisions.
> 
> We should probably have a method somewhere for this.

I posted a series that extract this logic in a function on the list at the end of july. Will it eventually emerge from your backlog or should I patch bomb it again ?

The series also added logic taking successors//precursors into account to determine if the new bookmark location was a valid update target. (Because typical successors are not descendants of precursors)


-- 
Pierre-Yves