Linus Torvalds <torvalds <at> osdl.org> writes:

> That "extra" check only helps once. If we ever hit the "extra--", it's 
> gone.

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 <at> comm.iter.xz
export GIT_COMMITTER_NAME='C O Mmiter'
export GIT_AUTHOR_NAME='A U Thor'
export GIT_AUTHOR_EMAIL=git <at> 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