Subject: Re: [PATCH 1/3] commit-reach: use one walk in remove_redundant()

From: Junio C Hamano <[email-masked]>
Date: Thu, 28 Jan 2021 12:51:45 -0800

"Derrick Stolee via GitGitGadget" <[email-masked]> writes:

> +	/* Mark all parents of the input as STALE */
> +	for (i = 0; i < cnt; i++) {
> +		struct commit_list *parents;
> +		timestamp_t generation;
>  
>  		repo_parse_commit(r, array[i]);
> +		parents = array[i]->parents;
> +
> +		while (parents) {
> +			repo_parse_commit(r, parents->item);
> +			if (!(parents->item->object.flags & STALE)) {
> +				parents->item->object.flags |= STALE;
> +				prio_queue_put(&queue, parents->item);
> +			}
> +			parents = parents->next;
> +		}
> +
> +		generation = commit_graph_generation(array[i]);
> +
> +		if (generation < min_generation)
> +			min_generation = generation;
> +	}
> +
> +	/* push the STALE bits up to min generation */
> +	while (queue.nr) {
> +		struct commit_list *parents;
> +		struct commit *c = prio_queue_get(&queue);
> +
> +		repo_parse_commit(r, c);
>  
> +		if (commit_graph_generation(c) < min_generation)
>  			continue;
>  
> +		parents = c->parents;
> +		while (parents) {
> +			if (!(parents->item->object.flags & STALE)) {
> +				parents->item->object.flags |= STALE;
> +				prio_queue_put(&queue, parents->item);
> +			}
> +			parents = parents->next;
> +		}
> +	}

So, the inner loop makes sure we won't revisit STALE parent, but
keep digging parents we haven't seen, and stop when the generation
is old enough.  What happens when there is no generation number
computed yet, I wonder...  We'll keep getting infinity and dig all
the way down to root?

> +	/* rearrange array */
> +	dup = xcalloc(cnt, sizeof(struct commit *));
> +	COPY_ARRAY(dup, array, cnt);
> +	for (i = 0; i < cnt; i++) {
> +		if (dup[i]->object.flags & STALE) {
> +			int insert = cnt - 1 - (i - count_non_stale);
> +			array[insert] = dup[i];
> +		} else {
> +			array[count_non_stale] = dup[i];
> +			count_non_stale++;
> +		}
> +	}
> +	free(dup);

The "fill stale ones from the end, non-stale ones from the
beginning" in the loop looks unnecessarily complex to me.  I wonder
if we can do only the "fill non-stale ones from the beginning" half,
i.e.

	for (i = count_non_stale = 0; i < cnt; i++) {
		if (dup[i] is not stale)
			array[count_non_stale++] = dup[i];
	}

without the "keep the stale one at the end of array[]", and clear
marks using what is in dup[] as starting points before discarding
dup[]?

Or do the callers still look at the entries beyond count_non_stale?

Other than that, nicely done.

> +	/* clear marks */
> +	for (i = 0; i < cnt; i++) {
> +		struct commit_list *parents;
> +		parents = array[i]->parents;
> +
> +		while (parents) {
> +			clear_commit_marks(parents->item, STALE);
> +			parents = parents->next;
>  		}
> -		common = paint_down_to_common(r, array[i], filled,
> -					      work, min_generation);
> -		if (array[i]->object.flags & PARENT2)
> -			redundant[i] = 1;
> -		for (j = 0; j < filled; j++)
> -			if (work[j]->object.flags & PARENT1)
> -				redundant[filled_index[j]] = 1;
> -		clear_commit_marks(array[i], all_flags);
> -		clear_commit_marks_many(filled, work, all_flags);
> -		free_commit_list(common);
>  	}
>  
> -	/* Now collect the result */
> -	COPY_ARRAY(work, array, cnt);
> -	for (i = filled = 0; i < cnt; i++)
> -		if (!redundant[i])
> -			array[filled++] = work[i];
> -	for (j = filled, i = 0; i < cnt; i++)
> -		if (redundant[i])
> -			array[j++] = work[i];
> -	free(work);
> -	free(redundant);
> -	free(filled_index);
> -	return filled;
> +	return count_non_stale;
>  }
>  
>  static struct commit_list *get_merge_bases_many_0(struct repository *r,