Automatic merge failed, fix up by hand

Automatic merge failed, fix up by hand

[Len Brown]

I'm having trouble using git for merging kernel trees.

git seems to manufacture conflicts in files that
I never touched, and on some files it completely
throws up its arms, see "Not handling case" below.

Not clear how I got into this state -- probably
something to do with adding commits on branches
and them git-pull-branch'ing them into the master;
combined with updating the master from-linus.

when i switch heads, I simply remove .git/HEAD
and link it to the refs/heads/master or refs/heads/acpi-2.6.12
followed by a git checkout -f.  To merge the work
back into the master I switch back to the master
and git-pull-branch per jeff's howto.  I also
periodically pull from-linus after switching
the branch back to the master.

The merge issue below is reproduced in a "git clone -l" copy
with no plain files present.

Got any tips on how to recover?

thanks,
-Len

[lenb@firebird to-akpm.latest]$ git pull ../../from-linus
Packing 842 objects
Unpacking 842 objects
 100% (842/842) done
Trying to merge 81065e2f415af6c028eac13f481fb9e60a0b487b into
702c7e7626deeabb057b6f529167b65ec2eefbdb
Simple merge failed, trying Automatic merge
Auto-merging CREDITS.
Removing Documentation/DocBook/scsidrivers.tmpl
Removing Documentation/dvb/README.dibusb
Removing Documentation/i2c/chips/smsc47b397.txt
Removing Documentation/i2c/sysfs-interface
Removing Documentation/networking/wanpipe.txt
Auto-merging MAINTAINERS.
merge: warning: conflicts during merge
ERROR: Merge conflict in MAINTAINERS.
Removing arch/arm/configs/omnimeter_defconfig
Removing arch/arm/kernel/arch.c
Removing arch/arm/lib/longlong.h
Removing arch/arm/lib/udivdi3.c
Removing arch/arm/mach-omap/Kconfig
Removing arch/arm/mach-omap/Makefile
Removing arch/arm/mach-omap/Makefile.boot
Removing arch/arm/mach-omap/board-generic.c
Removing arch/arm/mach-omap/board-h2.c
Removing arch/arm/mach-omap/board-h3.c
Removing arch/arm/mach-omap/board-innovator.c
Removing arch/arm/mach-omap/board-netstar.c
Removing arch/arm/mach-omap/board-osk.c
Removing arch/arm/mach-omap/board-perseus2.c
Removing arch/arm/mach-omap/board-voiceblue.c
Removing arch/arm/mach-omap/clock.c
Removing arch/arm/mach-omap/clock.h
Removing arch/arm/mach-omap/common.c
Removing arch/arm/mach-omap/common.h
Removing arch/arm/mach-omap/dma.c
Removing arch/arm/mach-omap/fpga.c
Removing arch/arm/mach-omap/gpio.c
Removing arch/arm/mach-omap/irq.c
Removing arch/arm/mach-omap/leds-h2p2-debug.c
Removing arch/arm/mach-omap/leds-innovator.c
Removing arch/arm/mach-omap/leds-osk.c
Removing arch/arm/mach-omap/leds.c
Removing arch/arm/mach-omap/leds.h
Removing arch/arm/mach-omap/mcbsp.c
Removing arch/arm/mach-omap/mux.c
Removing arch/arm/mach-omap/ocpi.c
Removing arch/arm/mach-omap/pm.c
Removing arch/arm/mach-omap/sleep.S
Removing arch/arm/mach-omap/time.c
Removing arch/arm/mach-omap/usb.c
Auto-merging arch/arm/mm/Kconfig.
Auto-merging arch/arm/mm/proc-v6.S.
Auto-merging arch/arm/nwfpe/softfloat.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/arm/nwfpe/softfloat.c.
Auto-merging arch/i386/kernel/acpi/boot.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/i386/kernel/acpi/boot.c.
Auto-merging arch/i386/kernel/acpi/sleep.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/i386/kernel/acpi/sleep.c.
Auto-merging arch/i386/kernel/apic.c.
Auto-merging arch/i386/kernel/nmi.c.
Auto-merging arch/ia64/Kconfig.
Auto-merging arch/ia64/configs/sn2_defconfig.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/ia64/configs/sn2_defconfig.
Auto-merging arch/ia64/configs/tiger_defconfig.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/ia64/configs/tiger_defconfig.
Auto-merging arch/ia64/configs/zx1_defconfig.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/ia64/configs/zx1_defconfig.
Auto-merging arch/ia64/kernel/acpi.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/ia64/kernel/acpi.c.
Auto-merging arch/ia64/kernel/domain.c.
Auto-merging arch/ia64/kernel/iosapic.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/ia64/kernel/iosapic.c.
Auto-merging arch/ia64/kernel/perfmon.c.
Removing arch/ia64/sn/include/pci/pcibr_provider.h
Removing arch/ia64/sn/include/pci/pic.h
Removing arch/ia64/sn/include/pci/tiocp.h
Auto-merging arch/ia64/sn/kernel/io_init.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/ia64/sn/kernel/io_init.c.
Removing arch/mips/vr41xx/common/giu.c
Removing arch/ppc/boot/utils/addSystemMap.c
Removing arch/ppc/syslib/ppc4xx_kgdb.c
Removing arch/ppc64/boot/mknote.c
Removing arch/ppc64/boot/piggyback.c
Auto-merging arch/ppc64/kernel/LparData.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/ppc64/kernel/LparData.c.
Auto-merging arch/ppc64/kernel/Makefile.
Removing arch/ppc64/kernel/XmPciLpEvent.c
Auto-merging arch/ppc64/kernel/head.S.
Removing arch/ppc64/kernel/iSeries_pci_reset.c
Auto-merging arch/ppc64/kernel/iommu.c.
Auto-merging arch/sparc64/kernel/traps.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/sparc64/kernel/traps.c.
Auto-merging arch/um/kernel/skas/process.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/um/kernel/skas/process.c.
Removing arch/um/kernel/skas/time.c
Removing arch/um/kernel/tt/time.c
Removing arch/um/kernel/tt/unmap.c
Auto-merging arch/um/os-Linux/elf_aux.c.
Auto-merging arch/x86_64/kernel/smpboot.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in arch/x86_64/kernel/smpboot.c.
Auto-merging arch/x86_64/mm/fault.c.
Auto-merging drivers/acpi/Kconfig.
Auto-merging drivers/acpi/container.c.
Auto-merging drivers/acpi/osl.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/acpi/osl.c.
Auto-merging drivers/acpi/pci_bind.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/acpi/pci_bind.c.
Auto-merging drivers/acpi/pci_irq.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/acpi/pci_irq.c.
Auto-merging drivers/acpi/pci_link.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/acpi/pci_link.c.
Auto-merging drivers/acpi/pci_root.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/acpi/pci_root.c.
Auto-merging drivers/acpi/processor_core.c.
Auto-merging drivers/acpi/processor_idle.c.
Auto-merging drivers/acpi/scan.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/acpi/scan.c.
Auto-merging drivers/acpi/sleep/poweroff.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/acpi/sleep/poweroff.c.
Auto-merging drivers/base/bus.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/base/bus.c.
Auto-merging drivers/base/class.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/base/class.c.
Removing drivers/base/class_simple.c
Auto-merging drivers/char/hpet.c.
Removing drivers/i2c/chips/adm1021.c
Removing drivers/i2c/chips/adm1025.c
Removing drivers/i2c/chips/adm1026.c
Removing drivers/i2c/chips/adm1031.c
Removing drivers/i2c/chips/asb100.c
Removing drivers/i2c/chips/ds1621.c
Removing drivers/i2c/chips/fscher.c
Removing drivers/i2c/chips/fscpos.c
Removing drivers/i2c/chips/gl518sm.c
Removing drivers/i2c/chips/gl520sm.c
Removing drivers/i2c/chips/it87.c
Removing drivers/i2c/chips/lm63.c
Removing drivers/i2c/chips/lm75.c
Removing drivers/i2c/chips/lm75.h
Removing drivers/i2c/chips/lm77.c
Removing drivers/i2c/chips/lm78.c
Removing drivers/i2c/chips/lm80.c
Removing drivers/i2c/chips/lm83.c
Removing drivers/i2c/chips/lm85.c
Removing drivers/i2c/chips/lm87.c
Removing drivers/i2c/chips/lm90.c
Removing drivers/i2c/chips/lm92.c
Removing drivers/i2c/chips/max1619.c
Removing drivers/i2c/chips/pc87360.c
Removing drivers/i2c/chips/sis5595.c
Removing drivers/i2c/chips/smsc47b397.c
Removing drivers/i2c/chips/smsc47m1.c
Removing drivers/i2c/chips/via686a.c
Removing drivers/i2c/chips/w83627hf.c
Removing drivers/i2c/chips/w83781d.c
Removing drivers/i2c/chips/w83l785ts.c
Auto-merging drivers/ide/Kconfig.
Removing drivers/ide/cris/ide-v10.c
Auto-merging drivers/ide/ide-floppy.c.
Auto-merging drivers/ide/pci/generic.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/ide/pci/generic.c.
Auto-merging drivers/ide/pci/serverworks.c.
Auto-merging drivers/ide/ppc/pmac.c.
Auto-merging drivers/ide/setup-pci.c.
Removing drivers/input/gameport/cs461x.c
Removing drivers/input/gameport/vortex.c
Removing drivers/isdn/hisax/enternow.h
Removing drivers/isdn/hisax/st5481_hdlc.c
Removing drivers/isdn/hisax/st5481_hdlc.h
Removing drivers/isdn/sc/debug.c
Removing drivers/macintosh/macserial.c
Removing drivers/macintosh/macserial.h
Auto-merging drivers/md/md.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/md/md.c.
Removing drivers/media/dvb/b2c2/skystar2.c
Removing drivers/media/dvb/dibusb/Kconfig
Removing drivers/media/dvb/dibusb/Makefile
Removing drivers/media/dvb/dibusb/dvb-dibusb-core.c
Removing drivers/media/dvb/dibusb/dvb-dibusb-dvb.c
Removing drivers/media/dvb/dibusb/dvb-dibusb-fe-i2c.c
Removing drivers/media/dvb/dibusb/dvb-dibusb-firmware.c
Removing drivers/media/dvb/dibusb/dvb-dibusb-remote.c
Removing drivers/media/dvb/dibusb/dvb-dibusb-usb.c
Removing drivers/media/dvb/dibusb/dvb-dibusb.h
Removing drivers/media/dvb/dibusb/dvb-fe-dtt200u.c
Removing drivers/mtd/maps/db1550-flash.c
Removing drivers/mtd/maps/db1x00-flash.c
Removing drivers/mtd/maps/elan-104nc.c
Removing drivers/mtd/maps/pb1550-flash.c
Removing drivers/mtd/maps/pb1xxx-flash.c
Removing drivers/mtd/nand/tx4925ndfmc.c
Removing drivers/mtd/nand/tx4938ndfmc.c
Auto-merging drivers/net/8139cp.c.
ERROR: drivers/net/dm9000.c: Not handling case  ->
5fddc0ff887822fde5cbf904e3db8e46b4becca1 ->
6440a892bb813ca4a08e0a1878cf0dedb43b254d
Removing drivers/net/fmv18x.c
Removing drivers/net/sk_g16.c
Removing drivers/net/sk_g16.h
Removing drivers/net/skfp/lnkstat.c
Removing drivers/net/skfp/smtparse.c
Removing drivers/net/smc-mca.h
Auto-merging drivers/net/tg3.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/net/tg3.c.
Removing drivers/pci/hotplug/acpiphp_pci.c
Removing drivers/pci/hotplug/acpiphp_res.c
Auto-merging drivers/pci/msi.c.
Auto-merging drivers/pci/quirks.c.
Auto-merging drivers/pnp/card.c.
Removing drivers/scsi/pci2000.c
Removing drivers/scsi/pci2220i.c
Removing drivers/scsi/pci2220i.h
Removing drivers/scsi/psi_dale.h
Removing drivers/scsi/psi_roy.h
Removing drivers/serial/bast_sio.c
Auto-merging drivers/serial/sn_console.c.
Removing drivers/usb/atm/usb_atm.c
Removing drivers/usb/atm/usb_atm.h
Auto-merging drivers/usb/input/wacom.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in drivers/usb/input/wacom.c.
Auto-merging drivers/usb/net/zd1201.c.
Removing fs/freevxfs/vxfs_kcompat.h
ERROR: fs/ioprio.c: Not handling case  ->
97e1f088ba00b3b63f7f9ea594b756781fcf6596 ->
d1c1f2b2c9da9796affc6be18b8793489b9f2873
Auto-merging fs/jffs2/symlink.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in fs/jffs2/symlink.c.
Auto-merging fs/jfs/inode.c.
Auto-merging fs/jfs/jfs_logmgr.c.
Auto-merging fs/jfs/jfs_logmgr.h.
Auto-merging fs/jfs/jfs_txnmgr.c.
Auto-merging fs/jfs/super.c.
Auto-merging fs/jfs/symlink.c.
Auto-merging fs/namei.c.
Auto-merging fs/nfs/dir.c.
Auto-merging fs/nfs/file.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in fs/nfs/file.c.
Auto-merging fs/nfs/inode.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in fs/nfs/inode.c.
ERROR: fs/nfs/nfs3acl.c: Not handling case  ->
1b7a3ef2f8131f4f9c02534f55d5a42de4633f67 ->
6a5bbc0ae941aa690e1f73137cbce4af38902092
Auto-merging fs/nfs/nfs3proc.c.
Auto-merging fs/nfs/nfs4proc.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in fs/nfs/nfs4proc.c.
Auto-merging fs/nfs/proc.c.
Auto-merging fs/nfs/read.c.
ERROR: fs/nfs_common/nfsacl.c: Not handling case  ->
18c58c32e326281bfa7226edbaaec135b45c2b70 ->
251e5a1bb1c4cbe0308c042073b0d83cfe71d73d
Auto-merging fs/nfsd/nfssvc.c.
Auto-merging fs/ntfs/ChangeLog.
merge: warning: conflicts during merge
ERROR: Merge conflict in fs/ntfs/ChangeLog.
Auto-merging fs/ntfs/aops.c.
Auto-merging fs/ntfs/mft.c.
Auto-merging fs/proc/base.c.
Auto-merging fs/reiserfs/inode.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in fs/reiserfs/inode.c.
Auto-merging fs/sysfs/symlink.c.
Auto-merging include/acpi/acpi_bus.h.
merge: warning: conflicts during merge
ERROR: Merge conflict in include/acpi/acpi_bus.h.
Auto-merging include/acpi/acpi_drivers.h.
merge: warning: conflicts during merge
ERROR: Merge conflict in include/acpi/acpi_drivers.h.
Auto-merging include/asm-i386/processor.h.
Auto-merging include/asm-ia64/iosapic.h.
merge: warning: conflicts during merge
ERROR: Merge conflict in include/asm-ia64/iosapic.h.
Removing include/asm-m32r/m32102peri.h
Removing include/asm-ppc/fsl_ocp.h
Auto-merging include/asm-ppc/ibm44x.h.
Removing include/asm-ppc64/iSeries/HvCallCfg.h
Removing include/asm-ppc64/iSeries/LparData.h
Auto-merging include/asm-ppc64/iSeries/LparMap.h.
merge: warning: conflicts during merge
ERROR: Merge conflict in include/asm-ppc64/iSeries/LparMap.h.
Removing include/asm-ppc64/iSeries/XmPciLpEvent.h
Removing include/asm-ppc64/iSeries/iSeries_proc.h
Auto-merging include/asm-sh/unistd.h.
Auto-merging include/asm-sparc64/thread_info.h.
Auto-merging include/asm-x86_64/processor.h.
Auto-merging include/linux/acpi.h.
Auto-merging include/linux/fs.h.
Removing include/linux/ioc4_common.h
Removing include/linux/netfilter_ipv4/lockhelp.h
Auto-merging include/linux/nfs_fs.h.
merge: warning: conflicts during merge
ERROR: Merge conflict in include/linux/nfs_fs.h.
Removing include/linux/pci-dynids.h
Auto-merging include/linux/pci.h.
Auto-merging include/linux/pci_ids.h.
Auto-merging include/linux/sunrpc/xdr.h.
merge: warning: conflicts during merge
ERROR: Merge conflict in include/linux/sunrpc/xdr.h.
Removing include/linux/xattr_acl.h
Auto-merging include/net/ax25.h.
Auto-merging include/net/sock.h.
Auto-merging kernel/sched.c.
Auto-merging kernel/signal.c.
Auto-merging kernel/timer.c.
Auto-merging mm/shmem.c.
Auto-merging net/decnet/dn_neigh.c.
Auto-merging net/ipv4/icmp.c.
Auto-merging net/ipv4/ipcomp.c.
Auto-merging net/ipv4/tcp.c.
Auto-merging net/ipv4/tcp_ipv4.c.
Auto-merging net/ipv4/tcp_output.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in net/ipv4/tcp_output.c.
Removing net/ipv4/utils.c
Auto-merging net/ipv6/ipcomp6.c.
Auto-merging net/ipv6/netfilter/ip6_queue.c.
Auto-merging net/ipv6/raw.c.
Auto-merging net/ipv6/tcp_ipv6.c.
Auto-merging net/sched/sch_generic.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in net/sched/sch_generic.c.
Auto-merging net/sunrpc/xdr.c.
merge: warning: conflicts during merge
ERROR: Merge conflict in net/sunrpc/xdr.c.
Removing sound/pcmcia/vx/vx_entry.c
Removing sound/pcmcia/vx/vxp440.c
Auto-merging sound/ppc/pmac.c.
fatal: merge program failed
Automatic merge failed, fix up by hand

