* [PATCH v3 0/8] commit-reach: terminate merge-base walk when one side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:07 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson
In-Reply-To: <pull.2149.v2.git.1782303254.gitgitgadget@gmail.com>
commit-reach: terminate merge-base walk when one paint side is exhausted
Optimize paint_down_to_common() for merge-base queries that hit large
one-sided histories.
When the walk from one side reaches a commit with a very low generation
number that the other side never paints, the walk is forced to drain most of
the graph. A common trigger is a repository import that grafts a separate
history with its own root, but any merge that introduces a low-generation
commit never painted by the other side has the same effect.
A new merge-base candidate can only be discovered when exclusive PARENT1 and
PARENT2 paint meet. This series teaches paint_down_to_common() to stop as
soon as one side has no exclusive commits left in the queue; once one side
is exhausted, no further candidates can appear.
origin/HEAD o o PR HEAD
| |
(import) o :
/ \ /
| o merge-base
| |
: : (~2.5M commits)
| |
import root main root
In the RFC thread [1], Derrick Stolee provided a criss-cross counterexample
that sharpened the halt condition, and Elijah Newren independently
discovered the same optimization and shared an implementation in PR #2150
[2]. Patches 2-3 incorporate test cases from Elijah's branch.
This series implements the optimization only after the walk enters the
finite-generation region, where generation ordering guarantees that paint on
visited commits is final.
Patch layout:
1/8 Documentation/technical: add paint-down-to-common doc 2/8 t6600: add
test cases for side-exhaustion edge cases 3/8 t6099, t6600: add
side-exhaustion regression tests 4/8 commit-reach: add trace2
instrumentation to paint_down_to_common() 5/8 commit-reach: introduce struct
paint_state with per-side counters 6/8 commit-reach: remove unused
nonstale_queue dedup wrappers 7/8 commit-reach: terminate merge-base walk
when one paint side is exhausted 8/8 commit-reach: move min_generation check
into paint_queue_get()
Benchmarks
Step counts are deterministic (measured via trace2_data_intmax added in
patch 4). Wall-clock times are best-of-11 runs.
2.6M-commit monorepo with commit-graph:
steps wall-clock
merge-base --all (across import) 2143438 -> 3 3.67s -> 5ms
merge-base --all (1000 apart) 2692915 -> 1035 4.41s -> 7ms
merge-base --all (5000 apart) 2692915 -> 6401 4.45s -> 13ms
merge-base --all (HEAD vs import) 2698872 -> 45960 4.50s -> 79ms
merge-tree (across import) 2143438 -> 3 4.42s -> 11ms
git.git (88k commits, commit-graph):
steps wall-clock
merge-base --all v2.0.0 v2.55.0-rc1 72264 -> 44589 110ms -> 68ms
merge-base --all HEAD HEAD~1000 9891 -> 3828 18ms -> 10ms
merge-base --all HEAD HEAD~10000 72303 -> 41487 101ms -> 50ms
Changes since v2:
* New patch 8/8: moved the min_generation termination check and the
last_gen monotonicity assertion into paint_queue_get(), consolidating
halt conditions. commit_graph_generation() is now called once per
dequeued commit and shared across all checks.
* Widened the generation-monotonicity BUG assertion to fire
unconditionally, not only when min_generation is set. The side-exhaustion
optimization depends on correct generation ordering, so the assertion
should always be active. This is a behavior change: the BUG() now fires
for any generation ordering violation, regardless of the caller.
* Moved all halt conditions inside paint_queue_get() with the "pop first"
form: pop, check, then decrement counters. This keeps the optimization
commit's diff minimal (just inserting the new checks between pop and
decrement).
* Shortened the doc comment on paint_queue_get() to describe what it does
rather than how. Inline comments on each return NULL explain the specific
halt condition.
* Replaced the manual commit-graph setup in the step-count test with
run_all_modes, which now sets GIT_TRACE2_EVENT per mode and produces
trace-mode-{none,full,half,no-gdat}.txt files.
* Added a test_paint_down_steps helper for concise 4-mode step assertions
with diagnostic output on mismatch (prints "expected X, got Y" instead of
a silent grep failure).
* Added step-count assertions to the single-walk edge-case tests:
in_merge_bases_many:self, pending-stale, infinity-both-sides,
mixed-finite-infinity.
* Included step counts alongside wall-clock times in the benchmark tables.
Changes since v1:
* Reordered patches: documentation first (describing the existing
algorithm), tests before code changes, so they demonstrate passing with
old logic first.
* Dropped the ahead_behind decoupling patch. paint_state is now a NEW
struct alongside nonstale_queue instead of replacing it. ahead_behind()
is completely untouched.
* Removed nonstale_queue_put_dedup() and nonstale_queue_get_dedup() (dead
code after the conversion) in a separate commit.
* Renamed: struct paint_queue -> paint_state, field pq -> queue,
paint_count_add/remove -> paint_count_update (single function with signed
delta parameter).
* Split the old paint_count_transition (which handled both old and new
flags in one call) into separate remove/add calls with a signed delta.
This eliminates the need for the case 0 handler (which tracked "not in
the queue") and allows an exhaustive switch on (PARENT1 | PARENT2 |
STALE) that documents all valid flag combinations, with BUG() in default.
* Added trace2_data_intmax() instrumentation to report the number of
commits visited per paint walk (separate commit), with deterministic
step-count assertions in t6600.
* Expanded switch statements to multi-line format per .clang-format.
* Used !count style throughout instead of count == 0.
* Updated technical documentation alongside code changes.
[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] https://github.com/gitgitgadget/git/pull/2150
Elijah Newren (1):
t6600: add test cases for side-exhaustion edge cases
Kristofer Karlsson (7):
Documentation/technical: add paint-down-to-common doc
t6099, t6600: add side-exhaustion regression tests
commit-reach: add trace2 instrumentation to paint_down_to_common()
commit-reach: introduce struct paint_state with per-side counters
commit-reach: remove unused nonstale_queue dedup wrappers
commit-reach: terminate merge-base walk when one paint side is
exhausted
commit-reach: move min_generation check into paint_queue_get()
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 137 +++++++++++++
commit-reach.c | 147 ++++++++++----
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 ++++++++
t/t6600-test-reach.sh | 181 ++++++++++++++++--
7 files changed, 501 insertions(+), 49 deletions(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
base-commit: 6c3d7b73556db708feb3b16232fab1efc4353428
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/2149
Range-diff vs v2:
1: 19ed743bd1 = 1: 2593866bce Documentation/technical: add paint-down-to-common doc
2: 6151b8e0a3 = 2: 9efc084850 t6600: add test cases for side-exhaustion edge cases
3: 90f09ecb5c = 3: 14b0d86b93 t6099, t6600: add side-exhaustion regression tests
4: 6ade4df2ed ! 4: 2592264cda commit-reach: add trace2 instrumentation to paint_down_to_common()
@@ Commit message
Add a step counter and trace2_data_intmax() call so that the number
of commits visited during the paint walk is observable via
- GIT_TRACE2_PERF. This provides a way to measure the impact of
+ GIT_TRACE2_EVENT. This provides a way to measure the impact of
future optimizations without relying on wall-clock benchmarks alone.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
}
## t/t6600-test-reach.sh ##
-@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
- test_all_modes get_merge_bases_many
+@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
'
-+test_expect_success 'merge-base --all commit-walk steps' '
-+ test_when_finished rm -rf .git/objects/info/commit-graph \
-+ .git/objects/info/commit-graphs &&
-+ rm -rf .git/objects/info/commit-graph \
-+ .git/objects/info/commit-graphs &&
-+
-+ GIT_TRACE2_EVENT="$(pwd)/trace-none.txt" \
-+ git merge-base --all commit-9-9 commit-9-1 >actual &&
-+ test_trace2_data paint_down_to_common steps 81 <trace-none.txt &&
+ run_all_modes () {
+- test_when_finished rm -rf .git/objects/info/commit-graph &&
+- "$@" <input >actual &&
+- test_cmp expect actual &&
+- cp commit-graph-full .git/objects/info/commit-graph &&
+- "$@" <input >actual &&
+- test_cmp expect actual &&
+- cp commit-graph-half .git/objects/info/commit-graph &&
+- "$@" <input >actual &&
+- test_cmp expect actual &&
+- cp commit-graph-no-gdat .git/objects/info/commit-graph &&
+- "$@" <input >actual &&
+- test_cmp expect actual
++ graph=.git/objects/info/commit-graph &&
++ test_when_finished rm -rf "$graph" "${graph}s" &&
++ rm -f trace-mode-*.txt &&
+
-+ cp commit-graph-full .git/objects/info/commit-graph &&
-+ GIT_TRACE2_EVENT="$(pwd)/trace-full.txt" \
-+ git merge-base --all commit-9-9 commit-9-1 >actual &&
-+ test_trace2_data paint_down_to_common steps 80 <trace-full.txt &&
++ for mode in none full half no-gdat
++ do
++ rm -rf "$graph" "${graph}s" &&
++ cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
++ true &&
++ GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
++ "$@" <input >actual &&
++ test_cmp expect actual || return 1
++ done
+ }
+
+ test_all_modes () {
+ run_all_modes test-tool reach "$@"
+ }
+
++test_paint_down_steps () {
++ for mode in none full half no-gdat
++ do
++ test_trace2_data paint_down_to_common steps "$1" \
++ <"trace-mode-${mode}.txt" || return 1
++ shift
++ done
++}
+
-+ cp commit-graph-half .git/objects/info/commit-graph &&
-+ GIT_TRACE2_EVENT="$(pwd)/trace-half.txt" \
-+ git merge-base --all commit-9-9 commit-9-1 >actual &&
-+ test_trace2_data paint_down_to_common steps 81 <trace-half.txt
+ test_expect_success 'ref_newer:miss' '
+ cat >input <<-\EOF &&
+ A:commit-5-7
+@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:self' '
+ X:commit-6-8
+ EOF
+ echo "in_merge_bases_many(A,X):1" >expect &&
+- test_all_modes in_merge_bases_many
++ test_all_modes in_merge_bases_many &&
++ test_paint_down_steps 45 2 25 3
+ '
+
+ test_expect_success 'is_descendant_of:hit' '
+@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:pending-stale' '
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-B
+ } >expect &&
+- test_all_modes get_merge_bases_many
++ test_all_modes get_merge_bases_many &&
++ test_paint_down_steps 6 6 6 6
+ '
+
+ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse pi-B
+ } >expect &&
+- test_all_modes get_merge_bases_many
++ test_all_modes get_merge_bases_many &&
++ test_paint_down_steps 5 5 5 5
+ '
+
+ test_expect_success 'setup mixed finite/INFINITY topology' '
+@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-X
+ } >expect &&
+- test_all_modes get_merge_bases_many
++ test_all_modes get_merge_bases_many &&
++ test_paint_down_steps 3 3 3 3
+'
+
++test_expect_success 'merge-base --all commit-walk steps' '
++ >input &&
++ git rev-parse commit-9-1 >expect &&
++ run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
++ test_paint_down_steps 81 80 81 81
+ '
+
test_expect_success 'reduce_heads' '
- cat >input <<-\EOF &&
- X:commit-1-10
5: f24edd45f0 ! 5: e82e0c72b6 commit-reach: introduce struct paint_state with per-side counters
@@ Commit message
(max_nonstale). This is equivalent behavior -- both conditions
detect that no non-stale entries remain.
- The existing nonstale_queue is left in place for ahead_behind().
+ paint_queue_get() uses a "pop first" form: it dequeues a commit,
+ then checks the counters. This means the loop exits one iteration
+ earlier than the old code in some topologies (the popped stale
+ commit is never processed), so a few step counts drop by one.
- Step counts (via trace2 from the previous commit) are identical
- before and after this refactoring, confirming no behavioral change.
+ The existing nonstale_queue is left in place for ahead_behind().
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
+
+static struct commit *paint_queue_get(struct paint_state *state)
+{
-+ struct commit *commit;
++ struct commit *commit = prio_queue_get(&state->queue);
++
++ if (!commit)
++ return NULL;
++
++ commit->object.flags &= ~ENQUEUED;
+
+ if (!state->p1_count && !state->p2_count &&
+ !state->pending_merge_bases)
+ return NULL;
+
-+ commit = prio_queue_get(&state->queue);
-+ if (commit) {
-+ commit->object.flags &= ~ENQUEUED;
-+ paint_count_update(state, commit->object.flags, -1);
-+ }
++ paint_count_update(state, commit->object.flags, -1);
+ return commit;
+}
+
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
trace2_data_intmax("paint_down_to_common", r,
"steps", steps);
commit_list_sort_by_date(result);
+
+ ## t/t6600-test-reach.sh ##
+@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:pending-stale' '
+ git rev-parse ps-B
+ } >expect &&
+ test_all_modes get_merge_bases_many &&
+- test_paint_down_steps 6 6 6 6
++ test_paint_down_steps 5 5 5 5
+ '
+
+ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+ git rev-parse pi-B
+ } >expect &&
+ test_all_modes get_merge_bases_many &&
+- test_paint_down_steps 5 5 5 5
++ test_paint_down_steps 5 4 5 5
+ '
+
+ test_expect_success 'setup mixed finite/INFINITY topology' '
6: 8c72f01083 = 6: e6181bf3c1 commit-reach: remove unused nonstale_queue dedup wrappers
7: d84b932e5b ! 7: f3572a8a89 commit-reach: terminate merge-base walk when one paint side is exhausted
@@ Commit message
once the walk enters the finite-generation region where ordering
guarantees hold.
+ Widen the existing generation-monotonicity BUG assertion to fire
+ unconditionally, not only when min_generation is set. The
+ side-exhaustion optimization depends on correct generation ordering,
+ so the assertion should always be active.
+
Step counts measured with trace2 on git.git with commit-graph:
merge-base --all v2.0.0 v2.55.0-rc1:
@@ Documentation/technical/paint-down-to-common.adoc: existing candidates by provin
## commit-reach.c ##
@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
+ }
+ }
++/*
++ * Dequeue the next commit for the paint walk, or return NULL when
++ * no more merge bases can be discovered.
++ */
static struct commit *paint_queue_get(struct paint_state *state)
{
-- struct commit *commit;
-+ struct commit *commit = prio_queue_get(&state->queue);
+ struct commit *commit = prio_queue_get(&state->queue);
+@@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
+
+ commit->object.flags &= ~ENQUEUED;
- if (!state->p1_count && !state->p2_count &&
- !state->pending_merge_bases)
-+ if (!commit)
- return NULL;
-
-- commit = prio_queue_get(&state->queue);
-- if (commit) {
-- commit->object.flags &= ~ENQUEUED;
-- paint_count_update(state, commit->object.flags, -1);
-+ commit->object.flags &= ~ENQUEUED;
-+
+- return NULL;
+ if (!state->pending_merge_bases) {
++ /* only stale entries remain */
+ if (!state->p1_count && !state->p2_count)
+ return NULL;
-+ /*
-+ * Side exhaustion: a new merge-base can only form
-+ * when both PARENT1-only and PARENT2-only commits
-+ * remain in the queue. In the finite-generation
-+ * region the queue is ordered topologically, so
-+ * no future step can add paint to visited commits
-+ * and an exhausted side cannot reappear.
-+ */
++
++ /* one side is exhausted */
+ if ((!state->p1_count || !state->p2_count) &&
+ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ return NULL;
- }
-+
-+ paint_count_update(state, commit->object.flags, -1);
++ }
+
+ paint_count_update(state, commit->object.flags, -1);
return commit;
- }
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ timestamp_t generation = commit_graph_generation(commit);
+ steps++;
+- if (min_generation && generation > last_gen)
++ if (generation > last_gen)
+ BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
+ generation, last_gen,
+ oid_to_hex(&commit->object.oid));
## t/t6600-test-reach.sh ##
-@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps' '
- cp commit-graph-full .git/objects/info/commit-graph &&
- GIT_TRACE2_EVENT="$(pwd)/trace-full.txt" \
- git merge-base --all commit-9-9 commit-9-1 >actual &&
-- test_trace2_data paint_down_to_common steps 80 <trace-full.txt &&
-+ test_trace2_data paint_down_to_common steps 9 <trace-full.txt &&
+@@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:self' '
+ EOF
+ echo "in_merge_bases_many(A,X):1" >expect &&
+ test_all_modes in_merge_bases_many &&
+- test_paint_down_steps 45 2 25 3
++ test_paint_down_steps 45 1 25 1
+ '
- cp commit-graph-half .git/objects/info/commit-graph &&
- GIT_TRACE2_EVENT="$(pwd)/trace-half.txt" \
- git merge-base --all commit-9-9 commit-9-1 >actual &&
-- test_trace2_data paint_down_to_common steps 81 <trace-half.txt
-+ test_trace2_data paint_down_to_common steps 57 <trace-half.txt
+ test_expect_success 'is_descendant_of:hit' '
+@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps' '
+ >input &&
+ git rev-parse commit-9-1 >expect &&
+ run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
+- test_paint_down_steps 81 80 81 81
++ test_paint_down_steps 81 9 57 10
'
test_expect_success 'reduce_heads' '
-: ---------- > 8: 4b9f192d98 commit-reach: move min_generation check into paint_queue_get()
--
gitgitgadget
^ permalink raw reply
* [PATCH v3 1/8] Documentation/technical: add paint-down-to-common doc
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:07 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a technical document describing the paint_down_to_common()
algorithm used for merge-base computation, covering the paint
walk, generation number regions, and termination conditions.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 114 ++++++++++++++++++
commit-reach.c | 6 +-
4 files changed, 121 insertions(+), 1 deletion(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
diff --git a/Documentation/Makefile b/Documentation/Makefile
index 2699f0b24a..f8dea4b395 100644
--- a/Documentation/Makefile
+++ b/Documentation/Makefile
@@ -129,6 +129,7 @@ TECH_DOCS += technical/long-running-process-protocol
TECH_DOCS += technical/multi-pack-index
TECH_DOCS += technical/packfile-uri
TECH_DOCS += technical/pack-heuristics
+TECH_DOCS += technical/paint-down-to-common
TECH_DOCS += technical/parallel-checkout
TECH_DOCS += technical/partial-clone
TECH_DOCS += technical/platform-support
diff --git a/Documentation/technical/meson.build b/Documentation/technical/meson.build
index ec07088c57..9ce11d5e48 100644
--- a/Documentation/technical/meson.build
+++ b/Documentation/technical/meson.build
@@ -18,6 +18,7 @@ articles = [
'multi-pack-index.adoc',
'packfile-uri.adoc',
'pack-heuristics.adoc',
+ 'paint-down-to-common.adoc',
'parallel-checkout.adoc',
'partial-clone.adoc',
'platform-support.adoc',
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
new file mode 100644
index 0000000000..c10d5d2887
--- /dev/null
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -0,0 +1,114 @@
+Merge-Base Computation and paint_down_to_common()
+==================================================
+
+The function `paint_down_to_common()` in `commit-reach.c` computes merge
+bases by walking the commit graph backwards from two sets of tips and
+finding where their ancestry meets.
+
+Use cases
+---------
+
+Computing merge bases is used in two different ways:
+
+ 1. *Finding all merge bases* (`merge-base --all`, `merge-tree`,
+ `merge`, `rebase`). A merge base is a common ancestor that is
+ not itself an ancestor of another common ancestor.
+
+ 2. *Ancestry checks* (`in_merge_bases`, used by `merge-base
+ --is-ancestor`, `branch -d`, `fetch`). These ask: "is commit A
+ an ancestor of commit B?" If a common ancestor equals one of the
+ inputs, that input is necessarily the only merge base -- no other
+ common ancestor can be both as recent and not an ancestor of it.
+
+Both use cases share the same algorithm and implementation.
+
+Algorithm
+---------
+
+Given a commit `one` and a set of commits `twos[]`, the walk paints
+commits with two colors:
+
+ - PARENT1: reachable from `one`
+ - PARENT2: reachable from any commit in `twos[]`
+
+The walk uses a priority queue ordered by generation number (falling
+back to commit date when generation numbers are unavailable). Each
+step dequeues the highest-priority commit (this is when we say a
+commit is "visited") and propagates its paint flags to its parents,
+enqueuing them if they gained new flags. When a commit receives
+both PARENT1 and PARENT2, it is a merge-base candidate. A candidate
+gains the STALE flag so its ancestors propagate staleness -- any
+deeper common ancestor is necessarily redundant.
+
+INFINITY and finite generation regions
+--------------------------------------
+
+The commit-graph stores a generation number for each commit. Commits
+not in the commit-graph have generation `GENERATION_NUMBER_INFINITY`. The
+graph is closed under reachability: if a commit is in the graph, all
+its ancestors are too. This partitions the commit graph into two regions:
+
+....
+ +---------------------------------------+
+ | INFINITY region |
+ | generation = INFINITY |
+ | queue order: heuristic (commit date) |
+ +---------------------------------------+
+ |
+ v
+ +---------------------------------------+
+ | Finite region |
+ | generation = finite |
+ | queue order: topological |
+ +---------------------------------------+
+....
+
+When the commit-graph is enabled, the INFINITY region is typically
+very small -- it only contains commits added since the last
+commit-graph refresh.
+
+All reachable INFINITY-generation commits are visited before any
+finite-generation commit, because INFINITY is larger than any finite
+value. Once the walk crosses into the finite region, it stays there.
+
+In the finite region, generation ordering guarantees topological
+traversal: children are always visited before their parents. This
+means that paint on already-visited commits is final -- no future
+traversal step can add paint to them.
+
+In the INFINITY region, commit-date ordering can violate this: a
+parent with a later date can be visited before a child with an earlier
+date. Paint flags are therefore NOT final at visit time, and a
+commit visited with only one side's paint may later gain the other.
+
+Paint flags are only added, never removed. Since each flag can be set
+at most once per commit, the number of times a commit can be
+re-enqueued is bounded by the number of flag transitions.
+
+Termination
+-----------
+
+The walk uses a `nonstale_queue` wrapper around `prio_queue` that
+tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
+so far. Once that commit is dequeued, every remaining entry is known
+to be STALE and the loop terminates. Specifically, the main loop
+ends when one of the following conditions holds:
+
+ 1. The queue is empty.
+ 2. `max_nonstale` has been dequeued, meaning the queue only contains
+ STALE entries.
+
+Stale entry condition
+~~~~~~~~~~~~~~~~~~~~~
+Once all queued entries are stale, no new merge-base candidates can
+be discovered -- that requires at least one non-stale commit from
+each side meeting. Continuing the walk could still invalidate
+existing candidates by proving one is an ancestor of another, but
+`remove_redundant()` handles that as a post-processing step, so it
+is safe to exit early.
+
+Related documentation
+---------------------
+
+ - `Documentation/technical/commit-graph.adoc` -- generation numbers
+ and the reachability closure property.
diff --git a/commit-reach.c b/commit-reach.c
index 5df471a313..a9483759e0 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -96,7 +96,11 @@ static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
return commit;
}
-/* all input commits in one and twos[] must have been parsed! */
+/*
+ * See Documentation/technical/paint-down-to-common.adoc
+ *
+ * All input commits in one and twos[] must have been parsed!
+ */
static int paint_down_to_common(struct repository *r,
struct commit *one, int n,
struct commit **twos,
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 2/8] t6600: add test cases for side-exhaustion edge cases
From: Elijah Newren via GitGitGadget @ 2026-06-26 13:07 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson, Elijah Newren
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Elijah Newren <newren@gmail.com>
Add test cases to t6600-test-reach.sh that exercise edge cases in the
side-exhaustion optimization for paint_down_to_common():
- in_merge_bases_many:self: commit is both A and one of the X inputs
- get_merge_bases_many:duplicate-twos: duplicate entries in X list
- get_merge_bases_many:pending-stale: STALE transition on an
already-painted commit (ps-* diamond topology)
- get_merge_bases_many:infinity-both-sides: both tips outside the
commit-graph with non-monotonic dates (pi-* topology)
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/t6600-test-reach.sh | 111 ++++++++++++++++++++++++++++++++++++++++++
1 file changed, 111 insertions(+)
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b5b314e570..c2e091aad1 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -49,6 +49,62 @@ test_expect_success 'setup' '
git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i || return 1
done
done &&
+
+ # Build a small side topology to exercise the (PARENT1|PARENT2) ->
+ # (PARENT1|PARENT2|STALE) transition in paint_down_to_common(); the
+ # 10x10 grid above does not exercise it because no merge-base candidate
+ # there is a descendant of another, so STALE never reaches a
+ # still-pending candidate.
+ #
+ # ps-X
+ # /|\
+ # / | \
+ # ps-Z ps-B ps-W
+ # | / \ |
+ # | / \ |
+ # |/ \|
+ # ps-T1 ps-T2
+ #
+ # where ps-T1=merge(ps-Z,ps-B), ps-T2=merge(ps-W,ps-B), so
+ # merge-base(ps-T1,ps-T2) = ps-B. During the walk, ps-X transitions
+ # to (PARENT1|PARENT2) via ps-Z and ps-W before ps-B is dequeued;
+ # then the STALE-walk from ps-B transitions ps-X to
+ # (PARENT1|PARENT2|STALE).
+ git checkout --orphan ps-orphan &&
+ test_commit ps-X &&
+ git checkout -b ps-B-br ps-X && test_commit ps-B &&
+ git checkout -b ps-Z-br ps-X && test_commit ps-Z &&
+ git checkout -b ps-W-br ps-X && test_commit ps-W &&
+ git checkout -b ps-T1 ps-Z &&
+ git merge --no-ff -m ps-T1 ps-B &&
+ git checkout -b ps-T2 ps-W &&
+ git merge --no-ff -m ps-T2 ps-B &&
+
+ # Build a side topology that lives entirely outside the half
+ # commit-graph and has non-monotonic commit dates, to exercise the
+ # INFINITY-gate in paint_down_to_common. With both tips outside
+ # the graph, generation is INFINITY and the queue falls back to
+ # commit-date order, which here is non-monotonic.
+ #
+ # pi-X (date 500, PARENT1 tip) --> pi-P, pi-D
+ # pi-D (date 480) --> pi-C
+ # pi-C (date 200) --> pi-B
+ # pi-B (date 100, PARENT2 tip) --> pi-P
+ # pi-P (date 450, root)
+ #
+ # merge-base(pi-X, pi-B) = pi-B (it is an ancestor of pi-X and is
+ # itself one of the queried tips).
+ git checkout --orphan pi-orphan &&
+ test_commit --date "@450 +0000" pi-P &&
+ test_commit --date "@100 +0000" pi-B &&
+ test_commit --date "@200 +0000" pi-C &&
+ test_commit --date "@480 +0000" pi-D &&
+ GIT_AUTHOR_DATE="@500 +0000" GIT_COMMITTER_DATE="@500 +0000" \
+ git commit-tree -p pi-D -p pi-P -m pi-X pi-D^{tree} >pi-X-oid &&
+ pi_x="$(cat pi-X-oid)" &&
+ git branch -f pi-X-br "$pi_x" &&
+ git tag pi-X "$pi_x" &&
+
git commit-graph write --reachable &&
mv .git/objects/info/commit-graph commit-graph-full &&
chmod u+w commit-graph-full &&
@@ -146,6 +202,16 @@ test_expect_success 'in_merge_bases_many:miss-heuristic' '
test_all_modes in_merge_bases_many
'
+test_expect_success 'in_merge_bases_many:self' '
+ cat >input <<-\EOF &&
+ A:commit-6-8
+ X:commit-5-9
+ X:commit-6-8
+ EOF
+ echo "in_merge_bases_many(A,X):1" >expect &&
+ test_all_modes in_merge_bases_many
+'
+
test_expect_success 'is_descendant_of:hit' '
cat >input <<-\EOF &&
A:commit-5-7
@@ -183,6 +249,51 @@ test_expect_success 'get_merge_bases_many' '
test_all_modes get_merge_bases_many
'
+test_expect_success 'get_merge_bases_many:duplicate-twos' '
+ cat >input <<-\EOF &&
+ A:commit-5-7
+ X:commit-4-8
+ X:commit-4-8
+ X:commit-6-6
+ X:commit-6-6
+ X:commit-8-3
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse commit-5-6 \
+ commit-4-7 | sort
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:pending-stale' '
+ # Exercises the (PARENT1|PARENT2) -> (...|STALE) transition path in
+ # paint_down_to_common(). See the topology comment in the setup test.
+ cat >input <<-\EOF &&
+ A:ps-T1
+ X:ps-T2
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-B
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+ # Exercises the push-time INFINITY-gate in paint_down_to_common(). See
+ # the pi-* topology comment in the setup test.
+ cat >input <<-\EOF &&
+ A:pi-X
+ X:pi-B
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse pi-B
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
test_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 3/8] t6099, t6600: add side-exhaustion regression tests
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:08 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add t6099 to test the case where multiple merge-base candidates exist
and one is an ancestor of another. This exercises the side-exhaustion
optimization in paint_down_to_common together with the
remove_redundant safety net in get_merge_bases_many_0.
Add a mixed finite/INFINITY test to t6600 where one tip is outside
the commit-graph (INFINITY generation) and the other is inside.
This exercises the region transition: the walk starts in the
INFINITY region where side-exhaustion is disabled, then crosses
into the finite region where it can fire.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 +++++++++++++++++++++++++++
t/t6600-test-reach.sh | 25 ++++++++
3 files changed, 108 insertions(+)
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
diff --git a/t/meson.build b/t/meson.build
index 3219264fe7..ee6ebdffb9 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -786,6 +786,7 @@ integration_tests = [
't6041-bisect-submodule.sh',
't6050-replace.sh',
't6060-merge-index.sh',
+ 't6099-merge-base-side-exhaustion.sh',
't6100-rev-list-in-order.sh',
't6101-rev-parse-parents.sh',
't6102-rev-list-unexpected-objects.sh',
diff --git a/t/t6099-merge-base-side-exhaustion.sh b/t/t6099-merge-base-side-exhaustion.sh
new file mode 100755
index 0000000000..4f1e0d50ef
--- /dev/null
+++ b/t/t6099-merge-base-side-exhaustion.sh
@@ -0,0 +1,82 @@
+#!/bin/sh
+
+test_description='merge-base with ancestor among merge-base candidates
+
+Test that merge-base --all correctly handles cases where
+multiple merge-base candidates exist and one is an ancestor
+of another. The side-exhaustion optimization in
+paint_down_to_common may exit before STALE propagation
+removes the ancestor, but remove_redundant catches it.
+
+Graph shape (parents are below children):
+
+ A ----------- X
+ |\ /|
+ | B---------/ |
+ | | |
+ e2 \ f2
+ | | |
+ e1 d1 f1
+ \ | /
+ \ | /
+ \| /
+ C
+
+A and X are the two tips.
+B and C are both reachable from A and X.
+B reaches C through d1.
+Only B should appear in merge-base --all output.
+'
+
+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main
+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
+
+TEST_PASSES_SANITIZE_LEAK=true
+. ./test-lib.sh
+
+test_expect_success 'setup ancestor merge-base candidate' '
+ test_commit C &&
+
+ git checkout -b d-chain HEAD &&
+ test_commit d1 &&
+ test_commit B &&
+
+ git checkout -b e-path C &&
+ test_commit e1 &&
+ test_commit e2 &&
+
+ git checkout -b f-path C &&
+ test_commit f1 &&
+ test_commit f2 &&
+
+ git checkout -b branch-A e-path &&
+ test_merge A B &&
+
+ git checkout -b branch-X f-path &&
+ test_merge X B &&
+
+ git commit-graph write --reachable
+'
+
+test_expect_success 'merge-base --all excludes ancestor candidate' '
+ git rev-parse B >expected &&
+ git merge-base --all A X >actual &&
+ test_cmp expected actual
+'
+
+test_expect_success 'merge-base (single) finds shallowest' '
+ git rev-parse B >expected &&
+ git merge-base A X >actual &&
+ test_cmp expected actual
+'
+
+# Without commit-graph: generation numbers are INFINITY,
+# side-exhaustion optimization does not fire.
+test_expect_success 'merge-base --all without commit-graph' '
+ rm -f .git/objects/info/commit-graph &&
+ git rev-parse B >expected &&
+ git merge-base --all A X >actual &&
+ test_cmp expected actual
+'
+
+test_done
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index c2e091aad1..4b771b4c58 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -294,6 +294,31 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
test_all_modes get_merge_bases_many
'
+test_expect_success 'setup mixed finite/INFINITY topology' '
+ # Create a commit outside all saved commit-graph files so it always
+ # has INFINITY generation, while its parent (ps-X) is in the graph
+ # with a finite generation. Use the ps-* orphan topology so we do
+ # not pollute the grid-based rev-list tests.
+ git checkout ps-X &&
+ test_env GIT_TEST_COMMIT_GRAPH= test_commit pm-INF
+'
+
+test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
+ # One tip (pm-INF) is outside the commit-graph with INFINITY
+ # generation; the other (ps-B) is in the graph with finite
+ # generation. The walk starts in the INFINITY region and crosses
+ # into the finite region where side-exhaustion can fire.
+ cat >input <<-\EOF &&
+ A:pm-INF
+ X:ps-B
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-X
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
test_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 4/8] commit-reach: add trace2 instrumentation to paint_down_to_common()
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:08 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a step counter and trace2_data_intmax() call so that the number
of commits visited during the paint walk is observable via
GIT_TRACE2_EVENT. This provides a way to measure the impact of
future optimizations without relying on wall-clock benchmarks alone.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 5 ++++
t/t6600-test-reach.sh | 53 ++++++++++++++++++++++++++++++-------------
2 files changed, 42 insertions(+), 16 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index a9483759e0..f6a438550b 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -11,6 +11,7 @@
#include "tag.h"
#include "commit-reach.h"
#include "ewah/ewok.h"
+#include "trace2.h"
/* Remember to update object flag allocation in object.h */
#define PARENT1 (1u<<16)
@@ -112,6 +113,7 @@ static int paint_down_to_common(struct repository *r,
{ compare_commits_by_gen_then_commit_date }
};
int i;
+ int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
@@ -135,6 +137,7 @@ static int paint_down_to_common(struct repository *r,
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
+ steps++;
if (min_generation && generation > last_gen)
BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
@@ -190,6 +193,8 @@ static int paint_down_to_common(struct repository *r,
}
clear_nonstale_queue(&queue);
+ trace2_data_intmax("paint_down_to_common", r,
+ "steps", steps);
commit_list_sort_by_date(result);
return 0;
}
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 4b771b4c58..b3a31b80ac 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -118,24 +118,34 @@ test_expect_success 'setup' '
'
run_all_modes () {
- test_when_finished rm -rf .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-full .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-half .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-no-gdat .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual
+ graph=.git/objects/info/commit-graph &&
+ test_when_finished rm -rf "$graph" "${graph}s" &&
+ rm -f trace-mode-*.txt &&
+
+ for mode in none full half no-gdat
+ do
+ rm -rf "$graph" "${graph}s" &&
+ cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
+ true &&
+ GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
+ "$@" <input >actual &&
+ test_cmp expect actual || return 1
+ done
}
test_all_modes () {
run_all_modes test-tool reach "$@"
}
+test_paint_down_steps () {
+ for mode in none full half no-gdat
+ do
+ test_trace2_data paint_down_to_common steps "$1" \
+ <"trace-mode-${mode}.txt" || return 1
+ shift
+ done
+}
+
test_expect_success 'ref_newer:miss' '
cat >input <<-\EOF &&
A:commit-5-7
@@ -209,7 +219,8 @@ test_expect_success 'in_merge_bases_many:self' '
X:commit-6-8
EOF
echo "in_merge_bases_many(A,X):1" >expect &&
- test_all_modes in_merge_bases_many
+ test_all_modes in_merge_bases_many &&
+ test_paint_down_steps 45 2 25 3
'
test_expect_success 'is_descendant_of:hit' '
@@ -277,7 +288,8 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
echo "get_merge_bases_many(A,X):" &&
git rev-parse ps-B
} >expect &&
- test_all_modes get_merge_bases_many
+ test_all_modes get_merge_bases_many &&
+ test_paint_down_steps 6 6 6 6
'
test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ -291,7 +303,8 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
echo "get_merge_bases_many(A,X):" &&
git rev-parse pi-B
} >expect &&
- test_all_modes get_merge_bases_many
+ test_all_modes get_merge_bases_many &&
+ test_paint_down_steps 5 5 5 5
'
test_expect_success 'setup mixed finite/INFINITY topology' '
@@ -316,7 +329,15 @@ test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
echo "get_merge_bases_many(A,X):" &&
git rev-parse ps-X
} >expect &&
- test_all_modes get_merge_bases_many
+ test_all_modes get_merge_bases_many &&
+ test_paint_down_steps 3 3 3 3
+'
+
+test_expect_success 'merge-base --all commit-walk steps' '
+ >input &&
+ git rev-parse commit-9-1 >expect &&
+ run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
+ test_paint_down_steps 81 80 81 81
'
test_expect_success 'reduce_heads' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 5/8] commit-reach: introduce struct paint_state with per-side counters
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:08 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a paint_state struct for use by paint_down_to_common() that
wraps a prio_queue with per-side commit counters. Each non-stale
queued commit occupies exactly one counter bucket based on its
paint flags: PARENT1-only, PARENT2-only, or both sides (a pending
merge-base candidate).
The counters are maintained by paint_count_update() which adjusts
the appropriate bucket by a signed delta. An exhaustive switch on
the paint+stale bits documents all valid flag combinations in one
place.
Convert paint_down_to_common() to use paint_state. The loop now
drains the queue via paint_queue_get() which returns NULL when all
counters reach zero, replacing the old pointer-based termination
(max_nonstale). This is equivalent behavior -- both conditions
detect that no non-stale entries remain.
paint_queue_get() uses a "pop first" form: it dequeues a commit,
then checks the counters. This means the loop exits one iteration
earlier than the old code in some topologies (the popped stale
commit is never processed), so a few step counts drop by one.
The existing nonstale_queue is left in place for ahead_behind().
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 9 +-
commit-reach.c | 94 ++++++++++++++++---
t/t6600-test-reach.sh | 4 +-
3 files changed, 85 insertions(+), 22 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index c10d5d2887..0f4e1892a5 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -88,15 +88,12 @@ re-enqueued is bounded by the number of flag transitions.
Termination
-----------
-The walk uses a `nonstale_queue` wrapper around `prio_queue` that
-tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
-so far. Once that commit is dequeued, every remaining entry is known
-to be STALE and the loop terminates. Specifically, the main loop
+The walk tracks the number of commits of each type in the queue
+(PARENT1-only, PARENT2-only, pending merge-base). The main loop
ends when one of the following conditions holds:
1. The queue is empty.
- 2. `max_nonstale` has been dequeued, meaning the queue only contains
- STALE entries.
+ 2. The queue contains only stale entries.
Stale entry condition
~~~~~~~~~~~~~~~~~~~~~
diff --git a/commit-reach.c b/commit-reach.c
index f6a438550b..0f29b143bd 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -97,6 +97,75 @@ static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
return commit;
}
+/*
+ * Priority queue with per-side commit counters for paint_down_to_common().
+ * Each non-stale queued commit occupies exactly one bucket: PARENT1-only,
+ * PARENT2-only, or both (a pending merge-base candidate).
+ */
+struct paint_state {
+ struct prio_queue queue;
+ int p1_count;
+ int p2_count;
+ int pending_merge_bases;
+};
+
+static void paint_count_update(struct paint_state *state,
+ unsigned flags, int delta)
+{
+ switch (flags & (PARENT1 | PARENT2 | STALE)) {
+ case PARENT1:
+ state->p1_count += delta;
+ break;
+
+ case PARENT2:
+ state->p2_count += delta;
+ break;
+
+ case PARENT1 | PARENT2:
+ state->pending_merge_bases += delta;
+ break;
+
+ case PARENT1 | PARENT2 | STALE:
+ break;
+
+ default:
+ BUG("unexpected paint state");
+ }
+}
+
+static void paint_queue_put(struct paint_state *state,
+ struct commit *c, unsigned add_flags)
+{
+ unsigned old_flags = c->object.flags;
+ c->object.flags |= add_flags;
+
+ if (old_flags & ENQUEUED) {
+ paint_count_update(state, old_flags, -1);
+ paint_count_update(state, c->object.flags, 1);
+ } else {
+ c->object.flags |= ENQUEUED;
+ prio_queue_put(&state->queue, c);
+ paint_count_update(state, c->object.flags, 1);
+ }
+}
+
+static struct commit *paint_queue_get(struct paint_state *state)
+{
+ struct commit *commit = prio_queue_get(&state->queue);
+
+ if (!commit)
+ return NULL;
+
+ commit->object.flags &= ~ENQUEUED;
+
+ if (!state->p1_count && !state->p2_count &&
+ !state->pending_merge_bases)
+ return NULL;
+
+ paint_count_update(state, commit->object.flags, -1);
+ return commit;
+}
+
/*
* See Documentation/technical/paint-down-to-common.adoc
*
@@ -109,31 +178,29 @@ static int paint_down_to_common(struct repository *r,
enum merge_base_flags mb_flags,
struct commit_list **result)
{
- struct nonstale_queue queue = {
- { compare_commits_by_gen_then_commit_date }
+ struct paint_state state = {
+ .queue = { compare_commits_by_gen_then_commit_date }
};
+ struct commit *commit;
int i;
int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
if (!min_generation && !corrected_commit_dates_enabled(r))
- queue.pq.compare = compare_commits_by_commit_date;
+ state.queue.compare = compare_commits_by_commit_date;
one->object.flags |= PARENT1;
if (!n) {
commit_list_append(one, result);
return 0;
}
- nonstale_queue_put_dedup(&queue, one);
+ paint_queue_put(&state, one, 0);
- for (i = 0; i < n; i++) {
- twos[i]->object.flags |= PARENT2;
- nonstale_queue_put_dedup(&queue, twos[i]);
- }
+ for (i = 0; i < n; i++)
+ paint_queue_put(&state, twos[i], PARENT2);
- while (queue.max_nonstale) {
- struct commit *commit = nonstale_queue_get_dedup(&queue);
+ while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
@@ -172,7 +239,7 @@ static int paint_down_to_common(struct repository *r,
if ((p->object.flags & flags) == flags)
continue;
if (repo_parse_commit(r, p)) {
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&state.queue);
commit_list_free(*result);
*result = NULL;
/*
@@ -187,12 +254,11 @@ static int paint_down_to_common(struct repository *r,
return error(_("could not parse commit %s"),
oid_to_hex(&p->object.oid));
}
- p->object.flags |= flags;
- nonstale_queue_put_dedup(&queue, p);
+ paint_queue_put(&state, p, flags);
}
}
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&state.queue);
trace2_data_intmax("paint_down_to_common", r,
"steps", steps);
commit_list_sort_by_date(result);
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b3a31b80ac..51f3d70492 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -289,7 +289,7 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
git rev-parse ps-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 6 6 6 6
+ test_paint_down_steps 5 5 5 5
'
test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ -304,7 +304,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
git rev-parse pi-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 5 5 5 5
+ test_paint_down_steps 5 4 5 5
'
test_expect_success 'setup mixed finite/INFINITY topology' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 6/8] commit-reach: remove unused nonstale_queue dedup wrappers
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:08 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
nonstale_queue_put_dedup() and nonstale_queue_get_dedup() became
unused after the previous commit. The core nonstale_queue functions
remain in use by ahead_behind().
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 18 ------------------
1 file changed, 18 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 0f29b143bd..ee0e0fdf6e 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -79,24 +79,6 @@ static void clear_nonstale_queue(struct nonstale_queue *queue)
queue->max_nonstale = NULL;
}
-static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
- struct commit *c)
-{
- if (c->object.flags & ENQUEUED)
- return;
- c->object.flags |= ENQUEUED;
- nonstale_queue_put(queue, c);
-}
-
-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
-{
- struct commit *commit = nonstale_queue_get(queue);
-
- if (commit)
- commit->object.flags &= ~ENQUEUED;
- return commit;
-}
-
/*
* Priority queue with per-side commit counters for paint_down_to_common().
* Each non-stale queued commit occupies exactly one bucket: PARENT1-only,
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 7/8] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:08 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add an early termination check to paint_down_to_common() using the
per-side counters introduced earlier. Once the walk enters the
finite-generation region, terminate early when one side's exclusive
count drops to zero -- no new merge-base can form without both paint
sides meeting.
The check also waits for pending_merge_bases to reach zero, ensuring
all merge-base candidates have been dequeued and recorded before
exiting.
The INFINITY gate ensures correctness: commits without a commit-graph
entry have GENERATION_NUMBER_INFINITY and are ordered by commit date,
which is not topologically reliable. The optimization only fires
once the walk enters the finite-generation region where ordering
guarantees hold.
Widen the existing generation-monotonicity BUG assertion to fire
unconditionally, not only when min_generation is set. The
side-exhaustion optimization depends on correct generation ordering,
so the assertion should always be active.
Step counts measured with trace2 on git.git with commit-graph:
merge-base --all v2.0.0 v2.55.0-rc1:
before: 72264 steps after: 44589 steps
merge-base --all v2.55.0-rc1 v2.55.0-rc1~5:
before: 110 steps after: 7 steps
Helped-by: Derrick Stolee <stolee@gmail.com>
Helped-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 17 +++++++++++++++++
commit-reach.c | 19 +++++++++++++++----
t/t6600-test-reach.sh | 4 ++--
3 files changed, 34 insertions(+), 6 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index 0f4e1892a5..983dfcf233 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -94,6 +94,9 @@ ends when one of the following conditions holds:
1. The queue is empty.
2. The queue contains only stale entries.
+ 3. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
+ remain in the queue, no pending merge-base candidates exist,
+ and the walk has entered the finite-generation region.
Stale entry condition
~~~~~~~~~~~~~~~~~~~~~
@@ -104,6 +107,20 @@ existing candidates by proving one is an ancestor of another, but
`remove_redundant()` handles that as a post-processing step, so it
is safe to exit early.
+Side-exhaustion condition
+~~~~~~~~~~~~~~~~~~~~~~~~~
+A new merge-base requires commits from both sides to meet. When one
+side's exclusive counter reaches zero and there are no pending
+merge-base candidates, no future traversal step can produce a new
+candidate.
+
+This optimization only activates in the finite-generation region
+where topological ordering holds. In that region, children are
+always visited before parents, so paint flags are final at visit
+time and an exhausted side cannot reappear. In the INFINITY region,
+commit-date ordering can violate this guarantee, so the check is
+skipped.
+
Related documentation
---------------------
diff --git a/commit-reach.c b/commit-reach.c
index ee0e0fdf6e..0248d6fedb 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -131,6 +131,10 @@ static void paint_queue_put(struct paint_state *state,
}
}
+/*
+ * Dequeue the next commit for the paint walk, or return NULL when
+ * no more merge bases can be discovered.
+ */
static struct commit *paint_queue_get(struct paint_state *state)
{
struct commit *commit = prio_queue_get(&state->queue);
@@ -140,9 +144,16 @@ static struct commit *paint_queue_get(struct paint_state *state)
commit->object.flags &= ~ENQUEUED;
- if (!state->p1_count && !state->p2_count &&
- !state->pending_merge_bases)
- return NULL;
+ if (!state->pending_merge_bases) {
+ /* only stale entries remain */
+ if (!state->p1_count && !state->p2_count)
+ return NULL;
+
+ /* one side is exhausted */
+ if ((!state->p1_count || !state->p2_count) &&
+ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ return NULL;
+ }
paint_count_update(state, commit->object.flags, -1);
return commit;
@@ -188,7 +199,7 @@ static int paint_down_to_common(struct repository *r,
timestamp_t generation = commit_graph_generation(commit);
steps++;
- if (min_generation && generation > last_gen)
+ if (generation > last_gen)
BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
generation, last_gen,
oid_to_hex(&commit->object.oid));
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 51f3d70492..6365007560 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -220,7 +220,7 @@ test_expect_success 'in_merge_bases_many:self' '
EOF
echo "in_merge_bases_many(A,X):1" >expect &&
test_all_modes in_merge_bases_many &&
- test_paint_down_steps 45 2 25 3
+ test_paint_down_steps 45 1 25 1
'
test_expect_success 'is_descendant_of:hit' '
@@ -337,7 +337,7 @@ test_expect_success 'merge-base --all commit-walk steps' '
>input &&
git rev-parse commit-9-1 >expect &&
run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
- test_paint_down_steps 81 80 81 81
+ test_paint_down_steps 81 9 57 10
'
test_expect_success 'reduce_heads' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v3 8/8] commit-reach: move min_generation check into paint_queue_get()
From: Kristofer Karlsson via GitGitGadget @ 2026-06-26 13:08 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Consolidate the min_generation termination condition into
paint_queue_get(), alongside the existing stale-entry and
side-exhaustion checks.
Move last_gen into struct paint_state so that
commit_graph_generation() is called exactly once per dequeued commit
and the result is shared across all termination checks and the
monotonicity BUG assertion. The loop body in paint_down_to_common()
reads state.last_gen instead of recomputing the generation number.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 9 ++++++
commit-reach.c | 31 +++++++++++--------
2 files changed, 27 insertions(+), 13 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index 983dfcf233..eef249f4a4 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -97,6 +97,8 @@ ends when one of the following conditions holds:
3. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
remain in the queue, no pending merge-base candidates exist,
and the walk has entered the finite-generation region.
+ 4. Generation cutoff: the dequeued commit's generation is below
+ a caller-supplied `min_generation` threshold.
Stale entry condition
~~~~~~~~~~~~~~~~~~~~~
@@ -121,6 +123,13 @@ time and an exhausted side cannot reappear. In the INFINITY region,
commit-date ordering can violate this guarantee, so the check is
skipped.
+Generation cutoff
+~~~~~~~~~~~~~~~~~
+Some callers (notably `remove_redundant()`) supply a `min_generation`
+threshold -- the minimum generation of the input commits. No merge
+base can have a generation below this threshold, so the walk
+terminates as soon as it dequeues such a commit.
+
Related documentation
---------------------
diff --git a/commit-reach.c b/commit-reach.c
index 0248d6fedb..0cd785c31b 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -89,6 +89,8 @@ struct paint_state {
int p1_count;
int p2_count;
int pending_merge_bases;
+ timestamp_t min_generation;
+ timestamp_t last_gen;
};
static void paint_count_update(struct paint_state *state,
@@ -138,11 +140,23 @@ static void paint_queue_put(struct paint_state *state,
static struct commit *paint_queue_get(struct paint_state *state)
{
struct commit *commit = prio_queue_get(&state->queue);
+ timestamp_t generation;
if (!commit)
return NULL;
commit->object.flags &= ~ENQUEUED;
+ generation = commit_graph_generation(commit);
+
+ if (generation > state->last_gen)
+ BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
+ generation, state->last_gen,
+ oid_to_hex(&commit->object.oid));
+ state->last_gen = generation;
+
+ /* generation cutoff */
+ if (generation < state->min_generation)
+ return NULL;
if (!state->pending_merge_bases) {
/* only stale entries remain */
@@ -151,7 +165,7 @@ static struct commit *paint_queue_get(struct paint_state *state)
/* one side is exhausted */
if ((!state->p1_count || !state->p2_count) &&
- commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ generation < GENERATION_NUMBER_INFINITY)
return NULL;
}
@@ -177,9 +191,10 @@ static int paint_down_to_common(struct repository *r,
struct commit *commit;
int i;
int steps = 0;
- timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
+ state.min_generation = min_generation;
+ state.last_gen = GENERATION_NUMBER_INFINITY;
if (!min_generation && !corrected_commit_dates_enabled(r))
state.queue.compare = compare_commits_by_commit_date;
@@ -196,18 +211,8 @@ static int paint_down_to_common(struct repository *r,
while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
int flags;
- timestamp_t generation = commit_graph_generation(commit);
steps++;
- if (generation > last_gen)
- BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
- generation, last_gen,
- oid_to_hex(&commit->object.oid));
- last_gen = generation;
-
- if (generation < min_generation)
- break;
-
flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
if (flags == (PARENT1 | PARENT2)) {
if (!(commit->object.flags & RESULT)) {
@@ -219,7 +224,7 @@ static int paint_down_to_common(struct repository *r,
* descendant of this one.
*/
if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
- generation < GENERATION_NUMBER_INFINITY)
+ state.last_gen < GENERATION_NUMBER_INFINITY)
break;
}
/* Mark parents of a found merge stale */
--
gitgitgadget
^ permalink raw reply related
* Re: [PATCH v5 0/4] history: add squash subcommand to fold a range
From: Phillip Wood @ 2026-06-26 13:12 UTC (permalink / raw)
To: Harald Nordgren, phillip.wood
Cc: Harald Nordgren via GitGitGadget, git, Patrick Steinhardt
In-Reply-To: <CAHwyqnWXaG1HGunztVgUdWnVogqCHRbxh8pcS5fGA6f3mB-nEA@mail.gmail.com>
On 26/06/2026 10:57, Harald Nordgren wrote:
> On Fri, Jun 26, 2026 at 10:53 AM Phillip Wood <phillip.wood123@gmail.com> wrote:>> >> Only accepting a single argument is quite limiting as one
>> cannot say
>>
>> git history squash ^:/base :/tip
>
> I don't understand why this is limiting? It thought it was clear that
> it should be one argument REF1..REF2 ? What does '^:/base :/tip'
> achieve that '^:/base..:/tip' cannot?
'^/:base..:/tip' is not a range - everything after the first '/:' is
treated as a regular expression to search for.
Thanks
Phillip
^ permalink raw reply
* Re: [RFH] Why do osx CI jobs so unreliable?
From: Junio C Hamano @ 2026-06-26 13:45 UTC (permalink / raw)
To: Patrick Steinhardt; +Cc: Jeff King, Michael Montalbo, git
In-Reply-To: <aj5ZaZK7xylfs4Xw@pks.im>
Patrick Steinhardt <ps@pks.im> writes:
>> Trying to make the wedged state fail fast and loudly is mostly just
>> punting on the problem. We'd still see spurious failures. We've so far
>> resisted the urge to do any automatic flaky-test retries, preferring
>> instead to just try to root out the flakes. I'm a little hesitant to
>> start now, because I think our strategy has mostly been good so far, and
>> I've seen some horrible counter-examples where flakes and retries become
>> a routine drag on development (and I'm afraid that accommodating flakes
>> might make them more common).
>
> I agree. I'm not a fan of retry logic, as every flaky test may mask an
> actual bug that we haven't fully investigated yet.
Can't agree more.
> I was also wondering whether we can maybe work around the issue by
> increasing the Apache timeout value. That sounds like an easy potential
> solution to try, and from all we've discovered so far it doesn't feel
> like this is something we can address on the Git side.
Thanks, all, for looking into this.
^ permalink raw reply
* Re: [PATCH v5 0/4] history: add squash subcommand to fold a range
From: Junio C Hamano @ 2026-06-26 14:02 UTC (permalink / raw)
To: Phillip Wood
Cc: Harald Nordgren, phillip.wood, Harald Nordgren via GitGitGadget,
git, Patrick Steinhardt
In-Reply-To: <4654a3f1-bf79-4c3f-b121-16bb3ab25f07@gmail.com>
Phillip Wood <phillip.wood123@gmail.com> writes:
> On 26/06/2026 10:57, Harald Nordgren wrote:
>> On Fri, Jun 26, 2026 at 10:53 AM Phillip Wood <phillip.wood123@gmail.com> wrote:>> >> Only accepting a single argument is quite limiting as one
>>> cannot say
>>>
>>> git history squash ^:/base :/tip
>>
>> I don't understand why this is limiting? It thought it was clear that
>> it should be one argument REF1..REF2 ? What does '^:/base :/tip'
>> achieve that '^:/base..:/tip' cannot?
>
> '^/:base..:/tip' is not a range - everything after the first '/:' is
> treated as a regular expression to search for.
This particular case you can do
HEAD^{/base}..HEAD^{/tip}
(or even go "HEAD^{/tip}~43" and fancier other forms, the point
being with matching {} pair, you can do more than what the lazy
short-hand form can).
But I think your point still stands, I think, as
git history squash HEAD^{/base}..:/tip ^main
may be something you would want to do to express additional
constraints, like "I want this range squashed, but I should never
ever touch what is already in main".
^ permalink raw reply
* Re: [PATCH v3 7/8] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Kristofer Karlsson @ 2026-06-26 14:29 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget; +Cc: git, Derrick Stolee, Elijah Newren
In-Reply-To: <f3572a8a89c74fad54a9e53be6f0e34daa2d50c2.1782479286.git.gitgitgadget@gmail.com>
On Fri, 26 Jun 2026 at 15:08, Kristofer Karlsson via GitGitGadget
<gitgitgadget@gmail.com> wrote:
>
> From: Kristofer Karlsson <krka@spotify.com>
>
> - if (min_generation && generation > last_gen)
> + if (generation > last_gen)
I have to note that I accidentally pushed this version before noticing
that it now fails for a subset of commit-graph modes.
Apologies for that - I will rework the logic here later
to preserve the behavior better.
I think (and hope) the rest of the patch series is in good shape though
and addressed the previous feedback, so any partial new review
feedback would still be appreciated.
Thanks,
Kristofer
^ permalink raw reply
* Re: [PATCH v3 4/8] commit-reach: add trace2 instrumentation to paint_down_to_common()
From: Derrick Stolee @ 2026-06-26 14:31 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget, git
Cc: Elijah Newren, Kristofer Karlsson
In-Reply-To: <2592264cda543c96c4479bb4ba6368c0121e4207.1782479286.git.gitgitgadget@gmail.com>
On 6/26/2026 9:08 AM, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> run_all_modes () {
> - test_when_finished rm -rf .git/objects/info/commit-graph &&
> - "$@" <input >actual &&
> - test_cmp expect actual &&
> - cp commit-graph-full .git/objects/info/commit-graph &&
> - "$@" <input >actual &&
> - test_cmp expect actual &&
> - cp commit-graph-half .git/objects/info/commit-graph &&
> - "$@" <input >actual &&
> - test_cmp expect actual &&
> - cp commit-graph-no-gdat .git/objects/info/commit-graph &&
> - "$@" <input >actual &&
> - test_cmp expect actual
> + graph=.git/objects/info/commit-graph &&
> + test_when_finished rm -rf "$graph" "${graph}s" &&
> + rm -f trace-mode-*.txt &&
> +
> + for mode in none full half no-gdat
> + do
> + rm -rf "$graph" "${graph}s" &&
> + cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
> + true &&
> + GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
> + "$@" <input >actual &&
> + test_cmp expect actual || return 1
> + done
> }
Thank you for putting these traces into this helper AND for
making it cleaner at the same time!
> +test_paint_down_steps () {
> + for mode in none full half no-gdat
> + do
> + test_trace2_data paint_down_to_common steps "$1" \
> + <"trace-mode-${mode}.txt" || return 1
> + shift
> + done
> +}
> +
> test_expect_success 'ref_newer:miss' '
> cat >input <<-\EOF &&
> A:commit-5-7
> @@ -209,7 +219,8 @@ test_expect_success 'in_merge_bases_many:self' '
> X:commit-6-8
> EOF
> echo "in_merge_bases_many(A,X):1" >expect &&
> - test_all_modes in_merge_bases_many
> + test_all_modes in_merge_bases_many &&
> + test_paint_down_steps 45 2 25 3
> '
oooh that's clean. Thanks!
Way to over-achieve here. Thanks for going the extra mile with
this patch.
Thanks,
-Stolee
^ permalink raw reply
* Re: [PATCH v3 7/8] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Derrick Stolee @ 2026-06-26 14:32 UTC (permalink / raw)
To: Kristofer Karlsson, Kristofer Karlsson via GitGitGadget
Cc: git, Elijah Newren
In-Reply-To: <CAL71e4N3RPHSrXscwYJUiLWc8-a172h+nE13yuUBRV7Uu3zGzw@mail.gmail.com>
On 6/26/2026 10:29 AM, Kristofer Karlsson wrote:
> On Fri, 26 Jun 2026 at 15:08, Kristofer Karlsson via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
>>
>> From: Kristofer Karlsson <krka@spotify.com>
>>
>> - if (min_generation && generation > last_gen)
>> + if (generation > last_gen)
>
> I have to note that I accidentally pushed this version before noticing
> that it now fails for a subset of commit-graph modes.
> Apologies for that - I will rework the logic here later
> to preserve the behavior better.
And do we catch this with a test case? I'm hoping that you discovered
this error through the test suite, even if you submitted the series a
little early.
> I think (and hope) the rest of the patch series is in good shape though
> and addressed the previous feedback, so any partial new review
> feedback would still be appreciated.
Thanks for calling this out, as now I can avoid trying to understand
this change during my review.
Thanks,
-Stolee
^ permalink raw reply
* Re: [PATCH v3 7/8] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Derrick Stolee @ 2026-06-26 14:35 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget, git
Cc: Elijah Newren, Kristofer Karlsson
In-Reply-To: <f3572a8a89c74fad54a9e53be6f0e34daa2d50c2.1782479286.git.gitgitgadget@gmail.com>
On 6/26/2026 9:08 AM, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
> @@ -140,9 +144,16 @@ static struct commit *paint_queue_get(struct paint_state *state)
>
> commit->object.flags &= ~ENQUEUED;
>
> - if (!state->p1_count && !state->p2_count &&
> - !state->pending_merge_bases)
> - return NULL;
> + if (!state->pending_merge_bases) {
> + /* only stale entries remain */
> + if (!state->p1_count && !state->p2_count)
> + return NULL;
> +
> + /* one side is exhausted */
> + if ((!state->p1_count || !state->p2_count) &&
> + commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
> + return NULL;
> + }
This continues to look correct.
> paint_count_update(state, commit->object.flags, -1);
> return commit;
> @@ -188,7 +199,7 @@ static int paint_down_to_common(struct repository *r,
> timestamp_t generation = commit_graph_generation(commit);
> steps++;
>
> - if (min_generation && generation > last_gen)
> + if (generation > last_gen)
> BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
> generation, last_gen,
> oid_to_hex(&commit->object.oid));
You mention in your own reply that this is broken. This also looks
like a stray change for this patch, so perhaps your end state is
correct despite this patch causing failures. Will inspect soon.
> - test_paint_down_steps 45 2 25 3
> + test_paint_down_steps 45 1 25 1
...> - test_paint_down_steps 81 80 81 81
> + test_paint_down_steps 81 9 57 10
These diffs are satisfying.
Thanks,
-Stolee
^ permalink raw reply
* Re: [PATCH v3 4/8] commit-reach: add trace2 instrumentation to paint_down_to_common()
From: Kristofer Karlsson @ 2026-06-26 14:35 UTC (permalink / raw)
To: Derrick Stolee; +Cc: Kristofer Karlsson via GitGitGadget, git, Elijah Newren
In-Reply-To: <a74d3114-7d7f-469a-b181-60853bb82864@gmail.com>
On Fri, 26 Jun 2026 at 16:31, Derrick Stolee <stolee@gmail.com> wrote:
>
> > test_expect_success 'ref_newer:miss' '
> > cat >input <<-\EOF &&
> > A:commit-5-7
> > @@ -209,7 +219,8 @@ test_expect_success 'in_merge_bases_many:self' '
> > X:commit-6-8
> > EOF
> > echo "in_merge_bases_many(A,X):1" >expect &&
> > - test_all_modes in_merge_bases_many
> > + test_all_modes in_merge_bases_many &&
> > + test_paint_down_steps 45 2 25 3
> > '
>
> oooh that's clean. Thanks!
>
> Way to over-achieve here. Thanks for going the extra mile with
> this patch.
Thanks! I did not want to change it too much but this felt like
a natural place to simplify it a bit.
I also have a local branch now for adding a
test_trace2_data_singular helper function that provides
more diagnostics on failures
(show expected vs actual similar to test_cmp)
but I'll submit that separately later to limit the scope creep here.
Thanks,
Kristofer
^ permalink raw reply
* Re: [PATCH GSoC RFC v13 06/12] connect: refactor packet writing
From: Karthik Nayak @ 2026-06-26 14:39 UTC (permalink / raw)
To: Junio C Hamano
Cc: Pablo Sabater, peff, eric.peijian, chriscool, git, jltobler, toon,
chandrapratap3519, Jonathan Tan, Calvin Wan
In-Reply-To: <xmqqpl1fhesc.fsf@gitster.g>
[-- Attachment #1: Type: text/plain, Size: 777 bytes --]
Junio C Hamano <gitster@pobox.com> writes:
> Karthik Nayak <karthik.188@gmail.com> writes:
>
>>> +/*
>>> + * Writes a command along with the requested server capabilities/features into a
>>> + * request buffer.
>>> + */
>>> struct string_list;
>>
>> The comment should be above the function and not the forward
>> declaration.
>>
>> While we're here, why not `#include "string-list.h"` and remove the
>> forward declaration, is there a circular dependency?
>
> Isn't it to avoid unnecessary include? When the header itself only
> needs to know about the presence of the type, and not the concrete
> shape of the type (e.g., because it only uses a pointer to that
> type), it may be overkill to include the entire header file.
Indeed that seems to be it. Makes sense to me.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 690 bytes --]
^ permalink raw reply
* Re: [PATCH v3 7/8] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Kristofer Karlsson @ 2026-06-26 14:39 UTC (permalink / raw)
To: Derrick Stolee; +Cc: Kristofer Karlsson via GitGitGadget, git, Elijah Newren
In-Reply-To: <5edd5912-80b2-4372-b921-52c20e496276@gmail.com>
On Fri, 26 Jun 2026 at 16:35, Derrick Stolee <stolee@gmail.com> wrote:
>
> > - if (min_generation && generation > last_gen)
> > + if (generation > last_gen)
> > BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
> > generation, last_gen,
> > oid_to_hex(&commit->object.oid));
>
> You mention in your own reply that this is broken. This also looks
> like a stray change for this patch, so perhaps your end state is
> correct despite this patch causing failures. Will inspect soon.
I did not intend it to be a stray change, but rather a natural followup
to the idea that we could fold all of the halt conditions into the same
place. I am happy to either revert that part for v4 (to keep the change
simpler, but not fully unified) or fix it properly - I think it should be easy
since this was just human error, not a sign of a fundamentally tricky
problem.
> > - test_paint_down_steps 45 2 25 3
> > + test_paint_down_steps 45 1 25 1
> ...> - test_paint_down_steps 81 80 81 81
> > + test_paint_down_steps 81 9 57 10
> These diffs are satisfying.
Agreed! It was nice to introduce the steps counter to the
test suite, showing that the patch reached its intended goal
which is clearer than just having benchmarks in the messages.
Thanks again,
Kristofer
^ permalink raw reply
* Re: [PATCH v3 8/8] commit-reach: move min_generation check into paint_queue_get()
From: Derrick Stolee @ 2026-06-26 14:42 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget, git
Cc: Elijah Newren, Kristofer Karlsson
In-Reply-To: <4b9f192d98b8e8f2d30eed4261a73e766eeafcc2.1782479286.git.gitgitgadget@gmail.com>
On 6/26/2026 9:08 AM, Kristofer Karlsson via GitGitGadget wrote:
> From: Kristofer Karlsson <krka@spotify.com>
>
> Consolidate the min_generation termination condition into
> paint_queue_get(), alongside the existing stale-entry and
> side-exhaustion checks.
>
> Move last_gen into struct paint_state so that
> commit_graph_generation() is called exactly once per dequeued commit
> and the result is shared across all termination checks and the
> monotonicity BUG assertion. The loop body in paint_down_to_common()
> reads state.last_gen instead of recomputing the generation number.
Thanks for incorporating this change into this version.
> + 4. Generation cutoff: the dequeued commit's generation is below
> + a caller-supplied `min_generation` threshold.
Technically, this was always a termination condition of the walk,
but now we are correcting the documentation to match. It was just
not part of the termination in the dequeue method until now.
> @@ -89,6 +89,8 @@ struct paint_state {
> int p1_count;
> int p2_count;
> int pending_merge_bases;
> + timestamp_t min_generation;
> + timestamp_t last_gen;
> };
I'm happy that these details are being imported into the struct.
My first reaction is that last_gen shouldn't be here because we
can see a generation from the dequeued commit. I'll read on to
be sure.
> static void paint_count_update(struct paint_state *state,
> @@ -138,11 +140,23 @@ static void paint_queue_put(struct paint_state *state,
> static struct commit *paint_queue_get(struct paint_state *state)
> {
> struct commit *commit = prio_queue_get(&state->queue);
> + timestamp_t generation;
>
> if (!commit)
> return NULL;
>
> commit->object.flags &= ~ENQUEUED;
> + generation = commit_graph_generation(commit);
> +
> + if (generation > state->last_gen)
> + BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
> + generation, state->last_gen,
> + oid_to_hex(&commit->object.oid));
Oh I see. It's just for this condition.
Does this case still break without 'state->min_generation' in the
condition?
> + state->last_gen = generation;
This is an appropriate use of this value. My concerns are no longer
valid. Thanks for letting me think out loud.
> + /* generation cutoff */
> + if (generation < state->min_generation)
> + return NULL;
And here's the crux. Again, impossible for this to halt when
min_generation is zero.
> if (!state->pending_merge_bases) {
> /* only stale entries remain */
> @@ -151,7 +165,7 @@ static struct commit *paint_queue_get(struct paint_state *state)
>
> /* one side is exhausted */
> if ((!state->p1_count || !state->p2_count) &&
> - commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
> + generation < GENERATION_NUMBER_INFINITY)
> return NULL;
Good reuse of the value.
> }
>
> @@ -177,9 +191,10 @@ static int paint_down_to_common(struct repository *r,
> struct commit *commit;
> int i;
> int steps = 0;
> - timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
> struct commit_list **tail = result;
>
> + state.min_generation = min_generation;
> + state.last_gen = GENERATION_NUMBER_INFINITY;
> if (!min_generation && !corrected_commit_dates_enabled(r))
> state.queue.compare = compare_commits_by_commit_date;
>
> @@ -196,18 +211,8 @@ static int paint_down_to_common(struct repository *r,
> while ((commit = paint_queue_get(&state))) {
> struct commit_list *parents;
> int flags;
> - timestamp_t generation = commit_graph_generation(commit);
> steps++;
>
> - if (generation > last_gen)
> - BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
> - generation, last_gen,
> - oid_to_hex(&commit->object.oid));
> - last_gen = generation;
> -
> - if (generation < min_generation)
> - break;
> -
I'm happy this is getting cleaned up.
> flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
> if (flags == (PARENT1 | PARENT2)) {
> if (!(commit->object.flags & RESULT)) {
> @@ -219,7 +224,7 @@ static int paint_down_to_common(struct repository *r,
> * descendant of this one.
> */
> if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
> - generation < GENERATION_NUMBER_INFINITY)
> + state.last_gen < GENERATION_NUMBER_INFINITY)
> break;
> }
> /* Mark parents of a found merge stale */
And here's another termination condition. We are now leaking the
abstraction of the 'state.last_gen' which give me some bad feelings.
We are getting to the point where I'd leave such a thing for a
follow-up, but since you are needing to re-roll, then this is
another case where we can move this into the paint_queue_get(). I
don't think this is me "raising the bar" from earlier recommendations,
because I was asking for all loop termination to be in the get()
method, if possible.
But also: I'm not looking at the full method right now to see if
terminating _at this location in the loop_ is critical. So it may
very well be impossible to move this into the get() call, in which
case please ignore this suggestion and use state.last_gen.
Thanks,
-Stolee
^ permalink raw reply
* Re: [PATCH v3 8/8] commit-reach: move min_generation check into paint_queue_get()
From: Kristofer Karlsson @ 2026-06-26 14:53 UTC (permalink / raw)
To: Derrick Stolee; +Cc: Kristofer Karlsson via GitGitGadget, git, Elijah Newren
In-Reply-To: <34ff8be2-1b3c-480f-ae27-9d65875e6e62@gmail.com>
On Fri, 26 Jun 2026 at 16:42, Derrick Stolee <stolee@gmail.com> wrote:
>
> > + 4. Generation cutoff: the dequeued commit's generation is below
> > + a caller-supplied `min_generation` threshold.
>
> Technically, this was always a termination condition of the walk,
> but now we are correcting the documentation to match. It was just
> not part of the termination in the dequeue method until now.
You're right, I should perhaps fold it into the first patch instead,
which would be logically more accurate. Would be an easy thing
to fix for a v4.
> > flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
> > if (flags == (PARENT1 | PARENT2)) {
> > if (!(commit->object.flags & RESULT)) {
> > @@ -219,7 +224,7 @@ static int paint_down_to_common(struct repository *r,
> > * descendant of this one.
> > */
> > if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
> > - generation < GENERATION_NUMBER_INFINITY)
> > + state.last_gen < GENERATION_NUMBER_INFINITY)
> > break;
> > }
> > /* Mark parents of a found merge stale */
>
> And here's another termination condition. We are now leaking the
> abstraction of the 'state.last_gen' which give me some bad feelings.
Yes, this is one of the minor annoyances I also noticed,
but it's not too bad. I think a followup could be to either:
1. remove this optimization entirely (though I will have to spend
some time reasoning if there are realistic use cases where this
would trigger much earlier than side exhaustion.
2. tweak the logic to instead halting on exactly this commit,
instead halt inside paint_queue_get if:
generation < INFINITY && !FIND_ALL && num_results >= 1
This would change the semantics slightly (but for the better?)
in the the found merge-base could be in the infinite region but
near the finite region and thus would unlock the optimization
as soon as we pass that boundary. But I did not want to include
that change in this series, which is perhaps already getting
too complex.
> We are getting to the point where I'd leave such a thing for a
> follow-up, but since you are needing to re-roll, then this is
> another case where we can move this into the paint_queue_get(). I
> don't think this is me "raising the bar" from earlier recommendations,
> because I was asking for all loop termination to be in the get()
> method, if possible.
>
> But also: I'm not looking at the full method right now to see if
> terminating _at this location in the loop_ is critical. So it may
> very well be impossible to move this into the get() call, in which
> case please ignore this suggestion and use state.last_gen.
I think it's not critical (as I mentioned above) and I think I will
need to follow up on this later.
Thanks,
Kristofer
^ permalink raw reply
* Re: [PATCH v3 8/8] commit-reach: move min_generation check into paint_queue_get()
From: Derrick Stolee @ 2026-06-26 14:58 UTC (permalink / raw)
To: Kristofer Karlsson
Cc: Kristofer Karlsson via GitGitGadget, git, Elijah Newren
In-Reply-To: <CAL71e4PWmVjh5pQATGj1GrwgtWDZOeawKUXbKZ7DZX-DcWuCfw@mail.gmail.com>
On 6/26/2026 10:53 AM, Kristofer Karlsson wrote:
> On Fri, 26 Jun 2026 at 16:42, Derrick Stolee <stolee@gmail.com> wrote:
>>
>>> + 4. Generation cutoff: the dequeued commit's generation is below
>>> + a caller-supplied `min_generation` threshold.
>>
>> Technically, this was always a termination condition of the walk,
>> but now we are correcting the documentation to match. It was just
>> not part of the termination in the dequeue method until now.
>
> You're right, I should perhaps fold it into the first patch instead,
> which would be logically more accurate. Would be an easy thing
> to fix for a v4.
And the remaining condition exposed in this diff isn't included,
either:
>>> flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
>>> if (flags == (PARENT1 | PARENT2)) {
>>> if (!(commit->object.flags & RESULT)) {
>>> @@ -219,7 +224,7 @@ static int paint_down_to_common(struct repository *r,
>>> * descendant of this one.
>>> */
>>> if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
>>> - generation < GENERATION_NUMBER_INFINITY)
>>> + state.last_gen < GENERATION_NUMBER_INFINITY)
>>> break;
>>> }
>>> /* Mark parents of a found merge stale */
>>
>> And here's another termination condition. We are now leaking the
>> abstraction of the 'state.last_gen' which give me some bad feelings.
>
> Yes, this is one of the minor annoyances I also noticed,
> but it's not too bad. I think a followup could be to either:
>
> 1. remove this optimization entirely (though I will have to spend
> some time reasoning if there are realistic use cases where this
> would trigger much earlier than side exhaustion.
>
> 2. tweak the logic to instead halting on exactly this commit,
> instead halt inside paint_queue_get if:
> generation < INFINITY && !FIND_ALL && num_results >= 1
> This would change the semantics slightly (but for the better?)
> in the the found merge-base could be in the infinite region but
> near the finite region and thus would unlock the optimization
> as soon as we pass that boundary. But I did not want to include
> that change in this series, which is perhaps already getting
> too complex.
I'm happy to keep this one out of the series. Perhaps it would
be good for you to finish this series with the current scope
and then for another contributor (me, probably) to do another
round of cleanup/reaction on top. I only say "another
contributor" because new eyes can help to see new things, outside
of a patch diff.
>> We are getting to the point where I'd leave such a thing for a
>> follow-up, but since you are needing to re-roll, then this is
>> another case where we can move this into the paint_queue_get(). I
>> don't think this is me "raising the bar" from earlier recommendations,
>> because I was asking for all loop termination to be in the get()
>> method, if possible.
>>
>> But also: I'm not looking at the full method right now to see if
>> terminating _at this location in the loop_ is critical. So it may
>> very well be impossible to move this into the get() call, in which
>> case please ignore this suggestion and use state.last_gen.
>
> I think it's not critical (as I mentioned above) and I think I will
> need to follow up on this later.
Sounds good.
-Stolee
^ permalink raw reply
* Re: [PATCH v6 00/11] refs: fix "onbranch" conditions
From: Junio C Hamano @ 2026-06-26 15:20 UTC (permalink / raw)
To: Justin Tobler; +Cc: Patrick Steinhardt, git, Karthik Nayak, Jeff King
In-Reply-To: <xmqqse6ae45i.fsf@gitster.g>
Junio C Hamano <gitster@pobox.com> writes:
> Justin Tobler <jltobler@gmail.com> writes:
>
>> On 26/06/25 11:19AM, Patrick Steinhardt wrote:
>>> Changes in v6:
>>> - Drop redundant condition when setting the default for
>>> "core.logallrefupdates".
>>> - Leave breakcrumb for why we lazy-load write options for the "files"
>>> backend.
>>> - Fix commit message typo.
>>
>> Thanks. This version of the series looks good to me.
>>
>> -Justin
>
> Thanks, both. Let's call it ready for 'next' then.
Ah, before I forget, as the focus of the topic shifted dramatically
between v4 and v5, I think we should rename it to something like
'ps/refs-onbranch-fixes' to reflect the fact that is no longer is
about chdir-notify-parent but to fix "onbranch" chicken-and-egg
situation.
^ permalink raw reply
* Re: [PATCH v2 0/2] environment: move excludes_file into repo_config_values
From: Junio C Hamano @ 2026-06-26 15:42 UTC (permalink / raw)
To: Tian Yuchen
Cc: git, cirnovskyv, Christian Couder, Ayush Chandekar,
Olamide Caleb Bello
In-Reply-To: <20260626075037.532164-1-cat@malon.dev>
Tian Yuchen <cat@malon.dev> writes:
> This series continues the libification effort by migrating the global
> string variable 'excludes_file' into 'struct repo_config_values'. Since
> this is a dynamically allocated variable, the migration requires proper
> heap memory management.
This appears here:
https://lore.kernel.org/git/20260626075037.532164-1-cat@malon.dev/
and as you can see, there is no linkage back to the previous round.
The lack of In-Reply-To and References headers unfortunately delays my
automation in marking topics with newer iterations available to be
reviewed when I come back to the keyboard, which happens overnight.
^ permalink raw reply
* Re: [PATCH v2 2/2] environment: move excludes_file into repo_config_values
From: Junio C Hamano @ 2026-06-26 15:43 UTC (permalink / raw)
To: Tian Yuchen
Cc: git, cirnovskyv, Christian Couder, Ayush Chandekar,
Olamide Caleb Bello
In-Reply-To: <20260626075037.532164-3-cat@malon.dev>
Tian Yuchen <cat@malon.dev> writes:
> Continue the libification effort by moving the 'excludes_file' global
> variable into 'struct repo_config_values'.
>
> Since 'excludes_file' is a dynamically allocated string (char *), it
> requires proper memory management. Introduce repo_config_values_clear()
> to safely free the heap memory when repository instance is destroyed.
>
> Note:
>
> - 'if (repo != the_repository)' fallback logic is temporarily added
> in both the getter and the clear function. This prevents calling
> repo_config_values() on uninitialized submodules, which triggers BUG().
>
> - 'attribute_file' is another string variable that was migrated
> earlier. Its FREE_AND_NULL() call is also added to
> repo_config_values_clear().
OK. I think the placement of the new member in repo_config_values
in this round, moving to the spot next to existing attributes_file,
makes more sense than the previous round, too.
Looking good. Shall we mark it as ready for 'next' now?
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox