Resolving conflicts

Resolving conflicts

[Wink Saville]

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

Re: Resolving conflicts

[Alan Chandler]

On Friday 01 December 2006 07:06, Wink Saville wrote:
...
>    git-pull . master
>
> But that failed:
I am not the worlds expert in this, but since most seem to be in bed I'll 
attempt to answer you

...
>    CONFLICT (content): Merge conflict in kernel/fork.c
>    Auto-merging kernel/spinlock.c
>    CONFLICT (content): Merge conflict in kernel/spinlock.c

These show that these two files had some conflicts in the contents from the 
kernel and your local branch
...
> And git-status shows:
...
>    # 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?

Nothing - its asking you to manually resolve the conflict.  

> Did the pull complete and I just need to resolve this or
> do I need to redo the git-pull?

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

Re: Resolving conflicts

[Wink Saville]

Alan Chandler wrote:
> On Friday 01 December 2006 07:06, Wink Saville wrote:
> 
> Take a look in these two files - you should see conflict markers of the form
> <<<<<<<<<<<<<<<< 
> some content
> ================
> some other content
> 

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
--- a/kernel/fork.c
+++ b/kernel/fork.c
wink@winkc2d1:~/linux/linux-2.6$


wink@winkc2d1:~/linux/linux-2.6$ git-diff kernel/spinlock.c
diff --cc kernel/spinlock.c
index f4d1718,2c6c2bf..0000000
--- a/kernel/spinlock.c
+++ b/kernel/spinlock.c
wink@winkc2d1:~/linux/linux-2.6$

Thanks,

Re: Resolving conflicts

[Alan Chandler]

On Friday 01 December 2006 07:41, Wink Saville wrote:
> Alan Chandler wrote:
> > On Friday 01 December 2006 07:06, Wink Saville wrote:
> >
> > Take a look in these two files - you should see conflict markers of the
> > form <<<<<<<<<<<<<<<<
> > some content
> > ================
> > some other content
>
> That's what I thought but there isn't any "<<<<<" and git-diff also seems
> to indicate no differences:

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

Re: Resolving conflicts

[Linus Torvalds]

On Thu, 30 Nov 2006, Wink Saville wrote:
> 
> 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

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.

Re: Resolving conflicts

[Wink Saville]

Linus Torvalds wrote:
> 
> On Thu, 30 Nov 2006, Wink Saville wrote:
>> 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
> 
> 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
> -
> To unsubscribe from this list: send the line "unsubscribe git" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

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
diff --git a/kernel/fork.c b/kernel/fork.c
* Unmerged path kernel/spinlock.c
diff --git a/kernel/spinlock.c b/kernel/spinlock.c
wink@winkc2d1:~/linux/linux-2.6$

Wink

Not too helpful:(

Re: Resolving conflicts

[Linus Torvalds]

On Thu, 30 Nov 2006, Wink Saville 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:

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. 

Re: Resolving conflicts

[Linus Torvalds]

On Thu, 30 Nov 2006, Linus Torvalds wrote:
> 
> 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.

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

Re: Resolving conflicts

[Alan Chandler]

On Friday 01 December 2006 08:00, Linus Torvalds wrote:
> On Thu, 30 Nov 2006, Linus Torvalds wrote:
> > 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.
>
> ..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..

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

Re: Resolving conflicts

[Wink Saville]

Linus Torvalds wrote:
> 
> On Thu, 30 Nov 2006, Linus Torvalds wrote:
>> 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.
> 
> ..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..
> 
> 		Linus
> 

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

Re: Resolving conflicts

[Alan Chandler]

On Friday 01 December 2006 08:22, Wink Saville 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:)

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

Re: Resolving conflicts

[Wink Saville]

Alan Chandler wrote:
> On Friday 01 December 2006 08:22, Wink Saville 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:)
> 
> 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?
> 
It was an older version, so I started at the source.

W

Re: Resolving conflicts

[Linus Torvalds]