Re: Automatic merge failed, fix up by hand

[Junio C Hamano]

Len Brown <len.brown@intel.com> writes:

> The merge issue below is reproduced in a "git clone -l" copy
> with no plain files present.

Meaning you did not have any file in the working tree?  It seems
to me that what is happenning is the resolve is trying to merge
the head of your tree and from-linus, but at the same time it
notices that you removed those files from your working tree and
thinks that is what you would want to do.

I could get to 81065e2f415af6... commit (Linus tip at this
moment), so if you can tell me where to snarf the other commit
(702c7e76....) that would help me diagnose the problem a lot.

Thanks.

Re: Automatic merge failed, fix up by hand

[Len Brown]

On Tue, 2005-08-23 at 18:06 -0400, Junio C Hamano wrote:
> Len Brown <len.brown@intel.com> writes:
> 
> > The merge issue below is reproduced in a "git clone -l" copy
> > with no plain files present.
> 
> Meaning you did not have any file in the working tree?  It seems
> to me that what is happenning is the resolve is trying to merge
> the head of your tree and from-linus, but at the same time it
> notices that you removed those files from your working tree and
> thinks that is what you would want to do.

Doesn't matter if the merge is after a git checkout -f
or not.  I was just pointing out that it also fails
if there are no plain files checked out.

