[PATCH 2 of 4] log: do not walk the entire revision window when it's bigger than required

[Matt Mackall]

On Wed, 2010-04-28 at 09:59 +0200, Benoit Boissinot wrote:
> On Wed, Apr 28, 2010 at 12:43:12AM -0500, Matt Mackall wrote:
> > On Wed, 2010-04-28 at 14:08 +0900, Nicolas Dumazet wrote:
> > > I talked a bit about it with Benoit on IRC.
> > > 
> > > I admit that I still have difficulties to wrap my mind around
> > > non-monotic linkrevs. I see the output of test-strip-cross and it
> > > helps to see that it indeed happens. But the way the revisions are
> > > created is a bit too cryptic to allow me to think about it.
> > 
> > If I recall correctly, it works like this:
> > 
> > - filerevs created with the same content and same parents have the same
> >   hash
> > - newly-created identical files are a common instance of such
> > - pull will fix up linkrevs when doing a pull where the linked rev is
> >   not included (ie on a parallel branch)
> > - the file revisions come across in their original order, so an old file
> >   revision can be fixed up to point to a new cset
> > - the next linkrev will probably "cross" in by pointing to an earlier
> >   revision
> 
> Yes that's it, we don't reorder filerevs on pull/push.
> > 
> > The real problem isn't the crossing, so much as the fact that we now
> > have a pointer that points to the future rather than the past. Perhaps
> > if we were smarter, we'd have made pull reorder things in flight. But
> > strip can create a similar situation.
> 
> And anyway, we probably need to live with the fact that cross-linkrev
> exists.

You know, in most situations, we can probably just sort filelog and
manifest indices by linkrev and arrive at an ordering that is a) still
topological and b) "compatible" with the changelog ordering. Something
like:

visitorder = range(len(fl)).sort(key=fl.linkrev)
for r in visitorder:
   ...

-- 
http://selenic.com : development and support for Mercurial and Linux