[PATCHv2 00/57] Re-roll of en/merge-recursive from pu

[PATCHv2 00/57] Re-roll of en/merge-recursive from pu

[Elijah Newren]

This is a re-roll of en/merge-recursive from pu, fixing half a dozen
bugs (some pre-existing ones, some caused by my first series).

I think the series is now ready for wide consumption and should be
safe for the upcoming release, particularly due to some heavy
additional testing I performed.  If others disagree, I'm fine and can
wait out another release cycle.  Either way, I am open for suggestions
or ideas on additional testing people would like to see if they have
worries about the robustness of these changes.


*** Heavy additional testing I performed ***

Because it's so hard to rule out regressions with so many changes to a
complicated portion of the code (though hopefully it is less complicated
now), and because we've had multiple problems in the past with the
changes I've been making to merge-recursive, I came up with an idea to
test this series more thoroughly.  So, I wrote a script to take every
single merge commit in git.git that had exactly two parents (no octopus
merges) and redid them both with /usr/bin/git and the version of git
from this series.  I checked to ensure that the two different versions
of git:
  (a) EITHER both failed to merge cleanly OR both merged cleanly
AND
  (b) the output of 'git ls-tree -r HEAD' matched between the two

I ran this process with the original version of the series and indeed
found that my original series mis-merged half a dozen or so merges (out
of about 5000).

With this new version of the series, I get no such mis-merges, which
gives me relatively strong confidence that there are no merge
regressions relative to git-1.7.4.4 (the version I happened to have in
/usr/bin).

*** What's fixed ***

Everything that I claimed the original series fixed, is still fixed in
this series.

This series fixes the following bugs from the previous series:
  * The mis-merge that Junio reported (which would have been found had I
    been more thorough in the new testcases I myself had added -- oops)
  * The windows bug identified by Johannes (at least I hope I fixed that
    one -- I'll need him to verify)
  * The potential incorrect deletion of a path that I reported (while
    discussing the patch that Johannes flagged for other reasons)
  * A fix to my more detailed conflict markers when renames are involved
    (it sometimes swapped filenames between branches)

This series also fixes the following bugs that exist in current git and
had not been fixed by my previous series:
  * The incorrectly-deleted file in the created virtual merge base problem
    that Junio identified when rename/rename(1to2) conflicts also involved
    rename/add-dest conflicts for one or more of the two renames.  [That's
    a mouthful, isn't it?]
  * Sometimes git would erroneously print 'refusing to lose untracked file...'
    warning messages.
  * There are three more cases where files were needlessly getting rewritten
    despite already having the correct contents (though none of these
    cases involved content merges).

The fixes to problems in the original series were made as modifications to
the relevant patches.  The new fixes were simply added to the end of the
series, in order to facilitate review.

*** What's changed ***

I took the series with Junio's modifications in pu, and made changes as
necessary to address his comments and other problems that were found.  I
have left his signed-off-by on patches where no changes were made.  Most
patches were unchanged; the full list of changed patches are:

  [05] t6042: Add tests for content issues with modify/rename/directory conflicts
    Changes: Fleshed out the commit message

  [07] t6042: Ensure rename/rename conflicts leave index and workdir in sane state
    Changes: Move this patch prior to the previous one (as suggested by
             Junio), since it has a simpler rename/rename(1to2) case in
             it.  (Did not remove Junio's s-o-b, since this was a
             trivial test-reorder change.)

  [08] t6036: Add differently resolved modify/delete conflict in criss-cross test
    Changes: Made wording change suggested by Junio.  (Did not remove
             Junio's s-o-b, since I took his exact suggestion.)

  [10] t6036: tests for criss-cross merges with various directory/file conflicts
    Changes: Lots of wording cleanups and making the tests more thorough

  [11] t6036: criss-cross w/ rename/rename(1to2)/modify+rename/rename(2to1)/modify
    Changes: More thorough testing of result, usage of some of Junio's
             wording in a comment

  [12] t6036: criss-cross + rename/rename(1to2)/add-source + modify/modify
    Changes: More thorough testing of result, improvement on wording describing test

  [15] t6022: Add testcase for merging a renamed file with a simple change
    Changes: Fix to check actual result is correct; that would have caught the
             bug Junio instead found the hard way.

  [19] merge-recursive: Consolidate different update_stages functions
    Changes: Moved earlier in the series, as per Junio's request; used
             to be patch number 27.  (Did not remove Junio's s-o-b,
             since no significant changes were necessary.)

  [23] merge-recursive: Fix sorting order and directory change assumptions
    Changes: Mentioned Johannes' squashed-in changes and added his
             signed-off-by from his squashed-in patch.  (Did not remove
             Junio's s-o-b, since he had added his to Johannes' patch.)

  [27] string-list: Add API to remove an item from an unsorted list
    Changes: This is an entirely new patch, recently submitted to the list by
             Johannes.

  [28] merge-recursive: Allow make_room_for_path() to remove D/F entries
    Changes: (1) Made use of Johannes' new string-list API to remove
             items we have already checked in order to avoid trying to
             unlink a path more than once, (2) fixed bug with not
             checking that basepath was directory

  [36] merge-recursive: Provide more info in conflict markers with file renames
    Changes: Fix bug where I could get filenames from two branches reversed

  
  [37] merge-recursive: When we detect we can skip an update, actually skip it
    Changes: Moved to later in the series (used to be patch #29).  Also,
             changed the "was_tracked" logic to use information about
             what paths were involved in renames to determine whether
             the file really 'was tracked' before the merge started.
             Also, added another minor tweak to get the expected
             "Skipped" messages that t6022.12 expects.

  [51-56]
    These are entirely new patches providing testcases and fixes for
    bugs that exist with current git and were not fixed in my previous
    series (but probably should have been).

*** What is still missing ***

Two things:
  * Junio had a great suggestion about alternate handling of the index in the
    case of rename/rename(2to1) and directory/file conflicts (just rename the
    entry in the index to match how we are renaming in the working copy to
    some new unique name, in order to allow 'git diff' to provide more useful
    information to the user).  Just didn't get to it.
  * Support for running break detection in diffs, in order to fix the testcase
    corrected by Peff in this series.  Simply didn't get around to it either.
Neither of these two things represent regressions relative to what is in
current releases of git, however.

*** Full patch list and diffstat ***

Elijah Newren (54):
  [01] t6042: Add a testcase where git deletes an untracked file
  [02] t6042: Add failing testcase for rename/modify/add-source conflict
  [03] t6042: Add a pair of cases where undetected renames cause issues
  [04] t6042: Add a testcase where undetected rename causes silent file deletion
  [05] t6042: Add tests for content issues with modify/rename/directory conflicts
  [06] t6042: Ensure rename/rename conflicts leave index and workdir in sane state
  [07] t6042: Add failing testcases for rename/rename/add-{source,dest} conflicts
  [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
  [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
  [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: Consolidate different update_stages functions
  [20] merge-recursive: Remember to free generated unique path names
  [21] merge-recursive: Avoid working directory changes during recursive case
  [22] merge-recursive: Fix recursive case with D/F conflict via add/add conflict
  [23] merge-recursive: Fix sorting order and directory change assumptions
  [24] merge-recursive: Fix code checking for D/F conflicts still being present
  [25] merge-recursive: Save D/F conflict filenames instead of unlinking them
  [26] merge-recursive: Split was_tracked() out of would_lose_untracked()
  [28] merge-recursive: Allow make_room_for_path() to remove D/F entries
  [29] merge-recursive: Split update_stages_and_entry; only update stages at end
  [30] merge-recursive: Fix deletion of untracked file in rename/delete conflicts
  [31] merge-recursive: Make dead code for rename/rename(2to1) conflicts undead
  [32] merge-recursive: Add comments about handling rename/add-source cases
  [33] merge-recursive: Improve handling of rename target vs. directory addition
  [34] merge-recursive: Consolidate process_entry() and process_df_entry()
  [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: When we detect we can skip an update, actually skip it
  [38] merge-recursive: Fix modify/delete resolution in the recursive case
  [39] merge-recursive: Introduce a merge_file convenience function
  [40] merge-recursive: Fix rename/rename(1to2) resolution for virtual merge base
  [41] merge-recursive: Small cleanups for conflict_rename_rename_1to2
  [42] merge-recursive: Defer rename/rename(2to1) handling until process_entry
  [43] merge-recursive: Record more data needed for merging with dual renames
  [44] merge-recursive: Create function for merging with branchname:file markers
  [45] merge-recursive: Consider modifications in rename/rename(2to1) conflicts
  [46] merge-recursive: Make modify/delete handling code reusable
  [47] merge-recursive: Have conflict_rename_delete reuse modify/delete code
  [48] merge-recursive: add handling for rename/rename/add-dest/add-dest
  [49] merge-recursive: Fix working copy handling for rename/rename/add/add
  [51] t6022: Add testcase for spurious "refusing to lose untracked" messages
  [52] merge-recursive: Fix spurious 'refusing to lose untracked file...' messages
  [53] t6022: Additional tests checking for unnecessary updates of files
  [54] merge-recursive: Avoid unnecessary file rewrites
  [55] t6042: Add testcase demonstrating missing file in virtual merge base
  [56] merge-recursive: Fix virtual merge base for rename/rename(1to2)/add-dest

Jeff King (1):
  [50] t3030: fix accidental success in symlink rename

Johannes Sixt (1):
  [27] string-list: Add API to remove an item from an unsorted list

 Documentation/technical/api-string-list.txt |   10 +
 merge-recursive.c                           | 1067 +++++++++++++++++----------
 merge-recursive.h                           |    1 +
 string-list.c                               |    9 +
 string-list.h                               |    1 +
 t/t3030-merge-recursive.sh                  |    7 +-
 t/t6020-merge-df.sh                         |   26 +-
 t/t6022-merge-rename.sh                     |  291 +++++++-
 t/t6036-recursive-corner-cases.sh           |  598 ++++++++++++++-
 t/t6042-merge-rename-corner-cases.sh        |  625 ++++++++++++++++
 10 files changed, 2207 insertions(+), 428 deletions(-)
 create mode 100755 t/t6042-merge-rename-corner-cases.sh

-- 
1.7.6.100.gac5c1

[PATCHv2 01/56] t6042: Add a testcase where git deletes an untracked file

[Elijah Newren]

Current git will nuke an untracked file during a rename/delete conflict if
(a) there is an untracked file whose name matches the source of a rename
and (b) the merge is done in a certain direction.  Add a simple testcase
demonstrating this bug.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6036-recursive-corner-cases.sh    |    2 +-
 t/t6042-merge-rename-corner-cases.sh |   36 ++++++++++++++++++++++++++++++++++
 2 files changed, 37 insertions(+), 1 deletions(-)
 create mode 100755 t/t6042-merge-rename-corner-cases.sh

diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 871577d..319b6fa 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -1,6 +1,6 @@
 #!/bin/sh
 
-test_description='recursive merge corner cases'
+test_description='recursive merge corner cases involving criss-cross merges'
 
 . ./test-lib.sh
 
diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
new file mode 100755
index 0000000..5054459
--- /dev/null
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -0,0 +1,36 @@
+#!/bin/sh
+
+test_description="recursive merge corner cases w/ renames but not criss-crosses"
+# t6036 has corner cases that involve both criss-cross merges and renames
+
+. ./test-lib.sh
+
+test_expect_success 'setup rename/delete + untracked file' '
+	echo "A pretty inscription" >ring &&
+	git add ring &&
+	test_tick &&
+	git commit -m beginning &&
+
+	git branch people &&
+	git checkout -b rename-the-ring &&
+	git mv ring one-ring-to-rule-them-all &&
+	test_tick &&
+	git commit -m fullname &&
+
+	git checkout people &&
+	git rm ring &&
+	echo gollum >owner &&
+	git add owner &&
+	test_tick &&
+	git commit -m track-people-instead-of-objects &&
+	echo "Myyy PRECIOUSSS" >ring
+'
+
+test_expect_failure "Does git preserve Gollum's precious artifact?" '
+	test_must_fail git merge -s recursive rename-the-ring &&
+
+	# Make sure git did not delete an untracked file
+	test -f ring
+'
+
+test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 02/56] t6042: Add failing testcase for rename/modify/add-source conflict

[Elijah Newren]

If there is a cleanly resolvable rename/modify conflict AND there is a new
file introduced on the renamed side of the merge whose name happens to
match that of the source of the rename (but is otherwise unrelated to the
rename), then git fails to cleanly resolve the merge despite the fact that
the new file should not cause any problems.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6042-merge-rename-corner-cases.sh |   39 ++++++++++++++++++++++++++++++++++
 1 files changed, 39 insertions(+), 0 deletions(-)

diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 5054459..276d7dd 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -33,4 +33,43 @@ test_expect_failure "Does git preserve Gollum's precious artifact?" '
 	test -f ring
 '
 
+# Testcase setup for rename/modify/add-source:
+#   Commit A: new file: a
+#   Commit B: modify a slightly
+#   Commit C: rename a->b, add completely different a
+#
+# We should be able to merge B & C cleanly
+
+test_expect_success 'setup rename/modify/add-source conflict' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n6\n7\n" >a &&
+	git add a &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	echo 8 >>a &&
+	git add a &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv a b &&
+	echo something completely different >a &&
+	git add a &&
+	git commit -m C
+'
+
+test_expect_failure 'rename/modify/add-source conflict resolvable' '
+	git checkout B^0 &&
+
+	git merge -s recursive C^0 &&
+
+	test $(git rev-parse B:a) = $(git rev-parse b) &&
+	test $(git rev-parse C:a) = $(git rev-parse a)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 03/56] t6042: Add a pair of cases where undetected renames cause issues

[Elijah Newren]

An undetected rename can cause a silent success where a conflict should
have been detected, or can cause an erroneous conflict state where the
merge should have been resolvable.  Add testcases for both.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6042-merge-rename-corner-cases.sh |   61 ++++++++++++++++++++++++++++++++++
 1 files changed, 61 insertions(+), 0 deletions(-)

diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 276d7dd..f338fb4 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -72,4 +72,65 @@ test_expect_failure 'rename/modify/add-source conflict resolvable' '
 	test $(git rev-parse C:a) = $(git rev-parse a)
 '
 
+test_expect_success 'setup resolvable conflict missed if rename missed' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n" >a &&
+	echo foo >b &&
+	git add a b &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a c &&
+	echo "Completely different content" >a &&
+	git add a &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	echo 6 >>a &&
+	git add a &&
+	git commit -m C
+'
+
+test_expect_failure 'conflict caused if rename not detected' '
+	git checkout -q C^0 &&
+	git merge -s recursive B^0 &&
+
+	test 3 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test 6 -eq $(wc -l < c) &&
+	test $(git rev-parse HEAD:a) = $(git rev-parse B:a) &&
+	test $(git rev-parse HEAD:b) = $(git rev-parse A:b)
+'
+
+test_expect_success 'setup conflict resolved wrong if rename missed' '
+	git reset --hard &&
+	git clean -f &&
+
+	git checkout -b D A &&
+	echo 7 >>a &&
+	git add a &&
+	git mv a c &&
+	echo "Completely different content" >a &&
+	git add a &&
+	git commit -m D &&
+
+	git checkout -b E A &&
+	git rm a &&
+	echo "Completely different content" >>a &&
+	git add a &&
+	git commit -m E
+'
+
+test_expect_failure 'missed conflict if rename not detected' '
+	git checkout -q E^0 &&
+	test_must_fail git merge -s recursive D^0
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 04/56] t6042: Add a testcase where undetected rename causes silent file deletion

[Elijah Newren]

There are cases where history should merge cleanly, and which current git
does merge cleanly despite not detecting a rename; however the merge
currently nukes files that should not be removed.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6042-merge-rename-corner-cases.sh |   65 ++++++++++++++++++++++++++++++++++
 1 files changed, 65 insertions(+), 0 deletions(-)

diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index f338fb4..db5560c 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -133,4 +133,69 @@ test_expect_failure 'missed conflict if rename not detected' '
 	test_must_fail git merge -s recursive D^0
 '
 
+# Tests for undetected rename/add-source causing a file to erroneously be
+# deleted (and for mishandled rename/rename(1to1) causing the same issue).
+#
+# This test uses a rename/rename(1to1)+add-source conflict (1to1 means the
+# same file is renamed on both sides to the same thing; it should trigger
+# the 1to2 logic, which it would do if the add-source didn't cause issues
+# for git's rename detection):
+#   Commit A: new file: a
+#   Commit B: rename a->b
+#   Commit C: rename a->b, add unrelated a
+
+test_expect_success 'setup undetected rename/add-source causes data loss' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n" >a &&
+	git add a &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv a b &&
+	echo foobar >a &&
+	git add a &&
+	git commit -m C
+'
+
+test_expect_failure 'detect rename/add-source and preserve all data' '
+	git checkout B^0 &&
+
+	git merge -s recursive C^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 2 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test -f a &&
+	test -f b &&
+
+	test $(git rev-parse HEAD:b) = $(git rev-parse A:a) &&
+	test $(git rev-parse HEAD:a) = $(git rev-parse C:a)
+'
+
+test_expect_failure 'detect rename/add-source and preserve all data, merge other way' '
+	git checkout C^0 &&
+
+	git merge -s recursive B^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 2 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test -f a &&
+	test -f b &&
+
+	test $(git rev-parse HEAD:b) = $(git rev-parse A:a) &&
+	test $(git rev-parse HEAD:a) = $(git rev-parse C:a)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 05/56] t6042: Add tests for content issues with modify/rename/directory conflicts

[Elijah Newren]

Add testcases that cover a variety of merge issues with files being
renamed and modified on different sides of history, when there are
directories possibly conflicting with the rename location.

Case 1:
On one side of history, a file is modified and a new directory is added.
On the other side of history, the file is modified in a non-conflicting
way but is renamed to the location of the new directory.

Case 2:
[Same as case 1, but there is also a content conflict.  In detail:]
On one side of history, a file is modified and a new directory is added.
On the other side of history, the file is modified in a conflicting way
and it is renamed to the location of the new directory.

Case 3:
[Similar to case 1, but the "conflicting" directory is the directory
where the file original resided.  In detail:]
On one side of history, a file is modified.  On the other side of history,
the file is modified in a non-conflicting way, but the directory it was
under is removed and the file is renamed to the location of the directory
it used to reside in (i.e. 'sub/file' gets renamed to 'sub').  This is
flagged as a directory/rename conflict, but should be able to be resolved
since the directory can be cleanly removed by the merge.

One branch renames a file and makes a file where the directory the renamed
file used to be in, and the other branch updates the file in
place. Merging them should resolve it cleanly as long as the content level
change on the branches do not overlap and rename is detected, or should
leave conflict without losing information.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1: New and improved commit message.

 t/t6042-merge-rename-corner-cases.sh |  141 ++++++++++++++++++++++++++++++++++
 1 files changed, 141 insertions(+), 0 deletions(-)

diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index db5560c..b465667 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -198,4 +198,145 @@ test_expect_failure 'detect rename/add-source and preserve all data, merge other
 	test $(git rev-parse HEAD:a) = $(git rev-parse C:a)
 '
 
+test_expect_success 'setup content merge + rename/directory conflict' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n6\n" >file &&
+	git add file &&
+	test_tick &&
+	git commit -m base &&
+	git tag base &&
+
+	git checkout -b right &&
+	echo 7 >>file &&
+	mkdir newfile &&
+	echo junk >newfile/realfile &&
+	git add file newfile/realfile &&
+	test_tick &&
+	git commit -m right &&
+
+	git checkout -b left-conflict base &&
+	echo 8 >>file &&
+	git add file &&
+	git mv file newfile &&
+	test_tick &&
+	git commit -m left &&
+
+	git checkout -b left-clean base &&
+	echo 0 >newfile &&
+	cat file >>newfile &&
+	git add newfile &&
+	git rm file &&
+	test_tick &&
+	git commit -m left
+'
+
+test_expect_failure 'rename/directory conflict + clean content merge' '
+	git reset --hard &&
+	git reset --hard &&
+	git clean -fdqx &&
+
+	git checkout left-clean^0 &&
+
+	test_must_fail git merge -s recursive right^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 1 -eq $(git ls-files -u | wc -l) &&
+	test 1 -eq $(git ls-files -o | wc -l) &&
+
+	echo 0 >expect &&
+	git cat-file -p base:file >>expect &&
+	echo 7 >>expect &&
+	test_cmp expect newfile~HEAD &&
+
+	test $(git rev-parse :2:newfile) = $(git hash-object expect) &&
+
+	test -f newfile/realfile &&
+	test -f newfile~HEAD
+'
+
+test_expect_failure 'rename/directory conflict + content merge conflict' '
+	git reset --hard &&
+	git reset --hard &&
+	git clean -fdqx &&
+
+	git checkout left-conflict^0 &&
+
+	test_must_fail git merge -s recursive right^0 &&
+
+	test 4 -eq $(git ls-files -s | wc -l) &&
+	test 3 -eq $(git ls-files -u | wc -l) &&
+	test 1 -eq $(git ls-files -o | wc -l) &&
+
+	git cat-file -p left-conflict:newfile >left &&
+	git cat-file -p base:file    >base &&
+	git cat-file -p right:file   >right &&
+	test_must_fail git merge-file \
+		-L "HEAD:newfile" \
+		-L "" \
+		-L "right^0:file" \
+		left base right &&
+	test_cmp left newfile~HEAD &&
+
+	test $(git rev-parse :1:newfile) = $(git rev-parse base:file) &&
+	test $(git rev-parse :2:newfile) = $(git rev-parse left-conflict:newfile) &&
+	test $(git rev-parse :3:newfile) = $(git rev-parse right:file) &&
+
+	test -f newfile/realfile &&
+	test -f newfile~HEAD
+'
+
+test_expect_success 'setup content merge + rename/directory conflict w/ disappearing dir' '
+	git reset --hard &&
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	mkdir sub &&
+	printf "1\n2\n3\n4\n5\n6\n" >sub/file &&
+	git add sub/file &&
+	test_tick &&
+	git commit -m base &&
+	git tag base &&
+
+	git checkout -b right &&
+	echo 7 >>sub/file &&
+	git add sub/file &&
+	test_tick &&
+	git commit -m right &&
+
+	git checkout -b left base &&
+	echo 0 >newfile &&
+	cat sub/file >>newfile &&
+	git rm sub/file &&
+	mv newfile sub &&
+	git add sub &&
+	test_tick &&
+	git commit -m left
+'
+
+test_expect_success 'disappearing dir in rename/directory conflict handled' '
+	git reset --hard &&
+	git clean -fdqx &&
+
+	git checkout left^0 &&
+
+	git merge -s recursive right^0 &&
+
+	test 1 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	echo 0 >expect &&
+	git cat-file -p base:sub/file >>expect &&
+	echo 7 >>expect &&
+	test_cmp expect sub &&
+
+	test -f sub
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 06/56] t6042: Ensure rename/rename conflicts leave index and workdir in sane state

[Elijah Newren]

rename/rename conflicts, both with one file being renamed to two different
files and with two files being renamed to the same file, should leave the
index and the working copy in a sane state with appropriate conflict
recording, auxiliary files, etc.  Git seems to handle one of the two cases
alright, but has some problems with the two files being renamed to one
case.  Add tests for both cases.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6042-merge-rename-corner-cases.sh |  102 ++++++++++++++++++++++++++++++++++
 1 files changed, 102 insertions(+), 0 deletions(-)

diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index b465667..371fb39 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -339,4 +339,106 @@ test_expect_success 'disappearing dir in rename/directory conflict handled' '
 	test -f sub
 '
 
+# Test for all kinds of things that can go wrong with rename/rename (2to1):
+#   Commit A: new files: a & b
+#   Commit B: rename a->c, modify b
+#   Commit C: rename b->c, modify a
+#
+# Merging of B & C should NOT be clean.  Questions:
+#   * Both a & b should be removed by the merge; are they?
+#   * The two c's should contain modifications to a & b; do they?
+#   * The index should contain two files, both for c; does it?
+#   * The working copy should have two files, both of form c~<unique>; does it?
+#   * Nothing else should be present.  Is anything?
+
+test_expect_success 'setup rename/rename (2to1) + modify/modify' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n" >a &&
+	printf "5\n4\n3\n2\n1\n" >b &&
+	git add a b &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a c &&
+	echo 0 >>b &&
+	git add b &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv b c &&
+	echo 6 >>a &&
+	git add a &&
+	git commit -m C
+'
+
+test_expect_failure 'handle rename/rename (2to1) conflict correctly' '
+	git checkout B^0 &&
+
+	test_must_fail git merge -s recursive C^0 >out &&
+	grep "CONFLICT (rename/rename)" out &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 2 -eq $(git ls-files -u | wc -l) &&
+	test 2 -eq $(git ls-files -u c | wc -l) &&
+	test 3 -eq $(git ls-files -o | wc -l) &&
+
+	test ! -f a &&
+	test ! -f b &&
+	test -f c~HEAD &&
+	test -f c~C^0 &&
+
+	test $(git hash-object c~HEAD) = $(git rev-parse C:a) &&
+	test $(git hash-object c~C^0) = $(git rev-parse B:b)
+'
+
+# Testcase setup for simple rename/rename (1to2) conflict:
+#   Commit A: new file: a
+#   Commit B: rename a->b
+#   Commit C: rename a->c
+test_expect_success 'setup simple rename/rename (1to2) conflict' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	echo stuff >a &&
+	git add a &&
+	test_tick &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	test_tick &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv a c &&
+	test_tick &&
+	git commit -m C
+'
+
+test_expect_success 'merge has correct working tree contents' '
+	git checkout C^0 &&
+
+	test_must_fail git merge -s recursive B^0 &&
+
+	test 3 -eq $(git ls-files -s | wc -l) &&
+	test 3 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse :1:a) = $(git rev-parse A:a) &&
+	test $(git rev-parse :3:b) = $(git rev-parse A:a) &&
+	test $(git rev-parse :2:c) = $(git rev-parse A:a) &&
+
+	test ! -f a &&
+	test $(git hash-object b) = $(git rev-parse A:a) &&
+	test $(git hash-object c) = $(git rev-parse A:a)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 07/56] t6042: Add failing testcases for rename/rename/add-{source,dest} conflicts

[Elijah Newren]

Add testcases that cover three failures with current git merge, all
involving renaming one file on both sides of history:

Case 1:
If a single file is renamed to two different filenames on different sides
of history, there should be a conflict.  Adding a new file on one of those
sides of history whose name happens to match the rename source should not
cause the merge to suddenly succeed.

Case 2:
If a single file is renamed on both sides of history but renamed
identically, there should not be a conflict.  This works fine.  However,
if one of those sides also added a new file that happened to match the
rename source, then that file should be left alone.  Currently, the
rename/rename conflict handling causes that new file to become untracked.

Case 3:
If a single file is renamed to two different filenames on different sides
of history, there should be a conflict.  This works currently.  However,
if those renames also involve rename/add conflicts (i.e. there are new
files on one side of history that match the destination of the rename of
the other side of history), then the resulting conflict should be recorded
in the index, showing that there were multiple files with a given filename.
Currently, git silently discards one of file versions.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
Changes since v1: moved this patch (and its content) prior to the
  patch it used to follow (as suggested by Junio), since it has a
  simpler rename/rename(1to2) case in it.

 t/t6042-merge-rename-corner-cases.sh |  125 ++++++++++++++++++++++++++++++++++
 1 files changed, 125 insertions(+), 0 deletions(-)

diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 371fb39..427fe1c 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -441,4 +441,129 @@ test_expect_success 'merge has correct working tree contents' '
 	test $(git hash-object c) = $(git rev-parse A:a)
 '
 
+# Testcase setup for rename/rename(1to2)/add-source conflict:
+#   Commit A: new file: a
+#   Commit B: rename a->b
+#   Commit C: rename a->c, add completely different a
+#
+# Merging of B & C should NOT be clean; there's a rename/rename conflict
+
+test_expect_success 'setup rename/rename(1to2)/add-source conflict' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n6\n7\n" >a &&
+	git add a &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv a c &&
+	echo something completely different >a &&
+	git add a &&
+	git commit -m C
+'
+
+test_expect_failure 'detect conflict with rename/rename(1to2)/add-source merge' '
+	git checkout B^0 &&
+
+	test_must_fail git merge -s recursive C^0 &&
+
+	test 4 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse 3:a) = $(git rev-parse C:a) &&
+	test $(git rev-parse 1:a) = $(git rev-parse A:a) &&
+	test $(git rev-parse 2:b) = $(git rev-parse B:b) &&
+	test $(git rev-parse 3:c) = $(git rev-parse C:c) &&
+
+	test -f a &&
+	test -f b &&
+	test -f c
+'
+
+test_expect_success 'setup rename/rename(1to2)/add-source resolvable conflict' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	>a &&
+	git add a &&
+	test_tick &&
+	git commit -m base &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	test_tick &&
+	git commit -m one &&
+
+	git checkout -b C A &&
+	git mv a b &&
+	echo important-info >a &&
+	git add a &&
+	test_tick &&
+	git commit -m two
+'
+
+test_expect_failure 'rename/rename/add-source still tracks new a file' '
+	git checkout C^0 &&
+	git merge -s recursive B^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse HEAD:a) = $(git rev-parse C:a) &&
+	test $(git rev-parse HEAD:b) = $(git rev-parse A:a)
+'
+
+test_expect_success 'setup rename/rename(1to2)/add-dest conflict' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	echo stuff >a &&
+	git add a &&
+	test_tick &&
+	git commit -m base &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	echo precious-data >c &&
+	git add c &&
+	test_tick &&
+	git commit -m one &&
+
+	git checkout -b C A &&
+	git mv a c &&
+	echo important-info >b &&
+	git add b &&
+	test_tick &&
+	git commit -m two
+'
+
+test_expect_failure 'rename/rename/add-dest merge still knows about conflicting file versions' '
+	git checkout C^0 &&
+	test_must_fail git merge -s recursive B^0 &&
+
+	test 5 -eq $(git ls-files -s | wc -l) &&
+	test 2 -eq $(git ls-files -u b | wc -l) &&
+	test 2 -eq $(git ls-files -u c | wc -l) &&
+
+	test $(git rev-parse :1:a) = $(git rev-parse A:a) &&
+	test $(git rev-parse :2:b) = $(git rev-parse C:b) &&
+	test $(git rev-parse :3:b) = $(git rev-parse B:b) &&
+	test $(git rev-parse :2:c) = $(git rev-parse C:c) &&
+	test $(git rev-parse :3:c) = $(git rev-parse B:c)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 08/56] t6036: Add differently resolved modify/delete conflict in criss-cross test

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
Changes since v1: Made wording change suggested by Junio.

 t/t6036-recursive-corner-cases.sh |   83 +++++++++++++++++++++++++++++++++++++
 1 files changed, 83 insertions(+), 0 deletions(-)

diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 319b6fa..90b50bb 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -231,4 +231,87 @@ test_expect_success 'git detects differently handled merges conflict' '
 	test $(git rev-parse :1:new_a) = $(git hash-object merged)
 '
 
+#
+# criss-cross + modify/delete:
+#
+#      B   D
+#      o---o
+#     / \ / \
+#  A o   X   ? F
+#     \ / \ /
+#      o---o
+#      C   E
+#
+#   Commit A: file with contents 'A\n'
+#   Commit B: file with contents 'B\n'
+#   Commit C: file not present
+#   Commit D: file with contents 'B\n'
+#   Commit E: file not present
+#
+# Merging commits D & E should result in modify/delete conflict.
+
+test_expect_success 'setup criss-cross + modify/delete resolved differently' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	echo A >file &&
+	git add file &&
+	test_tick &&
+	git commit -m A &&
+
+	git branch B &&
+	git checkout -b C &&
+	git rm file &&
+	test_tick &&
+	git commit -m C &&
+
+	git checkout B &&
+	echo B >file &&
+	git add file &&
+	test_tick &&
+	git commit -m B &&
+
+	git checkout B^0 &&
+	test_must_fail git merge C &&
+	echo B >file &&
+	git add file &&
+	test_tick &&
+	git commit -m D &&
+	git tag D &&
+
+	git checkout C^0 &&
+	test_must_fail git merge B &&
+	git rm file &&
+	test_tick &&
+	git commit -m E &&
+	git tag E
+'
+
+test_expect_failure 'git detects conflict merging criss-cross+modify/delete' '
+	git checkout D^0 &&
+
+	test_must_fail git merge -s recursive E^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 2 -eq $(git ls-files -u | wc -l) &&
+
+	test $(git rev-parse :1:file) = $(git rev-parse master:file) &&
+	test $(git rev-parse :2:file) = $(git rev-parse B:file)
+'
+
+test_expect_failure 'git detects conflict merging criss-cross+modify/delete, reverse direction' '
+	git reset --hard &&
+	git checkout E^0 &&
+
+	test_must_fail git merge -s recursive D^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 2 -eq $(git ls-files -u | wc -l) &&
+
+	test $(git rev-parse :1:file) = $(git rev-parse master:file) &&
+	test $(git rev-parse :3:file) = $(git rev-parse B:file)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 09/56] t6036: criss-cross with weird content can fool git into clean merge

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6036-recursive-corner-cases.sh |   83 +++++++++++++++++++++++++++++++++++++
 1 files changed, 83 insertions(+), 0 deletions(-)

diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 90b50bb..991c56d 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -314,4 +314,87 @@ test_expect_failure 'git detects conflict merging criss-cross+modify/delete, rev
 	test $(git rev-parse :3:file) = $(git rev-parse B:file)
 '
 
+#
+# criss-cross + modify/modify with very contrived file contents:
+#
+#      B   D
+#      o---o
+#     / \ / \
+#  A o   X   ? F
+#     \ / \ /
+#      o---o
+#      C   E
+#
+#   Commit A: file with contents 'A\n'
+#   Commit B: file with contents 'B\n'
+#   Commit C: file with contents 'C\n'
+#   Commit D: file with contents 'D\n'
+#   Commit E: file with contents:
+#      <<<<<<< Temporary merge branch 1
+#      C
+#      =======
+#      B
+#      >>>>>>> Temporary merge branch 2
+#
+# Now, when we merge commits D & E, does git detect the conflict?
+
+test_expect_success 'setup differently handled merges of content conflict' '
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	echo A >file &&
+	git add file &&
+	test_tick &&
+	git commit -m A &&
+
+	git branch B &&
+	git checkout -b C &&
+	echo C >file &&
+	git add file &&
+	test_tick &&
+	git commit -m C &&
+
+	git checkout B &&
+	echo B >file &&
+	git add file &&
+	test_tick &&
+	git commit -m B &&
+
+	git checkout B^0 &&
+	test_must_fail git merge C &&
+	echo D >file &&
+	git add file &&
+	test_tick &&
+	git commit -m D &&
+	git tag D &&
+
+	git checkout C^0 &&
+	test_must_fail git merge B &&
+	cat <<EOF >file &&
+<<<<<<< Temporary merge branch 1
+C
+=======
+B
+>>>>>>> Temporary merge branch 2
+EOF
+	git add file &&
+	test_tick &&
+	git commit -m E &&
+	git tag E
+'
+
+test_expect_failure 'git detects conflict w/ criss-cross+contrived resolution' '
+	git checkout D^0 &&
+
+	test_must_fail git merge -s recursive E^0 &&
+
+	test 3 -eq $(git ls-files -s | wc -l) &&
+	test 3 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse :2:file) = $(git rev-parse D:file) &&
+	test $(git rev-parse :3:file) = $(git rev-parse E:file)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 10/56] t6036: tests for criss-cross merges with various directory/file conflicts

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1: Lots of wording cleanups, made the tests more thorough.

 t/t6036-recursive-corner-cases.sh |  159 +++++++++++++++++++++++++++++++++++++
 1 files changed, 159 insertions(+), 0 deletions(-)

diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 991c56d..acff84d 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -4,6 +4,12 @@ test_description='recursive merge corner cases involving criss-cross merges'
 
 . ./test-lib.sh
 
+get_clean_checkout () {
+	git reset --hard &&
+	git clean -fdqx &&
+	git checkout "$1"
+}
+
 #
 #  L1  L2
 #   o---o
@@ -397,4 +403,157 @@ test_expect_failure 'git detects conflict w/ criss-cross+contrived resolution' '
 	test $(git rev-parse :3:file) = $(git rev-parse E:file)
 '
 
+#
+# criss-cross + d/f conflict via add/add:
+#   Commit A: Neither file 'a' nor directory 'a/' exist.
+#   Commit B: Introduce 'a'
+#   Commit C: Introduce 'a/file'
+#   Commit D: Merge B & C, keeping 'a' and deleting 'a/'
+#
+# Two different later cases:
+#   Commit E1: Merge B & C, deleting 'a' but keeping 'a/file'
+#   Commit E2: Merge B & C, deleting 'a' but keeping a slightly modified 'a/file'
+#
+#      B   D
+#      o---o
+#     / \ / \
+#  A o   X   ? F
+#     \ / \ /
+#      o---o
+#      C   E1 or E2
+#
+# Merging D & E1 requires we first create a virtual merge base X from
+# merging A & B in memory.  Now, if X could keep both 'a' and 'a/file' in
+# the index, then the merge of D & E1 could be resolved cleanly with both
+# 'a' and 'a/file' removed.  Since git does not currently allow creating
+# such a tree, the best we can do is have X contain both 'a~<unique>' and
+# 'a/file' resulting in the merge of D and E1 having a rename/delete
+# conflict for 'a'.  (Although this merge appears to be unsolvable with git
+# currently, git could do a lot better than it currently does with these
+# d/f conflicts, which is the purpose of this test.)
+#
+# Merge of D & E2 has similar issues for path 'a', but should always result
+# in a modify/delete conflict for path 'a/file'.
+#
+# We run each merge in both directions, to check for directional issues
+# with D/F conflict handling.
+#
+
+test_expect_success 'setup differently handled merges of directory/file conflict' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	>ignore-me &&
+	git add ignore-me &&
+	test_tick &&
+	git commit -m A &&
+	git tag A &&
+
+	git branch B &&
+	git checkout -b C &&
+	mkdir a &&
+	echo 10 >a/file &&
+	git add a/file &&
+	test_tick &&
+	git commit -m C &&
+
+	git checkout B &&
+	echo 5 >a &&
+	git add a &&
+	test_tick &&
+	git commit -m B &&
+
+	git checkout B^0 &&
+	test_must_fail git merge C &&
+	git clean -f &&
+	rm -rf a/ &&
+	echo 5 >a &&
+	git add a &&
+	test_tick &&
+	git commit -m D &&
+	git tag D &&
+
+	git checkout C^0 &&
+	test_must_fail git merge B &&
+	git clean -f &&
+	git rm --cached a &&
+	echo 10 >a/file &&
+	git add a/file &&
+	test_tick &&
+	git commit -m E1 &&
+	git tag E1 &&
+
+	git checkout C^0 &&
+	test_must_fail git merge B &&
+	git clean -f &&
+	git rm --cached a &&
+	printf "10\n11\n" >a/file &&
+	git add a/file &&
+	test_tick &&
+	git commit -m E2 &&
+	git tag E2
+'
+
+test_expect_failure 'merge of D & E1 fails but has appropriate contents' '
+	get_clean_checkout D^0 &&
+
+	test_must_fail git merge -s recursive E1^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 1 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse :0:ignore-me) = $(git rev-parse A:ignore-me) &&
+	test $(git rev-parse :2:a) = $(git rev-parse B:a)
+'
+
+test_expect_failure 'merge of E1 & D fails but has appropriate contents' '
+	get_clean_checkout E1^0 &&
+
+	test_must_fail git merge -s recursive D^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 1 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse :0:ignore-me) = $(git rev-parse A:ignore-me) &&
+	test $(git rev-parse :3:a) = $(git rev-parse B:a)
+'
+
+test_expect_success 'merge of D & E2 fails but has appropriate contents' '
+	get_clean_checkout D^0 &&
+
+	test_must_fail git merge -s recursive E2^0 &&
+
+	test 4 -eq $(git ls-files -s | wc -l) &&
+	test 3 -eq $(git ls-files -u | wc -l) &&
+	test 1 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse :2:a) = $(git rev-parse B:a) &&
+	test $(git rev-parse :3:a/file) = $(git rev-parse E2:a/file) &&
+	test $(git rev-parse :1:a/file) = $(git rev-parse C:a/file) &&
+	test $(git rev-parse :0:ignore-me) = $(git rev-parse A:ignore-me) &&
+
+	test -f a~HEAD
+'
+
+test_expect_failure 'merge of E2 & D fails but has appropriate contents' '
+	get_clean_checkout E2^0 &&
+
+	test_must_fail git merge -s recursive D^0 &&
+
+	test 4 -eq $(git ls-files -s | wc -l) &&
+	test 3 -eq $(git ls-files -u | wc -l) &&
+	test 1 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse :3:a) = $(git rev-parse B:a) &&
+	test $(git rev-parse :2:a/file) = $(git rev-parse E2:a/file) &&
+	test $(git rev-parse :1:a/file) = $(git rev-parse C:a/file)
+	test $(git rev-parse :0:ignore-me) = $(git rev-parse A:ignore-me) &&
+
+	test -f a~D^0
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 11/56] t6036: criss-cross w/ rename/rename(1to2)/modify+rename/rename(2to1)/modify

[Elijah Newren]

This test is mostly just designed for testing optimality of the virtual
merge base in the event of a rename/rename(1to2) conflict.  The current
choice for resolving this in git seems somewhat confusing and suboptimal.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1: More thorough testing of results, usage of some of
  Junio's wording in a comment.

 t/t6036-recursive-corner-cases.sh |   88 +++++++++++++++++++++++++++++++++++++
 1 files changed, 88 insertions(+), 0 deletions(-)

diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index acff84d..38cace6 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -556,4 +556,92 @@ test_expect_failure 'merge of E2 & D fails but has appropriate contents' '
 	test -f a~D^0
 '
 
+#
+# criss-cross with rename/rename(1to2)/modify followed by
+# rename/rename(2to1)/modify:
+#
+#      B   D
+#      o---o
+#     / \ / \
+#  A o   X   ? F
+#     \ / \ /
+#      o---o
+#      C   E
+#
+#   Commit A: new file: a
+#   Commit B: rename a->b, modifying by adding a line
+#   Commit C: rename a->c
+#   Commit D: merge B&C, resolving conflict by keeping contents in newname
+#   Commit E: merge B&C, resolving conflict similar to D but adding another line
+#
+# There is a conflict merging B & C, but one of filename not of file
+# content.  Whoever created D and E chose specific resolutions for that
+# conflict resolution.  Now, since: (1) there is no content conflict
+# merging B & C, (2) D does not modify that merged content further, and (3)
+# both D & E resolve the name conflict in the same way, the modification to
+# newname in E should not cause any conflicts when it is merged with D.
+# (Note that this can be accomplished by having the virtual merge base have
+# the merged contents of b and c stored in a file named a, which seems like
+# the most logical choice anyway.)
+#
+# Comment from Junio: I do not necessarily agree with the choice "a", but
+# it feels sound to say "B and C do not agree what the final pathname
+# should be, but we know this content was derived from the common A:a so we
+# use one path whose name is arbitrary in the virtual merge base X between
+# D and E" and then further let the rename detection to notice that that
+# arbitrary path gets renamed between X-D to "newname" and X-E also to
+# "newname" to resolve it as both sides renaming it to the same new
+# name. It is akin to what we do at the content level, i.e. "B and C do not
+# agree what the final contents should be, so we leave the conflict marker
+# but that may cancel out at the final merge stage".
+
+test_expect_success 'setup rename/rename(1to2)/modify followed by what looks like rename/rename(2to1)/modify' '
+	git reset --hard &&
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n6\n" >a &&
+	git add a &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	echo 7 >>b &&
+	git add -u &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv a c &&
+	git commit -m C &&
+
+	git checkout -q B^0 &&
+	git merge --no-commit -s ours C^0 &&
+	git mv b newname &&
+	git commit -m "Merge commit C^0 into HEAD" &&
+	git tag D &&
+
+	git checkout -q C^0 &&
+	git merge --no-commit -s ours B^0 &&
+	git mv c newname &&
+	printf "7\n8\n" >>newname &&
+	git add -u &&
+	git commit -m "Merge commit B^0 into HEAD" &&
+	git tag E
+'
+
+test_expect_failure 'handle rename/rename(1to2)/modify followed by what looks like rename/rename(2to1)/modify' '
+	git checkout D^0 &&
+
+	git merge -s recursive E^0 &&
+
+	test 1 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse HEAD:newname) = $(git rev-parse E:newname)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 12/56] t6036: criss-cross + rename/rename(1to2)/add-source + modify/modify

[Elijah Newren]

This is another challenging testcase trying to exercise the virtual merge
base creation in the rename/rename(1to2) code.  A testcase is added that
we should be able to merge cleanly, but which requires a virtual merge
base to be created that is aware of rename/rename(1to2)/add-source
conflicts and can handle those.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1: More thorough testing of results, improvement on
  wording in description of testcase.

 t/t6036-recursive-corner-cases.sh |   77 +++++++++++++++++++++++++++++++++++++
 1 files changed, 77 insertions(+), 0 deletions(-)

diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 38cace6..526a2ea 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -644,4 +644,81 @@ test_expect_failure 'handle rename/rename(1to2)/modify followed by what looks li
 	test $(git rev-parse HEAD:newname) = $(git rev-parse E:newname)
 '
 
+#
+# criss-cross with rename/rename(1to2)/add-source + resolvable modify/modify:
+#
+#      B   D
+#      o---o
+#     / \ / \
+#  A o   X   ? F
+#     \ / \ /
+#      o---o
+#      C   E
+#
+#   Commit A: new file: a
+#   Commit B: rename a->b
+#   Commit C: rename a->c, add different a
+#   Commit D: merge B&C, keeping b&c and (new) a modified at beginning
+#   Commit E: merge B&C, keeping b&c and (new) a modified at end
+#
+# Merging commits D & E should result in no conflict; doing so correctly
+# requires getting the virtual merge base (from merging B&C) right, handling
+# renaming carefully (both in the virtual merge base and later), and getting
+# content merge handled.
+
+test_expect_success 'setup criss-cross + rename/rename/add + modify/modify' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "lots\nof\nwords\nand\ncontent\n" >a &&
+	git add a &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv a c &&
+	printf "2\n3\n4\n5\n6\n7\n" >a &&
+	git add a &&
+	git commit -m C &&
+
+	git checkout B^0 &&
+	git merge --no-commit -s ours C^0 &&
+	git checkout C -- a c &&
+	mv a old_a &&
+	echo 1 >a &&
+	cat old_a >>a &&
+	rm old_a &&
+	git add -u &&
+	git commit -m "Merge commit C^0 into HEAD" &&
+	git tag D &&
+
+	git checkout C^0 &&
+	git merge --no-commit -s ours B^0 &&
+	git checkout B -- b &&
+	echo 8 >>a &&
+	git add -u &&
+	git commit -m "Merge commit B^0 into HEAD" &&
+	git tag E
+'
+
+test_expect_failure 'detect rename/rename/add-source for virtual merge-base' '
+	git checkout D^0 &&
+
+	git merge -s recursive E^0 &&
+
+	test 3 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse HEAD:b) = $(git rev-parse A:a) &&
+	test $(git rev-parse HEAD:c) = $(git rev-parse A:a) &&
+	test "$(cat a)" = "$(printf "1\n2\n3\n4\n5\n6\n7\n8\n")"
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 13/56] t6022: Remove unnecessary untracked files to make test cleaner

[Elijah Newren]

Since this test later does a git add -A, we should clean out unnecessary
untracked files as part of our cleanup.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6022-merge-rename.sh |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 1ed259d..1d1b32e 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -252,6 +252,7 @@ test_expect_success 'setup for rename + d/f conflicts' '
 	git reset --hard &&
 	git checkout --orphan dir-in-way &&
 	git rm -rf . &&
+	git clean -fdqx &&
 
 	mkdir sub &&
 	mkdir dir &&
-- 
1.7.6.100.gac5c1

[PATCHv2 14/56] t6022: New tests checking for unnecessary updates of files

[Elijah Newren]

This testcase was part of en/merge-recursive that was reverted in 6db4105
(Revert "Merge branch 'en/merge-recursive'" 2011-05-19).  While the other
changes in that series caused unfortunate breakage, this testcase is still
useful; reinstate it.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 t/t6022-merge-rename.sh |   63 +++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 63 insertions(+), 0 deletions(-)

diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 1d1b32e..11c5c60 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -610,4 +610,67 @@ test_expect_success 'check handling of differently renamed file with D/F conflic
 	! test -f original
 '
 
+test_expect_success 'setup avoid unnecessary update, normal rename' '
+	git reset --hard &&
+	git checkout --orphan avoid-unnecessary-update-1 &&
+	git rm -rf . &&
+	git clean -fdqx &&
+
+	printf "1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n" >original &&
+	git add -A &&
+	git commit -m "Common commmit" &&
+
+	git mv original rename &&
+	echo 11 >>rename &&
+	git add -u &&
+	git commit -m "Renamed and modified" &&
+
+	git checkout -b merge-branch-1 HEAD~1 &&
+	echo "random content" >random-file &&
+	git add -A &&
+	git commit -m "Random, unrelated changes"
+'
+
+test_expect_failure 'avoid unnecessary update, normal rename' '
+	git checkout -q avoid-unnecessary-update-1^0 &&
+	test-chmtime =1000000000 rename &&
+	test-chmtime -v +0 rename >expect &&
+	git merge merge-branch-1 &&
+	test-chmtime -v +0 rename >actual &&
+	test_cmp expect actual # "rename" should have stayed intact
+'
+
+test_expect_success 'setup to test avoiding unnecessary update, with D/F conflict' '
+	git reset --hard &&
+	git checkout --orphan avoid-unnecessary-update-2 &&
+	git rm -rf . &&
+	git clean -fdqx &&
+
+	mkdir df &&
+	printf "1\n2\n3\n4\n5\n6\n7\n8\n9\n10\n" >df/file &&
+	git add -A &&
+	git commit -m "Common commmit" &&
+
+	git mv df/file temp &&
+	rm -rf df &&
+	git mv temp df &&
+	echo 11 >>df &&
+	git add -u &&
+	git commit -m "Renamed and modified" &&
+
+	git checkout -b merge-branch-2 HEAD~1 &&
+	>unrelated-change &&
+	git add unrelated-change &&
+	git commit -m "Only unrelated changes"
+'
+
+test_expect_failure 'avoid unnecessary update, with D/F conflict' '
+	git checkout -q avoid-unnecessary-update-2^0 &&
+	test-chmtime =1000000000 df &&
+	test-chmtime -v +0 df >expect &&
+	git merge merge-branch-2 &&
+	test-chmtime -v +0 df >actual &&
+	test_cmp expect actual # "df" should have stayed intact
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 15/56] t6022: Add testcase for merging a renamed file with a simple change

[Elijah Newren]

This is a testcase that was broken by b2c8c0a (merge-recursive: When we
detect we can skip an update, actually skip it 2011-02-28) and fixed by
6db4105 (Revert "Merge branch 'en/merge-recursive'" 2011-05-19).  Include
this testcase to ensure we don't regress it again.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1: Check that the result of the merge is actually
  correct; had I done that in v1, I would have caught the bug that
  Junio found the hard way.

 t/t6022-merge-rename.sh |   27 +++++++++++++++++++++++++++
 1 files changed, 27 insertions(+), 0 deletions(-)

diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 11c5c60..6ff4bd2 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -673,4 +673,31 @@ test_expect_failure 'avoid unnecessary update, with D/F conflict' '
 	test_cmp expect actual # "df" should have stayed intact
 '
 
+test_expect_success 'setup merge of rename + small change' '
+	git reset --hard &&
+	git checkout --orphan rename-plus-small-change &&
+	git rm -rf . &&
+	git clean -fdqx &&
+
+	echo ORIGINAL >file &&
+	git add file &&
+
+	test_tick &&
+	git commit -m Initial &&
+	git checkout -b rename_branch &&
+	git mv file renamed_file &&
+	git commit -m Rename &&
+	git checkout rename-plus-small-change &&
+	echo NEW-VERSION >file &&
+	git commit -a -m Reformat
+'
+
+test_expect_success 'merge rename + small change' '
+	git merge rename_branch &&
+
+	test 1 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+	test $(git rev-parse HEAD:renamed_file) = $(git rev-parse HEAD~1:file)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 16/56] merge-recursive: Make BUG message more legible by adding a newline

[Elijah Newren]

