unexpected git-cherry-pick conflict

On Thu, Jun 07, 2007 at 11:52:19AM +0200, Remi Vanicat wrote:

how to reproduce :
create a repos with a link in it, then in a branch, remove the link,
and add a directory in place of the link (same name).

Then try to cherry pick a commit from a branch where there is the
directory into a branch where there is the link : it failed even if
the modification ave nothing to do with said link/directory.

Hi, please see http://bugs.debian.org/417885

This is how I can reproduce the conflict, and I too didn't expect that.
The link/dir that conflicts is not changed in the commit that's
cherry-pick'ed:

 $ mkdir repo && cd repo
 $ git init
 Initialized empty Git repository in .git/
 $ echo foo >file
 $ ln -s dangling link
 $ git add .
 $ git commit -mfoo
 Created initial commit c6a9189: foo
  2 files changed, 2 insertions(+), 0 deletions(-)
  create mode 100644 file
  create mode 120000 link
 $ git checkout -b branch
 Switched to a new branch "branch"
 $ git rm link
 rm 'link'
 $ git commit -mremovelink
 Created commit 2c60f15: removelink
  1 files changed, 0 insertions(+), 1 deletions(-)
  delete mode 120000 link
 $ mkdir link
 $ echo bar >link/file
 $ git add link
 $ git commit -m adddir
 Created commit d3b30b5: adddir
  1 files changed, 1 insertions(+), 0 deletions(-)
  create mode 100644 link/file
 $ echo bar >>file
 $ git commit -mfile file
 Created commit 8ddc4d5: file
  1 files changed, 1 insertions(+), 0 deletions(-)
 $ git checkout master
 Switched to branch "master"
 $ git cherry-pick 8ddc4d5
 CONFLICT (file/directory): There is a directory with name link in
 8ddc4d5... file. Added link as link~HEAD
 Automatic cherry-pick failed.  After resolving the conflicts,
 mark the corrected paths with 'git-add <paths>'
 and commit the result.
 When commiting, use the option '-c 8ddc4d5' to retain authorship and
 message.
 $ 

Thanks, Gerrit.

Hi,

On Wed, 13 Jun 2007, Gerrit Pape wrote:

 $ mkdir repo && cd repo
 $ git init
 Initialized empty Git repository in .git/
 $ echo foo >file
 $ ln -s dangling link
 $ git add .
 $ git commit -mfoo
 Created initial commit c6a9189: foo
  2 files changed, 2 insertions(+), 0 deletions(-)
  create mode 100644 file
  create mode 120000 link

So, basically your master has a file and a symbolic link.

 $ git checkout -b branch
 Switched to a new branch "branch"
 $ git rm link
 rm 'link'
 $ git commit -mremovelink
 Created commit 2c60f15: removelink
  1 files changed, 0 insertions(+), 1 deletions(-)
  delete mode 120000 link

Here, you remove the link from the branch.

 $ mkdir link
 $ echo bar >link/file
 $ git add link
 $ git commit -m adddir
 Created commit d3b30b5: adddir
  1 files changed, 1 insertions(+), 0 deletions(-)
  create mode 100644 link/file

Here you added a directory of the same name as the symbolic link has in 
master.

 $ git checkout master
 Switched to branch "master"
 $ git cherry-pick 8ddc4d5
 CONFLICT (file/directory): There is a directory with name link in
 8ddc4d5... file. Added link as link~HEAD

Here you _still_ have the file in master. So that conflict is really 
expected, since a cherry-pick will only do a three-way merge.

I guess you want to use git-rebase instead.

Ciao,
Dscho

On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:

On Wed, 13 Jun 2007, Gerrit Pape wrote:

quoted

 $ git checkout master
 Switched to branch "master"
 $ git cherry-pick 8ddc4d5
 CONFLICT (file/directory): There is a directory with name link in
 8ddc4d5... file. Added link as link~HEAD

Here you _still_ have the file in master. So that conflict is really 
expected, since a cherry-pick will only do a three-way merge.

git-cherry-pick(1) states
 Given one existing commit, apply the change the patch introduces, and
 record a new commit that records it. This requires your working tree to
 be clean (no modifications from the HEAD commit).

