Re: [PATCH] Update the documentation for git-merge-base

From: Junio C Hamano <junkio@cox.net>
Date: May 16, 2006, 07:51 UTC
Message-ID: <7vu07qcsqk.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <20060516065452.GA5540@c165.ib.student.liu.se>

Fredrik Kuivinen <freku045@student.liu.se> writes:

Show 10 quoted lines

>> See the big illustration at the top of the source for how you
>> can construct pathological case to defeat an attempt to
>> guarantee such.  --all guarantees that the output contains all
>> interesting ones, but does not guarantee the output has no
>> suboptimal merge bases.
>
> There are two examples at the top of the source. In the first one a
> least common ancestor is returned. As I interpret the second one, it
> is an example of how the old algorithm without the postprocessing step
> produced a common ancestor which is not least.

Ah, yes, I remember now.

The drawing was done while we were working on the solution to that pathological case; mark_reachable_commits() solves that horizon effect.

    http://article.gmane.org/gmane.comp.version-control.git/11410
    http://article.gmane.org/gmane.comp.version-control.git/11429
    http://article.gmane.org/gmane.comp.version-control.git/11552
    http://article.gmane.org/gmane.comp.version-control.git/11613

However, our inability to come up with one is not a nonexistence proof of cases the current algorithm can fail, so math minded people _might_ want to prove the algorithm is optimal.

Not me, though.