Hopefully no one ever hits this error except when making large changes to
merge-recursive.c and debugging...

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index db9ba19..3fcd0a5 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -230,7 +230,7 @@ struct tree *write_tree_from_memory(struct merge_options *o)
 		for (i = 0; i < active_nr; i++) {
 			struct cache_entry *ce = active_cache[i];
 			if (ce_stage(ce))
-				fprintf(stderr, "BUG: %d %.*s", ce_stage(ce),
+				fprintf(stderr, "BUG: %d %.*s\n", ce_stage(ce),
 					(int)ce_namelen(ce), ce->name);
 		}
 		die("Bug in merge-recursive.c");
-- 
1.7.6.100.gac5c1

[PATCHv2 17/56] merge-recursive: Correct a comment

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 3fcd0a5..3d464d9 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1439,7 +1439,7 @@ static int process_df_entry(struct merge_options *o,
 		handle_delete_modify(o, path, new_path,
 				     a_sha, a_mode, b_sha, b_mode);
 	} else if (!o_sha && !!a_sha != !!b_sha) {
-		/* directory -> (directory, file) */
+		/* directory -> (directory, file) or <nothing> -> (directory, file) */
 		const char *add_branch;
 		const char *other_branch;
 		unsigned mode;
-- 
1.7.6.100.gac5c1

[PATCHv2 18/56] merge-recursive: Mark some diff_filespec struct arguments const

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   19 ++++++++++---------
 1 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 3d464d9..317bf23 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -461,9 +461,10 @@ static struct string_list *get_renames(struct merge_options *o,
 	return renames;
 }
 
-static int update_stages_options(const char *path, struct diff_filespec *o,
-			 struct diff_filespec *a, struct diff_filespec *b,
-			 int clear, int options)
+static int update_stages_options(const char *path, const struct diff_filespec *o,
+				 const struct diff_filespec *a,
+				 const struct diff_filespec *b,
+				 int clear, int options)
 {
 	if (clear)
 		if (remove_file_from_cache(path))
@@ -712,9 +713,9 @@ struct merge_file_info {
 
 static int merge_3way(struct merge_options *o,
 		      mmbuffer_t *result_buf,
-		      struct diff_filespec *one,
-		      struct diff_filespec *a,
-		      struct diff_filespec *b,
+		      const struct diff_filespec *one,
+		      const struct diff_filespec *a,
+		      const struct diff_filespec *b,
 		      const char *branch1,
 		      const char *branch2)
 {
@@ -772,9 +773,9 @@ static int merge_3way(struct merge_options *o,
 }
 
 static struct merge_file_info merge_file(struct merge_options *o,
-				         struct diff_filespec *one,
-					 struct diff_filespec *a,
-					 struct diff_filespec *b,
+					 const struct diff_filespec *one,
+					 const struct diff_filespec *a,
+					 const struct diff_filespec *b,
 					 const char *branch1,
 					 const char *branch2)
 {
-- 
1.7.6.100.gac5c1

[PATCHv2 19/56] merge-recursive: Consolidate different update_stages functions

[Elijah Newren]

We are only calling update_stages_options() one way really, so we can
consolidate the slightly different variants into one and remove some
parameters whose values are always the same.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
Changes since v1: This patch now appears much earlier in the series than before.

 merge-recursive.c |   27 +++++++++------------------
 1 files changed, 9 insertions(+), 18 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 317bf23..8a5c1a6 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -461,11 +461,12 @@ static struct string_list *get_renames(struct merge_options *o,
 	return renames;
 }
 
-static int update_stages_options(const char *path, const struct diff_filespec *o,
-				 const struct diff_filespec *a,
-				 const struct diff_filespec *b,
-				 int clear, int options)
+static int update_stages(const char *path, const struct diff_filespec *o,
+			 const struct diff_filespec *a,
+			 const struct diff_filespec *b)
 {
+	int clear = 1;
+	int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK;
 	if (clear)
 		if (remove_file_from_cache(path))
 			return -1;
@@ -481,14 +482,6 @@ static int update_stages_options(const char *path, const struct diff_filespec *o
 	return 0;
 }
 
-static int update_stages(const char *path, struct diff_filespec *o,
-			 struct diff_filespec *a, struct diff_filespec *b,
-			 int clear)
-{
-	int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_OK_TO_REPLACE;
-	return update_stages_options(path, o, a, b, clear, options);
-}
-
 static int update_stages_and_entry(const char *path,
 				   struct stage_data *entry,
 				   struct diff_filespec *o,
@@ -505,8 +498,7 @@ static int update_stages_and_entry(const char *path,
 	hashcpy(entry->stages[1].sha, o->sha1);
 	hashcpy(entry->stages[2].sha, a->sha1);
 	hashcpy(entry->stages[3].sha, b->sha1);
-	options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK;
-	return update_stages_options(path, o, a, b, clear, options);
+	return update_stages(path, o, a, b);
 }
 
 static int remove_file(struct merge_options *o, int clean,
@@ -862,8 +854,7 @@ static void conflict_rename_delete(struct merge_options *o,
 	if (!o->call_depth)
 		update_stages(dest_name, NULL,
 			      rename_branch == o->branch1 ? pair->two : NULL,
-			      rename_branch == o->branch1 ? NULL : pair->two,
-			      1);
+			      rename_branch == o->branch1 ? NULL : pair->two);
 	if (lstat(dest_name, &st) == 0 && S_ISDIR(st.st_mode)) {
 		dest_name = unique_path(o, dest_name, rename_branch);
 		df_conflict = 1;
@@ -907,8 +898,8 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 		 * update_file(o, 0, pair2->two->sha1, pair2->two->mode, dst_name2);
 		 */
 	} else {
-		update_stages(ren1_dst, NULL, pair1->two, NULL, 1);
-		update_stages(ren2_dst, NULL, NULL, pair2->two, 1);
+		update_stages(ren1_dst, NULL, pair1->two, NULL);
+		update_stages(ren2_dst, NULL, NULL, pair2->two);
 
 		update_file(o, 0, pair1->two->sha1, pair1->two->mode, dst_name1);
 		update_file(o, 0, pair2->two->sha1, pair2->two->mode, dst_name2);
-- 
1.7.6.100.gac5c1

[PATCHv2 20/56] merge-recursive: Remember to free generated unique path names

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   20 ++++++++++++--------
 1 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 8a5c1a6..b5a8f17 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1063,7 +1063,6 @@ static int process_renames(struct merge_options *o,
 				   renamed: clean merge */
 				update_file(o, 1, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
 			} else if (!sha_eq(dst_other.sha1, null_sha1)) {
-				const char *new_path;
 				clean_merge = 0;
 				try_merge = 1;
 				output(o, 1, "CONFLICT (rename/add): Rename %s->%s in %s. "
@@ -1092,9 +1091,10 @@ static int process_renames(struct merge_options *o,
 						    ren1_dst);
 					try_merge = 0;
 				} else {
-					new_path = unique_path(o, ren1_dst, branch2);
+					char *new_path = unique_path(o, ren1_dst, branch2);
 					output(o, 1, "Adding as %s instead", new_path);
 					update_file(o, 0, dst_other.sha1, dst_other.mode, new_path);
+					free(new_path);
 				}
 			} else if ((item = string_list_lookup(renames2Dst, ren1_dst))) {
 				ren2 = item->util;
@@ -1262,13 +1262,14 @@ static int merge_content(struct merge_options *o,
 	}
 
 	if (df_conflict_remains) {
-		const char *new_path;
+		char *new_path;
 		update_file_flags(o, mfi.sha, mfi.mode, path,
 				  o->call_depth || mfi.clean, 0);
 		new_path = unique_path(o, path, df_rename_conflict_branch);
 		mfi.clean = 0;
 		output(o, 1, "Adding as %s instead", new_path);
 		update_file_flags(o, mfi.sha, mfi.mode, new_path, 0, 1);
+		free(new_path);
 	} else {
 		update_file(o, mfi.clean, mfi.sha, mfi.mode, path);
 	}
@@ -1424,12 +1425,14 @@ static int process_df_entry(struct merge_options *o,
 		}
 	} else if (o_sha && (!a_sha || !b_sha)) {
 		/* Modify/delete; deleted side may have put a directory in the way */
-		const char *new_path = path;
-		if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode))
-			new_path = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
+		char *renamed = NULL;
+		if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
+			renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
+		}
 		clean_merge = 0;
-		handle_delete_modify(o, path, new_path,
+		handle_delete_modify(o, path, renamed ? renamed : path,
 				     a_sha, a_mode, b_sha, b_mode);
+		free(renamed);
 	} else if (!o_sha && !!a_sha != !!b_sha) {
 		/* directory -> (directory, file) or <nothing> -> (directory, file) */
 		const char *add_branch;
@@ -1452,12 +1455,13 @@ static int process_df_entry(struct merge_options *o,
 			conf = "directory/file";
 		}
 		if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
-			const char *new_path = unique_path(o, path, add_branch);
+			char *new_path = unique_path(o, path, add_branch);
 			clean_merge = 0;
 			output(o, 1, "CONFLICT (%s): There is a directory with name %s in %s. "
 			       "Adding %s as %s",
 			       conf, path, other_branch, path, new_path);
 			update_file(o, 0, sha, mode, new_path);
+			free(new_path);
 		} else {
 			output(o, 2, "Adding %s", path);
 			update_file(o, 1, sha, mode, path);
-- 
1.7.6.100.gac5c1

[PATCHv2 21/56] merge-recursive: Avoid working directory changes during recursive case

[Elijah Newren]

make_room_for_directories_of_df_conflicts() is about making sure necessary
working directory changes can succeed.  When o->call_depth > 0 (i.e. the
recursive case), we do not want to make any working directory changes so
this function should be skipped.

Note that make_room_for_directories_of_df_conflicts() is broken as has
been pointed out by Junio; it should NOT be unlinking files.  What it
should do is keep track of files that could be unlinked if a directory
later needs to be written in their place.  However, that work also is only
relevant in the non-recursive case, so this change is helpful either way.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index b5a8f17..8863b02 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -355,6 +355,13 @@ static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
 	int last_len = 0;
 	int i;
 
+	/*
+	 * If we're merging merge-bases, we don't want to bother with
+	 * any working directory changes.
+	 */
+	if (o->call_depth)
+		return;
+
 	for (i = 0; i < entries->nr; i++) {
 		const char *path = entries->items[i].string;
 		int len = strlen(path);
-- 
1.7.6.100.gac5c1

[PATCHv2 22/56] merge-recursive: Fix recursive case with D/F conflict via add/add conflict

[Elijah Newren]

When a D/F conflict is introduced via an add/add conflict, when
o->call_depth > 0 we need to ensure that the higher stage entry from the
base stage is removed.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                 |    2 ++
 t/t6036-recursive-corner-cases.sh |    4 ++--
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 8863b02..85620f7 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1468,6 +1468,8 @@ static int process_df_entry(struct merge_options *o,
 			       "Adding %s as %s",
 			       conf, path, other_branch, path, new_path);
 			update_file(o, 0, sha, mode, new_path);
+			if (o->call_depth)
+				remove_file_from_cache(path);
 			free(new_path);
 		} else {
 			output(o, 2, "Adding %s", path);
diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 526a2ea..ed6c6f4 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -509,7 +509,7 @@ test_expect_failure 'merge of D & E1 fails but has appropriate contents' '
 	test $(git rev-parse :2:a) = $(git rev-parse B:a)
 '
 
-test_expect_failure 'merge of E1 & D fails but has appropriate contents' '
+test_expect_success 'merge of E1 & D fails but has appropriate contents' '
 	get_clean_checkout E1^0 &&
 
 	test_must_fail git merge -s recursive D^0 &&
@@ -539,7 +539,7 @@ test_expect_success 'merge of D & E2 fails but has appropriate contents' '
 	test -f a~HEAD
 '
 
-test_expect_failure 'merge of E2 & D fails but has appropriate contents' '
+test_expect_success 'merge of E2 & D fails but has appropriate contents' '
 	get_clean_checkout E2^0 &&
 
 	test_must_fail git merge -s recursive D^0 &&
-- 
1.7.6.100.gac5c1

[PATCHv2 23/56] merge-recursive: Fix sorting order and directory change assumptions

[Elijah Newren]

We cannot assume that directory/file conflicts will appear in sorted
order; for example, 'letters.txt' comes between 'letters' and
'letters/file'.

Thanks to Johannes for a pointer about qsort stability issues with
Windows and suggested code change.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Johannes Sixt <j6t@kdbg.org>
---
Changes since v1: Mentioned Johannes' pointer and squashed in his
  patch that Junio had appended to the end of the en/merge-recursive
  series.  Added his s-o-b because of that.

 merge-recursive.c   |   40 +++++++++++++++++++++++++++++++++++-----
 t/t6020-merge-df.sh |   26 ++++++++++++++++++--------
 2 files changed, 53 insertions(+), 13 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 85620f7..76b895f 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -333,6 +333,37 @@ static struct string_list *get_unmerged(void)
 	return unmerged;
 }
 
+static int string_list_df_name_compare(const void *a, const void *b)
+{
+	const struct string_list_item *one = a;
+	const struct string_list_item *two = b;
+	int onelen = strlen(one->string);
+	int twolen = strlen(two->string);
+	/*
+	 * Here we only care that entries for D/F conflicts are
+	 * adjacent, in particular with the file of the D/F conflict
+	 * appearing before files below the corresponding directory.
+	 * The order of the rest of the list is irrelevant for us.
+	 *
+	 * To achieve this, we sort with df_name_compare and provide
+	 * the mode S_IFDIR so that D/F conflicts will sort correctly.
+	 * We use the mode S_IFDIR for everything else for simplicity,
+	 * since in other cases any changes in their order due to
+	 * sorting cause no problems for us.
+	 */
+	int cmp = df_name_compare(one->string, onelen, S_IFDIR,
+				  two->string, twolen, S_IFDIR);
+	/*
+	 * Now that 'foo' and 'foo/bar' compare equal, we have to make sure
+	 * that 'foo' comes before 'foo/bar'.
+	 */
+	if (cmp)
+		return cmp;
+	return onelen - twolen;
+}
+
+
+
 static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
 						      struct string_list *entries)
 {
@@ -345,11 +376,6 @@ static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
 	 * otherwise, if the file is not supposed to be removed by the
 	 * merge, the contents of the file will be placed in another
 	 * unique filename.
-	 *
-	 * NOTE: This function relies on the fact that entries for a
-	 * D/F conflict will appear adjacent in the index, with the
-	 * entries for the file appearing before entries for paths
-	 * below the corresponding directory.
 	 */
 	const char *last_file = NULL;
 	int last_len = 0;
@@ -362,6 +388,10 @@ static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
 	if (o->call_depth)
 		return;
 
+	/* Ensure D/F conflicts are adjacent in the entries list. */
+	qsort(entries->items, entries->nr, sizeof(*entries->items),
+	      string_list_df_name_compare);
+
 	for (i = 0; i < entries->nr; i++) {
 		const char *path = entries->items[i].string;
 		int len = strlen(path);
diff --git a/t/t6020-merge-df.sh b/t/t6020-merge-df.sh
index eec8f4e..27c3d73 100755
--- a/t/t6020-merge-df.sh
+++ b/t/t6020-merge-df.sh
@@ -59,15 +59,19 @@ test_expect_success 'setup modify/delete + directory/file conflict' '
 	git add letters &&
 	git commit -m initial &&
 
+	# Throw in letters.txt for sorting order fun
+	# ("letters.txt" sorts between "letters" and "letters/file")
 	echo i >>letters &&
-	git add letters &&
+	echo "version 2" >letters.txt &&
+	git add letters letters.txt &&
 	git commit -m modified &&
 
 	git checkout -b delete HEAD^ &&
 	git rm letters &&
 	mkdir letters &&
 	>letters/file &&
-	git add letters &&
+	echo "version 1" >letters.txt &&
+	git add letters letters.txt &&
 	git commit -m deleted
 '
 
@@ -75,25 +79,31 @@ test_expect_success 'modify/delete + directory/file conflict' '
 	git checkout delete^0 &&
 	test_must_fail git merge modify &&
 
-	test 3 = $(git ls-files -s | wc -l) &&
-	test 2 = $(git ls-files -u | wc -l) &&
-	test 1 = $(git ls-files -o | wc -l) &&
+	test 5 -eq $(git ls-files -s | wc -l) &&
+	test 4 -eq $(git ls-files -u | wc -l) &&
+	test 1 -eq $(git ls-files -o | wc -l) &&
 
 	test -f letters/file &&
+	test -f letters.txt &&
 	test -f letters~modify
 '
 
 test_expect_success 'modify/delete + directory/file conflict; other way' '
+	# Yes, we really need the double reset since "letters" appears as
+	# both a file and a directory.
+	git reset --hard &&
 	git reset --hard &&
 	git clean -f &&
 	git checkout modify^0 &&
+
 	test_must_fail git merge delete &&
 
-	test 3 = $(git ls-files -s | wc -l) &&
-	test 2 = $(git ls-files -u | wc -l) &&
-	test 1 = $(git ls-files -o | wc -l) &&
+	test 5 -eq $(git ls-files -s | wc -l) &&
+	test 4 -eq $(git ls-files -u | wc -l) &&
+	test 1 -eq $(git ls-files -o | wc -l) &&
 
 	test -f letters/file &&
+	test -f letters.txt &&
 	test -f letters~HEAD
 '
 
-- 
1.7.6.100.gac5c1

[PATCHv2 24/56] merge-recursive: Fix code checking for D/F conflicts still being present

[Elijah Newren]

Previously, we were using lstat() to determine if a directory was still
present after a merge (and thus in the way of adding a file).  We should
have been using lstat() only to determine if untracked directories were in
the way (and then only when necessary to check for untracked directories);
we should instead using the index to determine if there is a tracked
directory in the way.  Create a new function to do this and use it to
replace the existing checks for directories being in the way.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   49 ++++++++++++++++++++++++++++++++++---------------
 1 files changed, 34 insertions(+), 15 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 76b895f..9aacf5e 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -593,6 +593,30 @@ static void flush_buffer(int fd, const char *buf, unsigned long size)
 	}
 }
 
+static int dir_in_way(const char *path, int check_working_copy)
+{
+	int pos, pathlen = strlen(path);
+	char *dirpath = xmalloc(pathlen + 2);
+	struct stat st;
+
+	strcpy(dirpath, path);
+	dirpath[pathlen] = '/';
+	dirpath[pathlen+1] = '\0';
+
+	pos = cache_name_pos(dirpath, pathlen+1);
+
+	if (pos < 0)
+		pos = -1 - pos;
+	if (pos < active_nr &&
+	    !strncmp(dirpath, active_cache[pos]->name, pathlen+1)) {
+		free(dirpath);
+		return 1;
+	}
+
+	free(dirpath);
+	return check_working_copy && !lstat(path, &st) && S_ISDIR(st.st_mode);
+}
+
 static int would_lose_untracked(const char *path)
 {
 	int pos = cache_name_pos(path, strlen(path));
@@ -882,7 +906,6 @@ static void conflict_rename_delete(struct merge_options *o,
 {
 	char *dest_name = pair->two->path;
 	int df_conflict = 0;
-	struct stat st;
 
 	output(o, 1, "CONFLICT (rename/delete): Rename %s->%s in %s "
 	       "and deleted in %s",
@@ -892,7 +915,7 @@ static void conflict_rename_delete(struct merge_options *o,
 		update_stages(dest_name, NULL,
 			      rename_branch == o->branch1 ? pair->two : NULL,
 			      rename_branch == o->branch1 ? NULL : pair->two);
-	if (lstat(dest_name, &st) == 0 && S_ISDIR(st.st_mode)) {
+	if (dir_in_way(dest_name, !o->call_depth)) {
 		dest_name = unique_path(o, dest_name, rename_branch);
 		df_conflict = 1;
 	}
@@ -914,13 +937,12 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 	const char *ren2_dst = pair2->two->path;
 	const char *dst_name1 = ren1_dst;
 	const char *dst_name2 = ren2_dst;
-	struct stat st;
-	if (lstat(ren1_dst, &st) == 0 && S_ISDIR(st.st_mode)) {
+	if (dir_in_way(ren1_dst, !o->call_depth)) {
 		dst_name1 = del[delp++] = unique_path(o, ren1_dst, branch1);
 		output(o, 1, "%s is a directory in %s adding as %s instead",
 		       ren1_dst, branch2, dst_name1);
 	}
-	if (lstat(ren2_dst, &st) == 0 && S_ISDIR(st.st_mode)) {
+	if (dir_in_way(ren2_dst, !o->call_depth)) {
 		dst_name2 = del[delp++] = unique_path(o, ren2_dst, branch2);
 		output(o, 1, "%s is a directory in %s adding as %s instead",
 		       ren2_dst, branch1, dst_name2);
@@ -1080,7 +1102,7 @@ static int process_renames(struct merge_options *o,
 			try_merge = 0;
 
 			if (sha_eq(src_other.sha1, null_sha1)) {
-				if (string_list_has_string(&o->current_directory_set, ren1_dst)) {
+				if (dir_in_way(ren1_dst, 0 /*check_wc*/)) {
 					ren1->dst_entry->processed = 0;
 					setup_rename_df_conflict_info(RENAME_DELETE,
 								      ren1->pair,
@@ -1159,7 +1181,7 @@ static int process_renames(struct merge_options *o,
 					a = &src_other;
 				}
 				update_stages_and_entry(ren1_dst, ren1->dst_entry, one, a, b, 1);
-				if (string_list_has_string(&o->current_directory_set, ren1_dst)) {
+				if (dir_in_way(ren1_dst, 0 /*check_wc*/)) {
 					setup_rename_df_conflict_info(RENAME_NORMAL,
 								      ren1->pair,
 								      NULL,
@@ -1264,7 +1286,6 @@ static int merge_content(struct merge_options *o,
 	const char *reason = "content";
 	struct merge_file_info mfi;
 	struct diff_filespec one, a, b;
-	struct stat st;
 	unsigned df_conflict_remains = 0;
 
 	if (!o_sha) {
@@ -1281,7 +1302,7 @@ static int merge_content(struct merge_options *o,
 
 	mfi = merge_file(o, &one, &a, &b, o->branch1, o->branch2);
 	if (df_rename_conflict_branch &&
-	    lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
+	    dir_in_way(path, !o->call_depth)) {
 		df_conflict_remains = 1;
 	}
 
@@ -1346,8 +1367,7 @@ static int process_entry(struct merge_options *o,
 				output(o, 2, "Removing %s", path);
 			/* do not touch working file if it did not exist */
 			remove_file(o, 1, path, !a_sha);
-		} else if (string_list_has_string(&o->current_directory_set,
-						  path)) {
+		} else if (dir_in_way(path, 0 /*check_wc*/)) {
 			entry->processed = 0;
 			return 1; /* Assume clean until processed */
 		} else {
@@ -1370,7 +1390,7 @@ static int process_entry(struct merge_options *o,
 			mode = b_mode;
 			sha = b_sha;
 		}
-		if (string_list_has_string(&o->current_directory_set, path)) {
+		if (dir_in_way(path, 0 /*check_wc*/)) {
 			/* Handle D->F conflicts after all subfiles */
 			entry->processed = 0;
 			return 1; /* Assume clean until processed */
@@ -1418,7 +1438,6 @@ static int process_df_entry(struct merge_options *o,
 	unsigned char *o_sha = stage_sha(entry->stages[1].sha, o_mode);
 	unsigned char *a_sha = stage_sha(entry->stages[2].sha, a_mode);
 	unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
-	struct stat st;
 
 	entry->processed = 1;
 	if (entry->rename_df_conflict_info) {
@@ -1463,7 +1482,7 @@ static int process_df_entry(struct merge_options *o,
 	} else if (o_sha && (!a_sha || !b_sha)) {
 		/* Modify/delete; deleted side may have put a directory in the way */
 		char *renamed = NULL;
-		if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
+		if (dir_in_way(path, !o->call_depth)) {
 			renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
 		}
 		clean_merge = 0;
@@ -1491,7 +1510,7 @@ static int process_df_entry(struct merge_options *o,
 			sha = b_sha;
 			conf = "directory/file";
 		}
-		if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
+		if (dir_in_way(path, !o->call_depth)) {
 			char *new_path = unique_path(o, path, add_branch);
 			clean_merge = 0;
 			output(o, 1, "CONFLICT (%s): There is a directory with name %s in %s. "
-- 
1.7.6.100.gac5c1

[PATCHv2 25/56] merge-recursive: Save D/F conflict filenames instead of unlinking them

[Elijah Newren]

Rename make_room_for_directories_of_df_conflicts() to
record_df_conflict_files() to reflect the change in functionality.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   40 ++++++++++++++++++++++++----------------
 merge-recursive.h |    1 +
 2 files changed, 25 insertions(+), 16 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 9aacf5e..e1723d4 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -362,20 +362,24 @@ static int string_list_df_name_compare(const void *a, const void *b)
 	return onelen - twolen;
 }
 
-
-
-static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
-						      struct string_list *entries)
+static void record_df_conflict_files(struct merge_options *o,
+				     struct string_list *entries)
 {
-	/* If there are D/F conflicts, and the paths currently exist
-	 * in the working copy as a file, we want to remove them to
-	 * make room for the corresponding directory.  Such paths will
-	 * later be processed in process_df_entry() at the end.  If
-	 * the corresponding directory ends up being removed by the
-	 * merge, then the file will be reinstated at that time;
-	 * otherwise, if the file is not supposed to be removed by the
-	 * merge, the contents of the file will be placed in another
-	 * unique filename.
+	/* If there is a D/F conflict and the file for such a conflict
+	 * currently exist in the working copy, we want to allow it to
+	 * be removed to make room for the corresponding directory if
+	 * needed.  The files underneath the directories of such D/F
+	 * conflicts will be handled in process_entry(), while the
+	 * files of such D/F conflicts will be processed later in
+	 * process_df_entry().  If the corresponding directory ends up
+	 * being removed by the merge, then no additional work needs
+	 * to be done by process_df_entry() for the conflicting file.
+	 * If the directory needs to be written to the working copy,
+	 * then the conflicting file will simply be removed (e.g. in
+	 * make_room_for_path).  If the directory is written to the
+	 * working copy but the file also has a conflict that needs to
+	 * be resolved, then process_df_entry() will reinstate the
+	 * file with a new unique name.
 	 */
 	const char *last_file = NULL;
 	int last_len = 0;
@@ -392,6 +396,7 @@ static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
 	qsort(entries->items, entries->nr, sizeof(*entries->items),
 	      string_list_df_name_compare);
 
+	string_list_clear(&o->df_conflict_file_set, 1);
 	for (i = 0; i < entries->nr; i++) {
 		const char *path = entries->items[i].string;
 		int len = strlen(path);
@@ -400,14 +405,15 @@ static void make_room_for_directories_of_df_conflicts(struct merge_options *o,
 		/*
 		 * Check if last_file & path correspond to a D/F conflict;
 		 * i.e. whether path is last_file+'/'+<something>.
-		 * If so, remove last_file to make room for path and friends.
+		 * If so, record that it's okay to remove last_file to make
+		 * room for path and friends if needed.
 		 */
 		if (last_file &&
 		    len > last_len &&
 		    memcmp(path, last_file, last_len) == 0 &&
 		    path[last_len] == '/') {
 			output(o, 3, "Removing %s to make room for subdirectory; may re-add later.", last_file);
-			unlink(last_file);
+			string_list_insert(&o->df_conflict_file_set, last_file);
 		}
 
 		/*
@@ -1571,7 +1577,7 @@ int merge_trees(struct merge_options *o,
 		get_files_dirs(o, merge);
 
 		entries = get_unmerged();
-		make_room_for_directories_of_df_conflicts(o, entries);
+		record_df_conflict_files(o, entries);
 		re_head  = get_renames(o, head, common, head, merge, entries);
 		re_merge = get_renames(o, merge, common, head, merge, entries);
 		clean = process_renames(o, re_head, re_merge);
@@ -1797,6 +1803,8 @@ void init_merge_options(struct merge_options *o)
 	o->current_file_set.strdup_strings = 1;
 	memset(&o->current_directory_set, 0, sizeof(struct string_list));
 	o->current_directory_set.strdup_strings = 1;
+	memset(&o->df_conflict_file_set, 0, sizeof(struct string_list));
+	o->df_conflict_file_set.strdup_strings = 1;
 }
 
 int parse_merge_opt(struct merge_options *o, const char *s)
diff --git a/merge-recursive.h b/merge-recursive.h
index 7e1e972..58f3435 100644
--- a/merge-recursive.h
+++ b/merge-recursive.h
@@ -26,6 +26,7 @@ struct merge_options {
 	struct strbuf obuf;
 	struct string_list current_file_set;
 	struct string_list current_directory_set;
+	struct string_list df_conflict_file_set;
 };
 
 /* merge_trees() but with recursive ancestor consolidation */
-- 
1.7.6.100.gac5c1

[PATCHv2 26/56] merge-recursive: Split was_tracked() out of would_lose_untracked()

[Elijah Newren]

Checking whether a filename was part of stage 0 or stage 2 is code that we
would like to be able to call from a few other places without also
lstat()-ing the file to see if it exists in the working copy.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   11 ++++++++---
 1 files changed, 8 insertions(+), 3 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index e1723d4..c12e4d5 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -623,7 +623,7 @@ static int dir_in_way(const char *path, int check_working_copy)
 	return check_working_copy && !lstat(path, &st) && S_ISDIR(st.st_mode);
 }
 
-static int would_lose_untracked(const char *path)
+static int was_tracked(const char *path)
 {
 	int pos = cache_name_pos(path, strlen(path));
 
@@ -640,11 +640,16 @@ static int would_lose_untracked(const char *path)
 		switch (ce_stage(active_cache[pos])) {
 		case 0:
 		case 2:
-			return 0;
+			return 1;
 		}
 		pos++;
 	}
-	return file_exists(path);
+	return 0;
+}
+
+static int would_lose_untracked(const char *path)
+{
+	return !was_tracked(path) && file_exists(path);
 }
 
 static int make_room_for_path(const char *path)
-- 
1.7.6.100.gac5c1

[PATCHv2 27/56] string-list: Add API to remove an item from an unsorted list

[Elijah Newren]

From: Johannes Sixt <j.sixt@viscovery.net>

Here's an attempt for a delete_item API (note: only compile-tested).
Bike-shed painters welcome: delete_item, remove_item, free_item?

Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
New patch that wasn't part of v1, submitted by Johannes.

 Documentation/technical/api-string-list.txt |   10 ++++++++++
 string-list.c                               |    9 +++++++++
 string-list.h                               |    1 +
 3 files changed, 20 insertions(+), 0 deletions(-)

diff --git a/Documentation/technical/api-string-list.txt b/Documentation/technical/api-string-list.txt
index 3f575bd..ce24eb9 100644
--- a/Documentation/technical/api-string-list.txt
+++ b/Documentation/technical/api-string-list.txt
@@ -29,6 +29,9 @@ member (you need this if you add things later) and you should set the
 
 . Can sort an unsorted list using `sort_string_list`.
 
+. Can remove individual items of an unsorted list using
+  `unsorted_string_list_delete_item`.
+
 . Finally it should free the list using `string_list_clear`.
 
 Example:
@@ -112,6 +115,13 @@ write `string_list_insert(...)->util = ...;`.
 The above two functions need to look through all items, as opposed to their
 counterpart for sorted lists, which performs a binary search.
 
+`unsorted_string_list_delete_item`::
+
+	Remove an item from a string_list. The `string` pointer of the items
+	will be freed in case the `strdup_strings` member of the string_list
+	is set. The third parameter controls if the `util` pointer of the
+	items should be freed or not.
+
 Data structures
 ---------------
 
diff --git a/string-list.c b/string-list.c
index 5168118..d9810ab 100644
--- a/string-list.c
+++ b/string-list.c
@@ -185,3 +185,12 @@ int unsorted_string_list_has_string(struct string_list *list,
 	return unsorted_string_list_lookup(list, string) != NULL;
 }
 
+void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util)
+{
+	if (list->strdup_strings)
+		free(list->items[i].string);
+	if (free_util)
+		free(list->items[i].util);
+	list->items[i] = list->items[list->nr-1];
+	list->nr--;
+}
diff --git a/string-list.h b/string-list.h
index bda6983..0684cb7 100644
--- a/string-list.h
+++ b/string-list.h
@@ -44,4 +44,5 @@ void sort_string_list(struct string_list *list);
 int unsorted_string_list_has_string(struct string_list *list, const char *string);
 struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
 						     const char *string);
+void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util);
 #endif /* STRING_LIST_H */
-- 
1.7.6.100.gac5c1

[PATCHv2 28/56] merge-recursive: Allow make_room_for_path() to remove D/F entries

[Elijah Newren]

If there were several files conflicting below a directory corresponding
to a D/F conflict, and the file of that D/F conflict is in the way, we
want it to be removed.  Since files of D/F conflicts are handled last,
they can be reinstated later and possibly with a new unique name.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1:
  (1) Made use of Johannes' new string-list API to remove items we
      have already checked in order to avoid trying to unlink a path
      more than once
  (2) Moved the comment about removing paths to make room to the
      location where we actually remove the path.
  (3) Fixed a bug with accidentally removing wrong paths (by adding the
        path[df_pathlen] == '/'
      check)

 merge-recursive.c                 |   26 ++++++++++++++++++++++----
 t/t6036-recursive-corner-cases.sh |    2 +-
 2 files changed, 23 insertions(+), 5 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index c12e4d5..1547691 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -412,7 +412,6 @@ static void record_df_conflict_files(struct merge_options *o,
 		    len > last_len &&
 		    memcmp(path, last_file, last_len) == 0 &&
 		    path[last_len] == '/') {
-			output(o, 3, "Removing %s to make room for subdirectory; may re-add later.", last_file);
 			string_list_insert(&o->df_conflict_file_set, last_file);
 		}
 
@@ -652,11 +651,30 @@ static int would_lose_untracked(const char *path)
 	return !was_tracked(path) && file_exists(path);
 }
 
-static int make_room_for_path(const char *path)
+static int make_room_for_path(struct merge_options *o, const char *path)
 {
-	int status;
+	int status, i;
 	const char *msg = "failed to create path '%s'%s";
 
+	/* Unlink any D/F conflict files that are in the way */
+	for (i = 0; i < o->df_conflict_file_set.nr; i++) {
+		const char *df_path = o->df_conflict_file_set.items[i].string;
+		size_t pathlen = strlen(path);
+		size_t df_pathlen = strlen(df_path);
+		if (df_pathlen < pathlen &&
+		    path[df_pathlen] == '/' &&
+		    strncmp(path, df_path, df_pathlen) == 0) {
+			output(o, 3,
+			       "Removing %s to make room for subdirectory\n",
+			       df_path);
+			unlink(df_path);
+			unsorted_string_list_delete_item(&o->df_conflict_file_set,
+							 i, 0);
+			break;
+		}
+	}
+
+	/* Make sure leading directories are created */
 	status = safe_create_leading_directories_const(path);
 	if (status) {
 		if (status == -3) {
@@ -724,7 +742,7 @@ static void update_file_flags(struct merge_options *o,
 			}
 		}
 
-		if (make_room_for_path(path) < 0) {
+		if (make_room_for_path(o, path) < 0) {
 			update_wd = 0;
 			free(buf);
 			goto update_index;
diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index ed6c6f4..279f33c 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -496,7 +496,7 @@ test_expect_success 'setup differently handled merges of directory/file conflict
 	git tag E2
 '
 
-test_expect_failure 'merge of D & E1 fails but has appropriate contents' '
+test_expect_success 'merge of D & E1 fails but has appropriate contents' '
 	get_clean_checkout D^0 &&
 
 	test_must_fail git merge -s recursive E1^0 &&
-- 
1.7.6.100.gac5c1

[PATCHv2 29/56] merge-recursive: Split update_stages_and_entry; only update stages at end

[Elijah Newren]

Instead of having the process_renames logic update the stages in the index
for the rename destination, have the index updated after process_entry or
process_df_entry.  This will also allow us to have process_entry determine
whether a file was tracked and existed in the working copy before the
merge started.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   35 +++++++++++++++++------------------
 1 files changed, 17 insertions(+), 18 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 1547691..650d5ec 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -90,6 +90,7 @@ struct stage_data {
 	} stages[4];
 	struct rename_df_conflict_info *rename_df_conflict_info;
 	unsigned processed:1;
+	unsigned involved_in_rename:1;
 };
 
 static inline void setup_rename_df_conflict_info(enum rename_type rename_type,
@@ -524,15 +525,11 @@ static int update_stages(const char *path, const struct diff_filespec *o,
 	return 0;
 }
 
-static int update_stages_and_entry(const char *path,
-				   struct stage_data *entry,
-				   struct diff_filespec *o,
-				   struct diff_filespec *a,
-				   struct diff_filespec *b,
-				   int clear)
+static void update_entry(struct stage_data *entry,
+			 struct diff_filespec *o,
+			 struct diff_filespec *a,
+			 struct diff_filespec *b)
 {
-	int options;
-
 	entry->processed = 0;
 	entry->stages[1].mode = o->mode;
 	entry->stages[2].mode = a->mode;
@@ -540,7 +537,6 @@ static int update_stages_and_entry(const char *path,
 	hashcpy(entry->stages[1].sha, o->sha1);
 	hashcpy(entry->stages[2].sha, a->sha1);
 	hashcpy(entry->stages[3].sha, b->sha1);
-	return update_stages(path, o, a, b);
 }
 
 static int remove_file(struct merge_options *o, int clean,
@@ -1099,12 +1095,11 @@ static int process_renames(struct merge_options *o,
 							      ren2->dst_entry);
 			} else {
 				remove_file(o, 1, ren1_src, 1);
-				update_stages_and_entry(ren1_dst,
-							ren1->dst_entry,
-							ren1->pair->one,
-							ren1->pair->two,
-							ren2->pair->two,
-							1 /* clear */);
+				update_entry(ren1->dst_entry,
+					     ren1->pair->one,
+					     ren1->pair->two,
+					     ren2->pair->two);
+				ren1->dst_entry->involved_in_rename = 1;
 			}
 		} else {
 			/* Renamed in 1, maybe changed in 2 */
@@ -1209,7 +1204,8 @@ static int process_renames(struct merge_options *o,
 					b = ren1->pair->two;
 					a = &src_other;
 				}
-				update_stages_and_entry(ren1_dst, ren1->dst_entry, one, a, b, 1);
+				update_entry(ren1->dst_entry, one, a, b);
+				ren1->dst_entry->involved_in_rename = 1;
 				if (dir_in_way(ren1_dst, 0 /*check_wc*/)) {
 					setup_rename_df_conflict_info(RENAME_NORMAL,
 								      ren1->pair,
@@ -1306,6 +1302,7 @@ static void handle_delete_modify(struct merge_options *o,
 }
 
 static int merge_content(struct merge_options *o,
+			 unsigned involved_in_rename,
 			 const char *path,
 			 unsigned char *o_sha, int o_mode,
 			 unsigned char *a_sha, int a_mode,
@@ -1346,6 +1343,8 @@ static int merge_content(struct merge_options *o,
 			reason = "submodule";
 		output(o, 1, "CONFLICT (%s): Merge conflict in %s",
 				reason, path);
+		if (involved_in_rename)
+			update_stages(path, &one, &a, &b);
 	}
 
 	if (df_conflict_remains) {
@@ -1430,7 +1429,7 @@ static int process_entry(struct merge_options *o,
 	} else if (a_sha && b_sha) {
 		/* Case C: Added in both (check for same permissions) and */
 		/* case D: Modified in both, but differently. */
-		clean_merge = merge_content(o, path,
+		clean_merge = merge_content(o, entry->involved_in_rename, path,
 					    o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
 					    NULL);
 	} else if (!o_sha && !a_sha && !b_sha) {
@@ -1474,7 +1473,7 @@ static int process_df_entry(struct merge_options *o,
 		char *src;
 		switch (conflict_info->rename_type) {
 		case RENAME_NORMAL:
-			clean_merge = merge_content(o, path,
+			clean_merge = merge_content(o, entry->involved_in_rename, path,
 						    o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
 						    conflict_info->branch1);
 			break;
-- 
1.7.6.100.gac5c1

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

[Elijah Newren]

In the recursive case (o->call_depth > 0), we do not modify the working
directory.  However, when o->call_depth==0, file renames can mean we need
to delete the old filename from the working copy.  Since there have been
lots of changes and mistakes here, let's go through the details.  Let's
start with a simple explanation of what we are trying to achieve:

  Original goal: If a file is renamed on the side of history being merged
  into head, the filename serving as the source of that rename needs to be
  removed from the working directory.

The path to getting the above statement implemented in merge-recursive took
several steps.  The relevant bits of code may be instructive to keep in
mind for the explanation, especially since an English-only description
involves double negatives that are hard to follow.  These bits of code are:
  int remove_file(..., const char *path, int no_wd)
  {
    ...
    int update_working_directory = !o->call_depth && !no_wd;
and
  remove_file(o, 1, ren1_src, <expression>);
Where the choice for <expression> has morphed over time:

65ac6e9 (merge-recursive: adjust to loosened "working file clobbered"
check 2006-10-27), introduced the "no_wd" parameter to remove_file() and
used "1" for <expression>.  This meant ren1_src was never deleted, leaving
it around in the working copy.

In 8371234 (Remove uncontested renamed files during merge. 2006-12-13),
<expression> was changed to "index_only" (where index_only ==
!!o->call_depth; see b7fa51da).   This was equivalent to using "0" for
<expression> (due to the early logic in remove_file), and is orthogonal to
the condition we actually want to check at this point; it resulted in the
source file being removed except when index_only was false.  This was
problematic because the file could have been renamed on the side of history
including head, in which case ren1_src could correspond to an untracked
file that should not be deleted.

In 183d797 (Keep untracked files not involved in a merge. 2007-02-04),
<expression> was changed to "index_only || stage == 3".  While this gives
correct behavior, the "index_only ||" portion of <expression> is
unnecessary and makes the code slightly harder to follow.

There were also two further changes to this expression, though without
any change in behavior.  First in b7fa51d (merge-recursive: get rid of the
index_only global variable 2008-09-02), it was changed to "o->call_depth
|| stage == 3".  (index_only == !!o->call_depth).  Later, in 41d70bd6
(merge-recursive: Small code clarification -- variable name and comments),
this was changed to "o->call_depth || renamed_stage == 2" (where stage was
renamed to other_stage and renamed_stage == other_stage ^ 1).

So we ended with <expression> being "o->call_depth || renamed_stage == 2".
But the "o->call_depth ||" piece was unnecessary.  We can remove it,
leaving us with <expression> being "renamed_stage == 2".  This doesn't
change behavior at all, but it makes the code clearer.  Which is good,
because it's about to get uglier.

  Corrected goal: If a file is renamed on the side of history being merged
  into head, the filename serving as the source of that rename needs to be
  removed from the working directory *IF* that file is tracked in head AND
  the file tracked in head is related to the original file.

Note that the only difference between the original goal and the corrected
goal is the two extra conditions added at the end.  The first condition is
relevant in a rename/delete conflict.  If the file was deleted on the
HEAD side of the merge and an untracked file of the same name was added to
the working copy, then without that extra condition the untracked file
will be erroneously deleted.  This changes <expression> to "renamed_stage
== 2 || !was_tracked(ren1_src)".

The second additional condition is relevant in two cases.

The first case the second condition can occur is when a file is deleted
and a completely different file is added with the same name.  To my
knowledge, merge-recursive has no mechanism for detecting deleted-and-
replaced-by-different-file cases, so I am simply punting on this
possibility.

The second case for the second condition to occur is when there is a
rename/rename/add-source conflict.  That is, when the original file was
renamed on both sides of history AND the original filename is being
re-used by some unrelated (but tracked) content.  This case also presents
some additional difficulties for us since we cannot currently detect these
rename/rename/add-source conflicts; as long as the rename detection logic
"optimizes" by ignoring filenames that are present at both ends of the
diff, these conflicts will go unnoticed.  However, rename/rename conflicts
are handled by an entirely separate codepath not being discussed here, so
this case is not relevant for the line of code under consideration.

In summary:
  Change <expression> from "o->call_depth || renamed_stage == 2" to
  "renamed_stage == 2 || !was_tracked(ren1_src)", in order to remove
  unnecessary code and avoid deleting untracked files.

96 lines of explanation in the changelog to describe a one-line fix...

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                    |    3 ++-
 t/t6042-merge-rename-corner-cases.sh |    2 +-
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 650d5ec..f395d20 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1117,7 +1117,8 @@ static int process_renames(struct merge_options *o,
 			int renamed_stage = a_renames == renames1 ? 2 : 3;
 			int other_stage =   a_renames == renames1 ? 3 : 2;
 
-			remove_file(o, 1, ren1_src, o->call_depth || renamed_stage == 2);
+			remove_file(o, 1, ren1_src,
+				    renamed_stage == 2 || !was_tracked(ren1_src));
 
 			hashcpy(src_other.sha1, ren1->src_entry->stages[other_stage].sha);
 			src_other.mode = ren1->src_entry->stages[other_stage].mode;
diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 427fe1c..668ec6d 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -26,7 +26,7 @@ test_expect_success 'setup rename/delete + untracked file' '
 	echo "Myyy PRECIOUSSS" >ring
 '
 
-test_expect_failure "Does git preserve Gollum's precious artifact?" '
+test_expect_success "Does git preserve Gollum's precious artifact?" '
 	test_must_fail git merge -s recursive rename-the-ring &&
 
 	# Make sure git did not delete an untracked file
-- 
1.7.6.100.gac5c1

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

[Elijah Newren]

The code for rename_rename_2to1 conflicts (two files both being renamed to
the same filename) was dead since the rename/add path was always being
independently triggered for each of the renames instead.  Further,
reviving the dead code showed that it was inherently buggy and would
always segfault -- among a few other bugs.

Move the else-if branch for the rename/rename block before the rename/add
block to make sure it is checked first, and fix up the rename/rename(2to1)
code segments to make it handle most cases.  Work is still needed to
handle higher dimensional corner cases such as rename/rename/modify/modify
issues.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                 |   70 +++++++++++++++++++++++++-----------
 t/t6036-recursive-corner-cases.sh |   17 +++++----
 2 files changed, 57 insertions(+), 30 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index f395d20..f74feb5 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -998,17 +998,36 @@ static void conflict_rename_rename_2to1(struct merge_options *o,
 					struct rename *ren2,
 					const char *branch2)
 {
+	char *path = ren1->pair->two->path; /* same as ren2->pair->two->path */
 	/* Two files were renamed to the same thing. */
-	char *new_path1 = unique_path(o, ren1->pair->two->path, branch1);
-	char *new_path2 = unique_path(o, ren2->pair->two->path, branch2);
-	output(o, 1, "Renaming %s to %s and %s to %s instead",
-	       ren1->pair->one->path, new_path1,
-	       ren2->pair->one->path, new_path2);
-	remove_file(o, 0, ren1->pair->two->path, 0);
-	update_file(o, 0, ren1->pair->two->sha1, ren1->pair->two->mode, new_path1);
-	update_file(o, 0, ren2->pair->two->sha1, ren2->pair->two->mode, new_path2);
-	free(new_path2);
-	free(new_path1);
+	if (o->call_depth) {
+		struct merge_file_info mfi;
+		struct diff_filespec one, a, b;
+
+		one.path = a.path = b.path = path;
+		hashcpy(one.sha1, null_sha1);
+		one.mode = 0;
+		hashcpy(a.sha1, ren1->pair->two->sha1);
+		a.mode = ren1->pair->two->mode;
+		hashcpy(b.sha1, ren2->pair->two->sha1);
+		b.mode = ren2->pair->two->mode;
+		mfi = merge_file(o, &one, &a, &b, branch1, branch2);
+		output(o, 1, "Adding merged %s", path);
+		update_file(o, 0, mfi.sha, mfi.mode, path);
+	} else {
+		char *new_path1 = unique_path(o, path, branch1);
+		char *new_path2 = unique_path(o, path, branch2);
+		output(o, 1, "Renaming %s to %s and %s to %s instead",
+		       ren1->pair->one->path, new_path1,
+		       ren2->pair->one->path, new_path2);
+		remove_file(o, 0, path, 0);
+		update_file(o, 0, ren1->pair->two->sha1, ren1->pair->two->mode,
+			    new_path1);
+		update_file(o, 0, ren2->pair->two->sha1, ren2->pair->two->mode,
+			    new_path2);
+		free(new_path2);
+		free(new_path1);
+	}
 }
 
 static int process_renames(struct merge_options *o,
@@ -1023,12 +1042,12 @@ static int process_renames(struct merge_options *o,
 	for (i = 0; i < a_renames->nr; i++) {
 		sre = a_renames->items[i].util;
 		string_list_insert(&a_by_dst, sre->pair->two->path)->util
-			= sre->dst_entry;
+			= (void *)sre;
 	}
 	for (i = 0; i < b_renames->nr; i++) {
 		sre = b_renames->items[i].util;
 		string_list_insert(&b_by_dst, sre->pair->two->path)->util
-			= sre->dst_entry;
+			= (void *)sre;
 	}
 
 	for (i = 0, j = 0; i < a_renames->nr || j < b_renames->nr;) {
@@ -1140,6 +1159,23 @@ static int process_renames(struct merge_options *o,
 					clean_merge = 0;
 					conflict_rename_delete(o, ren1->pair, branch1, branch2);
 				}
+			} else if ((item = string_list_lookup(renames2Dst, ren1_dst))) {
+				char *ren2_src, *ren2_dst;
+				ren2 = item->util;
+				ren2_src = ren2->pair->one->path;
+				ren2_dst = ren2->pair->two->path;
+
+				clean_merge = 0;
+				ren2->processed = 1;
+				remove_file(o, 1, ren2_src,
+					    renamed_stage == 3 || would_lose_untracked(ren1_src));
+
+				output(o, 1, "CONFLICT (rename/rename): "
+				       "Rename %s->%s in %s. "
+				       "Rename %s->%s in %s",
+				       ren1_src, ren1_dst, branch1,
+				       ren2_src, ren2_dst, branch2);
+				conflict_rename_rename_2to1(o, ren1, branch1, ren2, branch2);
 			} else if ((dst_other.mode == ren1->pair->two->mode) &&
 				   sha_eq(dst_other.sha1, ren1->pair->two->sha1)) {
 				/* Added file on the other side
@@ -1180,16 +1216,6 @@ static int process_renames(struct merge_options *o,
 					update_file(o, 0, dst_other.sha1, dst_other.mode, new_path);
 					free(new_path);
 				}
-			} else if ((item = string_list_lookup(renames2Dst, ren1_dst))) {
-				ren2 = item->util;
-				clean_merge = 0;
-				ren2->processed = 1;
-				output(o, 1, "CONFLICT (rename/rename): "
-				       "Rename %s->%s in %s. "
-				       "Rename %s->%s in %s",
-				       ren1_src, ren1_dst, branch1,
-				       ren2->pair->one->path, ren2->pair->two->path, branch2);
-				conflict_rename_rename_2to1(o, ren1, branch1, ren2, branch2);
 			} else
 				try_merge = 1;
 
diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 279f33c..b046e1b 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -66,13 +66,13 @@ test_expect_success 'merge simple rename+criss-cross with no modifications' '
 	test $(git rev-parse :2:three) = $(git rev-parse L2:three) &&
 	test $(git rev-parse :3:three) = $(git rev-parse R2:three) &&
 
-	cp two merged &&
+	cp one merged &&
 	>empty &&
 	test_must_fail git merge-file \
-		-L "Temporary merge branch 2" \
-		-L "" \
 		-L "Temporary merge branch 1" \
-		merged empty one &&
+		-L "" \
+		-L "Temporary merge branch 2" \
+		merged empty two &&
 	test $(git rev-parse :1:three) = $(git hash-object merged)
 '
 
@@ -145,11 +145,12 @@ test_expect_success 'merge criss-cross + rename merges with basic modification'
 	cp one merge-me &&
 	>empty &&
 	test_must_fail git merge-file \
-		-L "Temporary merge branch 2" \
-		-L "" \
 		-L "Temporary merge branch 1" \
-		merged empty merge-me &&
-	test $(git rev-parse :1:three) = $(git hash-object merged)
+		-L "" \
+		-L "Temporary merge branch 2" \
+		merge-me empty merged &&
+
+	test $(git rev-parse :1:three) = $(git hash-object merge-me)
 '
 
 #
-- 
1.7.6.100.gac5c1

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

[Elijah Newren]

There are a couple of places where changes are needed to for situations
involving rename/add-source issues.  Add comments about the needed changes
(and existing bugs) until git has been enabled to detect such cases.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   11 +++++++++++
 1 files changed, 11 insertions(+), 0 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index f74feb5..5f28905 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1087,6 +1087,9 @@ static int process_renames(struct merge_options *o,
 		}
 
 		ren1->dst_entry->processed = 1;
+		/* BUG: We should only mark src_entry as processed if we
+		 * are not dealing with a rename + add-source case.
+		 */
 		ren1->src_entry->processed = 1;
 
 		if (ren1->processed)
@@ -1113,6 +1116,10 @@ static int process_renames(struct merge_options *o,
 							      ren1->dst_entry,
 							      ren2->dst_entry);
 			} else {
+				/* BUG: We should only remove ren1_src in
+				 * the base stage (think of rename +
+				 * add-source cases).
+				 */
 				remove_file(o, 1, ren1_src, 1);
 				update_entry(ren1->dst_entry,
 					     ren1->pair->one,
@@ -1136,6 +1143,10 @@ static int process_renames(struct merge_options *o,
 			int renamed_stage = a_renames == renames1 ? 2 : 3;
 			int other_stage =   a_renames == renames1 ? 3 : 2;
 
+			/* BUG: We should only remove ren1_src in the base
+			 * stage and in other_stage (think of rename +
+			 * add-source case).
+			 */
 			remove_file(o, 1, ren1_src,
 				    renamed_stage == 2 || !was_tracked(ren1_src));
 
-- 
1.7.6.100.gac5c1

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

[Elijah Newren]

When dealing with file merging and renames and D/F conflicts and possible
criss-cross merges (how's that for a corner case?), we did not do a
thorough job ensuring the index and working directory had the correct
contents.   Fix the logic in merge_content() to handle this.  Also,
correct some erroneous tests in t6022 that were expecting the wrong number
of unmerged index entries.  These changes fix one of the tests in t6042
(and almost fix another one from t6042 as well).

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                    |   27 ++++++++++++++++++++++-----
 t/t6022-merge-rename.sh              |    4 ++--
 t/t6042-merge-rename-corner-cases.sh |    2 +-
 3 files changed, 25 insertions(+), 8 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 5f28905..f1160d5 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1381,19 +1381,34 @@ static int merge_content(struct merge_options *o,
 			reason = "submodule";
 		output(o, 1, "CONFLICT (%s): Merge conflict in %s",
 				reason, path);
-		if (involved_in_rename)
+		if (involved_in_rename && !df_conflict_remains)
 			update_stages(path, &one, &a, &b);
 	}
 
 	if (df_conflict_remains) {
 		char *new_path;
-		update_file_flags(o, mfi.sha, mfi.mode, path,
-				  o->call_depth || mfi.clean, 0);
+		if (o->call_depth) {
+			remove_file_from_cache(path);
+		} else {
+			if (!mfi.clean)
+				update_stages(path, &one, &a, &b);
+			else {
+				int file_from_stage2 = was_tracked(path);
+				struct diff_filespec merged;
+				hashcpy(merged.sha1, mfi.sha);
+				merged.mode = mfi.mode;
+
+				update_stages(path, NULL,
+					      file_from_stage2 ? &merged : NULL,
+					      file_from_stage2 ? NULL : &merged);
+			}
+
+		}
 		new_path = unique_path(o, path, df_rename_conflict_branch);
-		mfi.clean = 0;
 		output(o, 1, "Adding as %s instead", new_path);
-		update_file_flags(o, mfi.sha, mfi.mode, new_path, 0, 1);
+		update_file(o, 0, mfi.sha, mfi.mode, new_path);
 		free(new_path);
+		mfi.clean = 0;
 	} else {
 		update_file(o, mfi.clean, mfi.sha, mfi.mode, path);
 	}
@@ -1582,6 +1597,8 @@ static int process_df_entry(struct merge_options *o,
 			output(o, 1, "CONFLICT (%s): There is a directory with name %s in %s. "
 			       "Adding %s as %s",
 			       conf, path, other_branch, path, new_path);
+			if (o->call_depth)
+				remove_file_from_cache(path);
 			update_file(o, 0, sha, mode, new_path);
 			if (o->call_depth)
 				remove_file_from_cache(path);
diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 6ff4bd2..fcc1d4c 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -307,7 +307,7 @@ test_expect_success 'Rename+D/F conflict; renamed file merges but dir in way' '
 	grep "Auto-merging dir" output &&
 	grep "Adding as dir~HEAD instead" output &&
 
-	test 2 -eq "$(git ls-files -u | wc -l)" &&
+	test 3 -eq "$(git ls-files -u | wc -l)" &&
 	test 2 -eq "$(git ls-files -u dir/file-in-the-way | wc -l)" &&
 
 	test_must_fail git diff --quiet &&
@@ -329,7 +329,7 @@ test_expect_success 'Same as previous, but merged other way' '
 	grep "Auto-merging dir" output &&
 	grep "Adding as dir~renamed-file-has-no-conflicts instead" output &&
 
-	test 2 -eq "$(git ls-files -u | wc -l)" &&
+	test 3 -eq "$(git ls-files -u | wc -l)" &&
 	test 2 -eq "$(git ls-files -u dir/file-in-the-way | wc -l)" &&
 
 	test_must_fail git diff --quiet &&
diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 668ec6d..968055d 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -234,7 +234,7 @@ test_expect_success 'setup content merge + rename/directory conflict' '
 	git commit -m left
 '
 
-test_expect_failure 'rename/directory conflict + clean content merge' '
+test_expect_success 'rename/directory conflict + clean content merge' '
 	git reset --hard &&
 	git reset --hard &&
 	git clean -fdqx &&
-- 
1.7.6.100.gac5c1

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

[Elijah Newren]

The whole point of adding process_df_entry() was to ensure that files of
D/F conflicts were processed after paths under the corresponding
directory.  However, given that the entries are in sorted order, all we
need to do is iterate through them in reverse order to achieve the same
effect.  That lets us remove some duplicated code, and lets us keep
track of one less thing as we read the code ("do we need to make sure
this is processed before process_df_entry() or do we need to defer it
until then?").

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |  188 ++++++++++++++++-------------------------------------
 1 files changed, 57 insertions(+), 131 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index f1160d5..74b1139 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -116,7 +116,6 @@ static inline void setup_rename_df_conflict_info(enum rename_type rename_type,
 		ci->dst_entry2 = dst_entry2;
 		ci->pair2 = pair2;
 		dst_entry2->rename_df_conflict_info = ci;
-		dst_entry2->processed = 0;
 	}
 }
 
@@ -367,20 +366,17 @@ static void record_df_conflict_files(struct merge_options *o,
 				     struct string_list *entries)
 {
 	/* If there is a D/F conflict and the file for such a conflict
-	 * currently exist in the working copy, we want to allow it to
-	 * be removed to make room for the corresponding directory if
-	 * needed.  The files underneath the directories of such D/F
-	 * conflicts will be handled in process_entry(), while the
-	 * files of such D/F conflicts will be processed later in
-	 * process_df_entry().  If the corresponding directory ends up
-	 * being removed by the merge, then no additional work needs
-	 * to be done by process_df_entry() for the conflicting file.
-	 * If the directory needs to be written to the working copy,
-	 * then the conflicting file will simply be removed (e.g. in
-	 * make_room_for_path).  If the directory is written to the
-	 * working copy but the file also has a conflict that needs to
-	 * be resolved, then process_df_entry() will reinstate the
-	 * file with a new unique name.
+	 * currently exist in the working copy, we want to allow it to be
+	 * removed to make room for the corresponding directory if needed.
+	 * The files underneath the directories of such D/F conflicts will
+	 * be processed before the corresponding file involved in the D/F
+	 * conflict.  If the D/F directory ends up being removed by the
+	 * merge, then we won't have to touch the D/F file.  If the D/F
+	 * directory needs to be written to the working copy, then the D/F
+	 * file will simply be removed (in make_room_for_path()) to make
+	 * room for the necessary paths.  Note that if both the directory
+	 * and the file need to be present, then the D/F file will be
+	 * reinstated with a new unique name at the time it is processed.
 	 */
 	const char *last_file = NULL;
 	int last_len = 0;
@@ -1325,17 +1321,17 @@ static void handle_delete_modify(struct merge_options *o,
 		       "and modified in %s. Version %s of %s left in tree%s%s.",
 		       path, o->branch1,
 		       o->branch2, o->branch2, path,
-		       path == new_path ? "" : " at ",
-		       path == new_path ? "" : new_path);
-		update_file(o, 0, b_sha, b_mode, new_path);
+		       NULL == new_path ? "" : " at ",
+		       NULL == new_path ? "" : new_path);
+		update_file(o, 0, b_sha, b_mode, new_path ? new_path : path);
 	} else {
 		output(o, 1, "CONFLICT (delete/modify): %s deleted in %s "
 		       "and modified in %s. Version %s of %s left in tree%s%s.",
 		       path, o->branch2,
 		       o->branch1, o->branch1, path,
-		       path == new_path ? "" : " at ",
-		       path == new_path ? "" : new_path);
-		update_file(o, 0, a_sha, a_mode, new_path);
+		       NULL == new_path ? "" : " at ",
+		       NULL == new_path ? "" : new_path);
+		update_file(o, 0, a_sha, a_mode, new_path ? new_path : path);
 	}
 }
 
@@ -1433,93 +1429,6 @@ static int process_entry(struct merge_options *o,
 	unsigned char *a_sha = stage_sha(entry->stages[2].sha, a_mode);
 	unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
 
-	if (entry->rename_df_conflict_info)
-		return 1; /* Such cases are handled elsewhere. */
-
-	entry->processed = 1;
-	if (o_sha && (!a_sha || !b_sha)) {
-		/* Case A: Deleted in one */
-		if ((!a_sha && !b_sha) ||
-		    (!b_sha && blob_unchanged(o_sha, a_sha, normalize, path)) ||
-		    (!a_sha && blob_unchanged(o_sha, b_sha, normalize, path))) {
-			/* Deleted in both or deleted in one and
-			 * unchanged in the other */
-			if (a_sha)
-				output(o, 2, "Removing %s", path);
-			/* do not touch working file if it did not exist */
-			remove_file(o, 1, path, !a_sha);
-		} else if (dir_in_way(path, 0 /*check_wc*/)) {
-			entry->processed = 0;
-			return 1; /* Assume clean until processed */
-		} else {
-			/* Deleted in one and changed in the other */
-			clean_merge = 0;
-			handle_delete_modify(o, path, path,
-					     a_sha, a_mode, b_sha, b_mode);
-		}
-
-	} else if ((!o_sha && a_sha && !b_sha) ||
-		   (!o_sha && !a_sha && b_sha)) {
-		/* Case B: Added in one. */
-		unsigned mode;
-		const unsigned char *sha;
-
-		if (a_sha) {
-			mode = a_mode;
-			sha = a_sha;
-		} else {
-			mode = b_mode;
-			sha = b_sha;
-		}
-		if (dir_in_way(path, 0 /*check_wc*/)) {
-			/* Handle D->F conflicts after all subfiles */
-			entry->processed = 0;
-			return 1; /* Assume clean until processed */
-		} else {
-			output(o, 2, "Adding %s", path);
-			update_file(o, 1, sha, mode, path);
-		}
-	} else if (a_sha && b_sha) {
-		/* Case C: Added in both (check for same permissions) and */
-		/* case D: Modified in both, but differently. */
-		clean_merge = merge_content(o, entry->involved_in_rename, path,
-					    o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
-					    NULL);
-	} else if (!o_sha && !a_sha && !b_sha) {
-		/*
-		 * this entry was deleted altogether. a_mode == 0 means
-		 * we had that path and want to actively remove it.
-		 */
-		remove_file(o, 1, path, !a_mode);
-	} else
-		die("Fatal merge failure, shouldn't happen.");
-
-	return clean_merge;
-}
-
-/*
- * Per entry merge function for D/F (and/or rename) conflicts.  In the
- * cases we can cleanly resolve D/F conflicts, process_entry() can
- * clean out all the files below the directory for us.  All D/F
- * conflict cases must be handled here at the end to make sure any
- * directories that can be cleaned out, are.
- *
- * Some rename conflicts may also be handled here that don't necessarily
- * involve D/F conflicts, since the code to handle them is generic enough
- * to handle those rename conflicts with or without D/F conflicts also
- * being involved.
- */
-static int process_df_entry(struct merge_options *o,
-			    const char *path, struct stage_data *entry)
-{
-	int clean_merge = 1;
-	unsigned o_mode = entry->stages[1].mode;
-	unsigned a_mode = entry->stages[2].mode;
-	unsigned b_mode = entry->stages[3].mode;
-	unsigned char *o_sha = stage_sha(entry->stages[1].sha, o_mode);
-	unsigned char *a_sha = stage_sha(entry->stages[2].sha, a_mode);
-	unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
-
 	entry->processed = 1;
 	if (entry->rename_df_conflict_info) {
 		struct rename_df_conflict_info *conflict_info = entry->rename_df_conflict_info;
@@ -1554,24 +1463,38 @@ static int process_df_entry(struct merge_options *o,
 						    conflict_info->branch1,
 						    conflict_info->pair2,
 						    conflict_info->branch2);
-			conflict_info->dst_entry2->processed = 1;
 			break;
 		default:
 			entry->processed = 0;
 			break;
 		}
 	} else if (o_sha && (!a_sha || !b_sha)) {
-		/* Modify/delete; deleted side may have put a directory in the way */
-		char *renamed = NULL;
-		if (dir_in_way(path, !o->call_depth)) {
-			renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
+		/* Case A: Deleted in one */
+		if ((!a_sha && !b_sha) ||
+		    (!b_sha && blob_unchanged(o_sha, a_sha, normalize, path)) ||
+		    (!a_sha && blob_unchanged(o_sha, b_sha, normalize, path))) {
+			/* Deleted in both or deleted in one and
+			 * unchanged in the other */
+			if (a_sha)
+				output(o, 2, "Removing %s", path);
+			/* do not touch working file if it did not exist */
+			remove_file(o, 1, path, !a_sha);
+		} else {
+			/* Modify/delete; deleted side may have put a directory in the way */
+			char *renamed = NULL;
+			clean_merge = 0;
+			if (dir_in_way(path, !o->call_depth)) {
+				renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
+			}
+			handle_delete_modify(o, path, renamed,
+					     a_sha, a_mode, b_sha, b_mode);
+			free(renamed);
 		}
-		clean_merge = 0;
-		handle_delete_modify(o, path, renamed ? renamed : path,
-				     a_sha, a_mode, b_sha, b_mode);
-		free(renamed);
-	} else if (!o_sha && !!a_sha != !!b_sha) {
-		/* directory -> (directory, file) or <nothing> -> (directory, file) */
+	} else if ((!o_sha && a_sha && !b_sha) ||
+		   (!o_sha && !a_sha && b_sha)) {
+		/* Case B: Added in one. */
+		/* [nothing|directory] -> ([nothing|directory], file) */
+
 		const char *add_branch;
 		const char *other_branch;
 		unsigned mode;
@@ -1607,10 +1530,20 @@ static int process_df_entry(struct merge_options *o,
 			output(o, 2, "Adding %s", path);
 			update_file(o, 1, sha, mode, path);
 		}
-	} else {
-		entry->processed = 0;
-		return 1; /* not handled; assume clean until processed */
-	}
+	} else if (a_sha && b_sha) {
+		/* Case C: Added in both (check for same permissions) and */
+		/* case D: Modified in both, but differently. */
+		clean_merge = merge_content(o, entry->involved_in_rename, path,
+					    o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
+					    NULL);
+	} else if (!o_sha && !a_sha && !b_sha) {
+		/*
+		 * this entry was deleted altogether. a_mode == 0 means
+		 * we had that path and want to actively remove it.
+		 */
+		remove_file(o, 1, path, !a_mode);
+	} else
+		die("Fatal merge failure, shouldn't happen.");
 
 	return clean_merge;
 }
@@ -1658,7 +1591,7 @@ int merge_trees(struct merge_options *o,
 		re_head  = get_renames(o, head, common, head, merge, entries);
 		re_merge = get_renames(o, merge, common, head, merge, entries);
 		clean = process_renames(o, re_head, re_merge);
-		for (i = 0; i < entries->nr; i++) {
+		for (i = entries->nr-1; 0 <= i; i--) {
 			const char *path = entries->items[i].string;
 			struct stage_data *e = entries->items[i].util;
 			if (!e->processed
@@ -1666,13 +1599,6 @@ int merge_trees(struct merge_options *o,
 				clean = 0;
 		}
 		for (i = 0; i < entries->nr; i++) {
-			const char *path = entries->items[i].string;
-			struct stage_data *e = entries->items[i].util;
-			if (!e->processed
-				&& !process_df_entry(o, path, e))
-				clean = 0;
-		}
-		for (i = 0; i < entries->nr; i++) {
 			struct stage_data *e = entries->items[i].util;
 			if (!e->processed)
 				die("Unprocessed path??? %s",
-- 
1.7.6.100.gac5c1

[PATCHv2 35/56] merge-recursive: Cleanup and consolidation of rename_conflict_info

[Elijah Newren]

The consolidation of process_entry() and process_df_entry() allows us to
consolidate more code paths concerning rename conflicts, and to do
a few additional related cleanups.  It also means we are using
rename_df_conflict_info in some cases where there is no D/F conflict;
rename it to rename_conflict_info.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |  134 ++++++++++++++++++++++++++---------------------------
 1 files changed, 66 insertions(+), 68 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 74b1139..0635e1b 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -66,10 +66,11 @@ static int sha_eq(const unsigned char *a, const unsigned char *b)
 enum rename_type {
 	RENAME_NORMAL = 0,
 	RENAME_DELETE,
+	RENAME_ONE_FILE_TO_ONE,
 	RENAME_ONE_FILE_TO_TWO
 };
 
-struct rename_df_conflict_info {
+struct rename_conflict_info {
 	enum rename_type rename_type;
 	struct diff_filepair *pair1;
 	struct diff_filepair *pair2;
@@ -88,34 +89,33 @@ struct stage_data {
 		unsigned mode;
 		unsigned char sha[20];
 	} stages[4];
-	struct rename_df_conflict_info *rename_df_conflict_info;
+	struct rename_conflict_info *rename_conflict_info;
 	unsigned processed:1;
-	unsigned involved_in_rename:1;
 };
 
-static inline void setup_rename_df_conflict_info(enum rename_type rename_type,
-						 struct diff_filepair *pair1,
-						 struct diff_filepair *pair2,
-						 const char *branch1,
-						 const char *branch2,
-						 struct stage_data *dst_entry1,
-						 struct stage_data *dst_entry2)
+static inline void setup_rename_conflict_info(enum rename_type rename_type,
+					      struct diff_filepair *pair1,
+					      struct diff_filepair *pair2,
+					      const char *branch1,
+					      const char *branch2,
+					      struct stage_data *dst_entry1,
+					      struct stage_data *dst_entry2)
 {
-	struct rename_df_conflict_info *ci = xcalloc(1, sizeof(struct rename_df_conflict_info));
+	struct rename_conflict_info *ci = xcalloc(1, sizeof(struct rename_conflict_info));
 	ci->rename_type = rename_type;
 	ci->pair1 = pair1;
 	ci->branch1 = branch1;
 	ci->branch2 = branch2;
 
 	ci->dst_entry1 = dst_entry1;
-	dst_entry1->rename_df_conflict_info = ci;
+	dst_entry1->rename_conflict_info = ci;
 	dst_entry1->processed = 0;
 
 	assert(!pair2 == !dst_entry2);
 	if (dst_entry2) {
 		ci->dst_entry2 = dst_entry2;
 		ci->pair2 = pair2;
-		dst_entry2->rename_df_conflict_info = ci;
+		dst_entry2->rename_conflict_info = ci;
 	}
 }
 
@@ -954,10 +954,29 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 	/* One file was renamed in both branches, but to different names. */
 	char *del[2];
 	int delp = 0;
+	const char *src      = pair1->one->path;
 	const char *ren1_dst = pair1->two->path;
 	const char *ren2_dst = pair2->two->path;
 	const char *dst_name1 = ren1_dst;
 	const char *dst_name2 = ren2_dst;
+
+	output(o, 1, "CONFLICT (rename/rename): "
+	       "Rename \"%s\"->\"%s\" in branch \"%s\" "
+	       "rename \"%s\"->\"%s\" in \"%s\"%s",
+	       src, pair1->two->path, branch1,
+	       src, pair2->two->path, branch2,
+	       o->call_depth ? " (left unresolved)" : "");
+	if (o->call_depth) {
+		/*
+		 * FIXME: Why remove file from cache, and then
+		 * immediately readd it?  Why not just overwrite using
+		 * update_file only?  Also...this is buggy for
+		 * rename/add-source situations...
+		 */
+		remove_file_from_cache(src);
+		update_file(o, 0, pair1->one->sha1, pair1->one->mode, src);
+	}
+
 	if (dir_in_way(ren1_dst, !o->call_depth)) {
 		dst_name1 = del[delp++] = unique_path(o, ren1_dst, branch1);
 		output(o, 1, "%s is a directory in %s adding as %s instead",
@@ -1098,20 +1117,16 @@ static int process_renames(struct merge_options *o,
 		if (ren2) {
 			const char *ren2_src = ren2->pair->one->path;
 			const char *ren2_dst = ren2->pair->two->path;
+			enum rename_type rename_type;
 			/* Renamed in 1 and renamed in 2 */
 			if (strcmp(ren1_src, ren2_src) != 0)
 				die("ren1.src != ren2.src");
 			ren2->dst_entry->processed = 1;
 			ren2->processed = 1;
 			if (strcmp(ren1_dst, ren2_dst) != 0) {
-				setup_rename_df_conflict_info(RENAME_ONE_FILE_TO_TWO,
-							      ren1->pair,
-							      ren2->pair,
-							      branch1,
-							      branch2,
-							      ren1->dst_entry,
-							      ren2->dst_entry);
+				rename_type = RENAME_ONE_FILE_TO_TWO;
 			} else {
+				rename_type = RENAME_ONE_FILE_TO_ONE;
 				/* BUG: We should only remove ren1_src in
 				 * the base stage (think of rename +
 				 * add-source cases).
@@ -1121,8 +1136,14 @@ static int process_renames(struct merge_options *o,
 					     ren1->pair->one,
 					     ren1->pair->two,
 					     ren2->pair->two);
-				ren1->dst_entry->involved_in_rename = 1;
 			}
+			setup_rename_conflict_info(rename_type,
+						   ren1->pair,
+						   ren2->pair,
+						   branch1,
+						   branch2,
+						   ren1->dst_entry,
+						   ren2->dst_entry);
 		} else {
 			/* Renamed in 1, maybe changed in 2 */
 			struct string_list_item *item;
@@ -1153,19 +1174,13 @@ static int process_renames(struct merge_options *o,
 			try_merge = 0;
 
 			if (sha_eq(src_other.sha1, null_sha1)) {
-				if (dir_in_way(ren1_dst, 0 /*check_wc*/)) {
-					ren1->dst_entry->processed = 0;
-					setup_rename_df_conflict_info(RENAME_DELETE,
-								      ren1->pair,
-								      NULL,
-								      branch1,
-								      branch2,
-								      ren1->dst_entry,
-								      NULL);
-				} else {
-					clean_merge = 0;
-					conflict_rename_delete(o, ren1->pair, branch1, branch2);
-				}
+				setup_rename_conflict_info(RENAME_DELETE,
+							   ren1->pair,
+							   NULL,
+							   branch1,
+							   branch2,
+							   ren1->dst_entry,
+							   NULL);
 			} else if ((item = string_list_lookup(renames2Dst, ren1_dst))) {
 				char *ren2_src, *ren2_dst;
 				ren2 = item->util;
@@ -1239,16 +1254,13 @@ static int process_renames(struct merge_options *o,
 					a = &src_other;
 				}
 				update_entry(ren1->dst_entry, one, a, b);
-				ren1->dst_entry->involved_in_rename = 1;
-				if (dir_in_way(ren1_dst, 0 /*check_wc*/)) {
-					setup_rename_df_conflict_info(RENAME_NORMAL,
-								      ren1->pair,
-								      NULL,
-								      branch1,
-								      NULL,
-								      ren1->dst_entry,
-								      NULL);
-				}
+				setup_rename_conflict_info(RENAME_NORMAL,
+							   ren1->pair,
+							   NULL,
+							   branch1,
+							   NULL,
+							   ren1->dst_entry,
+							   NULL);
 			}
 		}
 	}
@@ -1336,12 +1348,11 @@ static void handle_delete_modify(struct merge_options *o,
 }
 
 static int merge_content(struct merge_options *o,
-			 unsigned involved_in_rename,
 			 const char *path,
 			 unsigned char *o_sha, int o_mode,
 			 unsigned char *a_sha, int a_mode,
 			 unsigned char *b_sha, int b_mode,
-			 const char *df_rename_conflict_branch)
+			 struct rename_conflict_info *rename_conflict_info)
 {
 	const char *reason = "content";
 	struct merge_file_info mfi;
@@ -1361,8 +1372,7 @@ static int merge_content(struct merge_options *o,
 	b.mode = b_mode;
 
 	mfi = merge_file(o, &one, &a, &b, o->branch1, o->branch2);
-	if (df_rename_conflict_branch &&
-	    dir_in_way(path, !o->call_depth)) {
+	if (rename_conflict_info && dir_in_way(path, !o->call_depth)) {
 		df_conflict_remains = 1;
 	}
 
@@ -1377,7 +1387,7 @@ static int merge_content(struct merge_options *o,
 			reason = "submodule";
 		output(o, 1, "CONFLICT (%s): Merge conflict in %s",
 				reason, path);
-		if (involved_in_rename && !df_conflict_remains)
+		if (rename_conflict_info && !df_conflict_remains)
 			update_stages(path, &one, &a, &b);
 	}
 
@@ -1400,7 +1410,7 @@ static int merge_content(struct merge_options *o,
 			}
 
 		}
-		new_path = unique_path(o, path, df_rename_conflict_branch);
+		new_path = unique_path(o, path, rename_conflict_info->branch1);
 		output(o, 1, "Adding as %s instead", new_path);
 		update_file(o, 0, mfi.sha, mfi.mode, new_path);
 		free(new_path);
@@ -1430,14 +1440,14 @@ static int process_entry(struct merge_options *o,
 	unsigned char *b_sha = stage_sha(entry->stages[3].sha, b_mode);
 
 	entry->processed = 1;
-	if (entry->rename_df_conflict_info) {
-		struct rename_df_conflict_info *conflict_info = entry->rename_df_conflict_info;
-		char *src;
+	if (entry->rename_conflict_info) {
+		struct rename_conflict_info *conflict_info = entry->rename_conflict_info;
 		switch (conflict_info->rename_type) {
 		case RENAME_NORMAL:
-			clean_merge = merge_content(o, entry->involved_in_rename, path,
+		case RENAME_ONE_FILE_TO_ONE:
+			clean_merge = merge_content(o, path,
 						    o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
-						    conflict_info->branch1);
+						    conflict_info);
 			break;
 		case RENAME_DELETE:
 			clean_merge = 0;
@@ -1446,19 +1456,7 @@ static int process_entry(struct merge_options *o,
 					       conflict_info->branch2);
 			break;
 		case RENAME_ONE_FILE_TO_TWO:
-			src = conflict_info->pair1->one->path;
 			clean_merge = 0;
-			output(o, 1, "CONFLICT (rename/rename): "
-			       "Rename \"%s\"->\"%s\" in branch \"%s\" "
-			       "rename \"%s\"->\"%s\" in \"%s\"%s",
-			       src, conflict_info->pair1->two->path, conflict_info->branch1,
-			       src, conflict_info->pair2->two->path, conflict_info->branch2,
-			       o->call_depth ? " (left unresolved)" : "");
-			if (o->call_depth) {
-				remove_file_from_cache(src);
-				update_file(o, 0, conflict_info->pair1->one->sha1,
-					    conflict_info->pair1->one->mode, src);
-			}
 			conflict_rename_rename_1to2(o, conflict_info->pair1,
 						    conflict_info->branch1,
 						    conflict_info->pair2,
@@ -1533,7 +1531,7 @@ static int process_entry(struct merge_options *o,
 	} else if (a_sha && b_sha) {
 		/* Case C: Added in both (check for same permissions) and */
 		/* case D: Modified in both, but differently. */
-		clean_merge = merge_content(o, entry->involved_in_rename, path,
+		clean_merge = merge_content(o, path,
 					    o_sha, o_mode, a_sha, a_mode, b_sha, b_mode,
 					    NULL);
 	} else if (!o_sha && !a_sha && !b_sha) {
-- 
1.7.6.100.gac5c1

[PATCHv2 36/56] merge-recursive: Provide more info in conflict markers with file renames

[Elijah Newren]

Whenever there are merge conflicts in file contents, we would mark the
different sides of the conflict with the two branches being merged.
However, when there is a rename involved as well, the branchname is not
sufficient to specify where the conflicting content came from.  In such
cases, mark the two sides of the conflict with branchname:filename rather
than just branchname.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1: Fix bug where I could get filenames from two
  branches reversed depending on the direction of the merge.

 merge-recursive.c                    |   28 +++++++++++-
 t/t6022-merge-rename.sh              |   75 ++++++++++++++++++++++++++++++++--
 t/t6042-merge-rename-corner-cases.sh |    2 +-
 3 files changed, 97 insertions(+), 8 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 0635e1b..bc99f1a 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1355,6 +1355,7 @@ static int merge_content(struct merge_options *o,
 			 struct rename_conflict_info *rename_conflict_info)
 {
 	const char *reason = "content";
+	char *side1 = NULL, *side2 = NULL;
 	struct merge_file_info mfi;
 	struct diff_filespec one, a, b;
 	unsigned df_conflict_remains = 0;
@@ -1371,10 +1372,31 @@ static int merge_content(struct merge_options *o,
 	hashcpy(b.sha1, b_sha);
 	b.mode = b_mode;
 
-	mfi = merge_file(o, &one, &a, &b, o->branch1, o->branch2);
-	if (rename_conflict_info && dir_in_way(path, !o->call_depth)) {
-		df_conflict_remains = 1;
+	if (rename_conflict_info) {
+		const char *path1, *path2;
+		struct diff_filepair *pair1 = rename_conflict_info->pair1;
+
+		path1 = (o->branch1 == rename_conflict_info->branch1) ?
+			pair1->two->path : pair1->one->path;
+		/* If rename_conflict_info->pair2 != NULL, we are in
+		 * RENAME_ONE_FILE_TO_ONE case.  Otherwise, we have a
+		 * normal rename.
+		 */
+		path2 = (rename_conflict_info->pair2 ||
+			 o->branch2 == rename_conflict_info->branch1) ?
+			pair1->two->path : pair1->one->path;
+		side1 = xmalloc(strlen(o->branch1) + strlen(path1) + 2);
+		side2 = xmalloc(strlen(o->branch2) + strlen(path2) + 2);
+		sprintf(side1, "%s:%s", o->branch1, path1);
+		sprintf(side2, "%s:%s", o->branch2, path2);
+
+		if (dir_in_way(path, !o->call_depth))
+			df_conflict_remains = 1;
 	}
+	mfi = merge_file(o, &one, &a, &b,
+			 side1 ? side1 : o->branch1, side2 ? side2 : o->branch2);
+	free(side1);
+	free(side2);
 
 	if (mfi.clean && !df_conflict_remains &&
 	    sha_eq(mfi.sha, a_sha) && mfi.mode == a.mode)
diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index fcc1d4c..4695cbc 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -351,11 +351,11 @@ cat >expected <<\EOF &&
 8
 9
 10
-<<<<<<< HEAD
+<<<<<<< HEAD:dir
 12
 =======
 11
->>>>>>> dir-not-in-way
+>>>>>>> dir-not-in-way:sub/file
 EOF
 
 test_expect_success 'Rename+D/F conflict; renamed file cannot merge, dir not in way' '
@@ -405,11 +405,11 @@ cat >expected <<\EOF &&
 8
 9
 10
-<<<<<<< HEAD
+<<<<<<< HEAD:sub/file
 11
 =======
 12
->>>>>>> renamed-file-has-conflicts
+>>>>>>> renamed-file-has-conflicts:dir
 EOF
 
 test_expect_success 'Same as previous, but merged other way' '
@@ -700,4 +700,71 @@ test_expect_success 'merge rename + small change' '
 	test $(git rev-parse HEAD:renamed_file) = $(git rev-parse HEAD~1:file)
 '
 
+test_expect_success 'setup for use of extended merge markers' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n6\n7\n8\n" >original_file &&
+	git add original_file &&
+	git commit -mA &&
+
+	git checkout -b rename &&
+	echo 9 >>original_file &&
+	git add original_file &&
+	git mv original_file renamed_file &&
+	git commit -mB &&
+
+	git checkout master &&
+	echo 8.5 >>original_file &&
+	git add original_file &&
+	git commit -mC
+'
+
+cat >expected <<\EOF &&
+1
+2
+3
+4
+5
+6
+7
+8
+<<<<<<< HEAD:renamed_file
+9
+=======
+8.5
+>>>>>>> master^0:original_file
+EOF
+
+test_expect_success 'merge master into rename has correct extended markers' '
+	git checkout rename^0 &&
+	test_must_fail git merge -s recursive master^0 &&
+	test_cmp expected renamed_file
+'
+
+cat >expected <<\EOF &&
+1
+2
+3
+4
+5
+6
+7
+8
+<<<<<<< HEAD:original_file
+8.5
+=======
+9
+>>>>>>> rename^0:renamed_file
+EOF
+
+test_expect_success 'merge rename into master has correct extended markers' '
+	git reset --hard &&
+	git checkout master^0 &&
+	test_must_fail git merge -s recursive rename^0 &&
+	test_cmp expected renamed_file
+'
+
 test_done
diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 968055d..bfc3179 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -258,7 +258,7 @@ test_expect_success 'rename/directory conflict + clean content merge' '
 	test -f newfile~HEAD
 '
 
-test_expect_failure 'rename/directory conflict + content merge conflict' '
+test_expect_success 'rename/directory conflict + content merge conflict' '
 	git reset --hard &&
 	git reset --hard &&
 	git clean -fdqx &&
-- 
1.7.6.100.gac5c1

[PATCHv2 37/56] merge-recursive: When we detect we can skip an update, actually skip it

[Elijah Newren]

In 882fd11 (merge-recursive: Delay content merging for renames 2010-09-20),
there was code that checked for whether we could skip updating a file in
the working directory, based on whether the merged version matched the
current working copy.  Due to the desire to handle directory/file conflicts
that were resolvable, that commit deferred content merging by first
updating the index with the unmerged entries and then moving the actual
merging (along with the skip-the-content-update check) to another function
that ran later in the merge process.  As part moving the content merging
code, a bug was introduced such that although the message about skipping
the update would be printed (whenever GIT_MERGE_VERBOSITY was sufficiently
high), the file would be unconditionally updated in the working copy
anyway.

When we detect that the file does not need to be updated in the working
copy, update the index appropriately and then return early before updating
the working copy.

Note that there was a similar change in b2c8c0a (merge-recursive: When we
detect we can skip an update, actually skip it 2011-02-28), but it was
reverted by 6db4105 (Revert "Merge branch 'en/merge-recursive'"
2011-05-19) since it did not fix both of the relevant types of unnecessary
update breakages and, worse, it made use of some band-aids that caused
other problems.  The reason this change works is due to the changes earlier
in this series to (a) record_df_conflict_files instead of just unlinking
them early, (b) allowing make_room_for_path() to remove D/F entries,
(c) the splitting of update_stages_and_entry() to have its functionality
called at different points, and (d) making the pathnames of the files
involved in the merge available to merge_content().

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Changes since v1:
  (1) Moved to later in the series (used to be patch #29).
  (2) Changed the "was_tracked" logic to use information about what
      paths were involved in renames to determine whether the file
      really 'was tracked' before the merge started.  Thus, the code
      is now about checking "!path_renamed_outside_HEAD" rather than
      "was_tracked(path)" (The latter was problematic because it tells
      us whether path was tracked once unpack_trees finishes() rather
      than whether the path was tracked before the merge started.)
  (3) Added another minor tweak to get the expected "Skipped" messages
      that t6022.12 expects.  We need to report that we are skipping
      the update even if the content is only on the other side of the
      merge and we need to update the working directory contents.  At
      least, that's what the author of t6022.12 who put the message in
      explicitly expected.

 merge-recursive.c       |   19 ++++++++++++++++---
 t/t6022-merge-rename.sh |    4 ++--
 2 files changed, 18 insertions(+), 5 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index bc99f1a..ccf71d3 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1356,6 +1356,7 @@ static int merge_content(struct merge_options *o,
 {
 	const char *reason = "content";
 	char *side1 = NULL, *side2 = NULL;
+	const char *path1 = NULL, *path2 = NULL;
 	struct merge_file_info mfi;
 	struct diff_filespec one, a, b;
 	unsigned df_conflict_remains = 0;
@@ -1373,7 +1374,6 @@ static int merge_content(struct merge_options *o,
 	b.mode = b_mode;
 
 	if (rename_conflict_info) {
-		const char *path1, *path2;
 		struct diff_filepair *pair1 = rename_conflict_info->pair1;
 
 		path1 = (o->branch1 == rename_conflict_info->branch1) ?
@@ -1399,9 +1399,22 @@ static int merge_content(struct merge_options *o,
 	free(side2);
 
 	if (mfi.clean && !df_conflict_remains &&
-	    sha_eq(mfi.sha, a_sha) && mfi.mode == a.mode)
+	    sha_eq(mfi.sha, a_sha) && mfi.mode == a_mode) {
+		int path_renamed_outside_HEAD;
 		output(o, 3, "Skipped %s (merged same as existing)", path);
-	else
+		/*
+		 * The content merge resulted in the same file contents we
+		 * already had.  We can return early if those file contents
+		 * are recorded at the correct path (which may not be true
+		 * if the merge involves a rename).
+		 */
+		path_renamed_outside_HEAD = !path2 || !strcmp(path, path2);
+		if (!path_renamed_outside_HEAD) {
+			add_cacheinfo(mfi.mode, mfi.sha, path,
+				      0 /*stage*/, 1 /*refresh*/, 0 /*options*/);
+			return mfi.clean;
+		}
+	} else
 		output(o, 2, "Auto-merging %s", path);
 
 	if (!mfi.clean) {
diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 4695cbc..d96d3c5 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -631,7 +631,7 @@ test_expect_success 'setup avoid unnecessary update, normal rename' '
 	git commit -m "Random, unrelated changes"
 '
 
-test_expect_failure 'avoid unnecessary update, normal rename' '
+test_expect_success 'avoid unnecessary update, normal rename' '
 	git checkout -q avoid-unnecessary-update-1^0 &&
 	test-chmtime =1000000000 rename &&
 	test-chmtime -v +0 rename >expect &&
@@ -664,7 +664,7 @@ test_expect_success 'setup to test avoiding unnecessary update, with D/F conflic
 	git commit -m "Only unrelated changes"
 '
 
-test_expect_failure 'avoid unnecessary update, with D/F conflict' '
+test_expect_success 'avoid unnecessary update, with D/F conflict' '
 	git checkout -q avoid-unnecessary-update-2^0 &&
 	test-chmtime =1000000000 df &&
 	test-chmtime -v +0 df >expect &&
-- 
1.7.6.100.gac5c1

[PATCHv2 38/56] merge-recursive: Fix modify/delete resolution in the recursive case

[Elijah Newren]

When o->call_depth>0 and we have conflicts, we try to find "middle ground"
when creating the virtual merge base.  In the case of content conflicts,
this can be done by doing a three-way content merge and using the result.
In all parts where the three-way content merge is clean, it is the correct
middle ground, and in parts where it conflicts there is no middle ground
but the conflict markers provide a good compromise since they are unlikely
to accidentally match any further changes.

In the case of a modify/delete conflict, we cannot do the same thing.
Accepting either endpoint as the resolution for the virtual merge base
runs the risk that when handling the non-recursive case we will silently
accept one person's resolution over another without flagging a conflict.
In this case, the closest "middle ground" we have is actually the merge
base of the candidate merge bases.  (We could alternatively attempt a
three way content merge using an empty file in place of the deleted file,
but that seems to be more work than necessary.)

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                 |   38 +++++++++++++++++++++++-------------
 t/t6036-recursive-corner-cases.sh |    4 +-
 2 files changed, 26 insertions(+), 16 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index ccf71d3..a0dc0bf 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1324,27 +1324,42 @@ error_return:
 
 static void handle_delete_modify(struct merge_options *o,
 				 const char *path,
-				 const char *new_path,
+				 unsigned char *o_sha, int o_mode,
 				 unsigned char *a_sha, int a_mode,
 				 unsigned char *b_sha, int b_mode)
 {
-	if (!a_sha) {
+	char *renamed = NULL;
+	if (dir_in_way(path, !o->call_depth)) {
+		renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
+	}
+
+	if (o->call_depth) {
+		/*
+		 * We cannot arbitrarily accept either a_sha or b_sha as
+		 * correct; since there is no true "middle point" between
+		 * them, simply reuse the base version for virtual merge base.
+		 */
+		remove_file_from_cache(path);
+		update_file(o, 0, o_sha, o_mode, renamed ? renamed : path);
+	} else if (!a_sha) {
 		output(o, 1, "CONFLICT (delete/modify): %s deleted in %s "
 		       "and modified in %s. Version %s of %s left in tree%s%s.",
 		       path, o->branch1,
 		       o->branch2, o->branch2, path,
-		       NULL == new_path ? "" : " at ",
-		       NULL == new_path ? "" : new_path);
-		update_file(o, 0, b_sha, b_mode, new_path ? new_path : path);
+		       NULL == renamed ? "" : " at ",
+		       NULL == renamed ? "" : renamed);
+		update_file(o, 0, b_sha, b_mode, renamed ? renamed : path);
 	} else {
 		output(o, 1, "CONFLICT (delete/modify): %s deleted in %s "
 		       "and modified in %s. Version %s of %s left in tree%s%s.",
 		       path, o->branch2,
 		       o->branch1, o->branch1, path,
-		       NULL == new_path ? "" : " at ",
-		       NULL == new_path ? "" : new_path);
-		update_file(o, 0, a_sha, a_mode, new_path ? new_path : path);
+		       NULL == renamed ? "" : " at ",
+		       NULL == renamed ? "" : renamed);
+		update_file(o, 0, a_sha, a_mode, renamed ? renamed : path);
 	}
+	free(renamed);
+
 }
 
 static int merge_content(struct merge_options *o,
@@ -1514,14 +1529,9 @@ static int process_entry(struct merge_options *o,
 			remove_file(o, 1, path, !a_sha);
 		} else {
 			/* Modify/delete; deleted side may have put a directory in the way */
-			char *renamed = NULL;
 			clean_merge = 0;
-			if (dir_in_way(path, !o->call_depth)) {
-				renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
-			}
-			handle_delete_modify(o, path, renamed,
+			handle_delete_modify(o, path, o_sha, o_mode,
 					     a_sha, a_mode, b_sha, b_mode);
-			free(renamed);
 		}
 	} else if ((!o_sha && a_sha && !b_sha) ||
 		   (!o_sha && !a_sha && b_sha)) {
diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index b046e1b..314fdae 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -296,7 +296,7 @@ test_expect_success 'setup criss-cross + modify/delete resolved differently' '
 	git tag E
 '
 
-test_expect_failure 'git detects conflict merging criss-cross+modify/delete' '
+test_expect_success 'git detects conflict merging criss-cross+modify/delete' '
 	git checkout D^0 &&
 
 	test_must_fail git merge -s recursive E^0 &&
@@ -308,7 +308,7 @@ test_expect_failure 'git detects conflict merging criss-cross+modify/delete' '
 	test $(git rev-parse :2:file) = $(git rev-parse B:file)
 '
 
-test_expect_failure 'git detects conflict merging criss-cross+modify/delete, reverse direction' '
+test_expect_success 'git detects conflict merging criss-cross+modify/delete, reverse direction' '
 	git reset --hard &&
 	git checkout E^0 &&
 
-- 
1.7.6.100.gac5c1

[PATCHv2 39/56] merge-recursive: Introduce a merge_file convenience function

[Elijah Newren]

merge_file previously required diff_filespec arguments, but all callers
only had sha1s and modes.  Rename merge_file to merge_file_1 and introduce
a new merge_file convenience function which takes the sha1s and modes and
creates the temporary diff_filespec variables needed to call merge_file_1.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   72 +++++++++++++++++++++++++++-------------------------
 1 files changed, 37 insertions(+), 35 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index a0dc0bf..76a451c 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -846,12 +846,12 @@ static int merge_3way(struct merge_options *o,
 	return merge_status;
 }
 
-static struct merge_file_info merge_file(struct merge_options *o,
-					 const struct diff_filespec *one,
-					 const struct diff_filespec *a,
-					 const struct diff_filespec *b,
-					 const char *branch1,
-					 const char *branch2)
+static struct merge_file_info merge_file_1(struct merge_options *o,
+					   const struct diff_filespec *one,
+					   const struct diff_filespec *a,
+					   const struct diff_filespec *b,
+					   const char *branch1,
+					   const char *branch2)
 {
 	struct merge_file_info result;
 	result.merge = 0;
@@ -920,6 +920,26 @@ static struct merge_file_info merge_file(struct merge_options *o,
 	return result;
 }
 
+static struct merge_file_info merge_file(struct merge_options *o,
+					 const char *path,
+					 const unsigned char *o_sha, int o_mode,
+					 const unsigned char *a_sha, int a_mode,
+					 const unsigned char *b_sha, int b_mode,
+					 const char *branch1,
+					 const char *branch2)
+{
+	struct diff_filespec one, a, b;
+
+	one.path = a.path = b.path = (char *)path;
+	hashcpy(one.sha1, o_sha);
+	one.mode = o_mode;
+	hashcpy(a.sha1, a_sha);
+	a.mode = a_mode;
+	hashcpy(b.sha1, b_sha);
+	b.mode = b_mode;
+	return merge_file_1(o, &one, &a, &b, branch1, branch2);
+}
+
 static void conflict_rename_delete(struct merge_options *o,
 				   struct diff_filepair *pair,
 				   const char *rename_branch,
@@ -1017,16 +1037,10 @@ static void conflict_rename_rename_2to1(struct merge_options *o,
 	/* Two files were renamed to the same thing. */
 	if (o->call_depth) {
 		struct merge_file_info mfi;
-		struct diff_filespec one, a, b;
-
-		one.path = a.path = b.path = path;
-		hashcpy(one.sha1, null_sha1);
-		one.mode = 0;
-		hashcpy(a.sha1, ren1->pair->two->sha1);
-		a.mode = ren1->pair->two->mode;
-		hashcpy(b.sha1, ren2->pair->two->sha1);
-		b.mode = ren2->pair->two->mode;
-		mfi = merge_file(o, &one, &a, &b, branch1, branch2);
+		mfi = merge_file(o, path, null_sha1, 0,
+				 ren1->pair->two->sha1, ren1->pair->two->mode,
+				 ren2->pair->two->sha1, ren2->pair->two->mode,
+				 branch1, branch2);
 		output(o, 1, "Adding merged %s", path);
 		update_file(o, 0, mfi.sha, mfi.mode, path);
 	} else {
@@ -1213,24 +1227,12 @@ static int process_renames(struct merge_options *o,
 				       ren1_dst, branch2);
 				if (o->call_depth) {
 					struct merge_file_info mfi;
-					struct diff_filespec one, a, b;
-
-					one.path = a.path = b.path =
-						(char *)ren1_dst;
-					hashcpy(one.sha1, null_sha1);
-					one.mode = 0;
-					hashcpy(a.sha1, ren1->pair->two->sha1);
-					a.mode = ren1->pair->two->mode;
-					hashcpy(b.sha1, dst_other.sha1);
-					b.mode = dst_other.mode;
-					mfi = merge_file(o, &one, &a, &b,
-							 branch1,
-							 branch2);
+					mfi = merge_file(o, ren1_dst, null_sha1, 0,
+							 ren1->pair->two->sha1, ren1->pair->two->mode,
+							 dst_other.sha1, dst_other.mode,
+							 branch1, branch2);
 					output(o, 1, "Adding merged %s", ren1_dst);
-					update_file(o, 0,
-						    mfi.sha,
-						    mfi.mode,
-						    ren1_dst);
+					update_file(o, 0, mfi.sha, mfi.mode, ren1_dst);
 					try_merge = 0;
 				} else {
 					char *new_path = unique_path(o, ren1_dst, branch2);
@@ -1408,8 +1410,8 @@ static int merge_content(struct merge_options *o,
 		if (dir_in_way(path, !o->call_depth))
 			df_conflict_remains = 1;
 	}
-	mfi = merge_file(o, &one, &a, &b,
-			 side1 ? side1 : o->branch1, side2 ? side2 : o->branch2);
+	mfi = merge_file_1(o, &one, &a, &b,
+			   side1 ? side1 : o->branch1, side2 ? side2 : o->branch2);
 	free(side1);
 	free(side2);
 
-- 
1.7.6.100.gac5c1

[PATCHv2 40/56] merge-recursive: Fix rename/rename(1to2) resolution for virtual merge base

[Elijah Newren]

When renaming one file to two files, we really should be doing a content
merge.  Also, in the recursive case, undoing the renames and recording the
merged file in the index with the source of the rename (while deleting
both destinations) allows the renames to be re-detected in the
non-recursive merge and will result in fewer spurious conflicts.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                 |   30 +++++++++++++-----------------
 t/t6036-recursive-corner-cases.sh |    2 +-
 2 files changed, 14 insertions(+), 18 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 76a451c..58a6ce3 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -986,17 +986,6 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 	       src, pair1->two->path, branch1,
 	       src, pair2->two->path, branch2,
 	       o->call_depth ? " (left unresolved)" : "");
-	if (o->call_depth) {
-		/*
-		 * FIXME: Why remove file from cache, and then
-		 * immediately readd it?  Why not just overwrite using
-		 * update_file only?  Also...this is buggy for
-		 * rename/add-source situations...
-		 */
-		remove_file_from_cache(src);
-		update_file(o, 0, pair1->one->sha1, pair1->one->mode, src);
-	}
-
 	if (dir_in_way(ren1_dst, !o->call_depth)) {
 		dst_name1 = del[delp++] = unique_path(o, ren1_dst, branch1);
 		output(o, 1, "%s is a directory in %s adding as %s instead",
@@ -1008,14 +997,21 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 		       ren2_dst, branch1, dst_name2);
 	}
 	if (o->call_depth) {
-		remove_file_from_cache(dst_name1);
-		remove_file_from_cache(dst_name2);
+		struct merge_file_info mfi;
+		mfi = merge_file(o, src,
+				 pair1->one->sha1, pair1->one->mode,
+				 pair1->two->sha1, pair1->two->mode,
+				 pair2->two->sha1, pair2->two->mode,
+				 branch1, branch2);
 		/*
-		 * Uncomment to leave the conflicting names in the resulting tree
-		 *
-		 * update_file(o, 0, pair1->two->sha1, pair1->two->mode, dst_name1);
-		 * update_file(o, 0, pair2->two->sha1, pair2->two->mode, dst_name2);
+		 * FIXME: For rename/add-source conflicts (if we could detect
+		 * such), this is wrong.  We should instead find a unique
+		 * pathname and then either rename the add-source file to that
+		 * unique path, or use that unique path instead of src here.
 		 */
+		update_file(o, 0, mfi.sha, mfi.mode, src);
+		remove_file_from_cache(ren1_dst);
+		remove_file_from_cache(ren2_dst);
 	} else {
 		update_stages(ren1_dst, NULL, pair1->two, NULL);
 		update_stages(ren2_dst, NULL, NULL, pair2->two);
diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 314fdae..5a7af0c 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -633,7 +633,7 @@ test_expect_success 'setup rename/rename(1to2)/modify followed by what looks lik
 	git tag E
 '
 
-test_expect_failure 'handle rename/rename(1to2)/modify followed by what looks like rename/rename(2to1)/modify' '
+test_expect_success 'handle rename/rename(1to2)/modify followed by what looks like rename/rename(2to1)/modify' '
 	git checkout D^0 &&
 
 	git merge -s recursive E^0 &&
-- 
1.7.6.100.gac5c1

[PATCHv2 41/56] merge-recursive: Small cleanups for conflict_rename_rename_1to2

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   60 +++++++++++++++++++++++-----------------------------
 1 files changed, 27 insertions(+), 33 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 58a6ce3..8b65051 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -966,58 +966,55 @@ static void conflict_rename_delete(struct merge_options *o,
 }
 
 static void conflict_rename_rename_1to2(struct merge_options *o,
-					struct diff_filepair *pair1,
-					const char *branch1,
-					struct diff_filepair *pair2,
-					const char *branch2)
+					struct rename_conflict_info *ci)
 {
 	/* One file was renamed in both branches, but to different names. */
+	struct diff_filespec *one = ci->pair1->one;
+	struct diff_filespec *a = ci->pair1->two;
+	struct diff_filespec *b = ci->pair2->two;
+	const char *dst_name_a = a->path;
+	const char *dst_name_b = b->path;
 	char *del[2];
 	int delp = 0;
-	const char *src      = pair1->one->path;
-	const char *ren1_dst = pair1->two->path;
-	const char *ren2_dst = pair2->two->path;
-	const char *dst_name1 = ren1_dst;
-	const char *dst_name2 = ren2_dst;
 
 	output(o, 1, "CONFLICT (rename/rename): "
 	       "Rename \"%s\"->\"%s\" in branch \"%s\" "
 	       "rename \"%s\"->\"%s\" in \"%s\"%s",
-	       src, pair1->two->path, branch1,
-	       src, pair2->two->path, branch2,
+	       one->path, a->path, ci->branch1,
+	       one->path, b->path, ci->branch2,
 	       o->call_depth ? " (left unresolved)" : "");
-	if (dir_in_way(ren1_dst, !o->call_depth)) {
-		dst_name1 = del[delp++] = unique_path(o, ren1_dst, branch1);
+	if (dir_in_way(a->path, !o->call_depth)) {
+		dst_name_a = del[delp++] = unique_path(o, a->path, ci->branch1);
 		output(o, 1, "%s is a directory in %s adding as %s instead",
-		       ren1_dst, branch2, dst_name1);
+		       a->path, ci->branch2, dst_name_a);
 	}
-	if (dir_in_way(ren2_dst, !o->call_depth)) {
-		dst_name2 = del[delp++] = unique_path(o, ren2_dst, branch2);
+	if (dir_in_way(b->path, !o->call_depth)) {
+		dst_name_b = del[delp++] = unique_path(o, b->path, ci->branch2);
 		output(o, 1, "%s is a directory in %s adding as %s instead",
-		       ren2_dst, branch1, dst_name2);
+		       b->path, ci->branch1, dst_name_b);
 	}
 	if (o->call_depth) {
 		struct merge_file_info mfi;
-		mfi = merge_file(o, src,
-				 pair1->one->sha1, pair1->one->mode,
-				 pair1->two->sha1, pair1->two->mode,
-				 pair2->two->sha1, pair2->two->mode,
-				 branch1, branch2);
+		mfi = merge_file(o, one->path,
+				 one->sha1, one->mode,
+				 a->sha1, a->mode,
+				 b->sha1, b->mode,
+				 ci->branch1, ci->branch2);
 		/*
 		 * FIXME: For rename/add-source conflicts (if we could detect
 		 * such), this is wrong.  We should instead find a unique
 		 * pathname and then either rename the add-source file to that
 		 * unique path, or use that unique path instead of src here.
 		 */
-		update_file(o, 0, mfi.sha, mfi.mode, src);
-		remove_file_from_cache(ren1_dst);
-		remove_file_from_cache(ren2_dst);
+		update_file(o, 0, mfi.sha, mfi.mode, one->path);
+		remove_file_from_cache(a->path);
+		remove_file_from_cache(b->path);
 	} else {
-		update_stages(ren1_dst, NULL, pair1->two, NULL);
-		update_stages(ren2_dst, NULL, NULL, pair2->two);
+		update_stages(a->path, NULL, a, NULL);
+		update_stages(b->path, NULL, NULL, b);
 
-		update_file(o, 0, pair1->two->sha1, pair1->two->mode, dst_name1);
-		update_file(o, 0, pair2->two->sha1, pair2->two->mode, dst_name2);
+		update_file(o, 0, a->sha1, a->mode, dst_name_a);
+		update_file(o, 0, b->sha1, b->mode, dst_name_b);
 	}
 	while (delp--)
 		free(del[delp]);
@@ -1505,10 +1502,7 @@ static int process_entry(struct merge_options *o,
 			break;
 		case RENAME_ONE_FILE_TO_TWO:
 			clean_merge = 0;
-			conflict_rename_rename_1to2(o, conflict_info->pair1,
-						    conflict_info->branch1,
-						    conflict_info->pair2,
-						    conflict_info->branch2);
+			conflict_rename_rename_1to2(o, conflict_info);
 			break;
 		default:
 			entry->processed = 0;
-- 
1.7.6.100.gac5c1

[PATCHv2 42/56] merge-recursive: Defer rename/rename(2to1) handling until process_entry

[Elijah Newren]

This puts the code for the different types of double rename conflicts
closer together (fewer lines of other code separating the two paths) and
increases similarity between how they are handled.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |  104 +++++++++++++++++++++++++++++++---------------------
 1 files changed, 62 insertions(+), 42 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 8b65051..77c2c41 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -67,7 +67,8 @@ enum rename_type {
 	RENAME_NORMAL = 0,
 	RENAME_DELETE,
 	RENAME_ONE_FILE_TO_ONE,
-	RENAME_ONE_FILE_TO_TWO
+	RENAME_ONE_FILE_TO_TWO,
+	RENAME_TWO_FILES_TO_ONE
 };
 
 struct rename_conflict_info {
@@ -1021,32 +1022,40 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 }
 
 static void conflict_rename_rename_2to1(struct merge_options *o,
-					struct rename *ren1,
-					const char *branch1,
-					struct rename *ren2,
-					const char *branch2)
+					struct rename_conflict_info *ci)
 {
-	char *path = ren1->pair->two->path; /* same as ren2->pair->two->path */
-	/* Two files were renamed to the same thing. */
+	/* Two files, a & b, were renamed to the same thing, c. */
+	struct diff_filespec *a = ci->pair1->one;
+	struct diff_filespec *b = ci->pair2->one;
+	struct diff_filespec *c1 = ci->pair1->two;
+	struct diff_filespec *c2 = ci->pair2->two;
+	char *path = c1->path; /* == c2->path */
+
+	output(o, 1, "CONFLICT (rename/rename): "
+	       "Rename %s->%s in %s. "
+	       "Rename %s->%s in %s",
+	       a->path, c1->path, ci->branch1,
+	       b->path, c2->path, ci->branch2);
+
+	remove_file(o, 1, a->path, would_lose_untracked(a->path));
+	remove_file(o, 1, b->path, would_lose_untracked(b->path));
+
 	if (o->call_depth) {
 		struct merge_file_info mfi;
 		mfi = merge_file(o, path, null_sha1, 0,
-				 ren1->pair->two->sha1, ren1->pair->two->mode,
-				 ren2->pair->two->sha1, ren2->pair->two->mode,
-				 branch1, branch2);
+				 c1->sha1, c1->mode,
+				 c2->sha1, c2->mode,
+				 ci->branch1, ci->branch2);
 		output(o, 1, "Adding merged %s", path);
 		update_file(o, 0, mfi.sha, mfi.mode, path);
 	} else {
-		char *new_path1 = unique_path(o, path, branch1);
-		char *new_path2 = unique_path(o, path, branch2);
+		char *new_path1 = unique_path(o, path, ci->branch1);
+		char *new_path2 = unique_path(o, path, ci->branch2);
 		output(o, 1, "Renaming %s to %s and %s to %s instead",
-		       ren1->pair->one->path, new_path1,
-		       ren2->pair->one->path, new_path2);
+		       a->path, new_path1, b->path, new_path2);
 		remove_file(o, 0, path, 0);
-		update_file(o, 0, ren1->pair->two->sha1, ren1->pair->two->mode,
-			    new_path1);
-		update_file(o, 0, ren2->pair->two->sha1, ren2->pair->two->mode,
-			    new_path2);
+		update_file(o, 0, c1->sha1, c1->mode, new_path1);
+		update_file(o, 0, c2->sha1, c2->mode, new_path2);
 		free(new_path2);
 		free(new_path1);
 	}
@@ -1077,6 +1086,7 @@ static int process_renames(struct merge_options *o,
 		struct rename *ren1 = NULL, *ren2 = NULL;
 		const char *branch1, *branch2;
 		const char *ren1_src, *ren1_dst;
+		struct string_list_item *lookup;
 
 		if (i >= a_renames->nr) {
 			ren2 = b_renames->items[j++].util;
@@ -1108,30 +1118,30 @@ static int process_renames(struct merge_options *o,
 			ren1 = tmp;
 		}
 
+		if (ren1->processed)
+			continue;
+		ren1->processed = 1;
 		ren1->dst_entry->processed = 1;
 		/* BUG: We should only mark src_entry as processed if we
 		 * are not dealing with a rename + add-source case.
 		 */
 		ren1->src_entry->processed = 1;
 
-		if (ren1->processed)
-			continue;
-		ren1->processed = 1;
-
 		ren1_src = ren1->pair->one->path;
 		ren1_dst = ren1->pair->two->path;
 
 		if (ren2) {
+			/* One file renamed on both sides */
 			const char *ren2_src = ren2->pair->one->path;
 			const char *ren2_dst = ren2->pair->two->path;
 			enum rename_type rename_type;
-			/* Renamed in 1 and renamed in 2 */
 			if (strcmp(ren1_src, ren2_src) != 0)
-				die("ren1.src != ren2.src");
+				die("ren1_src != ren2_src");
 			ren2->dst_entry->processed = 1;
 			ren2->processed = 1;
 			if (strcmp(ren1_dst, ren2_dst) != 0) {
 				rename_type = RENAME_ONE_FILE_TO_TWO;
+				clean_merge = 0;
 			} else {
 				rename_type = RENAME_ONE_FILE_TO_ONE;
 				/* BUG: We should only remove ren1_src in
@@ -1151,9 +1161,32 @@ static int process_renames(struct merge_options *o,
 						   branch2,
 						   ren1->dst_entry,
 						   ren2->dst_entry);
+		} else if ((lookup = string_list_lookup(renames2Dst, ren1_dst))) {
+			/* Two different files renamed to the same thing */
+			char *ren2_dst;
+			ren2 = lookup->util;
+			ren2_dst = ren2->pair->two->path;
+			if (strcmp(ren1_dst, ren2_dst) != 0)
+				die("ren1_dst != ren2_dst");
+
+			clean_merge = 0;
+			ren2->processed = 1;
+			/*
+			 * BUG: We should only mark src_entry as processed
+			 * if we are not dealing with a rename + add-source
+			 * case.
+			 */
+			ren2->src_entry->processed = 1;
+
+			setup_rename_conflict_info(RENAME_TWO_FILES_TO_ONE,
+						   ren1->pair,
+						   ren2->pair,
+						   branch1,
+						   branch2,
+						   ren1->dst_entry,
+						   ren2->dst_entry);
 		} else {
 			/* Renamed in 1, maybe changed in 2 */
-			struct string_list_item *item;
 			/* we only use sha1 and mode of these */
 			struct diff_filespec src_other, dst_other;
 			int try_merge;
@@ -1188,23 +1221,6 @@ static int process_renames(struct merge_options *o,
 							   branch2,
 							   ren1->dst_entry,
 							   NULL);
-			} else if ((item = string_list_lookup(renames2Dst, ren1_dst))) {
-				char *ren2_src, *ren2_dst;
-				ren2 = item->util;
-				ren2_src = ren2->pair->one->path;
-				ren2_dst = ren2->pair->two->path;
-
-				clean_merge = 0;
-				ren2->processed = 1;
-				remove_file(o, 1, ren2_src,
-					    renamed_stage == 3 || would_lose_untracked(ren1_src));
-
-				output(o, 1, "CONFLICT (rename/rename): "
-				       "Rename %s->%s in %s. "
-				       "Rename %s->%s in %s",
-				       ren1_src, ren1_dst, branch1,
-				       ren2_src, ren2_dst, branch2);
-				conflict_rename_rename_2to1(o, ren1, branch1, ren2, branch2);
 			} else if ((dst_other.mode == ren1->pair->two->mode) &&
 				   sha_eq(dst_other.sha1, ren1->pair->two->sha1)) {
 				/* Added file on the other side
@@ -1504,6 +1520,10 @@ static int process_entry(struct merge_options *o,
 			clean_merge = 0;
 			conflict_rename_rename_1to2(o, conflict_info);
 			break;
+		case RENAME_TWO_FILES_TO_ONE:
+			clean_merge = 0;
+			conflict_rename_rename_2to1(o, conflict_info);
+			break;
 		default:
 			entry->processed = 0;
 			break;
-- 
1.7.6.100.gac5c1

[PATCHv2 43/56] merge-recursive: Record more data needed for merging with dual renames

[Elijah Newren]

When two different files are renamed to one, we need to be able to do
three-way merges for both of those files.  To do that, we need to record
the sha1sum of the (possibly modified) file on the unrenamed side.  Modify
setup_rename_conflict_info() to take this extra information and record it
when the rename_type is RENAME_TWO_FILES_TO_ONE.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   42 +++++++++++++++++++++++++++++++++++++++---
 1 files changed, 39 insertions(+), 3 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 77c2c41..63f3aa0 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -79,6 +79,8 @@ struct rename_conflict_info {
 	const char *branch2;
 	struct stage_data *dst_entry1;
 	struct stage_data *dst_entry2;
+	struct diff_filespec ren1_other;
+	struct diff_filespec ren2_other;
 };
 
 /*
@@ -100,7 +102,10 @@ static inline void setup_rename_conflict_info(enum rename_type rename_type,
 					      const char *branch1,
 					      const char *branch2,
 					      struct stage_data *dst_entry1,
-					      struct stage_data *dst_entry2)
+					      struct stage_data *dst_entry2,
+					      struct merge_options *o,
+					      struct stage_data *src_entry1,
+					      struct stage_data *src_entry2)
 {
 	struct rename_conflict_info *ci = xcalloc(1, sizeof(struct rename_conflict_info));
 	ci->rename_type = rename_type;
@@ -118,6 +123,24 @@ static inline void setup_rename_conflict_info(enum rename_type rename_type,
 		ci->pair2 = pair2;
 		dst_entry2->rename_conflict_info = ci;
 	}
+
+	if (rename_type == RENAME_TWO_FILES_TO_ONE) {
+		/*
+		 * For each rename, there could have been
+		 * modifications on the side of history where that
+		 * file was not renamed.
+		 */
+		int ostage1 = o->branch1 == branch1 ? 3 : 2;
+		int ostage2 = ostage1 ^ 1;
+
+		ci->ren1_other.path = pair1->one->path;
+		hashcpy(ci->ren1_other.sha1, src_entry1->stages[ostage1].sha);
+		ci->ren1_other.mode = src_entry1->stages[ostage1].mode;
+
+		ci->ren2_other.path = pair2->one->path;
+		hashcpy(ci->ren2_other.sha1, src_entry2->stages[ostage2].sha);
+		ci->ren2_other.mode = src_entry2->stages[ostage2].mode;
+	}
 }
 
 static int show(struct merge_options *o, int v)
@@ -1160,7 +1183,10 @@ static int process_renames(struct merge_options *o,
 						   branch1,
 						   branch2,
 						   ren1->dst_entry,
-						   ren2->dst_entry);
+						   ren2->dst_entry,
+						   o,
+						   NULL,
+						   NULL);
 		} else if ((lookup = string_list_lookup(renames2Dst, ren1_dst))) {
 			/* Two different files renamed to the same thing */
 			char *ren2_dst;
@@ -1184,7 +1210,11 @@ static int process_renames(struct merge_options *o,
 						   branch1,
 						   branch2,
 						   ren1->dst_entry,
-						   ren2->dst_entry);
+						   ren2->dst_entry,
+						   o,
+						   ren1->src_entry,
+						   ren2->src_entry);
+
 		} else {
 			/* Renamed in 1, maybe changed in 2 */
 			/* we only use sha1 and mode of these */
@@ -1220,6 +1250,9 @@ static int process_renames(struct merge_options *o,
 							   branch1,
 							   branch2,
 							   ren1->dst_entry,
+							   NULL,
+							   o,
+							   NULL,
 							   NULL);
 			} else if ((dst_other.mode == ren1->pair->two->mode) &&
 				   sha_eq(dst_other.sha1, ren1->pair->two->sha1)) {
@@ -1271,6 +1304,9 @@ static int process_renames(struct merge_options *o,
 							   branch1,
 							   NULL,
 							   ren1->dst_entry,
+							   NULL,
+							   o,
+							   NULL,
 							   NULL);
 			}
 		}
-- 
1.7.6.100.gac5c1

[PATCHv2 44/56] merge-recursive: Create function for merging with branchname:file markers

[Elijah Newren]

We want to be able to reuse the code to do a three-way file content merge
and have the conflict markers use both branchname and filename.  Split it
out into a separate function.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   42 +++++++++++++++++++++++++++++++++---------
 1 files changed, 33 insertions(+), 9 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 63f3aa0..390abea 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -944,6 +944,36 @@ static struct merge_file_info merge_file_1(struct merge_options *o,
 	return result;
 }
 
+static struct merge_file_info
+merge_file_special_markers(struct merge_options *o,
+			   const struct diff_filespec *one,
+			   const struct diff_filespec *a,
+			   const struct diff_filespec *b,
+			   const char *branch1,
+			   const char *filename1,
+			   const char *branch2,
+			   const char *filename2)
+{
+	char *side1 = NULL;
+	char *side2 = NULL;
+	struct merge_file_info mfi;
+
+	if (filename1) {
+		side1 = xmalloc(strlen(branch1) + strlen(filename1) + 2);
+		sprintf(side1, "%s:%s", branch1, filename1);
+	}
+	if (filename2) {
+		side2 = xmalloc(strlen(branch2) + strlen(filename2) + 2);
+		sprintf(side2, "%s:%s", branch2, filename2);
+	}
+
+	mfi = merge_file_1(o, one, a, b,
+			   side1 ? side1 : branch1, side2 ? side2 : branch2);
+	free(side1);
+	free(side2);
+	return mfi;
+}
+
 static struct merge_file_info merge_file(struct merge_options *o,
 					 const char *path,
 					 const unsigned char *o_sha, int o_mode,
@@ -1417,7 +1447,6 @@ static int merge_content(struct merge_options *o,
 			 struct rename_conflict_info *rename_conflict_info)
 {
 	const char *reason = "content";
-	char *side1 = NULL, *side2 = NULL;
 	const char *path1 = NULL, *path2 = NULL;
 	struct merge_file_info mfi;
 	struct diff_filespec one, a, b;
@@ -1447,18 +1476,13 @@ static int merge_content(struct merge_options *o,
 		path2 = (rename_conflict_info->pair2 ||
 			 o->branch2 == rename_conflict_info->branch1) ?
 			pair1->two->path : pair1->one->path;
-		side1 = xmalloc(strlen(o->branch1) + strlen(path1) + 2);
-		side2 = xmalloc(strlen(o->branch2) + strlen(path2) + 2);
-		sprintf(side1, "%s:%s", o->branch1, path1);
-		sprintf(side2, "%s:%s", o->branch2, path2);
 
 		if (dir_in_way(path, !o->call_depth))
 			df_conflict_remains = 1;
 	}
-	mfi = merge_file_1(o, &one, &a, &b,
-			   side1 ? side1 : o->branch1, side2 ? side2 : o->branch2);
-	free(side1);
-	free(side2);
+	mfi = merge_file_special_markers(o, &one, &a, &b,
+					 o->branch1, path1,
+					 o->branch2, path2);
 
 	if (mfi.clean && !df_conflict_remains &&
 	    sha_eq(mfi.sha, a_sha) && mfi.mode == a_mode) {
-- 
1.7.6.100.gac5c1

[PATCHv2 45/56] merge-recursive: Consider modifications in rename/rename(2to1) conflicts

[Elijah Newren]

Our previous conflict resolution for renaming two different files to the
same name ignored the fact that each of those files may have modifications
from both sides of history to consider.  We need to do a three-way merge
for each of those files, and then handle the conflict of both sets of
merged contents trying to be recorded with the same name.

It is important to note that this changes our strategy in the recursive
case.  After doing a three-way content merge of each of the files
involved, we still are faced with the fact that we are trying to put both
of the results (including conflict markers) into the same path.  We could
do another two-way merge, but I think that becomes confusing.  Also,
taking a hint from the modify/delete and rename/delete cases we handled
earlier, a more useful "common ground" would be to keep the three-way
content merge but record it with the original filename.  The renames can
still be detected, we just allow it to be done in the o->call_depth=0
case.  This seems to result in simpler & easier to understand merge
conflicts as well, as evidenced by some of the changes needed in our
testsuite in t6036.  (However, it should be noted that this change will
cause problems those renames also occur along with a file being added
whose name matches the source of the rename.  Since git currently cannot
detect rename/add-source situations, though, this codepath is not
currently used for those cases anyway.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                    |   30 ++++++++++++++++++--------
 t/t6036-recursive-corner-cases.sh    |   38 +++++++++-------------------------
 t/t6042-merge-rename-corner-cases.sh |    2 +-
 3 files changed, 32 insertions(+), 38 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 390abea..c305857 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1083,6 +1083,8 @@ static void conflict_rename_rename_2to1(struct merge_options *o,
 	struct diff_filespec *c1 = ci->pair1->two;
 	struct diff_filespec *c2 = ci->pair2->two;
 	char *path = c1->path; /* == c2->path */
+	struct merge_file_info mfi_c1;
+	struct merge_file_info mfi_c2;
 
 	output(o, 1, "CONFLICT (rename/rename): "
 	       "Rename %s->%s in %s. "
@@ -1093,22 +1095,32 @@ static void conflict_rename_rename_2to1(struct merge_options *o,
 	remove_file(o, 1, a->path, would_lose_untracked(a->path));
 	remove_file(o, 1, b->path, would_lose_untracked(b->path));
 
+	mfi_c1 = merge_file_special_markers(o, a, c1, &ci->ren1_other,
+					    o->branch1, c1->path,
+					    o->branch2, ci->ren1_other.path);
+	mfi_c2 = merge_file_special_markers(o, b, &ci->ren2_other, c2,
+					    o->branch1, ci->ren2_other.path,
+					    o->branch2, c2->path);
+
 	if (o->call_depth) {
-		struct merge_file_info mfi;
-		mfi = merge_file(o, path, null_sha1, 0,
-				 c1->sha1, c1->mode,
-				 c2->sha1, c2->mode,
-				 ci->branch1, ci->branch2);
-		output(o, 1, "Adding merged %s", path);
-		update_file(o, 0, mfi.sha, mfi.mode, path);
+		/*
+		 * If mfi_c1.clean && mfi_c2.clean, then it might make
+		 * sense to do a two-way merge of those results.  But, I
+		 * think in all cases, it makes sense to have the virtual
+		 * merge base just undo the renames; they can be detected
+		 * again later for the non-recursive merge.
+		 */
+		remove_file(o, 0, path, 0);
+		update_file(o, 0, mfi_c1.sha, mfi_c1.mode, a->path);
+		update_file(o, 0, mfi_c2.sha, mfi_c2.mode, b->path);
 	} else {
 		char *new_path1 = unique_path(o, path, ci->branch1);
 		char *new_path2 = unique_path(o, path, ci->branch2);
 		output(o, 1, "Renaming %s to %s and %s to %s instead",
 		       a->path, new_path1, b->path, new_path2);
 		remove_file(o, 0, path, 0);
-		update_file(o, 0, c1->sha1, c1->mode, new_path1);
-		update_file(o, 0, c2->sha1, c2->mode, new_path2);
+		update_file(o, 0, mfi_c1.sha, mfi_c1.mode, new_path1);
+		update_file(o, 0, mfi_c2.sha, mfi_c2.mode, new_path2);
 		free(new_path2);
 		free(new_path1);
 	}
diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index 5a7af0c..d8c6bda 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -57,23 +57,15 @@ test_expect_success 'merge simple rename+criss-cross with no modifications' '
 
 	test_must_fail git merge -s recursive R2^0 &&
 
-	test 5 = $(git ls-files -s | wc -l) &&
-	test 3 = $(git ls-files -u | wc -l) &&
-	test 0 = $(git ls-files -o | wc -l) &&
+	test 2 = $(git ls-files -s | wc -l) &&
+	test 2 = $(git ls-files -u | wc -l) &&
+	test 2 = $(git ls-files -o | wc -l) &&
 
-	test $(git rev-parse :0:one) = $(git rev-parse L2:one) &&
-	test $(git rev-parse :0:two) = $(git rev-parse R2:two) &&
 	test $(git rev-parse :2:three) = $(git rev-parse L2:three) &&
 	test $(git rev-parse :3:three) = $(git rev-parse R2:three) &&
 
-	cp one merged &&
-	>empty &&
-	test_must_fail git merge-file \
-		-L "Temporary merge branch 1" \
-		-L "" \
-		-L "Temporary merge branch 2" \
-		merged empty two &&
-	test $(git rev-parse :1:three) = $(git hash-object merged)
+	test $(git rev-parse L2:three) = $(git hash-object three~HEAD) &&
+	test $(git rev-parse R2:three) = $(git hash-object three~R2^0)
 '
 
 #
@@ -132,25 +124,15 @@ test_expect_success 'merge criss-cross + rename merges with basic modification'
 
 	test_must_fail git merge -s recursive R2^0 &&
 
-	test 5 = $(git ls-files -s | wc -l) &&
-	test 3 = $(git ls-files -u | wc -l) &&
-	test 0 = $(git ls-files -o | wc -l) &&
+	test 2 = $(git ls-files -s | wc -l) &&
+	test 2 = $(git ls-files -u | wc -l) &&
+	test 2 = $(git ls-files -o | wc -l) &&
 
-	test $(git rev-parse :0:one) = $(git rev-parse L2:one) &&
-	test $(git rev-parse :0:two) = $(git rev-parse R2:two) &&
 	test $(git rev-parse :2:three) = $(git rev-parse L2:three) &&
 	test $(git rev-parse :3:three) = $(git rev-parse R2:three) &&
 
-	head -n 10 two >merged &&
-	cp one merge-me &&
-	>empty &&
-	test_must_fail git merge-file \
-		-L "Temporary merge branch 1" \
-		-L "" \
-		-L "Temporary merge branch 2" \
-		merge-me empty merged &&
-
-	test $(git rev-parse :1:three) = $(git hash-object merge-me)
+	test $(git rev-parse L2:three) = $(git hash-object three~HEAD) &&
+	test $(git rev-parse R2:three) = $(git hash-object three~R2^0)
 '
 
 #
diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index bfc3179..3be5059 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -376,7 +376,7 @@ test_expect_success 'setup rename/rename (2to1) + modify/modify' '
 	git commit -m C
 '
 
-test_expect_failure 'handle rename/rename (2to1) conflict correctly' '
+test_expect_success 'handle rename/rename (2to1) conflict correctly' '
 	git checkout B^0 &&
 
 	test_must_fail git merge -s recursive C^0 >out &&
-- 
1.7.6.100.gac5c1

[PATCHv2 46/56] merge-recursive: Make modify/delete handling code reusable

[Elijah Newren]

modify/delete and rename/delete share a lot of similarities; we'd like all
the criss-cross and D/F conflict handling specializations to be shared
between the two.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c       |   82 +++++++++++++++++++++++++++-------------------
 t/t6022-merge-rename.sh |    4 +-
 2 files changed, 50 insertions(+), 36 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index c305857..17fe7c3 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -994,6 +994,46 @@ static struct merge_file_info merge_file(struct merge_options *o,
 	return merge_file_1(o, &one, &a, &b, branch1, branch2);
 }
 
+static void handle_change_delete(struct merge_options *o,
+				 const char *path,
+				 const unsigned char *o_sha, int o_mode,
+				 const unsigned char *a_sha, int a_mode,
+				 const unsigned char *b_sha, int b_mode,
+				 const char *change, const char *change_past)
+{
+	char *renamed = NULL;
+	if (dir_in_way(path, !o->call_depth)) {
+		renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
+	}
+
+	if (o->call_depth) {
+		/*
+		 * We cannot arbitrarily accept either a_sha or b_sha as
+		 * correct; since there is no true "middle point" between
+		 * them, simply reuse the base version for virtual merge base.
+		 */
+		remove_file_from_cache(path);
+		update_file(o, 0, o_sha, o_mode, renamed ? renamed : path);
+	} else if (!a_sha) {
+		output(o, 1, "CONFLICT (%s/delete): %s deleted in %s "
+		       "and %s in %s. Version %s of %s left in tree%s%s.",
+		       change, path, o->branch1,
+		       change_past, o->branch2, o->branch2, path,
+		       NULL == renamed ? "" : " at ",
+		       NULL == renamed ? "" : renamed);
+		update_file(o, 0, b_sha, b_mode, renamed ? renamed : path);
+	} else {
+		output(o, 1, "CONFLICT (%s/delete): %s deleted in %s "
+		       "and %s in %s. Version %s of %s left in tree%s%s.",
+		       change, path, o->branch2,
+		       change_past, o->branch1, o->branch1, path,
+		       NULL == renamed ? "" : " at ",
+		       NULL == renamed ? "" : renamed);
+		update_file(o, 0, a_sha, a_mode, renamed ? renamed : path);
+	}
+	free(renamed);
+}
+
 static void conflict_rename_delete(struct merge_options *o,
 				   struct diff_filepair *pair,
 				   const char *rename_branch,
@@ -1411,44 +1451,18 @@ error_return:
 	return ret;
 }
 
-static void handle_delete_modify(struct merge_options *o,
+static void handle_modify_delete(struct merge_options *o,
 				 const char *path,
 				 unsigned char *o_sha, int o_mode,
 				 unsigned char *a_sha, int a_mode,
 				 unsigned char *b_sha, int b_mode)
 {
-	char *renamed = NULL;
-	if (dir_in_way(path, !o->call_depth)) {
-		renamed = unique_path(o, path, a_sha ? o->branch1 : o->branch2);
-	}
-
-	if (o->call_depth) {
-		/*
-		 * We cannot arbitrarily accept either a_sha or b_sha as
-		 * correct; since there is no true "middle point" between
-		 * them, simply reuse the base version for virtual merge base.
-		 */
-		remove_file_from_cache(path);
-		update_file(o, 0, o_sha, o_mode, renamed ? renamed : path);
-	} else if (!a_sha) {
-		output(o, 1, "CONFLICT (delete/modify): %s deleted in %s "
-		       "and modified in %s. Version %s of %s left in tree%s%s.",
-		       path, o->branch1,
-		       o->branch2, o->branch2, path,
-		       NULL == renamed ? "" : " at ",
-		       NULL == renamed ? "" : renamed);
-		update_file(o, 0, b_sha, b_mode, renamed ? renamed : path);
-	} else {
-		output(o, 1, "CONFLICT (delete/modify): %s deleted in %s "
-		       "and modified in %s. Version %s of %s left in tree%s%s.",
-		       path, o->branch2,
-		       o->branch1, o->branch1, path,
-		       NULL == renamed ? "" : " at ",
-		       NULL == renamed ? "" : renamed);
-		update_file(o, 0, a_sha, a_mode, renamed ? renamed : path);
-	}
-	free(renamed);
-
+	handle_change_delete(o,
+			     path,
+			     o_sha, o_mode,
+			     a_sha, a_mode,
+			     b_sha, b_mode,
+			     "modify", "modified");
 }
 
 static int merge_content(struct merge_options *o,
@@ -1614,7 +1628,7 @@ static int process_entry(struct merge_options *o,
 		} else {
 			/* Modify/delete; deleted side may have put a directory in the way */
 			clean_merge = 0;
-			handle_delete_modify(o, path, o_sha, o_mode,
+			handle_modify_delete(o, path, o_sha, o_mode,
 					     a_sha, a_mode, b_sha, b_mode);
 		}
 	} else if ((!o_sha && a_sha && !b_sha) ||
diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index d96d3c5..74dcf20 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -303,7 +303,7 @@ test_expect_success 'Rename+D/F conflict; renamed file merges but dir in way' '
 	git checkout -q renamed-file-has-no-conflicts^0 &&
 	test_must_fail git merge --strategy=recursive dir-in-way >output &&
 
-	grep "CONFLICT (delete/modify): dir/file-in-the-way" output &&
+	grep "CONFLICT (modify/delete): dir/file-in-the-way" output &&
 	grep "Auto-merging dir" output &&
 	grep "Adding as dir~HEAD instead" output &&
 
@@ -325,7 +325,7 @@ test_expect_success 'Same as previous, but merged other way' '
 	test_must_fail git merge --strategy=recursive renamed-file-has-no-conflicts >output 2>errors &&
 
 	! grep "error: refusing to lose untracked file at" errors &&
-	grep "CONFLICT (delete/modify): dir/file-in-the-way" output &&
+	grep "CONFLICT (modify/delete): dir/file-in-the-way" output &&
 	grep "Auto-merging dir" output &&
 	grep "Adding as dir~renamed-file-has-no-conflicts instead" output &&
 
-- 
1.7.6.100.gac5c1

[PATCHv2 47/56] merge-recursive: Have conflict_rename_delete reuse modify/delete code

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c |   48 +++++++++++++++++++++++++++++++-----------------
 1 files changed, 31 insertions(+), 17 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 17fe7c3..c89a5ce 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1039,24 +1039,38 @@ static void conflict_rename_delete(struct merge_options *o,
 				   const char *rename_branch,
 				   const char *other_branch)
 {
-	char *dest_name = pair->two->path;
-	int df_conflict = 0;
+	const struct diff_filespec *orig = pair->one;
+	const struct diff_filespec *dest = pair->two;
+	const char *path;
+	const unsigned char *a_sha = NULL;
+	const unsigned char *b_sha = NULL;
+	int a_mode = 0;
+	int b_mode = 0;
+
+	if (rename_branch == o->branch1) {
+		a_sha = dest->sha1;
+		a_mode = dest->mode;
+	} else {
+		b_sha = dest->sha1;
+		b_mode = dest->mode;
+	}
 
-	output(o, 1, "CONFLICT (rename/delete): Rename %s->%s in %s "
-	       "and deleted in %s",
-	       pair->one->path, pair->two->path, rename_branch,
-	       other_branch);
-	if (!o->call_depth)
-		update_stages(dest_name, NULL,
-			      rename_branch == o->branch1 ? pair->two : NULL,
-			      rename_branch == o->branch1 ? NULL : pair->two);
-	if (dir_in_way(dest_name, !o->call_depth)) {
-		dest_name = unique_path(o, dest_name, rename_branch);
-		df_conflict = 1;
+	if (o->call_depth) {
+		remove_file_from_cache(dest->path);
+		path = orig->path;
+	} else {
+		path = dest->path;
+		update_stages(dest->path, NULL,
+			      rename_branch == o->branch1 ? dest : NULL,
+			      rename_branch == o->branch1 ? NULL : dest);
 	}
-	update_file(o, 0, pair->two->sha1, pair->two->mode, dest_name);
-	if (df_conflict)
-		free(dest_name);
+
+	handle_change_delete(o,
+			     path,
+			     orig->sha1, orig->mode,
+			     a_sha, a_mode,
+			     b_sha, b_mode,
+			     "rename", "renamed");
 }
 
 static void conflict_rename_rename_1to2(struct merge_options *o,
-- 
1.7.6.100.gac5c1

[PATCHv2 48/56] merge-recursive: add handling for rename/rename/add-dest/add-dest

[Elijah Newren]

Each side of the rename in rename/rename(1to2) could potentially also be
involved in a rename/add conflict.  Ensure stages for such conflicts are
also recorded.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                    |   21 +++++++++++++++++++--
 t/t6042-merge-rename-corner-cases.sh |    2 +-
 2 files changed, 20 insertions(+), 3 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index c89a5ce..8ddd520 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1073,6 +1073,19 @@ static void conflict_rename_delete(struct merge_options *o,
 			     "rename", "renamed");
 }
 
+static struct diff_filespec *filespec_from_entry(struct diff_filespec *target,
+						 struct stage_data *entry,
+						 int stage)
+{
+	unsigned char *sha = entry->stages[stage].sha;
+	unsigned mode = entry->stages[stage].mode;
+	if (mode == 0 || is_null_sha1(sha))
+		return NULL;
+	hashcpy(target->sha1, sha);
+	target->mode = mode;
+	return target;
+}
+
 static void conflict_rename_rename_1to2(struct merge_options *o,
 					struct rename_conflict_info *ci)
 {
@@ -1118,8 +1131,12 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 		remove_file_from_cache(a->path);
 		remove_file_from_cache(b->path);
 	} else {
-		update_stages(a->path, NULL, a, NULL);
-		update_stages(b->path, NULL, NULL, b);
+		struct diff_filespec other;
+		update_stages(a->path, NULL,
+			      a, filespec_from_entry(&other, ci->dst_entry1, 3));
+
+		update_stages(b->path, NULL,
+			      filespec_from_entry(&other, ci->dst_entry2, 2), b);
 
 		update_file(o, 0, a->sha1, a->mode, dst_name_a);
 		update_file(o, 0, b->sha1, b->mode, dst_name_b);
diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 3be5059..6875919 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -551,7 +551,7 @@ test_expect_success 'setup rename/rename(1to2)/add-dest conflict' '
 	git commit -m two
 '
 
-test_expect_failure 'rename/rename/add-dest merge still knows about conflicting file versions' '
+test_expect_success 'rename/rename/add-dest merge still knows about conflicting file versions' '
 	git checkout C^0 &&
 	test_must_fail git merge -s recursive B^0 &&
 
-- 
1.7.6.100.gac5c1

[PATCHv2 49/56] merge-recursive: Fix working copy handling for rename/rename/add/add

[Elijah Newren]

If either side of a rename/rename(1to2) conflict is itself also involved
in a rename/add-dest conflict, then we need to make sure both the rename
and the added file appear in the working copy.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
No changes since v1.

 merge-recursive.c                    |   73 ++++++++++++++++++++++------------
 t/t6042-merge-rename-corner-cases.sh |   11 +++++-
 2 files changed, 58 insertions(+), 26 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 8ddd520..05c8aa0 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1086,6 +1086,52 @@ static struct diff_filespec *filespec_from_entry(struct diff_filespec *target,
 	return target;
 }
 
+static void handle_file(struct merge_options *o,
+			struct diff_filespec *rename,
+			int stage,
+			struct rename_conflict_info *ci)
+{
+	char *dst_name = rename->path;
+	struct stage_data *dst_entry;
+	const char *cur_branch, *other_branch;
+	struct diff_filespec other;
+	struct diff_filespec *add;
+
+	if (stage == 2) {
+		dst_entry = ci->dst_entry1;
+		cur_branch = ci->branch1;
+		other_branch = ci->branch2;
+	} else {
+		dst_entry = ci->dst_entry2;
+		cur_branch = ci->branch2;
+		other_branch = ci->branch1;
+	}
+
+	add = filespec_from_entry(&other, dst_entry, stage ^ 1);
+	if (stage == 2)
+		update_stages(rename->path, NULL, rename, add);
+	else
+		update_stages(rename->path, NULL, add, rename);
+
+	if (add) {
+		char *add_name = unique_path(o, rename->path, other_branch);
+		update_file(o, 0, add->sha1, add->mode, add_name);
+
+		remove_file(o, 0, rename->path, 0);
+		dst_name = unique_path(o, rename->path, cur_branch);
+	} else {
+		if (dir_in_way(rename->path, !o->call_depth)) {
+			dst_name = unique_path(o, rename->path, cur_branch);
+			output(o, 1, "%s is a directory in %s adding as %s instead",
+			       rename->path, other_branch, dst_name);
+		}
+	}
+	update_file(o, 0, rename->sha1, rename->mode, dst_name);
+
+	if (dst_name != rename->path)
+		free(dst_name);
+}
+
 static void conflict_rename_rename_1to2(struct merge_options *o,
 					struct rename_conflict_info *ci)
 {
@@ -1093,10 +1139,6 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 	struct diff_filespec *one = ci->pair1->one;
 	struct diff_filespec *a = ci->pair1->two;
 	struct diff_filespec *b = ci->pair2->two;
-	const char *dst_name_a = a->path;
-	const char *dst_name_b = b->path;
-	char *del[2];
-	int delp = 0;
 
 	output(o, 1, "CONFLICT (rename/rename): "
 	       "Rename \"%s\"->\"%s\" in branch \"%s\" "
@@ -1104,16 +1146,6 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 	       one->path, a->path, ci->branch1,
 	       one->path, b->path, ci->branch2,
 	       o->call_depth ? " (left unresolved)" : "");
-	if (dir_in_way(a->path, !o->call_depth)) {
-		dst_name_a = del[delp++] = unique_path(o, a->path, ci->branch1);
-		output(o, 1, "%s is a directory in %s adding as %s instead",
-		       a->path, ci->branch2, dst_name_a);
-	}
-	if (dir_in_way(b->path, !o->call_depth)) {
-		dst_name_b = del[delp++] = unique_path(o, b->path, ci->branch2);
-		output(o, 1, "%s is a directory in %s adding as %s instead",
-		       b->path, ci->branch1, dst_name_b);
-	}
 	if (o->call_depth) {
 		struct merge_file_info mfi;
 		mfi = merge_file(o, one->path,
@@ -1131,18 +1163,9 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 		remove_file_from_cache(a->path);
 		remove_file_from_cache(b->path);
 	} else {
-		struct diff_filespec other;
-		update_stages(a->path, NULL,
-			      a, filespec_from_entry(&other, ci->dst_entry1, 3));
-
-		update_stages(b->path, NULL,
-			      filespec_from_entry(&other, ci->dst_entry2, 2), b);
-
-		update_file(o, 0, a->sha1, a->mode, dst_name_a);
-		update_file(o, 0, b->sha1, b->mode, dst_name_b);
+		handle_file(o, a, 2, ci);
+		handle_file(o, b, 3, ci);
 	}
-	while (delp--)
-		free(del[delp]);
 }
 
 static void conflict_rename_rename_2to1(struct merge_options *o,
diff --git a/t/t6042-merge-rename-corner-cases.sh b/t/t6042-merge-rename-corner-cases.sh
index 6875919..32591f9 100755
--- a/t/t6042-merge-rename-corner-cases.sh
+++ b/t/t6042-merge-rename-corner-cases.sh
@@ -558,12 +558,21 @@ test_expect_success 'rename/rename/add-dest merge still knows about conflicting
 	test 5 -eq $(git ls-files -s | wc -l) &&
 	test 2 -eq $(git ls-files -u b | wc -l) &&
 	test 2 -eq $(git ls-files -u c | wc -l) &&
+	test 4 -eq $(git ls-files -o | wc -l) &&
 
 	test $(git rev-parse :1:a) = $(git rev-parse A:a) &&
 	test $(git rev-parse :2:b) = $(git rev-parse C:b) &&
 	test $(git rev-parse :3:b) = $(git rev-parse B:b) &&
 	test $(git rev-parse :2:c) = $(git rev-parse C:c) &&
-	test $(git rev-parse :3:c) = $(git rev-parse B:c)
+	test $(git rev-parse :3:c) = $(git rev-parse B:c) &&
+
+	test $(git hash-object c~HEAD) = $(git rev-parse C:c) &&
+	test $(git hash-object c~B\^0) = $(git rev-parse B:c) &&
+	test $(git hash-object b~HEAD) = $(git rev-parse C:b) &&
+	test $(git hash-object b~B\^0) = $(git rev-parse B:b) &&
+
+	test ! -f b &&
+	test ! -f c
 '
 
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 50/56] t3030: fix accidental success in symlink rename

[Elijah Newren]

From: Jeff King <peff@peff.net>

In this test, we have merge two branches. On one branch, we
renamed "a" to "e". On the other, we renamed "a" to "e" and
then added a symlink pointing at "a" pointing to "e".

The results for the test indicate that the merge should
succeed, but also that "a" should no longer exist. Since
both sides renamed "a" to the same destination, we will end
up comparing those destinations for content.

But what about what's left? One side (the rename only),
replaced "a" with nothing. The other side replaced it with a
symlink. The common base must also be nothing, because any
"a" before this was meaningless (it was totally unrelated
content that ended up getting renamed).

The only sensible resolution is to keep the symlink. The
rename-only side didn't touch the content versus the common
base, and the other side added content. The 3-way merge
dictates that we take the side with a change.

And this gives the overall merge an intuitive result.  One
side made one change (a rename), and the other side made two
changes: an identical rename, and an addition (that just
happened to be at the same spot). The end result should
contain both changes.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
This patch was not part of v1, but Junio pulled it out of a separate
series and combined it.

 t/t3030-merge-recursive.sh |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/t/t3030-merge-recursive.sh b/t/t3030-merge-recursive.sh
index 0c02d56..55ef189 100755
--- a/t/t3030-merge-recursive.sh
+++ b/t/t3030-merge-recursive.sh
@@ -267,7 +267,8 @@ test_expect_success 'setup 8' '
 		ln -s e a &&
 		git add a e &&
 		test_tick &&
-		git commit -m "rename a->e, symlink a->e"
+		git commit -m "rename a->e, symlink a->e" &&
+		oln=`printf e | git hash-object --stdin`
 	fi
 '
 
@@ -630,16 +631,18 @@ test_expect_success 'merge-recursive copy vs. rename' '
 
 if test_have_prereq SYMLINKS
 then
-	test_expect_success 'merge-recursive rename vs. rename/symlink' '
+	test_expect_failure 'merge-recursive rename vs. rename/symlink' '
 
 		git checkout -f rename &&
 		git merge rename-ln &&
 		( git ls-tree -r HEAD ; git ls-files -s ) >actual &&
 		(
+			echo "120000 blob $oln	a"
 			echo "100644 blob $o0	b"
 			echo "100644 blob $o0	c"
 			echo "100644 blob $o0	d/e"
 			echo "100644 blob $o0	e"
+			echo "120000 $oln 0	a"
 			echo "100644 $o0 0	b"
 			echo "100644 $o0 0	c"
 			echo "100644 $o0 0	d/e"
-- 
1.7.6.100.gac5c1

[PATCHv2 51/56] t6022: Add testcase for spurious "refusing to lose untracked" messages

[Elijah Newren]

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Completely new patch (about a problem that existed previous to v1, but which
I hadn't noticed).

 t/t6022-merge-rename.sh |   26 ++++++++++++++++++++++++++
 1 files changed, 26 insertions(+), 0 deletions(-)

diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 74dcf20..0fd2b0a 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -767,4 +767,30 @@ test_expect_success 'merge rename into master has correct extended markers' '
 	test_cmp expected renamed_file
 '
 
+test_expect_success 'setup spurious "refusing to lose untracked" message' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	> irrelevant_file &&
+	printf "1\n2\n3\n4\n5\n6\n7\n8\n" >original_file &&
+	git add irrelevant_file original_file &&
+	git commit -mA &&
+
+	git checkout -b rename &&
+	git mv original_file renamed_file &&
+	git commit -mB &&
+
+	git checkout master &&
+	git rm original_file &&
+	git commit -mC
+'
+
+test_expect_failure 'no spurious "refusing to lose untracked" message' '
+	git checkout master^0 &&
+	test_must_fail git merge rename^0 2>errors.txt &&
+	! grep "refusing to lose untracked file" errors.txt
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 52/56] merge-recursive: Fix spurious 'refusing to lose untracked file...' messages

[Elijah Newren]

Calling update_stages() before update_file() can sometimes result in git
thinking the file being updated is untracked (whenever update_stages
moves it to stage 3).  Reverse the call order, and add a big comment to
update_stages to hopefully prevent others from making the same mistake.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Completely new patch (about a problem that existed previous to v1, but which
I hadn't noticed).

 merge-recursive.c       |   34 ++++++++++++++++++++--------------
 t/t6022-merge-rename.sh |    2 +-
 2 files changed, 21 insertions(+), 15 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 05c8aa0..b2deb53 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -528,6 +528,15 @@ static int update_stages(const char *path, const struct diff_filespec *o,
 			 const struct diff_filespec *a,
 			 const struct diff_filespec *b)
 {
+
+	/*
+	 * NOTE: It is usually a bad idea to call update_stages on a path
+	 * before calling update_file on that same path, since it can
+	 * sometimes lead to spurious "refusing to lose untracked file..."
+	 * messages from update_file (via make_room_for path via
+	 * would_lose_untracked).  Instead, reverse the order of the calls
+	 * (executing update_file first and then update_stages).
+	 */
 	int clear = 1;
 	int options = ADD_CACHE_OK_TO_ADD | ADD_CACHE_SKIP_DFCHECK;
 	if (clear)
@@ -1041,7 +1050,6 @@ static void conflict_rename_delete(struct merge_options *o,
 {
 	const struct diff_filespec *orig = pair->one;
 	const struct diff_filespec *dest = pair->two;
-	const char *path;
 	const unsigned char *a_sha = NULL;
 	const unsigned char *b_sha = NULL;
 	int a_mode = 0;
@@ -1055,22 +1063,21 @@ static void conflict_rename_delete(struct merge_options *o,
 		b_mode = dest->mode;
 	}
 
+	handle_change_delete(o,
+			     o->call_depth ? orig->path : dest->path,
+			     orig->sha1, orig->mode,
+			     a_sha, a_mode,
+			     b_sha, b_mode,
+			     "rename", "renamed");
+
 	if (o->call_depth) {
 		remove_file_from_cache(dest->path);
-		path = orig->path;
 	} else {
-		path = dest->path;
 		update_stages(dest->path, NULL,
 			      rename_branch == o->branch1 ? dest : NULL,
 			      rename_branch == o->branch1 ? NULL : dest);
 	}
 
-	handle_change_delete(o,
-			     path,
-			     orig->sha1, orig->mode,
-			     a_sha, a_mode,
-			     b_sha, b_mode,
-			     "rename", "renamed");
 }
 
 static struct diff_filespec *filespec_from_entry(struct diff_filespec *target,
@@ -1108,11 +1115,6 @@ static void handle_file(struct merge_options *o,
 	}
 
 	add = filespec_from_entry(&other, dst_entry, stage ^ 1);
-	if (stage == 2)
-		update_stages(rename->path, NULL, rename, add);
-	else
-		update_stages(rename->path, NULL, add, rename);
-
 	if (add) {
 		char *add_name = unique_path(o, rename->path, other_branch);
 		update_file(o, 0, add->sha1, add->mode, add_name);
@@ -1127,6 +1129,10 @@ static void handle_file(struct merge_options *o,
 		}
 	}
 	update_file(o, 0, rename->sha1, rename->mode, dst_name);
+	if (stage == 2)
+		update_stages(rename->path, NULL, rename, add);
+	else
+		update_stages(rename->path, NULL, add, rename);
 
 	if (dst_name != rename->path)
 		free(dst_name);
diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 0fd2b0a..8f75762 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -787,7 +787,7 @@ test_expect_success 'setup spurious "refusing to lose untracked" message' '
 	git commit -mC
 '
 
-test_expect_failure 'no spurious "refusing to lose untracked" message' '
+test_expect_success 'no spurious "refusing to lose untracked" message' '
 	git checkout master^0 &&
 	test_must_fail git merge rename^0 2>errors.txt &&
 	! grep "refusing to lose untracked file" errors.txt
-- 
1.7.6.100.gac5c1

[PATCHv2 53/56] t6022: Additional tests checking for unnecessary updates of files

[Elijah Newren]

I stumbled across a case, this one not involving a content merge, where
git currently rewrites a file unnecessarily.  A quick audit uncovered two
additional situations (also not involving content merges) with the same
problem.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Completely new patch (about a problem that existed previous to v1, but which
I hadn't noticed).

 t/t6022-merge-rename.sh |   91 +++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 91 insertions(+), 0 deletions(-)

diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index 8f75762..c2993fc 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -673,6 +673,97 @@ test_expect_success 'avoid unnecessary update, with D/F conflict' '
 	test_cmp expect actual # "df" should have stayed intact
 '
 
+test_expect_success 'setup avoid unnecessary update, dir->(file,nothing)' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	>irrelevant &&
+	mkdir df &&
+	>df/file &&
+	git add -A &&
+	git commit -mA &&
+
+	git checkout -b side
+	git rm -rf df &&
+	git commit -mB &&
+
+	git checkout master &&
+	git rm -rf df &&
+	echo bla >df &&
+	git add -A &&
+	git commit -m "Add a newfile"
+'
+
+test_expect_failure 'avoid unnecessary update, dir->(file,nothing)' '
+	git checkout -q master^0 &&
+	test-chmtime =1000000000 df &&
+	test-chmtime -v +0 df >expect &&
+	git merge side &&
+	test-chmtime -v +0 df >actual &&
+	test_cmp expect actual # "df" should have stayed intact
+'
+
+test_expect_success 'setup avoid unnecessary update, modify/delete' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	>irrelevant &&
+	>file &&
+	git add -A &&
+	git commit -mA &&
+
+	git checkout -b side
+	git rm -f file &&
+	git commit -m "Delete file" &&
+
+	git checkout master &&
+	echo bla >file &&
+	git add -A &&
+	git commit -m "Modify file"
+'
+
+test_expect_failure 'avoid unnecessary update, modify/delete' '
+	git checkout -q master^0 &&
+	test-chmtime =1000000000 file &&
+	test-chmtime -v +0 file >expect &&
+	test_must_fail git merge side &&
+	test-chmtime -v +0 file >actual &&
+	test_cmp expect actual # "file" should have stayed intact
+'
+
+test_expect_success 'setup avoid unnecessary update, rename/add-dest' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	printf "1\n2\n3\n4\n5\n6\n7\n8\n" >file &&
+	git add -A &&
+	git commit -mA &&
+
+	git checkout -b side
+	cp file newfile &&
+	git add -A &&
+	git commit -m "Add file copy" &&
+
+	git checkout master &&
+	git mv file newfile &&
+	git commit -m "Rename file"
+'
+
+test_expect_failure 'avoid unnecessary update, rename/add-dest' '
+	git checkout -q master^0 &&
+	test-chmtime =1000000000 newfile &&
+	test-chmtime -v +0 newfile >expect &&
+	git merge side &&
+	test-chmtime -v +0 newfile >actual &&
+	test_cmp expect actual # "file" should have stayed intact
+'
+
 test_expect_success 'setup merge of rename + small change' '
 	git reset --hard &&
 	git checkout --orphan rename-plus-small-change &&
-- 
1.7.6.100.gac5c1

[PATCHv2 54/56] merge-recursive: Avoid unnecessary file rewrites

[Elijah Newren]

Often times, a potential conflict at a path is resolved by merge-recursive
by using the content that was already present at that location.  In such
cases, we do not want to overwrite the content that is already present, as
that could trigger unnecessary recompilations.  One of the patches earlier
in this series ("merge-recursive: When we detect we can skip an update,
actually skip it") fixed the cases that involved content merges, but there
were a few other cases as well.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Completely new patch (about a problem that existed previous to v1, but which
I hadn't noticed).

 merge-recursive.c       |   30 ++++++++++++++++++++++++------
 t/t6022-merge-rename.sh |    6 +++---
 2 files changed, 27 insertions(+), 9 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index b2deb53..f088132 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1038,7 +1038,14 @@ static void handle_change_delete(struct merge_options *o,
 		       change_past, o->branch1, o->branch1, path,
 		       NULL == renamed ? "" : " at ",
 		       NULL == renamed ? "" : renamed);
-		update_file(o, 0, a_sha, a_mode, renamed ? renamed : path);
+		if (renamed)
+			update_file(o, 0, a_sha, a_mode, renamed);
+		/*
+		 * No need to call update_file() on path when !renamed, since
+		 * that would needlessly touch path.  We could call
+		 * update_file_flags() with update_cache=0 and update_wd=0,
+		 * but that's a no-op.
+		 */
 	}
 	free(renamed);
 }
@@ -1398,10 +1405,20 @@ static int process_renames(struct merge_options *o,
 							   NULL);
 			} else if ((dst_other.mode == ren1->pair->two->mode) &&
 				   sha_eq(dst_other.sha1, ren1->pair->two->sha1)) {
-				/* Added file on the other side
-				   identical to the file being
-				   renamed: clean merge */
-				update_file(o, 1, ren1->pair->two->sha1, ren1->pair->two->mode, ren1_dst);
+				/*
+				 * Added file on the other side identical to
+				 * the file being renamed: clean merge.
+				 * Also, there is no need to overwrite the
+				 * file already in the working copy, so call
+				 * update_file_flags() instead of
+				 * update_file().
+				 */
+				update_file_flags(o,
+						  ren1->pair->two->sha1,
+						  ren1->pair->two->mode,
+						  ren1_dst,
+						  1, /* update_cache */
+						  0  /* update_wd    */);
 			} else if (!sha_eq(dst_other.sha1, null_sha1)) {
 				clean_merge = 0;
 				try_merge = 1;
@@ -1729,7 +1746,8 @@ static int process_entry(struct merge_options *o,
 			free(new_path);
 		} else {
 			output(o, 2, "Adding %s", path);
-			update_file(o, 1, sha, mode, path);
+			/* do not overwrite file if already present */
+			update_file_flags(o, sha, mode, path, 1, !a_sha);
 		}
 	} else if (a_sha && b_sha) {
 		/* Case C: Added in both (check for same permissions) and */
diff --git a/t/t6022-merge-rename.sh b/t/t6022-merge-rename.sh
index c2993fc..9d8584e 100755
--- a/t/t6022-merge-rename.sh
+++ b/t/t6022-merge-rename.sh
@@ -696,7 +696,7 @@ test_expect_success 'setup avoid unnecessary update, dir->(file,nothing)' '
 	git commit -m "Add a newfile"
 '
 
-test_expect_failure 'avoid unnecessary update, dir->(file,nothing)' '
+test_expect_success 'avoid unnecessary update, dir->(file,nothing)' '
 	git checkout -q master^0 &&
 	test-chmtime =1000000000 df &&
 	test-chmtime -v +0 df >expect &&
@@ -726,7 +726,7 @@ test_expect_success 'setup avoid unnecessary update, modify/delete' '
 	git commit -m "Modify file"
 '
 
-test_expect_failure 'avoid unnecessary update, modify/delete' '
+test_expect_success 'avoid unnecessary update, modify/delete' '
 	git checkout -q master^0 &&
 	test-chmtime =1000000000 file &&
 	test-chmtime -v +0 file >expect &&
@@ -755,7 +755,7 @@ test_expect_success 'setup avoid unnecessary update, rename/add-dest' '
 	git commit -m "Rename file"
 '
 
-test_expect_failure 'avoid unnecessary update, rename/add-dest' '
+test_expect_success 'avoid unnecessary update, rename/add-dest' '
 	git checkout -q master^0 &&
 	test-chmtime =1000000000 newfile &&
 	test-chmtime -v +0 newfile >expect &&
-- 
1.7.6.100.gac5c1

[PATCHv2 55/56] t6036: criss-cross + rename/rename(1to2)/add-dest + simple modify

[Elijah Newren]

This is another testcase trying to exercise the virtual merge base
creation in the rename/rename(1to2) code.  A testcase is added that we
should be able to merge cleanly, but which requires a virtual merge base
to be created that correctly handles rename/add-dest conflicts within the
rename/rename(1to2) testcase handling.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Completely new patch (about a problem that existed previous to v1, but which
I hadn't noticed).

 t/t6036-recursive-corner-cases.sh |   69 +++++++++++++++++++++++++++++++++++++
 1 files changed, 69 insertions(+), 0 deletions(-)

diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index d8c6bda..e9c7a25 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -704,4 +704,73 @@ test_expect_failure 'detect rename/rename/add-source for virtual merge-base' '
 	test "$(cat a)" = "$(printf "1\n2\n3\n4\n5\n6\n7\n8\n")"
 '
 
+#
+# criss-cross with rename/rename(1to2)/add-dest + simple modify:
+#
+#      B   D
+#      o---o
+#     / \ / \
+#  A o   X   ? F
+#     \ / \ /
+#      o---o
+#      C   E
+#
+#   Commit A: new file: a
+#   Commit B: rename a->b, add c
+#   Commit C: rename a->c
+#   Commit D: merge B&C, keeping A:a and B:c
+#   Commit E: merge B&C, keeping A:a and slightly modified c from B
+#
+# Merging commits D & E should result in no conflict.  The virtual merge
+# base of B & C needs to not delete B:c for that to work, though...
+
+test_expect_success 'setup criss-cross+rename/rename/add-dest + simple modify' '
+	git rm -rf . &&
+	git clean -fdqx &&
+	rm -rf .git &&
+	git init &&
+
+	>a &&
+	git add a &&
+	git commit -m A &&
+	git tag A &&
+
+	git checkout -b B A &&
+	git mv a b &&
+	printf "1\n2\n3\n4\n5\n6\n7\n" >c &&
+	git add c &&
+	git commit -m B &&
+
+	git checkout -b C A &&
+	git mv a c &&
+	git commit -m C &&
+
+	git checkout B^0 &&
+	git merge --no-commit -s ours C^0 &&
+	git mv b a &&
+	git commit -m "D is like B but renames b back to a" &&
+	git tag D &&
+
+	git checkout B^0 &&
+	git merge --no-commit -s ours C^0 &&
+	git mv b a &&
+	echo 8 >>c &&
+	git add c &&
+	git commit -m "E like D but has mod in c" &&
+	git tag E
+'
+
+test_expect_failure 'virtual merge base handles rename/rename(1to2)/add-dest' '
+	git checkout D^0 &&
+
+	git merge -s recursive E^0 &&
+
+	test 2 -eq $(git ls-files -s | wc -l) &&
+	test 0 -eq $(git ls-files -u | wc -l) &&
+	test 0 -eq $(git ls-files -o | wc -l) &&
+
+	test $(git rev-parse HEAD:a) = $(git rev-parse A:a) &&
+	test $(git rev-parse HEAD:c) = $(git rev-parse E:c)
+'
+
 test_done
-- 
1.7.6.100.gac5c1

[PATCHv2 56/56] merge-recursive: Fix virtual merge base for rename/rename(1to2)/add-dest

[Elijah Newren]

Earlier in this series, the patch "merge-recursive: add handling for
rename/rename/add-dest/add-dest" added code to handle the rename on each
side of history also being involved in a rename/add conflict, but only
did so in the non-recursive case.  Add code for the recursive case,
ensuring that the "added" files are not simply deleted.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Completely new patch (about a problem that existed previous to v1, but which
I hadn't noticed).

 merge-recursive.c                 |   23 +++++++++++++++++++++--
 t/t6036-recursive-corner-cases.sh |    2 +-
 2 files changed, 22 insertions(+), 3 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index f088132..05ba41c 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1161,6 +1161,8 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 	       o->call_depth ? " (left unresolved)" : "");
 	if (o->call_depth) {
 		struct merge_file_info mfi;
+		struct diff_filespec other;
+		struct diff_filespec *add;
 		mfi = merge_file(o, one->path,
 				 one->sha1, one->mode,
 				 a->sha1, a->mode,
@@ -1173,8 +1175,25 @@ static void conflict_rename_rename_1to2(struct merge_options *o,
 		 * unique path, or use that unique path instead of src here.
 		 */
 		update_file(o, 0, mfi.sha, mfi.mode, one->path);
-		remove_file_from_cache(a->path);
-		remove_file_from_cache(b->path);
+
+		/*
+		 * Above, we put the merged content at the merge-base's
+		 * path.  Now we usually need to delete both a->path and
+		 * b->path.  However, the rename on each side of the merge
+		 * could also be involved in a rename/add conflict.  In
+		 * such cases, we should keep the added file around,
+		 * resolving the conflict at that path in its favor.
+		 */
+		add = filespec_from_entry(&other, ci->dst_entry1, 2 ^ 1);
+		if (add)
+			update_file(o, 0, add->sha1, add->mode, a->path);
+		else
+			remove_file_from_cache(a->path);
+		add = filespec_from_entry(&other, ci->dst_entry2, 3 ^ 1);
+		if (add)
+			update_file(o, 0, add->sha1, add->mode, b->path);
+		else
+			remove_file_from_cache(b->path);
 	} else {
 		handle_file(o, a, 2, ci);
 		handle_file(o, b, 3, ci);
diff --git a/t/t6036-recursive-corner-cases.sh b/t/t6036-recursive-corner-cases.sh
index e9c7a25..dfee7d1 100755
--- a/t/t6036-recursive-corner-cases.sh
+++ b/t/t6036-recursive-corner-cases.sh
@@ -760,7 +760,7 @@ test_expect_success 'setup criss-cross+rename/rename/add-dest + simple modify' '
 	git tag E
 '
 
-test_expect_failure 'virtual merge base handles rename/rename(1to2)/add-dest' '
+test_expect_success 'virtual merge base handles rename/rename(1to2)/add-dest' '
 	git checkout D^0 &&
 
 	git merge -s recursive E^0 &&
-- 
1.7.6.100.gac5c1

Re: [PATCHv2 00/57] Re-roll of en/merge-recursive from pu

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> Because it's so hard to rule out regressions with so many changes to a
> complicated portion of the code (though hopefully it is less complicated
> now), and because we've had multiple problems in the past with the
> changes I've been making to merge-recursive, I came up with an idea to
> test this series more thoroughly.  So, I wrote a script to take every
> single merge commit in git.git that had exactly two parents (no octopus
> merges) and redid them both with /usr/bin/git and the version of git
> from this series.  I checked to ensure that the two different versions
> of git:
>   (a) EITHER both failed to merge cleanly OR both merged cleanly
> AND
>   (b) the output of 'git ls-tree -r HEAD' matched between the two
>
> I ran this process with the original version of the series and indeed
> found that my original series mis-merged half a dozen or so merges (out
> of about 5000).

Thanks for doing this; note that the previous "simple one-side renamed the
other just updated in-place are merged incorrectly" was caught by such a
test.

One thing we may need to be careful about is to compare the conflicted
state a failed merge leaves behind.  The latter half of (a) together with
(b) will ensure that you did not introduce silent mismerges.

Avoiding silent mismerges is of course one of the most important criteria,
but we also need to make sure that a conflicted state left in the index
and the working tree files must not be harder to reconcile than what we
have been giving our users---otherwise the change will be seen as a
regression by them.

> *** What is still missing ***
>
> Two things:
>   * Junio had a great suggestion about alternate handling of the index in the
>     case of rename/rename(2to1) and directory/file conflicts (just rename the
>     entry in the index to match how we are renaming in the working copy to
>     some new unique name, in order to allow 'git diff' to provide more useful
>     information to the user).  Just didn't get to it.
>   * Support for running break detection in diffs, in order to fix the testcase
>     corrected by Peff in this series.  Simply didn't get around to it either.

I would say it is sensible to leave these two out. They can be done as a
follow-up series after dust settles.

Thanks.

Re: [PATCHv2 27/56] string-list: Add API to remove an item from an unsorted list

[Johannes Sixt]

Am 8/12/2011 7:20, schrieb Elijah Newren:
> Here's an attempt for a delete_item API (note: only compile-tested).

Seriously? You haven't even tested this patch, and still don't mark it
with RFC?

> Bike-shed painters welcome: delete_item, remove_item, free_item?

You should know that a sentence like this shouldn't appear in the commit
message.

Yeah, I know, you just copy-pasted my email text. But that was not a
commit message. Perhaps like this:

    This implements removal of an entry in O(1) runtime by moving
    the last entry to the vacated spot. As such, the routine works
    only for unsorted lists.

BTW, the code does this:

> +	list->items[i] = list->items[list->nr-1];

i.e., it assigns an entire struct. Is this perhaps problematic with older
C compilers? (I don't know, I'm more used to C++, where this is well-defined.)

-- Hannes

Re: [PATCHv2 27/56] string-list: Add API to remove an item from an unsorted list

[Alex Riesen]

On Fri, Aug 12, 2011 at 09:00, Johannes Sixt <j.sixt@viscovery.net> wrote:
> BTW, the code does this:
>
>> +     list->items[i] = list->items[list->nr-1];
>
> i.e., it assigns an entire struct. Is this perhaps problematic with older
> C compilers? (I don't know, I'm more used to C++, where this is well-defined.)

Unlikely. As long as I can remember it always was a memcpy-like operation.

Re: [PATCHv2 00/57] Re-roll of en/merge-recursive from pu

[Elijah Newren]

Hi,

On Thu, Aug 11, 2011 at 11:48 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Avoiding silent mismerges is of course one of the most important criteria,
> but we also need to make sure that a conflicted state left in the index
> and the working tree files must not be harder to reconcile than what we
> have been giving our users---otherwise the change will be seen as a
> regression by them.

Yeah, good point.  I tried re-running my previous re-merge all merges
in git.git testcase, modified so that when both versions of git
reported a conflict I would compare the output of 'git ls-files  -s'.
That uncovered a regression.  I think I know the fix but I need to
retest and do some more checks.

Re: [PATCHv2 27/56] string-list: Add API to remove an item from an unsorted list

[Elijah Newren]

On Fri, Aug 12, 2011 at 1:00 AM, Johannes Sixt <j.sixt@viscovery.net> wrote:
> Am 8/12/2011 7:20, schrieb Elijah Newren:
>> Here's an attempt for a delete_item API (note: only compile-tested).
>
> Seriously? You haven't even tested this patch, and still don't mark it
> with RFC?
>
>> Bike-shed painters welcome: delete_item, remove_item, free_item?
>
> You should know that a sentence like this shouldn't appear in the commit
> message.
>
> Yeah, I know, you just copy-pasted my email text. But that was not a
> commit message. Perhaps like this:

You are right.  I apologize; I messed up here.

However, I am unclear what you mean by not even testing the patch,
though.  I couldn't find any unit-test harness or any other kind of
testsuite for the string_list API.  I did review the code to make sure
it looked right to me, added a use of your new function, and ran the
standard testsuite in addition to my "re-merge all merges from
git.git" testcase.  I even single stepped through the code in a
debugger for good measure.  What testing did you want to see in
particular?

[PATCHv2 57/57] merge-recursive: Don't re-sort a list whose order we depend upon

[Elijah Newren]

In record_df_conflict_files() we would resort the entries list using
df_name_compare to get a convenient ordering.  Unfortunately, this broke
assumptions of the get_renames() code (via string_list_lookup() calls)
which needed the list to be in the standard ordering.  When those lookups
would fail, duplicate stage_data entries could be inserted, causing the
process_renames and process_entry code to fail (in particular, a path that
that process_renames had marked as processed would still be processed
anyway in process_entry due to the duplicate entry).

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Really this should just be a fixup commit to patch 23 ("merge-recursive:
Fix sorting order and directory change assumptions"), but that has some
(minor) contextual conflicts, which would require me to resubmit the
whole 50+ patch-series again.  I've already flooded everyone's inboxes
enough, so I just created an extra patch.

 merge-recursive.c |   16 ++++++++++++----
 1 files changed, 12 insertions(+), 4 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 05ba41c..04f3c93 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -402,6 +402,7 @@ static void record_df_conflict_files(struct merge_options *o,
 	 * and the file need to be present, then the D/F file will be
 	 * reinstated with a new unique name at the time it is processed.
 	 */
+	struct string_list df_sorted_entries;
 	const char *last_file = NULL;
 	int last_len = 0;
 	int i;
@@ -414,14 +415,20 @@ static void record_df_conflict_files(struct merge_options *o,
 		return;
 
 	/* Ensure D/F conflicts are adjacent in the entries list. */
-	qsort(entries->items, entries->nr, sizeof(*entries->items),
+	memset(&df_sorted_entries, 0, sizeof(struct string_list));
+	for (i = 0; i < entries->nr; i++) {
+		struct string_list_item *next = &entries->items[i];
+		string_list_append(&df_sorted_entries, next->string)->util =
+				   next->util;
+	}
+	qsort(df_sorted_entries.items, entries->nr, sizeof(*entries->items),
 	      string_list_df_name_compare);
 
 	string_list_clear(&o->df_conflict_file_set, 1);
-	for (i = 0; i < entries->nr; i++) {
-		const char *path = entries->items[i].string;
+	for (i = 0; i < df_sorted_entries.nr; i++) {
+		const char *path = df_sorted_entries.items[i].string;
 		int len = strlen(path);
-		struct stage_data *e = entries->items[i].util;
+		struct stage_data *e = df_sorted_entries.items[i].util;
 
 		/*
 		 * Check if last_file & path correspond to a D/F conflict;
@@ -449,6 +456,7 @@ static void record_df_conflict_files(struct merge_options *o,
 			last_file = NULL;
 		}
 	}
+	string_list_clear(&df_sorted_entries, 0);
 }
 
 struct rename {
-- 
1.7.6.100.g7c63c.dirty

Re: [PATCHv2 00/57] Re-roll of en/merge-recursive from pu

[Elijah Newren]

On Fri, Aug 12, 2011 at 3:59 PM, Elijah Newren <newren@gmail.com> wrote:
> On Thu, Aug 11, 2011 at 11:48 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Avoiding silent mismerges is of course one of the most important criteria,
>> but we also need to make sure that a conflicted state left in the index
>> and the working tree files must not be harder to reconcile than what we
>> have been giving our users---otherwise the change will be seen as a
>> regression by them.
>
> Yeah, good point.  I tried re-running my previous re-merge all merges
> in git.git testcase, modified so that when both versions of git
> reported a conflict I would compare the output of 'git ls-files  -s'.
> That uncovered a regression.  I think I know the fix but I need to
> retest and do some more checks.

With the new patch that I just submitted ("[PATCHv2 57/57]
merge-recursive: Don't re-sort a list whose order we depend upon"), I
now have fixed up the only issue I found with the more thorough tests
you suggest.  In other words:

I used the new patch on top of my series and redid my testing.  For
each two-parent merge commit in git.git (about 5000 of them), I redid
my tests.  I verified that for each redone commit,  both versions of
git would:
  (A) EITHER both fail to merge cleanly OR both merged cleanly
  (B) had identical 'git ls-files -s' output
  (C) had identical output from
       find . -type f -print0 | grep -z -v ^./.git | sort -z -u |
xargs -0 sha1sum
(Note that (B) is different than before; it should be useful in
comparing failed merges as well as successful ones, making sure the
contents of the index match.  Also, the purpose of (C) is to ensure
that the contents of the working tree match.)

In all cases, (A) and (B) were true.  There were 16 commits for which
(C) was not true; the working tree contents were different.  However,
each and every such difference were due to the change in behavior to
provide more info in conflict markers (branchname:filename instead of
just branchname) -- see patch 36 in the series.


So with the new patch, and the commit message changes Johannes
suggested for patch 27, I'm hoping this series is finally in good
shape.  But, as before, comments on the changes and other ideas for
more thorough testing are welcome.

Re: [PATCHv2 27/56] string-list: Add API to remove an item from an unsorted list

[Johannes Sixt]

Am 13.08.2011 00:14, schrieb Elijah Newren:
> On Fri, Aug 12, 2011 at 1:00 AM, Johannes Sixt <j.sixt@viscovery.net> wrote:
>> Am 8/12/2011 7:20, schrieb Elijah Newren:
>>> Here's an attempt for a delete_item API (note: only compile-tested).
>>
>> Seriously? You haven't even tested this patch, and still don't mark it
>> with RFC?
> ...
> However, I am unclear what you mean by not even testing the patch,
> though.  I couldn't find any unit-test harness or any other kind of
> testsuite for the string_list API.  I did review the code to make sure
> it looked right to me, added a use of your new function, and ran the
> standard testsuite in addition to my "re-merge all merges from
> git.git" testcase.  I even single stepped through the code in a
> debugger for good measure.  What testing did you want to see in
> particular?

This kind of testing is fine. And I appologize for asking a provocative
question. Of course, I know that you did test the new function suitably,
otherwise you wouldn't have submitted the series.

So, the question is rather, why did that sentence remain in the commit
message? The commit message should not be deceptive (and in particular
not blindly copy-pasted from an email that throws out a patch in the
hopes that somebody picks it up and massages into a good shape - I
thought it was clear that my patch was not a proper patch submission).

Think about someone browses history constrained by pathspec
'string-list.c'. This person will see this commit without any hint about
the merge-recursive series or that the new API is used in the next
commit, and will have to ask: "Why the heck is did someone introduce
this code and didn't even test it?"

-- Hannes