unexpected git-cherry-pick conflict

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

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:

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

Here, you remove the link from the branch.

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

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:

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.

Hi,

On Wed, 13 Jun 2007, Gerrit Pape wrote:

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:

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:

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:

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

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

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.

Gerrit Pape <pape@smarden.org> writes:

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.

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

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

Hmm.

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, ...]".

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

Ciao, Dscho

Hi,

On Sun, 8 Jul 2007, Johannes Schindelin wrote:

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:

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(-)

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

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

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

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.

Hi,

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

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

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

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.

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

Hi,

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

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

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(-)

On Tue, Jul 17, 2007 at 06:13:12PM +0100, Johannes Schindelin wrote:

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.

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

Hi,

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

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