Re: [PATCH 1/3] commit-reach: implement get_reachable_subset

[Junio C Hamano <gitster@pobox.com>]

"Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:

> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
> +					 struct commit **to, int nr_to,
> +					 int reachable_flag)

This is OR'ed into object.flags, and I somoehow expected to see it
as 'unsigned int', not a signed one.

> +{
> +	struct commit **item;
> +	struct commit *current;
> +	struct commit_list *found_commits = NULL;
> +	struct commit **to_last = to + nr_to;
> +	struct commit **from_last = from + nr_from;
> +	uint32_t min_generation = GENERATION_NUMBER_INFINITY;
> +	int num_to_find = 0;
> +
> +	struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
> +
> +	for (item = to; item < to_last; item++) {
> +		struct commit *c = *item;
> +		
> +		parse_commit(c);
> +		if (c->generation < min_generation)
> +			min_generation = c->generation;
> +
> +		if (!(c->object.flags & PARENT1)) {
> +			c->object.flags |= PARENT1;
> +			num_to_find++;
> +		}
> +	}
> +
> +	for (item = from; item < from_last; item++) {
> +		struct commit *c = *item;
> +		if (!(c->object.flags & PARENT2)) {
> +			c->object.flags |= PARENT2;
> +			parse_commit(c);
> +
> +			prio_queue_put(&queue, *item);
> +		}
> +	}

OK, we marked "to" with PARENT1 and counted them in num_to_find
without dups.  We also marked "from" with PARENT2 and threw them in
the "queue" without dups.

Mental note: the caller must guarantee that everybody reachable from
"to" and "from" have PARENT1 and PARENT2 clear.  This might deserve
to be in the comment before the function.

> +	while (num_to_find && (current = prio_queue_get(&queue)) != NULL) {
> +		struct commit_list *parents;
> +
> +		if (current->object.flags & PARENT1) {
> +			current->object.flags &= ~PARENT1;
> +			current->object.flags |= reachable_flag;
> +			commit_list_insert(current, &found_commits);
> +			num_to_find--;

What is in "queue" are all reachable from "from" so we found this
object in the "to" set is reachable.  One down.

> +		}
> +
> +		for (parents = current->parents; parents; parents = parents->next) {
> +			struct commit *p = parents->item;
> +
> +			parse_commit(p);
> +
> +			if (p->generation < min_generation)
> +				continue;

Any commit reachable from "from" whose generation is too small
(i.e. old) can never reach any of "to", because all "to" are at
generation "min_generation" or greater.  Makes sense.

> +			if (p->object.flags & PARENT2)
> +				continue;

If the object is painted with PARENT2, we know we have it in queue
and traversing to find more of its ancestors.  Avoid recursing into
it twice.  Makes sense.

> +			p->object.flags |= PARENT2;
> +			prio_queue_put(&queue, p);

Otherwise, explore this parent.

> +		}
> +	}
> +
> +	clear_commit_marks_many(nr_to, to, PARENT1);

Among "to", the ones that were not found still have PARENT1.
Because we do not propagate this flag down the ancestry chain like
merge-base discovery, this only has to clear just one level.

> +	clear_commit_marks_many(nr_from, from, PARENT2);

And then we smudged everything that are reachable from "from"
with this flag.  In the worst case, i.e. when num_to_find is still
positive here, we would have painted all commits down to the root,
and we need to clear all of them.

> +	return found_commits;
> +}

OK, this all makes sense.  Unlike merge-base traversals, this does
not have to traverse from the "to" side at all, which makes it quite
simpler and straight-forward.

I do wonder if we can now reimplement in_merge_bases_many() in terms
of this helper, and if that gives us a better performance.  It asks
"is 'commit', i.e. a single 'to', an ancestor of, i.e. reachable
from, one of the 'references', i.e.  'from'"?

> diff --git a/commit-reach.h b/commit-reach.h
> index 7d313e297..43bd50a70 100644
> --- a/commit-reach.h
> +++ b/commit-reach.h
> @@ -74,4 +74,14 @@ int can_all_from_reach_with_flag(struct object_array *from,
>  int can_all_from_reach(struct commit_list *from, struct commit_list *to,
>  		       int commit_date_cutoff);
>  
> +
> +/*
> + * Return a list of commits containing the commits in the 'to' array
> + * that are reachable from at least one commit in the 'from' array.
> + * Also add the given 'flag' to each of the commits in the returned list.
> + */
> +struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
> +					 struct commit **to, int nr_to,
> +					 int reachable_flag);
> +
>  #endif