> I could get to 81065e2f415af6... commit (Linus tip at this
> moment), so if you can tell me where to snarf the other commit
> (702c7e76....) that would help me diagnose the problem a lot.

rsync://rsync.kernel.org/pub/scm/linux/kernel/git/lenb/to-akpm.git

fails when merged into latest linus, or when latest linus
is merged into it.

I suspect some artifact of my patches being based on
one of several branches rooted at 2.6.12 is the issue,
and that in switching between latest 2.6.13 and stable
2.6.12 branches, some state has bled through that
now confuses the heck out of resolve.

thanks,
-Len

Re: Automatic merge failed, fix up by hand

[Junio C Hamano]

Len Brown <len.brown@intel.com> writes:

>> I could get to 81065e2f415af6... commit (Linus tip at this
>> moment), so if you can tell me where to snarf the other commit
>> (702c7e76....) that would help me diagnose the problem a lot.
>
> rsync://rsync.kernel.org/pub/scm/linux/kernel/git/lenb/to-akpm.git

Thanks.

I think merge-base, even though we attempted to fix it recently,
is still confused and that is one of the reasons why you are
getting this.

    prompt$  git-rev-parse origin test-lenb-merge
    81065e2f415af6c028eac13f481fb9e60a0b487b
    702c7e7626deeabb057b6f529167b65ec2eefbdb
    prompt$  git-merge-base origin test-lenb-merge
    30e332f3307e9f7718490a706e5ce99f0d3a7b26
    prompt$  git show-branch origin test-lenb-merge
    ! [origin] zd1201 kmalloc size fix
     * [test-lenb-merge] [ACPI] fix ia64 build issues resulting from L...
    --
    +  [origin] zd1201 kmalloc size fix
    +  [origin~1] md: make sure resync gets started when array starts.
    +  [origin~2] preempt race in getppid
    +  [origin~3] Merge master.kernel.org:/pub/scm/linux/kernel/git/da
    -- >8 -- snip -- >8 --
    +  Merge ../to-linus-stable/
    ++ [ACPI] re-enable platform-specific hotkey drivers by default
    +  ARM: 2851/1: Fix NWFPE extended precision exception handling
    ++ [origin~34] intelfb/fbdev: Save info->flags in a local variable
    prompt$  git-rev-parse origin~34
    3edea4833a1efcd43e1dff082bc8001fdfe74b34

