Re: [PATCH v2 8/8] commit-reach: add tips_reachable_from_bases()

From: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Date: Mar 15, 2023, 14:13 UTC
Message-ID: <230315.864jqmxfd9.gmgdl@evledraar.gmail.com>
In-Reply-To: <f3fb6833bd71d559a3076d9617a235614ad9a5f8.1678468864.git.gitgitgadget@gmail.com>

On Fri, Mar 10 2023, Derrick Stolee via GitGitGadget wrote:

> From: Derrick Stolee <derrickstolee@github.com>

> +{
> +	size_t i;

Ditto the decl suggestion in an earlier commit, i.e...

Show 18 quoted lines

> +	struct commit_and_index *commits;
> +	unsigned int min_generation_index = 0;
> +	timestamp_t min_generation;
> +	struct commit_list *stack = NULL;
> +
> +	if (!bases || !tips || !tips_nr)
> +		return;
> +
> +	/*
> +	 * Do a depth-first search starting at 'bases' to search for the
> +	 * tips. Stop at the lowest (un-found) generation number. When
> +	 * finding the lowest commit, increase the minimum generation
> +	 * number to the next lowest (un-found) generation number.
> +	 */
> +
> +	CALLOC_ARRAY(commits, tips_nr);
> +
> +	for (i = 0; i < tips_nr; i++) {

...move this here?

Show 17 quoted lines

> +		commits[i].commit = tips[i];
> +		commits[i].index = i;
> +		commits[i].generation = commit_graph_generation(tips[i]);
> +	}
> +
> +	/* Sort with generation number ascending. */
> +	QSORT(commits, tips_nr, compare_commit_and_index_by_generation);
> +	min_generation = commits[0].generation;
> +
> +	while (bases) {
> +		parse_commit(bases->item);
> +		commit_list_insert(bases->item, &stack);
> +		bases = bases->next;
> +	}
> +
> +	while (stack) {
> +		unsigned int j;

...ditto...

Show 7 quoted lines

> +		int explored_all_parents = 1;
> +		struct commit_list *p;
> +		struct commit *c = stack->item;
> +		timestamp_t c_gen = commit_graph_generation(c);
> +
> +		/* Does it match any of our tips? */
> +		for (j = min_generation_index; j < tips_nr; j++) {

...to here...

Show 47 quoted lines

> +			if (c_gen < commits[j].generation)
> +				break;
> +
> +			if (commits[j].commit == c) {
> +				tips[commits[j].index]->object.flags |= mark;
> +
> +				if (j == min_generation_index) {
> +					unsigned int k = j + 1;
> +					while (k < tips_nr &&
> +					       (tips[commits[k].index]->object.flags & mark))
> +						k++;
> +
> +					/* Terminate early if all found. */
> +					if (k >= tips_nr)
> +						goto done;
> +
> +					min_generation_index = k;
> +					min_generation = commits[k].generation;
> +				}
> +			}
> +		}
> +
> +		for (p = c->parents; p; p = p->next) {
> +			parse_commit(p->item);
> +
> +			/* Have we already explored this parent? */
> +			if (p->item->object.flags & SEEN)
> +				continue;
> +
> +			/* Is it below the current minimum generation? */
> +			if (commit_graph_generation(p->item) < min_generation)
> +				continue;
> +
> +			/* Ok, we will explore from here on. */
> +			p->item->object.flags |= SEEN;
> +			explored_all_parents = 0;
> +			commit_list_insert(p->item, &stack);
> +			break;
> +		}
> +
> +		if (explored_all_parents)
> +			pop_commit(&stack);
> +	}
> +
> +done:
> +	free(commits);
> +	repo_clear_commit_marks(the_repository, SEEN);

I didn't see this in my earlier suggestion for passing "struct repository", but I think we should do the same here, i.e. have this function take a "r" argument.

Show 35 quoted lines

> [...]
> @@ -2390,33 +2390,21 @@ static void reach_filter(struct ref_array *array,
>  			 struct commit_list *check_reachable,
>  			 int include_reached)
>  {
> -	struct rev_info revs;
>  	int i, old_nr;
>  	struct commit **to_clear;
> -	struct commit_list *cr;
>  
>  	if (!check_reachable)
>  		return;
>  
>  	CALLOC_ARRAY(to_clear, array->nr);
> -
> -	repo_init_revisions(the_repository, &revs, NULL);
> -
>  	for (i = 0; i < array->nr; i++) {
>  		struct ref_array_item *item = array->items[i];
> -		add_pending_object(&revs, &item->commit->object, item->refname);
>  		to_clear[i] = item->commit;
>  	}
>  
> -	for (cr = check_reachable; cr; cr = cr->next) {
> -		struct commit *merge_commit = cr->item;
> -		merge_commit->object.flags |= UNINTERESTING;
> -		add_pending_object(&revs, &merge_commit->object, "");
> -	}
> -
> -	revs.limited = 1;
> -	if (prepare_revision_walk(&revs))
> -		die(_("revision walk setup failed"));
> +	tips_reachable_from_bases(check_reachable,
> +				  to_clear, array->nr,
> +				  UNINTERESTING);

I.e. it's not ideal, but we had a the_repository in this function before (should probably have passed it from further up, but whatever), so we could pass that to the new tips_reachable_from_bases() still.

Show 5 quoted lines

> -test_perf 'ahead-behind counts: git rev-list' '
> -	for r in $(cat refs)
> -	do
> -		git rev-list --count "HEAD..$r" || return 1
> -	done

Why does this change require deleting the old perf test? Your commit 7/8 notes this test, but here we're deleting it, let's keep it and instead note if the results changed, or stayed the same?

More generally, your commit message says:

> Add extra tests for this behavior in t6600-test-reach.sh as the
> interesting data shape of that repository can sometimes demonstrate
> corner case bugs.

And here for a supposed optimization commit you're adding new tests, but when I try them with the C code at 7/8 they pass.

So it seems we should add them earlier, and this is a pure-optimization commit, but one that's a bit confused about what goes where? :)