[PATCH 00/48] Handling more corner cases in merge-recursive.c

[Elijah Newren <newren@gmail.com>]

Well, this took me a LOT longer than I expected, but I now have a
(monster) patch series designed to fix various corner cases in
merge-recursive.c.  For those waiting for the 1.7.6 freeze to end,
reading this patch series makes for some great mental gymnastics.  :-)

You might be surprised by just how corner cases we have and the types of
bugs that can be triggered (including deleting untracked files).  This
series includes testcases for the unnecessary file update issues[1]
triggered by my series from last fall[2] and also a testcase that had
been regressed by my earlier (and now reverted) bandaids designed to fix
the unnecessary file update issue[3] (to make sure we fix both those
issues).  The current series aims to fix these problems using the
strategy Junio outlined[4].  However, this series is about a lot more
than just those issues.

[1] http://thread.gmane.org/gmane.comp.version-control.git/167800
[2] http://thread.gmane.org/gmane.comp.version-control.git/156559
[3] http://thread.gmane.org/gmane.comp.version-control.git/172617
[4] http://thread.gmane.org/gmane.comp.version-control.git/169209

You can note that I did not fix all the testcases I added.  I consider
some cases either unfixable or not worth fixing (see [5] for mailing
list discussion about the main such case).

[5] http://thread.gmane.org/gmane.comp.version-control.git/157591

However, there is one large class of problems that I think is fixable,
I'm just not sure whether it is worth fixing.  git's rename detection
optimization of only considering files that exist on one side of the
diff but not the other causes issues with merges (undetected conflicts,
spurious conflicts, or merged cleanly but wrongly due to deleting files
that should be present).  To fix these cases, we would need some way of
including rewritten files as potential rename candidates, meaning we
would also need to somehow check for rewritten files.  (I refer to these
as rename/add-source situations).  The potential problem with applying
such a fix is that it could make merges significantly more costly in the
common case, in order to fix some relatively rare problems that might
occur.  I don't know whether it is justified, especially since git's
merging can't be expected to know how to merge everything; at some point
the user is responsible for checking the result.  Patch 32 does add some
comments to the code if anyone does decide they want to look into this,
though.

Please test!  I apologize for the earlier regressions I caused in
merge-recursive.  I've tried to be MUCH more careful this time, but the
changes are numerous and much more invasive too.  I'm trying to put this
series through the testing wringer and will continue to do so, but extra
testing from others would be great.

Anyway, if you've read this far...thanks!  



Elijah Newren (48):

In patches 1-12, I add a bunch of corner case tests.  Since there are so
many I want to add and I think putting them all in t6036 would be a bit
unwieldy, I split the tests.  Since t6036 currently only contains
testcases that involve criss-cross merges, I mark it for such usage, and
create t6039 for dealing with corner cases involving renames without
criss-cross merges.

  [01] t6039: Add a testcase where git deletes an untracked file
  [02] t6039: Add failing testcase for rename/modify/add-source conflict
  [03] t6039: Add a pair of cases where undetected renames cause issues
  [04] t6039: Add a testcase where undetected rename causes silent file deletion
  [05] t6039: Add tests for content issues with modify/rename/directory conflicts
  [06] t6039: Add failing testcases for rename/rename/add-{source,dest} conflicts
  [07] t6039: Ensure rename/rename conflicts leave index and workdir in sane state
  [08] t6036: Add differently resolved modify/delete conflict in criss-cross test
  [09] t6036: criss-cross with weird content can fool git into clean merge
  [10] t6036: tests for criss-cross merges with various directory/file conflicts
  [11] t6036: criss-cross w/ rename/rename(1to2)/modify+rename/rename(2to1)/modify
  [12] t6036: criss-cross + rename/rename(1to2)/add-source + modify/modify

In patches 13-14, I add two tests that Junio reverted from master
(6db41050) which we would still like fixed, and a test that my previous
band-aids had broken to make sure we don't break it again.

  [13] t6022: Remove unnecessary untracked files to make test cleaner
  [14] t6022: New tests checking for unnecessary updates of files
  [15] t6022: Add testcase for merging a renamed file with a simple change

In patches 16-19, I'm just doing minor cleanups.  None of these are
critical; I'll be happy to drop any of them.

  [16] merge-recursive: Make BUG message more legible by adding a newline
  [17] merge-recursive: Correct a comment
  [18] merge-recursive: Mark some diff_filespec struct arguments const
  [19] merge-recursive: Remember to free generated unique path names

Patches 20-22 are small but important bug fixes.  Some of these might
make sense to be pulled to maint independent of the other changes.

  [20] merge-recursive: Avoid working directory changes during recursive case
  [21] merge-recursive: Fix recursive case with D/F conflict via add/add conflict
  [22] merge-recursive: Fix sorting order and directory change assumptions

