* Re: [PATCH v3 0/8] commit-reach: terminate merge-base walk when one side is exhausted
From: Junio C Hamano @ 2026-06-26 16:36 UTC (permalink / raw)
To: Kristofer Karlsson via GitGitGadget
Cc: git, Derrick Stolee, Elijah Newren, Kristofer Karlsson
In-Reply-To: <pull.2149.v3.git.1782479286.gitgitgadget@gmail.com>
"Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>
writes:
> 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.
I am getting this failure standalone, when applied on the same base
as where v2 was applied earlier. For now I'll eject it from 'seen'.
expecting success of 6600.12 'get_merge_bases_many':
cat >input <<-\EOF &&
A:commit-5-7
X:commit-4-8
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
BUG: commit-reach.c:152: bad generation skip 9 > 8 at 772be737f220103f706a39013c0d115009feefec
not ok 12 - get_merge_bases_many
#
# cat >input <<-\EOF &&
# A:commit-5-7
# X:commit-4-8
^ permalink raw reply
* Re: [PATCH RFC v2 2/2] Move libgit.a sources into separate "lib/" directory
From: Johannes Schindelin @ 2026-06-26 16:01 UTC (permalink / raw)
To: Patrick Steinhardt
Cc: git, brian m. carlson, Junio C Hamano, Elijah Newren,
Derrick Stolee, Phillip Wood
In-Reply-To: <20260622-pks-libgit-in-subdir-v2-2-cb946c51ee7b@pks.im>
Hi Patrick,
On Mon, 22 Jun 2026, Patrick Steinhardt wrote:
> diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
> index cf341d74db..a8402babd9 100644
> --- a/.github/workflows/main.yml
> +++ b/.github/workflows/main.yml
> @@ -179,7 +179,7 @@ jobs:
> uses: actions/checkout@v6
> with:
> repository: 'microsoft/vcpkg'
> - path: 'compat/vcbuild/vcpkg'
> + path: 'lib/compat/vcbuild/vcpkg'
> - name: download vcpkg artifacts
> uses: git-for-windows/get-azure-pipelines-artifact@v0
> with:
Please also adopt:
-- snip --
From 1d09a51d426bd3592e4f4b0331f7715ab3b5d502 Mon Sep 17 00:00:00 2001
From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Fri, 26 Jun 2026 14:39:19 +0200
Subject: [PATCH] fixup??? Move libgit.a sources into separate "lib/" directory
Turns out that there was one path that was forgotten to be adjusted.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
---
.github/workflows/main.yml | 1 +
1 file changed, 1 insertion(+)
diff --git a/.github/workflows/main.yml b/.github/workflows/main.yml
index 29d2057bde4b..57ad4ba64f67 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -188,6 +188,7 @@ jobs:
with:
repository: git/git
definitionId: 9
+ path: lib/compat
- name: add msbuild to PATH
uses: microsoft/setup-msbuild@v3
- name: copy dlls to root
-- snap --
This is needed to fix the `vs-build` job, see
https://github.com/git-for-windows/git/actions/runs/28242360731 for proof
that it's now working.
Thank you,
Johannes
> @@ -189,11 +189,11 @@ jobs:
> uses: microsoft/setup-msbuild@v3
> - name: copy dlls to root
> shell: cmd
> - run: compat\vcbuild\vcpkg_copy_dlls.bat release
> + run: lib\compat\vcbuild\vcpkg_copy_dlls.bat release
> - name: generate Visual Studio solution
> shell: bash
> run: |
> - cmake `pwd`/contrib/buildsystems/ -DCMAKE_PREFIX_PATH=`pwd`/compat/vcbuild/vcpkg/installed/x64-windows \
> + cmake `pwd`/contrib/buildsystems/ -DCMAKE_PREFIX_PATH=`pwd`/lib/compat/vcbuild/vcpkg/installed/x64-windows \
> -DNO_GETTEXT=YesPlease -DPERL_TESTS=OFF -DPYTHON_TESTS=OFF -DCURL_NO_CURL_CMAKE=ON
> - name: MSBuild
> run: msbuild git.sln -property:Configuration=Release -property:Platform=x64 -maxCpuCount:4 -property:PlatformToolset=v142
> @@ -201,7 +201,7 @@ jobs:
> shell: bash
> env:
> MSVC: 1
> - VCPKG_ROOT: ${{github.workspace}}\compat\vcbuild\vcpkg
> + VCPKG_ROOT: ${{github.workspace}}\lib\compat\vcbuild\vcpkg
> run: |
> mkdir -p artifacts &&
> eval "$(make -n artifacts-tar INCLUDE_DLLS_IN_ARTIFACTS=YesPlease ARTIFACTS_DIRECTORY=artifacts NO_GETTEXT=YesPlease 2>&1 | grep ^tar)"
> [...]
^ permalink raw reply related
* [PATCH] rust: validate object map insert algorithms
From: Feng Wu via GitGitGadget @ 2026-06-26 15:58 UTC (permalink / raw)
To: git; +Cc: Feng Wu, Feng Wu
From: Feng Wu <wufengwufengwufeng@gmail.com>
The loose object map stores entries keyed by the repository's storage
hash and the compatible hash. ObjectMap::insert() accepts its two object
IDs in either order, but it currently checks only whether oid1 uses the
compatible hash algorithm. If it does not, oid2 is assumed to be the
compatible ID without validating oid2's algorithm.
That means callers can pass two IDs with the same algorithm, or an ID
using an unknown algorithm, and have one of them silently treated as the
storage ID. This does not match the map invariant that each entry must
contain exactly one storage hash and one compatible hash.
Make the invariant explicit by decoding both object ID algorithms and
rejecting unknown or mismatched pairs before inserting anything. Introduce
ObjectMapInsertError with InvalidHashAlgorithm and MismatchedAlgorithms
variants for clear error reporting.
Update the existing tests to unwrap successful insertions, and add tests
for same-algorithm and unknown-algorithm inputs.
Signed-off-by: Feng Wu <wufengwufengwufeng@gmail.com>
---
rust: validate object map insert algorithms
ObjectMap::insert() accepts a storage OID and a compatible OID in either
order, but it currently checks whether oid1 uses the compatible
algorithm, and if not, assumes oid2 is the compatible one without
validating oid2.
That means inputs with two OIDs using the same hash algorithm, or an OID
using an unknown hash algorithm, are accepted and one of them is
silently treated as the storage OID. This breaks the object map
invariant that each entry must contain exactly one storage hash and one
compatible hash.
Teach ObjectMap::insert() to decode and validate both OID algorithms
before inserting anything. The function now accepts only the two valid
permutations: (storage, compat) and (compat, storage). Unknown
algorithms and mismatched algorithm pairs are rejected via
ObjectMapInsertError.
The tests cover successful insertion in either order, same-algorithm
input, and unknown-algorithm input.
Tested with:
* cargo fmt --all -- --check
* git diff --check
* cargo test
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-2350%2Fwufengwind%2Fobject-map-insert-validation-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-2350/wufengwind/object-map-insert-validation-v1
Pull-Request: https://github.com/git/git/pull/2350
src/loose.rs | 79 ++++++++++++++++++++++++++++++++++++++++++++++++----
1 file changed, 73 insertions(+), 6 deletions(-)
diff --git a/src/loose.rs b/src/loose.rs
index 24accf9c33..8f6c1fb40e 100644
--- a/src/loose.rs
+++ b/src/loose.rs
@@ -510,6 +510,17 @@ pub struct ObjectMap {
batch: Option<ObjectMemoryMap>,
}
+#[derive(Debug, Clone, Copy, Eq, PartialEq)]
+pub enum ObjectMapInsertError {
+ InvalidHashAlgorithm(u32),
+ MismatchedAlgorithms {
+ storage: HashAlgorithm,
+ compat: HashAlgorithm,
+ oid1: HashAlgorithm,
+ oid2: HashAlgorithm,
+ },
+}
+
impl ObjectMap {
/// Create a new `ObjectMap` with the given hash algorithms.
///
@@ -585,19 +596,39 @@ impl ObjectMap {
///
/// If `write` is true and there is a batch started, write the object into the batch as well as
/// into the memory map.
- pub fn insert(&mut self, oid1: &ObjectID, oid2: &ObjectID, kind: MapType, write: bool) {
- let (compat_oid, storage_oid) =
- if HashAlgorithm::from_u32(oid1.algo) == Some(self.mem.compat) {
+ pub fn insert(
+ &mut self,
+ oid1: &ObjectID,
+ oid2: &ObjectID,
+ kind: MapType,
+ write: bool,
+ ) -> Result<(), ObjectMapInsertError> {
+ let oid1_algo = HashAlgorithm::from_u32(oid1.algo)
+ .ok_or(ObjectMapInsertError::InvalidHashAlgorithm(oid1.algo))?;
+ let oid2_algo = HashAlgorithm::from_u32(oid2.algo)
+ .ok_or(ObjectMapInsertError::InvalidHashAlgorithm(oid2.algo))?;
+
+ let (storage_oid, compat_oid) =
+ if oid1_algo == self.mem.storage && oid2_algo == self.mem.compat {
(oid1, oid2)
- } else {
+ } else if oid1_algo == self.mem.compat && oid2_algo == self.mem.storage {
(oid2, oid1)
+ } else {
+ return Err(ObjectMapInsertError::MismatchedAlgorithms {
+ storage: self.mem.storage,
+ compat: self.mem.compat,
+ oid1: oid1_algo,
+ oid2: oid2_algo,
+ });
};
+
Self::insert_into(&mut self.mem, storage_oid, compat_oid, kind);
if write {
if let Some(ref mut batch) = self.batch {
Self::insert_into(batch, storage_oid, compat_oid, kind);
}
}
+ Ok(())
}
fn insert_into(
@@ -729,9 +760,9 @@ mod tests {
if *swap {
// Insert the item into the batch arbitrarily based on the type. This tests that
// we can specify either order and we'll do the right thing.
- map.insert(&s256, &s1, *kind, write);
+ map.insert(&s256, &s1, *kind, write).unwrap();
} else {
- map.insert(&s1, &s256, *kind, write);
+ map.insert(&s1, &s256, *kind, write).unwrap();
}
}
@@ -873,6 +904,42 @@ mod tests {
);
}
+ #[test]
+ fn refuses_insert_with_mismatched_algorithms() {
+ let mut map = ObjectMap::new(HashAlgorithm::SHA256, HashAlgorithm::SHA1);
+ let entries = test_entries();
+ let s256 = sha256_oid(entries[0].2);
+ let s256_other = sha256_oid(entries[1].2);
+ let s1 = sha1_oid(entries[0].1);
+ let s1_other = sha1_oid(entries[1].1);
+
+ assert!(map.insert(&s256, &s1, MapType::LooseObject, false).is_ok());
+ assert!(matches!(
+ map.insert(&s256, &s256_other, MapType::LooseObject, false),
+ Err(super::ObjectMapInsertError::MismatchedAlgorithms { .. })
+ ));
+ assert!(matches!(
+ map.insert(&s1, &s1_other, MapType::LooseObject, false),
+ Err(super::ObjectMapInsertError::MismatchedAlgorithms { .. })
+ ));
+ }
+
+ #[test]
+ fn refuses_insert_with_unknown_algorithm() {
+ let mut map = ObjectMap::new(HashAlgorithm::SHA256, HashAlgorithm::SHA1);
+ let entries = test_entries();
+ let s1 = sha1_oid(entries[0].1);
+ let invalid_oid = ObjectID {
+ hash: [0xffu8; 32],
+ algo: 99,
+ };
+
+ assert_eq!(
+ map.insert(&invalid_oid, &s1, MapType::LooseObject, false),
+ Err(super::ObjectMapInsertError::InvalidHashAlgorithm(99))
+ );
+ }
+
#[test]
fn looks_up_known_oids_correctly() {
let map = test_map(false);
base-commit: ab776a62a78576513ee121424adb19597fbb7613
--
gitgitgadget
^ permalink raw reply related
* 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
* 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 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 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 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: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 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 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 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 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 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 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: 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 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: [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: 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
* [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
* [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 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 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 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 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
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