Junio C Hamano <gitster@xxxxxxxxx> writes:
> 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.
As a corollary, the "is pu@{0} a fast-forward of pu@{1}?" check does
not need merge base computation at all. The only thing it needs to
do is to prove pu@{1} is reachable from pu@{0}, and that can be done
the same way in which '1' can be proved unreachable from '2' in the
post processing phase as described above, i.e. it needs only the
first phase of running merge_bases_many() without postprocessing.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html