[PATCHv3 0/6] D/F conflict fixes

[PATCHv3 0/6] D/F conflict fixes

[newren]

This patch series fixes a number of spurious directory/file conflicts
and associated bugs appearing in cherry-pick, rebase, merge, and
fast-export.  It also has a minor robustness improvement for
fast-import.  This series includes testsuite fixes for currently known
failures in both t6020-merge-df.sh and t6035-merge-dir-to-symlink.sh.

The right person to review most the changes (all but the trivial
fast-import change that Shawn already commented on, modulo one minor new
change) is probably Dscho.  In his absence, the next most logical
reviewer as far as I can tell is probably Junio or perhaps Shawn.  I
hate to overwork them even more, so if anyone else has some time to take
a look or even do some simple testing, it'd be much appreciated.

Changes since the previous submission:
  * Added a new patch (5/6) fixing fast-export -- Shawn pointed out
    in the previous round that the bug I attributed to fast-import was
    actually a fast-export issue
  * Modified the fast-import patch (6/6) to note that it was just a
    robustness improvement rather than bugfix, and extended the patch to
    also handle regular files in addition to symlinks

Alexander Gladysh (1):
      Add a rename + D/F conflict testcase

Elijah Newren (5):
      Add additional testcases for D/F conflicts
      merge-recursive: Fix D/F conflicts
      merge_recursive: Fix renames across paths below D/F conflicts
      fast-export: Fix output order of D/F changes
      fast-import: Improve robustness when D->F changes provided in wrong order

 builtin/fast-export.c           |    1 +
 diff.h                          |    1 +
 fast-import.c                   |    7 +++
 merge-recursive.c               |  106 ++++++++++++++++++++++++++++++++-------
 t/t3508-cherry-pick-merge-df.sh |   34 ++++++++++++
 t/t6020-merge-df.sh             |    2 +-
 t/t6035-merge-dir-to-symlink.sh |   37 +++++++++++++-
 t/t9350-fast-export.sh          |   24 +++++++++
 tree-diff.c                     |    4 +-
 9 files changed, 194 insertions(+), 22 deletions(-)

[PATCHv3 1/6] Add additional testcases for D/F conflicts

[newren]

From: Elijah Newren <newren@gmail.com>


Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t6035-merge-dir-to-symlink.sh |   37 +++++++++++++++++++++++++++++++++++--
 t/t9350-fast-export.sh          |   24 ++++++++++++++++++++++++
 2 files changed, 59 insertions(+), 2 deletions(-)

diff --git a/t/t6035-merge-dir-to-symlink.sh b/t/t6035-merge-dir-to-symlink.sh
index 3202e1d..3c176d7 100755
--- a/t/t6035-merge-dir-to-symlink.sh
+++ b/t/t6035-merge-dir-to-symlink.sh
@@ -56,7 +56,7 @@ test_expect_success 'do not lose a/b-2/c/d in merge (resolve)' '
 	test -f a/b-2/c/d
 '
 
-test_expect_failure 'do not lose a/b-2/c/d in merge (recursive)' '
+test_expect_failure 'Handle D/F conflict, do not lose a/b-2/c/d in merge (recursive)' '
 	git reset --hard &&
 	git checkout baseline^0 &&
 	git merge -s recursive master &&
@@ -64,6 +64,31 @@ test_expect_failure 'do not lose a/b-2/c/d in merge (recursive)' '
 	test -f a/b-2/c/d
 '
 
+test_expect_failure 'Handle F/D conflict, do not lose a/b-2/c/d in merge (recursive)' '
+	git reset --hard &&
+	git checkout master &&
+	git merge -s recursive baseline^0 &&
+	test -h a/b &&
+	test -f a/b-2/c/d
+'
+
+test_expect_success 'do not lose untracked in merge (recursive)' '
+	git reset --hard &&
+	git checkout baseline^0 &&
+	touch a/b/c/e &&
+	test_must_fail git merge -s recursive master &&
+	test -f a/b/c/e &&
+	test -f a/b-2/c/d
+'
+
+test_expect_success 'do not lose modifications in merge (recursive)' '
+	git add --all &&
+	git reset --hard &&
+	git checkout baseline^0 &&
+	echo more content >> a/b/c/d &&
+	test_must_fail git merge -s recursive master
+'
+
 test_expect_success 'setup a merge where dir a/b-2 changed to symlink' '
 	git reset --hard &&
 	git checkout start^0 &&
@@ -82,7 +107,7 @@ test_expect_success 'merge should not have conflicts (resolve)' '
 	test -f a/b/c/d
 '
 
-test_expect_failure 'merge should not have conflicts (recursive)' '
+test_expect_failure 'merge should not have D/F conflicts (recursive)' '
 	git reset --hard &&
 	git checkout baseline^0 &&
 	git merge -s recursive test2 &&
@@ -90,4 +115,12 @@ test_expect_failure 'merge should not have conflicts (recursive)' '
 	test -f a/b/c/d
 '
 
