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

From: Linus Torvalds <torvalds@osdl.org>
Date: May 16, 2006, 15:32 UTC
Message-ID: <Pine.LNX.4.64.0605160821570.3866@g5.osdl.org>
In-Reply-To: <20060516065452.GA5540@c165.ib.student.liu.se>

On Tue, 16 May 2006, Fredrik Kuivinen wrote:

Show 8 quoted lines

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

Yes, git-merge-base should always return a least common ancestor, never anything less. The only question is what happens when there are multiple LCA commits.

In fact, even in that case git-merge-base will have a pretty strong specification:

  "git-merge-base with the '--all' flag will return the complete set of
   least common ancestors, sorted by most recent (as defined purely by
   the commit date order, not any graph ordering) first.

   Without the '--all' flag, it will return just one LCA commit (the most 
   recent one, by the same date-based definition).

   In the case two or more LCA commits have exactly the same committer 
   date, the ordering between them is arbitrary"

I don't think you can be more specific, or do a better job. The definition of "most recent" is arbitrary, of course - and going by commit date is just _one_ way to order them, but it happens to be an easy one, and one that is as good as any other choice.

Of course, the defined ordering probably really matters only for the case where we return just one LCA out of many, but it's nice to be able to tell what the order will be even for the multi-commit case.

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

Correct. We used to occasionally get it wrong, and return a common ancestor that wasn't least.

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

Modulo bugs, no. And I don't think there are any bugs in that respect.

		Linus