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

Fredrik Kuivinen [off-list ref] writes:

quoted

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.