unexpected git-cherry-pick conflict

unexpected git-cherry-pick conflict

[Gerrit Pape]

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.

Re: unexpected git-cherry-pick conflict

[Johannes Schindelin]

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

Re: unexpected git-cherry-pick conflict

[Gerrit Pape]

On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:
> On Wed, 13 Jun 2007, Gerrit Pape wrote:
> >  $ 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 <pape@smarden.org>
 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.

Re: unexpected git-cherry-pick conflict

[Johannes Schindelin]

Hi,

On Wed, 13 Jun 2007, Gerrit Pape wrote:

> On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:
> > On Wed, 13 Jun 2007, Gerrit Pape wrote:
> > >  $ 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 <pape@smarden.org>
>  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

Re: unexpected git-cherry-pick conflict

[Gerrit Pape]

On Wed, Jun 13, 2007 at 03:43:48PM +0100, Johannes Schindelin wrote:
> On Wed, 13 Jun 2007, Gerrit Pape wrote:
> > On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:
> > > On Wed, 13 Jun 2007, Gerrit Pape wrote:
> > > >  $ 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 <pape@smarden.org>
> >  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.

Re: unexpected git-cherry-pick conflict

[Johannes Schindelin]

Hi,

On Mon, 25 Jun 2007, Gerrit Pape wrote:

> On Wed, Jun 13, 2007 at 03:43:48PM +0100, Johannes Schindelin wrote:
> > On Wed, 13 Jun 2007, Gerrit Pape wrote:
> > > On Wed, Jun 13, 2007 at 01:58:51PM +0100, Johannes Schindelin wrote:
> > > > On Wed, 13 Jun 2007, Gerrit Pape wrote:
> > > > >  $ 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 <pape@smarden.org>
> > >  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

Re: unexpected git-cherry-pick conflict

[Johannes Schindelin]

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

Re: unexpected git-cherry-pick conflict

[Gerrit Pape]

On Sat, Jul 07, 2007 at 09:58:08PM +0100, Johannes Schindelin wrote:
> 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.

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.

Re: unexpected git-cherry-pick conflict

[Junio C Hamano]

Gerrit Pape <pape@smarden.org> writes:

> On Sat, Jul 07, 2007 at 09:58:08PM +0100, Johannes Schindelin wrote:
>> 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.
>
> Hi, the discussion on this topic unfortunately didn't result in a patch.

I know.  Unfortunately the code structure in merge-recursive
around directory-file conflict handling needs major surgery to
fix this, and it won't be until somebody really sits down and
rethink the issue. I've been quietly working on some ideas and a
small nascent part of it is in 'pu' (or 'offcuts', perhaps, I do
not remember offhand), but it will take time.

[PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3427 bytes --]


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 <johannes.schindelin@gmx.de>
---

	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

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> @@ -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?

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.

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

Hi,

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

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> > @@ -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

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

Hi,

On Sun, 8 Jul 2007, Johannes Schindelin wrote:

> On Sat, 7 Jul 2007, Junio C Hamano wrote:
> 
> > 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

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

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;

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

>> 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?

I do not think so.  Isn't the whole "see if there are renames" thing
depend on threeway_merge() not resolving "one side removes other
side leaves intact" case itself?  Aggressive resolves it saying
"Ok that is a remove", which risks it to miss the case in which
that the side that apparently "removed" the path in fact moved
it somewhere else.

The last time I looked at merge-recursive's D/F check, I found
that it was not quite doing things right.  I may be able to dig
up what I posted to the list...

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> ...
>> Okay, so you're saying that merge-recursive should use the aggressive 
>> strategy?
>
> I do not think so.  Isn't the whole "see if there are renames" thing
> depend on threeway_merge() not resolving "one side removes other
> side leaves intact" case itself?  Aggressive resolves it saying
> "Ok that is a remove", which risks it to miss the case in which
> that the side that apparently "removed" the path in fact moved
> it somewhere else.
>
> The last time I looked at merge-recursive's D/F check, I found
> that it was not quite doing things right.  I may be able to dig
> up what I posted to the list...

