[RFH] bug in unpack_trees

[Jeff King <peff@peff.net>]

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