Subject: [PATCH] merge-recursive: ignore_case shouldn't reject intentional removals

From: Elijah Newren <[email-masked]>
Date: Fri, 24 Nov 2017 11:59:01 -0800

In commit ae352c7f3 (merge-recursive.c: fix case-changing merge bug,
2014-05-01), it was observed that removing files could be problematic on
case insensitive file systems, because we could end up removing files
that differed in case only rather than deleting the intended file --
something that happened when files were renamed on one branch in a way
that differed only in case.  To avoid that problem, that commit added
logic to avoid removing files other than the one intended, rejecting the
removal if the files differed only in case.

Unfortunately, the logic it used didn't fully implement that condition as
stated above; instead it merely checked that a case-insensitive lookup of
the file that was requested resulted in finding a file in the index at
stage 0, not that the file found in the index actually differed in case.
Alternatively, one could view the implementation as making an implicit
assumption that the file we actually wanted to remove would never appear
in the index with a stage of 0, and thus that if we found a file with our
lookup, that it had to be a different file (but different in case only).

The net result of this implementation is that it can ignore more requests
than it should, leaving a file around in the working copy that should
have been removed.  Make sure that the file found in the index actually
differs in case before silently ignoring the request to remove the file.

---

If that description leaves more questions than answers, we may need to
augment the above commit message with the following explanation...

But, you may ask, why didn't we ever discover this problem before?  And
why would we have a file at stage 0 in the index that we wanted to remove
from the working copy?  Great questions, both, but the answer is fairly
lengthy.  The short answer to the first question is that due to a myriad
of details, this bug is only currently triggerable:

    * on case insensitive filesystems
    * with rename/rename(2to1) conflicts
    * once one has taken care to avoid allowing renames to overwrite
      untracked or dirty files (see commit 30fd3a5 (merge overwrites
      unstaged changes in renamed file, 2012-04-15), which was fixed in
      my in-flight en/rename-directory-detection series currently sitting
      in pu)
    * AND where one of the renames is implicitly done (e.g. via
      directory rename detection).

Thus, this bug remained hidden/latent until those other conditions are
all triggered.  Luckily, testcase 7b of t6043 added in
en/rename-directory-detection was written to carefully check all details
of the index and working copy to ensure they had the right content,
giving us an early notification of this bug.  (I was worried when I wrote
those tests that I was being too laborious in checking all details, but I
apparently got lucky and the extra checks in one of them paid off.)

To explain why we would have a file at stage 0 in the index that we
wanted to remove from the working copy can be explained by four points
(most of which bring up further questions, but be patient and I'll try to
wrap up all the loose ends):

  * If we have two conflicting files at PATH, we will want the index to
    have two higher stage entries for PATH.  There are a few choices for
    the working copy, but one prominent choice is to remove PATH from the
    working copy, then create PATH~HEAD and PATH~$MERGE files.  This
    strategy for the working copy is currently used for
    rename/rename(2to1) conflicts, though it has also been proposed (in
    my pending rename-perf series I submitted this month) for some
    add/add and rename/add conflicts.

  * When unpack_trees() (called by merge-recursive) notices two paths at
    the same location (which could mean an add/add conflict, or after
    rename detection it might more precisely turn out to be a rename/add
    or rename/rename(2to1) conflict), unpack_trees() removes the stage 0
    index entry for the path and just creates higher stage entries.

    HOWEVER, if files can be implicitly renamed to a path that didn't
    exist on either side of the merge (such as from directory rename
    detection), then merge-recursive can see two conflicting files at the
    same location, despite unpack_trees() having left the path at stage
    0.

  * merge-recursive is traditionally thought of as doing a 3-way merge.
    But what it really is forced to do is more of a 4-way merge; a good
    chunk of its annoying complexity is based around this (undocumented
    and unfortunate) reality.  It derives from what I consider a simple
    design flaw.

  * In order to get the 4-way merge right (i.e. avoiding spurious error
    messages and taking care to not overwrite important dirty or
    untracked files), we MUST handle the working copy BEFORE updating the
    index.

The combination of these four items in aggregate answers how we get a
stage 0 file that we want to remove from the working copy, but leaves two
questions -- what do I mean by 4-way merge, and why does the working copy
have to be updated before the index to get that merge right?  Since those
are crucial to understanding this bug, let me begin by explaining the
4-way merge:

The recursive merge strategy is built on first running unpack_trees() and
then "fixing up" the parts it can't resolve.  unpack_trees() does three
things

  * Check whether any untracked or dirty (not-uptodate) files would be
    overwritten by the merge.
  * Update the index AND working tree for trivial cases
  * Store conflicts as higher order stages in the index for later steps
    (e.g. merge-recursive.c) to resolve.

Note that unpack_trees() doesn't understand renames, thus its checks for
whether a dirty or untracked file would be overwritten by the merge is
going to have both false positives and false negatives.  For false
positives, see testcase 10e of the new t6043 introduced in the in-flight
en/rename-directory-detection series.  For false negatives, see commit
30fd3a5 (merge overwrites unstaged changes in renamed file, 2012-04-15),
and most testcases in sections 10 and 11 of the new t6043 introduced in the
en/rename-directory-detection series.

The false positive cannot be fixed with the current design; unpack_trees()
simply aborts early in some highly uncommon cases.

The false negatives cannot be fixed either, but they can be worked around;
fundamentally, it is too late to "abort the merge early" with an error
message, because unpack_trees() already wrote lots of changes to the
working copy for all the trivial merge cases and thus aborting would mean
being left with a dirty working copy.  Since it can't abort early, the code
instead needs to consider what untracked or dirty files might exist in the
working copy and take care to not overwrite them, essentially forcing us to
not only consider HEAD, the merge branch, and the merge base, but also the
working copy as a fourth set of content we need to interact with.  (It
could be worse, though.  If not for merge's check that the index matches
HEAD and aborting early if they don't, we could have been forced to deal
with a 5-way merge.)  The workarounds for false negatives take the form of
calling the would_lose_untracked() and was_dirty() functions (the latter of
which was added in the en/rename-directory-detection series to fix
overwriting dirty files involved in both normal and directory renames).

That brings us to our final loose end -- why does the working copy have to
be updated before the index?  The short answer is that
would_lose_untracked() and was_dirty() both rely on information in the
index in order to do their work.  The current index has information copied
from the original index by unpack_trees() that we need in these functions.
Since unpack_trees() discards the original index before returning, the
current index is our one source for this information, so we need to be
careful not to discard it until after we have handled the working copy.

And it may be important to point out that discarding the information in the
index before updating the working copy is an easy mistake to make that is
painful to debug.  This is evidenced by the existence of commit f53d39778
(merge-recursive: Fix spurious 'refusing to lose untracked file...'
messages, 2011-08-11), which added a big comment at the beginning of
update_stages() pointing out the perils of trying to update the stages in
the index before updating the working copy.  In fact, despite adding that
big comment, I hit the same kind of problem again later and added two more
very similar large warnings to the top of the conflict_rename_rename_2to1()
and apply_directory_rename_modifications() functions in the
en/rename-directory-detection series.

To try to recap, 4-way merge is a pain.  It has always been a pain as
evidenced by commits like
  * f53d39778 (merge-recursive: Fix spurious 'refusing to lose untracked
    file...' messages, 2011)
  * 30fd3a5 (merge overwrites unstaged changes in renamed file, 2012)
but it becomes even more so with additional features and requirements like
case-insensitive filesystems and directory rename detection.  4-way merges
simply cause the complexity to increase with every new capability.

The cleanest fix would be to switch to a 3-way index-only merge (making
unpack_trees() completely ignore the working copy, and making most of
merge-recursive do the same), then checking for untracked or dirty
working tree files in the way of the merge, then adding code that allows
us to update the working copy from one index to a new index.  That new
update code would be very similar to checkout, except that the new index
might have conflicts, and the new update may need to be supplemented with
additional info in order to correctly report various special conflict
cases such as rename/rename(2to1) or rename/add).

But such a large rewrite is a big task.  In the mean time, fix the
ignore_case code.  Allow it to continue rejecting the removal of files
that differ in case only, but only allow it to reject such removals.

 merge-recursive.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Sidenote: I built this commit on master, but it cleanly cherry-picks to
maint, to next, and to pu.

diff --git a/merge-recursive.c b/merge-recursive.c
index b48b15a6f..100fb913f 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -646,7 +646,7 @@ static int remove_file(struct merge_options *o, int clean,
 		if (ignore_case) {
 			struct cache_entry *ce;
 			ce = cache_file_exists(path, strlen(path), ignore_case);
-			if (ce && ce_stage(ce) == 0)
+			if (ce && ce_stage(ce) == 0 && strcmp(path, ce->name))
 				return 0;
 		}
 		if (remove_path(path))
-- 
2.11.0