It was from around April 7th-10th this year.

    http://thread.gmane.org/gmane.comp.version-control.git/43970/focus=44158
    http://thread.gmane.org/gmane.comp.version-control.git/43971/focus=43997

I think the case described in the latter message is almost the
opposite case of what your patch tries to deal with.

In the web interface of

    http://news.gmane.org/gmane.comp.version-control.git

the patch series that led to my complaints are at around page 76
for me.

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

Hi,

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

> Junio C Hamano <gitster@pobox.com> writes:
> 
> > The last time I looked at merge-recursive's D/F check, I found that it 
> > was not quite doing things right.  I may be able to dig up what I 
> > posted to the list...
> 
> It was from around April 7th-10th this year.

Unfortunately, this is way over my time budget.  As well as over my 
intelligence budget, since I did not even succeed in understanding the 
code in threeway_merge _at all_.

Besides, IMHO there is a deeper issue. Since merge-recursive started out 
as a Python script, and grew there until it was usable, and grew the 
rename detection therein, too, until it was finally converted to C, it 
accumulated a lot of features that would have been nice to have 
independently.

Almost the same goes for unpack-trees, which (its name to the contrary) 
does quite a few things to merge entries, too.  And it tries to detect d/f 
conflicts, too.

So there we are, with two really big and unwieldy chunks of code, each 
deserving an own GSoC project to clean them up.  Or maybe not even a GSoC 
project, but a longer project.

What I would _like_ to see is something as clean as merge-tree.  Which is 
clearly separated (code and file wise, too) into these stages:

- reading the trees

- determining renames

- determining true d/f conflicts

- threeway merge

- writing the tree object

- writing the work tree

- recursive

Ideally, merge-recursive would really have been as simple as

	case "$1" in
	--index_only)
		index_only=$1
		shift
	esac
	a="$1"
	b="$2"
	set $(git merge-base --all $a $b)
	temp=$1
	shift
	while case $# in 0) break;; esac
	do
		temp=$(git merge-recursive --index-only $temp $1)
		shift
	done
	git merge-non-recursive $index_only $temp -- "$a" "$b"

because _read-tree -m_ should have learnt about renames, _not_ 
merge-recursive.

As it is, both unpack_trees() and merge-recursive have a certain degree of 
not-quite duplicated yet wants-to-do-largely-the-same functionality.  
Which of course leads to much finger pointing: "it's unpack_trees() fault. 
no. it's merge-recursive's fault. no, vice versa."

Maybe the proper way out is really to start from merge-tree.c and do 
something which is easy to understand, and concise, and thus has a much 
lesser chance of being buggy.

Ciao,
Dscho

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> Besides, IMHO there is a deeper issue. Since merge-recursive started out 
> as a Python script, and grew there until it was usable, and grew the 
> rename detection therein, too, until it was finally converted to C, it 
> accumulated a lot of features that would have been nice to have 
> independently.
> ...
> So there we are, with two really big and unwieldy chunks of code, each 
> deserving an own GSoC project to clean them up.  Or maybe not even a GSoC 
> project, but a longer project.

I would not disagree that tree merging part is a large piece of
code with nontrivial development history.  While I do agree that
merge-tree approach is attractive in the longer run, I do not
think the current "use read-tree for policy-neutral merge and
then higher level to decide what to do with conflicts" is beyond
repair.

I tried a variant of cherry-pick that does _not_ use
merge-recursive on the reproduction recipe from Gerrit & Rémi.
Essentially, a cherry-pick with a backend is:

	git-merge-$backend $commit^ -- HEAD $commit

It was made cumbersome to try different merge backend when
cherry-pick has become built-in, but the above essentially was
what we had in the shell script version.  

