Subject: Re: [PATCH 1/3] rev-list: allow bisect and first-parent flags

From: Junio C Hamano <[email-masked]>
Date: Tue, 28 Jul 2020 13:23:54 -0700

"Aaron Lipman via GitGitGadget" <[email-masked]> writes:

> From: Aaron Lipman <[email-masked]>
>
> Add first_parent_only parameter to find_bisection(), removing the
> barrier that prevented combining the --bisect and --first-parent flags
> when using git rev-list
>
> Signed-off-by: Aaron Lipman <[email-masked]>
> Based-on-patch-by: Tiago Botelho <[email-masked]>

In chronological order, please.

> diff --git a/bisect.c b/bisect.c
> index d5e830410f..762f68c8e9 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -37,7 +37,7 @@ static const char *term_good;
>   * We care just barely enough to avoid recursing for
>   * non-merge entries.
>   */
> -static int count_distance(struct commit_list *entry)
> +static int count_distance(struct commit_list *entry, int first_parent_only)
>  {
>  	int nr = 0;
>  
> @@ -52,10 +52,10 @@ static int count_distance(struct commit_list *entry)
>  		commit->object.flags |= COUNTED;
>  		p = commit->parents;
>  		entry = p;
> -		if (p) {
> +		if (p && !first_parent_only) {
>  			p = p->next;
>  			while (p) {
> -				nr += count_distance(p);
> +				nr += count_distance(p, first_parent_only);
>  				p = p->next;
>  			}
>  		}

If you are running a first-parent-only bisection, by default, each
commit in the "goodness not yet known" region is treated as a single
parent commit for the purpose of bisection.  As do_find_bisection()
avoids the cost of calling stupid-and-expensive count_distance() by
treating such a single-strand-of-pearls specially, wouldn't it be a
BUG() if this funtion is called under first_parent_only mode in the
first place?

> @@ -88,15 +88,16 @@ static inline void weight_set(struct commit_list *elem, int weight)
>  	**commit_weight_at(&commit_weight, elem->item) = weight;
>  }

> -static int count_interesting_parents(struct commit *commit)
> +static int count_interesting_parents(struct commit *commit, int first_parent_only)
>  {
>  	struct commit_list *p;
>  	int count;
>  
>  	for (count = 0, p = commit->parents; p; p = p->next) {
> -		if (p->item->object.flags & UNINTERESTING)
> -			continue;
> -		count++;
> +		if (!(p->item->object.flags & UNINTERESTING))
> +			count++;
> +		if (first_parent_only)
> +			break;
>  	}
>  	return count;
>  }

Any merge will be checked for interesting-ness of its first parent;
there is either zero or one interesting parent and no other case
under first-parent-only.  OK.

> @@ -259,7 +260,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
>   */
>  static struct commit_list *do_find_bisection(struct commit_list *list,
>  					     int nr, int *weights,
> -					     int find_all)
> +					     int find_all, int first_parent_only)
>  {
>  	int n, counted;
>  	struct commit_list *p;
> @@ -271,7 +272,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  		unsigned flags = commit->object.flags;
>  
>  		*commit_weight_at(&commit_weight, p->item) = &weights[n++];
> -		switch (count_interesting_parents(commit)) {
> +		switch (count_interesting_parents(commit, first_parent_only)) {
>  		case 0:
>  			if (!(flags & TREESAME)) {
>  				weight_set(p, 1);
> @@ -314,7 +315,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  			continue;
>  		if (weight(p) != -2)
>  			continue;

If count-interesting-parents can never be 2 or more, you will never
see weight(p) == -2 (see the switch statement in the previous hunk).

So it your first-parent-only mode allowed this continue not to
trigger, you have a BUG(), I think.

> -		weight_set(p, count_distance(p));
> +		weight_set(p, count_distance(p, first_parent_only));

Hence, you do not need to touch count_distance() at all, no?

> @@ -330,13 +331,21 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  			struct commit_list *q;
>  			unsigned flags = p->item->object.flags;
>  
> +			/* if commit p has already been weighted, continue. */
>  			if (0 <= weight(p))
>  				continue;
> +
> +			/*
> +			 * otherwise, find the first interesting
> +			 * already-weighted parent of p and store as q.
> +			 */

Unnecessary changes above.

>  			for (q = p->item->parents; q; q = q->next) {
> -				if (q->item->object.flags & UNINTERESTING)
> -					continue;
> -				if (0 <= weight(q))
> +				if (!(q->item->object.flags & UNINTERESTING) && 0 <= weight(q)) {
> +					break;

Overlong line.  Fold it after "&&", like this:

				if (!(q->item->object.flags & UNINTERESTING) &&
				    0 <= weight(q)) {

What is this change about?

Ah, if the first parent is uninteresting, we do not want to
continue, but with the original loop, we may go on and check
q->next.  We just want to break out of the loop instead.

I strongly suspect that

			for (q = p->item->parents;
			     q;
			     q = first_parent_only ? NULL : q->next) {

without any change inside the loop is much easier to reason about.
We follow exactly the same logic as the usual case.  We just pretend
that all commits have only one single parent which is the first one.

Thanks.