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

> "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.

> 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'"?