[RFH] bug in unpack_trees

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.

You can see the problem with this script:

  # make a repo
  mkdir repo && cd repo && git init

  # make a directory which will become a df conflict
  mkdir df
  echo content >df/file
  git add df/file
  git commit -m one

  # and save a copy of the index
  git ls-files >index1

  # now make a new commit that has the df conflict and
  # a newly added file
  rm -rf df
  echo content >df
  git add df
  echo content >new
  git add new
  git commit -m two

  # now this should put our index exactly back to 'one'
  git reset --hard HEAD^

  # but it doesn't
  git ls-files >index2
  diff -u index1 index2

The 'new' file is still in the index, and it shouldn't be. It's actually not git-reset to blame, but the "git read-tree -u --reset HEAD^" that it calls. The problem reproduces with every version of git I tried, so I suspect it is as old as unpack_trees.

As far as I can tell, the D/F conflict somehow gets the list merge out of sync. In unpack_trees_rec, every cache entry we look up gets compared to the first tree entry, but because we are out of sync, the tree entry will always become the new "first" (it looks like this test is supposed to be for processing foo/ before foo/bar, and shouldn't otherwise trigger). Because "first" and "cache_name" don't match, we don't realize we haven't found an entry missing from the tree, and we don't trigger the removal code.

So where I need help is figuring out how the traversal is _supposed_ to work. I.e., why does it get out of sync on the D/F case? I'm sure it's probably a one-liner fix, but I just don't see it.

-Peff