The patch introduced by the commit that's cherry-pick'ed has nothing to
do with the link or new directory, it just changes 'file'

 $ git show 8ddc4d5
 commit 8ddc4d59444a362261e10a3b22324818f5dd2fa7
 Author: Gerrit Pape [off-list ref]
 Date:   Wed Jun 13 09:10:30 2007 +0000
 
     file
 
 diff --git a/file b/file
 index 257cc56..3bd1f0e 100644
 --- a/file
 +++ b/file
 @@ -1 +1,2 @@
  foo
 +bar
 $ 

The patch applies to master just fine.  Where's my thinking wrong?

Thanks, Gerrit.

Hi,

On Wed, 13 Jun 2007, Gerrit Pape wrote:

On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:

quoted

On Wed, 13 Jun 2007, Gerrit Pape wrote:

quoted

 $ git checkout master
 Switched to branch "master"
 $ git cherry-pick 8ddc4d5
 CONFLICT (file/directory): There is a directory with name link in
 8ddc4d5... file. Added link as link~HEAD

Here you _still_ have the file in master. So that conflict is really 
expected, since a cherry-pick will only do a three-way merge.

git-cherry-pick(1) states
 Given one existing commit, apply the change the patch introduces, and
 record a new commit that records it. This requires your working tree to
 be clean (no modifications from the HEAD commit).

The patch introduced by the commit that's cherry-pick'ed has nothing to
do with the link or new directory, it just changes 'file'

 $ git show 8ddc4d5
 commit 8ddc4d59444a362261e10a3b22324818f5dd2fa7
 Author: Gerrit Pape [off-list ref]
 Date:   Wed Jun 13 09:10:30 2007 +0000
 
     file
 
 diff --git a/file b/file
 index 257cc56..3bd1f0e 100644
 --- a/file
 +++ b/file
 @@ -1 +1,2 @@
  foo
 +bar
 $ 

The patch applies to master just fine.  Where's my thinking wrong?

Hmm. Indeed. Thanks for clearing that up. Will work on it later.

Ciao,
Dscho

On Wed, Jun 13, 2007 at 03:43:48PM +0100, Johannes Schindelin wrote:

On Wed, 13 Jun 2007, Gerrit Pape wrote:

quoted

On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:

quoted

On Wed, 13 Jun 2007, Gerrit Pape wrote:

quoted

 $ git checkout master
 Switched to branch "master"
 $ git cherry-pick 8ddc4d5
 CONFLICT (file/directory): There is a directory with name link in
 8ddc4d5... file. Added link as link~HEAD

Here you _still_ have the file in master. So that conflict is really 
expected, since a cherry-pick will only do a three-way merge.

git-cherry-pick(1) states
 Given one existing commit, apply the change the patch introduces, and
 record a new commit that records it. This requires your working tree to
 be clean (no modifications from the HEAD commit).

The patch introduced by the commit that's cherry-pick'ed has nothing to
do with the link or new directory, it just changes 'file'

 $ git show 8ddc4d5
 commit 8ddc4d59444a362261e10a3b22324818f5dd2fa7
 Author: Gerrit Pape [off-list ref]
 Date:   Wed Jun 13 09:10:30 2007 +0000
 
     file
 
 diff --git a/file b/file
 index 257cc56..3bd1f0e 100644
 --- a/file
 +++ b/file
 @@ -1 +1,2 @@
  foo
 +bar
 $ 

The patch applies to master just fine.  Where's my thinking wrong?

Hmm. Indeed. Thanks for clearing that up. Will work on it later.

Hi, did you get to this yet?, not to stress you, just to make sure we
don't forget about it.

Thanks, Gerrit.

Hi,

On Mon, 25 Jun 2007, Gerrit Pape wrote:

On Wed, Jun 13, 2007 at 03:43:48PM +0100, Johannes Schindelin wrote:

quoted

On Wed, 13 Jun 2007, Gerrit Pape wrote:

quoted

On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:

quoted

On Wed, 13 Jun 2007, Gerrit Pape wrote:

quoted

 $ git checkout master
 Switched to branch "master"
 $ git cherry-pick 8ddc4d5
 CONFLICT (file/directory): There is a directory with name link in
 8ddc4d5... file. Added link as link~HEAD

