comparison of bookmarks at incoming/outgoing

[Matt Mackall]

On Tue, 2012-08-21 at 01:56 +0200, Pierre-Yves David wrote:
> 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.

Really? You wrote the above algorithm as a helper function already?
Color me skeptical.

Perhaps by "end of July", you mean August 1, in which case, no, those
patches don't relate to the above at all. But you should resend.

-- 
Mathematics is the supreme nostalgia of our time.