Interestingly, git-merge-resolve fails, but for an entirely
different reason; there is a bug in git-merge-one-file.  I am
kind of surprised that this has been left undetected for a long
time (this shows how everybody uses git-merge-recursive these
days and not git-merge-resolve).  commit ed93b449 adds tests for
only the "read-tree" part, even though it makes "matching"
change to merge-one-file, which was the breakage.  The bug is
that merge-one-file did not "resolve" an unmerged index entry
when it decided what the result should be --- it decided only in
its comments but not with what it does!  Embarrassing (a fix is
attached).

With that fix, the above "cherry-pick" lookalike with $backend
set to "resolve" and $commit set to "branch" in Gerrit's example
reproduction recipe seems to do the right thing.

> As it is, both unpack_trees() and merge-recursive have a certain degree of 
> not-quite duplicated yet wants-to-do-largely-the-same functionality.  
> Which of course leads to much finger pointing: "it's unpack_trees() fault. 
> no. it's merge-recursive's fault. no, vice versa."

I do not think there is any pointing-fingers involved in this
case.  The division of labor between "read-tree -m" and its
caller has been very clear from the beginning, and has not
changed.  The former does "uncontroversial parts of merge", and
the latter uses its own policy decision to resolve conflicts.

The "uncontroversial parts of merge" explicitly exclude "one
side removes (or adds), other side does not do anything" case.
This is cumbersome for rename-unaware merge-resolve, because its
policy is "we do not worry about the case that the apparent
removal is in fact it moves it to somewhere else -- if one side
removes, the result will not have it", and for that policy if
"read-tree -m" did so it would have less work to do.  But we
don't, exactly because other policy like merge-recursive may
want to look at the apparently removed path and figure out if
there is a rename involved.

The last time I looked at merge-recursive.c, I think the problem
I saw was the way it maintains and uses two lists that keeps
track of the set of directories and files; get_files_dirs() is
called for both head and merge at the beginning, and I did not
see a code that says "Oh, we recorded the path 'link' as being
potentially a directory at the beginning, but we have decided to
resolve 'link/file' by removing it, and 'link' does not have to
exist as a directory anymore. resolving 'link' as a symbolic
link is perfectly fine" --- and the reason Gerrit's test case
fails was something like that.

-- >8 --
[PATCH] Fix merge-one-file for our-side-added/our-side-removed cases

When commit ed93b449 changed the script so that it does not
touch untracked working tree file, we forgot that we still
needed to resolve the index entry (otherwise they are left
unmerged).

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

diff --git a/git-merge-one-file.sh b/git-merge-one-file.sh
index ebbb575..1e7727d 100755
--- a/git-merge-one-file.sh
+++ b/git-merge-one-file.sh
@@ -27,8 +27,9 @@ case "${1:-.}${2:-.}${3:-.}" in
 		# read-tree checked that index matches HEAD already,
 		# so we know we do not have this path tracked.
 		# there may be an unrelated working tree file here,
-		# which we should just leave unmolested.
-		exit 0
+		# which we should just leave unmolested.  Make sure
+		# we do not have it in the index, though.
+		exec git update-index --remove -- "$4"
 	fi
 	if test -f "$4"; then
 		rm -f -- "$4" &&
@@ -42,7 +43,8 @@ case "${1:-.}${2:-.}${3:-.}" in
 #
 ".$2.")
 	# the other side did not add and we added so there is nothing
-	# to be done.
+	# to be done, except making the path merged.
+	exec git update-index --add --cacheinfo "$6" "$2" "$4"
 	;;
 "..$3")
 	echo "Adding $4"
@@ -50,7 +52,7 @@ case "${1:-.}${2:-.}${3:-.}" in
 		echo "ERROR: untracked $4 is overwritten by the merge."
 		exit 1
 	}
-	git update-index --add --cacheinfo "$6$7" "$2$3" "$4" &&
+	git update-index --add --cacheinfo "$7" "$3" "$4" &&
 		exec git checkout-index -u -f -- "$4"
 	;;
 

merge-one-file, was Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

