[PATCH] commit-reach: remove get_reachable_subset()

[PATCH] commit-reach: remove get_reachable_subset()

[Kristofer Karlsson via GitGitGadget]

From: Kristofer Karlsson <krka@spotify.com>

get_reachable_subset() and tips_reachable_from_bases() answer the
same question: given a set of bases and a set of tips, which tips
are reachable from at least one base?

get_reachable_subset() was introduced in fcb2c0769d (2018-11-02)
for add_missing_tags() in remote.c. tips_reachable_from_bases()
was added in cbfe360b14 (2023-03-20) as part of the ahead-behind
series. The two were never consolidated.

With a commit-graph, tips_reachable_from_bases() can have an edge:
its DFS raises the generation floor as lower targets are found,
pruning more aggressively than the static floor in
get_reachable_subset(). Without generation numbers, some edge cases
may be slower with DFS instead of BFS since the date-ordered
prio_queue naturally stays near the top of the graph, but this
should not matter in practice -- worst case both visit the full
graph down from the bases.

The flag in remote.c changes from 1 (bit 0) to TMP_MARK (bit 4)
because tips_reachable_from_bases() uses SEEN (bit 0) internally.
TMP_MARK is already used for deduplication earlier in the same
function and is cleared before the reachability check.

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
    commit-reach: remove get_reachable_subset()
    
    This removes get_reachable_subset() and converts its only caller to use
    tips_reachable_from_bases() directly. Both answer the same category-2
    reachability question ("which tips are reachable from these bases?") but
    were introduced years apart and never consolidated.
    
    On the no-commit-graph tradeoff: without generation numbers, the
    date-ordered BFS in get_reachable_subset() can be more disciplined than
    DFS since it naturally stays near the top of the graph. But this only
    matters for repositories that are both large enough for the difference
    to be measurable and missing a commit-graph -- a combination that would
    already struggle for many other reasons. The fix there is to enable the
    commit-graph, not to maintain two implementations of the same
    reachability query.
    
    Notes for reviewers:
    
     * The flag in remote.c changes from 1 to TMP_MARK because
       tips_reachable_from_bases() uses SEEN (bit 0) internally. TMP_MARK is
       already used earlier in the same function and is cleared before the
       reachability block.
    
     * The sent_tips array is converted to a commit_list to match the
       tips_reachable_from_bases() API. This is O(n) list-node allocations,
       negligible compared to the graph walk.
    
     * Test helper and test names rename from get_reachable_subset to
       tips_reachable_from_bases to match the function being exercised.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2144%2Fspkrka%2Fkrka%2Fremove-get-reachable-subset-v2-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2144/spkrka/krka/remove-get-reachable-subset-v2-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2144

 commit-reach.c        | 73 -------------------------------------------
 commit-reach.h        | 13 --------
 remote.c              | 19 ++++++-----
 t/helper/test-reach.c | 39 +++++++++++------------
 t/t6600-test-reach.sh | 18 +++++------
 5 files changed, 36 insertions(+), 126 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 5df471a313..e78752eb87 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -1013,79 +1013,6 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,
 	return result;
 }
 
-struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,
-					 struct commit **to, size_t 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;
-	timestamp_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++) {
-		timestamp_t generation;
-		struct commit *c = *item;
-
-		repo_parse_commit(the_repository, c);
-		generation = commit_graph_generation(c);
-		if (generation < min_generation)
-			min_generation = 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;
-			repo_parse_commit(the_repository, 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;
-
-			repo_parse_commit(the_repository, p);
-
-			if (commit_graph_generation(p) < min_generation)
-				continue;
-
-			if (p->object.flags & PARENT2)
-				continue;
-
-			p->object.flags |= PARENT2;
-			prio_queue_put(&queue, p);
-		}
-	}
-
-	clear_prio_queue(&queue);
-
-	clear_commit_marks_many(nr_to, to, PARENT1);
-	clear_commit_marks_many(nr_from, from, PARENT2);
-
-	return found_commits;
-}
-
 define_commit_slab(bit_arrays, struct bitmap *);
 static struct bit_arrays bit_arrays;
 
