Re: [PATCH v7 06/10] t6600: add clock-skew topologies and step counts for edge cases

On Thu, Aug 6, 2026 at 4:05 AM Kristofer Karlsson via GitGitGadget
<[email protected]> wrote:
>
> From: Kristofer Karlsson <[email protected]>
>
> Add topologies and tests exercising paint_down_to_common() under
> clock skew, where commit-date ordering (v1 commit-graph without
> corrected commit dates) violates the topological invariant that
> children are dequeued before parents:

I love the care and attention being put in here to test all the edge
and corner cases.

>
>  - se-*: side-exhaustion fires too early when one paint side fully
>    drains from the queue while a low-date ancestor on the other
>    side is still queued
>
>  - se2-*: side-exhaustion returns a too-deep merge base because
>    the correct (closer) base never receives both paint sides
>
> Also add step counts to the edge-case tests from the previous
> commit, a mixed finite/INFINITY generation topology exercising
> the transition from INFINITY-generation commits to graph-backed
> commits, and step counts for the grid-based merge-base test.

Another nice addition.

>
> Signed-off-by: Kristofer Karlsson <[email protected]>
> ---
>  t/t6600-test-reach.sh | 98 ++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 96 insertions(+), 2 deletions(-)
>
> diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
> index 45aa26cd44..55aa220bb3 100755
> --- a/t/t6600-test-reach.sh
> +++ b/t/t6600-test-reach.sh
> @@ -140,6 +140,48 @@ test_expect_success 'setup' '
>         git branch -f pi-X-br "$pi_x" &&
>         git tag pi-X "$pi_x" &&
>
> +       # Clock-skew topology for side-exhaustion testing.
> +       # D is the correct merge base but has a higher committer date
> +       # than C (its child).  With date ordering, D would be dequeued
> +       # before C, causing side-exhaustion to fire too early.
> +       # Generation ordering prevents this by visiting children
> +       # before parents regardless of dates.
> +       #
> +       #   se-A (date 7000) --> se-C (date 3000) --> se-D (date 5000) --> se-root (date 4000)
> +       #   se-B (date 6000) --> se-D
> +       #
> +       se_root=$(skew_commit 4000 se-root) &&
> +       se_D=$(skew_commit 5000 se-D -p "$se_root") &&
> +       se_C=$(skew_commit 3000 se-C -p "$se_D") &&
> +       se_A=$(skew_commit 7000 se-A -p "$se_C") &&
> +       se_B=$(skew_commit 6000 se-B -p "$se_D") &&
> +       git branch -f se-A "$se_A" &&
> +       git branch -f se-B "$se_B" &&
> +       git tag se-D "$se_D" &&
> +
> +       # Clock-skew topology with redundant ancestor for
> +       # side-exhaustion testing.  MB1 is the correct merge base;
> +       # MB2 is its parent.  A reaches MB2 via E (high date) and
> +       # MB1 via C (low date).  B reaches MB1 via D.  With date
> +       # ordering, side-exhaustion would fire before C is dequeued,
> +       # missing MB1.  Generation ordering ensures both are found.
> +       #
> +       #   se2-A (date 8000) --> se2-C (date 2000) --> se2-MB1 (date 5000) --> se2-MB2 (date 4000) --> se2-root (date 1000)
> +       #   se2-A              --> se2-E (date 6500) --> se2-MB2
> +       #   se2-B (date 7000) --> se2-D (date 6000) --> se2-MB1
> +       #
> +       se2_root=$(skew_commit 1000 se2-root) &&
> +       se2_MB2=$(skew_commit 4000 se2-MB2 -p "$se2_root") &&
> +       se2_MB1=$(skew_commit 5000 se2-MB1 -p "$se2_MB2") &&
> +       se2_C=$(skew_commit 2000 se2-C -p "$se2_MB1") &&
> +       se2_D=$(skew_commit 6000 se2-D -p "$se2_MB1") &&
> +       se2_E=$(skew_commit 6500 se2-E -p "$se2_MB2") &&
> +       se2_A=$(skew_commit 8000 se2-A -p "$se2_C" -p "$se2_E") &&
> +       se2_B=$(skew_commit 7000 se2-B -p "$se2_D") &&
> +       git branch -f se2-A "$se2_A" &&
> +       git branch -f se2-B "$se2_B" &&
> +       git tag se2-MB1 "$se2_MB1" &&
> +
>         git commit-graph write --reachable &&
>         mv .git/objects/info/commit-graph commit-graph-full &&
>         chmod u+w commit-graph-full &&
> @@ -323,7 +365,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' '
> @@ -337,7 +380,34 @@ 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' '
> +       # 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_paint_down_steps 3 3 3 3
>  '
>
>  test_expect_success 'merge-base --all commit-walk steps' '
> @@ -347,6 +417,30 @@ test_expect_success 'merge-base --all commit-walk steps' '
>         test_paint_down_steps 81 80 81 81
>  '
>
> +test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
> +       # Verify correct merge base under clock skew.  se-D (the
> +       # merge base) has a higher date than its child se-C.
> +       # Generation ordering ensures se-C is visited before se-D,
> +       # so P1 paint propagates correctly and se-D is found.
> +       >input &&
> +       git rev-parse se-D >expect &&
> +       run_all_modes git merge-base --all se-A se-B &&
> +       test_paint_down_steps 6 4 6 6
> +'
> +
> +test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
> +       # Verify correct merge base when clock skew could cause a
> +       # too-deep result.  MB1 is the correct merge base; MB2 is
> +       # its ancestor.  A reaches MB2 via E (high date) and MB1
> +       # via C (low date).  Generation ordering ensures C is
> +       # visited before side-exhaustion fires, so MB1 is found
> +       # and remove_redundant correctly discards MB2.
> +       >input &&
> +       git rev-parse se2-MB1 >expect &&
> +       run_all_modes git merge-base --all se2-A se2-B &&
> +       test_paint_down_steps 8 7 8 8
> +'
> +
>  test_expect_success 'reduce_heads' ',
>         cat >input <<-\EOF &&
>         X:commit-1-10
> --
> gitgitgadget

Tests look like they match the commit message, and they look good to me.