Re: [PATCH v3 4/6] xdiff/xdl_cleanup_records: make limits more clear

[Junio C Hamano <gitster@pobox.com>]

Junio C Hamano <gitster@pobox.com> writes:

> "Ezekiel Newren via GitGitGadget" <gitgitgadget@gmail.com> writes:
>
>> From: Ezekiel Newren <ezekielnewren@gmail.com>
>>
>> Make the handling of per-file limits and the minimal-case clearer.
>>   * Use explicit per-file limit variables (mlim1, mlim2) and initialize
>>     them.
>>   * The additional condition `!need_min` is redudant now, remove it.
>> Best viewed with --color-words.
>>
>> Signed-off-by: Ezekiel Newren <ezekielnewren@gmail.com>
>> ---
>>  xdiff/xprepare.c | 19 ++++++++++++-------
>>  1 file changed, 12 insertions(+), 7 deletions(-)
>
> t4071 and t8015 do not like this step, even though they are happy
> with 1-3/6 applied.
>
>
>> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
>> index 386668a92d..2cf1f8d1a8 100644
>> --- a/xdiff/xprepare.c
>> +++ b/xdiff/xprepare.c
>> @@ -268,7 +268,7 @@ static bool xdl_clean_mmatch(uint8_t const *action, ptrdiff_t i, ptrdiff_t s, pt
>>   * might be potentially discarded if they appear in a run of discardable.
>>   */
>>  static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
>> -	ptrdiff_t i, nm, mlim;
>> +	ptrdiff_t i, nm, mlim1, mlim2;

Ah, the problem may manifest itself in this step in the series, but
the root cause might be before this step.  ptrdiff_t is signed and
that is the type used for mlim/mlim1/mlim2 here, and before this
series these counters count in "long" that is signed.

>> +	if (need_min) {
>> +		/* i.e. infinity */
>> +		mlim1 = SIZE_MAX;
>> +		mlim2 = SIZE_MAX;

But SIZE_MAX is the maximum that a size_t (unsigned) can take.  No
wonder assigning it to ptrdiff_t and assuming that any other
sensible ptrdiff_t value can ever reach it.  Instead, this
essentially assigns -1 to mlim1 and mlim2 when need_min is true.

>> +	} else {
>> +		mlim1 = XDL_MIN(xdl_bogosqrt(xdf1->nrec), XDL_MAX_EQLIMIT);
>> +		mlim2 = XDL_MIN(xdl_bogosqrt(xdf2->nrec), XDL_MAX_EQLIMIT);

This side I do not think has much to do with the breakage, but the
way XDL_MIN() is implemented, it must be noted that xdl_bogosqrt()
is called twice on the same value with this rewrite ...

>> +	}
>> +
>>  	/*
>>  	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
>>  	 */
>> -	if ((mlim = (long)xdl_bogosqrt((uint64_t)xdf1->nrec)) > XDL_MAX_EQLIMIT)
>> -		mlim = XDL_MAX_EQLIMIT;

... as opposed to computing the value only once, in the original.

>>  	for (i = xdf1->dstart; i <= xdf1->dend; i++) {
>>  		size_t mph1 = xdf1->recs[i].minimal_perfect_hash;
>>  		rcrec = cf->rcrecs[mph1];
>>  		nm = rcrec ? rcrec->len2 : 0;
>> -		action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;

So the original said, "if nm is not zero and need_min is true, do
not bother comparing nm with anything, and always use KEEP.  If
need_min is false, we use INVESTIGAGE only when nm is large enough,
otherwise KEEP.

>> +		action1[i] = (nm == 0) ? DISCARD: nm >= mlim1 ? INVESTIGATE: KEEP;

Updated code, when nm is not zero, does something different.  if
need_min is true, mlim1 is set to -1 and presumably nm is a count or
length that is bounded on its lower end with 0, so it is larger than
mlim1 (== -1), and we always take INVESTIGATE and never kEEP.

So the rewritten code is broken when need_min is true?

I suspect the remainder of the patch is broken exactly the same way,
so the remedy would be similar?

>>  	}
>>  
>> -	if ((mlim = (long)xdl_bogosqrt((uint64_t)xdf2->nrec)) > XDL_MAX_EQLIMIT)
>> -		mlim = XDL_MAX_EQLIMIT;
>>  	for (i = xdf2->dstart; i <= xdf2->dend; i++) {
>>  		size_t mph2 = xdf2->recs[i].minimal_perfect_hash;
>>  		rcrec = cf->rcrecs[mph2];
>>  		nm = rcrec ? rcrec->len1 : 0;
>> -		action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
>> +		action2[i] = (nm == 0) ? DISCARD: nm >= mlim2 ? INVESTIGATE: KEEP;
>>  	}
>>  
>>  	/*