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

From: Fredrik Kuivinen <freku045@student.liu.se>
Date: May 16, 2006, 06:54 UTC
Message-ID: <20060516065452.GA5540@c165.ib.student.liu.se>
In-Reply-To: <7vhd3qebuv.fsf@assigned-by-dhcp.cox.net>

On Mon, May 15, 2006 at 11:13:12PM -0700, Junio C Hamano wrote:

Show 8 quoted lines

> Fredrik Kuivinen <freku045@student.liu.se> writes:
> 
> > Is the code guaranteed to return a least common ancestor? If that is
> > the case we should probably mention it in the documentation.
> 
> Unfortunately, no, if you mean by "least common" closest to the
> tips.
>

By "least" I mean the following:

C is a least common ancestor of A and B if:

* C is a common ancestor of A and B, and
* for every other common ancestor D (different from C) of A and B, C
  is not reacheable from D.

Show 5 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.

Am I wrong? Do we have any cases where the current merge-base algorithm gives us common ancestors which are not least?

- Fredrik