using xdl_merge(), was Re: Resolving conflicts

Sorry to be so ignorant, but I just updated to 2.6.19 using:

   git-checkout master
   git-pull

   ...
   sound/usb/usbaudio.c                          |    3
   usr/Makefile                                  |    2
   92 files changed, 888 insertions(+), 371 deletions(-)
   create mode 100644 arch/mips/kernel/topology.c
   create mode 100644 arch/um/os-Linux/execvp.c
   create mode 100644 include/asm-arm/mach/udc_pxa2xx.h

All seemed to go I then moved back to my branch and pulled from master to my branch:

   git-checkout ace
   git-pull . master

But that failed:

   Trying really trivial in-index merge...
   fatal: Merge requires file-level merging
   Nope.
   Merging HEAD with 0215ffb08ce99e2bb59eca114a99499a4d06e704
   Merging:
   d7083db038fb98266e331a7f96198ec35a12367a A partial fix BUG 061124 (crashing when 1ms interrrupts).
   0215ffb08ce99e2bb59eca114a99499a4d06e704 Linux 2.6.19
   found 1 common ancestor(s):
   1abbfb412b1610ec3a7ec0164108cee01191d9f5 [PATCH] x86_64: fix bad page state in process 'swapper'
   Auto-merging kernel/fork.c
   CONFLICT (content): Merge conflict in kernel/fork.c
   Auto-merging kernel/spinlock.c
   CONFLICT (content): Merge conflict in kernel/spinlock.c

   Automatic merge failed; fix conflicts and then commit the result.

I then searched the net for how to resolve conflicts, seems you should start by doing a git-diff, so I did and I get this:

   diff --cc kernel/fork.c
   index d74b4a5,8cdd3e7..0000000
   --- a/kernel/fork.c
   +++ b/kernel/fork.c
   diff --cc kernel/spinlock.c
   index f4d1718,2c6c2bf..0000000
   --- a/kernel/spinlock.c
   +++ b/kernel/spinlock.c

And git-status shows:

   # On branch refs/heads/ace
   #
   # Updated but not checked in:
   #   (will commit)
   #
   #       modified: Documentation/rtc.txt
   #       modified: Makefile
   #       modified: arch/arm/configs/assabet_defconfig
   #       modified: arch/arm/configs/cerfcube_defconfig
   ......
   #       modified: sound/usb/usbaudio.c
   #       modified: usr/Makefile
   #
   #
   # Changed but not updated:
   #   (use git-update-index to mark for commit)
   #
   #       unmerged: kernel/fork.c
   #       modified: kernel/fork.c
   #       unmerged: kernel/spinlock.c
   #       modified: kernel/spinlock.c
   #

So what have I done wrong? Did the pull complete and I just need to resolve this or do I need to redo the git-pull?

Thanks,

Wink Saville

On Friday 01 December 2006 07:06, Wink Saville wrote: ...

I am not the worlds expert in this, but since most seem to be in bed I'll attempt to answer you

...

These show that these two files had some conflicts in the contents from the kernel and your local branch ...

...

Nothing - its asking you to manually resolve the conflict.  

Take a look in these two files - you should see conflict markers of the form <<<<<<<<<<<<<<<< some content ================ some other content

which is the contents that failed from your side and the new version of the kernel you pulled in.

Edit so the files have sensible content

then use

git update-index <filename>

to tell git that that particular conflict has been resolved.

When you have done that for both files

just do 

git commit

Alan Chandler wrote:

That's what I thought but there isn't any "<<<<<" and git-diff also seems to indicate no differences:

wink@winkc2d1:~/linux/linux-2.6$ git-diff kernel/fork.c diff --cc kernel/fork.c index d74b4a5,8cdd3e7..0000000

On Friday 01 December 2006 07:41, Wink Saville wrote:

This is at the limit of my understanding, but perhaps file permission problems could have been the cause (was also thinking white space - but to my recollection is that that DOES cause resolution markers)

I think you'll have to wait for experts from the list to comment.

On Thu, 30 Nov 2006, Wink Saville wrote:

Hmm. That doesn't look like a conflict. If it had a real conflict, I'd have expected to see it mentioned in that diff..

This may be a stupid question, but if you haven't actually ever needed to do any file-level merges before, this may be the first time you've actually had the external 3-way "merge" program called, and that's one of the few things that git still depends on _external_ programs for. And if that program is broken or missing, you'd get bubkis.

(This is hopefully getting fixed, and we'll have one less external dependency to worry about, but it's the only thing that springs to mind)

