Re: [PATCH v4 2/4] format-patch: add '--base' option to record base tree info

[Junio C Hamano <gitster@pobox.com>]

Ye Xiaolong <xiaolong.ye@intel.com> writes:

>>> +	for (i = 0; i < total; i++) {
>>> +		if (!in_merge_bases(base, list[i]) || base == list[i])
>>> +			die(_("base commit should be the ancestor of revision list"));
>>
>>This check looks overly expensive, but I do not think of a more
>>efficient way to do this, given that "All the commits from our
>>series must reach the specified base" is what you seem to want.
>>
>>My understanding is that if base=P is given and you are doing
>>"format-patch Z..C" in this picture:
>>
>>    Q---P---Z---B---*---C
>>     \             /
>>      .-----------A
>>
>
> How about we compute the merge base of the specified rev list in
> cmdline (it should be Q in above case), then check whether specified
> base (P in this case) could be reachable from it, if it couldn't, we
> just error out.

What commits are you considering "the specified rev list in cmdline"
in the example?  Do you mean "commits in the list[], i.e. those to
be shown as patches?"

That is, you are proposing to find the topologically-youngest common
ancestors of A, B and C, which is Q?

There is no canned way to compute that (merge_bases_many() is not
that function).

You however can do repeated pair-wise merge base computations to
reduce the complexity from your O(n) loop to O(log n), I guess.  Do
a pair-wise merge base between A and B (which is Q), and do a merge
base between C (which is the remaining one) and Q to arrive at Q.