diff --git a/commit-reach.h b/commit-reach.h
index 3f3a563d8a..b3e7051738 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -96,19 +96,6 @@ 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, size_t nr_from,
-					 struct commit **to, size_t nr_to,
-					 unsigned int reachable_flag);
-
 struct ahead_behind_count {
 	/**
 	 * As input, the *_index members indicate which positions in
diff --git a/remote.c b/remote.c
index f1a3681b7c..7cdb59ed87 100644
--- a/remote.c
+++ b/remote.c
@@ -1459,9 +1459,8 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 	 * sent to the other side.
 	 */
 	if (sent_tips.nr) {
-		const int reachable_flag = 1;
-		struct commit_list *found_commits;
 		struct commit_stack src_commits = COMMIT_STACK_INIT;
+		struct commit_list *bases = NULL;
 
 		for_each_string_list_item(item, &src_tag) {
 			struct ref *ref = item->util;
@@ -1479,11 +1478,12 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 			commit_stack_push(&src_commits, commit);
 		}
 
-		found_commits = get_reachable_subset(sent_tips.items,
-						     sent_tips.nr,
-						     src_commits.items,
-						     src_commits.nr,
-						     reachable_flag);
+		for (size_t i = 0; i < sent_tips.nr; i++)
+			commit_list_insert(sent_tips.items[i], &bases);
+		tips_reachable_from_bases(the_repository,
+					 bases, src_commits.items,
+					 src_commits.nr, TMP_MARK);
+		commit_list_free(bases);
 
 		for_each_string_list_item(item, &src_tag) {
 			struct ref *dst_ref;
@@ -1503,7 +1503,7 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 			 * Is this tag, which they do not have, reachable from
 			 * any of the commits we are sending?
 			 */
-			if (!(commit->object.flags & reachable_flag))
+			if (!(commit->object.flags & TMP_MARK))
 				continue;
 
 			/* Add it in */
@@ -1513,9 +1513,8 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 		}
 
 		clear_commit_marks_many(src_commits.nr, src_commits.items,
-					reachable_flag);
+					TMP_MARK);
 		commit_stack_clear(&src_commits);
-		commit_list_free(found_commits);
 	}
 
 	string_list_clear(&src_tag, 0);
diff --git a/t/helper/test-reach.c b/t/helper/test-reach.c
index 5d86a96c17..eb44a64f50 100644
--- a/t/helper/test-reach.c
+++ b/t/helper/test-reach.c
@@ -7,6 +7,7 @@
 #include "hex.h"
 #include "object-name.h"
 #include "ref-filter.h"
+#include "revision.h"
 #include "setup.h"
 #include "string-list.h"
 #include "tag.h"
@@ -149,30 +150,26 @@ int cmd__reach(int ac, const char **av)
 
 		printf("%s(_,A,X,_):%d\n", av[1], commit_contains(&filter, A, X, &cache));
 		clear_contains_cache(&cache);
-	} else if (!strcmp(av[1], "get_reachable_subset")) {
-		const int reachable_flag = 1;
-		int count = 0;
-		struct commit_list *current;
-		struct commit_list *list = get_reachable_subset(X_stack.items, X_stack.nr,
-								Y_stack.items, Y_stack.nr,
-								reachable_flag);
-		printf("get_reachable_subset(X,Y)\n");
-		for (current = list; current; current = current->next) {
-			if (!(list->item->object.flags & reachable_flag))
-				die(_("commit %s is not marked reachable"),
-				    oid_to_hex(&list->item->object.oid));
-			count++;
-		}
+	} else if (!strcmp(av[1], "tips_reachable_from_bases")) {
+		struct commit_list *bases = NULL;
+		struct commit_list *result = NULL;
+
+		for (size_t i = 0; i < X_stack.nr; i++)
+			commit_list_insert(X_stack.items[i], &bases);
+		tips_reachable_from_bases(the_repository,
+					 bases, Y_stack.items,
+					 Y_stack.nr, TMP_MARK);
+		commit_list_free(bases);
+
+		printf("tips_reachable_from_bases(X,Y)\n");
 		for (size_t i = 0; i < Y_stack.nr; i++) {
-			if (Y_stack.items[i]->object.flags & reachable_flag)
-				count--;
+			if (Y_stack.items[i]->object.flags & TMP_MARK)
+				commit_list_insert(Y_stack.items[i], &result);
 		}
+		print_sorted_commit_ids(result);
 
-		if (count < 0)
-			die(_("too many commits marked reachable"));
-
-		print_sorted_commit_ids(list);
-		commit_list_free(list);
+		clear_commit_marks_many(Y_stack.nr, Y_stack.items, TMP_MARK);
+		commit_list_free(result);
 	}
 
 	object_array_clear(&X_obj);
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b5b314e570..51b140a539 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -391,7 +391,7 @@ test_expect_success 'rev-list: symmetric difference topo-order' '
 	run_all_modes git rev-list --topo-order commit-3-8...commit-6-6
 '
 
