Subject: Re: [PATCH v2 07/10] commit-graph.txt: update future work

From: Jakub Narebski <[email-masked]>
Date: Fri, 13 Apr 2018 11:53:21 +0200

Derrick Stolee <[email-masked]> writes:

> On 4/12/2018 5:12 AM, Junio C Hamano wrote:
>> Derrick Stolee <[email-masked]> writes:
>>
>>> +Here is a diagram to visualize the shape of the full commit graph, and
>>> +how different generation numbers relate:
>>> +
>>> +    +-----------------------------------------+
>>> +    | GENERATION_NUMBER_INFINITY = 0xFFFFFFFF |
>>> +    +-----------------------------------------+
>>> +	    |            |      ^
>>> +	    |            |      |
>>> +	    |            +------+
>>> +	    |         [gen(A) = gen(B)]
>>> +	    V
>>> +    +-------------------------------------+
>>> +    | 0 < commit->generation < 0x40000000 |
>>> +    +-------------------------------------+
>>> +	    |            |      ^
>>> +	    |            |      |
>>> +	    |            +------+
>>> +	    |        [gen(A) > gen(B)]
>>> +	    V
>>> +    +-------------------------------------+
>>> +    | GENERATION_NUMBER_ZERO = 0          |
>>> +    +-------------------------------------+
>>> +			 |      ^
>>> +			 |      |
>>> +			 +------+
>>> +		     [gen(A) = gen(B)]
>>
>> It may be just me but all I can read out of the above is that

It's not just you.

>> commit->generation may store 0xFFFFFFFF, a value between 0 and
>> 0x40000000, or 0.  I cannot quite tell what the notation [gen(A)
>> <cmp> gen(B)] is trying to say.  I am guessing "Two generation
>> numbers within the 'valid' range can be compared" is what the second
>> one is trying to say, but it is much less interesting to know that
>> two infinities compare equal than how generation numbers from
>> different classes compare, which cannot be depicted in the above
>> notation, I am afraid.  For example, don't we want to say that a
>> commit with INF can never be reached by a commit with a valid
>> generation number, or something like that?
>
> My intention with the arrows was to demonstrate where parent
> relationships can go, and the generation-number relation between a
> commit A with parent B. Clearly, this diagram is less than helpful.

Perhaps the following table would make the information clearer (perhaps
in addition to the above graph, but without "gen(A) {cmp} gen(B)"
arrows).

I assume that it is possible to have both GENERATION_NUMBER_ZERO and non
zero generation numbers in one repo, perhaps via alternates.  I also
assume that A != B, and that generation numbers (both set, and 0s) are
transitivelu closed under reachability.

gen(A) \   commit B ->   |                     gen(B)
        \-----\          |
commit A       \         | 0xFFFFFFFF | larger   | smaller | 0x00000000
----------------\--------+------------+----------+---------+------------
0xFFFFFFFF               | =            >          >         >
0 < larger  < 0x40000000 | < N          = n        >         >
0 < smaller < 0x40000000 | < N          < N        = n       >
0x00000000               | < N          < N        < N       =

The "<", "=", ">" denotes result of comparison between gen(A) and gen(B).

Generation numbers create a negative-cut filter: "N" and "n" denote
situation where we know from gen(A) and gen(B) that B is not reachable
from A.

As can be seen if we use gen(A) < gen(B) as cutoff, we don't need to
treat "infinity" and "zero" in a special way.

Best,
-- 
Jakub Narębski