Re: [BUG] git-rev-list: --topo-order --boundary and --max-count

[Junio C Hamano <junkio@cox.net>]

Junio C Hamano <junkio@cox.net> writes:

> "Santi Béjar" <sbejar@gmail.com> writes:
>
>>  the --topo-order does not play well with --boundary and --max-count.
>>
>> $ git-rev-list --boundary --max-count=50 5ced0 | wc -l
>> 56
>> $ git-rev-list --topo-order --boundary --max-count=50 5ced0 | wc -l
>> 8846
>>
>> (5ced0 is git.git's master). I think it should be 56 for both. It
>> presents this behaviour since c4025103fa, when was added --boundary
>> support for git-rev-list --max-count and --max-age.
>
> I think the code that does --boundary when the list is limited
> with --max-count is not quite right, even without topo-order.
> Only when the traversal is not limited, the code happens to work
> correctly because in that case alone we pick up positive commits
> one by one up to the specified count, and do not place anything
> other than their immediate parents in the list.

This is not even correct.  Let's see an extreme example.
Suppose you have something like this:

 ---o---o---o---x---A
 
   ---o---o---o---y---B

and think about what "rev-list --boundary --max-count=1 A B"
should return.  It does not matter how branches A and B are
related in the past because we are showing only one.

Without --boundary, it is clear we will show B (time flows from
left to right).  With --boundary, the current code would show B,
and show -y and -A as boundaries, and I think that is wrong.

Originally --boundary was invented for the specific purpose of
supporting thin packs.  It worked on the set of commits
resulting from a limited traversal (that is, you have at least
one negative, iow UNINTERESTING, commit and one or more positive
commits), and it showed the negative commit that is a parent of
a positive commit.

There are two primary users of --boundary right now.  gitk wants
to show where the partial traversal ends (although it can figure
it out itself without help from --boundary), and thin pack
generation wants to have it upfront so that it can see which
trees and blobs can be used as the bases of delta.  In both
cases, the semantics desired is to show commits that are _not_
included in the usual (i.e. non --boundary) results that are
immediate parents of the commits that are included in the
result.

So with that definition, the above example should show B and
then -y as boundary, and should not even talk about A nor -x.
This may affect the git-bundle's computation of references
included in the bundle (I think the current code assumes that if
you do "git bundle --max-count=1 A B" the resulting bundle says
its set of tips consists of A and B) but if that is broken it
also needs to be fixed.