[ Tangentially related.. ]

On Thu, 30 Nov 2006, Wink Saville 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:

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

Re: Resolving conflicts

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> [ Tangentially related.. ]
>
> On Thu, 30 Nov 2006, Wink Saville 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:
>
> Btw, what's the status of the xdl_merge() thing in "pu"?

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

using xdl_merge(), was Re: Resolving conflicts

[Johannes Schindelin]

Hi,

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

> Linus Torvalds <torvalds@osdl.org> writes:
> 
> > [ Tangentially related.. ]
> >
> > On Thu, 30 Nov 2006, Wink Saville 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:
> >
> > Btw, what's the status of the xdl_merge() thing in "pu"?
> 
> 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;

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

>  - I haven't looked for leaks;

Neither have I.

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

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

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.

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

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

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

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

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

[Ramsay Jones]

Johannes Schindelin wrote:
> On Fri, 1 Dec 2006, Junio C Hamano wrote:
>> Linus Torvalds <torvalds@osdl.org> writes:
>>> On Thu, 30 Nov 2006, Wink Saville 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:
>>> Btw, what's the status of the xdl_merge() thing in "pu"?
>> 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;
> 
> With my track record of blamable patches, that should be done by somebody 
> else than me.
> 

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.

> Ciao,
> Dscho
> 

All the best,

Ramsay

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

[Linus Torvalds]

On Tue, 5 Dec 2006, Ramsay Jones 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.

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?

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

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> On Tue, 5 Dec 2006, Ramsay Jones 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.
>
> 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

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

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

[Johannes Schindelin]

Hi,

On Tue, 5 Dec 2006, Linus Torvalds wrote:

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

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,

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

[Junio C Hamano]

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

> On Tue, 5 Dec 2006, Linus Torvalds wrote:
>
>>  - 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

[PATCH] xdl_merge(): fix and simplify conflict handling

[Johannes Schindelin]

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

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

Re: [PATCH] xdl_merge(): fix and simplify conflict handling

[Junio C Hamano]

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;
>>>>>>> 38fd0721d0a2a1a723bc28fc0817e3571987b1ef/diff-delta.c

Re: [PATCH] xdl_merge(): fix and simplify conflict handling

[Johannes Schindelin]

Hi,

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

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

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

Re: [PATCH] xdl_merge(): fix and simplify conflict handling

[Junio C Hamano]

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

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

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.

> Now, I'd like the same with git-diff, and an RCS merge replacement...

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

Re: [PATCH] xdl_merge(): fix and simplify conflict handling

[Jakub Narebski]

Junio C Hamano wrote:

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

Is it with "try harder" option?
-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

Re: [PATCH] xdl_merge(): fix and simplify conflict handling

[Johannes Schindelin]

Hi,

On Tue, 5 Dec 2006, Jakub Narebski wrote:

> Junio C Hamano wrote:
> 
> > 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.
> 
> Is it with "try harder" option?

Yes, it uses the XDL_MERGE_ZEALOUS option.

Ciao,
Dscho

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

[Junio C Hamano]

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

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
>
>> On Tue, 5 Dec 2006, Linus Torvalds wrote:
>>
>>>  - 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.

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.

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

[Johannes Schindelin]

Hi,

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

> Junio C Hamano <junkio@cox.net> writes:
> 
> > Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
> >
> >> On Tue, 5 Dec 2006, Linus Torvalds wrote:
> >>
> >>>  - 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.
> 
> 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.

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

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

[Junio C Hamano]

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

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

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.

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

[Johannes Schindelin]

Hi,

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

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

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.

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

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

Ciao,
Dscho

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

[Johannes Schindelin]

Hi,

On Tue, 5 Dec 2006, Ramsay Jones wrote:

> Have you had time to look at my test cases?

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,

Re: Resolving conflicts

[Linus Torvalds]

On Thu, 30 Nov 2006, Linus Torvalds wrote:
> 
> 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?

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.