Patches 23-29 are where I try to implement what I understood Junio
wanted merge-recursive to do to avoid so many lstat() and other
unnecessary working directory changes (see link [4] above).

  [23] merge-recursive: Fix code checking for D/F conflicts still being present
  [24] merge-recursive: Save D/F conflict filenames instead of unlinking them
  [25] merge-recursive: Split was_tracked() out of would_lose_untracked()
  [26] merge-recursive: Allow make_room_for_path() to remove D/F entries
  [27] merge-recursive: Consolidate different update_stages functions
  [28] merge-recursive: Split update_stages_and_entry; only update stages at end
  [29] merge-recursive: When we detect we can skip an update, actually skip it

Patch 30 fixes the deletion of an untracked file; I believe it has the
highest ratio of commit message length to patch size, since it has to
explain why we have modified a certain line of code several times and
still didn't have it quite right.

  [30] merge-recursive: Fix deletion of untracked file in rename/delete conflicts

The commit message for patch 31 seems like there's some good zombie joke
in there that someone cleverer than myself ought to be able to come up
with.  Interestingly, our code for rename/rename (2to1) conflicts was
never executed, and would trigger segfaults had there been a way to
execute it.

  [31] merge-recursive: Make dead code for rename/rename(2to1) conflicts undead

There are a few cases where git's rename detection optimization of only
considering files that exist on one side of the diff but not the other
causes issues with merges (undetected conflicts, spurious conflicts, or
merged cleanly but wrongly due to deleting files that should be
present).  To fix these cases, we would need some way of including
rewritten files as potential rename candidates, meaning we would also
need to somehow check for rewritten files.  My series does not address
these cases (I'm unsure whether the performance hit would be worth it).
Instead, I simply have a half-dozen relevant test cases and add some
comments to the code about some things that would need to be considered
if we ever want to tackle these cases.

  [32] merge-recursive: Add comments about handling rename/add-source cases

Patch 33 was specifically written because of a rename/directory conflict
testcase, but tries to worry about three-way content merges in
combination with renames and D/F conflicts and possible criss-cross
merges and getting the appropriate index and working directory contents.

  [33] merge-recursive: Improve handling of rename target vs. directory addition

Patch 34 is an attempted simplification of merge-recursive.c.  We really
don't need process_df_entry(), since we can simply iterate through the
unmerged entries in the order we need.  That can make it easier to keep
track of things, which is particularly important for the rename/rename
fixes below...

  [34] merge-recursive: Consolidate process_entry() and process_df_entry()

Patches 35-48 try to fix our handling of rename/rename conflicts (both
one file being renamed to two or two files being renamed to one).  In
such cases, we need to consider that the renames may not be the only
change; there could also be modifications requiring a three-way content
merge.  Further, as with all other rename cases, we need to consider the
recursive case (o->call_depth > 0) and potential D/F conflicts.  There
is also the possibility of rename/add-source issues for each side of the
rename, though we currently can't detect those anyway.  The
rename_rename_1to2 case is especially interesting, as we also have to
worry about each rename potentially also being involved in rename/delete
and rename/add-dest conflicts.  This all makes handling rename/rename
conflicts a bit hairy.

  [35] merge-recursive: Cleanup and consolidation of rename_conflict_info
  [36] merge-recursive: Provide more info in conflict markers with file renames
  [37] merge-recursive: Fix modify/delete resolution in the recursive case
  [38] merge-recursive: Introduce a merge_file convenience function
  [39] merge-recursive: Fix rename/rename(1to2) resolution for virtual merge base
  [40] merge-recursive: Small cleanups for conflict_rename_rename_1to2
  [41] merge-recursive: Defer rename/rename(2to1) handling until process_entry
  [42] merge-recursive: Record more data needed for merging with dual renames
  [43] merge-recursive: Create function for merging with branchname:file markers
  [44] merge-recursive: Consider modifications in rename/rename(2to1) conflicts
  [45] merge-recursive: Make modify/delete handling code reusable
  [46] merge-recursive: Have conflict_rename_delete reuse modify/delete code
  [47] merge-recursive: add handling for rename/rename/add-dest/add-dest
  [48] merge-recursive: Fix working copy handling for rename/rename/add/add

 merge-recursive.c                    |  985 +++++++++++++++++++++-------------
 merge-recursive.h                    |    1 +
 t/t6020-merge-df.sh                  |   26 +-
 t/t6022-merge-rename.sh              |  102 ++++-
 t/t6036-recursive-corner-cases.sh    |  502 ++++++++++++++++-
 t/t6039-merge-rename-corner-cases.sh |  556 +++++++++++++++++++
 6 files changed, 1752 insertions(+), 420 deletions(-)
 create mode 100755 t/t6039-merge-rename-corner-cases.sh

-- 
1.7.6.rc0.62.g2d69f