That's especially true since the merge-head your log shows wasn't even all that long ago: there's just 80 commits since that common merge base, and only two of them even change those two files, and only in rather simple ways at that.

So my guess is that there wasn't actually a conflict at all, but the "merge" program (usually in /usr/bin/merge) returned an error for some reason. What does "which merge" and "rpm -qf /usr/bin/merge" say?

But you can also do "git diff --ours" (or "git diff --their") to get a simple two-way diff of the end result of the merge to what you were looking at.

Linus Torvalds wrote:

Earlier had a problem with git wanting merge but didn't have it and couldn't figure out which package it was in Ubuntu:( So I symlinked merge to kdiff3 which worked at the time:

wink@winkc2d1:~/linux/linux-2.6$ ls -al /usr/bin/merge lrwxrwxrwx 1 root root 6 2006-11-17 19:24 /usr/bin/merge -> kdiff3

But doesn't/didn't work this time.

I tried "git diff --ours"

wink@winkc2d1:~/linux/linux-2.6$ git diff --ours
* Unmerged path kernel/fork.c

On Thu, 30 Nov 2006, Wink Saville wrote:

Ahh. I'm pretty sure that is it.

No, kdiff3 probably doesn't have the same semantics, so better get the "real" merge. It's almost certainly in the rcs package, so "emerge rcs" should do it.

Or whatever system Ubuntu uses. 

On Thu, 30 Nov 2006, Linus Torvalds wrote:

..and just to be safe, remove the symlink first, so that you don't end up overwriting the "kdiff3" binary by mistake when you install the real "merge". Not that I think emerge is quite that stupid a package manager, but anyway..

On Friday 01 December 2006 08:00, Linus Torvalds wrote:

Ubuntu is a Debian based. I think it uses Synaptic as its package manager gui with the standard Debian apt-xxx tools underneath.

Linus Torvalds wrote:

Ubuntu is debian based and I use Synaptic GUI, a front end to apt-get. My earlier problem was I couldn't find which package "merge" was in. But now I just figured it out by going to debian.org and using "Search the contents of packages" for "merge". Turns out "merge" is in devel/rcs which of course the whole world knows, unless your a neophyte like me:)

Any way after getting the real merge, I reverted the first pull and re-did it and all was well:

wink@winkc2d1:~/linux/linux-2.6$ git-checkout -f wink@winkc2d1:~/linux/linux-2.6$ git-status # On branch refs/heads/ace nothing to commit wink@winkc2d1:~/linux/linux-2.6$ git-pull . master Trying really trivial in-index merge... fatal: Merge requires file-level merging Nope. Merging HEAD with 0215ffb08ce99e2bb59eca114a99499a4d06e704 Merging: d7083db038fb98266e331a7f96198ec35a12367a A partial fix BUG 061124 (crashing when 1ms interrrupts). 0215ffb08ce99e2bb59eca114a99499a4d06e704 Linux 2.6.19 found 1 common ancestor(s): 1abbfb412b1610ec3a7ec0164108cee01191d9f5 [PATCH] x86_64: fix bad page state in process 'swapper' Auto-merging kernel/fork.c Auto-merging kernel/spinlock.c

Merge made by recursive.
  Documentation/rtc.txt                         |  463 ++++++++++++++++---------
  Makefile                                      |    2
  arch/arm/configs/assabet_defconfig            |    1
  arch/arm/configs/cerfcube_defconfig           |    1
  arch/arm/configs/corgi_defconfig              |    1
......
  sound/pci/emu10k1/emu10k1_main.c              |    1
  sound/pci/hda/patch_realtek.c                 |    2
  sound/pci/hda/patch_sigmatel.c                |   14 -
  sound/usb/usbaudio.c                          |    3
  usr/Makefile                                  |    2
  92 files changed, 888 insertions(+), 371 deletions(-)
  create mode 100644 arch/mips/kernel/topology.c
  create mode 100644 arch/um/os-Linux/execvp.c
  create mode 100644 include/asm-arm/mach/udc_pxa2xx.h

Thank you very much,

Wink

On Friday 01 December 2006 08:22, Wink Saville wrote:

I'm actually using Debian Unstable and basically use the git-core package. Its at version 1.4.4.1 - so right up to date, and of course resolves all dependencies automatically.

Doesn't Ubuntu have git-core in its repository?

Alan Chandler wrote:

It was an older version, so I started at the source.

W

[ Tangentially related.. ]

On Thu, 30 Nov 2006, Wink Saville wrote:

Btw, what's the status of the xdl_merge() thing in "pu"?

It would be lovely if this could be one less thing we ever need to worry about, just because we just do it ourselves. But quite frankly, I've never looked at the RCS merge logic, so while I peeked at the xdl_merge patch itself, I have absolutely zero way of judging it.

But the patch in "pu" to make merge-recursive use it looks pretty, and removes more lines than it adds, and the xdl_merge() code itself _looked_ sane even if I can't judge the algorithm, so...

Anyway, here's one vote for trying to move this thing into "next" (first asking whether all of Dscho's fixup patches got merged too?).