+test_expect_failure 'merge should not have F/D conflicts (recursive)' '
+	git reset --hard &&
+	git checkout -b foo test2 &&
+	git merge -s recursive baseline^0 &&
+	test -h a/b-2 &&
+	test -f a/b/c/d
+'
+
 test_done
diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
index d43f37c..69179c6 100755
--- a/t/t9350-fast-export.sh
+++ b/t/t9350-fast-export.sh
@@ -376,4 +376,28 @@ test_expect_success 'tree_tag-obj'    'git fast-export tree_tag-obj'
 test_expect_success 'tag-obj_tag'     'git fast-export tag-obj_tag'
 test_expect_success 'tag-obj_tag-obj' 'git fast-export tag-obj_tag-obj'
 
+test_expect_failure 'directory becomes symlink'        '
+	git init dirtosymlink &&
+	git init result &&
+	(
+		cd dirtosymlink &&
+		mkdir foo &&
+		mkdir bar &&
+		echo hello > foo/world &&
+		echo hello > bar/world &&
+		git add foo/world bar/world &&
+		git commit -q -mone &&
+		git rm -r foo &&
+		ln -s bar foo &&
+		git add foo &&
+		git commit -q -mtwo
+	) &&
+	(
+		cd dirtosymlink &&
+		git fast-export master -- foo |
+		(cd ../result && git fast-import --quiet)
+	) &&
+	(cd result && git show master:foo)
+'
+
 test_done
-- 
1.7.1.1.10.g2e807

Re: [PATCHv3 1/6] Add additional testcases for D/F conflicts

[Junio C Hamano]

newren@gmail.com writes:

> From: Elijah Newren <newren@gmail.com>
>
> Signed-off-by: Elijah Newren <newren@gmail.com>
> ---
>  t/t6035-merge-dir-to-symlink.sh |   37 +++++++++++++++++++++++++++++++++++--
>  t/t9350-fast-export.sh          |   24 ++++++++++++++++++++++++
>  2 files changed, 59 insertions(+), 2 deletions(-)
>
> diff --git a/t/t6035-merge-dir-to-symlink.sh b/t/t6035-merge-dir-to-symlink.sh
> index 3202e1d..3c176d7 100755
> --- a/t/t6035-merge-dir-to-symlink.sh
> +++ b/t/t6035-merge-dir-to-symlink.sh
> @@ -56,7 +56,7 @@ test_expect_success 'do not lose a/b-2/c/d in merge (resolve)' '
>  	test -f a/b-2/c/d
>  '
>  
> -test_expect_failure 'do not lose a/b-2/c/d in merge (recursive)' '
> +test_expect_failure 'Handle D/F conflict, do not lose a/b-2/c/d in merge (recursive)' '

If you retitle this, you would probably want to retitle the corresponding
test for resolve (the one before this test) the same way.

> +test_expect_failure 'Handle F/D conflict, do not lose a/b-2/c/d in merge (recursive)' '
> +	git reset --hard &&
> +	git checkout master &&
> +	git merge -s recursive baseline^0 &&
> +	test -h a/b &&
> +	test -f a/b-2/c/d
> +'

It may be a good idea to see what resolve does for all these new
tests.

You would not want to do the above test while "master" branch is checked
out.  Once this is fixed, the commit subsequent tests refer to as "master"
will be a different one, and that affects their outcome in a big way.
Avoid unnecessarily making tests depend on earlier ones.

> +test_expect_failure 'Handle F/D conflict, do not lose a/b-2/c/d in merge (recursive)' '
> +	git reset --hard &&
> +	git checkout master &&

Likewise.

> +	git merge -s recursive baseline^0 &&
> +	test -h a/b &&
> +	test -f a/b-2/c/d
> +'
> +
> +test_expect_success 'do not lose untracked in merge (recursive)' '
> +	git reset --hard &&
> +	git checkout baseline^0 &&
> +	touch a/b/c/e &&
> +	test_must_fail git merge -s recursive master &&
> +	test -f a/b/c/e &&
> +	test -f a/b-2/c/d
> +'

I suspect resolve may fail this one, but as you don't have a test for it, we
won't know...

> +test_expect_success 'do not lose modifications in merge (recursive)' '
> +	git add --all &&
> +	git reset --hard &&
> +	git checkout baseline^0 &&
> +	echo more content >> a/b/c/d &&
> +	test_must_fail git merge -s recursive master
> +'
> +
>  test_expect_success 'setup a merge where dir a/b-2 changed to symlink' '
>  	git reset --hard &&
>  	git checkout start^0 &&

> @@ -82,7 +107,7 @@ test_expect_success 'merge should not have conflicts (resolve)' '
>  	test -f a/b/c/d
>  '
>  
> -test_expect_failure 'merge should not have conflicts (recursive)' '
> +test_expect_failure 'merge should not have D/F conflicts (recursive)' '

The same comment on retitling applies here.

Re: [PATCHv3 1/6] Add additional testcases for D/F conflicts

[Elijah Newren]

Hi,

Thanks for the thorough reviews!

On Wed, Jul 7, 2010 at 3:25 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> -test_expect_failure 'do not lose a/b-2/c/d in merge (recursive)' '
>> +test_expect_failure 'Handle D/F conflict, do not lose a/b-2/c/d in merge (recursive)' '
>
> If you retitle this, you would probably want to retitle the corresponding
> test for resolve (the one before this test) the same way.
<snip>
> It may be a good idea to see what resolve does for all these new
> tests.

I'd be happy to make these and the other changes you suggested, but I
notice that you've already done so in pu with Fixup commits for this
and the other patches.  Should I squash those in for a resend of the
series?

Also, do you want me to split the series as you did with the testsuite
addition patches separate from the fixes?

Thanks,
Elijah

Re: [PATCHv3 1/6] Add additional testcases for D/F conflicts

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> I'd be happy to make these and the other changes you suggested, but I
> notice that you've already done so in pu with Fixup commits for this
> and the other patches.  Should I squash those in for a resend of the
> series?

Yes, please; patches being in 'pu' does not have much more weight than
them being in the mailing list archive.  The patches should have warts
these separate "fixup" patches had to correct removed before they advance.

Thanks.

[PATCHv3 2/6] Add a rename + D/F conflict testcase

[newren]

From: Alexander Gladysh <agladysh@gmail.com>

This is a simple testcase where both sides of the rename are paths involved
in (separate) D/F merge conflicts

Signed-off-by: Alexander Gladysh <agladysh@gmail.com>
Signed-off-by: Elijah Newren <newren@gmail.com>
---
Copying my additional comments from round 2:

  As noted previously this is simply a testcase Alexander sent to the
  list on March 8 which I'm submitting in the form of a testsuite
  addition.  He's happy to have his testcase added to the testsuite
  and/or even submit it himself if that makes more sense -- just let
  us know what is wanted.  I'm less familiar with format-patch and am;
  hopefully this submission comes across with him recorded as the
  author.

 t/t3508-cherry-pick-merge-df.sh |   34 ++++++++++++++++++++++++++++++++++
 1 files changed, 34 insertions(+), 0 deletions(-)
 create mode 100755 t/t3508-cherry-pick-merge-df.sh

diff --git a/t/t3508-cherry-pick-merge-df.sh b/t/t3508-cherry-pick-merge-df.sh
new file mode 100755
index 0000000..646a56d
--- /dev/null
+++ b/t/t3508-cherry-pick-merge-df.sh
@@ -0,0 +1,34 @@
+#!/bin/sh
+
+test_description='Test cherry-pick with directory/file conflicts'
+. ./test-lib.sh
+
+test_expect_success 'Setup rename across paths each below D/F conflicts' '
+	mkdir a &&
+	touch a/f &&
+	git add a &&
+	git commit -m "a" &&
+
+	mkdir b &&
+	ln -s ../a b/a &&
+	git add b &&
+	git commit -m "b" &&
+
+	git checkout -b branch &&
+	rm b/a &&
+	mv a b/ &&
+	ln -s b/a a &&
+	git add . &&
+	git commit -m "swap" &&
+
+	touch f1 &&
+	git add f1 &&
+	git commit -m "f1"
+'
+
+test_expect_failure 'Cherry-pick succeeds with rename across D/F conflicts' '
+	git checkout master &&
+	git cherry-pick branch
+'
+
+test_done
-- 
1.7.1.1.10.g2e807

Re: [PATCHv3 2/6] Add a rename + D/F conflict testcase

[Junio C Hamano]

newren@gmail.com writes:

> From: Alexander Gladysh <agladysh@gmail.com>
>
> This is a simple testcase where both sides of the rename are paths involved
> in (separate) D/F merge conflicts
>
> Signed-off-by: Alexander Gladysh <agladysh@gmail.com>
> Signed-off-by: Elijah Newren <newren@gmail.com>
> ---
> Copying my additional comments from round 2:
>
>   As noted previously this is simply a testcase Alexander sent to the
>   list on March 8 which I'm submitting in the form of a testsuite
>   addition.  He's happy to have his testcase added to the testsuite
>   and/or even submit it himself if that makes more sense -- just let
>   us know what is wanted.  I'm less familiar with format-patch and am;
>   hopefully this submission comes across with him recorded as the
>   author.
>
>  t/t3508-cherry-pick-merge-df.sh |   34 ++++++++++++++++++++++++++++++++++

As t3508 is already used elsewhere I'll rename this to 3509, with minor
style fixes as well.

> diff --git a/t/t3508-cherry-pick-merge-df.sh b/t/t3508-cherry-pick-merge-df.sh
> new file mode 100755
> index 0000000..646a56d
> --- /dev/null
> +++ b/t/t3508-cherry-pick-merge-df.sh
> @@ -0,0 +1,34 @@
> ...
> +	touch f1 &&
> +	git add f1 &&
> +	git commit -m "f1"
> +'
> +
> +test_expect_failure 'Cherry-pick succeeds with rename across D/F conflicts' '
> +	git checkout master &&
> +	git cherry-pick branch
> +'

This is curious.  "branch" only adds a totally unrelated path to its
parent, and picking it should be trivial.  I wonder what it does
here if we used the resolve strategy...

Re: [PATCHv3 2/6] Add a rename + D/F conflict testcase

[Elijah Newren]

On Wed, Jul 7, 2010 at 3:26 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> diff --git a/t/t3508-cherry-pick-merge-df.sh b/t/t3508-cherry-pick-merge-df.sh
>> new file mode 100755
>> index 0000000..646a56d
>> --- /dev/null
>> +++ b/t/t3508-cherry-pick-merge-df.sh
>> @@ -0,0 +1,34 @@
>> ...
>> +     touch f1 &&
>> +     git add f1 &&
>> +     git commit -m "f1"
>> +'
>> +
>> +test_expect_failure 'Cherry-pick succeeds with rename across D/F conflicts' '
>> +     git checkout master &&
>> +     git cherry-pick branch
>> +'
>
> This is curious.  "branch" only adds a totally unrelated path to its
> parent, and picking it should be trivial.  I wonder what it does
> here if we used the resolve strategy...

It works with the resolve strategy.  I could add a testcase for it in
the next resend, though using the --strategy option will make the
series depend on master and make it no longer apply to maint.  Is that
an issue?

[PATCHv3 3/6] merge-recursive: Fix D/F conflicts

[newren]

From: Elijah Newren <newren@gmail.com>

The D/F conflicts that can be automatically resolved (file or directory
unmodified on one side of history), have the nice property that
process_entry() can correctly handle all subpaths of the D/F conflict.  In
the case of D->F conversions, it will correctly delete all non-conflicting
files below the relevant directory and the directory itself (note that both
untracked and conflicting files below the directory will prevent its
removal).  So if we handle D/F conflicts after all other conflicts, they
become fairly simple to handle -- we just need to check for whether or not
a path (file/directory) is in the way of creating the new content.  We do
this by having process_entry() defer handling such entries to a subsequent
process_df_entry() step.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-recursive.c               |   93 ++++++++++++++++++++++++++++++++-------
 t/t6035-merge-dir-to-symlink.sh |    8 ++--
 2 files changed, 81 insertions(+), 20 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 206c103..865729a 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1072,6 +1072,7 @@ 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);
 