Notice that show-branch, which walks the commit ancestry chain
pretty much the same way merge-base does, notices and stops at
origin~34 (that's 34th generation first parent commit from Linus
tip) that is the common commit between the two heads being
merged?  And that commit, 3edea48... is different from what
merge-base is reporting.

If I maually run merge-cache using origin~34 as the merge base,
only the following two files needs to result in non-simple merge:

    Documentation/acpi-hotkey.txt
    drivers/acpi/osl.c

Do these two files match your expectation?

I'll take a look at merge-base.c next, but just in case I CC:ed
this to Linus, who is more familiar with that code.

Re: Automatic merge failed, fix up by hand

[Junio C Hamano]

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

> I think merge-base, even though we attempted to fix it recently,
> is still confused and that is one of the reasons why you are
> getting this.
>
>     prompt$  git-rev-parse origin test-lenb-merge
>     81065e2f415af6c028eac13f481fb9e60a0b487b
>     702c7e7626deeabb057b6f529167b65ec2eefbdb
 -->8-- snip -->8--
>     +  Merge ../to-linus-stable/
>     ++ [ACPI] re-enable platform-specific hotkey drivers by default
>     +  ARM: 2851/1: Fix NWFPE extended precision exception handling
>     ++ [origin~34] intelfb/fbdev: Save info->flags in a local variable
>     prompt$  git-rev-parse origin~34
>     3edea4833a1efcd43e1dff082bc8001fdfe74b34

