[PATCH 00/37] Audit and fix corner case bugs in recursive merge

[Elijah Newren <newren@gmail.com>]

I may want to add another test or two, and tweak some things here or
there, but I finally have this series working enough that others could
test or comment on it now...

This patch series serves as an audit and fix of a number of corner
case bugs in the recursive merge algorithm.  The initial thrust for
the audit came from this exchange (from
http://thread.gmane.org/gmane.comp.version-control.git/155770/focus=155917):

On Thu, Sep 9, 2010 at 6:26 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Elijah Newren <newren@gmail.com> writes:
>> ... git can't know that there's a conflict
>> until after it's tried resolving paths involving newsub/newfile to see if
>> they are still in the way at the end (and if newsub/newfile is not in the
>> way at the end, there should be no conflict at all, which did not hold with
>> git previously).
>
> I'll queue this patch to 'pu', but anybody who wrote the above to
> correctly arriave at the crux of the issue in his analysis would know that
> this is another band-aid on top of band-aid.  The approach merge-recursive
> takes to first grab the set of directories and files fundamentally is
> wrong---it should be resolving the paths in-core first and then look at
> the result to ignore a directory that has become empty.

Junio is right, of course -- on all counts.  Inspection of the current
band-aids shows that there are still a number of bugs in the recursive
merge algorithm in corner cases with renames and directory/file (D/F)
conflicts.  My investigation also turned up a bug not involving
renames but dealing with D/F conflicts in combination with
modify/delete conflicts.  I also happened to find a bug not involving
D/F conflicts where git could incorrectly resolve a merge involving
prior criss-cross merges (in some cases silently accepting one side of
the merge as the final resolution without detecting a relevant
conflict).

This patch series is predominantly about doing exactly as Junio
suggests: resolving paths in-core first and then looking at the result
to see if the D/F conflicts still have paths in the way of each other
at the end.  However, it also includes the creation of several
testcases showing how and where the current algorithm is insufficient,
and addresses the undetected merge conflict found as well.

This series is based on next as it modifies/builds-on en/rename-d-f;
it cannot be played directly on top of that series as it also depends
on ks/recursive-rename-add-identical from master.

This series also includes three patches previously posted on the list
but which have not yet been picked up in pu or elsewhere: One from
Junio to allow creation of new process_*() functions and modifying
process_df_entry() to work with such chaining, one from Ken Schalk to
add a testcase for resolving a rename/add conflict involving symlinks,
and a previous submission of mine to rename/clarify the 'stage'
variable in process_renames().

The series ended up being bigger than I realized when I started.
Also, since it's whole purpose is to handle corner cases, I know that
it may be harder to review than other series.  I've tried to break it
down to address that, but I'm not sure if I have split the patches too
finely or too coarsely, or whether I've added sufficient explanation.
Let me know.


Schalk, Ken (1):
  t3030: Add a testcase for resolvable rename/add conflict with
    symlinks

Junio C Hamano (1):
  merge-recursive: Restructure showing how to chain more process_*
    functions

Elijah Newren (35):
  t6032: Add a test checking for excessive output from merge
  t6022: Add test combinations of {content conflict?, D/F conflict
    remains?}
  t6022: Add tests for reversing order of merges when D/F conflicts
    present
  t6022: Add tests with both rename source & dest involved in D/F
    conflicts
  t6022: Add paired rename+D/F conflict: (two/file, one/file) -> (one,
    two)
  t6022: Add tests for rename/rename combined with D/F conflicts
  t6020: Modernize style a bit
  t6020: Add a testcase for modify/delete + directory/file conflict
  t6036: Test index and worktree state, not just that merge fails
  t6036: Add a second testcase similar to the first but with content
    changes
  t6036: Add testcase for undetected conflict

The above patches are all about adding testcases both to extend our
coverage of different cases, and to expose corner case bugs.

  merge-recursive: Small code clarification -- variable name and
    comments
  merge-recursive: Rename conflict_rename_rename*() for clarity
  merge-recursive: Nuke rename/directory conflict detection

These three patches are just small code cleanups.  No bug fixes yet.

  merge-recursive: Move rename/delete handling into dedicated function
  merge-recursive: Move delete/modify handling into dedicated function
  merge-recursive: Move process_entry's content merging into a function

These three patches are just moving code into functions which will
later be called from multiple places.  Still no bug fixes.

  merge-recursive: New data structures for deferring of D/F conflicts
  merge-recursive: New function to assist resolving renames in-core
    only
  merge-recursive: Have process_entry() skip D/F or rename entries
  merge-recursive: Structure process_df_entry() to handle more cases
  merge-recursive: Update conflict_rename_rename_1to2() call signature
  merge-recursive: Update merge_content() call signature

These patches introduce new data structures and update the call
signatures of various functions to make it so I can pass additional
D/F conflict information to them.  Still no bug fixes yet.

  merge-recursive: Avoid doubly merging rename/add conflict contents

This patch is for what I belive to be the most concerning of the
corner case bugs I found (since git will under some circumstances
create and report a clean merge when it should have detected a
conflict), and the only one that doesn't involve D/F conflicts.

  merge-recursive: Move handling of double rename of one file to two
  merge-recursive: Move handling of double rename of one file to other
    file
  merge-recursive: Delay handling of rename/delete conflicts
  merge-recursive: Delay content merging for renames
  merge-recursive: Delay modify/delete conflicts if D/F conflict
    present

These patches simply move anything related to D/F conflicts from
process_renames() and process_entry() into process_df_entry().  Just
moving the code without further changes already fixes a couple bugs.

  conflict_rename_delete(): Check whether D/F conflicts are still
    present
  conflict_rename_rename_1to2(): Fix checks for presence of D/F
    conflicts
  merge_content(): Check whether D/F conflicts are still present
  handle_delete_modify(): Check whether D/F conflicts are still present
  merge-recursive: Make room for directories in D/F conflicts

These patches are where the majority of the corner case bugs involving
D/F conflicts get fixed, now that the appropriate structure is in place.

  merge-recursive: Remove redundant path clearing for D/F conflicts

...and one final clean up patch, due to the fact that keeping all the
tests passing in intermediate commits meant using ad-hoc methods to
make room for directories in D/F conflicts.


 merge-recursive.c                 |  649 ++++++++++++++++++++++++-------------
 t/t3030-merge-recursive.sh        |   37 ++-
 t/t6020-merge-df.sh               |   82 ++++-
 t/t6022-merge-rename.sh           |  366 +++++++++++++++++++++
 t/t6032-merge-large-rename.sh     |   30 ++
 t/t6036-recursive-corner-cases.sh |  185 +++++++++++-
 6 files changed, 1108 insertions(+), 241 deletions(-)

-- 
1.7.3.271.g16009