+	entry->processed = 1;
 	if (o_sha && (!a_sha || !b_sha)) {
 		/* Case A: Deleted in one */
 		if ((!a_sha && !b_sha) ||
@@ -1104,33 +1105,28 @@ static int process_entry(struct merge_options *o,
 	} else if ((!o_sha && a_sha && !b_sha) ||
 		   (!o_sha && !a_sha && b_sha)) {
 		/* Case B: Added in one. */
-		const char *add_branch;
-		const char *other_branch;
 		unsigned mode;
 		const unsigned char *sha;
-		const char *conf;
 
 		if (a_sha) {
-			add_branch = o->branch1;
-			other_branch = o->branch2;
 			mode = a_mode;
 			sha = a_sha;
-			conf = "file/directory";
 		} else {
-			add_branch = o->branch2;
-			other_branch = o->branch1;
 			mode = b_mode;
 			sha = b_sha;
-			conf = "directory/file";
 		}
 		if (string_list_has_string(&o->current_directory_set, path)) {
-			const 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);
-			remove_file(o, 0, path, 0);
-			update_file(o, 0, sha, mode, new_path);
+			/* Handle D->F conflicts after all subfiles */
+			entry->processed = 0;
+			/* But get any file out of the way now, so conflicted
+			 * entries below the directory of the same name can
+			 * be put in the working directory.
+			 */
+			if (a_sha)
+				output(o, 2, "Removing %s", path);
+			/* do not touch working file if it did not exist */
+			remove_file(o, 0, path, !a_sha);
+			return 1; /* Assume clean till processed */
 		} else {
 			output(o, 2, "Adding %s", path);
 			update_file(o, 1, sha, mode, path);
@@ -1178,6 +1174,64 @@ static int process_entry(struct merge_options *o,
 	return clean_merge;
 }
 
+/* Per entry merge function for D/F conflicts, to be called only after
+ * all files below dir have been processed.  We do this because in the
+ * cases we can cleanly resolve D/F conflicts, process_entry() can clean
+ * out all the files below the directory for us.
+ */
+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);
+
+	/* We currently only handle D->F cases */
+	assert((!o_sha && a_sha && !b_sha) ||
+	       (!o_sha && !a_sha && b_sha));
+
+	const char *add_branch;
+	const char *other_branch;
+	unsigned mode;
+	const unsigned char *sha;
+	const char *conf;
+
+	entry->processed = 1;
+
+	if (a_sha) {
+		add_branch = o->branch1;
+		other_branch = o->branch2;
+		mode = a_mode;
+		sha = a_sha;
+		conf = "file/directory";
+	} else {
+		add_branch = o->branch2;
+		other_branch = o->branch1;
+		mode = b_mode;
+		sha = b_sha;
+		conf = "directory/file";
+	}
+	struct stat st;
+	if (lstat(path, &st) == 0 && S_ISDIR(st.st_mode)) {
+		const 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);
+		remove_file(o, 0, path, 0);
+		update_file(o, 0, sha, mode, new_path);
+	} else {
+		output(o, 2, "Adding %s", path);
+		update_file(o, 1, sha, mode, path);
+	}
+
+	return clean_merge;
+}
+
 struct unpack_trees_error_msgs get_porcelain_error_msgs(void)
 {
 	struct unpack_trees_error_msgs msgs = {
@@ -1249,6 +1303,13 @@ int merge_trees(struct merge_options *o,
 				&& !process_entry(o, path, e))
 				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;
+		}
 
 		string_list_clear(re_merge, 0);
 		string_list_clear(re_head, 0);
diff --git a/t/t6035-merge-dir-to-symlink.sh b/t/t6035-merge-dir-to-symlink.sh
index 3c176d7..384547d 100755
--- a/t/t6035-merge-dir-to-symlink.sh
+++ b/t/t6035-merge-dir-to-symlink.sh
@@ -56,7 +56,7 @@ test_expect_success 'do not lose a/b-2/c/d in merge (resolve)' '
 	test -f a/b-2/c/d
 '
 
-test_expect_failure 'Handle D/F conflict, do not lose a/b-2/c/d in merge (recursive)' '
+test_expect_success 'Handle D/F conflict, do not lose a/b-2/c/d in merge (recursive)' '
 	git reset --hard &&
 	git checkout baseline^0 &&
 	git merge -s recursive master &&
@@ -64,7 +64,7 @@ test_expect_failure 'Handle D/F conflict, do not lose a/b-2/c/d in merge (recurs
 	test -f a/b-2/c/d
 '
 
-test_expect_failure 'Handle F/D conflict, do not lose a/b-2/c/d in merge (recursive)' '
+test_expect_success 'Handle F/D conflict, do not lose a/b-2/c/d in merge (recursive)' '
 	git reset --hard &&
 	git checkout master &&
 	git merge -s recursive baseline^0 &&
@@ -107,7 +107,7 @@ test_expect_success 'merge should not have conflicts (resolve)' '
 	test -f a/b/c/d
 '
 
-test_expect_failure 'merge should not have D/F conflicts (recursive)' '
+test_expect_success 'merge should not have D/F conflicts (recursive)' '
 	git reset --hard &&
 	git checkout baseline^0 &&
 	git merge -s recursive test2 &&
@@ -115,7 +115,7 @@ test_expect_failure 'merge should not have D/F conflicts (recursive)' '
 	test -f a/b/c/d
 '
 
-test_expect_failure 'merge should not have F/D conflicts (recursive)' '
+test_expect_success 'merge should not have F/D conflicts (recursive)' '
 	git reset --hard &&
 	git checkout -b foo test2 &&
 	git merge -s recursive baseline^0 &&
-- 
1.7.1.1.10.g2e807

Re: [PATCHv3 3/6] merge-recursive: Fix D/F conflicts

[Junio C Hamano]

newren@gmail.com writes:

> From: Elijah Newren <newren@gmail.com>
>
> The D/F conflicts that can be automatically resolved (file or directory
> unmodified on one side of history), have the nice property that
> process_entry() can correctly handle all subpaths of the D/F conflict.  In
> the case of D->F conversions, it will correctly delete all non-conflicting
> files below the relevant directory and the directory itself (note that both
> untracked and conflicting files below the directory will prevent its
> removal).  So if we handle D/F conflicts after all other conflicts, they
> become fairly simple to handle -- we just need to check for whether or not
> a path (file/directory) is in the way of creating the new content.  We do
> this by having process_entry() defer handling such entries to a subsequent
> process_df_entry() step.

The basic idea of this patch to process all removals first and then
process additions in a separate step feels very sound.  It is exactly the
same strategy that is used by "git apply" to avoid a similar issue of
applying a patch that removes "a/b" and creates "a" at the same time.

And it feels both correct and sufficient to have this additional logic
only in the "Added in one, but the path happens to be a directory on the
other branch" codepath.  The only case you will end up having to create D
(blob) where D used to be a directory (hence needing to make sure
everything under D/ is gone) is when you are the only one adding D (and
the other party is not adding nor modifying it---if it were, it means that
the other party also wants D as a blob and not a directory, and there
won't be D/F conflict in such a case).

> Signed-off-by: Elijah Newren <newren@gmail.com>
> ---
>  merge-recursive.c               |   93 ++++++++++++++++++++++++++++++++-------
>  t/t6035-merge-dir-to-symlink.sh |    8 ++--
>  2 files changed, 81 insertions(+), 20 deletions(-)
>
> diff --git a/merge-recursive.c b/merge-recursive.c
> index 206c103..865729a 100644
> --- a/merge-recursive.c
> +++ b/merge-recursive.c
> @@ -1072,6 +1072,7 @@ 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);
>  
> +	entry->processed = 1;

In the original code, process_renames() used to use this to signal the
loop that drives process_entry() that the stage data has been dealt with,
and this function was unaware of the flag.  Now it uses it to communicate
the same fact to its downstream (process_df_entry), which makes sense, but
somehow it made me feel a bit uneasy.

> @@ -1178,6 +1174,64 @@ static int process_entry(struct merge_options *o,
>  	return clean_merge;
>  }
>  
> +/* Per entry merge function for D/F conflicts, to be called only after
> + * all files below dir have been processed.  We do this because in the
> + * cases we can cleanly resolve D/F conflicts, process_entry() can clean
> + * out all the files below the directory for us.
> + */

/*
 * Please format large comment like
 * this.
 */

Style aside, what happens when we cannot cleanly resolve D/F conflicts,
i.e. when some untracked/modified paths still remain after the earlier
removal?  We would signal conflict but at that point what happens to the
files in the working tree that are involved in this new codepath?  They
are already gone, I presume, and they at least match the original index
entries, so not much is lost, but what would the recovery procedure out of
the resulting mess?  "reset --hard"?

> +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);
> +
> +	/* We currently only handle D->F cases */
> +	assert((!o_sha && a_sha && !b_sha) ||
> +	       (!o_sha && !a_sha && b_sha));
> +	const char *add_branch;
> +	const char *other_branch;
> +	unsigned mode;
> +	const unsigned char *sha;
> +	const char *conf;

