Re: using xdl_merge(), was Re: Resolving conflicts

Johannes Schindelin [off-list ref] writes:

On Tue, 5 Dec 2006, Linus Torvalds wrote:

quoted

 - take every single merge in git (or the kernel, if you want even more)

The attached is the script I am using.  The test checks the
output from 'master' (merge from RCS) and 'next' (with xdl-merge)
and also tries to see how different the conflicts look like.

In the git.git archive, there is no "clean" merge on which
'master' and 'next' did not agree.  It is not a proof of
correctness at all but it gives a sense of assurance.

However, the conflict 'next' leaves seems a bit suspicious.
Trying to reproduce

	56f9686c4d1e1d586b731b815bd98d70f84ecda4

gives an interesting illustration.

Here is one conflicted hunk from that merge (RCS merge)

-- 8< -- RCS merge conflict hunk, diff from the 1st parent -- 8< --
 

--- a/Makefile
+++ b/Makefile

@@ -232,8 +232,13 @@ LIB_FILE=libgit.a
 XDIFF_LIB=xdiff/lib.a
 
 LIB_H = \
+<<<<<<< HEAD/Makefile
 	archive.h blob.h cache.h commit.h csum-file.h delta.h \
 	diff.h object.h pack.h pkt-line.h quote.h refs.h \
+=======
+	blob.h cache.h commit.h csum-file.h delta.h \
+	diff.h object.h pack.h pkt-line.h quote.h refs.h sideband.h \
+>>>>>>> d47f3db75c58139cdcbca5cc63b17bf5db293b6a/Makefile
 	run-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \
 	tree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h
 
-- >8 -- RCS merge conflict hunk, diff from the 1st parent -- >8 --

-- 8< -- JS merge conflict hunk, diff from the 1st parent -- 8< --

--- a/Makefile
+++ b/Makefile

@@ -232,8 +232,14 @@ LIB_FILE=libgit.a
 XDIFF_LIB=xdiff/lib.a
 
 LIB_H = \
+<<<<<<< HEAD/Makefile
 	archive.h blob.h cache.h commit.h csum-file.h delta.h \
 	diff.h object.h pack.h pkt-line.h quote.h refs.h \
+=======
+	blob.h cache.h commit.h csum-file.h delta.h \
+	diff.h object.h pack.h pkt-line.h quote.h refs.h sideband.h \
+>>>>>>> d47f3db75c58139cdcbca5cc63b17bf5db293b6a/Makefile
+	diff.h object.h pack.h pkt-line.h quote.h refs.h sideband.h \
 	run-command.h strbuf.h tag.h tree.h git-compat-util.h revision.h \
 	tree-walk.h log-tree.h dir.h path-list.h unpack-trees.h builtin.h
 
-- >8 -- JS merge conflict hunk, diff from the 1st parent -- >8 --

Notice that there is one duplicated line after the closing
conflict marker?


-- 8< -- remerge.sh test script -- 8< --
#!/bin/sh
# Leaves things to be examined in /var/tmp/remerge-$$/

ogit=$HOME/git-master/bin/git
ngit=$HOME/git-next/bin/git
tmp=/var/tmp/remerge-$$-tmp

trap 'rm -f $tmp-*' 0

# Revlist
if ! test -f ./+RL
then
	git rev-list --parents HEAD |
	perl -n -e 'if (/^[0-9a-f]{40} [0-9a-f]{40} [0-9a-f]{40}$/) {
		print;
	}' >./+RL
fi

try_one () {
	# should be on a discardable branch.

	git=$1 parent1=$2 parent2=$3
	$git reset --hard "$parent1"
	
	if $git merge "$parent2"
	then
		echo clean merge
		$git diff-tree -r --raw "$parent1" HEAD 
	else
		echo conflicted merge
		$git ls-files -u
		$git diff --binary -p "$parent1"
	fi
}

