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

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 14, 2016, 16:23 UTC
Message-ID: <xmqq37qoi2h6.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <20160414142333.GA31621@yexl-desktop>

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

Show 20 quoted lines

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