-test_expect_success 'get_reachable_subset:all' '
+test_expect_success 'tips_reachable_from_bases:all' '
 	cat >input <<-\EOF &&
 	X:commit-9-1
 	X:commit-8-3
@@ -403,15 +403,15 @@ test_expect_success 'get_reachable_subset:all' '
 	Y:commit-5-6
 	EOF
 	(
-		echo "get_reachable_subset(X,Y)" &&
+		echo "tips_reachable_from_bases(X,Y)" &&
 		git rev-parse commit-3-3 \
 			      commit-1-7 \
 			      commit-5-6 | sort
 	) >expect &&
-	test_all_modes get_reachable_subset
+	test_all_modes tips_reachable_from_bases
 '
 
-test_expect_success 'get_reachable_subset:some' '
+test_expect_success 'tips_reachable_from_bases:some' '
 	cat >input <<-\EOF &&
 	X:commit-9-1
 	X:commit-8-3
@@ -422,14 +422,14 @@ test_expect_success 'get_reachable_subset:some' '
 	Y:commit-5-6
 	EOF
 	(
-		echo "get_reachable_subset(X,Y)" &&
+		echo "tips_reachable_from_bases(X,Y)" &&
 		git rev-parse commit-3-3 \
 			      commit-1-7 | sort
 	) >expect &&
-	test_all_modes get_reachable_subset
+	test_all_modes tips_reachable_from_bases
 '
 
-test_expect_success 'get_reachable_subset:none' '
+test_expect_success 'tips_reachable_from_bases:none' '
 	cat >input <<-\EOF &&
 	X:commit-9-1
 	X:commit-8-3
@@ -439,8 +439,8 @@ test_expect_success 'get_reachable_subset:none' '
 	Y:commit-7-6
 	Y:commit-2-8
 	EOF
-	echo "get_reachable_subset(X,Y)" >expect &&
-	test_all_modes get_reachable_subset
+	echo "tips_reachable_from_bases(X,Y)" >expect &&
+	test_all_modes tips_reachable_from_bases
 '
 
 test_expect_success 'for-each-ref ahead-behind:linear' '

base-commit: 600fe743028cbfb640855f659e9851522214bc0b
-- 
gitgitgadget

Re: [PATCH] commit-reach: remove get_reachable_subset()

[Junio C Hamano]

"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
writes:

> get_reachable_subset() was introduced in fcb2c0769d (2018-11-02)
> for add_missing_tags() in remote.c. tips_reachable_from_bases()
> was added in cbfe360b14 (2023-03-20) as part of the ahead-behind
> series. The two were never consolidated.

Good finding.  It is curious to see that these were from the same
author.

> ... Without generation numbers, some edge cases
> may be slower with DFS instead of BFS since the date-ordered
> prio_queue naturally stays near the top of the graph, but this
> should not matter in practice

"should not matter in practice" because...?

> -- worst case both visit the full
> graph down from the bases.

And of course the worst case scenario is by definition not a typical
case that appear in practice, so it does not make a good explanation
for "should not matter in practice".

