Re: [PATCH 1/3] commit-reach: implement get_reachable_subset
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Oct 31, 2018, 03:35 UTC
- Message-ID
- <xmqqy3aeyehs.fsf@gitster-ct.c.googlers.com>
- In-Reply-To
- <4c0c5c9143a757ee5187ae6fca9a76f29b6c6ae2.1540908961.git.gitgitgadget@gmail.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.
Show 33 quoted lines
> +{
> + 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.
Show 8 quoted lines
> + 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.
Show 9 quoted lines
> + }
> +
> + 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'"?
Show 19 quoted lines
> 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