I spoke too fast.  merge-base is not giving you an incorrect
answer.  It just happens that the answer was way suboptimal.

The "[ACPI] re-enable platform-specific hotkey" is what it
chose, and my monkey guessing origin~34 happened to be better
merge base, but the logic used by merge-base is to pick the
latest (from wallclock wise) commit among several candidates,
and by that criteria it did the "right" thing.

In this case, the "right" thing was a wrong decision.  So we
probably should revisit how we choose the "best" merge base
among candidates.  I think "origin~34" which happened to be the
last one output by "git show-branch" was just an accident, not a
good rule to follow, so changing merge-base to use the one that
the other command shows the last would not be a good way to fix
this.

Probably the ideal way would be to give merge-base an option to
spit out all the candidates, and have the script try to see
which ones yield the least number of non-trivial merges.

Linus?

Re: Automatic merge failed, fix up by hand

[Len Brown]

On Tue, 2005-08-23 at 19:58 -0400, Junio C Hamano wrote:
> Len Brown <len.brown@intel.com> writes:
> 
> >> I could get to 81065e2f415af6... commit (Linus tip at this
> >> moment), so if you can tell me where to snarf the other commit
> >> (702c7e76....) that would help me diagnose the problem a lot.
> >
> > rsync://rsync.kernel.org/pub/scm/linux/kernel/git/lenb/to-akpm.git
> 
> Thanks.
> 
> I think merge-base, even though we attempted to fix it recently,
> is still confused and that is one of the reasons why you are
> getting this.
> 
>     prompt$  git-rev-parse origin test-lenb-merge
>     81065e2f415af6c028eac13f481fb9e60a0b487b
>     702c7e7626deeabb057b6f529167b65ec2eefbdb
>     prompt$  git-merge-base origin test-lenb-merge
>     30e332f3307e9f7718490a706e5ce99f0d3a7b26
>     prompt$  git show-branch origin test-lenb-merge
>     ! [origin] zd1201 kmalloc size fix
>      * [test-lenb-merge] [ACPI] fix ia64 build issues resulting from
> L...
>     --
>     +  [origin] zd1201 kmalloc size fix
>     +  [origin~1] md: make sure resync gets started when array starts.
>     +  [origin~2] preempt race in getppid
>     +  [origin~3] Merge master.kernel.org:/pub/scm/linux/kernel/git/da
>     -- >8 -- snip -- >8 --
>     +  Merge ../to-linus-stable/
>     ++ [ACPI] re-enable platform-specific hotkey drivers by default
>     +  ARM: 2851/1: Fix NWFPE extended precision exception handling
>     ++ [origin~34] intelfb/fbdev: Save info->flags in a local variable
>     prompt$  git-rev-parse origin~34
>     3edea4833a1efcd43e1dff082bc8001fdfe74b34
> 
> Notice that show-branch, which walks the commit ancestry chain
> pretty much the same way merge-base does, notices and stops at
> origin~34 (that's 34th generation first parent commit from Linus
> tip) that is the common commit between the two heads being
> merged?  And that commit, 3edea48... is different from what
> merge-base is reporting.
> 
> If I maually run merge-cache using origin~34 as the merge base,
> only the following two files needs to result in non-simple merge:
> 
>     Documentation/acpi-hotkey.txt
>     drivers/acpi/osl.c
> 
> Do these two files match your expectation?

No, I don't think so.

Unless I missed something, to-akpm should be a proper super-set
of from-linus, so I wouldn't expect a merge on these two.

> I'll take a look at merge-base.c next, but just in case I CC:ed
> this to Linus, who is more familiar with that code.

thanks,
-Len

Re: Automatic merge failed, fix up by hand

[Linus Torvalds]

On Tue, 23 Aug 2005, Len Brown wrote:
>
> I'm having trouble using git for merging kernel trees.
> 
> git seems to manufacture conflicts in files that
> I never touched, and on some files it completely
> throws up its arms, see "Not handling case" below.

Cool.

You've found a case where git-merge-base finds what appears to be two 
equally good merge candidates, but they really aren't.

The merge candidates are 30e332f3307e9f7718490a706e5ce99f0d3a7b26 and 
3edea4833a1efcd43e1dff082bc8001fdfe74b34.

To see this graphically, do:

	echo 30e332f3307e9f7718490a706e5ce99f0d3a7b26 > .git/refs/tags/selected-merge-base
	echo 3edea4833a1efcd43e1dff082bc8001fdfe74b34 > .git/refs/tags/other-merge-base

	echo 81065e2f415af6c028eac13f481fb9e60a0b487b > .git/refs/tags/linus-head
	echo 702c7e7626deeabb057b6f529167b65ec2eefbdb > .git/refs/tags/lenb-head

	gitk --all

and notice how the not-selected one is:

	Author: Antonino A. Daplas <adaplas@gmail.com>  2005-08-15 06:29:11
	Committer: Linus Torvalds <torvalds@g5.osdl.org>  2005-08-15 09:59:39
	Tags: not-selected