> The flag in remote.c changes from 1 (bit 0) to TMP_MARK (bit 4)
> because tips_reachable_from_bases() uses SEEN (bit 0) internally.
> TMP_MARK is already used for deduplication earlier in the same
> function and is cleared before the reachability check.

And tips_reachable_from_bases() clears SEEN at the end as expected.

>  commit-reach.c        | 73 -------------------------------------------
>  commit-reach.h        | 13 --------
>  remote.c              | 19 ++++++-----
>  t/helper/test-reach.c | 39 +++++++++++------------
>  t/t6600-test-reach.sh | 18 +++++------
>  5 files changed, 36 insertions(+), 126 deletions(-)

Yay, a lot of deletions ;-)

> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> index b5b314e570..51b140a539 100755
> --- a/t/t6600-test-reach.sh
> +++ b/t/t6600-test-reach.sh
> @@ -391,7 +391,7 @@ test_expect_success 'rev-list: symmetric difference topo-order' '
>  	run_all_modes git rev-list --topo-order commit-3-8...commit-6-6
>  '
>  
> -test_expect_success 'get_reachable_subset:all' '
> +test_expect_success 'tips_reachable_from_bases:all' '
>  	cat >input <<-\EOF &&
>  	X:commit-9-1
>  	X:commit-8-3
> @@ -403,15 +403,15 @@ test_expect_success 'get_reachable_subset:all' '
>  	Y:commit-5-6
>  	EOF
>  	(
> -		echo "get_reachable_subset(X,Y)" &&
> +		echo "tips_reachable_from_bases(X,Y)" &&
>  		git rev-parse commit-3-3 \
>  			      commit-1-7 \
>  			      commit-5-6 | sort
>  	) >expect &&
> -	test_all_modes get_reachable_subset
> +	test_all_modes tips_reachable_from_bases
>  '
>  
> -test_expect_success 'get_reachable_subset:some' '
> +test_expect_success 'tips_reachable_from_bases:some' '
>  	cat >input <<-\EOF &&
>  	X:commit-9-1
>  	X:commit-8-3
> @@ -422,14 +422,14 @@ test_expect_success 'get_reachable_subset:some' '
>  	Y:commit-5-6
>  	EOF
>  	(
> -		echo "get_reachable_subset(X,Y)" &&
> +		echo "tips_reachable_from_bases(X,Y)" &&
>  		git rev-parse commit-3-3 \
>  			      commit-1-7 | sort
>  	) >expect &&
> -	test_all_modes get_reachable_subset
> +	test_all_modes tips_reachable_from_bases
>  '
>  
> -test_expect_success 'get_reachable_subset:none' '
> +test_expect_success 'tips_reachable_from_bases:none' '
>  	cat >input <<-\EOF &&
>  	X:commit-9-1
>  	X:commit-8-3
> @@ -439,8 +439,8 @@ test_expect_success 'get_reachable_subset:none' '
>  	Y:commit-7-6
>  	Y:commit-2-8
>  	EOF
> -	echo "get_reachable_subset(X,Y)" >expect &&
> -	test_all_modes get_reachable_subset
> +	echo "tips_reachable_from_bases(X,Y)" >expect &&
> +	test_all_modes tips_reachable_from_bases
>  '
>  
>  test_expect_success 'for-each-ref ahead-behind:linear' '
>
> base-commit: 600fe743028cbfb640855f659e9851522214bc0b

Initially I feared that changes to the test script were a sign of
need to adjuist to behaviour changes, but as the proposed log
message explained, all of the above changes are about the name of
the function being used and tested, which makes sense.

Thanks.

Re: [PATCH] commit-reach: remove get_reachable_subset()

[Kristofer Karlsson]

Junio C Hamano <gitster@pobox.com> writes:

> "should not matter in practice" because...?
>
> And of course the worst case scenario is by definition not a typical
> case that appear in practice, so it does not make a good explanation
> for "should not matter in practice".

You are right, that was hand-wavy. I started with writing a somewhat
long analysis but after finding a clean way of supporting both DFS
and priority queue modes it feels somewhat unnecessary - I will
still include it here, but the short summary is that it's fixable.

