{"thread":{"id":"65780","subject":"[PATCH] commit-reach: remove get_reachable_subset()","startedAt":"2026-06-09T19:28:08Z","lastAt":"2026-06-15T20:58:34Z","messageCount":14,"participants":["Kristofer Karlsson via GitGitGadget","Junio C Hamano","Kristofer Karlsson","Derrick Stolee","Weijie Yuan"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"545090","messageId":"pull.2144.git.1781033285419.gitgitgadget@gmail.com","threadId":"65780","inReplyTo":null,"subject":"[PATCH] commit-reach: remove get_reachable_subset()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-09T19:28:04Z","receivedAt":"2026-06-09T19:28:08Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nget_reachable_subset() and tips_reachable_from_bases() answer the\nsame question: given a set of bases and a set of tips, which tips\nare reachable from at least one base?\n\nget_reachable_subset() was introduced in fcb2c0769d (2018-11-02)\nfor add_missing_tags() in remote.c. tips_reachable_from_bases()\nwas added in cbfe360b14 (2023-03-20) as part of the ahead-behind\nseries. The two were never consolidated.\n\nWith a commit-graph, tips_reachable_from_bases() can have an edge:\nits DFS raises the generation floor as lower targets are found,\npruning more aggressively than the static floor in\nget_reachable_subset(). Without generation numbers, some edge cases\nmay be slower with DFS instead of BFS since the date-ordered\nprio_queue naturally stays near the top of the graph, but this\nshould not matter in practice -- worst case both visit the full\ngraph down from the bases.\n\nThe flag in remote.c changes from 1 (bit 0) to TMP_MARK (bit 4)\nbecause tips_reachable_from_bases() uses SEEN (bit 0) internally.\nTMP_MARK is already used for deduplication earlier in the same\nfunction and is cleared before the reachability check.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n    commit-reach: remove get_reachable_subset()\n    \n    This removes get_reachable_subset() and converts its only caller to use\n    tips_reachable_from_bases() directly. Both answer the same category-2\n    reachability question (\"which tips are reachable from these bases?\") but\n    were introduced years apart and never consolidated.\n    \n    On the no-commit-graph tradeoff: without generation numbers, the\n    date-ordered BFS in get_reachable_subset() can be more disciplined than\n    DFS since it naturally stays near the top of the graph. But this only\n    matters for repositories that are both large enough for the difference\n    to be measurable and missing a commit-graph -- a combination that would\n    already struggle for many other reasons. The fix there is to enable the\n    commit-graph, not to maintain two implementations of the same\n    reachability query.\n    \n    Notes for reviewers:\n    \n     * The flag in remote.c changes from 1 to TMP_MARK because\n       tips_reachable_from_bases() uses SEEN (bit 0) internally. TMP_MARK is\n       already used earlier in the same function and is cleared before the\n       reachability block.\n    \n     * The sent_tips array is converted to a commit_list to match the\n       tips_reachable_from_bases() API. This is O(n) list-node allocations,\n       negligible compared to the graph walk.\n    \n     * Test helper and test names rename from get_reachable_subset to\n       tips_reachable_from_bases to match the function being exercised.\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2144%2Fspkrka%2Fkrka%2Fremove-get-reachable-subset-v2-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2144/spkrka/krka/remove-get-reachable-subset-v2-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/2144\n\n commit-reach.c        | 73 -------------------------------------------\n commit-reach.h        | 13 --------\n remote.c              | 19 ++++++-----\n t/helper/test-reach.c | 39 +++++++++++------------\n t/t6600-test-reach.sh | 18 +++++------\n 5 files changed, 36 insertions(+), 126 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 5df471a313..e78752eb87 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1013,79 +1013,6 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \treturn result;\n }\n \n-struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,\n-\t\t\t\t\t struct commit **to, size_t nr_to,\n-\t\t\t\t\t unsigned int reachable_flag)\n-{\n-\tstruct commit **item;\n-\tstruct commit *current;\n-\tstruct commit_list *found_commits = NULL;\n-\tstruct commit **to_last = to + nr_to;\n-\tstruct commit **from_last = from + nr_from;\n-\ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n-\tint num_to_find = 0;\n-\n-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n-\n-\tfor (item = to; item < to_last; item++) {\n-\t\ttimestamp_t generation;\n-\t\tstruct commit *c = *item;\n-\n-\t\trepo_parse_commit(the_repository, c);\n-\t\tgeneration = commit_graph_generation(c);\n-\t\tif (generation < min_generation)\n-\t\t\tmin_generation = generation;\n-\n-\t\tif (!(c->object.flags & PARENT1)) {\n-\t\t\tc->object.flags |= PARENT1;\n-\t\t\tnum_to_find++;\n-\t\t}\n-\t}\n-\n-\tfor (item = from; item < from_last; item++) {\n-\t\tstruct commit *c = *item;\n-\t\tif (!(c->object.flags & PARENT2)) {\n-\t\t\tc->object.flags |= PARENT2;\n-\t\t\trepo_parse_commit(the_repository, c);\n-\n-\t\t\tprio_queue_put(&queue, *item);\n-\t\t}\n-\t}\n-\n-\twhile (num_to_find && (current = prio_queue_get(&queue)) != NULL) {\n-\t\tstruct commit_list *parents;\n-\n-\t\tif (current->object.flags & PARENT1) {\n-\t\t\tcurrent->object.flags &= ~PARENT1;\n-\t\t\tcurrent->object.flags |= reachable_flag;\n-\t\t\tcommit_list_insert(current, &found_commits);\n-\t\t\tnum_to_find--;\n-\t\t}\n-\n-\t\tfor (parents = current->parents; parents; parents = parents->next) {\n-\t\t\tstruct commit *p = parents->item;\n-\n-\t\t\trepo_parse_commit(the_repository, p);\n-\n-\t\t\tif (commit_graph_generation(p) < min_generation)\n-\t\t\t\tcontinue;\n-\n-\t\t\tif (p->object.flags & PARENT2)\n-\t\t\t\tcontinue;\n-\n-\t\t\tp->object.flags |= PARENT2;\n-\t\t\tprio_queue_put(&queue, p);\n-\t\t}\n-\t}\n-\n-\tclear_prio_queue(&queue);\n-\n-\tclear_commit_marks_many(nr_to, to, PARENT1);\n-\tclear_commit_marks_many(nr_from, from, PARENT2);\n-\n-\treturn found_commits;\n-}\n-\n define_commit_slab(bit_arrays, struct bitmap *);\n static struct bit_arrays bit_arrays;\n \ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3f3a563d8a..b3e7051738 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -96,19 +96,6 @@ int can_all_from_reach_with_flag(struct object_array *from,\n int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t       int commit_date_cutoff);\n \n-\n-/*\n- * Return a list of commits containing the commits in the 'to' array\n- * that are reachable from at least one commit in the 'from' array.\n- * Also add the given 'flag' to each of the commits in the returned list.\n- *\n- * This method uses the PARENT1 and PARENT2 flags during its operation,\n- * so be sure these flags are not set before calling the method.\n- */\n-struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,\n-\t\t\t\t\t struct commit **to, size_t nr_to,\n-\t\t\t\t\t unsigned int reachable_flag);\n-\n struct ahead_behind_count {\n \t/**\n \t * As input, the *_index members indicate which positions in\ndiff --git a/remote.c b/remote.c\nindex f1a3681b7c..7cdb59ed87 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1459,9 +1459,8 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t * sent to the other side.\n \t */\n \tif (sent_tips.nr) {\n-\t\tconst int reachable_flag = 1;\n-\t\tstruct commit_list *found_commits;\n \t\tstruct commit_stack src_commits = COMMIT_STACK_INIT;\n+\t\tstruct commit_list *bases = NULL;\n \n \t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *ref = item->util;\n@@ -1479,11 +1478,12 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\tcommit_stack_push(&src_commits, commit);\n \t\t}\n \n-\t\tfound_commits = get_reachable_subset(sent_tips.items,\n-\t\t\t\t\t\t     sent_tips.nr,\n-\t\t\t\t\t\t     src_commits.items,\n-\t\t\t\t\t\t     src_commits.nr,\n-\t\t\t\t\t\t     reachable_flag);\n+\t\tfor (size_t i = 0; i < sent_tips.nr; i++)\n+\t\t\tcommit_list_insert(sent_tips.items[i], &bases);\n+\t\ttips_reachable_from_bases(the_repository,\n+\t\t\t\t\t bases, src_commits.items,\n+\t\t\t\t\t src_commits.nr, TMP_MARK);\n+\t\tcommit_list_free(bases);\n \n \t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *dst_ref;\n@@ -1503,7 +1503,7 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\t * Is this tag, which they do not have, reachable from\n \t\t\t * any of the commits we are sending?\n \t\t\t */\n-\t\t\tif (!(commit->object.flags & reachable_flag))\n+\t\t\tif (!(commit->object.flags & TMP_MARK))\n \t\t\t\tcontinue;\n \n \t\t\t/* Add it in */\n@@ -1513,9 +1513,8 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t}\n \n \t\tclear_commit_marks_many(src_commits.nr, src_commits.items,\n-\t\t\t\t\treachable_flag);\n+\t\t\t\t\tTMP_MARK);\n \t\tcommit_stack_clear(&src_commits);\n-\t\tcommit_list_free(found_commits);\n \t}\n \n \tstring_list_clear(&src_tag, 0);\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 5d86a96c17..eb44a64f50 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -7,6 +7,7 @@\n #include \"hex.h\"\n #include \"object-name.h\"\n #include \"ref-filter.h\"\n+#include \"revision.h\"\n #include \"setup.h\"\n #include \"string-list.h\"\n #include \"tag.h\"\n@@ -149,30 +150,26 @@ int cmd__reach(int ac, const char **av)\n \n \t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1], commit_contains(&filter, A, X, &cache));\n \t\tclear_contains_cache(&cache);\n-\t} else if (!strcmp(av[1], \"get_reachable_subset\")) {\n-\t\tconst int reachable_flag = 1;\n-\t\tint count = 0;\n-\t\tstruct commit_list *current;\n-\t\tstruct commit_list *list = get_reachable_subset(X_stack.items, X_stack.nr,\n-\t\t\t\t\t\t\t\tY_stack.items, Y_stack.nr,\n-\t\t\t\t\t\t\t\treachable_flag);\n-\t\tprintf(\"get_reachable_subset(X,Y)\\n\");\n-\t\tfor (current = list; current; current = current->next) {\n-\t\t\tif (!(list->item->object.flags & reachable_flag))\n-\t\t\t\tdie(_(\"commit %s is not marked reachable\"),\n-\t\t\t\t    oid_to_hex(&list->item->object.oid));\n-\t\t\tcount++;\n-\t\t}\n+\t} else if (!strcmp(av[1], \"tips_reachable_from_bases\")) {\n+\t\tstruct commit_list *bases = NULL;\n+\t\tstruct commit_list *result = NULL;\n+\n+\t\tfor (size_t i = 0; i < X_stack.nr; i++)\n+\t\t\tcommit_list_insert(X_stack.items[i], &bases);\n+\t\ttips_reachable_from_bases(the_repository,\n+\t\t\t\t\t bases, Y_stack.items,\n+\t\t\t\t\t Y_stack.nr, TMP_MARK);\n+\t\tcommit_list_free(bases);\n+\n+\t\tprintf(\"tips_reachable_from_bases(X,Y)\\n\");\n \t\tfor (size_t i = 0; i < Y_stack.nr; i++) {\n-\t\t\tif (Y_stack.items[i]->object.flags & reachable_flag)\n-\t\t\t\tcount--;\n+\t\t\tif (Y_stack.items[i]->object.flags & TMP_MARK)\n+\t\t\t\tcommit_list_insert(Y_stack.items[i], &result);\n \t\t}\n+\t\tprint_sorted_commit_ids(result);\n \n-\t\tif (count < 0)\n-\t\t\tdie(_(\"too many commits marked reachable\"));\n-\n-\t\tprint_sorted_commit_ids(list);\n-\t\tcommit_list_free(list);\n+\t\tclear_commit_marks_many(Y_stack.nr, Y_stack.items, TMP_MARK);\n+\t\tcommit_list_free(result);\n \t}\n \n \tobject_array_clear(&X_obj);\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b5b314e570..51b140a539 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -391,7 +391,7 @@ test_expect_success 'rev-list: symmetric difference topo-order' '\n \trun_all_modes git rev-list --topo-order commit-3-8...commit-6-6\n '\n \n-test_expect_success 'get_reachable_subset:all' '\n+test_expect_success 'tips_reachable_from_bases:all' '\n \tcat >input <<-\\EOF &&\n \tX:commit-9-1\n \tX:commit-8-3\n@@ -403,15 +403,15 @@ test_expect_success 'get_reachable_subset:all' '\n \tY:commit-5-6\n \tEOF\n \t(\n-\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\techo \"tips_reachable_from_bases(X,Y)\" &&\n \t\tgit rev-parse commit-3-3 \\\n \t\t\t      commit-1-7 \\\n \t\t\t      commit-5-6 | sort\n \t) >expect &&\n-\ttest_all_modes get_reachable_subset\n+\ttest_all_modes tips_reachable_from_bases\n '\n \n-test_expect_success 'get_reachable_subset:some' '\n+test_expect_success 'tips_reachable_from_bases:some' '\n \tcat >input <<-\\EOF &&\n \tX:commit-9-1\n \tX:commit-8-3\n@@ -422,14 +422,14 @@ test_expect_success 'get_reachable_subset:some' '\n \tY:commit-5-6\n \tEOF\n \t(\n-\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\techo \"tips_reachable_from_bases(X,Y)\" &&\n \t\tgit rev-parse commit-3-3 \\\n \t\t\t      commit-1-7 | sort\n \t) >expect &&\n-\ttest_all_modes get_reachable_subset\n+\ttest_all_modes tips_reachable_from_bases\n '\n \n-test_expect_success 'get_reachable_subset:none' '\n+test_expect_success 'tips_reachable_from_bases:none' '\n \tcat >input <<-\\EOF &&\n \tX:commit-9-1\n \tX:commit-8-3\n@@ -439,8 +439,8 @@ test_expect_success 'get_reachable_subset:none' '\n \tY:commit-7-6\n \tY:commit-2-8\n \tEOF\n-\techo \"get_reachable_subset(X,Y)\" >expect &&\n-\ttest_all_modes get_reachable_subset\n+\techo \"tips_reachable_from_bases(X,Y)\" >expect &&\n+\ttest_all_modes tips_reachable_from_bases\n '\n \n test_expect_success 'for-each-ref ahead-behind:linear' '\n\nbase-commit: 600fe743028cbfb640855f659e9851522214bc0b\n-- \ngitgitgadget\n"},{"id":"545167","messageId":"xmqqbjdixupc.fsf@gitster.g","threadId":"65780","inReplyTo":"pull.2144.git.1781033285419.gitgitgadget@gmail.com","subject":"Re: [PATCH] commit-reach: remove get_reachable_subset()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-10T15:48:31Z","receivedAt":"2026-06-10T15:48:33Z","isPatch":true,"body":"\"Kristofer Karlsson via GitGitGadget\" <gitgitgadget@gmail.com>\nwrites:\n\n> get_reachable_subset() was introduced in fcb2c0769d (2018-11-02)\n> for add_missing_tags() in remote.c. tips_reachable_from_bases()\n> was added in cbfe360b14 (2023-03-20) as part of the ahead-behind\n> series. The two were never consolidated.\n\nGood finding.  It is curious to see that these were from the same\nauthor.\n\n> ... Without generation numbers, some edge cases\n> may be slower with DFS instead of BFS since the date-ordered\n> prio_queue naturally stays near the top of the graph, but this\n> should not matter in practice\n\n\"should not matter in practice\" because...?\n\n> -- worst case both visit the full\n> graph down from the bases.\n\nAnd of course the worst case scenario is by definition not a typical\ncase that appear in practice, so it does not make a good explanation\nfor \"should not matter in practice\".\n\n> The flag in remote.c changes from 1 (bit 0) to TMP_MARK (bit 4)\n> because tips_reachable_from_bases() uses SEEN (bit 0) internally.\n> TMP_MARK is already used for deduplication earlier in the same\n> function and is cleared before the reachability check.\n\nAnd tips_reachable_from_bases() clears SEEN at the end as expected.\n\n>  commit-reach.c        | 73 -------------------------------------------\n>  commit-reach.h        | 13 --------\n>  remote.c              | 19 ++++++-----\n>  t/helper/test-reach.c | 39 +++++++++++------------\n>  t/t6600-test-reach.sh | 18 +++++------\n>  5 files changed, 36 insertions(+), 126 deletions(-)\n\nYay, a lot of deletions ;-)\n\n> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\n> index b5b314e570..51b140a539 100755\n> --- a/t/t6600-test-reach.sh\n> +++ b/t/t6600-test-reach.sh\n> @@ -391,7 +391,7 @@ test_expect_success 'rev-list: symmetric difference topo-order' '\n>  \trun_all_modes git rev-list --topo-order commit-3-8...commit-6-6\n>  '\n>  \n> -test_expect_success 'get_reachable_subset:all' '\n> +test_expect_success 'tips_reachable_from_bases:all' '\n>  \tcat >input <<-\\EOF &&\n>  \tX:commit-9-1\n>  \tX:commit-8-3\n> @@ -403,15 +403,15 @@ test_expect_success 'get_reachable_subset:all' '\n>  \tY:commit-5-6\n>  \tEOF\n>  \t(\n> -\t\techo \"get_reachable_subset(X,Y)\" &&\n> +\t\techo \"tips_reachable_from_bases(X,Y)\" &&\n>  \t\tgit rev-parse commit-3-3 \\\n>  \t\t\t      commit-1-7 \\\n>  \t\t\t      commit-5-6 | sort\n>  \t) >expect &&\n> -\ttest_all_modes get_reachable_subset\n> +\ttest_all_modes tips_reachable_from_bases\n>  '\n>  \n> -test_expect_success 'get_reachable_subset:some' '\n> +test_expect_success 'tips_reachable_from_bases:some' '\n>  \tcat >input <<-\\EOF &&\n>  \tX:commit-9-1\n>  \tX:commit-8-3\n> @@ -422,14 +422,14 @@ test_expect_success 'get_reachable_subset:some' '\n>  \tY:commit-5-6\n>  \tEOF\n>  \t(\n> -\t\techo \"get_reachable_subset(X,Y)\" &&\n> +\t\techo \"tips_reachable_from_bases(X,Y)\" &&\n>  \t\tgit rev-parse commit-3-3 \\\n>  \t\t\t      commit-1-7 | sort\n>  \t) >expect &&\n> -\ttest_all_modes get_reachable_subset\n> +\ttest_all_modes tips_reachable_from_bases\n>  '\n>  \n> -test_expect_success 'get_reachable_subset:none' '\n> +test_expect_success 'tips_reachable_from_bases:none' '\n>  \tcat >input <<-\\EOF &&\n>  \tX:commit-9-1\n>  \tX:commit-8-3\n> @@ -439,8 +439,8 @@ test_expect_success 'get_reachable_subset:none' '\n>  \tY:commit-7-6\n>  \tY:commit-2-8\n>  \tEOF\n> -\techo \"get_reachable_subset(X,Y)\" >expect &&\n> -\ttest_all_modes get_reachable_subset\n> +\techo \"tips_reachable_from_bases(X,Y)\" >expect &&\n> +\ttest_all_modes tips_reachable_from_bases\n>  '\n>  \n>  test_expect_success 'for-each-ref ahead-behind:linear' '\n>\n> base-commit: 600fe743028cbfb640855f659e9851522214bc0b\n\nInitially I feared that changes to the test script were a sign of\nneed to adjuist to behaviour changes, but as the proposed log\nmessage explained, all of the above changes are about the name of\nthe function being used and tested, which makes sense.\n\nThanks.\n"},{"id":"545178","messageId":"CAL71e4NqCD0P_=qnT2R9ThNHEQx6qo27i_7Wj3Xnb9Xg0kcM2A@mail.gmail.com","threadId":"65780","inReplyTo":"xmqqbjdixupc.fsf@gitster.g","subject":"Re: [PATCH] commit-reach: remove get_reachable_subset()","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-10T18:25:17Z","receivedAt":"2026-06-10T18:25:29Z","isPatch":true,"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> \"should not matter in practice\" because...?\n>\n> And of course the worst case scenario is by definition not a typical\n> case that appear in practice, so it does not make a good explanation\n> for \"should not matter in practice\".\n\nYou are right, that was hand-wavy. I started with writing a somewhat\nlong analysis but after finding a clean way of supporting both DFS\nand priority queue modes it feels somewhat unnecessary - I will\nstill include it here, but the short summary is that it's fixable.\n\nSince the prio_queue struct supports both LIFO and heap mode,\nit's actually quite easy to plug this into\ntips_reachable_from_bases. I just need to switch away from using\nthe stack structure and pass a mode to choose between LIFO\nand heap. This preserves the old behavior while still reducing\nthe code size and unifying the code more.\n\nI will submit a v2 of the patch shortly.\n\nI will also include the original analysis I wrote before finding\nthe simple fix.\n\nThanks for the review!\nKristofer\n\n---\nI will refer to the prio_queue approach in get_reachable_subset\nas PQ for brevity, and the DFS in tips_reachable_from_bases as\nsimply DFS.\n\ntips_reachable_from_bases() was designed for --merged queries where\nthe targets (branches/tags) can be deep ancestors of the base. DFS\nis a natural fit there: it dives deep along first-parent quickly,\nand with generation numbers the dynamic floor raising prunes\naggressively.\n\nadd_missing_tags() has the opposite shape: the bases are branch\ntips being pushed (near the top) and the targets are tag commits\nthe remote does not have yet, which tend to be relatively close\nto those tips. PQ ordered by commit date is a better fit here\nbecause it sweeps down from the top and finds nearby targets early,\nwhile DFS might take a long detour down a side branch before\ncoming back.\n\nWith a commit-graph this difference mostly disappears since the\ngeneration floor keeps DFS from going too far off track. Without a\ncommit-graph, neither approach prunes anything (generation is\nGENERATION_NUMBER_INFINITY for all commits) so the traversal order\nis the only thing that matters, and PQ has the edge for shallow\ntargets.\n\nSo the current code actually has each caller matched to the\ntraversal strategy that fits its typical workload. My patch traded\nthat away for code reduction.\n\nThat said, in practice the difference is limited: repositories\nlarge enough for this to matter typically have a commit-graph,\nand small repositories are fast either way.\n---\n"},{"id":"545185","messageId":"eae94a67-9c66-4b1d-9f0b-45ee3e80ddf8@gmail.com","threadId":"65780","inReplyTo":"xmqqbjdixupc.fsf@gitster.g","subject":"Re: [PATCH] commit-reach: remove get_reachable_subset()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-10T19:29:01Z","receivedAt":"2026-06-10T19:29:04Z","isPatch":true,"body":"On 6/10/2026 11:48 AM, Junio C Hamano wrote:\n> \"Kristofer Karlsson via GitGitGadget\" <gitgitgadget@gmail.com>\n> writes:\n> \n>> get_reachable_subset() was introduced in fcb2c0769d (2018-11-02)\n>> for add_missing_tags() in remote.c. tips_reachable_from_bases()\n>> was added in cbfe360b14 (2023-03-20) as part of the ahead-behind\n>> series. The two were never consolidated.\n> \n> Good finding.  It is curious to see that these were from the same\n> author.\n\nI agree. In my defense, these commits are five years apart. I still\nshould have looked for similar code that could be reused instead of\nrolling new code. (But the new code is better when a commit-graph\nexists.)\n\nThe other thing that I should have done in the later commit was add\nthe method to the test-tool, which you do here.\n\n>> ... Without generation numbers, some edge cases\n>> may be slower with DFS instead of BFS since the date-ordered\n>> prio_queue naturally stays near the top of the graph, but this\n>> should not matter in practice\n> \n> \"should not matter in practice\" because...?\n> \n>> -- worst case both visit the full\n>> graph down from the bases.\n> \n> And of course the worst case scenario is by definition not a typical\n> case that appear in practice, so it does not make a good explanation\n> for \"should not matter in practice\".\n\nIt's important to recognize the use cases that call each method and\nto understand if it is appropriate to take these performance changes.\n\nBoth methods terminate in the case that all potential targets are\nfound. And that's the only case that matters, as we will walk all\nreachable commits in the case of any one commit not being reachable.\n\nBoth methods avoid walking below the \"minimum generation\" among the\ntarget commits.\n\nThe key opportunity here is that tips_reachable_from_bases() will\n\"increase\" the minimum generation when it finds the current-minimum\ntarget commit. That's a big reason why the DFS approach wins: it\nhas the opportunity to find those lower commits without needing to\nwalk _every_ commit with higher generation.\n\nThe one downside to this approach is that the DFS approach does not\ntake into account the commit date as a fallback when there is no\ncommit-graph file with computed generation numbers. When there is\nno commit-graph file, then the fallback to commit date to break ties\namong \"generation number infinity\" commits can't be used to help the\nBFS search in get_reachable_subset().\n\nAnd perhaps that is the critical reason for the different algorithms:\nin 2018 we didn't have the commit-graph for very long so it wasn't a\nreasonable expectation that we'd have one, even for large repositories.\n\nNow? The feature is quite stable and it's easy for users to create\nand maintain one. All servers are expected to use it for performance\nneeds. It's probably reasonable to expect that any repos where this\nwould matter would have one.\n\nThanks,\n-Stolee\n\n"},{"id":"545262","messageId":"pull.2144.v2.git.1781178567862.gitgitgadget@gmail.com","threadId":"65780","inReplyTo":"pull.2144.git.1781033285419.gitgitgadget@gmail.com","subject":"[PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Kristofer Karlsson via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2026-06-11T11:49:27Z","receivedAt":"2026-06-11T11:49:30Z","isPatch":true,"body":"From: Kristofer Karlsson <krka@spotify.com>\n\nget_reachable_subset() and tips_reachable_from_bases() both answer\nthe same reachability question but use different traversal\nstrategies: priority queue vs depth-first search.  Consolidate them\ninto tips_reachable_from_bases() with a mode parameter to select\nbetween DFS and PQ traversal, preserving the preferred strategy for\neach caller.\n\nThis works cleanly because prio_queue already supports LIFO mode\n(when compare is NULL), so a single prio_queue acts as either a\nstack or a heap depending on the mode.\n\nThe unified traversal pushes all unseen parents at once rather than\npeeking and pushing one parent at a time.  This eliminates merge\ncommit revisits entirely: a 2-parent merge now requires 1 visit\ninstead of 3.  For DFS (LIFO) mode, the first parent is pushed\nlast so it ends up on top of the stack, preserving first-parent\ntraversal order.\n\nParsing is deferred to pop time for DFS since parent objects carry\nvalid flags without a full repo_parse_commit() call.  PQ mode\nparses before push so the heap can order by generation number.\n\nAdd exhaustive reachability tests that use every commit in the\ngrid as a tip, protecting against subtle traversal bugs such as\nwrong parent ordering or premature pruning.  The existing tests\nare also extended to exercise both DFS and PQ modes.\n\nThe flag in remote.c changes from 1 (bit 0) to TMP_MARK (bit 4)\nbecause tips_reachable_from_bases() uses SEEN (bit 0) internally.\nTMP_MARK is already used for deduplication earlier in the same\nfunction and is cleared before the reachability check.\n\nSigned-off-by: Kristofer Karlsson <krka@spotify.com>\n---\n    commit-reach: remove get_reachable_subset()\n    \n    This removes get_reachable_subset() and consolidates its only caller\n    into tips_reachable_from_bases() with a mode parameter to select between\n    DFS and priority queue traversal. Both functions answer the same\n    reachability query and use the same generation-number pruning strategy,\n    differing primarily in traversal order (DFS vs generation-ordered PQ).\n    They were introduced years apart and never consolidated.\n    \n    The unified function uses prio_queue for both modes: LIFO (stack) when\n    compare is NULL, min-heap when given a comparator.\n    \n    Changes since v1:\n    \n     * Replaced the commit_stack + reverse-push pattern with a simpler\n       approach: push all unseen parents directly, with the first parent\n       pushed last so it lands on top of the LIFO stack. This preserves\n       first-parent DFS order without needing a temporary stack to reverse\n       parent order.\n    \n     * Deferred repo_parse_commit() to pop time for DFS mode. Parent objects\n       carry valid flags without a full parse, so we avoid parsing\n       already-SEEN parents in the inner loop. PQ mode still parses before\n       push so the heap can order by generation number.\n    \n     * Moved the generation floor check from the parent loop to pop time,\n       simplifying the hot path at the cost of occasionally enqueueing\n       commits that will later be discarded.\n    \n     * Added SEEN flag on base commits before enqueueing, preventing\n       duplicate processing if bases overlap with the traversal.\n    \n     * Added PQ mode to the existing test-reach tests so both DFS and PQ\n       paths are exercised by the test suite.\n    \n     * Added two new reachability tests that use all 100 commits in the grid\n       as tips - the idea is to better detect subtle traversal bugs.\n    \n    Notes for reviewers:\n    \n     * The flag in remote.c changes from 1 to TMP_MARK because\n       tips_reachable_from_bases() uses SEEN (bit 0) internally. TMP_MARK is\n       already used earlier in the same function and is cleared before the\n       reachability block.\n    \n     * Test helper and test names rename from get_reachable_subset to\n       tips_reachable_from_bases to match the function being exercised.\n    \n    As Stolee noted in the v1 review, commit-graph is now stable and\n    expected for repositories where this matters, making the DFS approach\n    with dynamic floor raising an attractive default. The mode parameter\n    could be dropped in a future patch if we decide to use DFS everywhere,\n    but preserving each caller's existing strategy keeps this change\n    conservative and avoids any behavior change for add_missing_tags().\n    \n    Performance was not a goal of this refactoring, but the simplified DFS\n    traversal turned out to be a pleasant surprise -- eliminating merge\n    commit revisits and deferring parse to pop time gives a consistent\n    speedup across repositories:\n    \n    Benchmark results (median, 30 runs, pre-built binaries):\n    \n    Repository   Command                   Speedup\n    -----------------------------------------------------------\n    linux        branch --merged=HEAD       1.09x faster\n    linux        for-each-ref --merged=HEAD 1.14x faster\n    git          branch --merged=HEAD       neutral\n    git          for-each-ref --merged=HEAD 1.12x faster\n    \n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-2144%2Fspkrka%2Fkrka%2Fremove-get-reachable-subset-v2-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2144/spkrka/krka/remove-get-reachable-subset-v2-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/2144\n\nRange-diff vs v1:\n\n 1:  df8e2de11b ! 1:  da01032a32 commit-reach: remove get_reachable_subset()\n     @@ Metadata\n       ## Commit message ##\n          commit-reach: remove get_reachable_subset()\n      \n     -    get_reachable_subset() and tips_reachable_from_bases() answer the\n     -    same question: given a set of bases and a set of tips, which tips\n     -    are reachable from at least one base?\n     +    get_reachable_subset() and tips_reachable_from_bases() both answer\n     +    the same reachability question but use different traversal\n     +    strategies: priority queue vs depth-first search.  Consolidate them\n     +    into tips_reachable_from_bases() with a mode parameter to select\n     +    between DFS and PQ traversal, preserving the preferred strategy for\n     +    each caller.\n      \n     -    get_reachable_subset() was introduced in fcb2c0769d (2018-11-02)\n     -    for add_missing_tags() in remote.c. tips_reachable_from_bases()\n     -    was added in cbfe360b14 (2023-03-20) as part of the ahead-behind\n     -    series. The two were never consolidated.\n     +    This works cleanly because prio_queue already supports LIFO mode\n     +    (when compare is NULL), so a single prio_queue acts as either a\n     +    stack or a heap depending on the mode.\n      \n     -    With a commit-graph, tips_reachable_from_bases() can have an edge:\n     -    its DFS raises the generation floor as lower targets are found,\n     -    pruning more aggressively than the static floor in\n     -    get_reachable_subset(). Without generation numbers, some edge cases\n     -    may be slower with DFS instead of BFS since the date-ordered\n     -    prio_queue naturally stays near the top of the graph, but this\n     -    should not matter in practice -- worst case both visit the full\n     -    graph down from the bases.\n     +    The unified traversal pushes all unseen parents at once rather than\n     +    peeking and pushing one parent at a time.  This eliminates merge\n     +    commit revisits entirely: a 2-parent merge now requires 1 visit\n     +    instead of 3.  For DFS (LIFO) mode, the first parent is pushed\n     +    last so it ends up on top of the stack, preserving first-parent\n     +    traversal order.\n     +\n     +    Parsing is deferred to pop time for DFS since parent objects carry\n     +    valid flags without a full repo_parse_commit() call.  PQ mode\n     +    parses before push so the heap can order by generation number.\n     +\n     +    Add exhaustive reachability tests that use every commit in the\n     +    grid as a tip, protecting against subtle traversal bugs such as\n     +    wrong parent ordering or premature pruning.  The existing tests\n     +    are also extended to exercise both DFS and PQ modes.\n      \n          The flag in remote.c changes from 1 (bit 0) to TMP_MARK (bit 4)\n          because tips_reachable_from_bases() uses SEEN (bit 0) internally.\n     @@ commit-reach.c: int can_all_from_reach(struct commit_list *from, struct commit_l\n       define_commit_slab(bit_arrays, struct bitmap *);\n       static struct bit_arrays bit_arrays;\n       \n     +@@ commit-reach.c: static int compare_commit_and_index_by_generation(const void *va, const void *vb\n     + void tips_reachable_from_bases(struct repository *r,\n     + \t\t\t       struct commit_list *bases,\n     + \t\t\t       struct commit **tips, size_t tips_nr,\n     +-\t\t\t       int mark)\n     ++\t\t\t       int mark, enum tips_reachable_mode mode)\n     + {\n     + \tstruct commit_and_index *commits;\n     ++\tstruct commit_list *p;\n     ++\tstruct commit *c;\n     + \tsize_t min_generation_index = 0;\n     + \ttimestamp_t min_generation;\n     +-\tstruct commit_list *stack = NULL;\n     ++\tstruct prio_queue queue = { NULL };\n     + \n     + \tif (!bases || !tips || !tips_nr)\n     + \t\treturn;\n     + \n     + \t/*\n     +-\t * Do a depth-first search starting at 'bases' to search for the\n     +-\t * tips. Stop at the lowest (un-found) generation number. When\n     +-\t * finding the lowest commit, increase the minimum generation\n     +-\t * number to the next lowest (un-found) generation number.\n     ++\t * Search starting at 'bases' looking for the tips. Stop at the\n     ++\t * lowest un-found generation number, raising the floor as tips\n     ++\t * are found. Use DFS by default; with TIPS_REACHABLE_PQ,\n     ++\t * use a priority queue ordered by generation then commit date.\n     + \t */\n     ++\tif (mode == TIPS_REACHABLE_PQ)\n     ++\t\tqueue.compare = compare_commits_by_gen_then_commit_date;\n     + \n     + \tCALLOC_ARRAY(commits, tips_nr);\n     + \n     +@@ commit-reach.c: void tips_reachable_from_bases(struct repository *r,\n     + \n     + \twhile (bases) {\n     + \t\trepo_parse_commit(r, bases->item);\n     +-\t\tcommit_list_insert(bases->item, &stack);\n     ++\t\tbases->item->object.flags |= SEEN;\n     ++\t\tprio_queue_put(&queue, bases->item);\n     + \t\tbases = bases->next;\n     + \t}\n     + \n     +-\twhile (stack) {\n     +-\t\tint explored_all_parents = 1;\n     +-\t\tstruct commit_list *p;\n     +-\t\tstruct commit *c = stack->item;\n     ++\twhile ((c = prio_queue_get(&queue))) {\n     ++\t\tstruct commit *first_parent = NULL;\n     ++\n     ++\t\trepo_parse_commit(r, c);\n     ++\n     ++\t\t/* Skip if below the current generation floor. */\n     ++\t\tif (commit_graph_generation(c) < min_generation)\n     ++\t\t\tcontinue;\n     + \n     + \t\t/* Does it match any of our tips? */\n     + \t\t{\n     +@@ commit-reach.c: void tips_reachable_from_bases(struct repository *r,\n     + \t\t}\n     + \n     + \t\tfor (p = c->parents; p; p = p->next) {\n     +-\t\t\trepo_parse_commit(r, p->item);\n     +-\n     + \t\t\t/* Have we already explored this parent? */\n     + \t\t\tif (p->item->object.flags & SEEN)\n     + \t\t\t\tcontinue;\n     + \n     +-\t\t\t/* Is it below the current minimum generation? */\n     +-\t\t\tif (commit_graph_generation(p->item) < min_generation)\n     +-\t\t\t\tcontinue;\n     +-\n     + \t\t\t/* Ok, we will explore from here on. */\n     + \t\t\tp->item->object.flags |= SEEN;\n     +-\t\t\texplored_all_parents = 0;\n     +-\t\t\tcommit_list_insert(p->item, &stack);\n     +-\t\t\tbreak;\n     ++\t\t\t/* Parse before pushing in PQ mode for ordering. */\n     ++\t\t\tif (mode == TIPS_REACHABLE_PQ)\n     ++\t\t\t\trepo_parse_commit(r, p->item);\n     ++\t\t\tif (!first_parent)\n     ++\t\t\t\tfirst_parent = p->item;\n     ++\t\t\telse\n     ++\t\t\t\tprio_queue_put(&queue, p->item);\n     + \t\t}\n     +-\n     +-\t\tif (explored_all_parents)\n     +-\t\t\tpop_commit(&stack);\n     ++\t\t/*\n     ++\t\t * Add the first parent last so that it is on top of\n     ++\t\t * the LIFO queue, maintaining first-parent DFS order.\n     ++\t\t */\n     ++\t\tif (first_parent)\n     ++\t\t\tprio_queue_put(&queue, first_parent);\n     + \t}\n     + \n     + done:\n     +@@ commit-reach.c: done:\n     + \t\tcommits[i].commit->object.flags &= ~RESULT;\n     + \tfree(commits);\n     + \trepo_clear_commit_marks(r, SEEN);\n     +-\tcommit_list_free(stack);\n     ++\tclear_prio_queue(&queue);\n     + }\n     + \n     + /*\n      \n       ## commit-reach.h ##\n      @@ commit-reach.h: int can_all_from_reach_with_flag(struct object_array *from,\n     @@ commit-reach.h: int can_all_from_reach_with_flag(struct object_array *from,\n       struct ahead_behind_count {\n       \t/**\n       \t * As input, the *_index members indicate which positions in\n     +@@ commit-reach.h: void ahead_behind(struct repository *r,\n     +  * For all tip commits, add 'mark' to their flags if and only if they\n     +  * are reachable from one of the commits in 'bases'.\n     +  */\n     ++enum tips_reachable_mode {\n     ++\tTIPS_REACHABLE_DFS,\n     ++\tTIPS_REACHABLE_PQ,\n     ++};\n     + void tips_reachable_from_bases(struct repository *r,\n     + \t\t\t       struct commit_list *bases,\n     + \t\t\t       struct commit **tips, size_t tips_nr,\n     +-\t\t\t       int mark);\n     ++\t\t\t       int mark, enum tips_reachable_mode mode);\n     + \n     + /*\n     +  * Given a 'tip' commit and a list potential 'bases', return the index 'i' that\n     +\n     + ## ref-filter.c ##\n     +@@ ref-filter.c: static void reach_filter(struct ref_array *array,\n     + \ttips_reachable_from_bases(the_repository,\n     + \t\t\t\t  *check_reachable,\n     + \t\t\t\t  to_clear, array->nr,\n     +-\t\t\t\t  UNINTERESTING);\n     ++\t\t\t\t  UNINTERESTING, TIPS_REACHABLE_DFS);\n     + \n     + \told_nr = array->nr;\n     + \tarray->nr = 0;\n      \n       ## remote.c ##\n      @@ remote.c: static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n     @@ remote.c: static void add_missing_tags(struct ref *src, struct ref **dst, struct\n      +\t\t\tcommit_list_insert(sent_tips.items[i], &bases);\n      +\t\ttips_reachable_from_bases(the_repository,\n      +\t\t\t\t\t bases, src_commits.items,\n     -+\t\t\t\t\t src_commits.nr, TMP_MARK);\n     ++\t\t\t\t\t src_commits.nr, TMP_MARK,\n     ++\t\t\t\t\t TIPS_REACHABLE_PQ);\n      +\t\tcommit_list_free(bases);\n       \n       \t\tfor_each_string_list_item(item, &src_tag) {\n     @@ t/helper/test-reach.c: int cmd__reach(int ac, const char **av)\n      -\t\t\t\t    oid_to_hex(&list->item->object.oid));\n      -\t\t\tcount++;\n      -\t\t}\n     -+\t} else if (!strcmp(av[1], \"tips_reachable_from_bases\")) {\n     ++\t} else if (!strcmp(av[1], \"tips_reachable_from_bases\") ||\n     ++\t\t   !strcmp(av[1], \"tips_reachable_from_bases_pq\")) {\n     ++\t\tenum tips_reachable_mode mode =\n     ++\t\t\t!strcmp(av[1], \"tips_reachable_from_bases_pq\")\n     ++\t\t\t? TIPS_REACHABLE_PQ : TIPS_REACHABLE_DFS;\n      +\t\tstruct commit_list *bases = NULL;\n      +\t\tstruct commit_list *result = NULL;\n      +\n     @@ t/helper/test-reach.c: int cmd__reach(int ac, const char **av)\n      +\t\t\tcommit_list_insert(X_stack.items[i], &bases);\n      +\t\ttips_reachable_from_bases(the_repository,\n      +\t\t\t\t\t bases, Y_stack.items,\n     -+\t\t\t\t\t Y_stack.nr, TMP_MARK);\n     ++\t\t\t\t\t Y_stack.nr, TMP_MARK,\n     ++\t\t\t\t\t mode);\n      +\t\tcommit_list_free(bases);\n      +\n      +\t\tprintf(\"tips_reachable_from_bases(X,Y)\\n\");\n     @@ t/t6600-test-reach.sh: test_expect_success 'get_reachable_subset:all' '\n       \t\t\t      commit-5-6 | sort\n       \t) >expect &&\n      -\ttest_all_modes get_reachable_subset\n     -+\ttest_all_modes tips_reachable_from_bases\n     ++\ttest_all_modes tips_reachable_from_bases &&\n     ++\ttest_all_modes tips_reachable_from_bases_pq\n       '\n       \n      -test_expect_success 'get_reachable_subset:some' '\n     @@ t/t6600-test-reach.sh: test_expect_success 'get_reachable_subset:some' '\n       \t\t\t      commit-1-7 | sort\n       \t) >expect &&\n      -\ttest_all_modes get_reachable_subset\n     -+\ttest_all_modes tips_reachable_from_bases\n     ++\ttest_all_modes tips_reachable_from_bases &&\n     ++\ttest_all_modes tips_reachable_from_bases_pq\n       '\n       \n      -test_expect_success 'get_reachable_subset:none' '\n     @@ t/t6600-test-reach.sh: test_expect_success 'get_reachable_subset:none' '\n      -\techo \"get_reachable_subset(X,Y)\" >expect &&\n      -\ttest_all_modes get_reachable_subset\n      +\techo \"tips_reachable_from_bases(X,Y)\" >expect &&\n     -+\ttest_all_modes tips_reachable_from_bases\n     ++\ttest_all_modes tips_reachable_from_bases &&\n     ++\ttest_all_modes tips_reachable_from_bases_pq\n       '\n       \n       test_expect_success 'for-each-ref ahead-behind:linear' '\n     +@@ t/t6600-test-reach.sh: test_expect_success 'for-each-ref merged:duplicate at min generation' '\n     + \t\t--format=\"%(refname)\" --stdin\n     + '\n     + \n     ++test_expect_success 'for-each-ref merged:all reachable commits' '\n     ++\tfor x in $(test_seq 1 10)\n     ++\tdo\n     ++\t\tfor y in $(test_seq 1 10)\n     ++\t\tdo\n     ++\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n     ++\t\tdone\n     ++\tdone >input &&\n     ++\tfor x in $(test_seq 1 5)\n     ++\tdo\n     ++\t\tfor y in $(test_seq 1 5)\n     ++\t\tdo\n     ++\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n     ++\t\tdone\n     ++\tdone | sort >expect &&\n     ++\trun_all_modes git for-each-ref --merged=commit-5-5 \\\n     ++\t\t--format=\"%(refname)\" --stdin\n     ++'\n     ++\n     ++test_expect_success 'for-each-ref merged:all reachable, multibase' '\n     ++\tfor x in $(test_seq 1 10)\n     ++\tdo\n     ++\t\tfor y in $(test_seq 1 10)\n     ++\t\tdo\n     ++\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n     ++\t\tdone\n     ++\tdone >input &&\n     ++\tfor x in $(test_seq 1 10)\n     ++\tdo\n     ++\t\tfor y in $(test_seq 1 10)\n     ++\t\tdo\n     ++\t\t\tif { test $x -le 3 && test $y -le 7; } ||\n     ++\t\t\t   { test $x -le 7 && test $y -le 3; }\n     ++\t\t\tthen\n     ++\t\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n     ++\t\t\tfi\n     ++\t\tdone\n     ++\tdone | sort >expect &&\n     ++\trun_all_modes git for-each-ref \\\n     ++\t\t--merged=commit-3-7 \\\n     ++\t\t--merged=commit-7-3 \\\n     ++\t\t--format=\"%(refname)\" --stdin\n     ++'\n     ++\n     + # For get_branch_base_for_tip, we only care about\n     + # first-parent history. Here is the test graph with\n     + # second parents removed:\n\n\n commit-reach.c        | 131 +++++++++++-------------------------------\n commit-reach.h        |  19 ++----\n ref-filter.c          |   2 +-\n remote.c              |  20 +++----\n t/helper/test-reach.c |  44 +++++++-------\n t/t6600-test-reach.sh |  65 ++++++++++++++++++---\n 6 files changed, 129 insertions(+), 152 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 5df471a313..1cad7b211e 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1013,79 +1013,6 @@ int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \treturn result;\n }\n \n-struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,\n-\t\t\t\t\t struct commit **to, size_t nr_to,\n-\t\t\t\t\t unsigned int reachable_flag)\n-{\n-\tstruct commit **item;\n-\tstruct commit *current;\n-\tstruct commit_list *found_commits = NULL;\n-\tstruct commit **to_last = to + nr_to;\n-\tstruct commit **from_last = from + nr_from;\n-\ttimestamp_t min_generation = GENERATION_NUMBER_INFINITY;\n-\tint num_to_find = 0;\n-\n-\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n-\n-\tfor (item = to; item < to_last; item++) {\n-\t\ttimestamp_t generation;\n-\t\tstruct commit *c = *item;\n-\n-\t\trepo_parse_commit(the_repository, c);\n-\t\tgeneration = commit_graph_generation(c);\n-\t\tif (generation < min_generation)\n-\t\t\tmin_generation = generation;\n-\n-\t\tif (!(c->object.flags & PARENT1)) {\n-\t\t\tc->object.flags |= PARENT1;\n-\t\t\tnum_to_find++;\n-\t\t}\n-\t}\n-\n-\tfor (item = from; item < from_last; item++) {\n-\t\tstruct commit *c = *item;\n-\t\tif (!(c->object.flags & PARENT2)) {\n-\t\t\tc->object.flags |= PARENT2;\n-\t\t\trepo_parse_commit(the_repository, c);\n-\n-\t\t\tprio_queue_put(&queue, *item);\n-\t\t}\n-\t}\n-\n-\twhile (num_to_find && (current = prio_queue_get(&queue)) != NULL) {\n-\t\tstruct commit_list *parents;\n-\n-\t\tif (current->object.flags & PARENT1) {\n-\t\t\tcurrent->object.flags &= ~PARENT1;\n-\t\t\tcurrent->object.flags |= reachable_flag;\n-\t\t\tcommit_list_insert(current, &found_commits);\n-\t\t\tnum_to_find--;\n-\t\t}\n-\n-\t\tfor (parents = current->parents; parents; parents = parents->next) {\n-\t\t\tstruct commit *p = parents->item;\n-\n-\t\t\trepo_parse_commit(the_repository, p);\n-\n-\t\t\tif (commit_graph_generation(p) < min_generation)\n-\t\t\t\tcontinue;\n-\n-\t\t\tif (p->object.flags & PARENT2)\n-\t\t\t\tcontinue;\n-\n-\t\t\tp->object.flags |= PARENT2;\n-\t\t\tprio_queue_put(&queue, p);\n-\t\t}\n-\t}\n-\n-\tclear_prio_queue(&queue);\n-\n-\tclear_commit_marks_many(nr_to, to, PARENT1);\n-\tclear_commit_marks_many(nr_from, from, PARENT2);\n-\n-\treturn found_commits;\n-}\n-\n define_commit_slab(bit_arrays, struct bitmap *);\n static struct bit_arrays bit_arrays;\n \n@@ -1212,22 +1139,26 @@ static int compare_commit_and_index_by_generation(const void *va, const void *vb\n void tips_reachable_from_bases(struct repository *r,\n \t\t\t       struct commit_list *bases,\n \t\t\t       struct commit **tips, size_t tips_nr,\n-\t\t\t       int mark)\n+\t\t\t       int mark, enum tips_reachable_mode mode)\n {\n \tstruct commit_and_index *commits;\n+\tstruct commit_list *p;\n+\tstruct commit *c;\n \tsize_t min_generation_index = 0;\n \ttimestamp_t min_generation;\n-\tstruct commit_list *stack = NULL;\n+\tstruct prio_queue queue = { NULL };\n \n \tif (!bases || !tips || !tips_nr)\n \t\treturn;\n \n \t/*\n-\t * Do a depth-first search starting at 'bases' to search for the\n-\t * tips. Stop at the lowest (un-found) generation number. When\n-\t * finding the lowest commit, increase the minimum generation\n-\t * number to the next lowest (un-found) generation number.\n+\t * Search starting at 'bases' looking for the tips. Stop at the\n+\t * lowest un-found generation number, raising the floor as tips\n+\t * are found. Use DFS by default; with TIPS_REACHABLE_PQ,\n+\t * use a priority queue ordered by generation then commit date.\n \t */\n+\tif (mode == TIPS_REACHABLE_PQ)\n+\t\tqueue.compare = compare_commits_by_gen_then_commit_date;\n \n \tCALLOC_ARRAY(commits, tips_nr);\n \n@@ -1245,14 +1176,19 @@ void tips_reachable_from_bases(struct repository *r,\n \n \twhile (bases) {\n \t\trepo_parse_commit(r, bases->item);\n-\t\tcommit_list_insert(bases->item, &stack);\n+\t\tbases->item->object.flags |= SEEN;\n+\t\tprio_queue_put(&queue, bases->item);\n \t\tbases = bases->next;\n \t}\n \n-\twhile (stack) {\n-\t\tint explored_all_parents = 1;\n-\t\tstruct commit_list *p;\n-\t\tstruct commit *c = stack->item;\n+\twhile ((c = prio_queue_get(&queue))) {\n+\t\tstruct commit *first_parent = NULL;\n+\n+\t\trepo_parse_commit(r, c);\n+\n+\t\t/* Skip if below the current generation floor. */\n+\t\tif (commit_graph_generation(c) < min_generation)\n+\t\t\tcontinue;\n \n \t\t/* Does it match any of our tips? */\n \t\t{\n@@ -1276,25 +1212,26 @@ void tips_reachable_from_bases(struct repository *r,\n \t\t}\n \n \t\tfor (p = c->parents; p; p = p->next) {\n-\t\t\trepo_parse_commit(r, p->item);\n-\n \t\t\t/* Have we already explored this parent? */\n \t\t\tif (p->item->object.flags & SEEN)\n \t\t\t\tcontinue;\n \n-\t\t\t/* Is it below the current minimum generation? */\n-\t\t\tif (commit_graph_generation(p->item) < min_generation)\n-\t\t\t\tcontinue;\n-\n \t\t\t/* Ok, we will explore from here on. */\n \t\t\tp->item->object.flags |= SEEN;\n-\t\t\texplored_all_parents = 0;\n-\t\t\tcommit_list_insert(p->item, &stack);\n-\t\t\tbreak;\n+\t\t\t/* Parse before pushing in PQ mode for ordering. */\n+\t\t\tif (mode == TIPS_REACHABLE_PQ)\n+\t\t\t\trepo_parse_commit(r, p->item);\n+\t\t\tif (!first_parent)\n+\t\t\t\tfirst_parent = p->item;\n+\t\t\telse\n+\t\t\t\tprio_queue_put(&queue, p->item);\n \t\t}\n-\n-\t\tif (explored_all_parents)\n-\t\t\tpop_commit(&stack);\n+\t\t/*\n+\t\t * Add the first parent last so that it is on top of\n+\t\t * the LIFO queue, maintaining first-parent DFS order.\n+\t\t */\n+\t\tif (first_parent)\n+\t\t\tprio_queue_put(&queue, first_parent);\n \t}\n \n done:\n@@ -1302,7 +1239,7 @@ done:\n \t\tcommits[i].commit->object.flags &= ~RESULT;\n \tfree(commits);\n \trepo_clear_commit_marks(r, SEEN);\n-\tcommit_list_free(stack);\n+\tclear_prio_queue(&queue);\n }\n \n /*\ndiff --git a/commit-reach.h b/commit-reach.h\nindex 3f3a563d8a..71e60d727a 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -96,19 +96,6 @@ int can_all_from_reach_with_flag(struct object_array *from,\n int can_all_from_reach(struct commit_list *from, struct commit_list *to,\n \t\t       int commit_date_cutoff);\n \n-\n-/*\n- * Return a list of commits containing the commits in the 'to' array\n- * that are reachable from at least one commit in the 'from' array.\n- * Also add the given 'flag' to each of the commits in the returned list.\n- *\n- * This method uses the PARENT1 and PARENT2 flags during its operation,\n- * so be sure these flags are not set before calling the method.\n- */\n-struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,\n-\t\t\t\t\t struct commit **to, size_t nr_to,\n-\t\t\t\t\t unsigned int reachable_flag);\n-\n struct ahead_behind_count {\n \t/**\n \t * As input, the *_index members indicate which positions in\n@@ -144,10 +131,14 @@ void ahead_behind(struct repository *r,\n  * For all tip commits, add 'mark' to their flags if and only if they\n  * are reachable from one of the commits in 'bases'.\n  */\n+enum tips_reachable_mode {\n+\tTIPS_REACHABLE_DFS,\n+\tTIPS_REACHABLE_PQ,\n+};\n void tips_reachable_from_bases(struct repository *r,\n \t\t\t       struct commit_list *bases,\n \t\t\t       struct commit **tips, size_t tips_nr,\n-\t\t\t       int mark);\n+\t\t\t       int mark, enum tips_reachable_mode mode);\n \n /*\n  * Given a 'tip' commit and a list potential 'bases', return the index 'i' that\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 1da4c0e60d..9c8896d347 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -3157,7 +3157,7 @@ static void reach_filter(struct ref_array *array,\n \ttips_reachable_from_bases(the_repository,\n \t\t\t\t  *check_reachable,\n \t\t\t\t  to_clear, array->nr,\n-\t\t\t\t  UNINTERESTING);\n+\t\t\t\t  UNINTERESTING, TIPS_REACHABLE_DFS);\n \n \told_nr = array->nr;\n \tarray->nr = 0;\ndiff --git a/remote.c b/remote.c\nindex 00723b385e..0324c25743 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -1459,9 +1459,8 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t * sent to the other side.\n \t */\n \tif (sent_tips.nr) {\n-\t\tconst int reachable_flag = 1;\n-\t\tstruct commit_list *found_commits;\n \t\tstruct commit_stack src_commits = COMMIT_STACK_INIT;\n+\t\tstruct commit_list *bases = NULL;\n \n \t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *ref = item->util;\n@@ -1479,11 +1478,13 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\tcommit_stack_push(&src_commits, commit);\n \t\t}\n \n-\t\tfound_commits = get_reachable_subset(sent_tips.items,\n-\t\t\t\t\t\t     sent_tips.nr,\n-\t\t\t\t\t\t     src_commits.items,\n-\t\t\t\t\t\t     src_commits.nr,\n-\t\t\t\t\t\t     reachable_flag);\n+\t\tfor (size_t i = 0; i < sent_tips.nr; i++)\n+\t\t\tcommit_list_insert(sent_tips.items[i], &bases);\n+\t\ttips_reachable_from_bases(the_repository,\n+\t\t\t\t\t bases, src_commits.items,\n+\t\t\t\t\t src_commits.nr, TMP_MARK,\n+\t\t\t\t\t TIPS_REACHABLE_PQ);\n+\t\tcommit_list_free(bases);\n \n \t\tfor_each_string_list_item(item, &src_tag) {\n \t\t\tstruct ref *dst_ref;\n@@ -1503,7 +1504,7 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t\t * Is this tag, which they do not have, reachable from\n \t\t\t * any of the commits we are sending?\n \t\t\t */\n-\t\t\tif (!(commit->object.flags & reachable_flag))\n+\t\t\tif (!(commit->object.flags & TMP_MARK))\n \t\t\t\tcontinue;\n \n \t\t\t/* Add it in */\n@@ -1513,9 +1514,8 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds\n \t\t}\n \n \t\tclear_commit_marks_many(src_commits.nr, src_commits.items,\n-\t\t\t\t\treachable_flag);\n+\t\t\t\t\tTMP_MARK);\n \t\tcommit_stack_clear(&src_commits);\n-\t\tcommit_list_free(found_commits);\n \t}\n \n \tstring_list_clear(&src_tag, 0);\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 5d86a96c17..66ee35e70d 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -7,6 +7,7 @@\n #include \"hex.h\"\n #include \"object-name.h\"\n #include \"ref-filter.h\"\n+#include \"revision.h\"\n #include \"setup.h\"\n #include \"string-list.h\"\n #include \"tag.h\"\n@@ -149,30 +150,31 @@ int cmd__reach(int ac, const char **av)\n \n \t\tprintf(\"%s(_,A,X,_):%d\\n\", av[1], commit_contains(&filter, A, X, &cache));\n \t\tclear_contains_cache(&cache);\n-\t} else if (!strcmp(av[1], \"get_reachable_subset\")) {\n-\t\tconst int reachable_flag = 1;\n-\t\tint count = 0;\n-\t\tstruct commit_list *current;\n-\t\tstruct commit_list *list = get_reachable_subset(X_stack.items, X_stack.nr,\n-\t\t\t\t\t\t\t\tY_stack.items, Y_stack.nr,\n-\t\t\t\t\t\t\t\treachable_flag);\n-\t\tprintf(\"get_reachable_subset(X,Y)\\n\");\n-\t\tfor (current = list; current; current = current->next) {\n-\t\t\tif (!(list->item->object.flags & reachable_flag))\n-\t\t\t\tdie(_(\"commit %s is not marked reachable\"),\n-\t\t\t\t    oid_to_hex(&list->item->object.oid));\n-\t\t\tcount++;\n-\t\t}\n+\t} else if (!strcmp(av[1], \"tips_reachable_from_bases\") ||\n+\t\t   !strcmp(av[1], \"tips_reachable_from_bases_pq\")) {\n+\t\tenum tips_reachable_mode mode =\n+\t\t\t!strcmp(av[1], \"tips_reachable_from_bases_pq\")\n+\t\t\t? TIPS_REACHABLE_PQ : TIPS_REACHABLE_DFS;\n+\t\tstruct commit_list *bases = NULL;\n+\t\tstruct commit_list *result = NULL;\n+\n+\t\tfor (size_t i = 0; i < X_stack.nr; i++)\n+\t\t\tcommit_list_insert(X_stack.items[i], &bases);\n+\t\ttips_reachable_from_bases(the_repository,\n+\t\t\t\t\t bases, Y_stack.items,\n+\t\t\t\t\t Y_stack.nr, TMP_MARK,\n+\t\t\t\t\t mode);\n+\t\tcommit_list_free(bases);\n+\n+\t\tprintf(\"tips_reachable_from_bases(X,Y)\\n\");\n \t\tfor (size_t i = 0; i < Y_stack.nr; i++) {\n-\t\t\tif (Y_stack.items[i]->object.flags & reachable_flag)\n-\t\t\t\tcount--;\n+\t\t\tif (Y_stack.items[i]->object.flags & TMP_MARK)\n+\t\t\t\tcommit_list_insert(Y_stack.items[i], &result);\n \t\t}\n+\t\tprint_sorted_commit_ids(result);\n \n-\t\tif (count < 0)\n-\t\t\tdie(_(\"too many commits marked reachable\"));\n-\n-\t\tprint_sorted_commit_ids(list);\n-\t\tcommit_list_free(list);\n+\t\tclear_commit_marks_many(Y_stack.nr, Y_stack.items, TMP_MARK);\n+\t\tcommit_list_free(result);\n \t}\n \n \tobject_array_clear(&X_obj);\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b5b314e570..b736d893d5 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -391,7 +391,7 @@ test_expect_success 'rev-list: symmetric difference topo-order' '\n \trun_all_modes git rev-list --topo-order commit-3-8...commit-6-6\n '\n \n-test_expect_success 'get_reachable_subset:all' '\n+test_expect_success 'tips_reachable_from_bases:all' '\n \tcat >input <<-\\EOF &&\n \tX:commit-9-1\n \tX:commit-8-3\n@@ -403,15 +403,16 @@ test_expect_success 'get_reachable_subset:all' '\n \tY:commit-5-6\n \tEOF\n \t(\n-\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\techo \"tips_reachable_from_bases(X,Y)\" &&\n \t\tgit rev-parse commit-3-3 \\\n \t\t\t      commit-1-7 \\\n \t\t\t      commit-5-6 | sort\n \t) >expect &&\n-\ttest_all_modes get_reachable_subset\n+\ttest_all_modes tips_reachable_from_bases &&\n+\ttest_all_modes tips_reachable_from_bases_pq\n '\n \n-test_expect_success 'get_reachable_subset:some' '\n+test_expect_success 'tips_reachable_from_bases:some' '\n \tcat >input <<-\\EOF &&\n \tX:commit-9-1\n \tX:commit-8-3\n@@ -422,14 +423,15 @@ test_expect_success 'get_reachable_subset:some' '\n \tY:commit-5-6\n \tEOF\n \t(\n-\t\techo \"get_reachable_subset(X,Y)\" &&\n+\t\techo \"tips_reachable_from_bases(X,Y)\" &&\n \t\tgit rev-parse commit-3-3 \\\n \t\t\t      commit-1-7 | sort\n \t) >expect &&\n-\ttest_all_modes get_reachable_subset\n+\ttest_all_modes tips_reachable_from_bases &&\n+\ttest_all_modes tips_reachable_from_bases_pq\n '\n \n-test_expect_success 'get_reachable_subset:none' '\n+test_expect_success 'tips_reachable_from_bases:none' '\n \tcat >input <<-\\EOF &&\n \tX:commit-9-1\n \tX:commit-8-3\n@@ -439,8 +441,9 @@ test_expect_success 'get_reachable_subset:none' '\n \tY:commit-7-6\n \tY:commit-2-8\n \tEOF\n-\techo \"get_reachable_subset(X,Y)\" >expect &&\n-\ttest_all_modes get_reachable_subset\n+\techo \"tips_reachable_from_bases(X,Y)\" >expect &&\n+\ttest_all_modes tips_reachable_from_bases &&\n+\ttest_all_modes tips_reachable_from_bases_pq\n '\n \n test_expect_success 'for-each-ref ahead-behind:linear' '\n@@ -657,6 +660,50 @@ test_expect_success 'for-each-ref merged:duplicate at min generation' '\n \t\t--format=\"%(refname)\" --stdin\n '\n \n+test_expect_success 'for-each-ref merged:all reachable commits' '\n+\tfor x in $(test_seq 1 10)\n+\tdo\n+\t\tfor y in $(test_seq 1 10)\n+\t\tdo\n+\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n+\t\tdone\n+\tdone >input &&\n+\tfor x in $(test_seq 1 5)\n+\tdo\n+\t\tfor y in $(test_seq 1 5)\n+\t\tdo\n+\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n+\t\tdone\n+\tdone | sort >expect &&\n+\trun_all_modes git for-each-ref --merged=commit-5-5 \\\n+\t\t--format=\"%(refname)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref merged:all reachable, multibase' '\n+\tfor x in $(test_seq 1 10)\n+\tdo\n+\t\tfor y in $(test_seq 1 10)\n+\t\tdo\n+\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n+\t\tdone\n+\tdone >input &&\n+\tfor x in $(test_seq 1 10)\n+\tdo\n+\t\tfor y in $(test_seq 1 10)\n+\t\tdo\n+\t\t\tif { test $x -le 3 && test $y -le 7; } ||\n+\t\t\t   { test $x -le 7 && test $y -le 3; }\n+\t\t\tthen\n+\t\t\t\techo \"refs/heads/commit-$x-$y\" || return 1\n+\t\t\tfi\n+\t\tdone\n+\tdone | sort >expect &&\n+\trun_all_modes git for-each-ref \\\n+\t\t--merged=commit-3-7 \\\n+\t\t--merged=commit-7-3 \\\n+\t\t--format=\"%(refname)\" --stdin\n+'\n+\n # For get_branch_base_for_tip, we only care about\n # first-parent history. Here is the test graph with\n # second parents removed:\n\nbase-commit: 1ff279f3404a482a83fb04c7457e41ab26884aea\n-- \ngitgitgadget\n"},{"id":"545267","messageId":"ffaf26b1-c55e-43c7-84b6-f810a54f7717@gmail.com","threadId":"65780","inReplyTo":"pull.2144.v2.git.1781178567862.gitgitgadget@gmail.com","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-11T12:57:19Z","receivedAt":"2026-06-11T12:57:21Z","isPatch":true,"body":"On 6/11/2026 7:49 AM, Kristofer Karlsson via GitGitGadget wrote:\n> From: Kristofer Karlsson <krka@spotify.com>\n\n>      * Added PQ mode to the existing test-reach tests so both DFS and PQ\n>        paths are exercised by the test suite.\n\nThis is a substantial change that I don't think is merited. I\nthink that this makes the point of your change moot: we essentially\nhave two implementations in one complicated method instead of two\nimplementations that have different performance characteristics.\n\nI'd rather leave the code as-is than take this complication. I don't\nthink your commit message justifies the merging of these\nimplementations, either.\n\nMoreover, I thought the previous patch was fine, it just needed better\nawareness of the performance implications of the change. Specifically,\nit could be a regression for large repos without a commit-graph file\nwhile simultaneously potentially being a performance boost for large\nrepos _with_ a commit-graph file.\n\n_If_ we were to go this direction, then it should be two patches, with\nthe first introducing the new mode and testing it. The second patch\ncould change the callers of get_reachable_subset() and delete that\ncode.\n\nFinally, a commentary: You seem to have a habit of responding to\nreview feedback only through new patch versions, but I'd rather see\nsome thoughts in the discussion thread as direct replies to the review,\nespecially if you think you will change direction like this. Saying\nsomething like \"Maybe I should update the method to have two walk modes\"\nin a reply would have given me an opportunity to respond and perhaps\navoided a new version that went in this direction.\n\nThanks,\n-Stolee\n\n"},{"id":"545283","messageId":"CAL71e4Nn8Lk87A5=t1Wu=SStQqzmFqad+pcyOw_Fu-PLpRMq_g@mail.gmail.com","threadId":"65780","inReplyTo":"ffaf26b1-c55e-43c7-84b6-f810a54f7717@gmail.com","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-11T13:52:21Z","receivedAt":"2026-06-11T13:52:33Z","isPatch":true,"body":"On Thu, 11 Jun 2026 at 14:57, Derrick Stolee <stolee@gmail.com> wrote:\n> Finally, a commentary: You seem to have a habit of responding to\n> review feedback only through new patch versions, but I'd rather see\n> some thoughts in the discussion thread as direct replies to the review,\n> especially if you think you will change direction like this. Saying\n> something like \"Maybe I should update the method to have two walk modes\"\n> in a reply would have given me an opportunity to respond and perhaps\n> avoided a new version that went in this direction.\n\nThat's fair, I apologize both for jumping ahead too quickly with a new\npatch and also for evolving it into multiple logical changes\n(both code removal and complex refactoring).\n\nI will be more mindful going forward about letting the discussion\nsettle more before submitting followup patches.\n\nI have no strong opinion on how to proceed - either park/abandon this\nor go with v1 as-is. I think you're right that having two modes within\ntips_reachable_from_bases is reducing the win here unless the mode is\ntruly seamless but the abstraction does leak through a bit.\n\nThanks,\nKristofer\n"},{"id":"545285","messageId":"3a3d1dc4-341f-4276-a1ee-2972a885db84@gmail.com","threadId":"65780","inReplyTo":"CAL71e4Nn8Lk87A5=t1Wu=SStQqzmFqad+pcyOw_Fu-PLpRMq_g@mail.gmail.com","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2026-06-11T14:51:41Z","receivedAt":"2026-06-11T14:51:43Z","isPatch":true,"body":"On 6/11/2026 9:52 AM, Kristofer Karlsson wrote:\n> On Thu, 11 Jun 2026 at 14:57, Derrick Stolee <stolee@gmail.com> wrote:\n>> Finally, a commentary: You seem to have a habit of responding to\n>> review feedback only through new patch versions, but I'd rather see\n>> some thoughts in the discussion thread as direct replies to the review,\n>> especially if you think you will change direction like this. Saying\n>> something like \"Maybe I should update the method to have two walk modes\"\n>> in a reply would have given me an opportunity to respond and perhaps\n>> avoided a new version that went in this direction.\n> \n> That's fair, I apologize both for jumping ahead too quickly with a new\n> patch and also for evolving it into multiple logical changes\n> (both code removal and complex refactoring).\n> \n> I will be more mindful going forward about letting the discussion\n> settle more before submitting followup patches.\n> \n> I have no strong opinion on how to proceed - either park/abandon this\n> or go with v1 as-is. I think you're right that having two modes within\n> tips_reachable_from_bases is reducing the win here unless the mode is\n> truly seamless but the abstraction does leak through a bit.\nI think that my biggest issue is that callers are needing to know\nsomething about the performance characteristics of each solution. It\nmay be better to keep the behavior completely internal: have the\nmethod decide which approach is better based on the information it\nhas. For instance: is the minimum generation number \"infinite\"? Then\nthe BFS is going to be better than the DFS approach. Such an approach\nwould make it clear why there is the complexity _and_ would improve\nboth callers in the right scenarios.\n\nYou were correct to find two methods that claimed to do the same\nthing, but we need to take time to consider the solutions based on\nall factors.\n\nThanks,\n-Stolee\n\n"},{"id":"545308","messageId":"xmqq7bo5nf31.fsf@gitster.g","threadId":"65780","inReplyTo":"ffaf26b1-c55e-43c7-84b6-f810a54f7717@gmail.com","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-11T17:48:18Z","receivedAt":"2026-06-11T17:48:20Z","isPatch":true,"body":"Derrick Stolee <stolee@gmail.com> writes:\n\n> Finally, a commentary: You seem to have a habit of responding to\n> review feedback only through new patch versions, but I'd rather see\n> some thoughts in the discussion thread as direct replies to the review,\n> especially if you think you will change direction like this. Saying\n> something like \"Maybe I should update the method to have two walk modes\"\n> in a reply would have given me an opportunity to respond and perhaps\n> avoided a new version that went in this direction.\n\nThanks for saying this.  \n\nI haven't (yet) found it in my exchange with Kristofer, but I did\nfind similar irritations during review sessions with other\ncontributors.\n\nI wonder if we should talk about it in the SubmittingPatches and/or\nMyFirstContribution document?\n"},{"id":"545357","messageId":"aivQv5FkTEWDn22i@wyuan.org","threadId":"65780","inReplyTo":"xmqq7bo5nf31.fsf@gitster.g","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Weijie Yuan","fromEmail":"wy@wyuan.org","sentAt":"2026-06-12T09:26:23Z","receivedAt":"2026-06-12T09:26:39Z","isPatch":true,"body":"On Thu, Jun 11, 2026 at 10:48:18AM -0700, Junio C Hamano wrote:\n> I wonder if we should talk about it in the SubmittingPatches and/or\n> MyFirstContribution document?\n\nHi, I think it might be a good idea to cover these details in\nMyFirstContribution, then cross-reference them from the part of\nSubmittingPatches that discusses sending a new version.\n\nMore specifically, I think these details could fit around steps 3 and 4\nof \"A typical life cycle of a patch series\" in SubmittingPatches,\nstarting around line 54. That section may need some reworking of the\nexisting wording, rather than just an additive change.\n\nAlso, for the part about sending a new version, I wonder whether it\nwould be better to summarize and fold in Patrick's explanation here,\nthank you Patrick:\n\n---\n\nFrom: Patrick Steinhardt <ps@pks.im>\nMessage-ID: <aietF4BX1Ewt3cpG@pks.im>\n\n> By the way, how long should I wait before sending new versions of my\n> patches? I have 4 outstanding at the moment.\n\nI typically aim to send at most one version per day per patch series.\nThis avoids that you're \"flooding\" the mailing list with too many\nversions of the same series, allows you to address feedback from\nmultiple folks in batches, and it gives you enough time to think about\nthe feedback without having to rush anything.\n\nWhether I actually do end up sending a series depends on a couple of\nfactors:\n\n  - How big is the series? The bigger it is the more time I give folks\n    to perform reviews.\n\n  - How substantial were the reviews you received? Is it just a couple\n    of small typos? Then it probably makes sense to wait one or two more\n    days to get some more involved reviews. Is it something that\n    requires signifciant rework? Then I'd send out soon so that others\n    don't review a patch series that will change significantly anyway.\n\n  - How close to being merged is the series? The closer it is the less\n    substantial the reviews will (hopefully) get, so it makes sense to\n    reroll a bit faster even if you only received minor feedback.\n\nSo there isn't really a golden rule to follow here, but a lot of this\ndepends on gut feeling. You probably won't have that feeling yet when\nstarting out in a new project, but that's fine. In case we see that\nbehaviour doesn't quite match the norm we'll typically give a hint that\nthe contributor should slow down or maybe send a new iteration.\n\nPatrick\n\n---\n\nPatrick's point may be beyond the scope of this thread, so I only\nmention it as an aside. Maybe these could be part of the same series.\n\nThanks.\n"},{"id":"545385","messageId":"xmqqecibizwz.fsf@gitster.g","threadId":"65780","inReplyTo":"aivQv5FkTEWDn22i@wyuan.org","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2026-06-12T14:41:48Z","receivedAt":"2026-06-12T14:41:51Z","isPatch":true,"body":"Weijie Yuan <wy@wyuan.org> writes:\n\n> On Thu, Jun 11, 2026 at 10:48:18AM -0700, Junio C Hamano wrote:\n>> I wonder if we should talk about it in the SubmittingPatches and/or\n>> MyFirstContribution document?\n>\n> Hi, I think it might be a good idea to cover these details in\n> MyFirstContribution, then cross-reference them from the part of\n> SubmittingPatches that discusses sending a new version.\n\nSorry to be nitpicky, but the above is omitting too much from your\nquote.  \"it\" in \"talk about it\" is totally unclear to a reader who\nhaven't seen the message you are replying to.\n\n> Also, for the part about sending a new version, I wonder whether it\n> would be better to summarize and fold in Patrick's explanation here,\n> thank you Patrick:\n\nYup, that is a great example.\n\n> From: Patrick Steinhardt <ps@pks.im>\n> Message-ID: <aietF4BX1Ewt3cpG@pks.im>\n"},{"id":"545401","messageId":"aiww2oXXDQXk0dgu@wyuan.org","threadId":"65780","inReplyTo":"xmqqecibizwz.fsf@gitster.g","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Weijie Yuan","fromEmail":"wy@wyuan.org","sentAt":"2026-06-12T16:16:26Z","receivedAt":"2026-06-12T16:16:35Z","isPatch":true,"body":"On Fri, Jun 12, 2026 at 07:41:48AM -0700, Junio C Hamano wrote:\n> Weijie Yuan <wy@wyuan.org> writes:\n> \n> > On Thu, Jun 11, 2026 at 10:48:18AM -0700, Junio C Hamano wrote:\n> >> I wonder if we should talk about it in the SubmittingPatches and/or\n> >> MyFirstContribution document?\n> >\n> > Hi, I think it might be a good idea to cover these details in\n> > MyFirstContribution, then cross-reference them from the part of\n> > SubmittingPatches that discusses sending a new version.\n> \n> Sorry to be nitpicky, but the above is omitting too much from your\n> quote.  \"it\" in \"talk about it\" is totally unclear to a reader who\n> haven't seen the message you are replying to.\n\nOops, so sorry! You are not nitpicky at all, this is totally my\ncarelessness and fault. Sorry readers!\n\nThank you for catching this! It shows that I still need to really\nunderstand the previous patch I wrote, and put it into real practice:\n\n> It is usually helpful to trim away unrelated context, such as large\n> portions of the patch that are not being discussed, while _keeping\n> enough quoted text_ for readers to understand *what* you are\n> responding to.\n\nThank you! I'll immediately set a solid \"pre-reply\" hook in my .git\nfolder ;-)\n"},{"id":"545402","messageId":"aiwx8MnnI2qSRvtF@wyuan.org","threadId":"65780","inReplyTo":"aiww2oXXDQXk0dgu@wyuan.org","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Weijie Yuan","fromEmail":"wy@wyuan.org","sentAt":"2026-06-12T16:21:04Z","receivedAt":"2026-06-12T16:21:28Z","isPatch":true,"body":"On Sat, Jun 13, 2026 at 12:16:34AM +0800, Weijie Yuan wrote:\n> On Fri, Jun 12, 2026 at 07:41:48AM -0700, Junio C Hamano wrote:\n> > Weijie Yuan <wy@wyuan.org> writes:\n> > \n> > > On Thu, Jun 11, 2026 at 10:48:18AM -0700, Junio C Hamano wrote:\n> > >> I wonder if we should talk about it in the SubmittingPatches and/or\n> > >> MyFirstContribution document?\n> > >\n> > > Hi, I think it might be a good idea to cover these details in\n> > > MyFirstContribution, then cross-reference them from the part of\n> > > SubmittingPatches that discusses sending a new version.\n> > \n> > Sorry to be nitpicky, but the above is omitting too much from your\n> > quote.  \"it\" in \"talk about it\" is totally unclear to a reader who\n> > haven't seen the message you are replying to.\n> \n> Oops, so sorry! You are not nitpicky at all, this is totally my\n> carelessness and fault. Sorry readers!\n> \n> Thank you for catching this! It shows that I still need to really\n> understand the previous patch I wrote, and put it into real practice:\n> \n> > It is usually helpful to trim away unrelated context, such as large\n> > portions of the patch that are not being discussed, while _keeping\n> > enough quoted text_ for readers to understand *what* you are\n> > responding to.\n> \n> Thank you! I'll immediately set a solid \"pre-reply\" hook in my .git\n> folder ;-)\n\nSorry, here I mean setting a pre-reply hook to remind me how to do a\ngood quote when writting a reply mail :-)\n\nSorry for the unnecessary noise, and thank you.\n"},{"id":"545613","messageId":"CAL71e4P3Oq08xVPZ+dxQ8L5PKekPJN0RsL4pTicom1og7-1D=A@mail.gmail.com","threadId":"65780","inReplyTo":"xmqq7bo5nf31.fsf@gitster.g","subject":"Re: [PATCH v2] commit-reach: remove get_reachable_subset()","fromName":"Kristofer Karlsson","fromEmail":"krka@spotify.com","sentAt":"2026-06-15T20:58:22Z","receivedAt":"2026-06-15T20:58:34Z","isPatch":true,"body":"I think we should park or abandon this patch for now; I initially thought\nit would be a somewhat cheap win in code reduction but the risk of\nintroducing performance regressions for repos without commit graphs\nmeans it's not really worth the time investment and I don't want to\nadd more maintainer burden for tracking it.\n\nThanks for looking at it though, I appreciate it!\nKristofer\n\nOn Thu, 11 Jun 2026 at 19:48, Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Derrick Stolee <stolee@gmail.com> writes:\n>\n> > Finally, a commentary: You seem to have a habit of responding to\n> > review feedback only through new patch versions, but I'd rather see\n> > some thoughts in the discussion thread as direct replies to the review,\n> > especially if you think you will change direction like this. Saying\n> > something like \"Maybe I should update the method to have two walk modes\"\n> > in a reply would have given me an opportunity to respond and perhaps\n> > avoided a new version that went in this direction.\n>\n> Thanks for saying this.\n>\n> I haven't (yet) found it in my exchange with Kristofer, but I did\n> find similar irritations during review sessions with other\n> contributors.\n>\n> I wonder if we should talk about it in the SubmittingPatches and/or\n> MyFirstContribution document?\n"}]}