while the selected on is:

	Author: Luming Yu <luming.yu@intel.com>  2005-08-11 21:31:00
	Committer: Len Brown <len.brown@intel.com>  2005-08-15 12:46:58
	Tags: selected

and the reason we chose that one is that it's three hours later than the 
other one, and we don't know any better.

> Not clear how I got into this state -- probably
> something to do with adding commits on branches
> and them git-pull-branch'ing them into the master;
> combined with updating the master from-linus.

No, it's git.

Well, it's git, together with your propensity to merge old work, which 
causes this kind of confusion where there are two "equally good" points to 
choose from as the merge base, and git chose the wrong one because it 
_looked_ newer and there was a recent merge to an old version of my tree. 

Cross-merges cause this, but I'm sure there's a good algorithm for 
selecting _which_ of the two interesting commits to pick.

Give me a moment to think about this.

		Linus

Re: Automatic merge failed, fix up by hand

[Junio C Hamano]

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

> Probably the ideal way would be to give merge-base an option to
> spit out all the candidates, and have the script try to see
> which ones yield the least number of non-trivial merges.

I first checked out your 702c7e.. commit, and slurped Linus tip
(back then, 81065e2f415af6c028eac13f481fb9e60a0b487b).  Then I
ran git resolve with the attached patch (against the tip of
git.git "master" branch).  Here is what happened, which seems to
work a little bit better, at least to me.

    prompt$ git checkout -f
    prompt$ git status
    nothing to commit
    prompt$ ls -l .git/HEAD
    lrwxrwxrwx  1 junio src 26 Aug 23 15:43 .git/HEAD -> refs/heads/lenb
    prompt$ git resolve HEAD origin 'Merge Linus into Lenb'
    Trying to find the optimum merge base
    Trying to merge 81065e2f415af6c028eac13f481fb9e60a0b487b into 702c7e7626deeabb057b6f529167b65ec2eefbdb using 3edea4833a1efcd43e1dff082bc8001fdfe74b34
    Simple merge failed, trying Automatic merge
    Auto-merging Documentation/acpi-hotkey.txt.
    merge: warning: conflicts during merge
    ERROR: Merge conflict in Documentation/acpi-hotkey.txt.
    Auto-merging drivers/acpi/osl.c.
    fatal: merge program failed
    Automatic merge failed, fix up by hand

Only lightly tested, in the sense that I did only this one case
and nothing else.  For a large repository and with complex
merges, "merge-base -a" _might_ end up reporting many
candidates, in which case the pre-merge step to figure out the
best merge base may turn out to be disastrously slow.  I dunno.


---
git diff HEAD
diff --git a/git-resolve-script b/git-resolve-script
--- a/git-resolve-script
+++ b/git-resolve-script
@@ -49,7 +49,42 @@ if [ "$common" == "$head" ]; then
 	dropheads
 	exit 0
 fi
-echo "Trying to merge $merge into $head"
+
+# Find optimum merge base if there are more than one candidate.
+LF='
+'
+common=$(git-merge-base -a $head $merge)
+case "$common" in
+?*"$LF"?*)
+	echo "Trying to find the optimum merge base"
+	G=.tmp-index$$
+	best=
+	best_cnt=-1
+	for c in $common
+	do
+		rm -f $G
+		GIT_INDEX_FILE=$G git-read-tree -m $c $head $merge \
+			2>/dev/null || continue
+		if GIT_INDEX_FILE=$G git-write-tree 2>/dev/null
+		then
+			# This one results in just a Simple merge;
+			# It cannot become better than this.
+			best=$c
+			break
+		fi
+		# Otherwise, count the paths that are unmerged.
+		cnt=`GIT_INDEX_FILE=$G git-ls-files --unmerged | wc -l`
+		if test $best_cnt -le 0 -o $cnt -le $best_cnt
+		then
+			best=$c
+			best_cnt=$cnt
+		fi
+	done
+	rm -f $G
+	common="$best"
+esac
+
+echo "Trying to merge $merge into $head using $common"
 git-read-tree -u -m $common $head $merge || exit 1
 result_tree=$(git-write-tree  2> /dev/null)
 if [ $? -ne 0 ]; then
