git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Elijah Newren <newren@gmail.com>
Date
Sep 20, 2010, 08:28 UTC
Message-ID
<1284971350-30590-1-git-send-email-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:
Show 13 quoted lines
> 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
Next: Elijah Newren
Message 1 of 46 in “Audit and fix corner case bugs in recursive merge”
  1. 00/37 Audit and fix corner case bugs in recursive mergeElijah Newren, Sep 20, 2010
  2. 01/37 t3030: Add a testcase for resolvable rename/add conflict with symlinksElijah Newren, Sep 20, 2010
  3. Johannes SixtSep 20, 2010
  4. Jakub NarebskiSep 20, 2010
  5. 02/37 merge-recursive: Restructure showing how to chain more process_* functionsElijah Newren, Sep 20, 2010
  6. 03/37 t6032: Add a test checking for excessive output from mergeElijah Newren, Sep 20, 2010
  7. 04/37 t6022: Add test combinations of {content conflict?, D/F conflict remains?}Elijah Newren, Sep 20, 2010
  8. 05/37 t6022: Add tests for reversing order of merges when D/F conflicts presentElijah Newren, Sep 20, 2010
  9. 06/37 t6022: Add tests with both rename source & dest involved in D/F conflictsElijah Newren, Sep 20, 2010
  10. 07/37 t6022: Add paired rename+D/F conflict: (two/file, one/file) -> (one, two)Elijah Newren, Sep 20, 2010
  11. 08/37 t6022: Add tests for rename/rename combined with D/F conflictsElijah Newren, Sep 20, 2010
  12. 09/37 t6020: Modernize style a bitElijah Newren, Sep 20, 2010
  13. Johannes SixtSep 20, 2010
  14. Elijah NewrenSep 20, 2010
  15. Junio C HamanoSep 22, 2010
  16. Elijah NewrenSep 22, 2010
  17. 10/37 t6020: Add a testcase for modify/delete + directory/file conflictElijah Newren, Sep 20, 2010
  18. 11/37 t6036: Test index and worktree state, not just that merge failsElijah Newren, Sep 20, 2010
  19. 12/37 t6036: Add a second testcase similar to the first but with content changesElijah Newren, Sep 20, 2010
  20. 13/37 t6036: Add testcase for undetected conflictElijah Newren, Sep 20, 2010
  21. 14/37 merge-recursive: Small code clarification -- variable name and commentsElijah Newren, Sep 20, 2010
  22. 15/37 merge-recursive: Rename conflict_rename_rename*() for clarityElijah Newren, Sep 20, 2010
  23. 16/37 merge-recursive: Nuke rename/directory conflict detectionElijah Newren, Sep 20, 2010
  24. 17/37 merge-recursive: Move rename/delete handling into dedicated functionElijah Newren, Sep 20, 2010
  25. 18/37 merge-recursive: Move delete/modify handling into dedicated functionElijah Newren, Sep 20, 2010
  26. 19/37 merge-recursive: Move process_entry's content merging into a functionElijah Newren, Sep 20, 2010
  27. 20/37 merge-recursive: New data structures for deferring of D/F conflictsElijah Newren, Sep 20, 2010
  28. 21/37 merge-recursive: New function to assist resolving renames in-core onlyElijah Newren, Sep 20, 2010
  29. 22/37 merge-recursive: Have process_entry() skip D/F or rename entriesElijah Newren, Sep 20, 2010
  30. 23/37 merge-recursive: Structure process_df_entry() to handle more casesElijah Newren, Sep 20, 2010
  31. 24/37 merge-recursive: Update conflict_rename_rename_1to2() call signatureElijah Newren, Sep 20, 2010
  32. 25/37 merge-recursive: Update merge_content() call signatureElijah Newren, Sep 20, 2010
  33. 26/37 merge-recursive: Avoid doubly merging rename/add conflict contentsElijah Newren, Sep 20, 2010
  34. 27/37 merge-recursive: Move handling of double rename of one file to twoElijah Newren, Sep 20, 2010
  35. 28/37 merge-recursive: Move handling of double rename of one file to other fileElijah Newren, Sep 20, 2010
  36. 29/37 merge-recursive: Delay handling of rename/delete conflictsElijah Newren, Sep 20, 2010
  37. 30/37 merge-recursive: Delay content merging for renamesElijah Newren, Sep 20, 2010
  38. 31/37 merge-recursive: Delay modify/delete conflicts if D/F conflict presentElijah Newren, Sep 20, 2010
  39. 32/37 conflict_rename_delete(): Check whether D/F conflicts are still presentElijah Newren, Sep 20, 2010
  40. 33/37 conflict_rename_rename_1to2(): Fix checks for presence of D/F conflictsElijah Newren, Sep 20, 2010
  41. 34/37 merge_content(): Check whether D/F conflicts are still presentElijah Newren, Sep 20, 2010
  42. 35/37 handle_delete_modify(): Check whether D/F conflicts are still presentElijah Newren, Sep 20, 2010
  43. 36/37 merge-recursive: Make room for directories in D/F conflictsElijah Newren, Sep 20, 2010
  44. Johannes SixtSep 20, 2010
  45. Elijah NewrenSep 20, 2010
  46. 37/37 merge-recursive: Remove redundant path clearing for D/F conflictsElijah Newren, Sep 20, 2010

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.