Re: [RFH] bug in unpack_trees

From: Daniel Barkalow <barkalow@iabervon.org>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Jeff King <peff@peff.net>,
	git@vger.kernel.org, Junio C Hamano <gitster@pobox.com>,
	John Goerzen <jgoerzen@complete.org>
Subject: Re: [RFH] bug in unpack_trees
Date: Wed, 5 Mar 2008 01:47:57 -0500 (EST)	[thread overview]
Message-ID: <alpine.LNX.1.00.0803050130190.19665@iabervon.org> (raw)
In-Reply-To: <alpine.LFD.1.00.0803041325370.12253@woody.linux-foundation.org>

On Tue, 4 Mar 2008, Linus Torvalds wrote:

> On Tue, 4 Mar 2008, Jeff King wrote:
> >
> > I am tracking down a bug in unpack_trees, but I can't seem to find the
> > exact problem; I'm hoping to get help from people who have touched this
> > code a bit more than I have.
> 
> Ok, I haven't (the blame for that unpack_trees function lies mainly at 
> Dscho, I think ;), and now that I'm looking at it more closely I really 
> don't think unpack_trees() is salvageable.

It was mostly me, 2.5 years ago in a file with a different name.

> I tried. I can't make it work.
> 
> The only really sane way to traverse trees in parallel is with the 
> walk-tree.c functionality (ie using "traverse_trees()"), which is quite 
> straightforward and rather simple, and which I can pretty much guarantee 
> works.
> 
> In contrast, the things that unpack_trees() does to try to figure out how 
> to mix in the index into the pot really doesn't work.

The thing that's hopeless isn't including the index; it's including the 
index that's simultaneously being regenerated. In this case, the mode 0 
entry for df is getting dropped in order to not have both a "remove df" 
entry and a create "df/file" entry, and this means that the position in 
the index is one entry later than it should be, skipping over "new", which 
then doesn't get touched.

Of course, regenerating the same index is not only very difficult but 
inefficient, because it involves adding and removing elements from the 
middle of an array. The sensible thing is just to generate a new 
in-memory index and swap it in on success at the end. This makes the 
position update trivial (increment the position if you use the entry) and 
the result generation efficient. In the process, we could have a separate 
list of things to unlink() that aren't stored as weird index entries.

> I'll take a good hard look at trying to convert users of unpack_trees() 
> into traverse_trees(), or perhaps even convert "unpack_trees()" itself.

I'll see if I can get something sensible worked out Wednesday afternoon.

	-Daniel
*This .sig left intentionally blank*