Re: [RFH] bug in unpack_trees

From: Daniel Barkalow <barkalow@iabervon.org>
Date: Mar 5, 2008, 06:47 UTC
Message-ID: <alpine.LNX.1.00.0803050130190.19665@iabervon.org>
In-Reply-To: <alpine.LFD.1.00.0803041325370.12253@woody.linux-foundation.org>

On Tue, 4 Mar 2008, Linus Torvalds wrote:

Show 9 quoted lines

> 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.

Show 9 quoted lines

> 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*