Jakub Narebski <jnareb@xxxxxxxxx> writes:
> Junio C Hamano <gitster@xxxxxxxxx> writes:
>> Derrick Stolee <dstolee@xxxxxxxxxxxxx> writes:
[...]
>>> +int compare_commits_by_gen_then_commit_date(const void *a_, const void *b_, void *unused)
>>> +{
>>> + const struct commit *a = a_, *b = b_;
>>> +
>>> + /* newer commits first */
>>> + if (a->generation < b->generation)
>>> + return 1;
>>> + else if (a->generation > b->generation)
>>> + return -1;
>>
>> ... this does not check if a->generation is _ZERO or _INF.
>>
>> Both being _MAX is OK (the control will fall through and use the
>> dates below). One being _MAX and the other being a normal value is
>> also OK (the above comparisons will declare the commit with _MAX is
>> farther than less-than-max one from a root).
>>
>> Or is the assumption that if one has _ZERO, that must have come from
>> an ancient commit-graph file and none of the commits have anything
>> but _ZERO?
>
> There is stronger and weaker version of the negative-cut criteria based
> on generation numbers.
>
> The strong criteria:
>
> if A != B and gen(A) <= gen(B), then A cannot reach B
>
> The weaker criteria:
>
> if gen(A) < gen(B), then A cannot reach B
>
>
> Because commit-graph is closed under reachability, this means that
>
> if A is in commit graph, and B is outside of it, then A cannot reach B
>
> If A is in commit graph, then either _MAX >= gen(A) >= 1,
> or gen(A) == _ZERO. Because _INFINITY > _MAX > _ZERO, then we have
>
> if _MAX >= gen(A) >= 1 || gen(A) == 0, and gen(B) == _INFINITY
> then A cannot reach B
>
> which also fullfils the weaker criteria
>
> if gen(A) < gen(B), then A cannot reach B
>
>
> If both A and B are outside commit-graph, i.e. gen(A) = gen(B) = _INFINITY,
> or if both A and B have gen(A) = gen(B) = _MAX,
> or if both A and B come from old commit graph with gen(A) = gen(B) =_ZERO,
> then we cannot say anything about reachability... and weak criteria
> also does not say anything about reachability.
>
>
> Maybe the following ASCII table would make it clear.
>
> | gen(B)
> | ................................ :::::::
> gen(A) | _INFINITY | _MAX | larger | smaller | _ZERO
> -------------+-----------+----------+----------+----------+--------
> _INFINITY | = | > | > | > | >
> _MAX | < Nn | = | > | > | >
> larger | < Nn | < Nn | = n | > | >
> smaller | < Nn | < Nn | < Nn | = n | >
> _ZERO | < Nn | < Nn | < Nn | < Nn | =
>
> Here "n" denotes stronger condition, and "N" denotes weaker condition.
> We have _INFINITY > _MAX > larger > smaller > _ZERO.
>
>
> NOTE however that it is a *tradeoff*. Using weaker criteria, with
> strict inequality, means that we don't need to handle _INFINITY, _MAX
> and _ZERO corner-cases in a special way; but it also means that we would
> walk slightly more commits than if we used stronger criteria, with less
> or equals.
Actually, if we look at the table above, it turns out that we can use
the stronger version of negative-cut criteria without special-casing all
the possible combinations. Just use stronger criteria on normal range,
weaker criteria if any of generation numbers is special generation
number.
if _MAX > gen(A) > _ZERO and
_MAX > gen(B) > _ZERO then
if A != B and gen(A) <= gen(B) then
A cannot reach B
else
A can reach B
else /* at least one special case */
if gen(A) < gen(B) then
A cannot reach B
else
A can reach B
NOTE that it specifically does not matter for created here
compare_commits_by_gen_then_commit_date(), as it requires strict
inequality for sorting - which using weak criteria explains why we don't
need any special cases in the code here.
Best,
--
Jakub Narębski
