From: Junio C Hamano Date: Tue, 16 May 2006 07:51:31 GMT Subject: Re: [PATCH] Update the documentation for git-merge-base Message-ID: <7vu07qcsqk.fsf@assigned-by-dhcp.cox.net> In-Reply-To: <20060516065452.GA5540@c165.ib.student.liu.se> Fredrik Kuivinen writes: >> 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.