Hi,

On Sun, 8 Jul 2007, Junio C Hamano wrote:

> [PATCH] Fix merge-one-file for our-side-added/our-side-removed cases

FWIW I have a patch series in my local repo, which makes merge-one-file a 
builtin, and even avoids fork()+exec()ing the program when called from 
unpack_trees().  However, I never came around to understand all the corner 
cases, and therefore did not write tests for it.  Therefore, I am not 
really sure if it works as intended.  So I'd be very grateful if you could 
write tests while you are touching it anyway...

Ciao,
Dscho

[PATCH 1/2] merge-recursive: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3697 bytes --]


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 <johannes.schindelin@gmx.de>
---

	Turns out I was wrong with my "this is only half of it" remark.
	AFAICT "merge-tree -u -m" does not touch the files which have
	unmerged entries, but merge-recursive does.  And since
	fix_up_df_conflicts() is called before any of that, it just works.

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

diff --git a/merge-recursive.c b/merge-recursive.c
index c8539ec..fb487ba 100644
--- a/merge-recursive.c
+++ b/merge-recursive.c
@@ -243,6 +243,91 @@ 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.
+ *
+ * We keep it nice and easy, in that we only fix the conflicts if one
+ * side was renamed without changing the contents _at all_.  We check that
+ * by comparing the hash.
+ */
+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 fix_up_df_conflicts(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 unchanged in HEAD */
+		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 type (e.g. dir->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;
@@ -1542,6 +1627,8 @@ static int merge_trees(struct tree *head,
 		    sha1_to_hex(head->object.sha1),
 		    sha1_to_hex(merge->object.sha1));
 
+	fix_up_df_conflicts(common->object.sha1,
+			head->object.sha1, merge->object.sha1);
 	if (unmerged_index()) {
 		struct path_list *entries, *re_head, *re_merge;
 		int i;
-- 
1.5.3.rc1.16.g9d6f-dirty

Re: [PATCH 1/2] merge-recursive: sometimes, d/f conflict is not an issue

[Gerrit Pape]

On Tue, Jul 17, 2007 at 06:13:12PM +0100, Johannes Schindelin wrote:
> 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.

Hi, this patch solves the reported problem fine, and it didn't break
anything for me yet.  Can this still be considered for 1.5.3?

Thanks, Gerrit.

[PATCH 2/2] Add tests for cherry-pick d/f conflict which should be none

[Johannes Schindelin]

This tests that we fixed the problem when a directory was renamed,
and a symlink was added in its place (or for that matter, if
the type changed in one branch, and the name in another).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---

	The last test checks that also a file/symlink conflict does
	not break cherry-pick, if one side had a clean rename.

 t/t3502-cherry-pick.sh |   43 +++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 43 insertions(+), 0 deletions(-)
 create mode 100755 t/t3502-cherry-pick.sh

diff --git a/t/t3502-cherry-pick.sh b/t/t3502-cherry-pick.sh
new file mode 100755
index 0000000..9921de5
--- /dev/null
+++ b/t/t3502-cherry-pick.sh
@@ -0,0 +1,43 @@
+#!/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_expect_success 'cherry-pick ignores unrelated file/symlink conflict' '
+	git checkout -b branch2 master^ &&
+	git rm link &&
+	test_tick &&
+	git commit -m "remove link" &&
+	: > link &&
+	git add link &&
+	test_tick &&
+	git commit -m "add file" &&
+	git cherry-pick master
+'
+
+test_done
-- 
1.5.3.rc1.16.g9d6f-dirty

Re: [PATCH] merge-tree: sometimes, d/f conflict is not an issue

[Johannes Schindelin]

Hi,

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

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> 
> >> 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?
> 
> I do not think so.

Yes, I realized that by running the tests with it.  A rename A->B in one, 
and A->C in the other branch will go undetected.

I should have written this into my mail posting the WIP patch, but 
frankly, I was too tired.

Ciao,
Dscho