threads / discuss / 1629

Automatic merge failed, fix up by hand

Subject: Automatic merge failed, fix up by hand

## tl;dr

12 messages between Aug 23, 2005 and Aug 24, 2005.

replies: 11people: 4as markdown or json

Len Brown· Aug 23, 2005, 21:12 UTC · lore
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
Junio C Hamano· Aug 23, 2005, 22:06 UTC · re: Len Brown · lore

Re: Automatic merge failed, fix up by hand

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.
Len Brown· Aug 23, 2005, 22:31 UTC · re: Junio C Hamano · lore

Re: Automatic merge failed, fix up by hand

On Tue, 2005-08-23 at 18:06 -0400, Junio C Hamano wrote:
Show 10 quoted lines
> 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

Junio C Hamano· Aug 23, 2005, 23:58 UTC · re: Len Brown · lore

Re: Automatic merge failed, fix up by hand

Len Brown <len.brown@intel.com> writes:
Show 5 quoted lines
>> 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.

Junio C Hamano· Aug 24, 2005, 00:29 UTC · re: Junio C Hamano · lore

Re: Automatic merge failed, fix up by hand

Junio C Hamano <junkio@cox.net> writes:
Show 7 quoted lines
> 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--
Show 6 quoted lines
>     +  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?
Junio C Hamano· Aug 24, 2005, 01:07 UTC · re: Junio C Hamano · lore

Re: Automatic merge failed, fix up by hand

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);
 }
Linus Torvalds· Aug 24, 2005, 01:28 UTC · re: Junio C Hamano · lore

Re: Automatic merge failed, fix up by hand

On Tue, 23 Aug 2005, Junio C Hamano wrote:
Show 6 quoted lines
> 
> 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)
Junio C Hamano· Aug 24, 2005, 03:52 UTC · re: Linus Torvalds · lore

Re: Automatic merge failed, fix up by hand

Linus Torvalds <torvalds@osdl.org> writes:
Show 12 quoted lines
> 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.
Len Brown· Aug 24, 2005, 02:25 UTC · re: Junio C Hamano · lore

Re: Automatic merge failed, fix up by hand

On Tue, 2005-08-23 at 21:07 -0400, Junio C Hamano wrote:
Show 23 quoted lines
> 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.
Show 13 quoted lines
>     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
Daniel Barkalow· Aug 24, 2005, 03:11 UTC · re: Junio C Hamano · lore

Re: Automatic merge failed, fix up by hand

On Tue, 23 Aug 2005, Junio C Hamano wrote:
Show 5 quoted lines
> 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*
Len Brown· Aug 24, 2005, 00:31 UTC · re: Junio C Hamano · lore

Re: Automatic merge failed, fix up by hand

On Tue, 2005-08-23 at 19:58 -0400, Junio C Hamano wrote:
Show 50 quoted lines
> 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

Linus Torvalds· Aug 24, 2005, 00:48 UTC · re: Len Brown · lore

Re: Automatic merge failed, fix up by hand

On Tue, 23 Aug 2005, Len Brown wrote:
Show 6 quoted lines
>
> 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

← back to recent threads