diff --git a/merge-base.c b/merge-base.c
--- a/merge-base.c
+++ b/merge-base.c
@@ -82,13 +82,17 @@ static struct commit *interesting(struct
  * commit B.
  */
 
-static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
+static int show_all = 0;
+
+static int merge_base(struct commit *rev1, struct commit *rev2)
 {
 	struct commit_list *list = NULL;
 	struct commit_list *result = NULL;
 
-	if (rev1 == rev2)
-		return rev1;
+	if (rev1 == rev2) {
+		printf("%s\n", sha1_to_hex(rev1->object.sha1));
+		return 0;
+	}
 
 	parse_commit(rev1);
 	parse_commit(rev2);
@@ -108,7 +112,7 @@ static struct commit *common_ancestor(st
 		if (flags == 3) {
 			insert_by_date(commit, &result);
 
-			/* Mark children of a found merge uninteresting */
+			/* Mark parents of a found merge uninteresting */
 			flags |= UNINTERESTING;
 		}
 		parents = commit->parents;
@@ -122,26 +126,46 @@ static struct commit *common_ancestor(st
 			insert_by_date(p, &list);
 		}
 	}
-	return interesting(result);
+
+	if (!result)
+		return 1;
+
+	while (result) {
+		struct commit *commit = result->item;
+		result = result->next;
+		if (commit->object.flags & UNINTERESTING)
+			continue;
+		printf("%s\n", sha1_to_hex(commit->object.sha1));
+		if (!show_all)
+			return 0;
+		commit->object.flags |= UNINTERESTING;
+	}
+	return 0;
 }
 
+static const char merge_base_usage[] =
+"git-merge-base [--all] <commit-id> <commit-id>";
+
 int main(int argc, char **argv)
 {
-	struct commit *rev1, *rev2, *ret;
+	struct commit *rev1, *rev2;
 	unsigned char rev1key[20], rev2key[20];
 
+	while (1 < argc && argv[1][0] == '-') {
+		char *arg = argv[1];
+		if (!strcmp(arg, "-a") || !strcmp(arg, "--all"))
+			show_all = 1;
+		else
+			usage(merge_base_usage);
+		argc--; argv++;
+	}
 	if (argc != 3 ||
 	    get_sha1(argv[1], rev1key) ||
-	    get_sha1(argv[2], rev2key)) {
-		usage("git-merge-base <commit-id> <commit-id>");
-	}
+	    get_sha1(argv[2], rev2key))
+		usage(merge_base_usage);
 	rev1 = lookup_commit_reference(rev1key);
 	rev2 = lookup_commit_reference(rev2key);
 	if (!rev1 || !rev2)
 		return 1;
-	ret = common_ancestor(rev1, rev2);
-	if (!ret)
-		return 1;
-	printf("%s\n", sha1_to_hex(ret->object.sha1));
-	return 0;
+	return merge_base(rev1, rev2);
 }

Re: Automatic merge failed, fix up by hand

[Linus Torvalds]

On Tue, 23 Aug 2005, Junio C Hamano wrote:
> 
> Only lightly tested, in the sense that I did only this one case
> and nothing else.  For a large repository and with complex
> merges, "merge-base -a" _might_ end up reporting many
> candidates, in which case the pre-merge step to figure out the
> best merge base may turn out to be disastrously slow.  I dunno.

Ok, I think your approach is the correct one. Just list all the commits, 
and let the merge logic figure out which one is the best one.

Here, in case anybody cares, is an alternate approach, which sucks. It 
_happens_ to pick the right parent in this case, but when I look at why it 
picks it, it's pretty much just pure luck again. The distance function is 
not good.

Just returning several entries is the correct thing to do, because then
you can make the distance function be based on the tree diffs, like you
do. That's _much_ better than trying to make the distance be based on some
topology.

So I append this patch just as a historical curiosity. Junio's patch is 
clearly superior.

		Linus

---
diff --git a/merge-base.c b/merge-base.c
--- a/merge-base.c
+++ b/merge-base.c
@@ -82,10 +82,84 @@ static struct commit *interesting(struct
  * commit B.
  */
 
+/*
+ * Count the distance from one commit to the base, using a very
+ * stupid recursive algorithm. We only avoid recursion when seeing
+ * a single parent.
+ */
+static unsigned long count_distance(struct commit *head, struct commit *base)
+{
+	struct commit_list *parents;
+	unsigned long distance = ULONG_MAX;
+	unsigned long chain = 1;
+
+	/* Walk the chain of direct parents */
+	for (;;) {
+		parents = head->parents;
+		if (!parents)
+			goto no_parent;
+		/* Multiple parents? */
+		if (parents->next)
+			break;
+		head = parents->item;
+		if (head == base)
+			return chain;
+		chain++;
+	}
+
+	while (parents) {
+		struct commit *c = parents->item;
+		unsigned long d;
+
+		parents = parents->next;
+		if (c == base)
+			return chain;
+		if (c->object.flags & UNINTERESTING)
+			continue;
+		d = count_distance(c, base);
+		if (d < distance)
+			distance = d;
+	}
+	if (distance != ULONG_MAX)
+		return distance + chain;
+no_parent:
+	return ULONG_MAX;
+}
+
+/*
+ * There are some really nasty cases where we get multiple apparently
+ * equally valid parents, and we need to disambiguate them.
+ *
+ * We aim for the one whose total distance to the two revisions is the
+ * smallest, where distance is "x**2 + y**2" (we _much_ prefer a nice
+ * balanced equidistant one over one that is near to one but far from
+ * the other)
+ */
+static struct commit *pick_best_commit(struct commit_list *list, struct commit *rev1, struct commit *rev2)
+{
+	unsigned long distance = ULONG_MAX;
+	struct commit *best = NULL;
+
+	do {
+		struct commit *base = list->item;
+		unsigned long d1 = count_distance(rev1, base);
+		unsigned long d2 = count_distance(rev2, base);
+		unsigned long d = d1*d1 + d2*d2;
+
+fprintf(stderr, "distance analysis: %s: %lu %lu %lu\n", sha1_to_hex(base->object.sha1), d1, d2, d);
+		if (d < distance) {
+			distance = d;
+			best = base;
+		}
+	} while ((list = list->next) != NULL);
+	return best;
+}
+
 static struct commit *common_ancestor(struct commit *rev1, struct commit *rev2)
 {
 	struct commit_list *list = NULL;
 	struct commit_list *result = NULL;
+	struct commit_list *final = NULL;
 
 	if (rev1 == rev2)
 		return rev1;
@@ -122,7 +196,32 @@ static struct commit *common_ancestor(st
 			insert_by_date(p, &list);
 		}
 	}
-	return interesting(result);
+
+	/*
+	 * Go through the result list, and pick out unique
+	 * members to put on the final list.
+	 */
+	while (result) {
+		struct commit_list *entry = result;
+		struct commit *c = result->item;
+		result = result->next;
+		if (c->object.flags & UNINTERESTING)
+			continue;
+		if (c == rev1 || c == rev2)
+			return c;
+		entry->next = final;
+		final = entry;
+		c->object.flags |= UNINTERESTING;
+	}
+
+	if (!final)
+		return NULL;
+
+	/* Just one entry? */
+	if (!final->next)
+		return final->item;
+
+	return pick_best_commit(final, rev1, rev2);
 }
 
 int main(int argc, char **argv)

