apply: do not get confused by symlinks in the middle

apply: do not get confused by symlinks in the middle

HPA noticed that git-rebase fails when changes involve symlinks
in the middle of the hierarchy.  Consider:

 * The tree state before the patch is applied has arch/x86_64/boot
   as a symlink pointing at ../i386/boot/

 * The patch tries to remove arch/x86_64/boot symlink, and
   create bunch of files there: .gitignore, Makefile, etc.

git-apply tries to be careful while applying patches; it never
touches the working tree until it is convinced that the patch
would apply cleanly.  One of the check it does is that when it
knows a path is going to be created by the patch, it runs
lstat() on the path to make sure it does not exist.

This leads to a false alarm.  Because we do not touch the
working tree before all the check passes, when we try to make
sure that arch/x86_64/boot/.gitignore does not exist yet, we
haven't removed the arch/x86_64/boot symlink.  The lstat() check
ends up seeing arch/i386/boot/.gitignore through the
yet-to-be-removed symlink, and says "Hey, you already have a
file there, but what you fed me is a patch to create a new
file. I am not going to clobber what you have in the working
tree."

We have similar checks to see a file we are going to modify does
exist and match the preimage of the diff, which is done by
directly opening and reading the file.

For a file we are going to delete, we make sure that it does
exist and matches what is going to be removed (a removal patch
records the full preimage, so we check what you have in your
working tree matches it in full -- otherwise we would risk
losing your local changes), which again is done by directly
opening and reading the file.

These checks need to be adjusted so that they are not fooled by
symlinks in the middle.

 - To make sure something does not exist, first lstat().  If it
   does not exist, it does not, so be happy.  If it _does_, we
   might be getting fooled by a symlink in the middle, so break
   leading paths and see if there are symlinks involved.  When
   we are checking for a path a/b/c/d, if any of a, a/b, a/b/c
   is a symlink, then a/b/c/d does _NOT_ exist, for the purpose
   of our test.

   This would fix this particular case you saw, and would not
   add extra overhead in the usual case.

 - To make sure something already exists, first lstat().  If it
   does not exist, barf (up to this, we already do).  Even if it
   does seem to exist, we might be getting fooled by a symlink
   in the middle, so make sure leading paths are not symlinks.

   This would make the normal codepath much more expensive for
   deep trees, which is a bit worrisome.

This patch implements the first side of the check "making sure
it does not exist".  The latter "making sure it exists" check is
not done yet, so applying the patch in reverse would still
fail, but we have to start from somewhere.

Signed-off-by: Junio C Hamano <junkio@cox.net>