Re: [PATCH/RFC] Add a --bouquet option to git rev-list

From: Junio C Hamano <gitster@pobox.com>
Date: Dec 1, 2009, 18:21 UTC
Message-ID: <7viqcqzhar.fsf@alter.siamese.dyndns.org>
In-Reply-To: <d77df1110912010931l40472723v80ad675a92d23fa3@mail.gmail.com>

"Nathan W. Panike" <nathan.panike@gmail.com> writes:

Show 8 quoted lines

>>> include_forks ()
>>> {
>>>     local head="$(git show -s --pretty=format:'%H' HEAD)";
>>>     echo "HEAD $(git for-each-ref --format='%(refname)' \
>>>       refs/heads refs/remotes | while read ref; do \
>>>       if test "$(git merge-base HEAD ${ref}^{commit})" != ""; \
>>>               then echo ${ref}; fi; done)"
>>> }

Because you have to traverse the entire history from tips of refs to know if the histories to reach them are disjoint, this is fundamentally a very expensive operation and will not scale to projects with deep histories.

If a low-level support for this kind of thing is necessary, then I do not think it should just be "give me set of refs that is related to HEAD". I suspect that is too inflexible to be useful in other situations.

A command to list refs (i.e. not as rev-list argument that shows list of commits, but as a new feature of for-each-ref) with new criteria might have wider use (I am just thinking aloud). Something like

 - among these refs (you would specify this with --all, --heads, or prefix
   'refs/heads refs/remotes'), list only the ones related to this and that
   ref (here you would give HEAD or whatever you want to check with as
   argument)"; and

 - its counterpart "list the ones that are _not_ related" with the same
   input.

As to the implementation, instead of running get_merge_bases() number of times (a naive implementation would be O(n*m), I guess), I think it may make sense to run the traversal in parallel, similar to the way done in show-branches (but the termination condition would be different).