Re: Automatic merge failed, fix up by hand

[Len Brown]

On Tue, 2005-08-23 at 21:07 -0400, Junio C Hamano wrote:
> Junio C Hamano <junkio@cox.net> writes:
> 
> > Probably the ideal way would be to give merge-base an option to
> > spit out all the candidates, and have the script try to see
> > which ones yield the least number of non-trivial merges.
> 
> I first checked out your 702c7e.. commit, and slurped Linus tip
> (back then, 81065e2f415af6c028eac13f481fb9e60a0b487b).  Then I
> ran git resolve with the attached patch (against the tip of
> git.git "master" branch).  Here is what happened, which seems to
> work a little bit better, at least to me.
> 
>     prompt$ git checkout -f
>     prompt$ git status
>     nothing to commit
>     prompt$ ls -l .git/HEAD
>     lrwxrwxrwx  1 junio src 26 Aug 23 15:43 .git/HEAD ->
> refs/heads/lenb
>     prompt$ git resolve HEAD origin 'Merge Linus into Lenb'
>     Trying to find the optimum merge base
>     Trying to merge 81065e2f415af6c028eac13f481fb9e60a0b487b into
> 702c7e7626deeabb057b6f529167b65ec2eefbdb using
> 3edea4833a1efcd43e1dff082bc8001fdfe74b34

Looking at gitk, it certainly chose the right ancestor in this case.

>     Simple merge failed, trying Automatic merge
>     Auto-merging Documentation/acpi-hotkey.txt.
>     merge: warning: conflicts during merge
>     ERROR: Merge conflict in Documentation/acpi-hotkey.txt.
>     Auto-merging drivers/acpi/osl.c.
>     fatal: merge program failed
>     Automatic merge failed, fix up by hand
> 
> Only lightly tested, in the sense that I did only this one case
> and nothing else.  For a large repository and with complex
> merges, "merge-base -a" _might_ end up reporting many
> candidates, in which case the pre-merge step to figure out the
> best merge base may turn out to be disastrously slow.  I dunno.

It ran a heck of a lot faster than the alternative -- which
would have been to export 85 patches and re-commit them
to a new tree.

Perhaps Tony's recent merge mystery had the same cause and he can also
benefit from this patch?

thanks!

-Len

Re: Automatic merge failed, fix up by hand

[Daniel Barkalow]

On Tue, 23 Aug 2005, Junio C Hamano wrote:

> Only lightly tested, in the sense that I did only this one case
> and nothing else.  For a large repository and with complex
> merges, "merge-base -a" _might_ end up reporting many
> candidates, in which case the pre-merge step to figure out the
> best merge base may turn out to be disastrously slow.  I dunno.

I think it's the right thing to do for now (and what I was going to
suggest), and if people find it too slow, we can consider teaching
read-tree to take multiple common ancestors and use any of them that gives
clear result on a per-file basis.

On the other hand, Tony might have hit a bad case with an ill-chosen
common ancestor for a patch/revert sequence, and we probably want to look
into that if we've got some history that demonstrates the problem. I think
that, if there are two common ancestors, one of which has applied a patch
and one of which hasn't, and on one side of the merge it gets reverted, we
should get the revert, but we'll only get it if we choose the ancestor
where it was applied.

(Letters are versions of the file, which 'b' being the bad patch; the
 second column is the two choices for common ancestor)

  a-b-a-?
 / X   /
a-b-b-b

Of course, you could have the two lines exactly flipped for a different
file in the same commits, or for a different hunk in the same file, and
there would be no single choice that doesn't lose the revert. The really
right thing to do is identify that there is a b->a transition that is not
a trivial merge and that is not beyond a common ancestor, but that's hard
to determine easily and with sufficient granularity to catch everything.

I still someday want to do a version of diff/merge for git that could
select common ancestors on a per-hunk basis and identify block moves and
avoid giving confusing (but marginally shorter) diffs, but that's a major
undertaking that I don't have time for right now.

	-Daniel
*This .sig left intentionally blank*

Re: Automatic merge failed, fix up by hand

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> Ok, I think your approach is the correct one. Just list all the commits, 
> and let the merge logic figure out which one is the best one.
>
> Just returning several entries is the correct thing to do, because then
> you can make the distance function be based on the tree diffs, like you
> do. That's _much_ better than trying to make the distance be based on some
> topology.
>
> So I append this patch just as a historical curiosity. Junio's patch is 
> clearly superior.
>
> 		Linus

Of course it is clearly superior, because it is not _my_ patch
but *yours*.

I just did what you earlier told the world how things should
work, based on this message:

    Date:	Mon, 11 Apr 2005 16:48:25 -0700 (PDT)
    From:	Linus Torvalds <torvalds@osdl.org>
    Subject: Re: git: patch for parent-id and idea for merge
    Message-ID: <Pine.LNX.4.58.0504111631360.1267@ppc970.osdl.org>

    Btw, I've changed the semantics of "rev-tree" once again.
    ...
    In other words, it will give you a way to figure out which changeset to
    use as the common one. It's always going to be a parent of one of these
    edge-commits that has all of its reachability bits set. Which one.. Now
    that's the question. Maybe just the most recent one, or maybe actually use
    "diff-tree" to see which one generates the fewest conflicts.