Junio C Hamano <gits...@pobox.com> writes: > Thomas Rast <tr...@student.ethz.ch> writes: > >> At the very least it should be possible to change in_merge_bases() to >> not do any of the post-filtering; perhaps like the patch below. > > I do not recall the details but the post-filtering was added after > the initial naive version without it that was posted to the list did > not work correctly in corner cases. I wouldn't doubt that N*(N-1) > loop can be optimized to something with log(N), but I offhand find > it hard to believe "to not do any" could be correct without seeing > more detailed analysis.

## Advertising

If "one on one side, many on the other side" in merge_bases_many() confuses any of you in the readers, you can just ignore many-ness. Getting merge bases for "one" against many "two"s using merge_bases_many() is exactly the same as getting merge bases for "one" against a (fictitious) single commit you can make by merging all "two"s. So we can think about the degenerate case of merge base between two commits A and B in the following discussion. A merge-base between A and B is defined to be a commit that is a common ancestor of both A and B, and that is not an ancestor of any other merge-base between A and B. In the simplest case (illustrated below), 1 is a merge base between A and B, but 2 is not (even though it is an ancestor of both A and B, it is an ancestor of 1 which is a merge base). y---A / ---2---o---1---x---B So, the thinking goes, in order to find all merge bases, first we can traverse from A and B, following "parent" link from children, and painting found parents in two colors. Start from A and B. Follow from B to find 'x' and paint it in blue, follow from A to find 'y' and paint it in amber. Follow from 'x' to '1', paint it in blue. Follow from 'y' to '1', paint it in amber but notice that it already is painted in blue. Stop the traversal there and we found a candidate '1' that could be a merge base. We know digging from '1' will not find more merge bases, so we should stop there (I do not recall offhand if the current code does stop there, though) [*1*]. There may be other paths that are not depicted in the above illustration that reach '2' from A and B without passing '1' through. o-------o / \ / y---A / / ---2---z---1---x---B \ / o-------o In such a history, we may stop after finding '1' and '2' in the first pass of "stop when a node is painted in both amber and blue". This way, the first pass will find _all_ merge bases, but it also may find common ancestors that are not merge bases. So we need to notice that '1' and '2' have ancestry relation in order to reject '2' as "common but not merge-base". One way of doing so is not to stop at '1' and keep digging (and eventually we find that '2' is what we could reach from '1' that already is a merge base), but then we will be susceptible to the same kind of clock skew issue as the revision traverser. Instead, merge-base traverser chose to do this by running the same "stop traversing at common" traverser between the candidates (in this case, '1' and '2'). The objective of this second traversal is very different from the first one, though. We do not need _all_ the merge bases between '1' and '2'; we do not even need merge bases. The only thing we need to prove that '1' is a merge base (i.e. not an ancestor of any other merge base candidates the first round of traversal between A and B found) is to do the first round of the traversal for '1' as "one" and all the other ('2' in this case) as "two"s; if the first round of such traversal finishes without painting '1' in both colors, that would mean '1' is not reachable from any other candidates of merge base between A and B, so we have proven that '1' is a merge base. So I suspect that the postprocess phase could be made from N*(N-1) to N (run merge_bases_many() once for each of the common ancestor the first round found). You might also be able to stop the traversal used in the first phase (i.e. get_merge_bases()) a bit earlier, if we are digging through '1' to paint 'z' (and eventually '2') in STALE (amber+blue) color, as digging further only to paint things in STALE color is not necessary with the postprocess. [Footnote] *1* Digging through '2' down may find that other candidate merge bases we reach by traversing other paths that may not be depicted in the above illustration, and there may be such paths to reach '1' from A and B that does not pass '2' through. That is a possible alternative way to reject common ancestor that is not merge-base. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html