rev-list: use merge-base --independent algorithm when possible

The --maximal-only option was added to git rev-list in b4e8f60a3c (revision:
add --maximal-only option, 2026-01-22) and the discussion [1] included talks of how 'git rev-list --maximal-only <refs>' acts the same as 'git merge-base --independent <refs>' assuming that no other walk modifiers are provided to the revision walk. And with those assumptions, the merge-base algorithm can be faster if the refs have most of their history shared.

[1]
https://lore.kernel.org/git/[email protected]/

This series updates the revision walk to use the merge-base algorithm when possible. This checks the rev_info struct for options that cause the walk to be different and also looks for negative references. If none of these appear, then the merge-base algorithm is used instead.

The series is broken into three patches that could theoretically be squashed into a single patch.

1. The first demonstrates the equivalence of these two commands via some tests.
2. The second creates a performance test and documents the current behavior.
3. The third updates the implementation and demonstrates the improvement in the case of no walk modifiers.

Thanks, -Stolee

Derrick Stolee (3):
t6600: test --maximal-only and --independent
p6011: add perf test for rev-list --maximal-only
rev-list: use reduce_heads() for --maximal-only

 builtin/rev-list.c               | 59 ++++++++++++++++++++++++++++++++
 t/perf/p6011-rev-list-maximal.sh | 29 ++++++++++++++++
 t/t6000-rev-list-misc.sh         | 31 +++++++++++++++++
 t/t6600-test-reach.sh            | 45 ++++++++++++++++++++++++
 4 files changed, 164 insertions(+)
 create mode 100755 t/perf/p6011-rev-list-maximal.sh

base-commit: ca1db8a0f7dc0dbea892e99f5b37c5fe5861be71
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2082%2Fderrickstolee%2Fmaximal-faster-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2082/derrickstolee/maximal-faster-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2082

gitgitgadget