Here you _still_ have the file in master. So that conflict is really 
expected, since a cherry-pick will only do a three-way merge.

git-cherry-pick(1) states
 Given one existing commit, apply the change the patch introduces, and
 record a new commit that records it. This requires your working tree to
 be clean (no modifications from the HEAD commit).

The patch introduced by the commit that's cherry-pick'ed has nothing to
do with the link or new directory, it just changes 'file'

 $ git show 8ddc4d5
 commit 8ddc4d59444a362261e10a3b22324818f5dd2fa7
 Author: Gerrit Pape [off-list ref]
 Date:   Wed Jun 13 09:10:30 2007 +0000
 
     file
 
 diff --git a/file b/file
 index 257cc56..3bd1f0e 100644
 --- a/file
 +++ b/file
 @@ -1 +1,2 @@
  foo
 +bar
 $ 

The patch applies to master just fine.  Where's my thinking wrong?

Hmm. Indeed. Thanks for clearing that up. Will work on it later.

Hi, did you get to this yet?, not to stress you, just to make sure we
don't forget about it.

I did not have time yet. Thanks for the reminder.

Just for the record, if you send a reply to my message to the list, but 
without Cc: to me, I am very likely to miss it. Just by chance I did not, 
this time.

Ciao,
Dscho

Hi,

On Mon, 25 Jun 2007, Gerrit Pape wrote:

Hi, did you get to this yet?, not to stress you, just to make sure we 
don't forget about it.

Okay. Since now both you and Junio asked for it, and I made today a Git 
day for me, I looked into this.

I'm not yet done, but preliminary results are: 

- cherry-pick calls merge-recursive, which in turn calls unpack_trees(), 
  which in turn gives the ball to threeway_merge. But for d/f conflicts, 
  it goes wrong.

- Documentation/technical/trivial-merge.txt is maybe about a trivial 
  merge. But the document is not trivial in and of itself.

I'll keep going,
Dscho

When a merge has a d/f conflict on a path which was not touched
between the merge base(s) and the remote HEAD, and the index and
HEAD contain the same version for that path (even if empty), it
is not really a conflict.

Noticed by Rémi Vanicat, reported to the Git list by Gerrit Pape.

Signed-off-by: Johannes Schindelin <redacted>
---

	The only peculiar result is that you can have an entry at
	stage 0 for one path, and stages 1 and 3 for another path
	where the first path is a prefix.

	This can happen now, when you have deleted a directory
	since the branching point, and put a file in the same place, but
	the other side has changed files in that directory.

	This change is reflected in the change to t3030.

	I have no idea if the change is the best there is, but after
	spending some hours trying to get my head around what is written
	in Documentation/technical/trivial-merge.txt, and what is in
	the function threeway_merge(), and still not understanding most of 
	it, there is not much more that I can do.

	Funny note at the side: when I finally got to Gerrit's email again
	today, gmane said _almost_ that it was 3 weeks, 3 days, 3 hours
	and 3 minutes ago...

 t/t3030-merge-recursive.sh |    2 +-
 t/t3502-cherry-pick.sh     |   31 +++++++++++++++++++++++++++++++
 unpack-trees.c             |   14 ++++++++++++++
 3 files changed, 46 insertions(+), 1 deletions(-)
 create mode 100755 t/t3502-cherry-pick.sh

diff --git a/t/t3030-merge-recursive.sh b/t/t3030-merge-recursive.sh
index 607f57f..d413af1 100755
--- a/t/t3030-merge-recursive.sh
+++ b/t/t3030-merge-recursive.sh

@@ -450,7 +450,7 @@ test_expect_success 'merge-recursive d/f conflict result' '
 		echo "100644 $o1 0	a"
 		echo "100644 $o0 0	b"
 		echo "100644 $o0 0	c"
-		echo "100644 $o6 2	d"
+		echo "100644 $o6 0	d"
 		echo "100644 $o0 1	d/e"
 		echo "100644 $o1 3	d/e"
 	) >expected &&