# Make sure we do not trash anything important
current=`git symbolic-ref HEAD`
if test "z$current" != zrefs/heads/remerge-test
then
	git checkout -b remerge-test ||
        git checkout remerge-test

        current=`git symbolic-ref HEAD`
        test "z$current" = zrefs/heads/remerge-test || exit
fi

while read result parent1 parent2
do
	try_one $ogit $parent1 $parent2 >$tmp-1 2>/dev/null
	try_one $ngit $parent1 $parent2 >$tmp-2 2>/dev/null
	if diff $tmp-1 $tmp-2
	then
		echo "Ok"
	else
		echo "Bad $result"
		mkdir -p $tmp/$result
		mv $tmp-1 $tmp/$result/ogit
		mv $tmp-2 $tmp/$result/ngit
	fi
	$git reset --hard
done < ./+RL

Suppose you have changes in new1 to the original lines 10-20,
and changes in new2 to the original lines 15-25, then the
changes to 10-25 conflict. But it is possible that the next
changes in new1 still overlap with this change to new2.

So, in the next iteration we have to look at the same change
to new2 again.

The old code tried to be a bit too clever. The new code is
shorter and more to the point: do not fiddle with the ranges
at all.

Also, xdl_append_merge() tries harder to combine conflicts.
This is necessary, because with the above simplification,
some conflicts would not be recognized as conflicts otherwise:

In the above scenario, it is possible that there is no other
change to new1. Absent the combine logic, the change in new2
would be recorded _again_, but as a non-conflict.

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

	On Tue, 5 Dec 2006, Junio C Hamano wrote:

	> However, the conflict 'next' leaves seems a bit suspicious.
	> Trying to reproduce
	> 
	> 	56f9686c4d1e1d586b731b815bd98d70f84ecda4
	> 
	> gives an interesting illustration.

	This is fixed now.

 xdiff/xmerge.c |   21 +++++----------------
 1 files changed, 5 insertions(+), 16 deletions(-)

diff --git a/xdiff/xmerge.c b/xdiff/xmerge.c
index 1fe7a1b..352207e 100644
--- a/xdiff/xmerge.c
+++ b/xdiff/xmerge.c

@@ -38,8 +38,9 @@ static int xdl_append_merge(xdmerge_t **merge, int mode,
 		long i1, long chg1, long i2, long chg2)
 {
 	xdmerge_t *m = *merge;
-	if (m && mode == m->mode &&
-			(i1 == m->i1 + m->chg1 || i2 == m->i2 + m->chg2)) {
+	if (m && (i1 <= m->i1 + m->chg1 || i2 <= m->i2 + m->chg2)) {
+		if (mode != m->mode)
+			m->mode = 0;
 		m->chg1 = i1 + chg1 - m->i1;
 		m->chg2 = i2 + chg2 - m->i2;
 	} else {

@@ -313,22 +314,10 @@ static int xdl_do_merge(xdfenv_t *xe1, xdchange_t *xscr1, const char *name1,
 		i1 = xscr1->i1 + xscr1->chg1;
 		i2 = xscr2->i1 + xscr2->chg1;
 
-		if (i1 > i2) {
-			xscr1->chg1 -= i1 - i2;
-			xscr1->i1 = i2;
-			xscr1->i2 += xscr1->chg2;
-			xscr1->chg2 = 0;
+		if (i1 >= i2)
 			xscr2 = xscr2->next;
-		} else if (i2 > i1) {
-			xscr2->chg1 -= i2 - i1;
-			xscr2->i1 = i1;
-			xscr2->i2 += xscr2->chg2;
-			xscr2->chg2 = 0;
-			xscr1 = xscr1->next;
-		} else {
+		if (i2 >= i1)
 			xscr1 = xscr1->next;
-			xscr2 = xscr2->next;
-		}
 	}
 	while (xscr1) {
 		if (!changes)

-- 
1.4.4.1.g394ac-dirty