As an assert becomes code under debugging build, do not put one before
declarations like this.

Also "struct stat st" later in this file needs to be lifted up for the
same reason to avoid decl-after-statement.

Thanks.

Re: [PATCHv3 3/6] merge-recursive: Fix D/F conflicts

[Elijah Newren]

On Wed, Jul 7, 2010 at 3:40 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Style aside, what happens when we cannot cleanly resolve D/F conflicts,
> i.e. when some untracked/modified paths still remain after the earlier
> removal?  We would signal conflict but at that point what happens to the
> files in the working tree that are involved in this new codepath?  They
> are already gone, I presume, and they at least match the original index
> entries, so not much is lost, but what would the recovery procedure out of
> the resulting mess?  "reset --hard"?

That's a really good point, and yes all those files are already gone.
However, isn't this already a problem with current git?  git does not
abort when it detects the D/F conflict, it simply creates the file
with an alternate name such as directory/file~branch, and then
continues processing all the other entries -- resulting in all those
same files under the directory being deleted.  So I don't think this
patch creates any new problem.

If you want to resolve such a merge by keeping the directory and the
files under it, it is possible, though not at all obvious or
straightforward:
$ git rm --cached file-that-used-to-be-dir
$ git status file-that-used-to-be-dir | grep deleted | sed -e
s/.*deleted:// | xargs git checkout $(git merge-base HEAD $(cat
.git/MERGE_HEAD)) --

I think we could fix this up, now that we have the D/F conflict
resolution being handled last: When process_df_entry() detects that
there's a directory in the way of the file that needs to be created
(and instead warns and creates it with an alternate name), it could
also restore those deleted entries at that time.  It seems like a bit
of unnecessary work to delete and then restore files, but I'm not sure
how to get around it given the basic strategy of having unpack_trees
do what it can and then trying to fix it up separately.


Elijah

[PATCHv3 4/6] merge_recursive: Fix renames across paths below D/F conflicts

[newren]

From: Elijah Newren <newren@gmail.com>

The rename logic in process_renames() handles renames and merging of file
contents and then marks files as processed.  However, there may be higher
stage entries left in the index for other reasons (e.g., due to D/F
conflicts).  By checking for such cases and marking the entry as not
processed, it allows process_entry() later to look at it and handle those
higher stages.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 merge-recursive.c               |   13 +++++++++++--
 t/t3508-cherry-pick-merge-df.sh |    2 +-
 t/t6020-merge-df.sh             |    2 +-
 3 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/merge-recursive.c b/merge-recursive.c