I realize that git-cvsserver (and my toy merge-file.c that isn't used by anything real) also use the external merge program, so we can't remove the dependency entirely (both in git.spec.in and documentation) without fixing those too, but at least we would _practically_ be able to ignore it for all normal users. And cvsserver would probably be quite fixable too..

Linus Torvalds <torvalds@osdl.org> writes:

I am *BEHIND*. There are too many distractions these days (read: day job) and I haven't touched git in any significant ways for the last several days.

I haven't looked at the code any further than minimally checking its external interface to be able to interface it with merge-recursive and no more. Namely:

 - I haven't read the algorithm to judge its correctness;

 - I haven't looked for leaks;

 - I haven't used the resulting merge-recursive in any real
   merge; some of our tests do rely on a correctly working
   merge-recursive, so it is not like the algorithm is always
   emitting "boo ha ha" and returning no conflicts ;-).

 - I haven't benched it to see how much performance is gained
   by bypassing an extra fork+exec.

Among the four patches Johannes sent out to the list and Davide, one was already in his original patch I have in 'pu', another makes the same return value change I did myself when interfacing the code with merge-recursive. I have queued the remaining two in 'pu', so there should be nothing missing.

One of them is marked as "fix off by one error" but it was about more than off by one (the code walks two arrays using one index for each, but the original code incorrectly used the same index to access both arrays at one point, which was also fixed). I did mind the lack of explanation and wanted to reword the log message, but as I said, I haven't read the algorithm to understand what the code is doing enough, so I cannot write anything useful there yet X-<, which is one of the reasons why it is still queued in 'pu'.

Hi,

On Fri, 1 Dec 2006, Junio C Hamano wrote:

With my track record of blamable patches, that should be done by somebody else than me.

Neither have I.

I have. There is a subtle difference to merge, but it might be serious enough:

diff --just-made-up orig new1
 Hello world
+This conflicts
 Bye bye world
+This does not conflict

diff --just-made-up orig new2
 Hello world
+This is different in new2
 Bye bye world

