commit-reach: implement get_reachable_subset

The existing reachability algorithms in commit-reach.c focus on
finding merge-bases or determining if all commits in a set X can
reach at least one commit in a set Y. However, for two commits sets
X and Y, we may also care about which commits in Y are reachable
from at least one commit in X.

Implement get_reachable_subset() which answers this question. Given
two arrays of commits, 'from' and 'to', return a commit_list with
every commit from the 'to' array that is reachable from at least
one commit in the 'from' array.

The algorithm is a simple walk starting at the 'from' commits, using
the PARENT2 flag to indicate "this commit has already been added to
the walk queue". By marking the 'to' commits with the PARENT1 flag,
we can determine when we see a commit from the 'to' array. We remove
the PARENT1 flag as we add that commit to the result list to avoid
duplicates.

The order of the resulting list is a reverse of the order that the
commits are discovered in the walk.

There are a couple shortcuts to avoid walking more than we need:

1. We determine the minimum generation number of commits in the
   'to' array. We do not walk commits with generation number
   below this minimum.

2. We count how many distinct commits are in the 'to' array, and
   decrement this count when we discover a 'to' commit during the
   walk. If this number reaches zero, then we can terminate the
   walk.

Tests will be added using the 'test-tool reach' helper in a
subsequent commit.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/commit-reach.c b/commit-reach.c
index a9da65c4625cbbeb165b0c2d54fe3edabb1a3a34..d5a39defd3d5144f83d4f48e43e54e1f7f49ab29 100644 (file)
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -690,3 +690,72 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
        object_array_clear(&from_objs);
        return result;
 }
+
+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
+                                        struct commit **to, int nr_to,
+                                        unsigned int reachable_flag)
+{
+       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);
+               }
+       }
+
+       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--;
+               }
+
+               for (parents = current->parents; parents; parents = parents->next) {
+                       struct commit *p = parents->item;
+
+                       parse_commit(p);
+
+                       if (p->generation < min_generation)
+                               continue;
+
+                       if (p->object.flags & PARENT2)
+                               continue;
+
+                       p->object.flags |= PARENT2;
+                       prio_queue_put(&queue, p);
+               }
+       }
+
+       clear_commit_marks_many(nr_to, to, PARENT1);
+       clear_commit_marks_many(nr_from, from, PARENT2);
+
+       return found_commits;
+}

diff --git a/commit-reach.h b/commit-reach.h
index 122a23a24d8a40d213c7a1fb167f3f9c2b3c73d6..defcef4076f2b9427a2572087e5909cba99874b7 100644 (file)
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -74,4 +74,17 @@ 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.
+ *
+ * This method uses the PARENT1 and PARENT2 flags during its operation,
+ * so be sure these flags are not set before calling the method.
+ */
+struct commit_list *get_reachable_subset(struct commit **from, int nr_from,
+                                        struct commit **to, int nr_to,
+                                        unsigned int reachable_flag);
+
 #endif