Subject: Re: [PATCH v6 00/12] Cleanup xdfile_t and xrecord_t in xdiff.

From: Phillip Wood <[email-masked]>
Date: Fri, 3 Oct 2025 14:47:49 +0100

Hi Ezekiel

On 26/09/2025 23:41, Ezekiel Newren via GitGitGadget wrote:
> Changes since v5.
> 
>   * Address review feedback on commit messages.
>   * Drop commit "xdiff: delete rchg aliasing"
>   * Use DISCARD/KEEP/INVESTIGATE instead of NONE/SOME/TOO_MANY
>   * Fix the word wrapping in the comments of xprepare.c

Thanks for expanding the commit messages, I think the range diff looks 
good. There's a typo in patch 12 (see below) but its not worth 
re-rolling just for that.

> Range-diff vs v5:
> [...] 
>   12:  08a0fceb72 ! 11:  f08782a977 xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
>       @@ Metadata
>        Author: Ezekiel Newren <[email-masked]>
>        
>         ## Commit message ##
>       -    xdiff: use enum macros NONE(0), SOME(1), TOO_MANY(2) in xprepare.c
>       +    xdiff: add macros DISCARD(0), KEEP(1), INVESTIGATE(2) in xprepare.c
>        
>       -    Rename dis1, dis2 to matches1, matches2.
>       +    This commit is refactor-only; no behavior is changed. A future commit
>       +    will use bool literals for changed[i].
>        
>       -    Define macros NONE(0), SOME(1), TOO_MANY(2) as the enum values for
>       -    matches1 and matches2. These states will influence whether changed[i]
>       -    is set to 1 or kept as 0.
>       +    The functions xdl_clean_mmatch() and xdl_cleanup_records() will be
>       +    cleaned up more in a future patch series. The changes to
>       +    xdl_cleanup_records(), in this patch, is just to make it clear why

Not worth a re-roll on its own s/is/are/

Thanks for working on this

Phillip