If my interpretation of the test is correct, then the last line of new1 will _not_ conflict with xdl_merg( as is, but with RCS merge. I will fix that shortly.

There is room for improvement, but I get shaky numbers betwen 31% and 118% (runtime git-merge-recursive xdl_merge() / RCS merge). These are extremely ad-hoc generated numbers, so handle with care. My gut feeling is that a few improvements in the code will give a rough 30%-50% in the average case.

These improvements include not parsing orig twice, and compacting the merge script before applying it.

Yeah, sorry. When I sent the patches, I did not see xdl_merge() in pu.

Sorry again. I fixed that bug in the middle of the night, and committed the next day, trying to deduct what I fixed.

Again, I do not see the patches in pu, though. I will concoct a nice commit message later today, okay?

Linus, you raised the concern that git-cvsserer still relies on external merge. I'd just bastardize git-merge-one-file to work as a replacement of RCS merge (just like git apply works as a replacement of patch), in addition to its original function.

Ciao, Dscho

Johannes Schindelin wrote:

Have you had time to look at my test cases? As I said, I found them very useful when debugging my git-diff3 code, and (hopefully) you will find them to be equally useful.

All the best,

Ramsay

On Tue, 5 Dec 2006, Ramsay Jones wrote:

It might be interesting to also do a simple test:

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

 - ignore all the trivial ones that didn't have any file-level merging at 
   all (ie done entirely in the index)

 - for all the rest, just compare what the end result is when re-doing the 
   merge with "xdl_merge" vs "external 3-way merge".

[ Side note: DO NOT COMPARE AGAINST THE ACTUAL RESULT IN GIT OR IN THE 
  KERNEL ARCHIVE! Those will obviously have been fixed up by humans in the 
  event of a data conflict, and sometimes even in the _absense_ of a data 
  conflict (ie "git commit --amend" to fix up something that got mismerged 
  perfectly automatically or whatever).

  So a script should literally re-do the merge two ways, and compare the 
  end result ]

Is that any "proof"? Of course not. And it will probably show differences due to any conflict handling, but a lot of the time you'd expect to get exactly the same end result, so the occasional differences are going to be just all the more interesting ("it resolved differently, but it was an equally good resolve" is interesting data on its own).

Anybody want to write a small script to do this?

Linus Torvalds <torvalds@osdl.org> writes:

I was planning to do this today anyway. Thanks for the reminder.

Hi,

On Tue, 5 Dec 2006, Linus Torvalds wrote:

I tried that already. Only to find that the first merge I tested showed one change between RCS merge and xdl_merge(): xdl_merge() does not yet take context into account, so these two diffs

@@ bla
 Ten
+weary
 footsore
+wanderers
 all
 in
 a

and

@@ blub
 Ten
+weird
 footsore
 all
 in
 a

will conflict only for the weary/weird lines, _not_ for wanderers.

Besides, my recent patch series was gained exactly by that test. Though I did not extend that test to the Linux repo, and I am by no means finished with the git one.

Ciao,

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

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

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

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

Thanks.

Looking at some other cases after applying your patch, I noticed that I really like one thing that your version does over what RCS merge does.

With RCS merge, a run of lines that are modified the same way in both branches appear twice, like this:

	<<< orig
        alpha
        bravo
        charlie
        ...
	x-ray
	yankee
        zulu
        ===
        alpha
        bravo
        charlie
        ...
        x-ray
        yankee
        zebra
        >>> new

The common part at the beginning (or at the end for that matter) can be hoisted outside, to produce:

        alpha
        bravo
        charlie
        ...
	x-ray
	yankee
	<<< orig
        zulu
        ===
        zebra
        >>> new

and your version seems to get this right.

When I had to deal with this kind of conflicts, I ended up splitting the buffer in two, and ran M-x compare-windows to find the true differences between the choices. It was frustrating. (I admit a big reason is I do not normally work in X environment and do not tend to use xdiff -U or Kompare).

This is especially noticeable when recreating diff-delta.c merge conflict in commit b485db98. It's fun to see this large hunk reduced down to only two lines ;-).

<<<<<<< HEAD/diff-delta.c
	/*
	 * Determine a limit on the number of entries in the same hash
	 * bucket.  This guard us against patological data sets causing
	 * really bad hash distribution with most entries in the same hash
	 * bucket that would bring us to O(m*n) computing costs (m and n
	 * corresponding to reference and target buffer sizes).
	 *
	 * The more the target buffer is large, the more it is important to
	 * have small entry lists for each hash buckets.  With such a limit
	 * the cost is bounded to something more like O(m+n).
	 */
	hlimit = (1 << 26) / trg_bufsize;
	if (hlimit < 16)
		hlimit = 16;

	/*
	 * Now make sure none of the hash buckets has more entries than
	 * we're willing to test.  Otherwise we short-circuit the entry
	 * list uniformly to still preserve a good repartition across
	 * the reference buffer.
	 */
	for (i = 0; i < hsize; i++) {
		if (hash_count[i] < hlimit)
			continue;
		entry = hash[i];
		do {
			struct index *keep = entry;
			int skip = hash_count[i] / hlimit / 2;
			do {
				entry = entry->next;
			} while(--skip && entry);
			keep->next = entry;
		} while(entry);
	}
	free(hash_count);

	return hash;
=======
	/*
	 * Determine a limit on the number of entries in the same hash
	 * bucket.  This guard us against patological data sets causing
	 * really bad hash distribution with most entries in the same hash
	 * bucket that would bring us to O(m*n) computing costs (m and n
	 * corresponding to reference and target buffer sizes).
	 *
	 * The more the target buffer is large, the more it is important to
	 * have small entry lists for each hash buckets.  With such a limit
	 * the cost is bounded to something more like O(m+n).
	 */
	hlimit = (1 << 26) / trg_bufsize;
	if (hlimit < 16)
		hlimit = 16;

	/*
	 * Now make sure none of the hash buckets has more entries than
	 * we're willing to test.  Otherwise we short-circuit the entry
	 * list uniformly to still preserve a good repartition across
	 * the reference buffer.
	 */
	for (i = 0; i < hsize; i++) {
		if (hash_count[i] < hlimit)
			continue;
		entry = hash[i];
		do {
			struct index *keep = entry;
			int skip = hash_count[i] / hlimit / 2;
			do {
				entry = entry->next;
			} while(--skip && entry);
			keep->next = entry;
		} while(entry);
	}
	free(hash_count);

	return hash-1;

Hi,

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

Gee, thanks!

Actually, this was what I intended to do first when somebody submitted a builtin merge: Be clever about what is a conflict and what not.

Speaking about a builtin merge: I like the fact that git-apply also works outside of git repositories. It makes life easier to have a sane patcher around.

Now, I'd like the same with git-diff, and an RCS merge replacement... Of course, what with all those porcelainish commands we should not add new commands, but enhance existing ones. Any ideas which ones?

Ciao, Dscho

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

Well, git-apply is designed as a better "patch", so it is natural that it works in a non-git directory [*1*].

I am not sure what you mean by a builtin merge that works outside the context of git. Do you mean a pure RCS merge replacement that takes three files and spits out the result in one of them? If so that would probably deserve to be a separate command, because I do not think of a use for such a thing inside git. We've done merge-recursive.c already so it would not need an external 'merge'. If somebody is so inclined to to do the "merge-resolve" strategy, I think the right way is to make a single program that does what git-merge-index and merge-one-file does without fork nor exec, so it would not need an external 'merge' either.

Yes, back when I was actively hacking git-diff, I dreamt about a variant that takes two or more (non-git managed) directories and does an equivalent of diff-tree with -M/-C/.../-c/--cc. It would be cool and useful.

I understand your aversion to new commands, but I do not think you can avoid it if what you mean is an RCS merge replacement.

The diff that works on "two or more directories without anything git" could be just a new option to "git diff", though.

But I am not going to do it myself; it's usually a lot faster for me to just do "git init-db; git add . " on an extracted tarball.

[Footnote]

*1* ... and that is one of the reasons why it does not even try to read the index unless it is told to do so.

And we should not make it "detect we are in git repository" and default to --index either. Often running without --index is useful inside a git repository. I would say roughly 50% of the time I use the command with --index and the rest without, so "more often" argument unfortunately does not apply to "apply".

I wish it were "2% without --index, 98% with --index". Then we could easily say "add '--no-index if you do not want to".

Junio C Hamano wrote:

Is it with "try harder" option?

Hi,

On Tue, 5 Dec 2006, Jakub Narebski wrote:

Yes, it uses the XDL_MERGE_ZEALOUS option.

Ciao, Dscho

Junio C Hamano <junkio@cox.net> writes:

And all merges in linux-2.6.git archive either result in conflict with both 'merge' implementations, or cleanly resolves the same way with both 'merge' implementations. I have not compared the conflicted cases yet, but at least it gives me a warm fuzzy feeling to see that autocommitted stuff are sensible.

Hi,

On Wed, 6 Dec 2006, Junio C Hamano wrote:

Thank you! Slowly I also get a warm fuzzy feeling...

My idea, to have an inbuilt work-alike to RCS merge, was not only instigated by my liking the zealous option, but also to be able to add relatively fast tests.

Originally, I thought that building in git-merge-one-file, and enhancing it to recognize by the parameters if it should act as a merge replacement, would be the way to go. Should I do this, or rather add builtin-merge-file?

Ciao, Dscho

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

All in-tree users of git-merge-one-file is of this pattern:

	git merge-index -o git-merge-one-file -a

so I was hoping we can capture this whole thing as a single command (merge-index would fork+exec a merge-one-file per unmerged path), instead of doing merge-one-file as a built-in.

In any case, the way your xdl-merge engine is done, it should be almost trivial to write a pure 'RCS merge replacement' as a totally separate program -- the bulk of the new code would be parsing parameters, opening the three input files, populating mmfile structures and writing the result out, and there would be almost no "smart" in that part of the code you would want to share with the git-aware version.

Hi,

On Wed, 6 Dec 2006, Junio C Hamano wrote:

Yes, this was also my thinking. But notice how git-merge-one-file does much more than just merge? So, you end up rewriting it in C anyway, if you want to make merge-index not fork unless "-o cmd" is passed.

Actually, I just did that. I will add some test cases (to reflect your option (3) in another thread), and submit.

Ciao, Dscho

Hi,

On Tue, 5 Dec 2006, Ramsay Jones wrote:

Not really. Besides, I did _not_ implement a full diff3, but _just_ the merge. I.e. my function does not output anything, but (in theory) fills a buffer with what merge would have written into the first file.

However, once I understand how your tests work, I'll try to concoct a test script for git-with-xdl_merge.

Ciao,

On Thu, 30 Nov 2006, Linus Torvalds wrote:

Side note: the historically more common failure was to not have a merge program at all, but exactly because that was common, we check for that and complain about it. So that's not it for you - you do have a 'merge' program somewhere that git found.

But if it returns the wrong error code, or doesn't do anything at all (ie you have "merge", but it's not the 3-way merge we expect, or it doesn't take the "-L" argument we use, or it's simply buggy) then that might explain the behaviour you report.

Or it might be something totally different. This is just a wild theory.