Since the prio_queue struct supports both LIFO and heap mode,
it's actually quite easy to plug this into
tips_reachable_from_bases. I just need to switch away from using
the stack structure and pass a mode to choose between LIFO
and heap. This preserves the old behavior while still reducing
the code size and unifying the code more.

I will submit a v2 of the patch shortly.

I will also include the original analysis I wrote before finding
the simple fix.

Thanks for the review!
Kristofer

---
I will refer to the prio_queue approach in get_reachable_subset
as PQ for brevity, and the DFS in tips_reachable_from_bases as
simply DFS.

tips_reachable_from_bases() was designed for --merged queries where
the targets (branches/tags) can be deep ancestors of the base. DFS
is a natural fit there: it dives deep along first-parent quickly,
and with generation numbers the dynamic floor raising prunes
aggressively.

add_missing_tags() has the opposite shape: the bases are branch
tips being pushed (near the top) and the targets are tag commits
the remote does not have yet, which tend to be relatively close
to those tips. PQ ordered by commit date is a better fit here
because it sweeps down from the top and finds nearby targets early,
while DFS might take a long detour down a side branch before
coming back.

With a commit-graph this difference mostly disappears since the
generation floor keeps DFS from going too far off track. Without a
commit-graph, neither approach prunes anything (generation is
GENERATION_NUMBER_INFINITY for all commits) so the traversal order
is the only thing that matters, and PQ has the edge for shallow
targets.

So the current code actually has each caller matched to the
traversal strategy that fits its typical workload. My patch traded
that away for code reduction.

That said, in practice the difference is limited: repositories
large enough for this to matter typically have a commit-graph,
and small repositories are fast either way.
---

Re: [PATCH] commit-reach: remove get_reachable_subset()

[Derrick Stolee]

On 6/10/2026 11:48 AM, Junio C Hamano wrote:
> "Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
> writes:
> 
>> get_reachable_subset() was introduced in fcb2c0769d (2018-11-02)
>> for add_missing_tags() in remote.c. tips_reachable_from_bases()
>> was added in cbfe360b14 (2023-03-20) as part of the ahead-behind
>> series. The two were never consolidated.
> 
> Good finding.  It is curious to see that these were from the same
> author.

I agree. In my defense, these commits are five years apart. I still
should have looked for similar code that could be reused instead of
rolling new code. (But the new code is better when a commit-graph
exists.)

The other thing that I should have done in the later commit was add
the method to the test-tool, which you do here.

>> ... Without generation numbers, some edge cases
>> may be slower with DFS instead of BFS since the date-ordered
>> prio_queue naturally stays near the top of the graph, but this
>> should not matter in practice
> 
> "should not matter in practice" because...?
> 
>> -- worst case both visit the full
>> graph down from the bases.
> 
> And of course the worst case scenario is by definition not a typical
> case that appear in practice, so it does not make a good explanation
> for "should not matter in practice".

It's important to recognize the use cases that call each method and
to understand if it is appropriate to take these performance changes.

Both methods terminate in the case that all potential targets are
found. And that's the only case that matters, as we will walk all
reachable commits in the case of any one commit not being reachable.

Both methods avoid walking below the "minimum generation" among the
target commits.

The key opportunity here is that tips_reachable_from_bases() will
"increase" the minimum generation when it finds the current-minimum
target commit. That's a big reason why the DFS approach wins: it
has the opportunity to find those lower commits without needing to
walk _every_ commit with higher generation.

The one downside to this approach is that the DFS approach does not
take into account the commit date as a fallback when there is no
commit-graph file with computed generation numbers. When there is
no commit-graph file, then the fallback to commit date to break ties
among "generation number infinity" commits can't be used to help the
BFS search in get_reachable_subset().

And perhaps that is the critical reason for the different algorithms:
in 2018 we didn't have the commit-graph for very long so it wasn't a
reasonable expectation that we'd have one, even for large repositories.

Now? The feature is quite stable and it's easy for users to create
and maintain one. All servers are expected to use it for performance
needs. It's probably reasonable to expect that any repos where this
would matter would have one.

Thanks,
-Stolee