Re: [PATCH v3 1/2] negotiator/default: avoid stack overflow

From: Derrick Stolee <derrickstolee@github.com>
Date: Apr 26, 2023, 17:30 UTC
Message-ID: <49695ce0-b9f9-0fc7-ed16-093dc7f12b7e@github.com>
In-Reply-To: <xmqqedo6tvkj.fsf@gitster.g>

On 4/26/2023 1:14 PM, Junio C Hamano wrote:

> Han Xin <hanxin.hx@bytedance.com> writes:

Show 23 quoted lines

>> +		if ((commit->object.flags & SEEN) && !(commit->object.flags & POPPED))
>> +			ns->non_common_revs--;
> 
> Hmph, this is a bit unexpected to duplicate the non_common_revs
> counting logic here.  In the original, this piece of code was there
> just after we decided to continue digging into the parents, and even
> if this patch changes the mechanism with which "digging into the
> parents" from recursion to priority queue, it is not obvious why we
> can keep doing the decrementing for the current commit we are
> looking at, instead of doing that for parents of the commit like
> this patch does.  In other words, it is not clear why it needs to be
> changed while going from recursive to iterative.
> 
> Is it because ancestors_only is not usable inside the loop in the
> iterative version?  That is, if ancestors_only is not set, we do
> paint the initial commit as COMMON just as the parents we discover
> in the loop, but when ancestors_only is set, we need to skip painting
> the initial commit as COMMON, so the patch moves that logic?
> 
> It may solve the issue of special casing the initial commit, but it
> feels backwards in that the resulting loop becomes harder to
> understand by making it necessary to process the initial commit
> outside the loop only halfway.

The "ancestors_only" parameter is about treating the initial commit differently than the ancestors. Since we add the initial commit to the priority queue, the only way to know we are dealing with an ancestor and not the initial commit is to do the processing when visiting a parent for the first time.

> It may make it easier to understand if we had another local
> variable, "struct commit *skip_commit", that is NULL by default but
> is set to the initial commit when ancestors_only is set,

This is an interesting idea and could reduce the duplicated logic for nw->common_revs.

Show 6 quoted lines

> and do the
> painting with COMMON and counting of non_common_revs all inside the
> loop for the current commit that is being processed (instead of the
> parents the loop discovered).  I dunno.  It would avoid duplicating
> the logic and implements the "ancestors_only, do not paint or count
> the initial commit" in a more readable and straight-forward way, no?

However, we need to do the painting with COMMON when visiting a parent in order to avoid adding duplicate entries to the priority queue (and potentially growing exponentially).

Since we need to examine and modify a parent before adding it to the queue, it is natural to do other "we are visiting a commit" logic in that same place.

It is unfortunate that the logic for nw->common_revs is duplicated, but I think this is a cleaner approach than other considered approaches.

Thanks, -Stolee