Re: Comments on recursive merge..

Linus Torvalds <torvalds@osdl.org> writes:

I think you are right here, but while digging into this I found an interesting case.

The current show-branch code does the same as merge-base in the pathological example depicted in merge-base.c, but they seem to do different things to this picture (commit grows from bottom to top, time flows alphabetically; find base between G and H).

                 H
                / \
           G   A   \
           |\ /     \ 
           | B       \
           |  \       \
            \  C       F
             \  \     / 
              \  D   /   
               \ |  /
                \| /
		 E

"git-merge-base --all" says the merge bases are B and E, while "show-branch --merge-base" mentions only B. In this case the latter is probably the better answer. Actually git-merge-base without --all only mentions E. This is because we give up when we find the list elements are all uninteresting. And this is very expensive to fix (I recall mentioning "horizon effect" last time we worked on this --- around August 12th).

G gets bit 1 and H gets bit 2. Here is what happens in each iteration:

	List			A B C D E F G H		Result
	G1 H2			- - - - - - 1 2
	H2 E1 B1		- 1 - - 1 - 1 2
	F2 E1 B1 A2		2 1 - - 1 2 1 2
	E3 B1 A2		2 1 - - 3 2 1 2		E3
	B1 A2			2 1 - - 3 2 1 2		E3
	C1 A2			2 1 1 - 3 2 1 2		E3
	D1 A2			2 1 1 1 3 2 1 2		E3
	A2			2 1 1 1 3 2 1 2		E3
	B3			2 3 1 1 3 2 1 2		E3 B3
	C7			2 3 7 1 3 2 1 2		E3 B3

We popped B with flag 3, and started contaminating the well by reinjecting its parent C with flag 7. That is all good, but "while (interesting(list))" check stops us from going further. Ideally the following two steps would have found out that E is also uninteresting.

	D7			2 3 7 7 3 2 1 2
	E7			2 3 7 7 7 2 1 2

But that is expensive -- we would not know when to stop.

A reproduction recipe is attached here, primarily so I do not have to worry about losing it from /var/tmp/.

-- >8 -- cut here -- >8 -- #!/bin/sh

rm -fr .git && git-init-db T=$(git-write-tree)

M=1130000000 Z=+0000

export GIT_COMMITTER_EMAIL=git@comm.iter.xz export GIT_COMMITTER_NAME='C O Mmiter' export GIT_AUTHOR_NAME='A U Thor' export GIT_AUTHOR_EMAIL=git@au.thor.xz

doit() {
	OFFSET=$1; shift
	NAME=$1; shift
	PARENTS=
	for P
	do
		PARENTS="${PARENTS}-p $P "
	done
	GIT_COMMITTER_DATE="$(($M + $OFFSET)) $Z"
	GIT_AUTHOR_DATE=$GIT_COMMITTER_DATE
	export GIT_COMMITTER_DATE GIT_AUTHOR_DATE
	commit=$(echo $NAME | git-commit-tree $T $PARENTS)
	echo $commit >.git/refs/tags/$NAME
	echo $commit
}

checkit() {
    echo MB
    git-merge-base --all "$@" | xargs git-name-rev
    echo SB
    git-show-branch --merge-base "$@" | xargs git-name-rev
    git-show-branch --sha1-name --more=99 "$@"
}

E=$(doit 5 E) D=$(doit 4 D $E) F=$(doit 6 F $E) C=$(doit 3 C $D) B=$(doit 2 B $C) A=$(doit 1 A $B) G=$(doit 7 G $B $E) H=$(doit 8 H $A $F)

checkit $G $H

exit