index 865729a..ecddd9e 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -1019,14 +1019,23 @@ static int process_renames(struct merge_options *o,
 
 				if (mfi.clean &&
 				    sha_eq(mfi.sha, ren1->pair->two->sha1) &&
-				    mfi.mode == ren1->pair->two->mode)
+				    mfi.mode == ren1->pair->two->mode) {
 					/*
 					 * This messaged is part of
 					 * t6022 test. If you change
 					 * it update the test too.
 					 */
 					output(o, 3, "Skipped %s (merged same as existing)", ren1_dst);
-				else {
+
+					/* There may be higher stage entries left
+					 * in the index (e.g. due to a D/F
+					 * conflict) that need to be resolved.
+					 */
+					for (i=1; i<=3; ++i) {
+						if (ren1->dst_entry->stages[i].mode)
+							ren1->dst_entry->processed = 0;
+					}
+				} else {
 					if (mfi.merge || !mfi.clean)
 						output(o, 1, "Renaming %s => %s", ren1_src, ren1_dst);
 					if (mfi.merge)
diff --git a/t/t3508-cherry-pick-merge-df.sh b/t/t3508-cherry-pick-merge-df.sh
index 646a56d..5895ea3 100755
--- a/t/t3508-cherry-pick-merge-df.sh
+++ b/t/t3508-cherry-pick-merge-df.sh
@@ -26,7 +26,7 @@ test_expect_success 'Setup rename across paths each below D/F conflicts' '
 	git commit -m "f1"
 '
 
-test_expect_failure 'Cherry-pick succeeds with rename across D/F conflicts' '
+test_expect_success 'Cherry-pick succeeds with rename across D/F conflicts' '
 	git checkout master &&
 	git cherry-pick branch
 '
diff --git a/t/t6020-merge-df.sh b/t/t6020-merge-df.sh
index e71c687..490d397 100755
--- a/t/t6020-merge-df.sh
+++ b/t/t6020-merge-df.sh
@@ -22,7 +22,7 @@ git commit -m "File: dir"'
 
 test_expect_code 1 'Merge with d/f conflicts' 'git merge "merge msg" B master'
 
-test_expect_failure 'F/D conflict' '
+test_expect_success 'F/D conflict' '
 	git reset --hard &&
 	git checkout master &&
 	rm .git/index &&
-- 
1.7.1.1.10.g2e807

[PATCHv3 5/6] fast-export: Fix output order of D/F changes

[newren]

From: Elijah Newren <newren@gmail.com>

The fast-import stream format requires incremental changes which take place
immediately, meaning that for D->F conversions all files below the relevant
directory must be deleted before the resulting file of the same name is
created.  Reversing the order can result in fast-import silently deleting
the file right after creating it, resulting in the file missing from the
resulting repository.

We correct the order by instructing the diff_tree machinery to compare
entries using df_name_compare instead of base_name_compare.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 builtin/fast-export.c  |    1 +
 diff.h                 |    1 +
 t/t9350-fast-export.sh |    2 +-
 tree-diff.c            |    4 +++-
 4 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index c6dd71a..de6349f 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -614,6 +614,7 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
 		die("revision walk setup failed");
 	revs.diffopt.format_callback = show_filemodify;
 	DIFF_OPT_SET(&revs.diffopt, RECURSIVE);
+	DIFF_OPT_SET(&revs.diffopt, COMPARE_DF_EQUAL);
 	while ((commit = get_revision(&revs))) {
 		if (has_unshown_parent(commit)) {
 			add_object_array(&commit->object, NULL, &commits);
diff --git a/diff.h b/diff.h
index 6a71013..6e1a1db 100644
--- a/diff.h
+++ b/diff.h
@@ -71,6 +71,7 @@ typedef void (*diff_format_fn_t)(struct diff_queue_struct *q,
 #define DIFF_OPT_SUBMODULE_LOG       (1 << 23)
 #define DIFF_OPT_DIRTY_SUBMODULES    (1 << 24)
 #define DIFF_OPT_IGNORE_UNTRACKED_IN_SUBMODULES (1 << 25)
+#define DIFF_OPT_COMPARE_DF_EQUAL    (1 << 26)
 
 #define DIFF_OPT_TST(opts, flag)    ((opts)->flags & DIFF_OPT_##flag)
 #define DIFF_OPT_SET(opts, flag)    ((opts)->flags |= DIFF_OPT_##flag)
diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
index 69179c6..1ee1461 100755
--- a/t/t9350-fast-export.sh
+++ b/t/t9350-fast-export.sh
@@ -376,7 +376,7 @@ test_expect_success 'tree_tag-obj'    'git fast-export tree_tag-obj'
 test_expect_success 'tag-obj_tag'     'git fast-export tag-obj_tag'
 test_expect_success 'tag-obj_tag-obj' 'git fast-export tag-obj_tag-obj'
 
-test_expect_failure 'directory becomes symlink'        '
+test_expect_success 'directory becomes symlink'        '
 	git init dirtosymlink &&
 	git init result &&
 	(
diff --git a/tree-diff.c b/tree-diff.c
index fe9f52c..03f93b7 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -40,7 +40,9 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 
 	pathlen1 = tree_entry_len(path1, sha1);
 	pathlen2 = tree_entry_len(path2, sha2);
-	cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
+	cmp = DIFF_OPT_TST(opt, COMPARE_DF_EQUAL) ?
+	      df_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2) :
+	      base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
 	if (cmp < 0) {
 		show_entry(opt, "-", t1, base, baselen);
 		return -1;
-- 
1.7.1.1.10.g2e807

Re: [PATCHv3 5/6] fast-export: Fix output order of D/F changes

[Junio C Hamano]

newren@gmail.com writes:

> From: Elijah Newren <newren@gmail.com>
>
> The fast-import stream format requires incremental changes which take place
> immediately, meaning that for D->F conversions all files below the relevant
> directory must be deleted before the resulting file of the same name is
> created.  Reversing the order can result in fast-import silently deleting
> the file right after creating it, resulting in the file missing from the
> resulting repository.
>
> We correct the order by instructing the diff_tree machinery to compare
> entries using df_name_compare instead of base_name_compare.

I am not so sure about this one.

You can be walking two trees, one of which has "b-1" (blob), "b-2" (blob)
and then "b" (tree), while the other one has "b" (blob), "b-1" (blob) and
then "b-2" (blob).  The patch tells the machinery that "b" (tree) sorts
just like "b" (blob) only during comparison, but the actual data stream it
is walking is sorted differently.  Without some form of lookahead, can you
reliably "correct the order"?

Re: [PATCHv3 5/6] fast-export: Fix output order of D/F changes

[Elijah Newren]

On Wed, Jul 7, 2010 at 3:40 PM, Junio C Hamano <gitster@pobox.com> wrote:
> newren@gmail.com writes:
>
>> From: Elijah Newren <newren@gmail.com>
>>
>> The fast-import stream format requires incremental changes which take place
>> immediately, meaning that for D->F conversions all files below the relevant
>> directory must be deleted before the resulting file of the same name is
>> created.  Reversing the order can result in fast-import silently deleting
>> the file right after creating it, resulting in the file missing from the
>> resulting repository.
>>
>> We correct the order by instructing the diff_tree machinery to compare
>> entries using df_name_compare instead of base_name_compare.
>
> I am not so sure about this one.
>
> You can be walking two trees, one of which has "b-1" (blob), "b-2" (blob)
> and then "b" (tree), while the other one has "b" (blob), "b-1" (blob) and
> then "b-2" (blob).  The patch tells the machinery that "b" (tree) sorts
> just like "b" (blob) only during comparison, but the actual data stream it
> is walking is sorted differently.  Without some form of lookahead, can you
> reliably "correct the order"?

Doh! Yep, you're right.  My patch would not handle that case
correctly.  I'll dig further.

Re: [PATCHv3 5/6] fast-export: Fix output order of D/F changes

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

>>> We correct the order by instructing the diff_tree machinery to compare
>>> entries using df_name_compare instead of base_name_compare.
>
> Doh! Yep, you're right.  My patch would not handle that case
> correctly.

If all you want is to force a particular order of paths in the output
(e.g. depth first) in this one single application, the cleanest way might
be to let the diffcore do its work and at the very end sort the elements
in the diff_queued_diff to your liking (c.f. diffcore_fix_diff_index()
that uses diffnamecmp() to sort the list).

[PATCHv3 6/6] fast-import: Improve robustness when D->F changes provided in wrong order

[newren]

From: Elijah Newren <newren@gmail.com>

When older versions of fast-export came across a directory changing to a
symlink (or regular file), it would output the changes in the form
  M 120000 :239821 dir-changing-to-symlink
  D dir-changing-to-symlink/filename1
When fast-import sees the first line, it deletes the directory named
dir-changing-to-symlink (and any files below it) and creates a symlink in
its place.  When fast-import came across the second line, it was previously
trying to remove the file and relevant leading directories in
tree_content_remove(), and as a side effect it would delete the symlink
that was just created.  This resulted in the symlink silently missing from
the resulting repository.

To improve robustness, we ignore file deletions underneath directory names
that correspond to non-directories.  This can also be viewed as a minor
optimization: since there cannot be a file and a directory with the same
name in the same directory, the file clearly can't exist so nothing needs
to be done to delete it.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
Quoting Shawn's comments on the previous version of this patch:

  I'm not against making the input parser more robust...

  It probably makes sense to still do this in fast-import, deleting
  something that doesn't exist is probably OK, its still going to
  be deleted in the end anyway.

I'm guessing that probably qualifies as an Acked-by, but I'm not quite
sure.  However, I made a minor change to the patch: the previous
version only handled directory->symlink changes (S_ISLNK), whereas
this one also handles directory->(normal)file changes and
directory->gitlink changes (!S_ISDIR).

 fast-import.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)

diff --git a/fast-import.c b/fast-import.c
index 309f2c5..c8c717a 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -1528,6 +1528,13 @@ static int tree_content_remove(
 	for (i = 0; i < t->entry_count; i++) {
 		e = t->entries[i];
 		if (e->name->str_len == n && !strncmp(p, e->name->str_dat, n)) {
+			if (slash1 && !S_ISDIR(e->versions[1].mode))
+				/* If p names a file in some subdirectory, and a
+				 * file or symlink matching the name of the
+				 * parent directory of p exists, then p cannot
+				 * exist and need not be deleted.
+				 */
+				return 1;
 			if (!slash1 || !S_ISDIR(e->versions[1].mode))
 				goto del_entry;
 			if (!e->tree)
-- 
1.7.1.1.10.g2e807