From: Derrick Stolee <stolee@gmail.com>
Date: Thu, 22 Jan 2026 22:15:55 GMT
Subject: Re: [PATCH v2] revision: add --maximal-only option
Message-ID: <7daff220-f93a-463a-b586-dd876b51edae@gmail.com>
In-Reply-To: <xmqqikctl3vj.fsf@gitster.g>

On 1/22/2026 4:44 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>>     My motivation for this feature is very similar to the bundle URI
>>     application. I can get around it by creating a tool that uses git
>>     rev-list --parents and then uses a hashset to collect the parent list
>>     and filter out any commits that ever appear as parents. It would be more
>>     efficient to use Git's native revision-walking feature.
> 
> How does this relate to "git merge-base --independent", or do they
> compute completely different things?

This is the same idea, where among the merge bases, the ones that are
"maximal" to that set are the --independent ones. 
 
The documentation for --independent even uses similar language here:

  In other words, among the commits given, list those which cannot
  be reached from any other.

Unfortunately, it also says "print a minimal subset" which in some
sense is correct by "it cannot be made smaller without losing
information" but we actually choose the maximal set there, not a
minimal set.

The merge-base --independent calculation is basically asking for
the maximal set among commits in the intersection of two (or more)
commit histories. One trick the merge-base calculation does is
that it first looks for the --boundary commits, and then reduces
from within that set. This avoid walking further into the history
than necessary.

You are presenting interesting overlaps of terminology and needs.
One thing that is different about 'git rev-list --maximal-only' with
a list of starting commits is that it wants the maximal set from
the _union_ of the histories, instead of the _intersection_ like
'git merge-base --independent' does.

There is potential for a performance improvement if we converted
the search to be like a merge-base algorithm and checked the
priority queue to see if all elements have the CHILD_VISITED flag.
I think the cost here is that we would need more new logic and
would lose some expressiveness of 'git rev-list'.

For example, one of the applications I mentioned will require a
range request including negative refs, such as

  git rev-list --maximal-only --stdin <<-\EOF
  refs/heads/branch1
  refs/heads/branch2
  ^refs/heads/main
  ^refs/heads/release
  EOF

And this would likely return the tips of the two branches, but
also will detect if one already reaches the other or if one of
'main' or 'release' reaches one or both of them, excluding it
from the maximal set.

Thanks,
-Stolee