diff --git a/t/t3502-cherry-pick.sh b/t/t3502-cherry-pick.sh
new file mode 100755
index 0000000..da3d26e
--- /dev/null
+++ b/t/t3502-cherry-pick.sh

@@ -0,0 +1,31 @@
+#!/bin/sh
+
+test_description='test cherry-pick'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	echo foo > file &&
+	ln -s dangling link &&
+	git add file link &&
+	test_tick &&
+	git commit -m foo &&
+	git checkout -b branch &&
+	git rm link &&
+	test_tick &&
+	git commit -m "remove link" &&
+	mkdir link &&
+	echo bar > link/file &&
+	git add link/file &&
+	test_tick &&
+	git commit -m "add dir" &&
+	echo bar > file &&
+	git commit -m "change file" file &&
+	git checkout master
+'
+
+test_expect_success 'cherry-pick ignores unrelated dir/symlink conflict' '
+	git cherry-pick branch
+'
+
+test_done

diff --git a/unpack-trees.c b/unpack-trees.c
index cac2411..080b016 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c

@@ -643,6 +643,20 @@ int threeway_merge(struct cache_entry **stages,
 	index = stages[0];
 	head = stages[o->head_idx];
 
+	/*
+	 * Special case: do not care about a dir/file conflict, when
+	 * the entries have not been touched.
+	 * IOW if the ancestors are identical to the remote, and the
+	 * index is the same as head, just take head.
+	 */
+	if (head && same(index, head)) {
+		for (i = 1; i < o->head_idx; i++)
+			if (!same(stages[i], remote))
+				break;
+		if (i == o->head_idx)
+			return merged_entry(head, index, o);
+	}
+
 	if (head == o->df_conflict_entry) {
 		df_conflict_head = 1;
 		head = NULL;

-- 
1.5.3.rc0.2712.g125b7f

Johannes Schindelin [off-list ref] writes:

Suppose paths "A" and "A/B" are involved, and you resolved with
this logic to have "A" as a blob (so your HEAD does not have
"A/B").  If the remote adds "A/B", what prevents the resulting
index to have both "A" and "A/B" resolved at stage #0?

A logic to do "if it is unchanged on one and changed in another,
take changed one" already exists in later part of the code; your
patch just circumvents D/F checks built into threeway_merge for
this one case, and only because this one case happens to have
reported.  It doesn't feel right.

IOW, don't make unpack-trees to make policy decisions on final
resolution, unless it is operating under aggressive rule (where
the caller explicitly allows it to make more than the "trivial"
decisions).  The caller (in this case, merge-recursive) should
see A at stage #2 with A/B at stages #1 and #3 and decide what
to do.

Hi,

On Sat, 7 Jul 2007, Junio C Hamano wrote:

Johannes Schindelin [off-list ref] writes:

quoted

@@ -643,6 +643,20 @@ int threeway_merge(struct cache_entry **stages,
 	index = stages[0];
 	head = stages[o->head_idx];
 
+	/*
+	 * Special case: do not care about a dir/file conflict, when
+	 * the entries have not been touched.
+	 * IOW if the ancestors are identical to the remote, and the
+	 * index is the same as head, just take head.
+	 */

Suppose paths "A" and "A/B" are involved, and you resolved with
this logic to have "A" as a blob (so your HEAD does not have
"A/B").  If the remote adds "A/B", what prevents the resulting
index to have both "A" and "A/B" resolved at stage #0?

Hmm.

A logic to do "if it is unchanged on one and changed in another,
take changed one" already exists in later part of the code; your
patch just circumvents D/F checks built into threeway_merge for
this one case, and only because this one case happens to have
reported.  It doesn't feel right.

Well, for me the code in threeway_merge does not feel right. There is a 
table in technical/trivial-merge.txt (which I not fully understand, since 
nowhere in the table, there is a mention of the index, and nowhere is 
explained what "ALT" is supposed to mean), but threeway_merge only 
references the numbers. The code is not obvious to me.

I spent some hours staring on, and trying to make sense of it. Alas, I am 
an idiot or something, since my brain feels like a mashed potato, and I 
still do not understand the code. For example, it is not apparent to me 
why the variable "head" should be set to NULL, when it was the 
df_conflict_entry.

So yeah, this patch was marked as "PATCH", but the subject line is not 
long enough for the proper prefix, which would have started like 
"[This PATCH works for me, and I do not know how to make it better, since 
I do not understand the code in threeway_merge(), and that does not make 
me happy, but that is the way things are, and maybe someone more 
intelligent than me recognizes what is meant by my little patch, and can 
fix it up, ...]".

IOW, don't make unpack-trees to make policy decisions on final 
resolution, unless it is operating under aggressive rule (where the 
caller explicitly allows it to make more than the "trivial" decisions).  
The caller (in this case, merge-recursive) should see A at stage #2 with 
A/B at stages #1 and #3 and decide what to do.

Okay, so you're saying that merge-recursive should use the aggressive 
strategy?

Ciao,
Dscho

Hi,

On Sun, 8 Jul 2007, Johannes Schindelin wrote:

On Sat, 7 Jul 2007, Junio C Hamano wrote:

quoted

IOW, don't make unpack-trees to make policy decisions on final 
resolution, unless it is operating under aggressive rule (where the 
caller explicitly allows it to make more than the "trivial" 
decisions).  The caller (in this case, merge-recursive) should see A 
at stage #2 with A/B at stages #1 and #3 and decide what to do.

Okay, so you're saying that merge-recursive should use the aggressive 
strategy?

To refine on that: from my (limited, I admit) understanding of the code, 
by the time it hits that "if (o->aggressive)", in case of a df conflict, 
the chance has long whizzed by to decide anything useful, since either 
head or remote were set to NULL. So they are no longer what they would 
have to be in order to make any sense.

Well, I try to cobble up a patch for merge-recursive like you suggested, 
and stay away from threeway_merge() as far as I can, for the rest of my 
life.

However, it feels somehow wrong that I have to check all the files in the 
unmerged index, when unpack_trees could have easily seen that the tree did 
not change between all (in that case, just one) ancestors and the remote, 
but that head has changed that path to a file, and head agrees with index 
on that, and remote can stay where it is with its darned directory.

Ciao,
Dscho

Hi,

On Sun, 8 Jul 2007, Johannes Schindelin wrote:

Well, I try to cobble up a patch for merge-recursive like you suggested, 
and stay away from threeway_merge() as far as I can, for the rest of my 
life.

Here is a WIP. Note: it only does half of the job. For performance 
reasons, we do not write out the working tree changes for intermediate 
merges. However, in the last step, we do. And this patch does not reflect 
that, but only updates the index.

Ciao,
Dscho

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

diff --git a/merge-recursive.c b/merge-recursive.c
index dbd06aa..99da2bb 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c

@@ -243,6 +243,92 @@ static int git_merge_trees(int index_only,
 	return rc;
 }
 
+/*
+ * If there were dir/file conflicts, which are not really dir/file
+ * conflicts, because only one side changed anything, take that
+ * side instead of outputting silly conflicts.
+ *
+ * NOTE! unpack_trees() would have a much better chance at resolving
+ * these conflicts, since it gets the _tree_ objects we have to
+ * reconstruct tediously, and it could get away with one simple
+ * comparison between sha1's, while that is not possible here.
+ */
+static inline int is_df(struct cache_entry *in_dir, struct cache_entry *file)
+{
+	int len = ce_namelen(file);
+	const char *name = in_dir->name;
+	return !memcmp(name, file->name, len) && name[len] == '/';
+}
+
+static int try_to_fix_up_df_conflicts_which_are_none(const unsigned char *base,
+		const unsigned char *head, const unsigned char *merge)
+{
+	int i;
+	for (i = 0; i + 2 < active_nr; i++) {
+		int last;
+		unsigned char sha1[20], sha2[20];
+		unsigned dummy;
+		char *name;
+		struct cache_entry *ce = active_cache[i], *ce1, *ce2;
+
+		if (ce_stage(ce) == 0)
+			continue;
+		ce1 = active_cache[i + 1];
+		ce2 = active_cache[i + 2];
+		if (ce_same_name(ce, ce2) || !is_df(ce2, ce)) {
+			/* not a d/f conflict */
+			i += 2;
+			continue;
+		}
+		for (last = i + 3; last < active_nr &&
+				is_df(active_cache[last], ce); last++)
+			; /* do nothing */
+		/* check if HEAD as an unchanged file, remote a dir */
+		if (ce_same_name(ce, ce1)) {
+			if (ce_stage(ce) != 1 ||
+					hashcmp(ce->sha1, ce1->sha1)) {
+				/* file was changed */
+				i = last - 1;
+				continue;
+			}
+			/* other side removed file, added dir */
+			if (!remove_file_from_cache(ce->name))
+				return error("index error");
+			for (i -= 2, last -= 2; i < last; i++)
+				active_cache[i]->ce_flags &=
+					~ntohs(CE_STAGEMASK);
+			i--;
+			continue;
+		}
+		if (i + 1 == last)
+			continue;
+		/* check if HEAD changed dir to a file */
+		if (ce_stage(ce) == 1) {
+			i = last - 1;
+			continue;
+		}
+		name = xstrndup(ce->name, ce_namelen(ce));
+		if (get_tree_entry(base, name, sha1, &dummy) ||
+				get_tree_entry(ce_stage(ce) == 2 ?
+					merge : head,
+					name, sha2, &dummy)) {
+			free(name);
+			i = last - 1;
+			continue;
+		}
+		free(name);
+		if (!hashcmp(sha1, sha2)) {
+			/* remove tree */
+			memmove(active_cache + i + 1, active_cache + last,
+				(active_nr - last) *
+				sizeof(struct cache_entry *));
+			active_nr -= last - i - 1;
+			ce->ce_flags &= ~ntohs(CE_STAGEMASK);
+		}
+	}
+	return 0;
+}
+
 static int unmerged_index(void)
 {
 	int i;

@@ -1520,6 +1606,8 @@ static int merge_trees(struct tree *head,
 		    sha1_to_hex(head->object.sha1),
 		    sha1_to_hex(merge->object.sha1));
 
+	try_to_fix_up_df_conflicts_which_are_none(common->object.sha1,
+			head->object.sha1, merge->object.sha1);
 	if (unmerged_index()) {
 		struct path_list *entries, *re_head, *re_merge;
 		int i;

On Sat, Jul 07, 2007 at 09:58:08PM +0100, Johannes Schindelin wrote:

On Mon, 25 Jun 2007, Gerrit Pape wrote:

quoted

Hi, did you get to this yet?, not to stress you, just to make sure we 
don't forget about it.

Okay. Since now both you and Junio asked for it, and I made today a Git 
day for me, I looked into this.

Hi, the discussion on this topic unfortunately didn't result in a patch.
The problem is still true with current master, here's again how to
reproduce it

 $ mkdir repo && cd repo
 $ git init
 Initialized empty Git repository in .git/
 $ echo foo >file
 $ ln -s dangling link
 $ git add .
 $ git commit -mfoo
 Created initial commit c6a9189: foo
  2 files changed, 2 insertions(+), 0 deletions(-)
  create mode 100644 file
  create mode 120000 link
 $ git checkout -b branch
 Switched to a new branch "branch"
 $ git rm link
 rm 'link'
 $ git commit -mremovelink
 Created commit 2c60f15: removelink
  1 files changed, 0 insertions(+), 1 deletions(-)
  delete mode 120000 link
 $ mkdir link
 $ echo bar >link/file
 $ git add link
 $ git commit -m adddir
 Created commit d3b30b5: adddir
  1 files changed, 1 insertions(+), 0 deletions(-)
  create mode 100644 link/file
 $ echo bar >>file
 $ git commit -mfile file
 Created commit 8ddc4d5: file
  1 files changed, 1 insertions(+), 0 deletions(-)
 $ git checkout master
 Switched to branch "master"
 $ git cherry-pick 8ddc4d5
 CONFLICT (file/directory): There is a directory with name link in
 8ddc4d5... file. Added link as link~HEAD
 Automatic cherry-pick failed.  After resolving the conflicts,
 mark the corrected paths with 'git-add <paths>'
 and commit the result.
 When commiting, use the option '-c 8ddc4d5' to retain authorship and
 message.
 $ 

Thanks, Gerrit.