Re: [PATCH 10/10] xdiff: move xdl_cleanup_records() from xprepare.c to xdiffi.c

[Phillip Wood <phillip.wood123@gmail.com>]

On 21/01/2026 15:01, Phillip Wood wrote:
> Hi Ezekiel
> 
> On 02/01/2026 18:52, Ezekiel Newren via GitGitGadget wrote:
>> From: Ezekiel Newren <ezekielnewren@gmail.com>
>>
>> Only the classic diff uses xdl_cleanup_records(). Move it,
>> xdl_clean_mmatch(), and the macros to xdiffi.c and call
>> xdl_cleanup_records() inside of xdl_do_classic_diff(). This better
>> organizes the code related to the classic diff.
> 
> I think calling xdl_cleanup_records() from inside xdl_do_classic_diff() 
> makes sense. I don't have a strong opinion either way on the code 
> movement.

Having thought about it I'm not so sure the code movement here makes 
sense. Having utility functions in a separate file is perfectly 
reasonable (afterall xprepare.c existed before the histogram and 
patientce algorithms were added). It's not like the code xdiffi.c is 
only about the myers diff there is generic code for diff sliders in 
there as well.

Thanks

Phillip

  You should remove '#include "compat/ivec.h"' from xprepare.c
> if you're moving the only code that uses it out of that file.
> 
> Thanks
> 
> Phillip
> 
>> Signed-off-by: Ezekiel Newren <ezekielnewren@gmail.com>
>> ---
>>   xdiff/xdiffi.c   | 180 ++++++++++++++++++++++++++++++++++++++++++++
>>   xdiff/xprepare.c | 191 +----------------------------------------------
>>   2 files changed, 181 insertions(+), 190 deletions(-)
>>
>> diff --git a/xdiff/xdiffi.c b/xdiff/xdiffi.c
>> index e3196c7245..0f1fd7cf80 100644
>> --- a/xdiff/xdiffi.c
>> +++ b/xdiff/xdiffi.c
>> @@ -21,6 +21,7 @@
>>    */
>>   #include "xinclude.h"
>> +#include "compat/ivec.h"
>>   static size_t get_hash(xdfile_t *xdf, long index)
>>   {
>> @@ -33,6 +34,14 @@ static size_t get_hash(xdfile_t *xdf, long index)
>>   #define XDL_SNAKE_CNT 20
>>   #define XDL_K_HEUR 4
>> +#define XDL_KPDIS_RUN 4
>> +#define XDL_MAX_EQLIMIT 1024
>> +#define XDL_SIMSCAN_WINDOW 100
>> +
>> +#define DISCARD 0
>> +#define KEEP 1
>> +#define INVESTIGATE 2
>> +
>>   typedef struct s_xdpsplit {
>>       long i1, i2;
>>       int min_lo, min_hi;
>> @@ -311,6 +320,175 @@ int xdl_recs_cmp(xdfile_t *xdf1, long off1, long 
>> lim1,
>>   }
>> +static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, 
>> long e) {
>> +    long r, rdis0, rpdis0, rdis1, rpdis1;
>> +
>> +    /*
>> +     * Limits the window that is examined during the similar-lines
>> +     * scan. The loops below stops when action[i - r] == KEEP
>> +     * (line that has no match), but there are corner cases where
>> +     * the loop proceed all the way to the extremities by causing
>> +     * huge performance penalties in case of big files.
>> +     */
>> +    if (i - s > XDL_SIMSCAN_WINDOW)
>> +        s = i - XDL_SIMSCAN_WINDOW;
>> +    if (e - i > XDL_SIMSCAN_WINDOW)
>> +        e = i + XDL_SIMSCAN_WINDOW;
>> +
>> +    /*
>> +     * Scans the lines before 'i' to find a run of lines that either
>> +     * have no match (action[j] == DISCARD) or have multiple matches
>> +     * (action[j] == INVESTIGATE). Note that we always call this
>> +     * function with action[i] == INVESTIGATE, so the current line
>> +     * (i) is already a multimatch line.
>> +     */
>> +    for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
>> +        if (action[i - r] == DISCARD)
>> +            rdis0++;
>> +        else if (action[i - r] == INVESTIGATE)
>> +            rpdis0++;
>> +        else if (action[i - r] == KEEP)
>> +            break;
>> +        else
>> +            BUG("Illegal value for action[i - r]");
>> +    }
>> +    /*
>> +     * If the run before the line 'i' found only multimatch lines,
>> +     * we return false and hence we don't make the current line (i)
>> +     * discarded. We want to discard multimatch lines only when
>> +     * they appear in the middle of runs with nomatch lines
>> +     * (action[j] == DISCARD).
>> +     */
>> +    if (rdis0 == 0)
>> +        return 0;
>> +    for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
>> +        if (action[i + r] == DISCARD)
>> +            rdis1++;
>> +        else if (action[i + r] == INVESTIGATE)
>> +            rpdis1++;
>> +        else if (action[i + r] == KEEP)
>> +            break;
>> +        else
>> +            BUG("Illegal value for action[i + r]");
>> +    }
>> +    /*
>> +     * If the run after the line 'i' found only multimatch lines,
>> +     * we return false and hence we don't make the current line (i)
>> +     * discarded.
>> +     */
>> +    if (rdis1 == 0)
>> +        return false;
>> +    rdis1 += rdis0;
>> +    rpdis1 += rpdis0;
>> +
>> +    return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
>> +}
>> +
>> +struct xoccurrence
>> +{
>> +    size_t file1, file2;
>> +};
>> +
>> +
>> +DEFINE_IVEC_TYPE(struct xoccurrence, xoccurrence);
>> +
>> +
>> +/*
>> + * Try to reduce the problem complexity, discard records that have no
>> + * matches on the other file. Also, lines that have multiple matches
>> + * might be potentially discarded if they appear in a run of 
>> discardable.
>> + */
>> +static int xdl_cleanup_records(xdfenv_t *xe, uint64_t flags) {
>> +    long i;
>> +    size_t nm, mlim;
>> +    xrecord_t *recs;
>> +    uint8_t *action1 = NULL, *action2 = NULL;
>> +    struct IVec_xoccurrence occ;
>> +    bool need_min = !!(flags & XDF_NEED_MINIMAL);
>> +    int ret = 0;
>> +    ptrdiff_t dend1 = xe->xdf1.nrec - 1 - xe->delta_end;
>> +    ptrdiff_t dend2 = xe->xdf2.nrec - 1 - xe->delta_end;
>> +
>> +    IVEC_INIT(occ);
>> +    ivec_zero(&occ, xe->mph_size);
>> +
>> +    for (size_t j = 0; j < xe->xdf1.nrec; j++) {
>> +        size_t mph1 = xe->xdf1.recs[j].minimal_perfect_hash;
>> +        occ.ptr[mph1].file1 += 1;
>> +    }
>> +
>> +    for (size_t j = 0; j < xe->xdf2.nrec; j++) {
>> +        size_t mph2 = xe->xdf2.recs[j].minimal_perfect_hash;
>> +        occ.ptr[mph2].file2 += 1;
>> +    }
>> +
>> +    /*
>> +     * Create temporary arrays that will help us decide if
>> +     * changed[i] should remain false, or become true.
>> +     */
>> +    if (!XDL_CALLOC_ARRAY(action1, xe->xdf1.nrec + 1)) {
>> +        ret = -1;
>> +        goto cleanup;
>> +    }
>> +    if (!XDL_CALLOC_ARRAY(action2, xe->xdf2.nrec + 1)) {
>> +        ret = -1;
>> +        goto cleanup;
>> +    }
>> +
>> +    /*
>> +     * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
>> +     */
>> +    if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
>> +        mlim = XDL_MAX_EQLIMIT;
>> +    for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; 
>> i <= dend1; i++, recs++) {
>> +        nm = occ.ptr[recs->minimal_perfect_hash].file2;
>> +        action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? 
>> INVESTIGATE: KEEP;
>> +    }
>> +
>> +    if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
>> +        mlim = XDL_MAX_EQLIMIT;
>> +    for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; 
>> i <= dend2; i++, recs++) {
>> +        nm = occ.ptr[recs->minimal_perfect_hash].file1;
>> +        action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? 
>> INVESTIGATE: KEEP;
>> +    }
>> +
>> +    /*
>> +     * Use temporary arrays to decide if changed[i] should remain
>> +     * false, or become true.
>> +     */
>> +    xe->xdf1.nreff = 0;
>> +    for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start];
>> +         i <= dend1; i++, recs++) {
>> +        if (action1[i] == KEEP ||
>> +            (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, 
>> i, xe->delta_start, dend1))) {
>> +            xe->xdf1.reference_index[xe->xdf1.nreff++] = i;
>> +            /* changed[i] remains false, i.e. keep */
>> +        } else
>> +            xe->xdf1.changed[i] = true;
>> +            /* i.e. discard */
>> +    }
>> +
>> +    xe->xdf2.nreff = 0;
>> +    for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start];
>> +         i <= dend2; i++, recs++) {
>> +        if (action2[i] == KEEP ||
>> +            (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, 
>> i, xe->delta_start, dend2))) {
>> +            xe->xdf2.reference_index[xe->xdf2.nreff++] = i;
>> +            /* changed[i] remains false, i.e. keep */
>> +        } else
>> +            xe->xdf2.changed[i] = true;
>> +            /* i.e. discard */
>> +    }
>> +
>> +cleanup:
>> +    xdl_free(action1);
>> +    xdl_free(action2);
>> +    ivec_free(&occ);
>> +
>> +    return ret;
>> +}
>> +
>> +
>>   int xdl_do_classic_diff(xdfenv_t *xe, uint64_t flags)
>>   {
>>       long ndiags;
>> @@ -318,6 +496,8 @@ int xdl_do_classic_diff(xdfenv_t *xe, uint64_t flags)
>>       xdalgoenv_t xenv;
>>       int res;
>> +    xdl_cleanup_records(xe, flags);
>> +
>>       /*
>>        * Allocate and setup K vectors to be used by the differential
>>        * algorithm.
>> diff --git a/xdiff/xprepare.c b/xdiff/xprepare.c
>> index b53a3b80c4..3f555e29f4 100644
>> --- a/xdiff/xprepare.c
>> +++ b/xdiff/xprepare.c
>> @@ -24,14 +24,6 @@
>>   #include "compat/ivec.h"
>> -#define XDL_KPDIS_RUN 4
>> -#define XDL_MAX_EQLIMIT 1024
>> -#define XDL_SIMSCAN_WINDOW 100
>> -
>> -#define DISCARD 0
>> -#define KEEP 1
>> -#define INVESTIGATE 2
>> -
>>   typedef struct s_xdlclass {
>>       struct s_xdlclass *next;
>>       xrecord_t rec;
>> @@ -50,8 +42,6 @@ typedef struct s_xdlclassifier {
>>   } xdlclassifier_t;
>> -
>> -
>>   static int xdl_init_classifier(xdlclassifier_t *cf, long size, long 
>> flags) {
>>       memset(cf, 0, sizeof(xdlclassifier_t));
>> @@ -186,175 +176,6 @@ void xdl_free_env(xdfenv_t *xe) {
>>   }
>> -static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, 
>> long e) {
>> -    long r, rdis0, rpdis0, rdis1, rpdis1;
>> -
>> -    /*
>> -     * Limits the window that is examined during the similar-lines
>> -     * scan. The loops below stops when action[i - r] == KEEP
>> -     * (line that has no match), but there are corner cases where
>> -     * the loop proceed all the way to the extremities by causing
>> -     * huge performance penalties in case of big files.
>> -     */
>> -    if (i - s > XDL_SIMSCAN_WINDOW)
>> -        s = i - XDL_SIMSCAN_WINDOW;
>> -    if (e - i > XDL_SIMSCAN_WINDOW)
>> -        e = i + XDL_SIMSCAN_WINDOW;
>> -
>> -    /*
>> -     * Scans the lines before 'i' to find a run of lines that either
>> -     * have no match (action[j] == DISCARD) or have multiple matches
>> -     * (action[j] == INVESTIGATE). Note that we always call this
>> -     * function with action[i] == INVESTIGATE, so the current line
>> -     * (i) is already a multimatch line.
>> -     */
>> -    for (r = 1, rdis0 = 0, rpdis0 = 1; (i - r) >= s; r++) {
>> -        if (action[i - r] == DISCARD)
>> -            rdis0++;
>> -        else if (action[i - r] == INVESTIGATE)
>> -            rpdis0++;
>> -        else if (action[i - r] == KEEP)
>> -            break;
>> -        else
>> -            BUG("Illegal value for action[i - r]");
>> -    }
>> -    /*
>> -     * If the run before the line 'i' found only multimatch lines,
>> -     * we return false and hence we don't make the current line (i)
>> -     * discarded. We want to discard multimatch lines only when
>> -     * they appear in the middle of runs with nomatch lines
>> -     * (action[j] == DISCARD).
>> -     */
>> -    if (rdis0 == 0)
>> -        return 0;
>> -    for (r = 1, rdis1 = 0, rpdis1 = 1; (i + r) <= e; r++) {
>> -        if (action[i + r] == DISCARD)
>> -            rdis1++;
>> -        else if (action[i + r] == INVESTIGATE)
>> -            rpdis1++;
>> -        else if (action[i + r] == KEEP)
>> -            break;
>> -        else
>> -            BUG("Illegal value for action[i + r]");
>> -    }
>> -    /*
>> -     * If the run after the line 'i' found only multimatch lines,
>> -     * we return false and hence we don't make the current line (i)
>> -     * discarded.
>> -     */
>> -    if (rdis1 == 0)
>> -        return false;
>> -    rdis1 += rdis0;
>> -    rpdis1 += rpdis0;
>> -
>> -    return rpdis1 * XDL_KPDIS_RUN < (rpdis1 + rdis1);
>> -}
>> -
>> -struct xoccurrence
>> -{
>> -    size_t file1, file2;
>> -};
>> -
>> -
>> -DEFINE_IVEC_TYPE(struct xoccurrence, xoccurrence);
>> -
>> -
>> -/*
>> - * Try to reduce the problem complexity, discard records that have no
>> - * matches on the other file. Also, lines that have multiple matches
>> - * might be potentially discarded if they appear in a run of 
>> discardable.
>> - */
>> -static int xdl_cleanup_records(xdfenv_t *xe, uint64_t flags) {
>> -    long i;
>> -    size_t nm, mlim;
>> -    xrecord_t *recs;
>> -    uint8_t *action1 = NULL, *action2 = NULL;
>> -    struct IVec_xoccurrence occ;
>> -    bool need_min = !!(flags & XDF_NEED_MINIMAL);
>> -    int ret = 0;
>> -    ptrdiff_t dend1 = xe->xdf1.nrec - 1 - xe->delta_end;
>> -    ptrdiff_t dend2 = xe->xdf2.nrec - 1 - xe->delta_end;
>> -
>> -    IVEC_INIT(occ);
>> -    ivec_zero(&occ, xe->mph_size);
>> -
>> -    for (size_t j = 0; j < xe->xdf1.nrec; j++) {
>> -        size_t mph1 = xe->xdf1.recs[j].minimal_perfect_hash;
>> -        occ.ptr[mph1].file1 += 1;
>> -    }
>> -
>> -    for (size_t j = 0; j < xe->xdf2.nrec; j++) {
>> -        size_t mph2 = xe->xdf2.recs[j].minimal_perfect_hash;
>> -        occ.ptr[mph2].file2 += 1;
>> -    }
>> -
>> -    /*
>> -     * Create temporary arrays that will help us decide if
>> -     * changed[i] should remain false, or become true.
>> -     */
>> -    if (!XDL_CALLOC_ARRAY(action1, xe->xdf1.nrec + 1)) {
>> -        ret = -1;
>> -        goto cleanup;
>> -    }
>> -    if (!XDL_CALLOC_ARRAY(action2, xe->xdf2.nrec + 1)) {
>> -        ret = -1;
>> -        goto cleanup;
>> -    }
>> -
>> -    /*
>> -     * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
>> -     */
>> -    if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
>> -        mlim = XDL_MAX_EQLIMIT;
>> -    for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; 
>> i <= dend1; i++, recs++) {
>> -        nm = occ.ptr[recs->minimal_perfect_hash].file2;
>> -        action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? 
>> INVESTIGATE: KEEP;
>> -    }
>> -
>> -    if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
>> -        mlim = XDL_MAX_EQLIMIT;
>> -    for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; 
>> i <= dend2; i++, recs++) {
>> -        nm = occ.ptr[recs->minimal_perfect_hash].file1;
>> -        action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? 
>> INVESTIGATE: KEEP;
>> -    }
>> -
>> -    /*
>> -     * Use temporary arrays to decide if changed[i] should remain
>> -     * false, or become true.
>> -     */
>> -    xe->xdf1.nreff = 0;
>> -    for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start];
>> -         i <= dend1; i++, recs++) {
>> -        if (action1[i] == KEEP ||
>> -            (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, 
>> i, xe->delta_start, dend1))) {
>> -            xe->xdf1.reference_index[xe->xdf1.nreff++] = i;
>> -            /* changed[i] remains false, i.e. keep */
>> -        } else
>> -            xe->xdf1.changed[i] = true;
>> -            /* i.e. discard */
>> -    }
>> -
>> -    xe->xdf2.nreff = 0;
>> -    for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start];
>> -         i <= dend2; i++, recs++) {
>> -        if (action2[i] == KEEP ||
>> -            (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, 
>> i, xe->delta_start, dend2))) {
>> -            xe->xdf2.reference_index[xe->xdf2.nreff++] = i;
>> -            /* changed[i] remains false, i.e. keep */
>> -        } else
>> -            xe->xdf2.changed[i] = true;
>> -            /* i.e. discard */
>> -    }
>> -
>> -cleanup:
>> -    xdl_free(action1);
>> -    xdl_free(action2);
>> -    ivec_free(&occ);
>> -
>> -    return ret;
>> -}
>> -
>> -
>>   /*
>>    * Early trim initial and terminal matching records.
>>    */
>> @@ -414,19 +235,9 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, 
>> xpparam_t const *xpp,
>>       }
>>       xe->mph_size = cf.count;
>> +    xdl_free_classifier(&cf);
>>       xdl_trim_ends(xe);
>> -    if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
>> -        (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
>> -        xdl_cleanup_records(xe, xpp->flags) < 0) {
>> -
>> -        xdl_free_ctx(&xe->xdf2);
>> -        xdl_free_ctx(&xe->xdf1);
>> -        xdl_free_classifier(&cf);
>> -        return -1;
>> -    }
>> -
>> -    xdl_free_classifier(&cf);
>>       return 0;
>>   }
> 
>