Re: [PATCH v4 04/10] commit: use generations in paint_down_to_common()

[Jakub Narebski <jnareb@gmail.com>]

Jakub Narebski <jnareb@gmail.com> writes:
> Junio C Hamano <gitster@pobox.com> writes:
>> Derrick Stolee <dstolee@microsoft.com> 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