Re: [PATCH] fast-import: use binary search in tree_content_remove

From: Shawn O. Pearce <spearce@spearce.org>
Date: Mar 11, 2007, 20:19 UTC
Message-ID: <20070311201912.GA12457@spearce.org>
In-Reply-To: <20070311165432.GA13555@coredump.intra.peff.net>

Jeff King <peff@peff.net> wrote:

Show 12 quoted lines

> On Sun, Mar 11, 2007 at 12:34:13PM -0400, Jeff King wrote:
> 
> > > I'm plastering over the problem by resorting a tree strictly by
> > > name after it has been written out and the deleted entries have
> > > been filtered out.
> > I wonder if we could make this a bit cleaner by actually using the git
> > sort in the first place. I will take a look...
> 
> Hrm, it's not that hard to pass the mode around and use
> base_name_compare, but I don't think that's enough. Any time we turn an
> entry into a tree, we'll have to resort. I think your patch is simpler
> and less error prone.

Yes, but it gets worse. We delete an entry by setting the mode to 0 in version 1, but leaving the entry in the tree so that the entry will show up in version 0 during delta generation.

So what happens if we delete the tree entry, then modify it in the same commit? We can't find it if we are searching with mode included.

Sidenote: I have the same sorting problems in jgit.  It all comes
down to how annoying the tree format is, in that entries are sorted
by both name and mode, but only name makes the entry be unique.

Right now I'm not sure how to resolve this, short of the bandaid patch I put onto the end of your series. :-(

-- 
Shawn.