>       +    `char rchg` is refactored to `bool changed`.
>       +
>       +    Rename dis* to action* and replace literal numericals with macros.
>       +    The old names came from when dis* (which I think was short for discard)
>       +    was treated like a boolean, but over time it grew into a ternary state
>       +    machine. The result was confusing because dis* and rchg* both used 0/1
>       +    values with different meanings.
>       +
>       +    The new names and macros make the states explicit. nm is short for
>       +    number of matches, and mlim is a heuristic limit:
>       +
>       +      nm == 0       -> action[i] = DISCARD     -> changed[i] = true
>       +      0 < nm < mlim -> action[i] = KEEP        -> changed[i] = false
>       +      nm >= mlim    -> action[i] = INVESTIGATE -> changed[i] = xdl_clean_mmatch()
>       +
>       +    When need_min is true, only DISCARD and KEEP occur because the limit
>       +    is effectively infinite.
>        
>            Best-viewed-with: --color-words
>            Signed-off-by: Ezekiel Newren <[email-masked]>
>       @@ xdiff/xprepare.c
>         #define XDL_GUESS_NLINES1 256
>         #define XDL_GUESS_NLINES2 20
>         
>       -+#define NONE 0
>       -+#define SOME 1
>       -+#define TOO_MANY 2
>       ++#define DISCARD 0
>       ++#define KEEP 1
>       ++#define INVESTIGATE 2
>         
>         typedef struct s_xdlclass {
>         	struct s_xdlclass *next;
>       @@ xdiff/xprepare.c: void xdl_free_env(xdfenv_t *xe) {
>         
>         
>        -static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
>       -+static bool xdl_clean_mmatch(uint8_t const *matches, long i, long s, long e) {
>       ++static bool xdl_clean_mmatch(uint8_t const *action, long i, long s, long e) {
>         	long r, rdis0, rpdis0, rdis1, rpdis1;
>         
>         	/*
>        -	 * Limits the window the is examined during the similar-lines
>        -	 * scan. The loops below stops when dis[i - r] == 1 (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.
>        +	 * Limits the window that is examined during the similar-lines
>       -+	 * scan. The loops below stops when matches[i - r] == SOME (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.
>       ++	 * 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;
>        @@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, long e) {
>         
>         	/*
>         	 * Scans the lines before 'i' to find a run of lines that either
>        -	 * have no match (dis[j] == 0) or have multiple matches (dis[j] > 1).
>        -	 * Note that we always call this function with dis[i] > 1, so the
>       -+	 * have no match (matches[j] == NONE) or have multiple matches (matches[j] == TOO_MANY).
>       -+	 * Note that we always call this function with matches[i] == TOO_MANY, so the
>       - 	 * current line (i) is already a multimatch line.
>       +-	 * current line (i) is already a multimatch line.
>       ++	 * 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 (!dis[i - r])
>       -+		if (matches[i - r] == NONE)
>       ++		if (action[i - r] == DISCARD)
>         			rdis0++;
>        -		else if (dis[i - r] == 2)
>       -+		else if (matches[i - r] == TOO_MANY)
>       ++		else if (action[i - r] == INVESTIGATE)
>         			rpdis0++;
>        -		else
>       -+		else if (matches[i - r] == SOME)
>       ++		else if (action[i - r] == KEEP)
>         			break;
>        +		else
>       -+			BUG("Illegal value for matches[i - r]");
>       ++			BUG("Illegal value for action[i - r]");
>         	}
>         	/*
>       - 	 * If the run before the line 'i' found only multimatch lines, we
>       +-	 * If the run before the line 'i' found only multimatch lines, we
>        -	 * return 0 and hence we don't make the current line (i) discarded.
>       -+	 * 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
>       +-	 * We want to discard multimatch lines only when they appear in the
>        -	 * middle of runs with nomatch lines (dis[j] == 0).
>       -+	 * middle of runs with nomatch lines (matches[j] == NONE).
>       ++	 * 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 (!dis[i + r])
>       -+		if (matches[i + r] == NONE)
>       ++		if (action[i + r] == DISCARD)
>         			rdis1++;
>        -		else if (dis[i + r] == 2)
>       -+		else if (matches[i + r] == TOO_MANY)
>       ++		else if (action[i + r] == INVESTIGATE)
>         			rpdis1++;
>        -		else
>       -+		else if (matches[i + r] == SOME)
>       ++		else if (action[i + r] == KEEP)
>         			break;
>        +		else
>       -+			BUG("Illegal value for matches[i + r]");
>       ++			BUG("Illegal value for action[i + r]");
>         	}
>         	/*
>       - 	 * If the run after the line 'i' found only multimatch lines, we
>       +-	 * If the run after the line 'i' found only multimatch lines, we
>        -	 * return 0 and hence we don't make the current line (i) discarded.
>       -+	 * return false and hence we don't make the current line (i) discarded.
>       ++	 * 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 0;
>       @@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, l
>         	xdlclass_t *rcrec;
>        -	char *dis, *dis1, *dis2;
>        -	int need_min = !!(cf->flags & XDF_NEED_MINIMAL);
>       -+	uint8_t *matches1, *matches2;
>       -+	int status = 0;
>       ++	uint8_t *action1 = NULL, *action2 = NULL;
>        +	bool need_min = !!(cf->flags & XDF_NEED_MINIMAL);
>       ++	int ret = 0;
>         
>        -	if (!XDL_CALLOC_ARRAY(dis, xdf1->nrec + xdf2->nrec + 2))
>        -		return -1;
>        -	dis1 = dis;
>        -	dis2 = dis1 + xdf1->nrec + 1;
>       -+	matches1 = NULL;
>       -+	matches2 = NULL;
>       -+
>        +	/*
>        +	 * Create temporary arrays that will help us decide if
>        +	 * changed[i] should remain 0 or become 1.
>        +	 */
>       -+	if (!XDL_CALLOC_ARRAY(matches1, xdf1->nrec + 1)) {
>       -+		status = -1;
>       ++	if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {
>       ++		ret = -1;
>        +		goto cleanup;
>        +	}
>       -+	if (!XDL_CALLOC_ARRAY(matches2, xdf2->nrec + 1)) {
>       -+		status = -1;
>       ++	if (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) {
>       ++		ret = -1;
>        +		goto cleanup;
>        +	}
>         
>        +	/*
>       -+	 * Initialize temporary arrays with NONE, SOME, or TOO_MANY.
>       ++	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
>        +	 */
>         	if ((mlim = xdl_bogosqrt(xdf1->nrec)) > XDL_MAX_EQLIMIT)
>         		mlim = XDL_MAX_EQLIMIT;
>       @@ xdiff/xprepare.c: static int xdl_clean_mmatch(char const *dis, long i, long s, l
>         		rcrec = cf->rcrecs[recs->ha];
>         		nm = rcrec ? rcrec->len2 : 0;
>        -		dis1[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;
>       -+		matches1[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ? TOO_MANY: SOME;
>       ++		action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
>         	}
>         
>         	if ((mlim = xdl_bogosqrt(xdf2->nrec)) > XDL_MAX_EQLIMIT)
>       @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
>         		rcrec = cf->rcrecs[recs->ha];
>         		nm = rcrec ? rcrec->len1 : 0;
>        -		dis2[i] = (nm == 0) ? 0: (nm >= mlim && !need_min) ? 2: 1;
>       -+		matches2[i] = (nm == 0) ? NONE: (nm >= mlim && !need_min) ? TOO_MANY: SOME;
>       ++		action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
>         	}
>         
>        +	/*
>       @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
>         	     i <= xdf1->dend; i++, recs++) {
>        -		if (dis1[i] == 1 ||
>        -		    (dis1[i] == 2 && !xdl_clean_mmatch(dis1, i, xdf1->dstart, xdf1->dend))) {
>       -+		if (matches1[i] == SOME ||
>       -+		    (matches1[i] == TOO_MANY && !xdl_clean_mmatch(matches1, i, xdf1->dstart, xdf1->dend))) {
>       ++		if (action1[i] == KEEP ||
>       ++		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
>         			xdf1->rindex[nreff++] = i;
>       -+			/* changed[i] remains 0 */
>       ++			/* changed[i] remains 0, i.e. keep */
>         		} else
>         			xdf1->changed[i] = 1;
>       ++			/* i.e. discard */
>         	}
>       -@@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>       + 	xdf1->nreff = nreff;
>         
>         	for (nreff = 0, i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart];
>         	     i <= xdf2->dend; i++, recs++) {
>        -		if (dis2[i] == 1 ||
>        -		    (dis2[i] == 2 && !xdl_clean_mmatch(dis2, i, xdf2->dstart, xdf2->dend))) {
>       -+		if (matches2[i] == SOME ||
>       -+		    (matches2[i] == TOO_MANY && !xdl_clean_mmatch(matches2, i, xdf2->dstart, xdf2->dend))) {
>       ++		if (action2[i] == KEEP ||
>       ++		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
>         			xdf2->rindex[nreff++] = i;
>       -+			/* changed[i] remains 0 */
>       ++			/* changed[i] remains 0, i.e. keep */
>         		} else
>         			xdf2->changed[i] = 1;
>       ++			/* i.e. discard */
>         	}
>         	xdf2->nreff = nreff;
>         
>        -	xdl_free(dis);
>        +cleanup:
>       -+	xdl_free(matches1);
>       -+	xdl_free(matches2);
>       ++	xdl_free(action1);
>       ++	xdl_free(action2);
>         
>        -	return 0;
>       -+	return status;
>       ++	return ret;
>         }
>         
>         
>   13:  975e845bfa ! 12:  83e1ace5bd xdiff: change type of xdfile_t.changed from char to bool
>       @@ Commit message
>            xdiff: change type of xdfile_t.changed from char to bool
>        
>            The only values possible for 'changed' is 1 and 0, which exactly maps
>       -    to a bool type. It might not look like this is the case because
>       -    matches1 and matches2 (which use to be dis1, and dis2) were also char
>       -    and were assigned numerical values within a few lines of 'changed'
>       -    (what used to be rchg).
>       +    to a bool type. It might not look like this because action1 and action2
>       +    (which use to be dis1, and dis2) were also of type char and were
>       +    assigned numerical values within a few lines of 'changed' (what used to
>       +    be rchg).
>        
>       -    Using NONE, SOME, TOO_MANY for matches1[i]/matches2[j], and true/false
>       +    Using DISCARD/KEEP/INVESTIGATE for action1[i]/action2[j], and true/false
>            for changed[k] makes it clear to future readers that these are
>            logically separate concepts.
>        
>       @@ xdiff/xdiffi.c: static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g)
>         
>         		while (xdf->changed[g->start - 1])
>         			g->start--;
>       +@@ xdiff/xdiffi.c: int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) {
>       +
>       + int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {
>       + 	xdchange_t *cscr = NULL, *xch;
>       +-	char *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed;
>       ++	bool *changed1 = xe->xdf1.changed, *changed2 = xe->xdf2.changed;
>       + 	long i1, i2, l1, l2;
>       +
>       + 	/*
>        
>         ## xdiff/xhistogram.c ##
>        @@ xdiff/xhistogram.c: redo:
>       @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
>        -	 * changed[i] should remain 0 or become 1.
>        +	 * changed[i] should remain false, or become true.
>         	 */
>       - 	if (!XDL_CALLOC_ARRAY(matches1, xdf1->nrec + 1)) {
>       - 		status = -1;
>       + 	if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {
>       + 		ret = -1;
>        @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>         
>         	/*
>       @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *
>         	 */
>         	for (nreff = 0, i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
>         	     i <= xdf1->dend; i++, recs++) {
>       - 		if (matches1[i] == SOME ||
>       - 		    (matches1[i] == TOO_MANY && !xdl_clean_mmatch(matches1, i, xdf1->dstart, xdf1->dend))) {
>       + 		if (action1[i] == KEEP ||
>       + 		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
>         			xdf1->rindex[nreff++] = i;
>       --			/* changed[i] remains 0 */
>       -+			/* changed[i] remains false */
>       +-			/* changed[i] remains 0, i.e. keep */
>       ++			/* changed[i] remains false, i.e. keep */
>         		} else
>        -			xdf1->changed[i] = 1;
>        +			xdf1->changed[i] = true;
>       + 			/* i.e. discard */
>         	}
>         	xdf1->nreff = nreff;
>       -
>        @@ xdiff/xprepare.c: static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
>       - 		if (matches2[i] == SOME ||
>       - 		    (matches2[i] == TOO_MANY && !xdl_clean_mmatch(matches2, i, xdf2->dstart, xdf2->dend))) {
>       + 		if (action2[i] == KEEP ||
>       + 		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
>         			xdf2->rindex[nreff++] = i;
>       --			/* changed[i] remains 0 */
>       -+			/* changed[i] remains false */
>       +-			/* changed[i] remains 0, i.e. keep */
>       ++			/* changed[i] remains false, i.e. keep */
>         		} else
>        -			xdf2->changed[i] = 1;
>        +			xdf2->changed[i] = true;
>       + 			/* i.e. discard */
>         	}
>         	xdf2->nreff = nreff;
>       -
>        
>         ## xdiff/xtypes.h ##
>        @@ xdiff/xtypes.h: typedef struct s_xdfile {
>