[PATCH 1/2] commit-graph: add trace2 instrumentation for generation DFS

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

From: Kristofer Karlsson <krka@spotify.com>

Add a step counter and trace2_data_intmax call to
compute_reachable_generation_numbers() to make the cost of
the generation number DFS observable.  This exposes a
regression introduced in 199d452758 (commit-graph: fix
"filling in" topological levels, 2025-04-07) where
incremental commit-graph writes re-walk the entire commit
ancestry instead of reading topo levels from lower graph
layers.

Add a test that demonstrates the problem: with a two-layer
split commit-graph, writing a new incremental layer for a
commit whose parent is in the base layer walks all the way
down to the root (7 steps for 5 base commits) instead of
reading the existing topo level and stopping immediately
(1 step).

Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
 commit-graph.c                |  5 +++++
 t/t5324-split-commit-graph.sh | 28 ++++++++++++++++++++++++++++
 2 files changed, 33 insertions(+)

diff --git a/commit-graph.c b/commit-graph.c
index 801471a098..4e39a048c4 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1653,6 +1653,7 @@ static void compute_reachable_generation_numbers(
 {
 	int i;
 	struct commit_list *list = NULL;
+	intmax_t steps = 0;
 
 	for (i = 0; i < info->commits->nr; i++) {
 		struct commit *c = info->commits->items[i];
@@ -1671,6 +1672,7 @@ static void compute_reachable_generation_numbers(
 			int all_parents_computed = 1;
 			timestamp_t max_gen = 0;
 
+			steps++;
 			for (parent = current->parents; parent; parent = parent->next) {
 				repo_parse_commit(info->r, parent->item);
 				gen = info->get_generation(parent->item, info->data);
@@ -1694,6 +1696,9 @@ static void compute_reachable_generation_numbers(
 			}
 		}
 	}
+
+	trace2_data_intmax("commit-graph", info->r,
+			   "generation-dfs-steps", steps);
 }
 
 static timestamp_t get_topo_level(struct commit *c, void *data)
diff --git a/t/t5324-split-commit-graph.sh b/t/t5324-split-commit-graph.sh
index 49a057cc2e..f9c57760f4 100755
--- a/t/t5324-split-commit-graph.sh
+++ b/t/t5324-split-commit-graph.sh
@@ -718,6 +718,34 @@ test_expect_success 'write generation data chunk when commit-graph chain is repl
 	)
 '
 
+test_expect_success 'incremental write reads topo levels from all layers' '
+	git init topo-from-lower &&
+	(
+		cd topo-from-lower &&
+
+		for i in $(test_seq 5)
+		do
+			test_commit base-$i || return 1
+		done &&
+		git commit-graph write --reachable &&
+
+		test_commit extra &&
+		git commit-graph write --reachable --split=no-merge &&
+
+		git checkout base-3 &&
+		test_commit new-branch &&
+
+		GIT_TRACE2_EVENT="$(pwd)/trace.txt" \
+			git commit-graph write --reachable --split=no-merge &&
+
+		# BUG: topo levels from lower graph layers are not
+		# propagated, so the DFS re-walks from base-3 down to
+		# the root (7 steps) instead of reading topo levels
+		# from the existing graph (1 step).
+		test_trace2_data commit-graph generation-dfs-steps 7 <trace.txt
+	)
+'
+
 test_expect_success 'temporary graph layer is discarded upon failure' '
 	git init layer-discard &&
 	(
-- 
gitgitgadget